Flow-Directed Lightweight Closure and CPS Conversion
Date	Friday, 08Dec00
Time	2-3pm
Speaker	Jeffrey Siskind
Affiliation	NEC Research Institute, Inc.
Abstract	Lexically-scoped higher-order programming languages require closures for procedures. Typical implementations create a closure for every procedure and a variable slot for every free variable. This entails substantial overhead. In this talk, I will present a novel compile-time analysis and code-generation strategy, called lightweight closure conversion, that significantly reduces the number of procedures that need closures and the number of variables that need slots, resulting in faster code. Programming languages such as Scheme and SML/NJ support first-class continuations through a CALL/CC primitive. Without continuations, programs obey a last-in-first-out procedure-call discipline that allows stack-based allocation of activation records. In the presence of continuations, programs no longer obey a last-in-first-out procedure-call discipline and thus require heap-based allocation of activation records. In the past, two general strategies have been used to support CALL/CC. One involves converting the entire program to continuation-passing style (CPS). This process is called CPS conversion. In essence, this heap-allocates all activation records. The other involves leaving the program in direct style by implementing mechanisms to copy portions of the stack to the heap when creating continuations and copying saved continuations from the heap back to the stack when calling continuations. The former has the advantage that creating and calling continuations is cheap but the disadvantage that ordinary procedure call and return is expensive. The latter has the reverse set of tradeoffs. Lightweight CPS conversion is a novel scheme that gives the advantages of both approaches, without the disadvantages, in most situations.
Location	545 Technology Square (aka "NE43")
Room	8th Floor Playroom
Bio	http://www.neci.nj.nec.com/homepages/qobi