| Infinitary Rewriting and Cyclic Graphs (1995) | |||||||||||||||
Abstract | |||||||||||||||
| Infinitary rewriting allows infinitely large terms and infinitely long reduction sequences. There are two computational motivations for studying these: the infinite data structures implicit in lazy functional programming, and the use of rewriting of possibly cyclic graphs as an implementation technique for functional languages. We survey the fundamental properties of infinitary rewriting in orthogonal term rewrite systems, and its relation to cyclic graph rewriting. 1 Introduction Our interest in term and graph rewriting arises from functional languages and their implementation. Functional programs can be seen as term rewrite systems. 2 Terms can be thought of as trees. Representing these trees as graphs allows repeated subterms to be replaced by multiple pointers to the same subgraph. This optimisation has a dramatic effect when rewrite steps are performed. Whenever a variable appears more than once on the right-hand side of a rule, when that rule is applied to a graph multiple poi... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||