💻 computer science

Linearising Explicit Substitutions using Intersection Types

This paper introduces a new term expansion for a calculus with explicit substitutions to establish a correspondence between lambda-terms with explicit substitutions and Boudol's resource-aware lambda-calculus with multiplicities, extending previous applications of term expansion to substructural type systems.

Original authors: Ana Jorge Almeida (LIACC,Faculdade de Ciências da Universidade do Porto), Sandra Alves (CRACS, INESC-TEC,Faculdade de Ciências da Universidade do Porto), Mário Florido (LIACC,Faculdade de Ciências da

Published 2026-07-23

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Ana Jorge Almeida (LIACC,Faculdade de Ciências da Universidade do Porto), Sandra Alves (CRACS, INESC-TEC,Faculdade de Ciências da Universidade do Porto), Mário Florido (LIACC,Faculdade de Ciências da Universidade do Porto)

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 watching a magician pull a rabbit out of a hat. In the world of computer science, the "magic trick" is how a program runs, but the magician's hat is often a bit too mysterious. For decades, the standard way to describe how computer programs work (called the $\lambda$ -calculus) was like a magic trick where the substitution of ingredients happened instantly and invisibly. You'd see a recipe say "mix flour and eggs," and poof! the eggs were gone, mixed in, and the result appeared. But in real life, if you are a chef trying to bake a cake, you need to know exactly how many eggs you have, where they are, and what happens if you run out.

This paper dives into that messy, real-world kitchen. It focuses on a specific problem: how to track resources (like ingredients or memory) when a computer program is running. The authors are working with two main ideas. First, there's "explicit substitutions," which is just a fancy way of saying "let's write down the act of swapping ingredients explicitly, so we can see the steps." Second, they use "intersection types," which is like giving an ingredient a list of all the different roles it can play (e.g., "this egg can be a binder, a leavener, and a filler"). The big question they are asking is: Can we take a standard computer program, break it down into these visible steps, and prove that it behaves exactly like a "resource-aware" version where we count every single copy of every ingredient? This matters because modern computers are often limited by how much memory or processing power they have, and understanding exactly how programs use these resources helps us build faster, safer, and more efficient software.

The Paper's Story: Unwrapping the Magic Trick

The authors, Ana Jorge Almeida, Sandra Alves, and Mário Florido, are essentially trying to build a bridge between two different ways of looking at computer code. On one side, you have the $\lambda$ -calculus with explicit substitutions (specifically a version they call $\lambda xgc$ ). Think of this as a recipe book where every time you swap an ingredient, you write it down in a little note attached to the recipe, rather than just doing it silently. On the other side, they have Boudol's resource-aware calculus, which is like a recipe that comes with a strict inventory list. In this version, if a recipe calls for "eggs," it doesn't just say "eggs"; it says "2 eggs" or "infinite eggs." If the recipe needs 3 eggs but you only have 2, the cooking stops (a "deadlock"), just like a real kitchen running out of supplies.

The paper's main goal is to show that you can take a term (a piece of code) from the first system and "expand" it into the second system, proving that they are doing the exact same thing, just with different levels of detail. They call this process term expansion.

The Two Types of Magic: Infinite vs. Finite

The authors realize that not all resources are created equal. Sometimes, a computer program can use a piece of data as many times as it wants (like a digital file you can copy forever). Other times, resources are limited (like a single-use coupon or a specific amount of memory). To handle this, they propose two different "expansion" methods, like having two different sets of tools for two different jobs.

1. The Infinite Toolkit (ACI Types)
For resources that are unlimited, the authors use a system based on associative, commutative, and idempotent (ACI) intersection types.

The Analogy: Imagine you have a magical infinite supply of flour. In this system, if a recipe needs flour twice, it doesn't matter if you grab two handfuls or one giant handful; it's all the same "flour." The math treats the intersection of "flour" and "flour" as just "flour" again (idempotent).
The Finding: They prove that if you take a program from their explicit substitution system and expand it using these rules, it perfectly matches the behavior of Boudol's system when dealing with infinite resources ( $m = \infty$ ). The program reduces (cooks) in the same way, step-by-step.

2. The Finite Toolkit (AC Types)
For resources that are limited, they switch to associative, commutative, and non-idempotent (AC) intersection types.

The Analogy: Now, imagine you have a limited number of eggs. If a recipe needs two eggs, you must have two distinct eggs. In this system, "egg" $\cap$ "egg" is not just "egg"; it's "two eggs." The math keeps track of the count.
The Finding: They show that this second method successfully expands programs to match Boudol's system for finite resources ( $m \in \mathbb{N}$ ). If the program tries to use more eggs than it has, the expansion reveals the shortage, and the system correctly identifies a "deadlock" (a situation where the program gets stuck because it can't proceed).

The "Weak-Head" Rule: Why We Don't Cook the Whole Cake at Once

One of the most important discoveries in the paper is about how they cook the cake. In real-world programming languages (like Python or JavaScript), computers don't usually cook the entire cake at once. They only cook the very first step they can see (the "head" of the recipe) and stop if they hit a wall. This is called weak-head reduction.

The authors prove that their expansion method works perfectly with this "lazy" cooking style. They show that if you take a program and take one step of cooking (reduction), the expanded version of that program also takes a corresponding step in the resource-aware world.

The Catch: They explicitly show that this magic only works for weak-head reduction. If you try to cook the whole cake at once (strong reduction), the magic breaks. They provide a specific example where a program reduces perfectly in the standard way, but the expanded version gets stuck or behaves differently if you try to force it to cook everything at once. This confirms that their method is designed for the way real computers actually work, not just for theoretical perfection.

What They Don't Claim

It's important to note what this paper doesn't do. They aren't saying they have invented a new programming language that everyone should use tomorrow. They aren't claiming to have solved all problems with memory management. Instead, they have built a mathematical "translation dictionary." They proved that if you speak the language of "explicit substitutions with types," you can translate it into the language of "resource counting," and the meaning stays the same.

They also clarify that this translation isn't a simple one-way street where you just swap words. It's a relationship, not a function. Sometimes, one program can be expanded into multiple different resource-aware versions depending on how you look at the types. This flexibility is a feature, not a bug, allowing them to model different scenarios.

The Big Picture

In the end, this paper is a success story of mathematical mapping. The authors have successfully defined a way to take a standard, somewhat abstract computer program and "linearize" it—breaking it down so that every use of a variable is accounted for, either as an infinite stream or a finite count. They have shown that:

Infinite resources can be modeled using idempotent types (where duplicates don't add up).
Finite resources can be modeled using non-idempotent types (where duplicates count).
This relationship holds true as long as we follow the "weak-head" rules of real-world computing.

By doing this, they provide a solid foundation for future work. They suggest that this "expansion" tool could be used to connect computer programs to other complex systems, like concurrent calculi (where many things happen at once), helping us understand how resources are shared and fought over in a busy digital kitchen. The paper doesn't just say "it works"; it provides the rigorous proof that the translation between these two worlds is sound, opening the door for more precise and resource-efficient software design in the future.

Technical Summary: Linearising Explicit Substitutions using Intersection Types

Problem Statement

The classical $\lambda$ -calculus serves as a robust model for computational functions but lacks mechanisms to observe the operational properties of algorithm execution. This limitation stems primarily from its implicit $\beta$ -contraction, a meta-operation that obscures the mechanics of substitution. While explicit substitution calculi (such as $\lambda\sigma$ ) have been developed to bridge the gap between theory and implementation by making substitutions first-class citizens, previous work on term expansion—a technique used to relate non-linear terms to linear ones—has not addressed calculi with explicit substitutions.

Furthermore, there is a need to relate standard $\lambda$ -terms to resource-aware calculi where function arguments have limited availability (multiplicities). Specifically, the authors aim to fill the gap between the $\lambda$ -calculus with explicit substitutions and Boudol's resource-aware $\lambda$ -calculus with multiplicities, where arguments are treated as bags of resources with explicit counts (finite or infinite).

Methodology

The authors propose a new definition of term expansion tailored for the $\lambda xgc$ -calculus, a variant of explicit substitution calculus that retains variable names (unlike De Bruijn indices) and includes explicit garbage collection. The methodology involves two parallel tracks based on the type of intersection types used:

Infinite Multiplicities ( $m = \infty$ ):
- The authors utilize Associative, Commutative, and Idempotent (ACI) intersection types.
- They define an expansion relation $E^\infty$ that maps terms from the $\lambda xgc$ -calculus to Boudol's calculus with infinite multiplicities ( $\Lambda^\infty$ ).
- In this context, the intersection operator $\cap$ satisfies $\sigma \cap \sigma = \sigma$ , reflecting the unlimited availability of resources.
Finite Multiplicities ( $m \in \mathbb{N}$ ):
- The authors utilize Associative, Commutative, and Non-Idempotent (AC) intersection types.
- They define an expansion relation $E$ that maps $\lambda xgc$ terms to Boudol's calculus with finite multiplicities ( $\Lambda$ ).
- Here, $\sigma \cap \sigma \neq \sigma$ , allowing the type system to track the exact number of times a resource is consumed. The multiplicity is managed in a multiplicative manner, consistent with linear logic terminology.

Key Technical Mechanisms:

Expansion Contexts: The authors define expansion contexts ( $A$ ) as sets of variable-type pairs. For finite multiplicities, these contexts include explicit counts (e.g., $x : \tau^m$ ).
Context Merging: Operations are defined to append contexts ( $\&$ for ACI, $\otimes$ for AC), which handle the distribution of types and multiplicities when variables are substituted or duplicated.
Weak-Head Reduction: The expansion is defined specifically to preserve weak-head reduction ( $\twoheadrightarrow_{bxgc}$ ), which aligns with the evaluation strategies of functional programming languages (reducing only at the outermost redex, not under $\lambda$ -abstractions).

Key Contributions

Novel Term Expansion for Explicit Substitutions: The paper defines the first term expansion framework specifically for a calculus with explicit substitutions ( $\lambda xgc$ ), extending the work of [14] which focused on standard $\lambda$ -terms.
Dual Expansion Definitions: The authors provide two distinct expansion definitions:
- One relating $\lambda xgc$ to Boudol's calculus with infinite multiplicities using ACI types.
- One relating $\lambda xgc$ to Boudol's calculus with finite multiplicities using AC types.
Preservation of Weak-Head Reduction: The paper proves that the expansion relation preserves weak-head reduction. Specifically, if a term $M$ reduces to $M'$ in the $\lambda xgc$ -calculus, the expansion of $M$ reduces to the expansion of $M'$ in Boudol's calculus (Theorem 4.6 and Theorem 4.14).
Resource Tracking: The expansion explicitly infers the availability of resources. For example, the term $(xx)\langle x := I \rangle$ expands to a term where the identity function $I$ is duplicated exactly as many times as $x$ appears in the body, with the multiplicity explicitly encoded in the syntax.

Results

Theoretical Correspondence: The authors establish a formal correspondence between terms typed in intersection type systems and terms in Boudol's resource calculus.
- ACI types correspond to the subset $\Lambda^\infty$ (infinite resources).
- AC types correspond to the subset $\Lambda$ (finite resources).
Deadlock Detection: The framework naturally handles cases of resource exhaustion. If a term requires more resources than available (e.g., substituting a variable with a bag of size 1 when 2 are needed), the expansion leads to a "deadlocked" state in Boudol's calculus, mirroring the inability to reduce the original term further.
Subject Reduction Limitation: The paper notes that the expansion relation preserves weak-head reduction but does not preserve strong reduction. This is attributed to the lack of subject reduction in the underlying intersection type system used to direct the expansion.

Significance

The paper claims significance in providing a simple, uniform framework for addressing linearisation problems in calculi with explicit substitutions. By relating explicit substitution calculi to resource-aware calculi, the work offers a method to:

Meticulously track the resource-aware behavior of terms during evaluation.
Understand how resources are consumed throughout term evaluation.
Bridge the gap between non-linear $\lambda$ -terms and linear/resource-bounded representations without requiring syntactic linearity in the source term.

The authors position this work as a foundation for future research, specifically suggesting the application of term expansion to relate the $\lambda$ -calculus with concurrent calculi (such as the $\pi$ -calculus), which inherently possess limited resource availability. However, the paper does not present these applications as realized results, but rather as a motivated direction for future study.