Home » forums » LtU Forum

literature on commutative lifted boolean operators

Even in a lazy language like Haskell, lifted boolean operators like 'and' are not commutative. What I mean is that they're commutative only as long as bottom is not involved. In that case, for example, 'and' and 'flip and' are not interchangeable. This causes problems in certain applications like trying to simulate certain cyclic logic circuits. To a great extent you can avoid these problems by carefully thinking about which input to 'and' you want to use, but I'm interested in designing a system where this is not necessary.

I've just finished coding up a system that has a commutative and. It consist of two parts: a new 'and' called 'land' that uses Maybe Bool as its data type and a discipline for programming with 'land' that requires you to iterate until you find a fixed point before returning a result.

I'm looking for some references to papers, books, web sites, etc. that might help me understand more about this topic and not reinvent the wheel any further than I already have. I'm also interested in the generalized version of this topic, i.e. beyond boolean operators: "when conventional laziness just isn't lazy enough." I've done some Googling but haven't seem to hit upon the "magic words."

By bdenckla at 2005-10-07 17:44 | LtU Forum | previous forum topic | next forum topic | other blogs | 6772 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Parallel Or

Most of the research on this topic talks about "Parallel Disjunction", which is the or-counterpart of the 'land' operator you describe. I'm not familiar enough to reference specific papers, but a search for "Parallel Disjunction" turns up lots of stuff.

Such parallel operators are definitely the route to "maximum lazyness", and it's easy to envision building higher-level operations from them, especially if nondeterminism is allowed. For example, a parallel "find" operation could find some occurance of a value in a list provided that at least one non-divergent such value is present.

One thing to keep in mind is that the combinatorical performance impact of these parallel operators can be quite dramatic, having to execute an unbounded amount of divergent code while searching for one convergent result. It's quite easy to construct programs this way that are convergent in principle but not on any available hardware.

By Tim Sweeney at Fri, 2005-10-07 19:02 | login or register to post comments