[Paper] A Calculus of Overlays

Source: arXiv - 2602.16291v1

Overview

Bo Yang’s “A Calculus of Overlays” proposes a new foundational model for declarative programming built on three primitives—record, definition, and inheritance—that mirrors how the λ‑calculus underpins functional languages. By grounding the semantics in plain set theory, the calculus makes inheritance naturally commutative, idempotent, and associative, sidestepping classic multiple‑inheritance headaches and delivering a fully abstract semantics for the lazy λ‑calculus.

Key Contributions

• Overlay‑Calculus definition: Introduces a minimal, three‑primitive calculus that can embed the λ‑calculus while remaining purely set‑theoretic.
• Commutative inheritance: Shows that inheritance operations are mathematically associative, commutative, and idempotent, eliminating the linearization problem of multiple inheritance.
• Fully abstract lazy λ‑calculus semantics: Proves equivalence to Böhm tree semantics, guaranteeing that overlay programs preserve the observational behavior of lazy functional programs.
• Practical language extraction: Derives the Overlay language from the calculus, demonstrating real‑world phenomena such as CPS‑agnosticism and native random‑access memory via records.
• Resolution of the Expression Problem: Shows that the calculus naturally unifies data‑type extension and operation extension without boilerplate or pattern‑matching hacks.
• Broad applicability: Highlights potential uses ranging from configuration DSLs and dependency‑injection frameworks to composable effect systems and no‑code platforms.

Methodology

1. Primitive design: The calculus starts with three syntactic forms—record (a set of fields), definition (binding a name to a record), and inheritance (a binary operator that merges records).
2. Set‑theoretic semantics: Each primitive is interpreted as a simple set operation (union, lookup, etc.). Because set union is commutative, associative, and idempotent, inheritance inherits these properties automatically.
3. Embedding λ‑calculus: Bo constructs a translation from λ‑terms to overlay terms, preserving application and abstraction via nested records and definitions.
4. Full abstraction proof: Using Böhm tree equivalence, the paper demonstrates that two λ‑terms are observationally indistinguishable iff their overlay translations are equal under the set‑theoretic model.
5. Prototype implementation: A lightweight interpreter for the Overlay language validates the theory, exposing emergent behaviors (e.g., CPS‑agnostic execution, self‑reference to multiple targets).

The approach is deliberately kept “naïve” to show that powerful language features need not rely on complex category‑theoretic machinery or sophisticated type systems.

Results & Findings

• Embedding works: All λ‑calculus constructs map cleanly into overlay terms, confirming the calculus’s expressive completeness.
• Inheritance behaves predictably: Merging records via inheritance never leads to ordering conflicts; the result is the same regardless of the merge order.
• Lazy semantics preserved: The overlay translation respects lazy evaluation, and the resulting Böhm trees match those of the original λ‑terms.
• Prototype showcases: In the Overlay language, developers can write configuration files that double as executable programs, inject dependencies without a container, and compose effects without explicit monad transformers.
• Expression Problem solved: Adding new data variants or new operations requires only new records/definitions—no refactoring of existing code.

Practical Implications

For developers, the biggest win is predictable composition: you can freely combine libraries, configurations, or UI components without worrying about the order in which they’re applied.

Limitations & Future Work

• Tooling maturity: The current prototype is an interpreter; production‑grade compilers, IDE support, and debugging facilities are still missing.
• Performance considerations: Naïve set‑theoretic operations may incur overhead for large record structures; optimizations (e.g., hash‑consing) are needed.
• Typed extensions: While the calculus is untyped, integrating a static type system (e.g., row types) would improve developer ergonomics and catch errors early.
• Interoperability: Bridging overlay programs with existing ecosystems (JavaScript, JVM, .NET) requires foreign‑function interfaces that are not yet defined.
• Formal verification: The paper proves full abstraction for the lazy λ‑calculus, but extending the proof to effectful or concurrent extensions remains open.

Future research directions include building a typed Overlay language, exploring incremental compilation strategies, and creating domain‑specific overlays for cloud configuration, micro‑service orchestration, and data‑pipeline composition.

Authors

• Bo Yang

Paper Information

• arXiv ID: 2602.16291v1
• Categories: cs.PL, cs.SE
• Published: February 18, 2026
• PDF: Download PDF