Lune

POPL2020Top-tier venue

The weak call-by-value λ-calculus is reasonable for both time and space

Yannick Forster, Fabian Kunze, Marc Roth

Abstract

We study the weak call-by-value λ\lambda-calculus as a model for computational complexity theory and establish the natural measures for time and space -- the number of beta-reductions and the size of the largest term in a computation -- as reasonable measures with respect to the invariance thesis of Slot and van Emde Boas [STOC 84]. More precisely, we show that, using those measures, Turing machines and the weak call-by-value λ\lambda-calculus can simulate each other within a polynomial overhead in time and a constant factor overhead in space for all computations that terminate in (encodings) of 'true' or 'false'. We consider this result as a solution to the long-standing open problem, explicitly posed by Accattoli [ENTCS 18], of whether the natural measures for time and space of the λ\lambda-calculus are reasonable, at least in case of weak call-by-value evaluation. Our proof relies on a hybrid of two simulation strategies of reductions in the weak call-by-value λ\lambda-calculus by Turing machines, both of which are insufficient if taken alone. The first strategy is the most naive one in the sense that a reduction sequence is simulated precisely as given by the reduction rules; in particular, all substitutions are executed immediately. This simulation runs within a constant overhead in space, but the overhead in time might be exponential. The second strategy is heap-based and relies on structure sharing, similar to existing compilers of eager functional languages. This strategy only has a polynomial overhead in time, but the space consumption might require an additional factor of log⁡n\log n, which is essentially due to the size of the pointers required for this strategy. Our main contribution is the construction and verification of a space-aware interleaving of the two strategies, which is shown to yield both a constant overhead in space and a polynomial overhead in time.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Reasonable Space for the λ-Calculus, Logarithmically cites The Space of Interaction
  • Reasonable Space for the λ-Calculus, Logarithmically cites Strong Call-by-Value is Reasonable, Implosively
  • A Machine-Independent, Log-Sensitive Space-Cost Measure for the Weak Lambda-Calculus cites Reasonable Space for the λ-Calculus, Logarithmically
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. Strong Call-by-Value is Reasonable, ImplosivelyBeniamino Accattoli, Andrea Condoluci, Claudio Sacerdoti CoenLICS 2021 · 21 citations
  2. Reasonable Space for the λ-Calculus, LogarithmicallyBeniamino Accattoli, Ugo Dal Lago, Gabriele VanoniLICS 2022 · 8 citations
  3. The Space of InteractionBeniamino Accattoli, Ugo Dal Lago, Gabriele VanoniLICS 2021 · 4 citations
  4. A Machine-Independent, Log-Sensitive Space-Cost Measure for the Weak Lambda-CalculusThibaut BalabonskiLICS 2026 · 1 citation
  5. A Case for First-Class EnvironmentsJinhao Tan, Bruno C. d. S. OliveiraOOPSLA 2024

Related papers

  1. A Compositional Cost Model for the λ-calculusJames LairdLICS 2021
  2. The (In)Efficiency of interactionBeniamino Accattoli, Ugo Dal Lago, Gabriele VanoniPOPL 2021 · 13 citations
  3. Genericity Through StratificationVictor Arrial, Giulio Guerrieri, Delia KesnerLICS 2024 · 1 citation
  4. Taylor subsumes Scott, Berry, Kahn and PlotkinDavide Barbarossa, Giulio ManzonettoPOPL 2020 · 15 citations
  5. Interaction EquivalenceBeniamino Accattoli, Adrienne Lancelot, Giulio Manzonetto, Gabriele VanoniPOPL 2025 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines