💻 computer science

Type Theory With Erasure

This paper presents a structural formulation of type theory with erasure as a second-order generalised algebraic theory (SOGAT) that distinguishes runtime-relevant and irrelevant data via a phase distinction, establishing its semantic models, conservativity over Martin-Löf type theory, and correctness for code extraction to untyped lambda calculus.

Original authors: Constantine Theocharis, Edwin Brady

Published 2026-05-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Constantine Theocharis, Edwin Brady

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef preparing a massive, complex banquet. You have a recipe book (the Type Theory) that tells you exactly how to make every dish. Some ingredients in the recipe are crucial for the final taste (like the salt or the main protein), while others are just for the chef's reference during the cooking process (like the specific brand of the pot, or a note saying "stir gently").

In modern programming languages that use Dependent Types, the "recipe" is so detailed that the computer often gets confused about what to keep and what to throw away when it's time to actually serve the meal (run the program). Usually, the computer has to guess or do a lot of heavy lifting to figure out which parts of the code are just "notes" and which are "ingredients."

This paper, "Type Theory With Erasure," by Constantine Theocharis and Edwin Brady, proposes a new, cleaner way to organize the recipe book so the computer knows exactly what to keep and what to discard before it even starts cooking.

Here is the breakdown of their idea using simple analogies:

1. The Two Modes: "The Chef's Notes" vs. "The Meal"

The authors introduce a simple rule: every piece of information in the code is tagged with one of two labels:

Runtime (The Meal): This is data that must survive to the end. It's the actual food the customer eats.
Erased (The Notes): This is data used only to prove the recipe is correct, but it gets thrown away before the meal is served.

Think of it like a blueprint for a house. The blueprint has notes about the structural integrity of the walls (crucial for the architect to check) and the actual bricks and mortar (what the builder uses). In this new system, the computer is told explicitly: "These notes are for the architect only; do not build them into the final house."

2. The Magic Switch: "The Phase Distinction"

The core innovation is a concept called a "Phase Distinction." Imagine a magical switch in the kitchen called #.

When the switch is OFF, you are in the "Construction Phase." You can see everything: the notes, the ingredients, and the tools.
When the switch is ON, you are in the "Serving Phase." The notes magically disappear.

The paper creates a logical rule: If you are in the "Serving Phase" (erased mode), you can pretend you are in the "Construction Phase" to do your work, but you cannot bring any "Construction Phase" tools back into the "Serving Phase."

This prevents a common bug where a program accidentally tries to use a "note" (like a proof that a number is positive) as if it were a real "ingredient" (like the number itself) when the program is actually running.

3. The "Ghost" Ingredients

In this system, you can have "Ghost Ingredients."

Example: Imagine a list of items. In a normal system, the computer might store the length of the list (e.g., "5 items") every time it saves the list, just to be safe.
In this system: The computer knows the length is only needed to check the list is valid. Once checked, the length is a "Ghost." It exists in the recipe but vanishes from the final dish.
The Result: The final program is smaller, faster, and cleaner because it doesn't carry around unnecessary baggage.

4. The "Universal Translator" (The Model)

The authors didn't just write a rule; they built a mathematical "translator" to prove it works.

They created a Model (a simulation) where they treat the "Erased" parts as if they are being viewed through a special lens that makes them invisible.
They proved that if you take a program written with these rules and translate it into a standard, untyped language (like a raw list of instructions), the program still works exactly as intended. The "Ghost" parts vanish, and the "Real" parts do their job perfectly.

5. Why This Matters (The "Toy" Implementation)

The authors built a small, working prototype (a "toy elaborator") to show this isn't just theory.

They showed that a computer can automatically take a complex, high-level program and strip away all the "Ghost" parts to create a lean, efficient final product.
They also proved that this new way of organizing code doesn't break any of the existing math. It's like adding a new, better filing system to a library; the books are still the same, but you can find them faster and the shelves are less cluttered.

Summary

Think of this paper as inventing a new kind of recipe book where the author can explicitly mark "Do Not Eat" on the instructions.

Old Way: The computer has to guess which instructions are "Do Not Eat," often making mistakes or doing extra work.
New Way: The author marks them clearly. The computer follows the rules, throws away the "Do Not Eat" instructions, and serves a perfect, lightweight meal.

The paper proves that this system is mathematically sound, works with complex types, and can be implemented in real software to make programs faster and more reliable.

1. Problem Statement

In dependently typed programming languages (like Agda, Idris, and Rocq), types often depend on values. This creates a fundamental ambiguity: which parts of a program are computationally relevant at runtime, and which can be safely erased during compilation?

Current Approaches: Existing solutions often rely on Quantitative Type Theory (QTT), which uses a quantitative semiring (e.g., $\{0 < \omega\}$ ) to track variable usage. While effective, QTT introduces complexity regarding substructural constraints and linearity. Other approaches use "ghost sorts" or heuristic whole-program analysis, which can be brittle and unpredictable for complex dependent types.
The Gap: There is a need for a structural, modular, and reduction-free formulation of erasure that integrates seamlessly with standard type theory metatheory, supports code extraction, and provides a clear semantic foundation without relying on complex quantitative semantics.

2. Methodology

The authors propose a structural version of type theory with erasure formulated as a Second-Order Generalised Algebraic Theory (SOGAT).

Synthetic Phase Distinction: Instead of using quantitative semirings, the authors encode erasure as a phase distinction using a synthetic proposition, denoted as # (the erasure marker).
- A context $\Gamma$ is considered "erased" if it contains the proposition $\#$ (i.e., $\# \in \Gamma$ ).
- This creates a distinction between runtime mode ( $\omega$ ) and erased mode ($0$).
- Crucially, $\#$ is a proposition with no truth value; it cannot be constructed or discharged arbitrarily. It acts as a marker that allows terms to be coerced between modes.
Coercion Mechanism: The theory introduces two coercions:
- Erasure ( $\#$ ): If a term $a$ is of type $A$ in a context extended by $\#$ , it can be coerced to an erased term ( $\# a : 0: A$ ).
- Lifting ( $\$ $): If a term $a$ is erased, it can be lifted to a runtime term under the assumption of $\#$ ( $\$ a : \omega: A$).
- These are mutual inverses up to definitional equality, ensuring that erased terms do not depend on runtime data.
Modular SOGAT Formulation: The theory is defined as a SOGAT extending Martin-Löf Type Theory (MLTT). This allows the authors to leverage existing metatheory for SOGATs, including functorial semantics and model construction via Categories with Families (CwFs).

3. Key Contributions

A. Theoretical Formulation

SOGAT Definition: The paper defines TT0 (Type Theory with Erasure) as a SOGAT. It includes types ($Ty$), terms ($Tm$) indexed by modes $\{0, \omega\}$ , and the erasure marker ( $\#$ ).
Derived Erased Fragment: A significant contribution is that the theory does not need to explicitly define erased versions of every term former (e.g., $\Pi_0, \Sigma_0$ ). Because of the isomorphism between contexts with and without $\#$ , the entire erased fragment is derived automatically from the runtime fragment.
Inductive Types: The framework supports inductive types where specific arguments (like indices) can be marked as erased. It handles "exotic" inductive types where constructors themselves might exist only in erased mode.

B. Semantic Models

Fam(Set) Model: The authors construct a standard model in the category of families of sets ($Fam(Set)$).
- In this model, an object is a pair $(X_0, X_1)$ where $X_0$ represents erased data and $X_1$ represents runtime data.
- The erasure marker $\#$ is interpreted as a "tiny proposition" (an object $\phi$ such that exponentiation by $\phi$ isolates the base component).
- This model generalizes to any Grothendieck topos equipped with a tiny proposition.
Squashed Universes: To handle universes in the erased context, the authors introduce "squashed universes" ( $\sqrt{\phi}U$ ). These are $\phi$ -modal objects that retain the structure of standard universes but satisfy the condition that their fibers are contractible, allowing them to exist in erased contexts without carrying runtime data.

C. Code Extraction and Correctness

Untyped Lambda Calculus Extraction: The authors construct a model that extracts TT0 programs into untyped lambda calculus.
- Runtime terms map to lambda terms.
- Erased terms map to the terminal object (effectively disappearing).
- Contexts with erased variables are isomorphic to contexts without them.
Gluing and Logical Relations: To prove correctness, they use gluing to construct a logical relation between the code extraction model and the standard set-theoretic model.
- Theorem 27 (Non-interference): Proves that every erased function is constant at runtime. If a function takes an erased argument, its output cannot depend on that argument at runtime.
- Theorem 25 & 26: Prove canonicity and that extracted code tracks the semantic interpretation.

D. Implementation

Elaborator: A toy elaborator was implemented in Agda. It takes a high-level language (similar to Idris/Agda with 0 and @0 annotations) and elaborates it into the core SOGAT.
Pattern Unification: The authors demonstrate that because the core is structural, standard pattern unification algorithms can be reused without needing complex quantity checks or special generalization mechanisms for erased metavariables, solving issues found in current implementations of Agda and Idris.

4. Results

Conservativity: The theory is proven to be conservative over MLTT. Adding erasure does not increase the proving power of the type theory; any theorem provable in TT0 is provable in standard MLTT.
Independence: Erased data is proven to be independent of runtime data. An erased term in a context $\Gamma$ corresponds uniquely to an erased term in the "zeroed" context $0\Gamma$ (where all modes are set to 0).
Correctness of Extraction: The gluing proof confirms that the extraction process preserves computational behavior and correctly erases irrelevant data, ensuring that the generated code is safe and efficient.

5. Significance

Structural Clarity: By moving away from quantitative semirings to a synthetic phase distinction, the paper provides a cleaner, more modular foundation for erasure. It separates the concept of erasure from the mechanism of resource tracking.
Implementation Guidance: The structural approach simplifies the implementation of type checkers and elaborators. It removes the need for ad-hoc quantity checks during unification, potentially fixing bugs in existing systems like Idris 2 and Agda.
Semantic Foundation: The use of Grothendieck toposes and tiny propositions connects erasure to broader categorical logic, enabling the use of Synthetic Tait Computability for metatheoretic proofs.
Future Extensions: The framework is designed to be extensible, supporting potential future work on runtime types, multiple phase distinctions (for staging/metaprogramming), and integration with Cubical Type Theory.

In summary, this paper presents a rigorous, structural, and semantically grounded approach to type theory with erasure, offering both theoretical guarantees (conservativity, non-interference) and practical benefits for compiler implementation and code extraction.