Lune

POPL2025Top-tier venue

On Decidable and Undecidable Extensions of Simply Typed Lambda Calculus

Naoki Kobayashi

Abstract

The decidability of the reachability problem for finitary PCF has been used as a theoretical basis for fully automated verification tools for functional programs. The reachability problem, however, often becomes undecidable for a slight extension of finitary PCF with side effects, such as exceptions, algebraic effects, and references, which hindered the extension of the above verification tools for supporting functional programs with side effects. In this paper, we first give simple proofs of the undecidability of four extensions of finitary PCF, which would help us understand and analyze the source of undecidability. We then focus on an extension with references, and give a decidable fragment using a type system. To our knowledge, this is the first non-trivial decidable fragment that features higher-order recursive functions containing reference cells.

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.

1 top-tier paper has 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

  • On Higher-Order Model Checking of Effectful Answer-Type-Polymorphic Programs cites On Model-Checking Higher-Order Effectful Programs
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. On Higher-Order Model Checking of Effectful Answer-Type-Polymorphic ProgramsTaro Sekiyama, Ugo Dal Lago, Hiroshi UnnoOOPSLA 2025

Builds on2

  1. SyTeCi: automating contextual equivalence for higher-order programs with referencesGuilhem JaberPOPL 2020 · 16 citations
  2. On Model-Checking Higher-Order Effectful ProgramsUgo Dal Lago, Alexis GhyselenPOPL 2024 · 10 citations

Related papers

  1. Contextual Equivalence for State and Control via Nested DataBenedict Bunting, Andrzej S. MurawskiLICS 2024
  2. Modeling Reachability Types with Logical Relations: Semantic Type Soundness, Termination, Effect Safety, and Equational TheoryYuyan Bao, Songlin Jia, Guannan Wei, Oliver Bracevac et al.OOPSLA 2025 · 3 citations
  3. Higher-Order Model Checking of Effect-Handling Programs with Answer-Type ModificationTaro Sekiyama, Hiroshi UnnoOOPSLA 2024 · 4 citations
  4. Algebraic Temporal Effects: Temporal Verification of Recursively Typed Higher-Order ProgramsTaro Sekiyama, Hiroshi UnnoPOPL 2025 · 2 citations
  5. Complete the Cycle: Reachability Types with Expressive Cyclic ReferencesHaotian Deng, Siyuan He, Songlin Jia, Yuyan Bao et al.OOPSLA 2025 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines