Embedding Prolog in Haskell

In joint work with Silvija Seres, I have found a small set of combinators that allow logic programs to be re-expressed as programs in a lazy functional programming language, with all the characteristic features of logic programming, including non-determinism, bi-directionality, and `logical variables'. These combinators enjoy a number of algebraic properties which serve as their specification, support program transformation, and allow a link to be made with the traditional semantics of logic programs based on the resolution principle.

The propositional part of logic programming is reflected in combinators that interpret propositional connectives in terms of a monad. One possibility for this monad is the monad of lazy lists, giving the familiar depth-first search strategy, but there are others that correspond to other strategies, including breadth-first search.