Part III
Strategies for Program Transformation
Programmable Rewriting Strategies
Contents
Introduction
Rewrite rules provide a good formalism for expressing basic program
transformation steps. However, rewriting has a number of
limitations. First, since most sets of rules are not confluent and/or
terminating, exhaustive application of rules is not adequate; more
careful control over the application of rewrite rules is needed.
Chapter In Control of Rewriting surveys several solutions to controlling
rewriting. Most solutions for the encoding of control suffer from a
substantial overhead in the definition of
traversals and/or
intertwine transformation rules and strategy. The paradigm of
programmable rewriting strategies provides a solution with
minimal overhead for traversal, while maintaining the separation of
rules and strategies.
Chapter Composing Strategies
to
Chapter Generic Traversal Strategies
introduce combinators for the
composition of programmable strategies.
Chapter Composing Strategies
introduces combinators for
sequential non-deterministic programming and for data type specific
traversal using congruence operators.
Chapter First Class Pattern Matching
reduces rewrite rules to the
more primitive strategy actions
match,
build, and
scope. The availability of
first class patterns allows
many other operations involving pattern matching. Data type specific
traversal with congruence operators does solve the separation between
rules and strategies, but not the overhead caused by the specification
of traversals.
Chapter Generic Traversal Strategies shows how
combinators for
generic traversal can concisely capture
traversal schemata independent of any object language.
Another limitation of rewriting is that rewrite rules are
context-free. That is, only local information available during the
pattern match can be used in a transformation step. In
Chapter Scoped Dynamic Rewrite Rules
the paradigm of rewriting strategies is
extended with
scoped dynamic rewrite rules, rules which are
generated at run-time to inherit context information.
