💻 computer science

Nominal Type Theory by Nullary Internal Parametricity

This paper presents a novel type theory based on Nullary Internally Parametric Type Theory and a specific name induction principle that successfully unifies the clean typing rules of universal name abstractions with the powerful pattern-matching capabilities of existential ones, thereby establishing a well-behaved nominal framework for representing syntax with binders.

Original authors: Antoine Van Muylder, Andreas Nuyts, Dominique Devriese

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Antoine Van Muylder, Andreas Nuyts, Dominique Devriese

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 trying to write a computer program that understands the rules of a language, like a programming language or a logic puzzle. A major headache in this field is dealing with variables (like x or y) that are "bound" inside specific scopes, like inside a function or a loop.

In traditional computer science, handling these variables is messy. You have to constantly worry about "alpha-equivalence" (is x the same as y if I just renamed it?) and "variable capture" (did I accidentally grab the wrong x?).

This paper introduces a new, cleaner way to handle these variables using a concept called Nominal Type Theory, built on a foundation called Nullary Internal Parametricity. Here is the breakdown using simple analogies:

1. The Problem: The "Name Tag" Dilemma

Imagine you are organizing a party. You have a list of guests (variables).

The Old Way (Existential): You treat a guest as a specific pair: "Here is a name tag, and here is the person wearing it." This is great because you can look at the tag and say, "Ah, that's Bob!" (Pattern Matching). But the rules for managing these tags are incredibly complicated and bureaucratic.
The Alternative Way (Universal): You treat a guest as a "function" that only works if you hand them a fresh, unused name tag. This is very clean and simple to manage, but you lose the ability to look at the tag and say, "That's Bob!" You can't easily match patterns.

For a long time, researchers had to choose between the messy-but-flexible way or the clean-but-rigid way.

2. The Solution: The "Magic Box" (Nullary Parametricity)

The authors propose a new system that gets the best of both worlds. They use a mathematical tool called Parametricity.

Think of Parametricity as a "Magic Box" that checks if your code is being honest.

Binary Parametricity (The Standard): Usually, this box checks if your code behaves the same way for two different inputs.
Nullary Parametricity (The New Trick): The authors realized that if you shrink this box down to zero inputs (Nullary), it becomes a perfect tool for handling names.

In this new system, a "name" isn't just a label; it's a special kind of "bridge" or "path" that connects things. The system treats names as affine functions—think of them as a "fresh name generator" that guarantees you are using a name that hasn't been used before in that specific context.

3. The Key Innovation: "Name Induction"

The paper introduces a special rule called Name Induction.

Imagine you have a mystery box containing a name. You want to know what's inside. The "Name Induction" rule says there are only two possibilities:

The Identity Case: The name inside is exactly the "current" name you are holding (like looking in a mirror).
The Fresh Case: The name inside is completely new and has never been seen before in this context.

This simple "either/or" check allows the computer to do something it couldn't do easily before: Nominal Pattern Matching. It can now look at a complex structure, say "Here is a function that takes a name," and safely break it down to see what's inside, just like the messy "Old Way" allowed, but with the clean rules of the "Alternative Way."

4. How It Works in Practice

The authors show that by using this "Nullary" approach, they can rebuild all the features of previous, complex systems (like FreshML) without the messy rules.

Swapping Names: You can swap two names around safely.
Local Scoping: You can create a "private" name that only exists inside a specific block of code and disappears when you leave it.
Pattern Matching: You can write code that says, "If I see a function taking a name, let's look at what it does," and the system automatically handles the safety checks for you.

5. The "HOAS" Example (The Grand Finale)

To prove their system works, the authors built a bridge between two different ways of representing the "Untyped Lambda Calculus" (a fundamental language of computing).

One way uses "De Bruijn indices" (counting numbers to track variables, like "the 3rd variable").
The other uses "Higher-Order Abstract Syntax" (using the host language's own functions to represent variables).

They showed that their new system could translate between these two worlds perfectly. They used a concept called Synthetic Kripke Parametricity, which is a fancy way of saying they used the "Nullary" rules to simulate a complex, multi-layered logic model that usually requires a much heavier mathematical setup.

Summary

In short, this paper says: "We found a way to make handling variable names in computer languages as easy as counting, but as powerful as looking at specific names, by shrinking a complex mathematical 'honesty checker' down to zero dimensions."

They didn't invent a new programming language to sell to consumers; they invented a new mathematical foundation that makes it easier for computer scientists to build tools that reason about code, ensuring that when we manipulate variables, we don't accidentally break the rules of logic.

Technical Summary: Nominal Type Theory by Nullary Internal Parametricity

Problem Statement
Formalizing the syntax of languages with binders (e.g., lambda calculus) requires handling $\alpha$ -equivalence, name abstraction, and freshness. Nominal frameworks address this using "name abstraction" types (denoted $\@N \multimap -$ ). However, existing approaches face a trade-off:

Existential Presentation: Treats abstractions as name-term pairs $\langle x, a \rangle$ . This supports convenient "nominal pattern matching" (deconstructing binders) but suffers from cumbersome typing rules requiring complex freshness propagation.
Universal Presentation: Treats abstractions as functions consuming fresh names (affine functions). This offers clean inference rules but seemingly lacks the ability to perform nominal pattern matching.

Current nominal frameworks often rely on external semantics (e.g., nominal sets) or complex internal mechanisms to bridge this gap. The paper seeks a foundation that unifies the clean rules of the universal presentation with the pattern-matching capabilities of the existential one, entirely within a type-theoretic setting.

Methodology
The authors propose Parametric Nominal Type Theory (PNTT), a dependent type theory built upon Nullary Internally Parametric Type Theory (nullary PTT). This approach adapts the binary internally parametric type theory of Cavallo and Harper (CH) by reducing the arity of parametricity from 2 to 0.

The core methodology involves:

Nullary Bridges: Replacing the standard binary path/bridge types with nullary bridges. A nullary bridge $q : \text{Bridge } A \dots$ is treated as an affine function out of a bridge interval $\@N$ . These bridges represent "fresh" variables.
Structure Abstraction Principle (SAP): The theory internalizes parametricity via the SAP, which establishes equivalences between a type $K$ and its "bridge type" $\@N \multimap K$ . Crucially, the SAP asserts that the bridge type former commutes with all other type formers.
Name Induction: The bridge interval $\@N$ is extended into a first-class type of names, $\text{Nm}$ . A novel eliminator, name induction ( $\text{ind}_{\text{Nm}}$ ), is introduced. This allows case analysis on a name $n$ : either $n$ is the specific affine variable $x$ currently in scope, or $x$ is fresh in $n$ .
Nominal Data Types: Standard nominal data types (like the syntax of the untyped lambda calculus) are defined using constructors that may take names as arguments.

Key Contributions

Recovery of Nominal Pattern Matching: The paper demonstrates that nominal pattern matching, typically associated with existential abstractions, can be recovered in the universal setting. By applying the SAP to a nominal data type $D$ , the bridge type $\@N \multimap D$ is shown to be equivalent to a "parametric translation" $D_1$ (e.g., $Ltm_1$ ). $D_1$ contains explicit "hole" constructors. Pattern matching on a binder in $D$ is thus reduced to induction on $D_1$ , where the "hole" case corresponds to the bound variable.
Unified Primitives: The authors show that PNTT naturally supports:
- Universal Name Abstraction: Via nullary bridge types.
- Typal Freshness: Via $\text{Gel}$ types, which classify terms where a specific name is fresh.
- Existential Abstraction: Derived non-primitively via the SAP and freshness types.
- Name Swapping and Local Scoping: Implemented using affine functions and the $\nu$ -binder (implemented as $\text{ung}(\lambda x. t)$ ).
Synthetic Kripke Parametricity: The paper connects nullary parametricity to Kripke binary parametricity. By combining nullary parametricity (for nominal reasoning) with a standard binary parametricity axiom, the authors emulate Kripke models. This is demonstrated by proving the equivalence between the De Bruijn syntax of the untyped lambda calculus and its Higher-Order Abstract Syntax (HOAS) encoding.
Structure Abstraction Principle (SAP) at Names: A specific proof is provided showing that $\@N \multimap \text{Nm} \simeq 1 + \text{Nm}$ . This equivalence is central to the name induction principle and the recovery of pattern matching.

Results

Theoretical Soundness: The authors provide a semantic model for PNTT in the presheaf category $\text{Psh}(\square_2 \times \square_0)$ , where $\square_0$ is the category of finite ordinals and injections (the base of the Schanuel topos). This confirms the consistency of the system.
Implementation Feasibility: The paper argues that since binary CH theory has been implemented in Cubical Agda, implementing PNTT (essentially nullary CH + name induction) is feasible.
Case Studies:
- $\pi$ -calculus Substitution: The authors define a substitution function for $\pi$ -calculus processes by matching on binding patterns, demonstrating the utility of the SAP-based approach.
- HOAS Adequacy: A proof is sketched (relying on an external binary parametricity axiom) showing that the nominal syntax of the lambda calculus is equivalent to its HOAS encoding, mirroring Atkey's Kripke parametricity results.

Significance and Claims
The paper claims to provide a "legitimate nominal framework" that resolves the historical tension between existential and universal name abstractions.

Unification: It unifies the clean inference rules of universal abstraction with the practical pattern-matching capabilities of existential abstraction without requiring external meta-theory.
Internalization: Unlike previous approaches where parametricity is a meta-theoretical property, PNTT internalizes parametricity via the SAP, allowing parametricity results to be proven within the theory.
Novelty: The authors state they are the first to make explicit and active use of nullary parametricity as a foundation for nominal type theory.
Modesty: The paper acknowledges limitations. The SAP proofs for complex terms are "unwieldy" and currently require manual reproduction of term structures. The authors suggest that future work could involve automating SAP proof construction or moving to an "observational" version of PNTT (as in the Narya proof assistant) to avoid the need for explicit SAP proofs. They also note that full FreshMLTT name swapping rules (commuting with substitution) are not yet fully accommodated without ad-hoc restrictions.

In summary, the paper establishes nullary internal parametricity as a robust foundation for nominal type theory, offering a principled way to handle binders, freshness, and pattern matching within a single, coherent type-theoretic system.