Reference. Verified Extraction from Coq to OCaml
One of the central claims of fame of the Coq proof assistant is extraction, i.e., the ability to obtain efficient programs in industrial programming languages such as OCaml, Haskell, or Scheme from programs written in Coq’s expressive dependent type theory. Extraction is of great practical usefulness, used crucially e.g., in the CompCert project. However, for such executables obtained by extraction, the extraction process is part of the trusted code base (TCB), as are Coq’s kernel and the compiler used to compile the extracted code. The extraction process contains intricate semantic transformation of programs that rely on subtle operational features of both the source and target language. Its code has also evolved since the last theoretical exposition in the seminal PhD thesis of Pierre Letouzey. Furthermore, while the exact correctness statements for the execution of extracted code are described clearly in academic literature, the interoperability with unverified code has never been investigated formally, and yet is used in virtually every project relying on extraction. In this paper, we describe the development of a novel extraction pipeline from Coq to OCaml, implemented and verified in Coq itself, with a clear correctness theorem and guarantees for safe interoperability. We build our work on the MetaCoq project, which aims at decreasing the TCB of Coq’s kernel by re-implementing it in Coq itself and proving it correct w.r.t. a formal specification of Coq’s type theory in Coq. Since OCaml does not have a formal specification, we make use of the Malfunction project specifying the semantics of the intermediate language of the OCaml compiler. Our work fills some gaps in the literature and highlights important differences between the operational semantics of Coq programs and their extraction. In particular, we focus on the guarantees that can be provided for interoperability with unverified code, and prove that extracted programs of first-order data type are correct and can safely interoperate, whereas for higher-order programs already simple interoperations can lead to incorrect behaviour and even outright segfaults.
Cite
Cites 38 works (2 here)
With notes (2)
CakeML: A verified implementation of ML kumar_cakeml_2014
We have developed and mechanically verified an ML system called CakeML, which supports a substantial subset of Standard ML. CakeML is implemented as an interactive read-eval-print loop (REPL) in x86-64 machine code. Our correctness theorem ensures that this REPL implementation prints only those results permitted by the semantics of CakeML. Our verification effort touches on a breadth of topics including lexing, parsing, type checking, incremental and dynamic compilation, garbage collection, arbitraryprecision arithmetic, and compiler bootstrapping.
Higher-order abstract syntax pfenning-1988-higher
External (36)
- Trocq: Proof Transfer for Free, With or Without Univalence (2024)
- Core_bench library (Jane Street) (2024)
- Efficient Extensional Binary Tries (2023)
- Verified Functional Algorithms (Software Foundations vol. 3) (2023)
- Candle: A Verified Implementation of HOL Light (2022)
- Relational compilation for performance-critical applications: extensible proof-producing translation of functional models into low-level code (2022)
- CertiCoq (GitHub repository) (2022)
- Aspects of a machine-checked intermediate language for extraction from Coq in MetaCoq (TYPES 2022) (2022)
- Extraction to OCaml from Coq: Operational Correctness Verified in Coq (ML Family Workshop) (2022)
- À bas l'η - Coq's troublesome η-conversion (WITS) (2022)
- Idris 2: Quantitative Type Theory in Practice (2021)
- The Lean 4 Theorem Prover and Programming Language (2021)
- Isabelle’s Metalogic: Formalization and Proof Checker (2021)
- Code Extraction from Coq to ML-like languages (ML Family Workshop) (2021)
- Proof-Producing Synthesis of CakeML from Monadic HOL Functions (2020)
- ConCert: a smart contract certification framework in Coq (2020)
- Verified Optimizations for Functional Languages (Paraskevopoulou, PhD thesis) (2020)
- Generating Verified LLVM from Isabelle/HOL (2019)
- Coq Coq correct! verification of type checking and erasure for Coq, in Coq (2019)
- The Type Soundness Theorem That You Really Want to Prove (and Now You Can) (2018)
- A Verified Compiler from Isabelle/HOL to CakeML (2018)
- Œuf: minimizing the Coq extraction TCB (2018)
- A formally verified compiler for Lustre (2017)
- Verified low-level programming embedded in F* (2017)
- CertiCoq: A verified compiler for Coq (CoqPL) (2017)
- Malfunctional programming (ML Family Workshop) (2016)
- A trusted mechanised JavaScript specification (2014)
- Proof-producing translation of higher-order logic into pure and stateful ML (2014)
- Proof-producing synthesis of ML from higher-order logic (2012)
- Verified heap theorem prover by paramodulation (2012)
- The development of Chez Scheme (2006)
- Formal certification of a compiler back-end or (2006)
- Programmation fonctionnelle certifiée: l'extraction de programmes dans l'assistant Coq (Letouzey, PhD thesis) (2004)
- Proofs about a folklore let-polymorphic type inference algorithm (1998)
- Register allocation via coloring (1981)
- A data structure for manipulating priority queues (1978)