Compiler-based implementation of syntax-directed functional programming
Katia Gladitz, Heinz Faßbender, Heiko Vogler · OPen Access Repositorium der Universität Ulm (OPARU) (Ulm University) · 1991
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 are 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.