Multi-Stage Specialization with Relative Binding Times Abstract

Programming systems that generate code at run time o er unique opportunities for specialization. Dynamic specialization can exploit run-time values that are not available at compile time, yielding code that is superior to statically optimal code. Unfortunately, conventional formulations of binding-time analysis prove overly restrictive in such a setting. The values computed by specialized procedures are classi ed as dynamic, which prevents a useful form of multi-stage specialization. We propose a simple notion of relative binding times that allow multiple stages of specialization to be realized in a two-level lambda calculus. 1 Dynamic Specialization and Binding-Time Analysis Most partial evaluators perform specialization at compile time. However, recent research has demonstrated that it is sometimes pro table to perform specialization at later stages, such as run time [8, 7,2,4, 6]. Some implementations of dynamic specialization rely on a bindingtime analysis (BTA) to determine how to specialize a program when some of its variables take on xed values. BTA requires an initial binding-time division that classi es program inputs as static or dynamic. From this initial division, the BTA translates a program into a two-level language in which every subexpression is annotated with its binding time. Unfortunately, conventional BTA prevents dynamic specialization from exploiting many opportunities for optimization. This is most easily illustrated with an example