Metacompilation

Metacompilation is a computation which involves metasystem transitions (MST) from a computing machine M to a metamachine M' which controls, analyzes and imitates the work of M. Semantics-based program transformation, such as partial evaluation and supercompilation (SCP), is metacomputation. Metasystem transitions may be repeated, as when a program transformer gets transformed itself. In this manner MST hierarchies of any height can be formed. The Fox paper reviews one strain of research which was started in Russia by Valentin Turchin's REFAL system in the late 1960s-early 1970s and became known for the development of supercompilation as a distinct method of program transformation. After a brief description of the history of this research line, the paper concentrates on those results and problems where supercompilation is combined with repeated metasystem transitions.