Program Transformation


A program is a structured object with semantics. The structure allows us to transform a program. The semantics gives us the means to compare programs and to reason about the validity of transformations. Semantics includes the extensional and intensional behaviour of a program. A programming language is a collection of programs. This is a rather broad definition that is designed to cover proper programming languages (with an operational interpretation), but also data formats and domain-specific languages.

Programming languages can be clustered into classes with structural and/or semantic similarities. One of the aims of a general framework for program transformation is to define transformations that are reusable across as wide a range of languages as possible. For example, the notion of variable and variable binding is shared by all programming languages. Transformations dealing with variables such as bound variable renaming, substitution, and unification can be defined in a very generic manner for all languages at once.

Program transformation is the act of changing one program into another. The term program transformation is also used for a formal description of an algorithm that implements program transformation. The language in which the program being transformed and the resulting program are written are called the source and target languages, respectively.

source language -> program transformation -> target language.

Program Transformation is also known as Generative Programming

Taxonomy of Program Transformations

Two different cases. One where the source and target language are different (translations) from scenarios where they are the me (rephrasings).


In a translation scenario a program is transformed from a source language into a program in a different target language.
Translation scenarios can be distinguished by their effect on the level of abstraction of a program. Examples of translation scenarios are synthesis, migration, reverse engineering, and analysis.

Program Synthesis

This class of transformations that lower the level of abstraction of a program.

Program Migration

Here a program is transformed to another language at the same level of abstraction. This can be a translation between dialects, for example, transforming a Fortran77 program to an equivalent Fortran90 program or a translation from one language to another, e.g., porting a Pascal program to C.

Reverse Engineering

The purpose is to extract from a low-level program a high-level program or specification, or at least some higher-level aspects. Reverse engineering raises the level of abstraction and is the dual of synthesis.

Program Analysis

This example reduces a program to one aspect such as its control-flow. Analysis can thus be considered a transformation to a sub-language or an aspect language.


Rephrasings are transformations that transform a program into a different program in the same language, i.e., source and target language are the same. In general, rephrasings try to say the same thing in different words thereby aiming at improving some aspect of the program, which entails that they change the semantics of the program. The main sub-scenarios of rephrasing are normalization, optimization, refactoring, and renovation.

Program Normalization

A normalization reduces a program to a program in a sub-language, with the purpose of decreasing its syntactic complexity.

Program Optimization

An optimization is a transformation that improves the run-time and/or space performance of a program. Examples of optimization are fusion, inlining, constant propagation, constant folding, common-subexpression elimination, and dead code elimination.

Program Refactoring

This is a transformation that improves the design of a program by restructuring it such that it becomes easier to understand while preserving its functionality.

Program Reflection

This is a transformation that changes a program to compute some aspect of the program itself. For instance, one can transform a program such that, in addition to its usual behaviour, the program also calculates a trace of its own execution. Other uses might include the generation of self-profiling programs.

Software Renovation

In software renovation the extensional behaviour of a program is changed in order to repair an error or to bring it up to date with respect to changed requirements. Examples are repairing a Y2K bug, or converting a program to deal with the Euro.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.