Previous: Costs of Deferred Compilation Up: Deferred Compilation: The Automation of Run-Time Code Generation Next: Conclusions

Deferred Compilation vs. Partial Evaluation

The correctness of a partial evaluator, called for historical reasons [JSS89], is described by the following equation, which specifies that the result produced by the residual program must be the same as the result of the original program when applied to the same inputs ( denotes evaluation of a program , yielding a function):

Perhaps the most intriguing aspect of partial evaluation is self-application. If is implemented in the language that it interprets, it can specialize itself to a particular source program , yielding a program that generates a residual program when executed:

This is the essence of our techniques for fast run-time code generation. is a generating extension that when given the first input value will produce an optimized residual program. A generating extension is simply a specialized code generator, and it can be constructed at compile time because it does not depend on any run-time data. A further self-application of yields the stand-alone program, commonly called cogen, that performs the construction:

In practice this approach has not been used to implement automatic run-time code generation. Typical partial evaluators [Con88][Bon93] are intended for source-to-source program transformation (see Section 3.3) and produce residual programs in Scheme or a similar high-level language. The generating extensions produced by self-application are therefore implemented in Scheme, and more importantly, they generate Scheme code when executed. The use of such systems for run-time code generation would therefore require general-purpose run-time compilation, which is too costly to be widely applicable.

Implementing a self-applicable partial evaluator that directly generates machine code would solve such problems. Generating extensions would be directly executable and they would generate native code when executed. To the best of our knowledge, no such partial evaluator has been described or implemented to date. One system that comes closer than most to this goal is AMIX, a self-applicable partial evaluator for a first-order functional language whose target is an abstract stack machine [Hol88]. AMIX's abstract machine code is a relatively high-level language, however, and the cost of compiling it to native code at run time would be substantial. The interpretational overhead present in this compilation cannot be statically eliminated.

A promising alternative to self-application is the hand-implementation of cogen [BW93]. In fact one can view FABIUS as a hand-implemented cogen whose target language is RISC machine code. This view is supported by our concentration on two-stage programs and our wholesale adoption of numerous techniques originally developed for partial evaluators, such as binding time analysis, unfolding heuristics, and memoized specialization. However, the goals and strategies of FABIUS, such as one-pass native-code generation and static register allocation, differ from those of any existing formulation of cogen.