Lune

PLDI2023Top-tier venue

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.

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

  • 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
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. Type Inference LogicsDenis Carnier, François Pottier, Steven KeuchelOOPSLA 2024 · 3 citations
  2. OwlC: Compiling Security Protocols to Verified, Secure, High-Performance LibrariesPratap Singh, Joshua Gancher, Bryan ParnoUSENIX Security 2025
  3. Functional Stream Semantics for a Synchronous Block-Diagram CompilerTimothy Bourke, Paul Jeanmaire, Marc PouzetLICS 2025

Builds on2

  1. Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
  2. Cakes That Bake Cakes: Dynamic Computation in CakeMLThomas Sewell, Magnus O. Myreen, Yong Kiam Tan, Ramana Kumar et al.PLDI 2023 · 16 citations

Related papers

  1. 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
  2. Grisette: Symbolic Compilation as a Functional Programming LibrarySirui Lu, Rastislav BodíkPOPL 2023 · 10 citations
  3. Verified Density Compilation for a Probabilistic Programming LanguageJoseph Tassarotti, Jean-Baptiste TristanPLDI 2023 · 6 citations
  4. How statically-typed functional programmers write codeJustin Lubin, Sarah E. ChasinsOOPSLA 2021 · 17 citations
  5. Pyrosome: Verified Compilation for Modular MetatheoryDustin Jamner, Gabriel Kammer, Ritam Nag, Adam ChlipalaOOPSLA 2025
Dusk over the sea between two cliffs drawn in fine vertical lines