Introduction
In the previous chapter we saw that pure term rewriting is not
adequate for term rewriting because of the lack of control over the
application of rules. Approaches for encoding such control within the
pure rewriting paradigm lead to functionalized control by means of
extra rules and constructors at the expense of traversal overhead and
at the loss of the separation of rules and strategies. We need a
mechanism that provides such control, but maintains the separation of
rules and strategies and keeps traversal overhead to a minimum. Such
a mechanism should allow strategies parameterized with selections from
the available rules.
Also we saw that many transformation problems can be solved by
alternative strategies such as a one-pass bottom-up or top-down
traversal. Others can be solved by selecting the rules that are
applied in an innermost normalization, rather than all the rules in a
specification. However, no fixed set of such alternative strategies
will be sufficient for dealing with all transformation problems.
Rather than providing one or a few fixed rewriting strategies, we need
to be able to
compose strategies from basic building blocks
with a few fundamental operators.
In program transformation, the basic building blocks are single
rewrite steps, for example defined by a rewrite rule. This chapter
introduces a set of operators for composing such single step
transformations into complex transformations. By allowing abstraction
over the basic transformation,
generic transformation
strategies can be defined. The combinators discussed in this
chapter cover sequential programming and type-specific
traversal. Extensions of this basic framework will be considered in
later chapters.
Preprint
Remarks
Lacks discussion of literature.