WG211/M2Kamin

Title: Using Partial Evaluation to Optimize Run-Time Program Generation

Sam Kamin

Abstract: We have been advocating an approach to run-time program generation (RTPG) in which the back end of the static compiler, appropriately structured, is used as the run-time compiler. The advantages of this appraoch are that there is only one compiler to build, and, more importantly, it allows for very general kinds of decomposition. The disadvantage is that the resulting run-time program generators are slow: The compiler writer cannot take advantage of constraints on the generation process to create an efficient code emitter, and the programmer expresses the run-time code at source level, thus having no way to affect the run-time program generation process.

We are exploring the idea of using partial evaluation to optimized the run-time generation process. Consider a staged program in which a quoted, dynamic code fragment P[] contains an anti-quoted "hole" to be filled in at run time by some fragment H. In effect, the compiler is a function of P and H, with P being static and H dynamic. In principle, we can partially evaluate the compiler on P. Note that, with this approach, the cost of RTPG depends upon "how dynamic" the fragments are; a fragment whose only holes are relatively inconsequential will allow for substantial static evaluation, while a fragment missing crucial parts will leave little room for optimization.

We have experimented with this approach in our Java-based RTPG system, Jumbo. To date, we have achieved only about a 5% speedup. Recently, we wrote a model of the system in the rule-based programming system Maude. The model is based on a simplified language, called Mumbo. In the model, taking rewrite steps as the performance measure, we have achieved speed-ups of 50%. In this talk, I will mainly discuss the Mumbo experiment, because this presents a clearer picture of the approach. I will also discuss the more difficult problem presented by Jumbo and present our latest results there (hopefully better than 5%!).

Based on work by: Sam Kamin, T. Baris Aktemur, Philip Morton.