Strategic Graph Rewriting -- Transforming and Traversing Terms with References

Eelco Visser and myself have a paper at the sixth international Workshop on Reduction Strategies in Rewriting and Programming (WRS'06), coming up next week.

Abstract

Some transformations and many analyses on programs are either difficult or unnatural to express using terms. In particular, analyses that involve type contexts, call- or control flow graphs are not easily captured in term rewriting systems. In this paper, we describe an extension to the System S term rewriting system that adds references. We show how references are used for graph rewriting, how we can express more transformations with graph-like structures using only local matching, and how references give a representation that is more natural for structures that are inherently graph-like. Furthermore, we discuss trade-offs of this extension, such as changed traversal termination and unexpected impact of reference rebinding.

bib - pdf