Search papers, labs, and topics across Lattice.
This paper investigates the semantics preservation in multi-stage programming, addressing the challenges posed by syntactic manipulations that can alter evaluation order and introduce discrepancies between staged and unstaged programs. The authors develop two statically typed two-stage calculi, $位_{|2|}$ and $位^{ref}_{|2|}$, which incorporate automatic let-insertion and a lightweight type-and-effect system to ensure type-safe manipulation of effectful code fragments. Their strong semantics-preservation theorems, proven through binary logical relations, confirm that well-typed staged programs maintain contextual equivalence with their unstaged counterparts, providing clarity on when staging annotations are semantically valid.
Staging annotations can be safely manipulated without losing semantics, thanks to new calculi that ensure type safety and context preservation.
Multi-stage programming with quotations has long provided a powerful way to generate and manipulate code. By treating code as data, programmers can write multi-stage programs in which earlier stages produce specialized code from inputs available at generation time. Modern typed multi-stage languages (e.g., MetaML, MetaOCaml, Template Haskell, and Scala 3) adopt quotation/splicing constructs while enforcing the well-typedness of generated code. However, manipulating code fragments syntactically can subtly change evaluation order, leading to semantic discrepancies between a staged program and its unstaged counterpart, which is intended to serve as a reference implementation in many cases. The inconsistency complicates reasoning about correctness, and prevents staged code from being a drop-in replacement for its unstaged counterpart. In this paper, we study the design of multi-stage languages with semantics preservation guarantees. We develop two statically typed two-stage calculi, $位_{|2|}$ and $位^{ref}_{|2|}$, the latter supporting mutable references in the second stage. Their dynamic semantics models automatic let-insertion, tracked as a control effect in a lightweight type-and-effect system, enabling type-safe and semantics-preserving manipulation of effectful code fragments. We develop binary logical relations to prove strong semantics-preservation theorems: if a well-typed two-stage program $t_1$ evaluates to a value $\mathsf{code} t_2$, then $t_2$ is contextually equivalent to the stage-erasure of $t_1$. Our calculi and their mechanized metatheory provide a simple and definitive answer to the question posed by Inoue and Taha of when staging annotations preserve semantics, and lay a foundation for future work on semantics-preserving multi-stage programming.
