Compiling Logic Programs with Equality

by Michael Hanus

2nd International Workshop on Programming Language Implementation and Logic Programming (PLILP'90), Springer LNCS 456, pp. 387-401, 1990
© Springer-Verlag

Horn clause logic with equality is an amalgamation of functional and logic programming languages. A sound and complete operational semantics for logic programs with equality is based on resolution to solve literals, and rewriting and narrowing to evaluate functional expressions. This paper proposes a technique for compiling programs with these inference rules into programs of a low-level abstract machine which can be efficiently executed on conventional architectures. The presented approach is based on an extension of the Warren abstract machine (WAM). In our approach pure logic programs without function definitions are compiled in the same way as in the WAM-approach, and for logic programs with function definitions particular instructions are generated for occurrences of functions inside clause bodies. In order to obtain an efficient implementation of functional computations, a stack of occurrences of function symbols in goals is managed by the abstract machine. The compiler generates the necessary instructions for the efficient manipulation of the occurrence stack from the given equational logic program.

DVI (83 KB) Postscript (211 KB) BibTeX-Entry