Verifying programs in the calculus of inductive constructions

This paper deals with a particular approach to the verification of functional programs. A specification of a program can be represented by a logical formula Con86, NPS90]. In a constructive framework, developing a program then corresponds to proving this formula. Given a specification and a program, we focus on reconstructing a proof of the specification whose algorithmic contents corresponds to the given program. The best we can hope is to generate proof obligations on atomic parts of the program corresponding to logical properties to be verified. First, this paper studies a weak extraction of a program from a proof that keeps track of intermediate specifications. From such a program, we prove the determinism of retrieving proof obligations. Then, heuristic methods are proposed for retrieving the proof from a natural program containing only partial annotations. Finally, the implementation of this method as a tactic of theCoq proof assistant is presented.This research was partly supported by ESPRIT Basic Research Action Types for Proofs and Programs and by Programme de Recherche Coordonnes and CNRS Groupement de Recherche Programmation.