Reference. ANF preserves dependent types up to extensional equality

Many programmers use dependently typed languages such as Coq to machine-verify high-assurance software. However, existing compilers for these languages provide no guarantees after compiling, nor when linking after compilation. Type-preserving compilers preserve guarantees encoded in types and then use type checking to verify compiled code and ensure safe linking with external code. Unfortunately, standard compiler passes do not preserve the dependent typing of commonly used (intensional) type theories. This is because assumptions valid in simpler type systems no longer hold, and intensional dependent type systems are highly sensitive to syntactic changes, including compilation. We develop an A-normal form (ANF) translation with join-point optimization—a standard translation for making control flow explicit in functional languages—from the Extended Calculus of Constructions (ECC) with dependent elimination of booleans and natural numbers (a representative subset of Coq). Our dependently typed target language has equality reflection, allowing the type system to encode semantic equality of terms. This is key to proving type preservation and correctness of separate compilation for this translation. This is the first ANF translation for dependent types. Unlike related translations, it supports the universe hierarchy, and does not rely on parametricity or impredicativity.

Cite

Cite as @koronkevich-2022-anf (helia, typst) · \cite{koronkevich-2022-anf} (LaTeX)
BibTeX
bibtex · 1 line
@article{koronkevich-2022-anf, title={ANF preserves dependent types up to extensional equality}, volume={32}, ISSN={1469-7653}, url={http://dx.doi.org/10.1017/s0956796822000090}, DOI={10.1017/s0956796822000090}, journal={Journal of Functional Programming}, publisher={Cambridge University Press (CUP)}, author={KORONKEVICH, PAULETTE and RAKOW, RAMON and AHMED, AMAL and BOWMAN, WILLIAM J.}, year={2022} }
hayagriva YAML (typst)
yaml · 18 lines
koronkevich-2022-anf:
  type: article
  title: ANF preserves dependent types up to extensional equality
  author:
  - KORONKEVICH, PAULETTE
  - RAKOW, RAMON
  - AHMED, AMAL
  - BOWMAN, WILLIAM J.
  date: 2022
  url: http://dx.doi.org/10.1017/s0956796822000090
  serial-number:
    doi: 10.1017/s0956796822000090
    issn: 1469-7653
  parent:
    type: periodical
    title: Journal of Functional Programming
    publisher: Cambridge University Press (CUP)
    volume: 32
Cited by (1)

Correctly Compiling Proofs About Programs Without Proving Compilers Correct seo-2024-correctly

Guaranteeing correct compilation is nearly synonymous with compiler verification. However, the correctness guarantees for certified compilers and translation validation can be stronger than we need. While many compilers do have incorrect behavior, even when a compiler bug occurs it may not change the program’s behavior meaningfully with respect to its specification. Many real-world specifications are necessarily partial in that they do not completely specify all of a program’s behavior. While compiler verification and formal methods have had great success for safety-critical systems, there are magnitudes more code, such as math libraries, compiled with incorrect compilers, that would benefit from a guarantee of its partial specification. This paper explores a technique to get guarantees about compiled programs even in the presence of an unverified, or even incorrect, compiler. Our workflow compiles programs, specifications, and proof objects, from an embedded source language and logic to an embedded target language and logic. We implement two simple imperative languages, each with its own Hoare-style program logic, and a system for instantiating proof compilers out of compilers between these two languages that fulfill certain equational conditions in Coq. We instantiate our system on four compilers: one that is incomplete, two that are incorrect, and one that is correct but unverified. We use these instances to compile Hoare proofs for several programs, and we are able to leverage compiled proofs to assist in proofs of larger programs. Our proof compiler system is formally proven sound in Coq. We demonstrate how our approach enables strong target program guarantees even in the presence of incorrect compilation, opening up new options for which proof burdens one might shoulder instead of, or in addition to, compiler correctness.
DOI
Cites 68 works (0 here)
External (68)
koronkevich-2022-anf reference entries/refs/koronkevich-2022-anf/koronkevich-2022-anf.hel