Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Calculus of constructions
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{short description|Type theory created by Thierry Coquand}} In [[mathematical logic]] and [[computer science]], the '''calculus of constructions''' ('''CoC''') is a [[type theory]] created by [[Thierry Coquand]]. It can serve as both a [[type system|typed]] [[programming language]] and as [[Constructivism (mathematics)|constructive]] [[Foundations of mathematics|foundation for mathematics]]. For this second reason, the CoC and its variants have been the basis for [[Coq (software)|Coq]] and other [[proof assistant]]s. Some of its variants include the calculus of inductive constructions (which adds inductive types), the calculus of (co)inductive constructions (which adds coinduction), and the predicative calculus of inductive constructions (which removes some [[impredicativity]]){{Citation needed|date=February 2025}}. ==General traits== The CoC is a higher-order [[typed lambda calculus]], initially developed by [[Thierry Coquand]]. It is well known for being at the top of [[Henk Barendregt|Barendregt]]'s [[lambda cube]]. It is possible within CoC to define functions from terms to terms, as well as terms to types, types to types, and types to terms. The CoC is [[normalization property (lambda-calculus)|strongly normalizing]], and hence [[consistent]].<ref>{{cite journal |last1=Coquand |first1=Thierry |last2=Gallier |first2=Jean H. |title=A Proof of Strong Normalization for the Theory of Constructions Using a Kripke-Like Interpretation |journal=Technical Reports (Cis) |date=July 1990 |issue=568 |page=14 |url=https://repository.upenn.edu/cis_reports/568/}}</ref> == Usage == The CoC has been developed alongside the [[Coq (software)|Coq]] [[proof assistant]]. As features were added (or possible liabilities removed) to the theory, they became available in Coq. Variants of the CoC are used in other proof assistants, such as [[Matita]] and [[Lean (proof assistant)|Lean]]. ==The basics of the calculus of constructions== The calculus of constructions can be considered an extension of the [[Curry–Howard isomorphism]]. The Curry–Howard isomorphism associates a term in the [[Typed lambda calculus|simply typed lambda calculus]] with each [[natural deduction|natural-deduction]] proof in [[intuitionistic logic|intuitionistic propositional logic]]. The calculus of constructions extends this isomorphism to proofs in the full intuitionistic [[predicate calculus]], which includes proofs of quantified statements (which we will also call "propositions"). ===Terms=== A ''term'' in the calculus of constructions is constructed using the following rules: * <math>\mathbf{T}</math> is a term (also called ''type''); * <math>\mathbf{P}</math> is a term (also called ''prop'', the type of all propositions); * Variables (<math>x, y, \ldots</math>) are terms; * If <math>A</math> and <math>B</math> are terms, then so is <math>(A B)</math>; * If <math>A</math> and <math>B</math> are terms and <math>x</math> is a variable, then the following are also terms: ** <math>(\lambda x:A. B)</math>, ** <math>(\forall x:A. B)</math>. In other words, the term syntax, in [[Backus–Naur form]], is then: :<math>e ::= \mathbf{T} \mid \mathbf{P} \mid x \mid e \, e \mid \lambda x\mathbin{:}e.e\mid \forall x\mathbin{:}e.e</math> The calculus of constructions has five kinds of objects: # ''proofs'', which are terms whose types are ''propositions''; # ''propositions'', which are also known as ''small types''; # ''predicates'', which are functions that return propositions; # ''large types'', which are the types of predicates (<math>\mathbf{P}</math> is an example of a large type); # <math>\mathbf{T}</math> itself, which is the type of large types. === β-equivalence === As with the untyped lambda calculus, the calculus of constructions uses a basic notion of equivalence of terms, known as <math>\beta</math>-equivalence. This captures the meaning of <math>\lambda</math>-abstraction: * <math>(\lambda x:A . B) N =_\beta B(x := N)</math> <math>\beta</math>-equivalence is a congruence relation for the calculus of constructions, in the sense that * If <math>A =_\beta B</math> and <math>M =_\beta N</math>, then <math>A M =_\beta B N</math>. ===Judgments=== The calculus of constructions allows proving '''typing judgments''': :<math> x_1:A_1, x_2:A_2, \ldots \vdash t:B</math>, which can be read as the implication : If variables <math>x_1, x_2, \ldots</math> have, respectively, types <math>A_1, A_2, \ldots</math>, then term <math>t</math> has type <math>B</math>. The valid judgments for the calculus of constructions are derivable from a set of [[Rule of inference|inference rules]]. In the following, we use <math>\Gamma</math> to mean a sequence of type assignments <math> x_1:A_1, x_2:A_2, \ldots </math>; <math>A, B, C, D</math> to mean terms; and <math>K, L</math> to mean either <math>\mathbf{P}</math> or <math>\mathbf{T}</math>. We shall write <math>B[x:=N]</math> to mean the result of substituting the term <math>N</math> for the [[free variable]] <math>x</math> in the term <math>B</math>. An inference rule is written in the form :<math>\frac{\Gamma \vdash A:B}{\Gamma' \vdash C:D}</math>, which means : if <math> \Gamma \vdash A:B </math> is a valid judgment, then so is <math> \Gamma' \vdash C:D </math>. ===Inference rules for the calculus of constructions=== '''1'''. <math> {{} \over \Gamma \vdash \mathbf{P} : \mathbf{T}} </math> '''2'''. <math> {{\Gamma \vdash A : K} \over {\Gamma, x:A, \Gamma' \vdash x : A}} </math> '''3'''. <math> {\Gamma \vdash A : K \qquad\qquad \Gamma, x:A \vdash B : L \over {\Gamma \vdash (\forall x:A . B) : L}} </math> '''4'''. <math> {\Gamma \vdash A : K \qquad\qquad \Gamma, x:A \vdash N : B \over {\Gamma \vdash (\lambda x:A . N) : (\forall x:A . B)}} </math> '''5'''. <math> {\Gamma \vdash M : (\forall x:A . B) \qquad\qquad \Gamma \vdash N : A \over {\Gamma \vdash M N : B[x := N]}} </math> '''6'''. <math> {\Gamma \vdash M : A \qquad \qquad A =_\beta B \qquad \qquad \Gamma \vdash B : K \over {\Gamma \vdash M : B}} </math> ===Defining logical operators=== The calculus of constructions has very few basic operators: the only logical operator for forming propositions is <math>\forall</math>. However, this one operator is sufficient to define all the other logical operators: : <math> \begin{array}{ccll} A \Rightarrow B & \equiv & \forall x:A . B & (x \notin B) \\ A \wedge B & \equiv & \forall C:\mathbf{P} . (A \Rightarrow B \Rightarrow C) \Rightarrow C & \\ A \vee B & \equiv & \forall C:\mathbf{P} . (A \Rightarrow C) \Rightarrow (B \Rightarrow C) \Rightarrow C & \\ \neg A & \equiv & \forall C:\mathbf{P} . (A \Rightarrow C) & \\ \exists x:A.B & \equiv & \forall C:\mathbf{P} . (\forall x:A.(B \Rightarrow C)) \Rightarrow C & \end{array} </math> ===Defining data types=== The basic data types used in computer science can be defined within the calculus of constructions: ; Booleans : <math>\forall A: \mathbf{P} . A \Rightarrow A \Rightarrow A</math> ; Naturals : <math>\forall A: \mathbf{P} . (A \Rightarrow A) \Rightarrow A \Rightarrow A</math> ; Product <math>A \times B</math> : <math>A \wedge B</math> ; Disjoint union <math>A + B</math> : <math>A \vee B</math> Note that Booleans and Naturals are defined in the same way as in [[Church encoding]]. However, additional problems arise from propositional extensionality and proof irrelevance.<ref name=":0">{{Cite web|title=Standard Library {{!}} The Coq Proof Assistant|url=https://coq.inria.fr/stdlib/Coq.Logic.ClassicalFacts.html|access-date=2020-08-08|website=coq.inria.fr}}</ref> ==See also== * [[Pure type system]] * [[Lambda cube]] * [[System F]] * [[Dependent type]] * [[Intuitionistic type theory]] * [[Homotopy type theory]] == References == {{Reflist}} ==Sources== {{refbegin}} * {{cite journal | first1 = Thierry | last1 = Coquand | author-link1 = Thierry Coquand | first2 = Gérard | last2 = Huet | author-link2 = Gérard Huet | title = The Calculus of Constructions | journal = [[Information and Computation]] | volume = 76 | issue = 2–3 | date = 1988 | doi = 10.1016/0890-5401(88)90005-3 | pages = 95–120 | url = http://hal.archives-ouvertes.fr/docs/00/07/60/24/PDF/RR-0530.pdf | doi-access = free }} ** Also available freely accessible online: {{cite tech report | first1 = Thierry | last1 = Coquand | first2 = Gérard | last2 = Huet | url = http://hal.inria.fr/inria-00076024/en/ | title = The calculus of constructions | id = 530 | publisher = [[INRIA]], Centre de Rocquencourt | date = 1986 }} <br/> Note terminology is rather different. For instance, (<math>\forall x:A . B</math>) is written [''x'' : ''A''] ''B''. * {{cite web|url=https://citeseerx.ist.psu.edu/doc/10.1.1.88.9497 | first1 = M. W. | last1 = Bunder | first2 = Jonathan P. | last2 = Seldin | title = Variants of the Basic Calculus of Constructions | date = 2004 | citeseerx = 10.1.1.88.9497 }} * {{cite web | first = Maria João | last = Frade | date = 2009 | url = http://www3.di.uminho.pt/~mjf/pub/SFV-CIC-2up.pdf | title = Calculus of Inductive Constructions | format = talk | access-date = 2013-03-03 | archive-url = https://web.archive.org/web/20140529103535/http://www3.di.uminho.pt/~mjf/pub/SFV-CIC-2up.pdf | archive-date = 2014-05-29 | url-status = dead }} * {{cite book| first=Gérard |last=Huet| chapter=Induction Principles Formalized in the Calculus of Constructions |year=1988 |pages=205–216 |publisher=North-Holland |editor-first=K. |editor-last=Fuchi |editor2-first=M. |editor2-last=Nivat |editor-link2=Maurice Nivat|chapter-url=http://yquem.inria.fr/~huet/PUBLIC/induction.pdf |title=Programming of Future Generation Computers |isbn=0444704108|archive-url=https://web.archive.org/web/20150701130220/http://yquem.inria.fr/~huet/PUBLIC/induction.pdf|archive-date=2015-07-01}} — An application of the CoC {{refend}} [[Category:Dependently typed programming]] [[Category:Lambda calculus]] [[Category:Type theory]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation needed
(
edit
)
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Cite tech report
(
edit
)
Template:Cite web
(
edit
)
Template:Refbegin
(
edit
)
Template:Refend
(
edit
)
Template:Reflist
(
edit
)
Template:Short description
(
edit
)