Supercompilation

• An excerpt from Supercompiling Java Programs by Ben Goertzel, Andrei Klimov, Arkady Klimov, April 2002, SuperCompilers, LCC - White Paper:

  Partial evaluation vs. Supercompilation

  We discussed above the global program optimization technique known as partial evaluation or partial evaluation[sic]. It is best to consider this simpler approach, not as an alternative to supercompilation, but rather as a special case of supercompilation, important yet severely limited in scope.

  In essence, the difference between partial evaluation and supercompilation is that the former requires a purely static analysis to decide which parts of code will be optimized out at specialization time, whereas the latter, via the process of metacomputation, makes decisions using a much larger information set, including information perceivable only during the course of execution. Partial evaluation is dependent upon a type of program analysis called Binding Time Analysis (BTA), which has no access to the concrete values taken on by local variables in a program as it executes, and hence does not use the maximum information available at a given point in the execution of a program.

  Specifically, in practice, BTA performs separation of program code into two types of fragments:

  • Those which can be executed based on variable values known at specialization time (these are annotated S, for static )
  • Those which cannot be thus executed, and which are therefore left in the residual program, the part of the program that is not modified by the partial evaluation process (these are annotated D, for dynamic)

  In the case of complex real-world programs, only a very small percentage of code can be specialized in this manner, which means that partial evaluation in and of itself is often of relatively limited utility.

  On the other hand, the essence of supercompilation is driving performed without knowing any information in advance (besides the program code itself). The only information required by supercompilation is that which is created dynamically via configuration analysis (though some a priori information on method properties may be useful in certain cases). Driving works perfectly well with program fragments that cannot be specialized with static ally separated binding times.

  The step from partial evaluation to supercompilation is a large one: on the one hand, a purely static analysis of variable-value relationships; on the other, a full-on metacomputation framework in which a program is executed by another program, keeping records and making analyses as it goes along. So far, however, nobody has found any significant intermediate forms of global program optimization. A few small simplifications of supercompilation may be identified, but by and large, if one wants to go beyond the simple analyses obtainable through partial evaluation, one has to pass through the metasystem transition to supercompilation.

Some other relevant papers:

• "Introduction to Supercompilation"
  • D-364 abstract
  • paper (.ps.gz)
• A Roadmap to Metacomputation by Supercompilation.
• Occam's Razor in Metacomputation: the Notion of a Perfect Process Tree.
• Metacomputation-based Compiler Architecture.
• "Perfect Supercompilation"
  • D-376 abstract
  • paper (.ps.gz)

This page is linked from: SCP   Valentin F. Turchin