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
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.
Cites 68 works (0 here)
External (68)
- Gradualizing the calculus of inductive constructions (2022)
- An Analysis of An Analysis of Girard’s Paradox (2021)
- Practical sized typing for coq (2020)
- Relating functional and imperative session types (2020)
- The fire triangle: how to mix substitution, dependent elimination, and effects (2019)
- Compiling with continuations, or without? whatever (2019)
- Handling delimited continuations with dependent types (2018)
- Parametric Closure Conversion for CIC (2018)
- Shifting and resetting in the calculus of constructions (2018)
- Syntax and Semantics of Cedille (2018)
- A Classical Sequent Calculus with Dependent Types (2017)
- FunTAL: reasonably mixing a functional language with assembly (2017)
- Compiling without continuations (2017)
- The next 700 syntactical models of type theory (2017)
- Type-preserving CPS translation of Σ and Π types is not not possible (2017)
- Fibred Computational Effects (2017)
- CertiCoq: A verified compiler for Coq (2017)
- A parametric CPS to sprinkle CIC with classical reasoning (2017)
- Consistency of the predicative calculus of cumulative inductive constructions (pCuIC) (2017)
- In Search of Effectful Dependent Types (2017)
- CertiKOS: An extensible architecture for building certified concurrent OS kernels (2016)
- Deep Specifications and Certified Abstraction Layers (2015)
- Verified Compilers for a Multi-language World (2015)
- Compositional CompCert (2015)
- Verification of a cryptographic primitive: SHA (2015)
- Verifying an Open Compiler Using Multi-language Semantics (2014)
- Certified Programming with Dependent Types - A Pragmatic Introduction to the Coq Proof Assistant (2013)
- A Constructive Proof of Dependent Choice, Compatible with Classical Logic (2012)
- A relaxation of Coq’s guard condition (2012)
- Call-By-Push-Value (2012)
- An equivalence-preserving CPS translation via multi-language semantics (2011)
- An Equivalence-Preserving CPS Translation via Multi-Language Semantics (Technical Appendix) (2011)
- Formal certification of code-based cryptographic proofs (2009)
- A formally verified compiler back-end (2009)
- On a few open problems of the calculus of inductive constructions and on their practical consequences (2009)
- Type-preserving compilation for large-scale optimizing object-oriented compilers (2008)
- Minimizing Code Defects to Improve Software Quality and Lower Development Costs (2008)
- Un environnement pour la programmation avec types dépendants (PhD thesis) (2008)
- A certified type-preserving compiler from lambda calculus to assembly language (2007)
- Compiling with continuations, continued (2007)
- A type system for certified binaries (2005)
- Extensionality in the Calculus of Constructions (2005)
- Small Proof Witnesses for LF (2005)
- On the Degeneracy of Sigma-Types in Presence of Computational Classical Logic (2005)
- Error Cost Escalation through the Project Life Cycle (2004)
- From control effects to typed continuation passing (2003)
- A concurrent logical framework: The propositional fragment (2003)
- CPS translating inductive and coinductive types (2002)
- A dependently typed assembly language (2001)
- Oracle-based checking of untrusted software (2001)
- From system F to typed assembly language (1999)
- Monads, effects and transformations (1999)
- Bisimilarity as a theory of functional programming (1999)
- CPS translations and applications: The cube and beyond (1999)
- Compiling standard ML to Java bytecodes (1998)
- Implementing typed intermediate languages (1998)
- Operationally-Based Theories of Program Equivalence (1997)
- Proof-carrying code (1997)
- A reflection on call-by-value (1997)
- An Overview of the FLINT/ML Compiler (1997)
- Compiling Haskell by Program Transformation: A Report from the Trenches (1996)
- TIL: a type-directed optimizing compiler for ML (1996)
- Pure Type Systems with Definitions (1994)
- The essence of compiling with continuations (1993)
- Reasoning about programs in continuation-Passing style (1992)
- An Extended Calculus of Constructions (1990)
- The calculus of constructions (1988)
- Formal Structures for Computation and Deduction (1986)