Metasystem Transitions + Supercompilation
The City College of New York
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.