💻 computer science

Implementing Dependent Type Theory Inhabitation and Unification

This paper introduces Canonical-min, a concise and sound solver for the undecidable problems of inhabitation and unification in dependent type theory, alongside a novel monadic framework for transforming type checkers into efficient solvers and the DTTBench benchmark for evaluation.

Original authors: Chase Norman, Jeremy Avigad

Published 2026-03-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Chase Norman, Jeremy Avigad

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

The Big Picture: Building a Magic Puzzle Solver

Imagine you are trying to build a house, but instead of bricks, you are building with logic. In the world of computer science, there is a powerful system called Dependent Type Theory (DTT). It's like a super-strict language where every piece of code must fit perfectly with every other piece, like a 3D puzzle where the shape of one block changes depending on the block next to it.

Usually, computers are great at following instructions, but they struggle with inventing solutions. If you ask a computer, "Write a program that sorts a list," it might just say, "I don't know how."

This paper introduces a new tool called Canonical-min. Think of it as a super-smart puzzle solver that doesn't just check if a puzzle is solved correctly; it actually finds the missing pieces to solve the puzzle from scratch. The authors managed to build this incredibly complex solver in just 185 lines of code (which is tiny for this kind of task).

The Two Main Challenges

To understand what the paper does, we need to understand the two hard problems it solves:

1. Inhabitation (The "Fill-in-the-Blanks" Game)

Imagine you have a blank space in a sentence that says: "The answer is a [BLANK] that is a number."

The Problem: What goes in the blank? It could be 5, 10, or 100.
The Difficulty: In this complex logic system, the "blank" isn't just a number; it's a whole function or a proof. The computer has to invent a valid piece of code that fits that specific shape.
The Paper's Solution: Canonical-min acts like a detective. It looks at the shape of the blank and tries to invent a piece that fits. If it tries one and it doesn't fit, it backtracks and tries a different one until it finds the perfect match.

2. Unification (The "Matching Game")

Imagine you have two puzzle pieces that look slightly different, but you suspect they are actually the same piece, just rotated or hidden.

The Problem: Piece A says "I am a red circle." Piece B says "I am a [COLOR] circle." Are they the same? Yes, if [COLOR] is "red."
The Difficulty: Sometimes the pieces are complex functions. The computer has to figure out what variables need to be set so that two different-looking expressions become identical.
The Paper's Solution: Canonical-min is a master matchmaker. It looks at the two pieces and says, "If we set variable X to be 5, then these two pieces become identical!"

How It Works: The "Magic Box" Metaphor

The authors built this solver using a clever trick involving Monads. In programming, a "Monad" is like a magic box that can hold a value, but it can also hold "side effects" (like a to-do list or a memory of mistakes).

1. The Type Checker (The Inspector)

First, they built a standard "Inspector" (a type checker). Its job is to look at a piece of code and say, "Yes, this fits," or "No, this is broken."

Analogy: Imagine a security guard at a club. If your ID (the code) matches the dress code (the type), you get in. If not, you get kicked out.

2. The Twist: Turning the Inspector into a Solver

Usually, if the guard says "No," the process stops. But the authors wanted the guard to say, "No, but if you change this one thing, you might get in."

They used a Monadic Framework to turn the "No" into a Constraint.

Analogy: Instead of just kicking you out, the guard hands you a To-Do List. "You can't enter yet. You need to fix your hat. Once you fix your hat, come back and I'll check again."
The computer pauses, writes down the "To-Do List" (the constraint), and goes looking for a solution to that list.

3. The Search (The Deep Dive)

Once the computer has a list of "To-Dos" (constraints), it needs to solve them. It uses a method called Iterative Deepening Depth-First Search.

Analogy: Imagine you are looking for a lost key in a giant, dark maze.
- Depth-First: You go down one hallway as far as you can. If you hit a dead end, you go back and try the next hallway.
- Iterative Deepening: You don't just wander randomly. You say, "I will only walk 1 step away from the start. If I don't find it, I'll walk 2 steps. Then 3 steps." This ensures you don't get stuck in a long, useless hallway forever.
The paper calls this "Entropy." It's like a fuel tank. The solver uses a little fuel to try a path. If it gets stuck, it uses more fuel to try deeper, more complex paths.

Why Is This Special?

It's Complete: Most existing solvers are "incomplete." They are like a student who only knows how to solve easy math problems. If the problem is too weird, they give up. Canonical-min is complete. It will keep trying every possible combination until it finds the answer (or proves no answer exists). It never gives up just because the problem looks hard.
It's Tiny: The entire logic for this super-powerful solver fits in 185 lines of code. Usually, these systems take thousands of lines. The authors achieved this by using a very clever way of organizing data (using "De Bruijn indices" and "Explicit Substitutions"), which is like packing a suitcase so efficiently that you can fit a whole wardrobe in a backpack.
It Works: They tested it against other famous solvers (Twelf, sauto, mimer) using a new benchmark called DTTBench.
- The Result: Canonical-min solved 100% of the problems (31/31). The others solved between 0% and 25%. It was the only one that could solve the hardest logic puzzles.

The Real-World Impact

Why do we care?

Proof Assistants: Tools like Lean (used to prove mathematical theorems) rely on this. If you want to prove a complex theorem, the computer can now automatically fill in the missing steps for you.
Program Synthesis: Imagine telling a computer, "I need a function that sorts a list," and it writes the code for you automatically. This solver is a giant step toward making that happen.

Summary

The authors took a very difficult, abstract problem (teaching a computer to invent logic proofs) and solved it by:

Building a strict Inspector to check logic.
Turning the Inspector's "failures" into To-Do Lists (constraints).
Using a Search Engine that systematically tries every possible way to solve those lists.
Doing it all in a tiny, efficient package.

They didn't just build a better tool; they showed that with the right design, you can build a "perfect" logic solver that is surprisingly small and easy to understand.

1. Problem Statement

The paper addresses the challenge of automated reasoning within Dependent Type Theory (DTT), which serves as the foundation for modern interactive theorem provers (e.g., Lean, Coq). Two fundamental problems in this domain are:

Type Inhabitation: Finding a term (expression) that inhabits a given type. This corresponds to theorem proving and program synthesis.
Unification: Solving equations between terms.

Both problems are undecidable in general DTT. Existing solvers for DTT are typically incomplete, relying on first-order pattern unification which fails to handle the full expressivity of dependent types. While a sound and complete algorithm (Canonical) exists conceptually, its implementation is complex. The authors aim to demystify this by creating a minimal, sound, and complete solver that demonstrates how to transform a standard type checker into a performant search engine.

2. Methodology

The authors introduce Canonical-min, a solver implemented in just 185 lines of Lean code. The methodology relies on a novel representation of terms and a monadic framework that decouples type checking from search logic.

A. Novel Data Structures

The implementation departs from standard inductive term definitions to support efficient manipulation and $\beta$ -reduction:

Term Decomposition: Terms are decomposed into a sequence of bindings, a head, and a spine of arguments.
Explicit Substitution (ES): Instead of standard de Bruijn indices alone, the system uses a linked list of "blocks" (variables or terms) to represent the context. This allows for efficient $\beta$ -reduction and handling of unassigned metavariables.
Metavariables (MVars): Terms are represented as mutable references to assignments. An unassigned metavariable acts as a placeholder that can be filled later during search.
WHNF (Weak Head Normal Form): The system reduces terms to WHNF to check equality. If a term reduces to a function symbol applied to arguments, it compares the head symbols and recursively checks arguments.

B. The Monadic Framework

The core innovation is the use of monads to transform a deterministic type checker into a non-deterministic solver without altering the core checking logic:

Constraint Generation: When the type checker encounters an unassigned metavariable, it does not fail immediately. Instead, it pauses execution and generates a Constraint. This constraint represents the remaining checks needed once the metavariable is assigned.
Continuation Monads (SearchM): The system uses a continuation monad (ContT) to capture the "rest of the computation" when a metavariable is unassigned. This allows the solver to backtrack and try different assignments later.
State Management: The solver maintains a global state containing:
- An array of current assignments for metavariables.
- An array of "stuck" constraints waiting for specific metavariables to be resolved.

C. Search Algorithm

The solver employs Iterative Deepening Depth-First Search (IDDFS):

Entropy Metric: Instead of tree height, the search depth is controlled by a custom "entropy" parameter that increases with each iteration, limiting the complexity of generated terms.
Metavariable Selection: The algorithm selects which metavariable to refine next using a heuristic. It prioritizes metavariables with rigid constraints (equations where one side is a concrete term, not a metavariable) and rightmost metavariables to generate strong unification constraints early.
Domain Generation: For a selected metavariable, the solver computes a "domain" of valid assignments (head symbols and arguments) based on the current context (Explicit Substitution). It recursively attempts each assignment, processes generated constraints, and backtracks if a path fails.

3. Key Contributions

Canonical-min: A sound and complete solver for DTT inhabitation and unification, implemented in a remarkably concise 185 lines of code.
Monadic Transformation: A demonstration of how to convert a standard type checker into a solver using monads (ReaderT, StateT, ContT) to manage constraints and backtracking, proving that search logic can be orthogonal to type checking logic.
Novel Term Representation: A specific data structure using Explicit Substitution and mutable metavariables that facilitates efficient $\beta$ -reduction and unification in a dependent setting.
DTTBench: The introduction of a new benchmark suite consisting of 31 problems derived from the Lean standard library and Mathlib, specifically designed to test DTT inhabitation capabilities (involving equality, inequalities, logic, relations, and sets).

4. Results

The authors evaluated Canonical-min against three other systems: Twelf, sauto, and mimer.

Performance: Canonical-min solved 31/31 problems in the DTTBench suite.
Comparison:
- Twelf: Solved 8/31.
- sauto: Solved 6/31.
- mimer: Solved 2/31.
Qualitative Difference: The other systems largely failed because they rely on incomplete pattern unification. Canonical-min's completeness allowed it to solve problems requiring full dependent type reasoning, such as:
- Transitivity of equality.
- Inductive reasoning on natural number inequalities.
- Properties of transitive closures.
- Cantor's diagonalization argument (proving a function from a set to its powerset is not surjective).

5. Significance

Proof of Concept: The paper proves that a sound and complete DTT solver can be implemented with extreme brevity, making the complex algorithms of systems like Canonical more accessible for study and modification.
Foundation for Automation: By separating the type checker from the search strategy via monads, the authors provide a blueprint for building automated reasoning tools for various type theories (substructural, univalent, modal) without rewriting the core type checker.
Benchmarking: The creation of DTTBench fills a gap in the literature by providing a standardized set of non-trivial dependent type problems for evaluating future solvers.
Educational Value: The code serves as a reference implementation for understanding the mechanics of unification and inhabitation in dependent type theory, bridging the gap between theoretical algorithms and practical implementation.

In conclusion, the paper demonstrates that with the right data structures and control flow abstractions (monads), the "undecidable" problems of DTT inhabitation and unification can be solved completely and efficiently, outperforming existing incomplete solvers on a broad range of mathematical problems.