A Simple and Efficient Implementation of Strong Call by Need by an Abstract Machine
Małgorzata Biernacka, Witold Charatonik, Tomasz Drab · 2026
Read A Simple and Efficient Implementation of Strong Call by Need by an Abstract Machine by Małgorzata Biernacka, Witold Charatonik, Tomasz Drab (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21949.txt.
Introduction
Biernacka and co-authors implement strong call-by-need, a lazy evaluation style that also fully normalizes terms. No earlier system was both simple and fast. Their RKNL abstract machine came automatically from a higher-order evaluator using memothunks for sharing. A standard tool turned the evaluator into a machine description, short and clear. The team proves the machine extends the lazy Krivine machine for weak call-by-need. It also tracks normal-order evaluation with bilinear overhead, linear in both reductions and input size.
Catalog record
| CREATOR | Małgorzata Biernacka, Witold Charatonik, Tomasz Drab |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 152538 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21949
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Simple and Efficient Implementation of Strong Call by Need by an Abstract Machine Małgorzata Biernacka, Witold Charatonik, Tomasz Drab Abstract . Strong call-by-need combines full normalization with the sharing discipline of lazy evaluation, yet no prior implementation achieved both simplicity and efficiency. We introduce RKNL, an abstract machine that realizes strong call-by-need with bilinear overhead. The machine has been derived automatically from a higher-order evaluator that uses the technique of memothunks to implement laziness. By employing an off-the-shelf transformation tool implementing the “functional correspondence” between higher-order interpreters and abstract machines, we obtained a simple and concise description of the machine. We prove that the resulting machine conservatively extends the lazy version of Krivine machine for the weak call-by-need strategy, and that it simulates the normal-order strategy in a bilinear number of steps, i.e., linear in both the number of β \beta -reductions and the size of the input term. \jfpYear 2026 \orcid 0000-0001-8094-0980 \orcid 0000-0001-7062-0385 \orcid 0000-0002-6629-5839 1. Introduction Lambda calculus is a well-established model for functional programming languages. Practical implementations rely on a deterministic reduction strategy (also known as evaluation strategy), which restricts the general \beta -reduction rule to specific positions within a term. Popular incarnations of the lambda calculus include the full-fledged programming languages OCaml and Haskell, each of which adopts a different evaluation strategy: weak call-by-value (CbV) and weak call-by-need (CbNd), respectively. A strategy is called weak if it does not descend into and reduce under lambda abstractions; hence, any lambda abstraction is treated as a value. The most widely used strategy in practical programming is weak CbV, where each argument is evaluated exactly once, before being passed to the function, even if its result is not used in the function body. In contrast, weak call-by-name (CbN) performs \beta -reduction without evaluating the argument beforehand. Consequently, an argument may be evaluated multiple times if it is needed more than once, i.e., if the variable it replaces occurs more than once in the function body in positions not eliminated by \beta -reduction. To mitigate this inefficiency, practical implementations (such as Haskell) employ call-by-need evaluation, which lazily evaluates arguments and memoizes their results for reuse. In this strategy each argument is evaluated at most once, only if it is needed. In some applications, weak strategies are insufficient. The development of proof assistants based on dependent type theory (such as Rocq or Agda) has prompted deeper investigation into strong reduction in the lambda calculus and its implementations. Strong reduction computes full normal forms of terms (required for type checking in proof assistants), necessitating reductions inside lambda abstractions and handling of open terms. A natural way to obtain a strong strategy from a weak one is to first weakly reduce the term to a value, then recursively reduce within function bodies and argument positions of rigid terms —terms of the form x\ t_{1}\ldots t_{n} , where the variable x will never be substituted and thus cannot create new \beta -redexes. Strong strategies defined this way are conservative extensions of their weak counterparts. In this work, we show the first efficient abstract machine for Strong CbNd: the RKNL machine. It is derived in a mechanical way using functional programming techniques, and we give its formal account. Our goal is twofold: (a) to provide a simple and concise definition of an abstract machine for Strong CbNd, and (b) to facilitate reasoning about the key properties of the machine and its underlying strategy, including its correctness and complexity. To achieve these goals, we adopt the derivational approach of Biernacka et al. 2021 , previously applied to Strong CbV. We begin with a standard higher-order normalization-by-evaluation function known to correspond to normal-order reduction Biernacka et al. 2020 . This normalizer is then optimized by the standard technique of memoization to avoid recomputation of intermediate values. Finally, we apply the functional correspondence transformation, as implemented in Racket by Buszka and Biernacki 2021 , to systematically derive a concise abstract machine. We prove that the resulting RKNL machine correctly simulates normal-order reduction, and as a measure of its efficiency we give a simple proof that it is reasonable in the sense of Accattoli et al. Accattoli and Dal Lago 2016 ; Accattoli et al. 2021 ; Accattoli and Guerrieri 2019 . Our development illustrates a principled and versatile approach to deriving abstract machines from well-understood high-level semantics. To reason about efficiency, we apply a variant of amortized cost analysis using a potential function Okasaki 1999 . The main contributions of this work are as follows: (1) A novel abstract machine for Strong CbNd, with a simple and clear design (only 11 transition rules), derived automatically with a semantic transformer of Buszka and Biernacki 2021 from an NbE normalizer. (2) A proof that the machine is reasonable for time, i.e., that the number of steps performed by the machine is bounded by a polynomial—in this case bilinear—function in the number of \beta -steps and in the size of the initial term. (3) A proof that the machine conservatively extends a weak call-by-need machine. (4) An improvement in simulation overhead for Strong CbNd over the existing machine for this strategy Biernacka and Charatonik 2019 , from exponential (unreasonable) to polynomial (reasonable). These machines are currently the only artefacts formalizing the strong call-by-need strategy, and amenable to complexity analysis. (5) An improvement of the overall simulation overhead of normal order by Useful MAM Accattoli 2016 from quadratic Accattoli et al. 2021 to quasibilinear in the RAM model. Motivation. The study of call-by-need calculi is generally motivated by the quest for efficient implementations of \beta -reduction in the \lambda -calculus. It is worth noting that our contribution here is primarily theoretical . We start from a well-understood, high-level specification (an NbE normalizer for normal order) and show how to derive—almost mechanically—a compact abstract machine whose correctness and complexity can be reasoned about with pen-and-paper proofs, or it can be implemented or formalized with reasonable effort. Furthermore, this approach can provide the basis to analyse other strategies along similar lines, allowing us to derive semantic artefacts that are correct by construction. The emphasis is on principles: a transparent derivation pipeline, a small rule set, and a clean complexity analysis; we prove the bilinear bound for machine steps, which guarantees that the normal form of a lambda term can be computed in time subquadratic in the number of normal-order reduction steps. A unit of time in our analysis is also abstract—it is a machine step, rather than, say, a millisecond as in realistic benchmarking. In this sense, our work sits closer to the semantic and proof-oriented lines of Balabonski et al. 2017 ; Balabonski et al. 2021 ; Biernacka and Charatonik 2019 ; Accattoli 2016 ; Accattoli et al. 2021 than to large, hand-engineered evaluators. Furthermore, because a compact, analysable CbNd machine yields a practical cost model for the \lambda -calculus, our work links naturally to the broader agenda of Implicit Computational Complexity and to recent efforts that treat the \lambda -calculus as a manageable computational model for complexity-theoretic formalizations Gäher and Kunze 2021 ; Forster et al. 2021 . Related work. Given their practical motivation, strong strategies have been the target of efficient implementation efforts in the form of abstract machines.