Functional Reading of Logic Programs

Silvija Seres (Oxford University Computing Laboratory, Wolfson Building, Parks Road, UK)

Michael Spivey (Oxford University Computing Laboratory, Wolfson Building, Parks Road, UK)

Abstract: 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.

Keywords: algebraic methods, functional embedding, logic programming, program transformation

Categories: D.1