HOUSE_OVERSIGHT_013237.jpg

18.3 Self-Modification via Supercompilation
321

Supercompilation is an innovative and general approach to global program optimization
initially developed by Valentin Turchin. In its simplest form, it provides an algorithm that
takes in a piece of software and output another piece of software that does the same thing,
but far faster and using less memory. It was introduced to the West in Turchin's 1986 technical
paper "The concept of a supercompiler" [TV96], and since this time the concept has been avidly
developed by computer scientists in Russia, America, Denmark and other nations. Prior to 1986,
a great deal of work on supercompilation was carried out and published in Russia; and Valentin
Turchin, Andrei Klimov and their colleagues at the Keldysh Institute in Russia developed a
supercompiler for the Russian programming language Refal. Since 1998 these researchers and
their team at Supercompilers LLC have been working to replicate their achievement for the
more complicated but far more commercially significant language Java. It is a large project
and completion is scheduled for early 2003. But even at this stage, their partially complete
Java supercompiler has had some interesting practical successes – including the use of the
supercompiler to produce efficient Java code from CogPrime combinator trees.

The radical nature of supercompilation may not be apparent to those unfamiliar with the
usual art of automated program optimization. Most approaches to program optimization involve
some kind of direct program transformation. A program is transformed, by the step by step
application of a series of equivalences, into a different program, hopefully a more efficient one.
Supercompilation takes a different approach. A supercompiler studies a program and constructs
a model of the program's dynamics. This model is in a special mathematical form, and it can,
in most cases, be used to create an efficient program doing the same thing as the original one.

The internal behavior of the supercompiler is, not surprisingly, quite complex; what we will
give here is merely a brief high-level summary. For an accessible overview of the supercompila-
tion algorithm, the reader is referred to the article "What is Supercompilation?" [1]

18.3.1 Three Aspects of Supercompilation

There are three separate levels to the supercompilation idea: first, a general philosophy; second
a translation of this philosophy into a concrete algorithmic framework; and third, the manifold
details involved making this algorithmic framework practicable in a particular programming
language. The third level is much more complicated in the Java context than it would be for
Sasha, for example.

The key philosophical concept underlying the supercompiler is that of a metasystem transi-
tion. In general, this term refers to a transition in which a system that previously had relatively
autonomous control, becomes part of a larger system that exhibits significant controlling influ-
ence over it. For example, in the evolution of life, when cells first become part of a multicellular
organism, there was a metasystem transition, in that the primary nexus of control passed from
the cellular level to the organism level.

The metasystem transition in supercompilation consists of the transition from considering
a program in itself, to considering a metaprogram which executes another program, treating
its free variables and their interdependencies as a subject for its mathematical analysis. In
other words, a metaprogram is a program that accepts a program as input, and then runs
this program, keeping the inputs in the form of free variables, doing analysis along the way
based on the way the program depends on these variables, and doing optimization based on
this analysis. A CogPrime schema does not explicitly contain variables, but the inputs to the

HOUSE_OVERSIGHT_013237