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.