E. Visser, Z.-e.-A. Benaissa, and A. Tolmach. Building program optimizers with rewriting strategies. In
Proceedings of the third ACM SIGPLAN International Conference on Functional Programming (ICFP'98), pages 13--26. ACM Press, September 1998.
Abstract
We describe a language for defining term rewriting strategies,
and its application to the production of program optimizers.
Valid transformations on program terms can be described by a
set of rewrite rules; rewriting strategies are used to
describe when and how the various rules should be applied in
order to obtain the desired optimization effects. Separating
rules from strategies in this fashion makes it easier to
reason about the behavior of the optimizer as a whole,
compared to traditional monolithic optimizer implementations.
We illustrate the expressiveness of our language by using it
to describe a simple optimizer for an ML-like intermediate
representation.
The basic strategy language uses operators such as sequential
composition, choice, and recursion to build transformers from
a set of labeled unconditional rewrite rules. We also define
an extended language in which the side-conditions and
contextual rules that arise in realistic optimizer
specifications can themselves be expressed as strategy-driven
rewrites. We show that the features of the basic and extended
languages can be expressed by breaking down the rewrite rules
into their primitive building blocks, namely matching and
building terms in variable binding environments. This gives
us a low-level core language which has a clear semantics, can
be implemented straightforwardly and can itself be optimized.
The current implementation generates C code from a strategy
specification.
Download
CategoryPaper