Lune

OOPSLA2022Top-tier venue

Purity of an ST monad: full abstraction by semantically typed back-translation

Koen Jacobs, Dominique Devriese, Amin Timany

Abstract

In 1995, Launchbury and Peyton Jones extended Haskell with an ST monad that allows the programmer to use higher-order mutable state. They informally argued that these state computations were safely encapsulated, and as such, that the rich reasoning principles stemming from the purity of the language, were not threatened.

In this paper, we give a formal account of the preservation of purity after adding an ST monad to a simplytyped call-by-value recursive lambda calculus. We state and prove full abstraction when embedding the pure language into its extension with ST; contextual equivalences from the pure language continue to hold in the presence of ST.

Proving full abstraction of compilers is usually done by emulating or back-translating the target features (here: ST computations) into the source language, a well-known challenge in the secure compilation community. We employ a novel proof technique for proving our full abstraction result that allows us to use a semantically (but not syntactically) typed back-translation into an intermediate language. We believe that this technique provides additional insight into our proof and that it is of general interest to researchers studying programming languages and compilers using full abstraction.

The results presented here are fully formalized in the Coq proof assistant using the Iris framework.

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.

6 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

  • Nola: Later-Free Ghost State for Verifying Termination in Iris cites Trillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional Refinement
  • Securing Verified IO Programs Against Unverified Code in F cites Iris-Wasm: Robust and Modular Verification of WebAssembly Programs
  • Trillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional Refinement cites Fully abstract from static to gradual
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. Iris-Wasm: Robust and Modular Verification of WebAssembly ProgramsXiaojia Rao, Aïna Linn Georges, Maxime Legoupil, Conrad Watt et al.PLDI 2023 · 19 citations
  2. Trillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional RefinementAmin Timany, Simon Oddershede Gregersen, Léo Stefanesco, Jonas Kastberg Hinrichsen et al.POPL 2024 · 14 citations
  3. Efficient Dual-Numbers Reverse AD via Well-Known Program TransformationsTom Smeding, Matthijs VákárPOPL 2023 · 10 citations
  4. Securing Verified IO Programs Against Unverified Code in FCezar-Constantin Andrici, Stefan Ciobaca, Catalin Hritcu, Guido Martínez et al.POPL 2024 · 5 citations
  5. Nola: Later-Free Ghost State for Verifying Termination in IrisYusuke Matsushita, Takeshi TsukadaPLDI 2025 · 2 citations

Builds on2

  1. On the semantic expressiveness of recursive typesMarco Patrignani, Eric Mark Martin, Dominique DevriesePOPL 2021 · 16 citations
  2. Fully abstract from static to gradualKoen Jacobs, Amin Timany, Dominique DevriesePOPL 2021 · 14 citations

Related papers

  1. Operational Algorithmic Game SemanticsBenedict Bunting, Andrzej S. MurawskiLICS 2023 · 1 citation
  2. Certifying derivation of state machines from coroutinesMirai Ikebuchi, Andres Erbsen, Adam ChlipalaPOPL 2022 · 2 citations
  3. Full Iso-Recursive TypesLitao Zhou, Qianyong Wan, Bruno C. d. S. OliveiraOOPSLA 2024 · 4 citations
  4. PureCake: A Verified Compiler for a Lazy Functional LanguageHrutvik Kanabar, Samuel Vivien, Oskar Abrahamsson, Magnus O. Myreen et al.PLDI 2023 · 7 citations
  5. Pure Borrow: Linear Haskell Meets Rust-Style BorrowingYusuke Matsushita, Hiromi IshiiPLDI 2026
Dusk over the sea between two cliffs drawn in fine vertical lines