Stack-based Implementation of Narrowing

R. Loogen

	   An abstract stack machine for the implementation of narrowing
	   is presented. On the one hand, this machine can be seen as
	   an extension of a stack-based reduction machine for purely
	   functional languages by components that are necessary for the
	   realization of unification and backtracking. On the other hand,
	   the machine represents an extension of Warren's Prolog engine
	   that enables the handling of nested expressions and embodies
	   an optimized treatment of deterministic computations. As in
	   Warren's machine the central component of the machine is a
	   stack that contains environments, i.e. activation records of
	   function calls, and choice points to keep track of possible
	   alternative computations. It is ensured that choice points
	   always contain the minimal amount of information that
	   is necessary to restore a previous state on backtracking.
	   A complete specification of the machine and of the translation
	   of a sample language into abstract machine code is given. To
	   test the feasibility of the new implementation technique a
	   preliminary implementation has been developed in Miranda.