Let It Be Optimized: Building Multi-stage Evaluators with Let-Insertion and Optimizations in Small Pieces (Functional Pearl)

Multi-stage programming lets programmers write meta-programs that generate efficient code. Staging is typically realized either as a language primitive with quotations and splices (e.g., MetaML and its descendants), or as a library embedded in a host language (e.g., Lightweight Modular Staging). Unlike quotation-based approaches, practical library-based systems combine staged evaluation with automatic let-insertion to preserve evaluation order, along with optimizations that improve residual code. Despite their popularity and practical importance, this combination has received little semantic treatment, making it difficult to reason about correctness or to compare systematically with other staging paradigms.

Using functional programming techniques, this pearl illuminates the operational aspects of staged evaluation with automatic let-insertion and optimizations as found in library-based staging systems. For a core two-stage language, we develop a series of definitional interpreters that concisely describe staged evaluation generating optimized, let-inserted residual programs. The interpreters are written in the extended continuation-passing style, where two continuations naturally account for let-insertion. With minor refactoring, we showcase a suite of optimizations, ranging from simple constant propagation/folding, common subexpression elimination, and dead-code elimination to more involved optimizations such as beta-inlining, partially-static data, and code motion. Each optimization is presented as a small, modular extension integrated into staged evaluation, requiring neither additional effort from the meta-programmer, nor complex post-hoc compiler infrastructure.