When Do Staging Annotations Preserve Semantics? (Extended Version) Journal: PACMPL Volume: 1 PLDI 1 1

Jun Tan, Guannan Wei · 2026

Read When Do Staging Annotations Preserve Semantics? (Extended Version) Journal: PACMPL Volume: 1 PLDI 1 1 by Jun Tan, Guannan Wei (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30854.txt.

Introduction

Jun Tan and Guannan Wei ask when staging annotations in a programming language can be trusted not to change a program's meaning. Multi-stage programming treats code as data: an early stage generates specialised code for a later one. Typed languages guarantee the generated code is well typed, yet rearranging fragments can subtly change evaluation order, so the staged program may drift from its unstaged reference version. The pair design two statically typed two-stage calculi, the second adding mutable references in the later stage.

Their semantics models automatic let-insertion as a control effect inside a lightweight type-and-effect system. Using binary logical relations, they prove strong preservation theorems: any generated code is contextually equivalent to the stage-erased original. The mechanised theory gives a definitive answer and a base for future language design.

Catalog record

CREATORJun Tan, Guannan Wei
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE118 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30854

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

When Do Staging Annotations Preserve Semantics? (Extended Version) Journal: PACMPL Volume: 1 PLDI 1 1 Jun Tan, Guannan Wei Abstract . 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, λ ∣ 𝟤 | \lambda_{\mid\mathsf{2}|} and λ | 𝟤 | 𝗋𝖾𝖿 \lambda^{\mathsf{ref}}_{|\mathsf{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 t_{1} evaluates to a value 𝖼𝗈𝖽𝖾 ​ t 2 \mathsf{code}~t_{2} , then t 2 t_{2} is contextually equivalent to the stage-erasure of t 1 t_{1} . Our calculi and their mechanized metatheory provide a simple and definitive answer to the question posed by 29 ; 30 of when staging annotations preserve semantics, and lay a foundation for future work on semantics-preserving multi-stage programming. [ Path=./JetBrainsMono/static/, Scale=0.85, Extension = .ttf, UprightFont=*-Regular, BoldFont=*-Bold, ItalicFont=*-Italic, BoldItalicFont=*-BoldItalic ] Mechanizing Typed Semantics-Preserving Multi-Stage Programming with Let-Insertion 1. Introduction Multi-stage programming (MSP) with quoting and splicing has long provided a powerful means for code generation and manipulation, from the early days of Lisp ( 6 ) to MetaML ( 57 ; 56 ) and its descendants. By constructing the meta-program with quotations and splices, MSP allows programs to execute in multiple stages, where earlier stages generate code specialized to the data available in earlier stages. Staging annotations provide a natural and programmer-controlled form of partial evaluation ( 32 ) , as well as an effective mechanism for domain-specific program optimization. With the syntactic form of annotations, MetaML ( 57 ; 56 ) further ensures hygiene and type safety of generated code by type systems, giving rise to what is now generally referred to as multi-stage programming. Since the introduction of MetaML, typed MSP with syntactic annotations has grown into a large family of research calculi ( 70 ; 68 ; 65 ) and has been adopted in various industrial languages, including MetaOCaml ( 38 ; 37 ; 39 ) , F# ( 55 ) , (Typed) Template Haskell ( 67 ; 52 ) , and more recently Scala 3 ( 53 ; 54 ) . Semantics-Breaking Staging Annotations Despite the expressive power and popularity of MetaML-style syntactic MSP, multi-stage programs are notoriously difficult to reason about ( 30 ; 29 ) . Unlike the name “annotations” might suggest, staging annotations are not just syntactic markers that can be freely added or removed without changing the semantics of the program. Staging annotations are syntactic in nature, but they can rearrange the evaluation order of programs, which can lead to inconsistent behaviors between the staged program and its original unstaged counterpart (obtained by erasing staging annotations) in the presence of computational effects, such as divergence and mutable states. We use the syntax from MetaOCaml ( 39 ; 37 ) to illustrate with a few examples. Brackets .< e >. delay the evaluation of the enclosed expression e as a code value, and an escape .~ e splices the value of e into a surrounding code fragment. The type \tau code denotes code fragments that, when run, produce a value of type \tau . Now let us consider the following first-stage function k (from the SKI combinators), which takes two second-stage integers and returns the first one: ⬇ let k ( x : int code ) ( y : int code ) : int code = x in let rec loop () = loop () in k .<42>. .< loop ()>. Here, when applying k , the first argument is a code fragment of integer .<42>. , and the second is a code fragment of a non-terminating computation .< loop ()>. . The first-stage evaluation terminates and produces a code .<42>. , which can be further evaluated to integer 42 when run. Since k simply returns the first argument, quoting not only delays the evaluation of loop () , but completely prevents it from being evaluated at all . However, if we compare the staged program with its unstaged counterpart, we can see that they behave differently. The unstaged version obtained by erasing staging annotations (brackets, escapes, and \tau code types) is the following, which diverges under call-by-value (CBV): ⬇ let k ( x : int ( y : int ) : int = x in let rec loop () = loop () in k 42 ( loop ()) Moreover, splicing code fragments at will can lead to code duplication, and with it, duplicated effects. Consider the following twice function that splices the argument x twice into the body, effectively adding the argument to itself: ⬇ (* erased: let twice x = x + x *) let twice ( x : int code ) : int code = .<.~ x + .~ x >. in Now invoking twice with a code fragment inducing the second-stage stdout effect: ⬇ twice .<( print_string "Hello" ; 42)>. (* generates code by copying the argument twice: *) .<( print_string "Hello" ; 42) + ( print_string "Hello" ; 42)>. The staged program generates code that prints twice. In contrast, the unstaged (or annotation-erased) program evaluates the argument only once before the function call and thus prints "Hello" only once, consistent with standard CBV evaluation. Why it Matters? To summarize, these examples show that, because syntactic staging annotations permit evaluation to be rearranged, they can arbitrarily discard, reorder, or duplicate effects. Although such a flexibility can be useful for program manipulation in some cases, we lose the ability to relate the staged program with the unstaged program, thus weakening semantic predictability and making staged programs much harder to reason about. This is particularly hindering performance-driven uses of staging, such as Futamura projections ( 24 ) and domain-specific compilers ( 58 ; 61 ; 63 ; 64 ) , where the goal is precisely to obtain faster code without changing the observable behavior of the original unstaged program . In such settings, if annotations do not preserve semantics, the unstaged program cannot be treated as a reference specification from which one derives a faster but semantically equivalent staged version merely by inserting staging annotations, therefore the generated program cannot be used as drop-in replacement for the original unstaged program. The key property connecting a staged program and its unstaged counterpart is known as erasure soundness ( 30 ; 29 ; 71 ) or semantics preservation

Read the complete text