PureCake: A Verified Compiler for a Lazy Functional Language
Hrutvik Kanabar, Samuel Vivien, Oskar Abrahamsson, Magnus O. Myreen, Michael Norrish, Johannes Åman Pohjola, Riccardo Zanetti
Abstract
We present PureCake, a mechanically-verified compiler for PureLang, a lazy, purely functional programming language with monadic effects. PureLang syntax is Haskell-like and indentation-sensitive, and its constraint-based Hindley-Milner type system guarantees safe execution. We derive sound equational reasoning principles over its operational semantics, dramatically simplifying some proofs. We prove end-to-end correctness for the compilation of PureLang down to machine code---the first such result for any lazy language---by targeting CakeML and composing with its verified compiler. Multiple optimisation passes are necessary to handle realistic lazy idioms effectively. We develop PureCake entirely within the HOL4 interactive theorem prover.
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
- OwlC: Compiling Security Protocols to Verified, Secure, High-Performance Libraries cites Interaction trees: representing recursive and impure programs in Coq
- Functional Stream Semantics for a Synchronous Block-Diagram Compiler cites Interaction trees: representing recursive and impure programs in Coq
- Cakes That Bake Cakes: Dynamic Computation in CakeML cites Interaction trees: representing recursive and impure programs in Coq
Cited by top-tier papers3
- Type Inference LogicsDenis Carnier, François Pottier, Steven KeuchelOOPSLA 2024 · 3 citations
- OwlC: Compiling Security Protocols to Verified, Secure, High-Performance LibrariesPratap Singh, Joshua Gancher, Bryan ParnoUSENIX Security 2025
- Functional Stream Semantics for a Synchronous Block-Diagram CompilerTimothy Bourke, Paul Jeanmaire, Marc PouzetLICS 2025
Builds on2
Related papers
- Do you have space for dessert? a verified space cost semantics for CakeML programsAlejandro Gómez-Londoño, Johannes Åman Pohjola, Hira Taqdees Syeda, Magnus O. Myreen et al.OOPSLA 2020 · 12 citations
- Grisette: Symbolic Compilation as a Functional Programming LibrarySirui Lu, Rastislav BodíkPOPL 2023 · 10 citations
- Verified Density Compilation for a Probabilistic Programming LanguageJoseph Tassarotti, Jean-Baptiste TristanPLDI 2023 · 6 citations
- How statically-typed functional programmers write codeJustin Lubin, Sarah E. ChasinsOOPSLA 2021 · 17 citations
- Pyrosome: Verified Compilation for Modular MetatheoryDustin Jamner, Gabriel Kammer, Ritam Nag, Adam ChlipalaOOPSLA 2025
