💻 computer science

Approximation theory for distant Bang calculus

This paper develops a unified approximation semantics for the Bang-calculus with explicit substitutions and distant reductions (dBang) by defining Böhm trees and Taylor expansion within this framework, thereby generalizing and subsuming the separate approximation theories of Call-by-Name and Call-by-Value λ-calculi.

Original authors: Kostia Chardonnet, Jules Chouquet, Axel Kerinec

Published 2026-07-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kostia Chardonnet, Jules Chouquet, Axel Kerinec

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 understand how a complex machine works, but the machine is made of invisible, shifting gears. In the world of computer science, this machine is the Lambda Calculus, a mathematical system used to describe how computer programs run.

For decades, scientists have tried to build a "map" of how these programs behave. They have two main ways of drawing this map:

The "Tree" Map (Böhm Trees): This looks at the program's structure, like peeling an onion layer by layer to see what's inside. If the onion is rotten (the program crashes or loops forever), the map says "Nothing here."
The "Resource" Map (Taylor Expansion): This looks at the program as a collection of tiny ingredients. It asks, "If I run this program, how many times do I use each ingredient?" It breaks the program down into a massive list of all possible ways the ingredients could be used.

The Problem:
For a long time, these two maps worked perfectly for one type of cooking style called Call-by-Name (where you wait to see what ingredients you need before you grab them). However, for the other style, Call-by-Value (where you must prepare all ingredients before you start cooking), the maps were messy. The "Tree" map didn't fit well with the "Resource" map, and sometimes the cooking process would get stuck because the rules were too strict.

The Solution: The "Bang" Calculator
The authors of this paper introduce a new, unified kitchen called the dBang-calculus. Think of this as a "Super-Kitchen" that can simulate both cooking styles perfectly.

It uses a special tool called the "Bang" (!) to freeze ingredients (delaying their preparation).
It uses a "Dereliction" tool to unfreeze them.
It uses "Distant Substitutions," which is like having a delivery robot that can drop ingredients into a pot from across the room, rather than having to walk over and stir them manually. This prevents the cooking process from getting stuck.

What They Did:
The authors built a new set of maps for this Super-Kitchen:

Approximation Trees: They created a new version of the "Tree" map that works for this Super-Kitchen. It shows the shape of the program as it runs, even if it runs forever.
Taylor Expansion: They adapted the "Resource" map to fit this new kitchen, showing exactly how the "Bang" and "Dereliction" tools handle ingredients.

The Big Discovery (The Commutation Theorem):
The most exciting part is that they proved these two maps are actually the same thing, just viewed differently.

If you take the "Tree" map of a program and break it down into its "Resource" ingredients, you get the exact same result as if you took the original program and broke it down into ingredients first, then looked at the final shape.
Analogy: Imagine you have a Lego castle. You can either:
- Take a photo of the whole castle, then list every single brick used in the photo.
- Or, take the castle apart into a pile of bricks, sort them, and then look at the photo of the pile.
- The authors proved that for this new Super-Kitchen, both methods give you the exact same list of bricks.

Why It Matters:

Unification: Before this, scientists had to study the "Name" style and "Value" style separately. Now, they can study them together in one place.
Meaningful vs. Nonsense: They showed that if a program has a "non-empty" Resource map (meaning it actually uses some ingredients to do something), it is a "meaningful" program. If the map is empty, the program is nonsense (it does nothing or crashes). This works for both cooking styles now.

In Summary:
The authors built a universal translator for computer program behavior. They created a new system (dBang) that fixes the glitches in the old "Value" style, and they proved that two different ways of analyzing programs (looking at the shape vs. looking at the ingredients) are perfectly compatible in this new system. This allows computer scientists to understand complex, infinite, or resource-heavy programs with a single, unified set of rules.

Technical Summary: Approximation Theory for Distant Bang Calculus

1. Problem Statement

Approximation theory serves as a central approach to $\lambda$ -calculus semantics, characterizing program behavior through finitary or infinitary means. While well-established for Call-by-Name (CbN) via Böhm Trees and Taylor Expansion, the Call-by-Value (CbV) setting has historically lagged behind. Recent developments in CbV Böhm trees (e.g., Kerinec [29, 28]) revealed that standard CbV reduction (Plotkin's $\beta_v$ ) is "too weak," often causing reduction to get stuck when arguments are in normal form but not values. This necessitated alternative frameworks, such as the $\lambda\sigma_v$ -calculus with permutation rules ( $\sigma$ -rules) or distance-based calculi (dCbV).

The Bang-calculus (Bang) was proposed as a unifying framework subsuming both CbN and CbV via Linear Logic translations. However, the standard Bang-calculus inherits the CbV issue of ill-formed redexes blocking evaluation. While $\sigma$ -rules could theoretically resolve this, they fail to preserve confluence in the Bang setting. The distant Bang-calculus (dBang) [15] offers a solution by utilizing explicit substitutions and "distant" reductions, ensuring confluence without $\sigma$ -rules.

Despite progress in dBang regarding confluence and meaningfulness [30, 9, 15], a comprehensive approximation theory for dBang remained underdeveloped. Specifically, there was no unified framework defining Böhm-like approximation trees and Taylor expansions for dBang, nor a proof of the Commutation Theorem relating them. Furthermore, while recent generic approaches (Mazza & Dufour [19]) exist, they lack a direct notion of meaningfulness and do not clearly relate back to the specific solvability/scrutability notions of CbN and CbV.

2. Methodology

The authors develop a unified approximation theory for dBang by integrating two central paradigms: Taylor Expansion (resource-sensitive semantics) and Approximation Trees (Böhm tradition).

2.1 The Resource Calculus ( $\delta$ Bang)

The authors define a resource calculus $\delta$ Bang as the target for Taylor expansion. This calculus replaces exponentials ( $!M$ ) with finite multisets (bags) of resource terms.

Approximation Relation ( $\triangleleft!$ ): A multilinear relation is defined between resource terms and dBang terms.
Reduction: The reduction relation $\Rightarrow_\delta$ is non-deterministic due to permutations of bags but is strongly normalizing due to linearity.
Taylor Normal Form (TNF): Defined as the set of full normal forms of all resource approximants of a term.

2.2 Approximation Trees

The authors define Approximation Trees for dBang by extending the calculus with a symbol $\bot$ representing undefined computation.

Approximants: A grammar of terms containing $\bot$ is defined, representing normal forms potentially containing undefined subterms.
Ideal Completion: The set of approximants for a term $M$ , denoted $A(M)$ , forms an ideal under a contextual preorder $\sqsubseteq$ . The approximation tree $AT!(M)$ is the supremum of this ideal, representing the limit of the term's behavior.
Distinction: Unlike classical CbN Böhm trees which restrict approximants to head normal forms, the authors adopt a broader definition (similar to Lévy-Longo trees in CbN and CbV Böhm trees in CbV) to accommodate the specific semantics of dBang and its embeddings.

2.3 Translations

To validate the framework, the authors utilize existing translations of distant Call-by-Name (dCbN) and distant Call-by-Value (dCbV) into dBang. They prove that these translations preserve reduction steps and meaningfulness, allowing results derived in dBang to be projected back onto dCbN and dCbV.

3. Key Contributions and Results

3.1 Simulation and Commutation

The paper establishes a rigorous link between the operational reduction of dBang and its approximations:

Simulation Theorem (Theorem 21): The Taylor expansion of a dBang term simulates its reduction. Specifically, if $M \to! N$ , then the set of Taylor expansions $T(M)$ reduces to $T(N)$ via parallel resource reduction.
Commutation Theorem (Theorem 46): This is the central result. It states that the Taylor expansion of the approximation tree of a term is equal to the Taylor normal form of the term itself:
$T(AT!(M)) = TNF(M)$
This confirms that the infinitary semantics (trees) and the resource-sensitive semantics (Taylor expansion) are consistent within the dBang framework.

3.2 Recovery of CbN and CbV Cases

By translating dCbN and dCbV into dBang, the authors recover the approximation theories for these specific calculi:

Theorem 59: The approximation tree of a translated term in dBang corresponds exactly to the translation of the approximation tree in the source calculus.
Theorem 60: The Commutation Theorem holds for both dCbN and dCbV as a direct consequence of the dBang result.

3.3 Meaningfulness and Taylor Expansion

The paper investigates the relationship between meaningfulness (the ability of a term to reduce to a value under a testing context) and the non-emptiness of the Taylor normal form.

Theorem 61: If a dBang term is meaningful, its Taylor normal form is non-empty ( $TNF(M) \neq \emptyset$ ).
The Converse: The converse does not hold for the general dBang calculus; there exist meaningless terms with non-empty Taylor normal forms (e.g., terms involving "clashes" like $xx$).
Fragments: However, for the specific fragments corresponding to dCbN ( $dBang_N$ $d B an g_{N}$ ) and dCbV ( $dBang_V$ $d B an g_{V}$ ), the equivalence is restored:
- Corollary 68 (dCbN): $M$ is meaningful iff $TNF(M) \neq \emptyset$ .
- Corollary 73 (dCbV): $M$ is meaningful iff $TNF(M) \neq \emptyset$ .

4. Significance and Claims

The paper claims to provide a unifying framework for approximation theory that captures both infinitary and resource-sensitive semantics for CbN and CbV within a single system (dBang).

Unification: It demonstrates that the distinct developments for CbN and CbV can be subsumed under the dBang calculus, resolving the historical need for separate semantic theories.
Robustness: By using the distant variant (dBang), the authors avoid the confluence issues associated with $\sigma$ -rules in the standard Bang calculus, providing a cleaner setting for approximation theory.
Bridging Semantics: The Commutation Theorem establishes a deep bridge between the "shape-based" infinitary semantics (Approximation Trees) and the "resource-based" differential semantics (Taylor Expansion) in a unified setting.
Characterization of Meaningfulness: The work provides a syntactic characterization of meaningfulness for dCbN and dCbV via non-empty Taylor normal forms, extending known results from standard CbN/CbV to their distant variants.

The authors modestly note that while the equivalence between meaningfulness and non-empty Taylor normal forms holds for the translated fragments, it remains an open question whether a larger, generic fragment of dBang (beyond the translations) can be characterized similarly. They also suggest future work extending these notions to proof structures, building upon the work of Mazza and Dufour.