Multi-Stage Specialization with Relative Binding Times

Mark Leone (Indiana University)
Peter Lee (Carnegie Mellon University

Technical Report #497
Computer Science Department, Indiana University

November 1997

Full paper in compressed postscript (72332 bytes)


Programming systems that generate code at run time offer 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 classified 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.