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

Cite as @forster_etal_2024 (helia, typst) · \cite{forster_etal_2024} (LaTeX)
BibTeX
bibtex · 1 line
@article{forster_etal_2024, title={Verified Extraction from Coq to OCaml}, volume={8}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3656379}, DOI={10.1145/3656379}, number={PLDI}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Forster, Yannick and Sozeau, Matthieu and Tabareau, Nicolas}, year={2024}, month=jun, pages={52–75} }
hayagriva YAML (typst)
yaml · 19 lines
forster_etal_2024:
  type: article
  title: Verified Extraction from Coq to OCaml
  author:
  - Forster, Yannick
  - Sozeau, Matthieu
  - Tabareau, Nicolas
  date: 2024-06
  page-range: 52-75
  url: http://dx.doi.org/10.1145/3656379
  serial-number:
    doi: 10.1145/3656379
    issn: 2475-1421
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    publisher: Association for Computing Machinery (ACM)
    issue: PLDI
    volume: 8
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.
PDF · DOI · pldb

Higher-order abstract syntax pfenning-1988-higher

PDF · DOI · pldb
External (36)
forster_etal_2024 reference entries/refs/forster_etal_2024/forster_etal_2024.hel