A new revision of this paper is available under the title A Survey of Strategies in Rule Based Program Transformation Systems.

CategoryPaper | -- EelcoVisser - 14 May 2001

-- EelcoVisser - 12 Mar 2004

EelcoVisser. **A Survey of Rewriting Strategies in Program Transformation Systems**. Draft. February 23, 2003 (pdf)

**Abstract**

Program transformation is used in a wide range of applications
including compiler construction, optimization, program synthesis,
refactoring, software renovation, and reverse engineering. In the
realization of a program transformation system for a certain type of
transformation, design choices must be made regarding the
representation of programs and the paradigm for implementation of
transformations. This paper gives a taxonomy of the application areas
of program transformation, discusses considerations to be made in the
implementation of program transformation systems, especially focussing
on the specification of transformation *strategies*.

Complex program transformations are achieved through a number of
consecutive modifications of a program. Basic modifications can be
modeled by rewrite rules, i.e., rules that rewrite a program
representation. A transformation *strategy* is an algorithm for
choosing a path in the rewrite relation induced by a set of rules.
The development of strategies in program transformation systems is
illustrated by a discussion of the support for strategies in several
typical systems.

An earlier version appeared as

E. Visser. A survey of rewriting strategies in program transformation systems. In B. Gramlich and S. Lucas, editors, Workshop on Reduction Strategies in Rewriting and Programming (WRS'01), volume 57 of Electronic Notes in Theoretical Computer Science, Utrecht, The Netherlands, May 2001. Elsevier Science Publishers.

**Abstract**

Program transformation is used in a wide range of applications including compiler construction, optimization, program synthesis, refactoring, software renovation, and reverse engineering. Complex program transformations are achieved through a number of consecutive modifications of a program. Transformation rules define basic modifications. A transformation strategy is an algorithm for choosing a path in the rewrite relation induced by a set of rules. This paper surveys the support for the definition of strategies in program transformation systems. After a discussion of kinds of program transformation and choices in program representation, the basic elements of a strategy system are discussed and the choices in the design of a strategy language are considered. Several styles of strategy systems as provided in existing languages are then analyzed.

**Download**

CategoryPaper | -- EelcoVisser - 14 May 2001