Metacompilation:Metasystem Transitions

Metacomputation is a computation which involves metasystem transitions(MST for short) 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 itsef. In this manner MST hierarchies of any height can be formed. The paper reviews one strain of research which was started in Russia 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.

Keywords: program transformation, supercompilation, metacomputation, self-application, metasystem transition, MST-schemes, metacode, pattern-matching graphs, Refal.

First of all, I want to thank the organizers of this seminar for inviting me to review the history and the present state of the work on supercompilation and metasystem transitions. I do believe that these two notions should be of primary importance for the seminar, because they indicate the directions of further development and generalization of the two key notions most familiar to the participants: supercompilation is a development and generalization of partial evaluation, while metasystem transition is in the same relation to self-application. For myself, however, the order of appearance of these keywords was opposite: I started from the general concept of metasystem transition (MST for short), and my consequent work in computer science has been an application and concretization of this basic idea.