Coq en CoqReport as inadecuate




Coq en Coq - Download this document for free, or read online. Document in PDF available to download.

1 COQ - Formal Specifications and Program Validation Inria Paris-Rocquencourt

Abstract : The essential step of the formal verification of a proof-checker such as Coq is the verification of its kernel: a type-checker for the Calculus of Inductive Constructions CIC which is its underlying formalism. The present work is a first small-scale attempt on a significative fragment of CIC: the Calculus of Constructions CC. We formalize the definition and the metatheory of CC in Coq. In particular, we prove strong normalization and decidability of type inference. From the latter proof, we extract a certified Caml Light program, which performs type inference or type-checking for an arbitrary typing judgement in CC. Integrating this program in a larger system, including a parser and pretty-printer, we obtain a stand-alone proof-checker, called CoC, for the Calculus of Constructions. As an example, the formal proof of Newman-s lemma, build with Coq, can be re-verified by CoC with reasonable performance.

Keywords : PROGRAM EXTRACTION TYPE THEORY METATHEORY CALCULUS OF CONSTRUCTIONS





Author: Bruno Barras -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents