Compiler-based Implementation of Syntax-Directed Functional Programming

K. Gladitz, H. Fassbender, H. Vogler

	   We consider particular functional programs in which on the one
	   hand the recursion is restricted to syntax-directed recursion
	   and on the other hand simultaneous recursion and nesting of
	   function calls in parameter positions of other functions is
	   allowed. For such programs called syntax-directed functional
	   programs, we formalize a compiler- based implementation of
	   the call-by-name computation strategy. The machine involved
	   in this implementation, called syntax-directed runtime-stack
	   machine, is minimal in the sense that it computes exactly
	   the class sdFun of functions which are expressible by
	   syntax- directed functional programs. We verify this
	   minimality property by showing a one-to-one correspondence
	   between the implementation presented in this paper, and an
	   interpreter-based implementation of syntax-directed functional
	   programs on checking-tree nested-stack transducers. It is
	   known from the literature that such transducers characterize
	   in a formal sense the class sdFun.