Term graph rewriting

Ronan Sleep

(University of East Anglia)

Term graph rewriting refers to techniques and theories for representing terms and term rewriting rules as graphs and graph rewriting rules. Many modern programming paradigms - most notably the functional and logic paradigms - have term rewriting at their heart, although the control regimes and semantics are very different. Practical implementations of these languages share subterms using pointers, and the machine code for such programs manipulates shared structures which we call term graphs. Reasoning about the correctness and efficiency of such representations relies on our ability to reason about term graph rewriting systems, and to relate them to other semantic models. Used in this way, term graph rewriting offers a model of computation which is closer to real implementations than pure term rewriting, but which avoids much unnecessary machine detail. The use of term graph rewriting to implement term rewriting will be illustrated, and some results concerning the correctness of term graph rewriting for term rewriting presented.
Thursday 18th November 1993, 14:30
Seminar Room 322
Department of Computer Science