Program transformation
Encyclopedia
A program transformation is any operation that takes a computer program
and generates another program. In many cases the transformed program is required to be semantically equivalent to the original, relative to a particular formal semantics
and in fewer cases the transformations result in programs that semantically differ from the original in predictable ways.
While the transformations can be performed manually, it is often more practical to use a program transformation system (such as Coccinelle
, Stratego/XT
, TXL
, DMS
, ASF+SDF
or Fermat
), a tool that can accept and apply specifications of the required transformations. Program transformations may be specified as automated procedures that modify compiler data structures (e.g. abstract syntax trees) representing the program text, or may be specified more conveniently using patterns representing parameterized source code text fragments.
A practical requirement for source code
transformation systems is that they be able
to process programs written in a programming language
. The problem of building adequate
front ends for languages and supporting static analyses may be of equal difficulty as building the program transformation system itself.
A generalisation of semantic equivalence is the notion of program refinement:
one program is a refinement of another if it terminates on all the initial states
for which the original program terminates, and for each
such state it is guaranteed to terminate in a possible final state for the original program.
In other words, a refinement of a program is more defined and more deterministic
than the original program. If two programs are refinements of each other,
then the programs are equivalent.
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
and generates another program. In many cases the transformed program is required to be semantically equivalent to the original, relative to a particular formal semantics
Formal semantics of programming languages
In programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation...
and in fewer cases the transformations result in programs that semantically differ from the original in predictable ways.
While the transformations can be performed manually, it is often more practical to use a program transformation system (such as Coccinelle
Coccinelle (software)
Coccinelle is a tool to match and transform the source code of programs written in the programming language C. Coccinelle was initially used to aid the evolution of Linux; with support for changes to library application programming interfaces such as renaming a function, adding a function...
, Stratego/XT
Stratego/XT
Stratego/XT is a language and toolset for constructing stand-alone program transformation systems.It combines the Stratego transformation language with the XT toolset of transformation components, providing a framework for constructing stand-alone...
, TXL
TXL (programming language)
TXL is a special-purpose programming language originally designed by Charles Halpern-Hamu and James Cordy at the University of Toronto in 1985. The acronym "TXL" originally stood for "Turing eXtender Language" after the language's original purpose, the specification and rapid prototyping of...
, DMS
DMS Software Reengineering Toolkit
The DMS Software Reengineering Toolkit is a proprietary set of program transformation tools available for automating custom source program analysis, modification, translation or generation of software systems for arbitrary mixtures of source languages for large scale software systems.DMS has been...
, ASF+SDF
ASF+SDF Meta Environment
The ASF+SDF Meta-Environment is an IDE and toolset for interactive program analysis and transformation. It combines SDF , ASF and other technologies.Some of the features:...
or Fermat
FermaT Transformation System
The FermaT Transformation System is an industrial strength programtransformation system targeted at reverse engineering, program comprehensionand migration between programming languages...
), a tool that can accept and apply specifications of the required transformations. Program transformations may be specified as automated procedures that modify compiler data structures (e.g. abstract syntax trees) representing the program text, or may be specified more conveniently using patterns representing parameterized source code text fragments.
A practical requirement for source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
transformation systems is that they be able
to process programs written in a programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
. The problem of building adequate
front ends for languages and supporting static analyses may be of equal difficulty as building the program transformation system itself.
A generalisation of semantic equivalence is the notion of program refinement:
one program is a refinement of another if it terminates on all the initial states
for which the original program terminates, and for each
such state it is guaranteed to terminate in a possible final state for the original program.
In other words, a refinement of a program is more defined and more deterministic
than the original program. If two programs are refinements of each other,
then the programs are equivalent.
See also
- Code generation (compiler)
- Comparison of code generation toolsComparison of code generation toolsThis article compares variable metamodel code generation tools . Fixed metamodel code generation tools, such as UML tools, are excluded .- Technical :...
- Data transformationData transformationIn metadata and data warehouse, a data transformation converts data from a source data format into destination data.Data transformation can be divided into two steps:...
- Source-to-source compilerSource-to-source compilerA source-to-source compiler is a type of compiler that takes a high level programming language as its input and outputs a high level language. For example, an automatic parallelizing compiler will frequently take in a high level language program as an input and then transform the code and annotate...
- Source code generation
- Transformation languageTransformation languageA transformation language is a computer language designed to transform some input text in a certain formal language into a modified output text that meets some specific goal....
- FermaT Transformation SystemFermaT Transformation SystemThe FermaT Transformation System is an industrial strength programtransformation system targeted at reverse engineering, program comprehensionand migration between programming languages...