The Concept of Supercompilation
The concept of a supercompilation is due to Valentin Turchin.
The purpose of a supercompiler
The purpose of a supercompiler
A supercompiler is a program transformer that traces the possible generalized histories of computation by the source program, and builds an equivalent target program, whose structure is, in a sense, "simpler" than the structure of the source program. The simplification is achieved by removing certain "redundant" actions from the source program.
The "simplifications" in the program that can be achieved by a supercompiler
The "simplifications" in the program that can be achieved by a supercompiler
- Redundant code elimination.
- Performing operations on data that are known at the time of supercompilation.
- Removing intermediate data structures.
- Transforming multi-pass algorithms to one-pass algorithms.
Metasystem Transition Theory
Metasystem Transition Theory
The "philosophy" behind a supercompiler is Metasystem Transition Theory (MSTT).
References
References
Note. Some documents are in the format DjVu, which is especially convenient for distributing scanned documents. DjVu documents can be viewed with WinDjView & MacDjView or DJVIEW4.
- V.F.Turchin. The Language Refal -- The Theory of Compilation and Metasystem Analysis. Curant Institute of Mathematics. Technical report #018, NY, 1980. DJVU, PDF
- V.F.Turchin. The concept of a supercompiler. ACM Transactions on Programming Languages and Systems, 8, pp.292-325, 1986. Link
- V.F.Turchin. Program transformation with metasystem transitions. Journal of Functional Programming 3(3) pp.283-313, July 1993. Link
- V.F.Turchin. Supercompilation: Techniques and Results. In: Perspectives of System Informatics, pp. 229-248, LNCS, vol 1181, Springer, 1996. Link
- V.F.Turchin. Metacomputation: Metasystem Transitions plus Supercompilation. In: Partial Evaluation, pp. 481-510, LNCS, vol. 1110, Springer, 1996. Link