Tail Modulo Cons, OCaml, and Relational Separation Logic
Clément Allain, Frédéric Bour, Basile Clément, François Pottier, Gabriel Scherer
Abstract
Common functional languages incentivize tail-recursive functions, as opposed to general recursive functions that consume stack space and may not scale to large inputs. This distinction occasionally requires writing functions in a tail-recursive style that may be more complex and slower than the natural, non-tail-recursive definition. This work describes our implementation of the tail modulo constructor (TMC) transformation in the OCaml compiler, an optimization that provides stack-efficiency for a larger class of functions — tail-recursive modulo constructors — which includes in particular the natural definition of List.map and many similar recursive data-constructing functions. We prove the correctness of this program transformation in a simplified setting — a small untyped calculus — that captures the salient aspects of the OCaml implementation. Our proof is mechanized in the Coq proof assistant, using the Iris base logic. An independent contribution of our work is an extension of the Simuliris approach to define simulation relations that support different calling conventions. To our knowledge, this is the first use of Simuliris to prove the correctness of a compiler transformation.
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.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Melocoton: A Program Logic for Verified Interoperability Between OCaml and C cites Transfinite Iris: resolving an existential dilemma of step-indexed separation logic
- Melocoton: A Program Logic for Verified Interoperability Between OCaml and C cites A separation logic for effect handlers
- KEM-IND-CCA-Preserving Compilation of Jasmin's ML-KEM cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Backwards-Compatible Row-Based Exceptions in ML cites A separation logic for effect handlers
- Backwards-Compatible Row-Based Exceptions in ML cites A Relational Separation Logic for Effect Handlers
- Backwards-Compatible Row-Based Exceptions in ML cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- A Relational Separation Logic for Effect Handlers cites A separation logic for effect handlers
- A Relational Separation Logic for Effect Handlers cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Simuliris: a separation logic framework for verifying concurrent program optimizations cites Transfinite Iris: resolving an existential dilemma of step-indexed separation logic
Cited by top-tier papers3
- A Relational Separation Logic for Effect HandlersPaulo Emílio de Vilhena, Simcha van Collem, Ines Wright, Robbert KrebbersPOPL 2026 · 3 citations
- KEM-IND-CCA-Preserving Compilation of Jasmin's ML-KEMSantiago Arranz-Olmos, Gilles Barthe, Lionel Blatter, Benjamin Gregoire et al.CCS 2026 · 1 citation
- Backwards-Compatible Row-Based Exceptions in MLSimcha van Collem, Paulo Emílio de Vilhena, Robbert KrebbersPLDI 2026
Builds on6
- Simuliris: a separation logic framework for verifying concurrent program optimizationsLennard Gäher, Michael Sammler, Simon Spies, Ralf Jung et al.POPL 2022 · 33 citations
- Transfinite Iris: resolving an existential dilemma of step-indexed separation logicSimon Spies, Lennard Gäher, Daniel Gratzer, Joseph Tassarotti et al.PLDI 2021 · 32 citations
- A separation logic for effect handlersPaulo Emílio de Vilhena, François PottierPOPL 2021 · 24 citations
- Melocoton: A Program Logic for Verified Interoperability Between OCaml and CArmaël Guéneau, Johannes Hostert, Simon Spies, Michael Sammler et al.OOPSLA 2023 · 10 citations
- Tail Recursion Modulo Context: An Equational ApproachDaan Leijen, Anton LorenzenPOPL 2023 · 9 citations
Related papers
- Actris: session-type based reasoning in separation logicJonas Kastberg Hinrichsen, Jesper Bengtson, Robbert KrebbersPOPL 2020 · 44 citations
- Pyrosome: Verified Compilation for Modular MetatheoryDustin Jamner, Gabriel Kammer, Ritam Nag, Adam ChlipalaOOPSLA 2025
- Retrofitting effect handlers onto OCamlK. C. Sivaramakrishnan, Stephen Dolan, Leo White, Tom Kelly et al.PLDI 2021 · 56 citations
- Compiling with continuations, correctlyZoe Paraskevopoulou, Anvay GroverOOPSLA 2021 · 10 citations
- Program Logics à la CarteMax Vistrup, Michael Sammler, Ralf JungPOPL 2025 · 4 citations
