💻 computer science

How to play the Accordion: Uniformity and the (non-)conservativity of the linear approximation of the λ-calculus (extended version)

This paper investigates the conservativity of the linear approximation of the $\lambda$ -calculus via Taylor expansion, demonstrating that while the property holds for finite terms, it fails for infinitary reductions due to a counter-example called the "Accordion," which is resolved by imposing a uniformity constraint that yields a conservative extension also applicable to $\beta\bot$ -reductions.

Original authors: Rémy Cerda, Lionel Vaux Auclair

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Rémy Cerda, Lionel Vaux Auclair

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, like a giant, self-assembling robot. In the world of computer science, specifically in a field called lambda calculus, these "machines" are actually mathematical expressions that represent computer programs. For decades, scientists have tried to predict what these programs will do by breaking them down into smaller, simpler pieces. One of the most powerful tools for doing this is called linear approximation. Think of it like taking a high-resolution photograph of a complex scene and breaking it down into a grid of tiny, simple pixels. If you understand how the pixels behave, you can understand the whole picture. This method, which uses ideas from calculus (like derivatives) to analyze code, has been a huge success. It allows researchers to prove that if you simplify a program enough, you can predict its final result.

However, there is a tricky question that has lingered for twenty years: Is this simplification process perfectly reversible? In other words, if you take a simplified "pixel" version of a program and watch it change, does every single change it makes correspond to a real, valid change in the original, complex program? For simple, finite programs, the answer is a confident "yes." But for programs that run forever or involve infinite loops, the rules get fuzzy. This paper asks: If we let our simplified models run wild with infinite steps, do they start doing things that the original program could never actually do? The authors set out to find the answer, and in doing so, they discovered a surprising glitch in the system.

The paper, titled "How to Play the Accordion," dives deep into this problem by testing the limits of linear approximation. The researchers first confirm that for standard, finite programs, the approximation is safe and reliable; every move the simplified model makes is a legitimate move the original program could make. But the story changes dramatically when they look at infinitary programs—those that involve infinite sequences of steps. Here, they prove that the approximation is not conservative. This means the simplified model can perform "magic tricks" that the real program cannot.

To demonstrate this, the authors design a specific, mind-bending counter-example they call the Accordion. Imagine a program that stretches and compresses itself in a rhythmic pattern, like an accordion being played. The authors show that while the simplified "pixel" version of this Accordion can be reduced to a specific final state through a series of steps, the original, infinite Accordion program cannot reach that same state through any valid sequence of its own rules. The simplified model gets ahead of itself, performing a reduction that looks correct in the pixel world but is impossible in the real world. It's as if a shadow puppet show could perform a move that the actual puppeteer's hand could never physically make.

The paper doesn't just stop at finding the problem; it offers a solution. The authors show that by adding a rule called uniformity—which essentially forces the simplified model to keep all its parts in sync, like a marching band where everyone steps at the exact same time—they can fix the glitch. By restricting the simplified model to only these "uniform" moves, they create a new system where the approximation becomes conservative again. In this stricter system, every move the model makes is guaranteed to be a valid move for the original program, even for infinite ones. They also extend this finding to include programs that might crash or produce "undefined" results, ensuring the theory holds up even in messy, real-world scenarios.

In short, the paper proves that while linear approximation is a powerful tool, it needs a "seatbelt" called uniformity to stay safe when dealing with infinite computations. Without it, the approximation can hallucinate behaviors that don't exist in reality. With it, the map perfectly matches the territory, allowing scientists to trust their simplified models even when dealing with the most complex, infinite loops imaginable.

Technical Summary: "How to Play the Accordion: Uniformity and the (Non-)Conservativity of the Linear Approximation of the $\lambda$ -Calculus"

Problem Statement
The paper investigates the conservativity of the linear approximation of the $\lambda$ -calculus, specifically within the framework of Ehrhard and Regnier's differential $\lambda$ -calculus and resource calculus. While it is well-established that the Taylor expansion $T(M)$ of a $\lambda$ -term $M$ allows for the simulation of $\beta$ -reduction (i.e., if $M \to_\beta N$ , then $T(M) \twoheadrightarrow_r T(N)$ ), the converse question remains: Is every reduction between Taylor expansions induced by an actual reduction in the source $\lambda$ -calculus?

Formally, given a reduction $T(M) \twoheadrightarrow_r T(N)$ in the resource calculus (acting on infinite linear combinations of resource terms), does there exist a $\beta$ -reduction sequence $M \to_\beta N$ ? The authors distinguish between two settings:

Finite $\lambda$ -calculus: Terms are finite, and reductions are finite sequences.
Infinitary $\lambda$ -calculus ( $\lambda^{001}$ ): Terms may be infinite (coinductive), and reductions may be infinite sequences ( $\to^{001}_\beta$ ), provided redexes are fired at increasing depths.

The central problem is whether the linear approximation is a conservative extension of the source calculus in these settings.

Methodology
The authors employ a combination of rewriting theory, coinductive definitions, and the "mashup" technique (relating source terms to their resource approximants).

Finite Case Analysis: For finite terms, the authors adapt the "mashup" proof technique used by Kerinec and Vaux Auclair. They define a relation $\vdash$ linking a $\lambda$ -term to its resource approximants. By proving that if $T(M) \twoheadrightarrow_r T(N)$ , then $M \vdash T(N)$ , and subsequently that $M \vdash T(N)$ implies $M \to^*_\beta N$ , they establish conservativity for the finite case.
Infinitary Counterexample (The Accordion): To address the infinitary case, the authors construct a specific counterexample, the Accordion ( $A$ $A$ ). This term is designed to simulate an infinite reduction sequence that "stretches" and "compresses" its structure.
- The term $A$ reduces to a sequence of terms $A_n$ that approximate an infinite term $\bar{A} = (\langle T \rangle)(\langle F \rangle)\omega$ .
- Crucially, while $T(A) \twoheadrightarrow_r T(\bar{A})$ holds, the authors prove that no valid infinitary $\beta$ -reduction $A \to^{001}_\beta \bar{A}$ exists. The reduction paths of $A$ require "global" steps at bounded depths that violate the stratification condition required for infinitary $\beta$ -reduction (Lemma 2.5).
Uniformity and Coherence: To recover conservativity in the infinitary setting, the authors introduce uniformity, a property originally central to Ehrhard and Regnier's work. They define a coherence relation ( $\bowtie$ $⋈$ ) on resource terms and restrict the reduction relation to uniform sums (sums where all elements are pairwise coherent).
- They define a uniform resource reduction ( $\to^{\curvearrowright}_r$ ) and its infinitary closure ( $\to^{\curvearrowright \infty}_r$ ).
- This restriction ensures that reductions in the resource calculus correspond strictly to reductions in the source calculus, eliminating "non-uniform" paths that do not map to actual $\beta$ -reductions.
Extension to $\beta_\perp$ : The authors extend these results to $\beta_\perp$ -reduction (which collapses unsolvable terms to $\bot$ ), showing that uniformity preserves conservativity even when $\bot$ -reductions are involved.

Key Contributions

Conservativity for Finite Terms: The paper provides a rigorous proof that the linear approximation is conservative with respect to the finite $\lambda$ -calculus (Theorem 3.1).
Non-Conservativity for Infinitary Terms: The authors demonstrate that the standard pointwise resource reduction ( $\twoheadrightarrow_r$ ) is not conservative with respect to the infinitary $\lambda$ -calculus. They construct the Accordion counterexample (Theorem 4.4), proving that $T(A) \twoheadrightarrow_r T(\bar{A})$ does not imply $A \to^{001}_\beta \bar{A}$ .
Restoration via Uniformity: The paper identifies uniformity as the missing ingredient required to restore conservativity. By restricting the resource calculus to uniform reductions ( $\to^{\curvearrowright \infty}_r$ ), the authors prove that the linear approximation becomes a conservative extension of the infinitary $\lambda$ -calculus (Theorem 5.10).
Extension to $\beta_\perp$ : The results are generalized to include $\beta_\perp$ -reductions, showing that the uniform approach correctly simulates and conserves reductions involving the undefined term $\bot$ (Theorems 5.18 and 5.19).

Results

Finite Setting: The simulation of finite $\beta$ -reduction by resource reduction is conservative.
Infinitary Setting (Standard): The simulation of infinitary $\beta$ -reduction by standard pointwise resource reduction is non-conservative. The Accordion term $A$ reduces to $\bar{A}$ in the resource calculus but not in the $\lambda$ -calculus.
Infinitary Setting (Uniform): The simulation of infinitary $\beta$ -reduction by uniform resource reduction is conservative.
$\beta_\perp$ Setting: The non-conservativity of the standard reduction extends to $\beta_\perp$ -reduction, while the uniform reduction remains conservative for $\beta_\perp$ as well.

Significance
The paper clarifies the precise conditions under which linear approximation serves as a faithful model of $\lambda$ -calculus dynamics. It resolves a conjecture from the first author's PhD thesis regarding the non-conservativity of the quantitative linear approximation in the infinitary setting.

The primary significance lies in the identification of uniformity not just as a semantic property of Taylor expansions, but as a necessary syntactic constraint on the reduction relation itself to ensure conservativity. Without this restriction, the resource calculus allows "ghost" reductions that have no counterpart in the source calculus, particularly in the presence of infinite terms. The work refines the understanding of the "commutation theorem" (normalization commutes with approximation) by distinguishing between simulation and conservativity, showing that while simulation holds generally, conservativity requires the stricter uniform framework.

The authors explicitly state that their work improves upon previous conference versions by providing full proofs for the counterexample and the uniformity results, and by extending the analysis to $\beta_\perp$ -reductions, which are crucial for relating terms to their Böhm trees.

Technical Summary: "How to Play the Accordion: Uniformity and the (Non-)Conservativity of the Linear Approximation of the λ\lambdaλ-Calculus"

More like this

Technical Summary: "How to Play the Accordion: Uniformity and the (Non-)Conservativity of the Linear Approximation of the $\lambda$ -Calculus"