Efficient Implementation of Narrowing and Rewriting

by Michael Hanus

Proc. International Workshop on Processing Declarative Knowledge (PDK'91), Springer LNAI 567, pp. 344-365, 1991
© Springer-Verlag

We present an efficient implementation method for a language that amalgamates functional and logic programming styles. The operational semantics of the language consists of resolution to solve predicates and narrowing and rewriting to evaluate functional expressions. The implementation is based on an extension of the Warren Abstract Machine (WAM). This extension causes no overhead for pure logic programs and allows the execution of functional programs by narrowing and rewriting with the same efficiency as their relational equivalents. Moreover, there are many cases where functional programs are more efficiently executed than their relational equivalents.

DVI (89 KB) Postscript (240 KB) BibTeX-Entry