💻 computer science

Well-Scoped Locally Nameless Representation of Syntax

This paper presents a generic, well-scoped locally nameless syntax representation for Agda parameterized by Plotkin-style binding signatures, proving its adequacy against naive nameful syntax modulo alpha-conversion and demonstrating its utility through examples.

Original authors: Andrew M. Pitts

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrew M. Pitts

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 librarian trying to organize a massive, chaotic library where books can refer to other books inside them. Some books have titles written on their covers (like "The Great Gatsby"), while others are just numbered shelves inside a specific section (like "Shelf 3, Row 2").

This paper, written by Andrew Pitts, is about a new, smarter way to organize this library so that computers (specifically, "interactive theorem provers" like Agda) can check the rules of the library without getting confused or making mistakes.

Here is the breakdown of the paper's ideas using simple analogies:

1. The Problem: The "Nameless" vs. "Named" Dilemma

When computer scientists try to teach a computer about languages (like programming languages or logic), they have to deal with variables.

The "Named" way: You give every variable a name, like x, y, or z. This is easy for humans to read, but computers get confused when you swap names around (a problem called "alpha-conversion"). Is x the same as y if you rename them?
The "Nameless" way (De Bruijn indices): You stop using names entirely. Instead, you just say "the 1st variable," "the 2nd variable," etc., counting from the inside out. This is great for computers but terrible for humans because it looks like a jumbled mess of numbers.

2. The Old Solution: "Locally Nameless"

A few years ago, researchers came up with a hybrid idea called Locally Nameless.

Free variables (things not bound inside a loop or function) keep their names (like x).
Bound variables (things inside a loop) use numbers (like 0, 1).

The Catch: This system has a "trap." It allows you to create "broken" terms where the numbers don't match the scope. Imagine a book saying "Go to Shelf 5," but you are currently in a room that only has 3 shelves. The computer has to constantly check, "Is this term 'locally closed' (valid)?" This requires a lot of extra proof work, like a librarian constantly checking if a book is in the right aisle before letting anyone borrow it.

3. The New Solution: "Well-Scoped Locally Nameless"

This paper proposes a better way: Well-Scoped Locally Nameless.

Instead of just using numbers, the computer uses types to enforce the rules.

Think of the library as having different "rooms."
If you are in Room 0, you can only see shelves numbered 0 to 0 (which means no shelves, just free names).
If you are in Room 1, you can see shelves 0 and 1.
If you are in Room 5, you can see shelves 0 through 5.

The Magic: In this system, you literally cannot build a broken book. If you try to write "Go to Shelf 10" while standing in Room 2, the computer's type system says, "No, that's impossible. You can't even write that sentence."

The paper argues that this approach:

Removes the "Trap": You don't need to write extra proofs to check if a term is valid. The fact that the term exists proves it is valid.
Is Transparent: It still looks mostly like the "Named" way humans are used to, so it's not as confusing as the pure "Nameless" way.
Is Generic: The authors built a "library" (a set of tools) that works for any language you want to define, as long as you describe the rules of binding (like how if statements or lambda functions work) using a standard template.

4. How It Works (The "Opening" and "Closing")

The paper describes two main operations, which are like moving books between rooms:

Abstraction (Closing): Taking a free name (like x) and turning it into a bound index (like 0). This is like taking a book off the shelf and putting it into a specific numbered slot in a new room.
Concretion (Opening): Taking a bound index and replacing it with a specific book (term). This is like taking a book out of a slot and putting a real book in its place.

The authors prove that their "Well-Scoped" math works perfectly. They show that their new system is mathematically equivalent to the old "Named" system, meaning they represent the exact same concepts, just organized more safely.

5. Real-World Examples

The paper doesn't just talk theory; they tested their "library" on three different types of languages:

The Pi-Calculus: A language used to describe how computer programs talk to each other (like phone calls). Here, names are "channels" for communication.
Martin-Löf Type Theory: A complex system for mathematical proofs. They showed how to write rules for natural numbers and types without getting lost in the "freshness" of names.
Gödel's System T: A system for proving that calculations will eventually finish (decidability). They used their method to prove that a specific algorithm works correctly.

The Bottom Line

The paper says: "Stop manually checking if your variables are in the right place. Let the computer's type system do the heavy lifting for you."

By using dependent types (a feature of the Agda programming language), they created a system where invalid syntax is impossible to write. This saves researchers from writing thousands of lines of boring proof code just to say, "Yes, this variable is in scope." It makes formal verification (proving software is bug-free) easier, safer, and closer to how humans naturally think about language.

Technical Summary: Well-Scoped Locally Nameless Representation of Syntax

Problem Statement
When formalizing languages with binding constructs (e.g., $\lambda$ -calculus, type systems) in interactive theorem provers based on dependent type theory (such as Agda, Lean, or Rocq), a central challenge is managing variable binding and $\alpha$ -equivalence. The "locally nameless" approach, which represents free variables as explicit names and bound variables as de Bruijn indices, has been shown to satisfy the PoplMark criteria for low infrastructure overhead, transparency, and ease of entry. However, standard locally nameless representations suffer from a critical flaw: the inductive definition of terms permits "dangling" indices (indices that exceed the current scope). To ensure correctness, one must restrict the domain to a subset of "locally closed" terms. This necessitates repetitive, manual proofs that operations (like substitution) preserve local closure, creating a significant burden and a source of potential errors in formal developments.

Methodology
The paper proposes a "well-scoped" variant of the locally nameless representation that leverages the dependent type system of Agda to enforce local closure intrinsically, rather than as a separate predicate.

Indexed Inductive Types: Instead of a single type of terms, the library defines a family of types Trm[n] indexed by a natural number $n$ . An n-term is a term where all de Bruijn indices are drawn from the finite type Fin n (natural numbers less than $n$ ).
Locally Closed Terms as 0-Terms: In this framework, "locally closed" terms (those with no dangling indices) correspond precisely to Trm[0]. Terms with free variables are represented as Trm[n] where $n$ corresponds to the number of free variables in scope.
Parameterization by Binding Signatures: The library is generic, parameterized by a Plotkin-style binding signature. This allows the definition of operators, their arities, and the number of names bound in each argument position.
Operations via Dependent Types:
- Scope Weakening: A function Trm[m] -> Trm[n] (for $m \le n$ ) that injects indices, handling the shift required when moving to a larger scope.
- Concretion (Opening): Replacing an index $i$ in an (1+n)-term with a 0-term to produce an n-term. This involves shifting indices greater than $i$ down by one.
- Abstraction (Closing): Replacing a free name in an n-term with an index to produce a (1+n)-term. This involves shifting indices up.
- Substitution: Defined structurally. Because the substitution function maps names to 0-terms (Trm), the "locally closed" condition is enforced by the type system automatically. Substitution on an n-term yields another n-term.

Key Contributions

The WSLN Library: A generic Agda library implementing well-scoped locally nameless terms. It provides the infrastructure for defining syntax, operations (weakening, substitution, abstraction, concretion), and reasoning principles for any language specified by a Plotkin binding signature.
Formal Adequacy Proof: The paper provides a rigorous proof establishing a bijection between:
1. The type of well-scoped locally nameless 0-terms (Trm[0]).
2. The $\alpha$ -equivalence classes of "nameful" terms (terms with explicit names for both free and bound variables).
  This bijection demonstrates that the well-scoped representation correctly captures the semantics of capture-avoiding substitution and $\alpha$ -equivalence.
Elimination of Local Closure Proofs: By encoding scope constraints in the type indices, the need for explicit "locally closed" predicates and the associated proof obligations (e.g., proving that substitution preserves local closure) is eliminated. These properties become consequences of the typing rules.
Handling of Freshness: The library integrates with nominal techniques, using a "finitely inexhaustible" set of atoms (natural numbers) to generate fresh names via cofinite quantification, ensuring that freshness conditions are handled systematically.

Results
The paper validates the approach through three distinct examples implemented in Agda:

$\pi$ -Calculus: Demonstrates the library's applicability beyond $\lambda$ -calculus, handling process expressions and channel names. It highlights that while the library handles the binding structure, type-checking for well-formedness (e.g., ensuring channels are used where expected) remains a separate, user-defined judgment.
Martin-Löf Type Theory (MLTT): Shows how the library facilitates the definition of typing rules. It contrasts "exists-fresh" rules (requiring explicit freshness assumptions) with "cofinite quantification" rules (where freshness is implicit), demonstrating that the well-scoped representation supports the latter, leading to cleaner and more transparent formalizations.
Gödel's System T (Normalization by Evaluation): A substantial development proving the decidability of $\beta\eta$ -conversion. This example illustrates how the well-scoped representation simplifies the semantics of abstraction and the handling of freshness in complex semantic constructions (setoid-valued presheaves), avoiding the need for finitely supported semantic objects.

Significance and Claims
The paper claims that the well-scoped locally nameless representation offers a "straightforward" yet powerful solution to the "trap" of dangling indices found in traditional locally nameless approaches. Its primary significance lies in shifting the burden of ensuring scope correctness from the user (via manual proofs) to the theorem prover's type checker (via dependent types).

The authors emphasize that this approach maintains the transparency required by the PoplMark criteria: formal definitions closely mirror informal conventions, and the "index yoga" (manipulation of de Bruijn indices) is encapsulated within the library's operations. While the implementation requires careful handling of finite ordinals (Fin n) and index shifting, the library parameterizes this complexity, allowing users to define languages and prove properties without managing low-level scope mechanics. The paper modestly notes that while the current binding signatures are unsorted and model simple binding scopes, the approach is robust enough to handle complex type systems and semantic proofs, as evidenced by the System T development.