Jungle evaluation. (English) Zbl 0661.68016

Recent trends in data type specification. Specification of abstract data types, Sel. Pap. 5th Workshop, Gullane/UK 1987, Lect. Notes Comput. Sci. 332, 92-112 (1988).
[For the entire collection see Zbl 0653.00015.]
Jungle evaluation is proposed as a new graph rewriting approach to the evaluation of functional expressions and, in particular, of algebraically specified operations. Jungles - being intuitively forests of coalesced trees with shared substructures - are certain acyclic hypergraphs (or equivalently, bipartite graphs) the nodes and edges of which are labeled with the sorts and operation symbols of a signature. Jungles are manipulated and evaluated by the application of jungle rewrite rules, which generalize equations or, more exactly, term rewrite rules.
Indeed, jungle evaluation turns out to be a compromise between term rewriting and graph rewriting displaying some favorable properties: the inefficiency of term rewriting is partly avoided while the possibility of structural induction is maintained, and a good part of the existing graph grammar theory is applicable so that there is some hope that the rich theory of term rewriting is not lost forever without a substitute.


68N99 Theory of software
68N20 Theory of compilers and interpreters


Zbl 0653.00015