Layered Modal ML: Syntax and Full Abstraction

Haoxuan Yin, Andrzej S. Murawski, C. -h. Luke Ong

Abstract

MetaML-style metaprogramming languages allow programmers to construct, manipulate and run code. In the presence of higher-order references for code, ensuring type safety is challenging, as free variables can escape their binders. In this paper, we present Layered Modal ML (LMML), the first metaprogramming language that supports storing and running open code under a strong type safety guarantee. The type system utilises contextual modal types to track and reason about free variables in code explicitly. Addressing the question of whether optimized programs preserve original meaning, we provide a semantic model capturing contextual equivalence for LMML, establishing the first full abstraction result for an imperative MetaML-style language. Our model is based on traces derived via operational game semantics.

Introduction: The Challenge of Safe Metaprogramming

Metaprogramming is a powerful technique for program optimization and the creation of domain-specific languages. However, integrating metaprogramming with imperative features like mutable references introduces significant complexity, primarily due to scope extrusion. This occurs when a piece of "open code" (code containing free variables) is stored in a reference and later executed in a context where those variables are no longer in scope, leading to runtime crashes.

Existing systems often compromise on either safety or expressiveness. Some languages throw runtime exceptions when scope extrusion is detected, while others forbid storing open code entirely. Layered Modal ML (LMML) aims to bridge this gap by providing a framework that safely supports storing and running open code in an imperative environment.

Comparison of LMML with existing metaprogramming type systems.

The LMML Framework

LMML achieves its safety guarantees through two primary mechanisms:

  1. Contextual Modal Types: The language uses types of the form $\square(\Gamma \vdash A)$ to represent code of type $A$ that depends on a specific set of variables $\Gamma$. This allows the type system to explicitly track dependencies.
  2. The letbox Operator: To execute or "unbox" code, LMML requires the letbox construct, which mandates explicit substitutions for all free variables. This ensures that no variable can escape its intended scope.

By restricting the system to two layers—the meta-level (generator) and the object-level (generated code)—the authors manage the complexity of the type theory while covering the majority of practical use cases.

Full Abstraction and Semantic Modeling

A critical contribution of this work is the establishment of a semantic model that captures contextual equivalence. This is essential for verifying that metaprogramming-based optimizations do not alter a program's behavior.

The authors utilize Operational Game Semantics, modeling program execution as a dialogue between the program (Player) and its environment (Opponent). This approach leads to the first full abstraction result for an imperative MetaML-style language, meaning the semantic model perfectly aligns with observable program behavior.

Comparison of semantic models for metaprogramming languages.

Key Results and Insights

  • Strong Type Safety: The authors provide proofs for Preservation and Progress, ensuring that well-typed LMML programs never suffer from scope extrusion.
  • Conservative Extension: LMML is shown to be a conservative extension of standard ML with higher-order state, ensuring familiarity for developers.
  • CIU Theorem: A novel "Closed Instances of Use" (CIU) theorem was established, accounting for both call-by-value and call-by-name substitutions, which is a vital tool for proving program equivalences.

Conclusion and Future Directions

LMML represents a significant step forward in safe metaprogramming. While currently limited to two layers, it provides a robust foundation for imperative code generation. Future work includes generalizing the system to $n$-layers and exploring how to reintroduce structural analysis (pattern matching) on code without compromising the full abstraction results.

Summary updated

Abstract

MetaML-style metaprogramming languages allow programmers to construct, manipulate and run code. In the presence of higher-order references for code, ensuring type safety is challenging, as free variables can escape their binders. In this paper, we present Layered Modal ML (LMML), \textit{the first metaprogramming language that supports storing and running open code under a strong type safety guarantee}. The type system utilises contextual modal types to track and reason about free variables in code explicitly. A crucial concern in metaprogramming-based program optimisations is whether the optimised program preserves the meaning of the original program. Addressing this question requires a notion of program equivalence and techniques to reason about it. In this paper, we provide a semantic model that captures contextual equivalence for LMML, establishing \textit{the first full abstraction result for an imperative MetaML-style language}. Our model is based on traces derived via operational game semantics, where the meaning of a program is modelled by its possible interactions with the environment. We also establish a novel closed instances of use theorem that accounts for both call-by-value and call-by-name closing substitutions.
BibTeX
@inproceedings{yin2026layered,
  author = {Haoxuan Yin and Andrzej S. Murawski and C. -H. Luke Ong},
  title = {{Layered Modal ML: Syntax and Full Abstraction}},
  booktitle = {LICS},
  year = {2026},
  doi = {10.4230/lipics.lics.2026.83},
}
Figure