The
calculus of constructions (CoC) is a
formal language in which both
computer programs and mathematical
proofs can be expressed. This language forms the basis of theory behind the
Coq proof assistant.
The CoC is a higher-order typed lambda calculus, initially developed by Thierry Coquand, where types are first-class values. It is thus possible, within the CoC, to define functions from, say, integers to types, types to types as well as functions from integers to integers. Within Barendregt's lambda cube, it is therefore the richest calculus.
The CoC is strongly normalizing, though, by Gödel's incompleteness theorem, it is impossible to prove this property within the CoC since it implies consistency.
The CoC was the basis of the early versions of the Coq proof assistant; later versions were built upon the Calculus of inductive constructions, an extension of CoC with native support for inductive datatypes. In the original CoC, inductive datatypes had to be emulated as their polymorphic destructor function.
