Jungle Evaluation

Article type: Research Article

Authors: Habel, Annegret | Kreowski, Hans-Jörg | Plump, Detlef^{; *}

Affiliations: Fachbereich Mathematik und Informatik, Universität Bremen, D-2800 Bremen 33

Note: [*] Work of this author was supported by the ESPRIT-project PROSPECTRA, ref. # 390.

Abstract: 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.

DOI: 10.3233/FI-1991-15104

Journal: Fundamenta Informaticae, vol. 15, no. 1, pp. 37-60, 1991