Lune

LICS2024Top-tier venue

Genericity Through Stratification

Victor Arrial, Giulio Guerrieri, Delia Kesner

Abstract

A fundamental issue in the λ-calculus is to find appropriate notions for meaningfulness. It is well-known that in the call-by-name λ-calculus (CbN) the meaningful terms can be identified with the solvable ones, and that this notion is not appropriate in the call-by-value λ-calculus (CbV). This paper validates the challenging claim that yet another notion, previously introduced in the literature as potential valuability (and later renamed scrutability), appropriately represents meaningfulness in CbV. Akin to CbN, this claim is corroborated by proving two essential properties. The first one is genericity, stating that meaningless subterms have no bearing on evaluating normalizing terms. To prove this (which was an open problem), we use a novel approach based on stratified reduction, indifferently applicable to CbN and CbV, and in a quantitative way. The second property concerns consistency of the smallest congruence relation resulting from equating all meaningless terms. While the consistency result is not new, we provide the first direct operational proof of it. We also show that such a congruence has a unique consistent and maximal extension, which coincides with a well-known notion of observational equivalence. Our results thus supply the formal concepts and tools that validate the informal notion of meaningfulness underlying CbN and CbV.

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. Strong Call-by-Value is Reasonable, ImplosivelyBeniamino Accattoli, Andrea Condoluci, Claudio Sacerdoti CoenLICS 2021 · 21 citations
  2. Taylor subsumes Scott, Berry, Kahn and PlotkinDavide Barbarossa, Giulio ManzonettoPOPL 2020 · 15 citations

Related papers

  1. Commuting Conversions and Join Points for Call-by-Push-ValueJonathan Chan, Madi Gudin, Annabel Levy, Stephanie WeirichOOPSLA 2026
  2. Abstract Operational Methods for Call-by-Push-ValueSergey Goncharov, Stelios Tsampas, Henning UrbatPOPL 2025 · 3 citations
  3. Adequacy for Algebraic Effects RevisitedG. A. KavvosOOPSLA 2025 · 6 citations
  4. Operational Algorithmic Game SemanticsBenedict Bunting, Andrzej S. MurawskiLICS 2023 · 1 citation
  5. A Cellular Howe TheoremPeio Borthelle, Tom Hirschowitz, Ambroise LafontLICS 2020 · 9 citations
Dusk over the sea between two cliffs drawn in fine vertical lines