A Call-by-need Implementation of Syntax Directed Functional Programming

H. Fassbender, H. Vogler

	   This paper contributes to the field of functional programming
	   languages. We investigate the call-by-name and call-by-need
	   implementation of a restricted type of functional programming,
	   called syntax directed functional programming; the target of
	   this implementation is an abstract machine that is based on
	   nested stacks.  In fact, the technical kernel of this paper
	   is a refinement of an automata theoretical result that,
	   roughly speaking, investigates the well-known relationship
	   ``recursion = iteration + stack'' in the framework of tree
	   transducers. More precisely, in the underlying result the
	   class of functions computed by total deterministic macro
	   tree-to-string transducers with the call-by-name computation
	   strategy is characterized by total deterministic checking-tree
	   nested-stack transducers. Note that total deterministic
	   macro tree-to-string transducers are term rewriting systems
	   by means of which the reduction semantics of syntax directed
	   functional programming languages can be described.