Old Program Transformation

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

• ProgramMigration
• ProgramSynthesis
  • Compilation
    • TranslationToIR^?
    • InstructionSelection
  • ProgramRefinement
• ReverseEngineering
  • ArchitectureExtraction
  • DocumentationGeneration
  • SoftwareVisualization
• ProgramAnalysis
  • ControlFlowAnalysis
  • DataFlowAnalysis
  • TypeAnalysis^?

Rephrasing scenarios

• ProgramNormalization
  • ProgramSimplification^?
  • ProgramDesugaring^?
  • AspectWeaving^?
• ProgramOptimization
  • ProgramSpecialization
  • FunctionInlining^?
  • CommonSubexpressionElimination^?
• ProgramRestructuring^?
  • ProgramRefactoring
  • SoftwareRenovation

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

• TheOnlineSurveyOfProgramTransformation