Functional Languages with Logic Variables

Functional languages like Pure LISP and Haskell are very elegant, but this elegance can come at the expense of efficiency in some areas such as data structure manipulation. Some of these problems can be overcome in a very appealing way by adding logic variables to functional languages. Logic variables can be viewed as variables whose value is defined incrementally using constraint intersection. The addition of logic variables to functional languages gives the programmer the ability to define data structures incrementally through constraint intersection, which can make data structure manipulation more efficient while retaining the essence of the declarative approach.

Together with Arvind and Nikhil at MIT, we designed the dataflow language Id Nouveau which has a weak version of logic variables called I-structures. Both functional and logic programming languages have elegant denotational semantics, but it was not obvious to us that combining them resulted in languages with such desirable properties. In joint work with Prakash Panangaden and Radha Jagadeesan, we gave a formal semantic account of such languages using the notion of closure operators on a Scott domain. Radha Jagadeesan's thesis describes this work in more detail.

Once you get used to logic variables, you can find all kinds of neat uses for them. We have used them to model demand propagation in the implementation of lazy functional languages, which leads to a a very efficient way of implementing lazy functional languages on dataflow machines.

If you think of logic variables as write-once variables, you can generalize them in a natural way by combining multiple writes to a logic variable into a single update by using a commutative and associate operation (reduction operation) such as addition or multiplication. Kattamuri Ekanadham at IBM and I studied such generalizations - we called them accumulators.

Publications: