The Implementation of Lazy Narrowing

Manuel M. T. Chakravarty, and Hendrik C. R. Lock

In J. Maluszunski and M. Wirsing, editors, Programming Language, Implementation, and Logic Programming, 3rd International Symposium PLILP'91, pp 123-134, LNCS 528, Springer-Verlag, 1991.

Lazy narrowing has been proposed as the operational model of functional logic languages. This paper presents a new abstract machine which implements lazy narrowing. The core of this machine consists of a conventional stack based architecture like the one used for imperative languages. Almost orthogonal extensions of this core implement the different concepts of functional logic languages. This simplifies the machine design to a great deal and reduces the instruction set which has been particularly designed to support the application of standard code generation techniques. By its orthogonality, it is achieved that unused features introduce only minimal overhead. As a result, when performing ground term reduction the machine enjoys the same characteristics as efficient graph reduction machines.

DVI version and PostScript version (12 pages)

This page is part of Manuel Chakravarty's WWW-stuff.