-- 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