Embedding Prolog in Haskell
Silvija Seres and Michael Spivey:
We propose an embedding of logic programming into lazy
functional programming in which each predicate in a Prolog
program becomes a Haskell function, in such a way that
both the declarative and the procedural reading of the
Prolog predicate are preserved.
The embedding computes by means of operations on lazy
lists. The state of each step in computation is passed on
as a stream of answer substitutions, and all the logic
operators of Prolog are implemented by explicit Haskell
operators on these streams. The search strategy can be
changed by altering the basic types of the embedding and
the implementation of these operators. This model results
in a perspicuous semantics for logic programs, and serves
as a good example of modularisation in functional
programming.