Multi-stage Programming for Mainstream Languages
Edwin M. Westbrook, Mathias Ricken, Jun Inoue, Yilong Yao, Tamer Abdelatif, Walid Taha · 2009
Multi-stage programming (MSP) provides a disciplined approach to run-time code generation. In the purely functional setting, it has been shown how MSP can be used to reduce the overhead of abstractions, allowing clean, maintainable code without pay-ing performance penalties. Unfortunately, MSP is difficult to com-bine with imperative features, which are prevalent in mainstream languages. The central difficulty is scope extrusion, wherein free variables can inadvertently be moved outside the scopes of their binders. This paper proposes a new approach to combining MSP with imperative features that occupies a “sweet spot ” in the design space in terms of expressiveness of useful MSP programs and being intuitive and easy for programmers to understand. The key insight is that escapes must be weakly separable from the rest of the code, meaning that the only computational effects occuring inside an es-cape that are visible outside the escape are those that are guaranteed to not contain code. To demonstrate the feasability of this approach, we formalize a type system based on Lightweight Java which we prove sound, and we also provide an implementation, called Mint, to validate both the expressivity of the system and the performance gains attainable by using MSP in this setting.