Internal Program Extraction in the Calculus of Inductive Constructions

Abstract

Based on the Calculus of Constructions extended with inductive de nitions we present a Theory of Speci fications with rules for simultaneously constructing programs and their correctness proofs. The theory contains types for representing speci fications, whose corresponding notion of implementation is that of a pair formed by a program and a correctness proof. The rules of the theory are such that in implementations the program parts appear mixed together with the proof parts. A reduction relation performs the task of separating programs from proofs. Consequently, every implementation computes to a pair composed of a program and a proof of its correctness, and so the program extraction procedure is immediate.