💻 computer science

Dependent Multiplicities in Dependent Linear Type Theory

This paper introduces a novel dependent linear type theory that enables variable multiplicities to depend on other variables, thereby providing precise resource annotations for branching and recursive programs through an embedding of linear logic into dependent type theory, supported by a categorical semantics and an Agda implementation.

Original authors: Maximilian Doré

Published 2026-05-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Maximilian Doré

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 Idea: A "Smart" Resource Manager

Imagine you are writing a computer program. In the world of computer science, some things are like resources (like a file you open, a battery you drain, or a secret key you use). You want to make sure your program uses these resources exactly the right number of times: not too many (which wastes them or causes errors) and not too few (which leaves work undone).

For a long time, computer scientists have used a system called Linear Logic to track these resources. Think of it like a strict librarian who says, "You can check out this book exactly once. If you try to check it out twice, the system stops you."

However, this strict librarian has a problem: they are too rigid. They can't handle situations where the number of times you need a resource depends on a decision you make while the program is running.

The Problem with the Old Rules:
Imagine you have a function that decides whether to bake a cake or make a salad based on a boolean switch (True/False).

If the switch is True, you might need 3 eggs.
If the switch is False, you might need 0 eggs.

Old systems couldn't say, "The number of eggs depends on the switch." They forced you to say, "You need 3 eggs no matter what," or "You need 0 eggs no matter what." This is inefficient and often impossible for complex programs involving loops or branching logic.

The Solution: "Dependent Multiplicities"

This paper introduces a new system where the number of times you use a resource (the multiplicity) can depend on other variables in the program.

Think of it like a smart vending machine instead of a strict librarian.

Old System: The machine says, "You can buy exactly 1 soda." (Period).
New System: The machine says, "You can buy as many sodas as the number of dollars in your wallet." If you put in $5, you get 5 sodas. If you put in $2, you get 2. The rule depends on the value you provide.

In this new theory, the "multiplicity" (the number of times a variable is used) isn't a fixed number written in stone. It's a dynamic calculation that happens while the program runs.

How It Works: The Two Layers

The author, Maximilian Doré, builds this system by combining two different ways of thinking about logic:

The "Host" Theory (The Brain): This is the standard, flexible logic used in most modern programming languages. It handles the "thinking" part: making decisions, calculating numbers, and checking conditions.
The "Linear" Theory (The Wallet): This is the strict logic that tracks resources.

The magic of this paper is how they connect them. Instead of the "Wallet" (Linear Logic) being a separate, rigid box, it is embedded inside the "Brain" (Host Theory).

The Analogy: Imagine the "Brain" is a chef and the "Wallet" is the inventory of ingredients.
- In old systems, the chef had to write down a fixed recipe: "Use 2 eggs."
- In this new system, the chef can say: "Use n eggs," where n is a number the chef calculates while cooking based on how hungry the customers are. The inventory system (Linear Logic) updates itself in real-time based on the chef's calculation.

Key Features Explained Simply

1. Dynamic Branching (The "If/Else" Problem)
In the paper, the author shows how to handle "If/Else" statements perfectly.

Scenario: You have a boolean switch.
Old Way: Both the "If" path and the "Else" path had to use the exact same amount of resources.
New Way: The "If" path can use 5 resources, and the "Else" path can use 2. The system knows exactly how many resources were used because it looks at the switch value before deciding the path.

2. Recursive Data (The "Tree" Problem)
The paper handles complex data structures like trees (a list of lists, or a family tree).

Scenario: You want to apply a function to every leaf on a tree.
Old Way: You couldn't easily say, "Use the function exactly as many times as there are leaves," because the system didn't know how many leaves there were until the program finished running.
New Way: The system calculates the number of leaves first, then sets the rule: "Use the function LeafCount times." It works perfectly even for trees of any size.

3. The "Real" vs. The "Spec"
The paper distinguishes between two types of code:

The Specification (The Blueprint): This is the part where you calculate numbers and make decisions. It's flexible.
The Execution (The Construction): This is the part where resources are actually consumed.
The system allows you to erase the "Blueprint" part after you've done the math, leaving only the efficient "Construction" part. This means the final program is fast and doesn't carry around unnecessary calculation baggage.

Why This Matters

The author implemented this system in a programming language called Agda. They proved that:

It is mathematically sound (it works logically).
It can type programs that previous systems couldn't handle (like complex branching and recursive functions).
It gives a precise "receipt" for every program, showing exactly how many times every resource was used, even when that number changes based on the program's logic.

Summary Metaphor

Imagine you are managing a construction site.

Old Systems: You have a foreman who says, "We need exactly 100 bricks for this wall," regardless of whether the wall is big or small. If the wall is small, you have leftover bricks. If it's big, you run out.
This Paper's System: You have a smart foreman who looks at the blueprints, counts the bricks needed for this specific wall, and orders exactly that amount. If the wall changes size halfway through, the foreman adjusts the order instantly.

This paper gives computer scientists a way to build that "smart foreman" for software, ensuring programs are both flexible and perfectly efficient with their resources.

Problem Statement
Existing quantitative type theories, such as Quantitative Type Theory (QTT) and Graded Modal Type Theory, allow for resource annotations where variables have multiplicities specifying how often they are used. However, these systems typically rely on static multiplicities drawn from a fixed resource algebra (e.g., natural numbers or semirings). This static nature creates significant limitations when dealing with program logic that does not directly represent resources but organizes them, such as branching (conditionals) and recursion.

In current systems, a boolean condition used to select between two branches requires both branches to consume identical resources, which is often impractical since different branches typically perform different operations. Similarly, in higher-order functions or inductive types (like binary trees), the number of times a function is applied or a resource is consumed often depends on values known only at runtime (e.g., the number of leaves in a tree). Previous attempts to combine Dependent Type Theory (DTT) with linear logic struggled with the question of whether types depending on terms constitute a "use" of those terms. While McBride and Atkey argued that types are for contemplation and not computation (allowing dependency on linear variables), their resulting QTT still restricts multiplicities to static elements, failing to capture the dynamic resource usage inherent in recursive programs and data-dependent branching.

Methodology
The paper proposes a novel dependent linear type theory that embeds linear logic directly into a standard intuitionistic Dependent Type Theory (the "host theory"). The core innovation is the treatment of multiplicities not as static algebraic elements, but as terms within the host theory itself.

Two Entailment Relations: The system distinguishes between two judgments:
- $\vdash$ : The standard intuitionistic DTT (host theory), used for defining types, terms, and dependencies.
- $\Vdash$ : A resource-aware calculus where terms are derived from "supplies" (linear contexts).
Supplies as Intuitionistic Types: Unlike traditional linear contexts, supplies in this system are terms of the host theory. This allows the host theory to compute with resource annotations. Specifically, the system utilizes the natural numbers of the host theory to define a "multiplication" of supplies ( $\Delta \hat{m}$ ), where $m$ is a term of type $\mathbb{N}$ . This operation allows a supply to be duplicated $m$ times, where $m$ can depend on other variables in the context.
Dynamic Multiplicities: By allowing the multiplicity $m$ to be an open term of the host theory, the system supports dynamic resource annotations. For example, a function mapping over a tree can specify that a function $f$ is used exactly leafs(t) times, where leafs(t) is computed from the structure of the input tree $t$ .
Type Formers: The paper defines linear versions of standard DTT type formers (functions, pairs, booleans, and W-types) annotated with these dynamic multiplicities. Crucially, the elimination rules for booleans and W-types allow resources to be distributed differently across branches or constructors based on runtime values.
Semantics: The semantics are characterized as "Linear Categories with Families" (lCwF), which are Categories with Families (CwF) indexed in symmetric monoidal categories. This structure generalizes Quantitative CwFs used for QTT.

Key Contributions

Syntax with Dependent Multiplicities: The paper presents a syntax where variable multiplicities are terms of the host theory, enabling precise typing of programs involving branching and recursion that were previously untypeable in linear systems.
Linear W-Types: A principled treatment of inductive types (specifically W-types with finite positions) in a linear setting. The system provides introduction and elimination rules that correctly account for the dynamic resource usage of recursive structures.
Semantic Characterization: The authors define lCwFs as the semantic model for the theory, showing how standard DTT models and linear logic models combine. They demonstrate that this model justifies the intricate rules for linear W-types and generalizes existing models for QTT.
Realisability and Erasure: A realisability model is constructed (based on BCI-algebras) to show that the intuitionistic fragment ( $\vdash$ ) can be erased for computation, leaving only the linear fragment ( $\Vdash$ ) for execution, similar to the 0- and 1-fragments of QTT.
Implementation: The theory is implemented in Agda. The implementation uses the semantic interpretation (mapping linear judgments to intuitionistic terms equipped with supply witnesses) to create a rigorous, albeit not yet practical, type checker.

Results

Expressivity: The system successfully types programs that require dynamic resource counting, such as a map function for binary trees where the usage of the mapping function is proportional to the number of leaves.
Completeness: The paper proves a completeness result for "clearly linear terms" (intuitionistic terms that do not discard or duplicate values via specific eliminators), showing they can be precisely typed in the linear system.
Recovery of Intuitionistic Logic: By introducing a linear exponential comonad ("!"), the system can recover full intuitionistic logic within the linear fragment, allowing for unrestricted use of resources where necessary.
Decidability Trade-off: The authors acknowledge that type-checking is undecidable in the general case because it requires comparing open terms of natural numbers (e.g., checking if $\Delta \hat{m}$ equals $\Delta \hat{n}$ ). However, they note that propositional equality in the host theory can be used to convince the type checker of resource equivalence.

Significance
The paper claims to provide a more expressive version of Quantitative Type Theory by moving from static resource algebras to dynamic, computable multiplicities derived from the host theory. By embedding linear logic into DTT rather than treating them as separate logics, the system avoids the restrictive dichotomy between intuitionistic and linear variables found in prior work. This allows for a "principled resource-aware treatment" of a large class of inductive types and higher-order functions. The work demonstrates that existing dependently typed languages can be extended with this system, offering a path toward more precise resource management in functional programming without sacrificing the expressiveness of dependent types. The authors position their work as a generalization of QTT that resolves the limitations of static multiplicities in handling runtime-dependent resource usage.