💻 computer science

Mirroring Call-by-Need, or Values Acting Silly

This paper introduces a degenerated "call-by-silly" calculus that symmetrically combines the worst aspects of call-by-name and call-by-value to demonstrate that call-by-value's contextual equivalence is blind to efficiency, while also providing a corresponding strategy, abstract machine, and tight multi-type system to prove it computes evaluation sequences of maximal length.

Original authors: Beniamino Accattoli, Adrienne Lancelot

Published 2026-07-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Beniamino Accattoli, Adrienne Lancelot

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 a chef in a bustling kitchen, trying to figure out the most efficient way to prepare a complex dish. In the world of computer science, specifically in a field called "programming language theory," chefs are actually mathematicians and logicians who study how computers "think" when they run code. They aren't cooking food, but rather manipulating symbols and instructions. The central question they ask is: "When a computer sees a task, should it do the work right away, or should it wait until it absolutely has to?"

To understand the answer, imagine two different cooking styles. The first style, called "Call-by-Name," is like a lazy chef who refuses to chop an onion until the recipe explicitly demands it. If the recipe says "throw away the onion," the lazy chef never even picks up the knife, saving time and effort. This is "wise" about throwing things away (erasing) but "silly" about chopping, because if the recipe asks for the onion twice, the lazy chef chops it twice, wasting time. The second style, "Call-by-Value," is like a hyper-prepared chef who chops every single ingredient immediately, before the recipe even starts. This is "wise" about chopping (duplicating) because they only do it once, but "silly" about throwing things away, because they might chop an onion that the recipe later says to ignore.

For decades, scientists have been fascinated by a third style called "Call-by-Need," which tries to be the perfect chef: it waits to chop until necessary (wise erasing) but only chops once even if needed multiple times (wise duplicating). But what if we wanted to study the exact opposite? What if we wanted to see what happens when a chef is terrible at both chopping and throwing things away? This is the strange and delightful question that the paper "Mirroring Call-by-Need, or Values Acting Silly" decides to answer.

The authors, Beniamino Accattoli and Adrienne Lancelot, decide to design a new, deliberately inefficient cooking style they call "Call-by-Silly." In this world, the chef chops ingredients even if they are never used (silly duplicating) and throws away ingredients even if they haven't been chopped yet (silly erasing). It sounds like a recipe for disaster, and the authors admit it is "desperately inefficient." However, they don't care about making a good dish; they care about understanding the rules of the kitchen itself. By building this "silly" system, they can prove that the "wise" system (Call-by-Need) is indeed a perfect optimization of the lazy one, and they discover something surprising about the "prepared" system (Call-by-Value).

The paper proves that if you look at the final result of a dish, the "prepared" chef (Call-by-Value) and the "silly" chef (Call-by-Silly) actually produce the exact same outcome, even though the silly chef did a lot of unnecessary chopping. This reveals a hidden blind spot in how we usually measure computer programs: the standard way of checking if two programs are "the same" cannot tell the difference between a smart chef and a silly one if the only difference is how much extra work they did. It turns out that in a pure, effect-free kitchen, the standard rules of equivalence are "blind to efficiency."

To prove this, the authors didn't just guess; they built a mathematical machine, a sort of "robot chef" called the Silly MAM, that follows the silly rules step-by-step. They also created a special counting system using "multi-types" (think of it as a very detailed recipe card that tracks exactly how many times an ingredient is touched). They used this system to count every single step the silly robot took. They found that the silly strategy actually takes the longest possible path to finish a task. While the Call-by-Need robot takes the shortest path, the Call-by-Silly robot takes the maximum number of steps possible.

The paper is a rigorous mathematical proof, not just a simulation. The authors have constructed a new calculus (a set of rules for manipulating symbols), proved that it behaves consistently, and used a formal type system to measure the exact number of steps taken. They showed that their "silly" system is a perfect mirror image of the "need" system. Just as the "need" system combines the best of two worlds, the "silly" system combines the worst.

The most significant finding is that this "silly" behavior exposes a limitation in how we define program equivalence for standard "Call-by-Value" languages. The paper demonstrates that two programs can be mathematically equivalent even if one does a massive amount of useless work and the other does none, provided they don't interact with the outside world (like changing a file or printing to a screen). This suggests that our current tools for checking if programs are "equal" might be missing a crucial detail: they don't count the wasted effort.

In the end, the paper doesn't tell us to start writing "silly" code. Instead, it uses this absurd, inefficient system as a mirror to better understand the efficient ones. It shows us that while "Call-by-Need" is a brilliant optimization, "Call-by-Value" has a hidden flaw in how it views equality: it doesn't care if you are smart or silly, as long as you get the job done. The authors have successfully built a "silly" corner in the map of computer science to help us see the landscape more clearly, proving that sometimes, to understand the best way to do something, you have to study the worst way to do it.

Technical Summary: Mirroring Call-by-Need, or Values Acting Silly

Problem and Motivation
Call-by-need (CbNeed) evaluation for the $\lambda$ -calculus is traditionally understood as an optimization of call-by-name (CbN) that merges the "wise" erasure of CbN (avoiding the evaluation of arguments that are never used) with the "wise" duplication of call-by-value (CbV) (evaluating arguments that are used at least once only once). This paper investigates the theoretical limits of combining duplication and erasure strategies by constructing a "degenerated" calculus, dubbed Call-by-Silly (CbS).

The authors posit that just as CbNeed combines the optimal strategies of CbN and CbV, CbS combines their worst aspects: "silly" erasure (reducing arguments that will never be used, characteristic of CbV) and "silly" duplication (re-evaluating arguments multiple times, characteristic of CbN). While CbS is intentionally inefficient and of no practical use for programming, the authors argue it is theoretically significant for understanding the modularity of duplication and erasure, the nature of contextual equivalence in CbV, and for providing a mirror image to the established theory of CbNeed.

Methodology
The paper employs the Linear Substitution Calculus (LSC) framework, a micro-step calculus with explicit substitutions that separates duplication and erasure rules. The authors define the Silly Substitution Calculus (SSC) by mirroring the construction of the CbNeed LSC:

CbNeed: Uses CbV's duplication rule and CbN's erasure rule.
CbS (SSC): Uses CbN's duplication rule and CbV's erasure rule.

The study is restricted to weak evaluation (reduction does not occur under abstractions). The methodology proceeds through five main phases:

Rewriting Analysis: Establishing basic properties of the SSC, including confluence and the postponement of garbage collection.
Semantic Analysis via Multi-Types: Designing a "silly" multi-type system (non-idempotent intersection types) to characterize termination and evaluation lengths. This system is a dual of the CbNeed system, modifying CbN typing rules to accommodate CbV-style erasure.
Operational Equivalence: Proving that CbS and CbV induce the same contextual equivalence, mirroring the known equivalence between CbN and CbNeed.
Abstract Machine and Strategy: Defining a Silly Milner Abstract Machine (Silly MAM) and a corresponding CbS strategy. The machine extends the standard CbN machine by continuing to evaluate explicit substitutions in the environment even after the main term reaches a normal form.
Quantitative Analysis: Using "tight" type derivations to measure the exact number of evaluation steps and proving the maximality of the CbS strategy.

Key Contributions and Results

The Silly Substitution Calculus (SSC):
The authors define the SSC with specific rewriting rules: multiplicative ( $\to_m$ ), exponential ( $\to_e$ ), and garbage collection by value ( $\to_{gcv}$ ). They prove that the SSC is confluent and that terms are uniformly normalizing (weak normalization implies strong normalization), a non-trivial result given that the SSC allows the duplication of diverging terms.
Operational Equivalence of CbS and CbV:
The paper proves that CbS and CbV are operationally equivalent (induce the same contextual equivalence). This is established by showing that the silly multi-type system characterizes termination for both calculi.
- Significance: This result demonstrates that standard CbV contextual equivalence is blind to efficiency. While CbV and CbS have different erasure policies (distinguishing them from CbN), their differing duplication policies (silly vs. wise) do not affect contextual equivalence in the pure, effect-free setting. The paper notes that this blindness is a fundamental limitation of CbV contextual equivalence, which cannot "count" how many times a sub-term is evaluated.
The Silly Abstract Machine (Silly MAM):
The authors design an abstract machine that implements the CbS strategy. Unlike the standard CbN machine, which stops when the code is a value and the stack is empty, the Silly MAM continues to evaluate explicit substitutions (ESs) in the environment that are no longer needed by the main term. This mirrors the behavior of CbNeed machines but in the opposite direction (evaluating "useless" copies). The machine is proven to terminate on a term $t$ if and only if the SSC terminates on $t$ .
The Call-by-Silly Strategy:
A deterministic (diamond) evaluation strategy for CbS is defined. The strategy is an extension of the CbN strategy on non-erasing steps but includes a specific mechanism to handle "silly" duplications. The authors prove that the Silly MAM implements this strategy.
Quantitative Results and Maximality:
Using tight multi-type derivations, the authors extract the exact number of multiplicative and exponential steps for the CbS strategy.
- Result: The CbS strategy computes maximal evaluation sequences in the weak SSC. That is, if a term has a weak normal form, the CbS strategy will find it, and the length of this sequence is maximal among all possible reduction sequences. This contrasts with CbNeed, which computes minimal sequences.

Significance and Claims
The paper claims that the study of CbS provides a "mirror" to the theory of CbNeed, validating the design of the LSC framework by showing that swapping the "wisdom" of duplication and erasure yields a consistent, albeit inefficient, calculus.

The primary theoretical contribution is the demonstration that CbV contextual equivalence is blind to efficiency. The authors argue that while CbV is often expected to be efficiency-sensitive, in the pure untyped setting, it cannot distinguish between "wise" and "silly" duplications. This insight is presented as a clarification of the limitations of contextual equivalence, distinct from settings with effects where such distinctions are possible.

The paper concludes that while CbS is not a practical evaluation strategy, its rigorous analysis via rewriting, abstract machines, and multi-types offers a deeper understanding of the interplay between duplication, erasure, and semantic equivalence in $\lambda$ -calculi. The authors explicitly state they do not claim CbS has applications in programming or that it solves open problems in efficiency, but rather that it serves as a theoretical tool to expose the structural properties of evaluation strategies.

More like this