Definition
Program transformation is the act of changing one program into another. The term
program transformation is also used for a program, or any other 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. One can distinguish scenarios where the source and target language are different (
translations) from scenarios where they are the same (
rephrasings).
Transformation Scenarios
Program transformation is used in many areas of
SoftwareEngineering, including
CompilerConstruction?,
SoftwareVisualization,
DocumentationGeneration, and automatic
SoftwareRenovation. At the basis of all these different applications lie the main program transformation
scenarios of translation and rephrasing. These main scenarios can be refined into a number of typical
sub-scenarios that are characterized by the
constraints imposed on the main scenarios.
Translation
In a
translating scenario a program is transformed from a source language into a program in a
different target language. Examples of translating scenarios are synthesis, migration, compilation, analysis.
In
ProgramSynthesis an implementation is derived from a high-level specification by semantics preserving transformations. That is, it is guaranteed that the implementation satisfies the specification. A prime example of program synthesis is parser generation.
In
ProgramMigration a program is transformed to another language, while preserving all meaning. For example, transforming a Fortran77 program to an equivalent Fortran90 program.
Compilation is a form of synthesis in which a program in a high-level language is transformed to a program in a more low-level language.
In
ProgramAnalysis a program is reduced to some property, or value. Type-checking is an example of program analysis.
Rephrasing
In a
rephrasing scenario a program is transformed into a different program in the
same language, i.e., source and target language are the same. Examples of rephrasing scenarios are normalization, renovation, refactoring and
optimization In a
ProgramNormalization a program is reduced to a program in a sub-language. In
SoftwareRenovation some aspect of a program is improved. For example, repairing a Y2K bug. A
ProgramRefactoring is a meaning preserving modification that improves the design. A
ProgramOptimization is a meaning
preserving modification that improves the run-time and/or space performance of the program.
CompilationByTransformation is a paradigm in which many components of a compilers are defined as rephrasing transformations.
A Taxonomy of Transformation Scenarios
The program transformation scenarios discussed above can be organized in a taxonomy of sub-scenarios.
Translating scenarios
Rephrasing scenarios
- ProgramImprovement?: changes some aspect of the program
- ProgramNormalization: reduces program to a subset of the language
- ProgramDesugaring?: express language constructs (syntactic sugar) in terms of other language constructs
ProgramAnalysis is a scenario that is not quite transformation since the result of analysis is not another program, but some property of the program. Program analysis has things in common with program transformation
Other Definitions
The
FreeOnLineDictionaryOfComputing describes program transformation as:
The systematic development of efficient programs from high-level specifications by meaning-preserving program manipulations. Also known as optimisation.
WolframKahl (at
http://ist.unibw-muenchen.de/kahl/progtrans.html) defines program transformation as:
Program transformation systematically changes a program within one language into a different shape, usually preserving its semantics. The aim usually is to improve efficiency.
These definitions correspond to the notions
ProgramSynthesis or
ProgramOptimization above. The reason for choosing a wider scope of program transformation is that the other scenarios discussed above have much in common with the narrower notion of
ProgramOptimization; improving the efficiency is not the only application of program transformation techniques.
Tools
Many program transformations can be implemented by means of
ProgramTransformationTools that support the description of program transformations at a (reasonably) high level of abstraction.
See Also
CategoryTransformation | Contributions by
EelcoVisser,
JoostVisser