Curry-Howard correspondence
254299
223910750
2008-07-06T13:42:46Z
Classicalecon
4831766
-dup
[[Image:Coq plus comm screenshot.jpg|thumb|An example of proof written as a functional program: the proof of commutativity of addition on natural numbers in the proof assistant [[Coq]]]]
The '''Curry-Howard correspondence''' is the direct relationship between computer programs and mathematical proofs. Also known as '''Curry-Howard isomorphism''', '''proofs-as-programs correspondence''' and '''formulae-as-types correspondence''', it refers to the generalization of a syntactic [[analogy]] between systems of formal logic and computational calculi that was first discovered by the American [[mathematician]] [[Haskell Curry]] and [[logician]] [[William Alvin Howard]].
== Origin, scope and consequences of the correspondence ==
At the very beginning, the '''Curry–Howard correspondence''' is
# the observation in 1934 by [[Haskell Curry|Curry]] that the [[typed lambda calculus|type]]s of the [[combinatory logic|combinator]]s could be seen as axiom-schemes for [[intuitionism|intuitionistic]] implicational logic,
# the observation in 1958 by [[Haskell Curry|Curry]] that a certain kind of [[proof calculus|proof system]], referred to as [[Hilbert-style deduction system]]s, coincides on some fragment to the typed fragment of a standard [[model of computation]] known as [[combinatory logic]],
# the observation in 1969 by [[William Alvin Howard|Howard]] that another, more "high level" [[proof calculus|proof system]], referred to as [[natural deduction]], can be directly interpreted in its [[intuitionistic]] version as a typed variant of the [[model of computation]] known as [[lambda calculus]].
In other words, the Curry-Howard correspondence is the simple observation that two at-the-time-seemingly-unrelated families of formalisms, the proof systems on one side and the models of computation on the other side, were, on the two examples considered by Curry and Howard, in fact structurally the same kind of objects.
If one now abstracts on the peculiarities of this or that formalism, the immediate generalization is the following claim: ''a proof is a program, the formula it proves is a type for the program''. Most informally, this can be seen as an [[analogy]] which states that the [[return type]] of a function (i.e., the type of values returned by a function) is analogous to a logical theorem, subject to hypotheses corresponding to the types of the argument values passed to the function; and that the program to compute that function is analogous to a proof of that theorem. This sets a form of [[logic programming]] on a rigorous foundation: ''proofs can be represented as programs, and especially as lambda terms'', or ''proofs can be <u>run</u>''.
The correspondence has been the starting point of a large spectrum of new research after its discovery, leading in particular to a new class of [[formal system]]s designed to act both as a [[proof calculus|proof system]] and as a typed [[functional programming language]]. This includes [[Martin-Löf]]'s [[intuitionistic type theory]] and Coquand's [[Calculus of Constructions]], two calculi in which proofs are regular objects of the discourse and in which one can state properties of proofs the same way as of any program. This field of research is usually referred to as modern [[type theory]].
Such [[typed lambda calculus|typed lambda calculi]] derived from the Curry-Howard paradigm led to [[software]], like [[Coq]], in which proofs seen as programs can be formalized, checked, and run.
A converse direction is to ''use a program to extract a proof'', given its [[correctness]]. This is only feasible if the [[programming language]] the program is written for is very richly typed: the development of such type systems has been partly motivated by the wish to make the Curry-Howard correspondence practically relevant.
The Curry-Howard correspondence also raised new questions regarding the computational content of proof concepts which were not covered by the original works of Curry and Howard. In particular, [[classical logic]] has been shown to correspond to the ability to manipulating the [[continuation]] of programs and the symmetry of [[sequent calculus]] to express the duality between the two [[evaluation strategy|evaluation strategies]] known as call-by-name and call-by-value.
Speculatively, the Curry-Howard correspondence may be expected to lead to a substantial [[unifying theories in mathematics|unification]] between mathematical logic and foundational computer science:
Hilbert-style logic and natural deduction are but two kinds of proof systems among a large family of formalisms. Alternative syntaxes include [[sequent calculus]], [[proof net]]s, [[calculus of structures]], etc. If one admits the Curry-Howard correspondence as the general principle that any proof system hides a model of computation, a theory of the untyped underlying computational structure of these kinds of proof system should be possible. Then, a natural question is whether something mathematically interesting can be said about these underlying computational calculi.
Conversely, combinatory logic and simply-typed lambda calculus are not the only [[models of computation]], either. Girard's [[linear logic]] was developed from the fine analysis of the use of resources in some models of lambda calculus; can we imagine a typed version of [[Turing machine]] that would behave as a proof system? [[Typed assembly language]]s are such an instance of "low-level" model of computation that carries [[types]].
==General formulation of the Curry-Howard correspondence==
In its more general formulation, the Curry-Howard correspondence is a correspondence between formal [[proof calculus|proof calculi]] and [[type systems]] for [[model of computation|models of computation]]. In particular, it splits into two correspondences. One at the level of [[formulas]] and [[data type|types]] that is independent of which particular proof system or model of computation is considered, and one at the level of [[mathematical proof|proofs]] and [[computer program|programs]] which, this time, is specific to the particular choice of proof system and model of computation considered.
At the level of formulas and types, the correspondence says that implication behaves the same as a function type, conjunction as a product type, disjunction as a sum type, the false formula as the empty type and the true formula as the singleton type. If quantification comes in two flavors, it is because there are two ways to think about the Curry-Howard correspondence. If one considers that every single proof step has to be computational, then [[universal quantification]] is interpreted as dependent product and [[existential quantification]] as a dependent sum (this corresponds to interpreting a proof as a term typed [[simply typed lambda calculus|à la Church]]). If otherwise one considers that some trivial computational step can be omitted, then universal quantification is interpreted as an [[Type_system#Intersection_types | intersection type]] and existential quantification as a [[Type_system#Union_types | union type]] (this corresponds to interpreting a proof as a term typed [[simply typed lambda calculus|à la Curry]], which was actually the approach taken by Howard). This is summarized in the following table:
<br>
{| border=1 style="text-align:center" cellpadding="5" cellspacing="0" align=center
! style="width:200px" rowspan=2 | Logic side
! style="width:200px" colspan=2 | Programming side
|-
! Curry-style typing || Church-style typing
|-
| [[universal quantification]] || [[Type_system#Intersection_types | intersection type]] || [[Dependent type | dependent]] product type
|-
| [[existential quantification]] || [[Type_system#Union_types | union type]] || [[Dependent type | dependent]] sum type
|-
| [[Logical implication|implication]] ||colspan=2| [[Type signature | function type]]
|-
| [[logical conjunction|conjunction]] ||colspan=2| [[product type]]
|-
| [[logical disjunction|disjunction]] ||colspan=2| [[tagged union|sum type]]
|-
| true formula ||colspan=2| [[unit type]]
|-
| false formula ||colspan=2| [[Bottom type | void type]]
|-
|}
<br>
At the level of proof systems and models of computations, the correspondence mainly shows the identity of structure, first, between some particular formulations of systems known as [[Hilbert-style deduction system]] and [[combinatory logic]], and, secondly, between some particular formulations of systems known as [[natural deduction]] and [[lambda calculus]].
<br>
{| border=1 style="text-align:center" cellpadding="5" cellspacing="0" align=center
! style="width:200px" | Logic side
! style="width:200px" | Programming side
|-
| [[Hilbert-style deduction system]] || <table align=center><tr><td>type system for</td></tr><tr><td>[[combinatory logic]]</td></tr></table>
|-
| [[natural deduction]] || <table align=center><tr><td>type system for</td></tr><tr><td>[[lambda calculus]]</td></tr></table>
|}
<br>
==Correspondence between Hilbert-style deduction systems and combinatory logic==
It was at the beginning a simple remark in Curry and Feys's 1958 book on combinatory logic: the simplest types for the basic combinators of [[combinatory logic]] surprisingly corresponded to the axioms used in [[Hilbert-style deduction system]]s.
If one restricts to the implicational intuitionistic fragment, a simple way to formalize logic in Hilbert's style is as follows. Let Γ be a finite sequence of formulas, considered as hypotheses. We say that δ is derivable from Γ, and we write Γ {{Unicode|⊢}} δ, in the following cases:
* δ is an hypothesis, i.e. it is a formula of Γ,
* δ is an instance of an axiom scheme, i.e.,
** δ has the form α → (β → α), or
** δ has the form (α → (β → γ)) → ((α → β) → (α → γ)),
* δ follows by deduction, i.e., for some α, both α → δ and α are already derivable from Γ (this is the rule of [[modus ponens]])
This can be formalized using [[inference rules]], what we do in the left column of the following table. We also give in the right-column the type system for combinatory logic based on K and S. Curry's remark simply states that both columns are in one-to-one correspondence. The restriction of the correspondence to [[intuitionistic logic]] means that purely implicational [[tautologies]] like the non intuitionistically provable ((α → β) → α) → α ([[Peirce's law]]) are excluded of the correspondence.
<br>
{| border=1 style="text-align:center" cellpadding="10" cellspacing="0" align=center
! width="200px"| Hilbert-style intuitionistic implicational logic
! width="200px"| Simply-typed combinatory logic
|- style="height:70px" valign=bottom
| <math>\frac{}{\Gamma_1, \alpha, \Gamma_2 \vdash \alpha} Assum</math>
| <math>\frac{}{\Gamma_1, x:\alpha, \Gamma_2 \vdash x:\alpha}</math>
|- style="height:70px" valign=bottom
| <math>\frac{}{\Gamma \vdash \alpha \rightarrow (\beta \rightarrow \alpha)} Ax_ 1</math>
| <math>\frac{}{\Gamma \vdash K: \alpha \rightarrow (\beta \rightarrow \alpha)}</math>
|- style="height:70px" valign=bottom
| <math>\frac{}{\Gamma \vdash (\alpha\!\rightarrow\!(\beta\!\rightarrow\!\gamma))\!\rightarrow\!((\alpha\!\rightarrow\!\beta)\!\rightarrow\!(\alpha\!\rightarrow\!\gamma))}Ax_2</math>
| <math>\frac{}{\Gamma \vdash S: (\alpha\!\rightarrow\!(\beta\!\rightarrow\!\gamma))\!\rightarrow\!((\alpha\!\rightarrow\!\beta)\!\rightarrow\!(\alpha\!\rightarrow\!\gamma))}</math>
|- style="height:70px" valign=bottom
| <math>\frac{\Gamma \vdash \alpha \rightarrow \beta \qquad \Gamma \vdash \alpha}{\Gamma \vdash \beta}\textit{Modus~Ponens}</math>
| <math>\frac{\Gamma \vdash E_1:\alpha \rightarrow \beta \qquad \Gamma \vdash E_2:\alpha}{\Gamma \vdash E_1\;E_2:\beta} </math>
|}
<br>
Seen at a more abstract level, the correspondence can be restated as shown in the following table. Especially, the [[deduction theorem]] specific to Hilbert-style logic matches the process of [[Combinatory logic#Conversion of a lambda term to an equivalent combinatorial term|abstraction elimination]] of combinatory logic.
<br>
{| border=1 style="text-align:center" cellpadding="5" cellspacing="0" align=center
! style="width:200px" | Logic side
! style="width:200px" | Programming side
|-
| assumption || variable
|-
| axioms || combinators
|-
| modus ponens || application
|-
| [[deduction theorem]] || [[Combinatory logic#Conversion of a lambda term to an equivalent combinatorial term|abstraction elimination]]
|}
<br>
Thanks to the correspondence, results from combinatory logic can be transferred to Hilbert-style logic and vice-versa. For instance, the notion of [[combinatory logic#reduction in combinatory logic|reduction]] of terms in combinatory logic can be transferred to Hilbert-style logic and it provides a way to canonically transform proofs into other proofs of the same statement. One can also transfer the notion of normal terms to a notion of normal proofs, expressing that the hypotheses of the axioms never need to be all detached (since otherwise a simplification can happen).
Conversely, the non provability in intuitionistic logic of [[Peirce's law]] can be transferred back to combinatory logic: there is no typed term of combinatory logic that is typable with type ((α → β) → α) → α.
Results on the completeness of some sets of combinators or axioms can also be transferred. For instance, the fact that the combinator '''X''' constitutes a [[Combinatory logic#one-point basis|one-point basis]] of (extensional) combinatory logic implies that the single axiom scheme
:((α → (β → γ)) → ((α → β) → (α → γ)) → ((δ → (ε → δ)) → ζ)) → ζ,
which is the [[principal type]] of '''X''', is an adequate replacement to the combination of the axiom schemes
:α → (β → α) and
:(α → (β → γ)) → ((α → β) → (α → γ)).
Due to the correspondence, the axiom schemes α → (β → α) and (α → (β → γ)) → ((α → β) → (α → γ)) are now often called axioms K and S respectively. Examples of programs seen as proofs in a Hilbert-style logic are given [[#Examples|below]].
==Correspondence between natural deduction and lambda calculus==
After [[Haskell Curry|Curry]] emphasized the syntactic correspondence between [[Hilbert-style deduction system|Hilbert-style deduction]] and [[combinatory logic]], [[William Alvin Howard|Howard]] made explicit in 1969 a syntactic analogy between the programs of [[simply typed lambda calculus|simply-typed lambda calculus]] and the proofs of [[natural deduction]]. Below, the left-hand side formalizes intuitionistic implicational natural deduction as a calculus of sequents with implicit weakening and the right-hand side shows the typing rules of [[lambda calculus]]. In the left-hand side, Γ, Γ₁ and Γ₂ denote ordered sequences of formulas while in the right-hand side, they denote sequences of named formulas with all names different.
<br>
{| border=1 style="text-align:center" cellpadding="10" cellspacing="0" align=center
! width="200px"| Intuitionistic implicational natural deduction
! width="200px"| Lambda calculus type assignment rules
|- style="height:70px" valign=bottom
| <math>\frac{}{\Gamma_1, \alpha, \Gamma_2 \vdash \alpha} Ax</math>
| <math>\frac{}{\Gamma_1, x:\alpha, \Gamma_2 \vdash x:\alpha}</math>
|- style="height:70px" valign=bottom
| <math>\frac{\Gamma, \alpha \vdash \beta}{\Gamma \vdash \alpha \rightarrow \beta} \rightarrow I</math>
| <math>\frac{\Gamma, x:\alpha \vdash t:\beta}{\Gamma \vdash \lambda x.t : \alpha \rightarrow \beta}</math>
|- style="height:70px" valign=bottom
| <math>\frac{\Gamma \vdash \alpha \rightarrow \beta \qquad \Gamma \vdash \alpha}{\Gamma \vdash \beta} \rightarrow E</math>
| <math>\frac{\Gamma \vdash t:\alpha \rightarrow \beta \qquad \Gamma \vdash u:\alpha}{\Gamma \vdash t\;u:\beta} </math>
|}
<br>
To paraphrase the correspondence, proving Γ {{Unicode|⊢}} α means having a program that, given values with the types listed in Γ, manufactures an object of type α. An axiom corresponds to the introduction of a new variable with a new, unconstrained type, the → I rule corresponds to function abstraction and the → E rule corresponds to function application. Observe that the correspondence is not exact if the context Γ is taken to be a set of formulas as, e.g., the λ-terms λx.λy.x and λx.λy.y of type α → α → α would not be distinguished in the correspondence. Examples are given [[#Examples|below]].
Howard showed that the correspondence extends to other connectives of the logic and other constructions of simply-typed lambda calculus. Seen at an abstract level, the correspondence can then be summarized as shown in the following table. Especially, it also shows that the notion of normal forms in [[lambda calculus]] matches [[Dag Prawitz|Prawitz]]'s notion of normal deduction in [[natural deduction]], from what we deduce, among others, that the algorithms for the [[type inhabitation problem]] can be turned into algorithms for deciding [[intuitionistic]] provability.
<br>
{| border=1 style="text-align:center" cellpadding="5" cellspacing="0" align=center
! style="width:200px" | Logic side
! style="width:200px" | Programming side
|-
| axiom || variable
|-
| introduction rule || constructor
|-
| elimination rule || destructor
|-
| normal deduction || normal form
|-
| normalisation of deductions || [[Normalization property (lambda-calculus)|weak normalisation]]
|-
| provability || [[type inhabitation problem]]
|-
| intuitionistic [[tautology]] || inhabited type
|}
<br>
Howard's correspondence naturally extends to other extensions of [[natural deduction]] and [[simply typed lambda calculus|simply-typed lambda calculus]]. Here is a non exhaustive list:
* Girard-Reynolds [[System F]] as a common language for both second-order propositional logic and polymorphic lambda calculus,
* [[higher-order logic]] and Girard's [[System F|System F<sub>ω</sub>]]
* inductive types as [[algebraic data type]]
* ...
==Correspondence between classical logic and control operators==
At the time of Curry, and so was at the time of Howard, the proof-as-program correspondence was only concerning [[intuitionistic logic]], i.e. a logic in which, in particular, [[Peirce's law]] was ''not'' deducible. The extension of the correspondence to Peirce's law and hence to [[classical logic]] became clear from the work of Griffin on typing operators that capture the evaluation context of a given program execution so that this evaluation context can be later on reinstalled. The basic Curry-Howard-style correspondence for classical logic is given below. Note the correspondence between the double-negation translation used to map classical proofs to intuitionistic logic and the [[continuation-passing style|continuation-passing-style]] translation used to map lambda terms involving control to pure lambda terms. More particularly, call-by-name continuation-passing-style translations relates to [[Kolmogorov]]'s double negation translation and call-by-value continuation-passing-style translations relates to a kind of double-negation translation due to Kuroda.
<br>
{| border=1 style="text-align:center" cellpadding="5" cellspacing="0" align=center
! width="200px"| Logic side
! width="200px"| Programming side
|-
| [[Peirce's law]]: ((α → β) → α) → α || [[call-with-current-continuation]]
|-
| double-negation translation || [[continuation-passing style|continuation-passing-style translation]]
|}
<br>
A finer Curry-Howard correspondence exists for classical logic if one defines classical logic not by adding an axiom such as [[Pierce's law]], but by allowing several conclusions in sequents. In the case of classical natural deduction, there exists a proofs-as-programs correspondence with the typed programs of Parigot's [[lambda-mu calculus|λμ-calculus]].
==Sequent calculus==
A proofs-as-programs correspondence can be settled for the formalism known as [[Gentzen]]'s [[sequent calculus]] but it is not a correspondence with a well-defined pre-existing model of computation as it was for Hilbert-style and natural deductions.
Sequent calculus is characterized by the presence of left introduction rules, right introduction rule and a cut rule that can be eliminated. The structure of sequent calculus relates to a calculus whose structure is close to the one of some [[abstract machine]]s. The informal correspondence is as follows:
<br>
{| border=1 style="text-align:center" cellpadding="5" cellspacing="0" align=center
! style="width:200px" | Logic side
! style="width:200px" | Programming side
|-
| cut elimination || reduction in a form of abstract machine
|-
| right introduction rules || constructors of code
|-
| left introduction rules || constructors of evaluation stacks
|-
| priority to right-hand side in cut-elimination
| call-by-name evaluation
|-
| priority to left-hand side in cut-elimination
| call-by-value reduction
|}
<br>
==Related proofs-as-programs correspondences==
===The rôle of de Bruijn===
[[Nicolaas Govert de Bruijn|N. G. de Bruijn]] used the lambda notation for representing proofs of the theorem checker [[Automath]]. It was in the late 1960s at the same period of time Howard wrote his manuscript. Some researchers tend to use the term Curry-Howard-de Bruijn correspondence in place of Curry-Howard correspondence.
===BHK interpretation===
The [[BHK interpretation]] interprets intuitionistic proofs as functions but it does not specify the class of functions relevant for the interpretation. If one takes lambda calculus for this class of function, then the [[BHK interpretation]] tells the same as Howard's correspondence between natural deduction and lambda calculus.
===Realizability===
[[Stephen Cole Kleene|Kleene]]'s recursive [[realizability]] splits proofs of intuitionistic arithmetic into the pair of a recursive function and of
a proof of a formula expressing that the recursive function "realizes", i.e. correctly instantiates the disjunctions and existential quantifiers of the initial formula so that the formula gets true.
[[Georg Kreisel|Kreisel]]'s modified realizability applies to intuitionistic higher-order predicate logic and shows that the [[simply typed lambda calculus|simply-typed lambda term]] inductively extracted from the proof realizes the initial formula. In the case of propositional logic, it coincides with Howard's statement: the extracted lambda term is the proof itself (seen as an untyped lambda term) and the realizability statement is a paraphrase of the fact that the extracted lambda term has the type that the formula means (seen as a type).
[[Kurt Gödel|Gödel]]'s [[dialectica interpretation]] realizes classical arithmetic with functions. The connection with
lambda calculus is unclear, even in the case of natural deduction.
===Curry-Howard-Lambek correspondence===
[[Joachim Lambek]] showed in the early 1970s that the proofs of intuitionistic propositional logic and the combinators of typed [[combinatory logic]] share a common equational theory which is the one of [[cartesian closed categories]]. The expression Curry-Howard-Lambek correspondence is now used by some people to refer to the three way isomorphism between intuitionistic logic, typed lambda calculus and cartesian closed categories, with objects being interpreted as types or propositions and morphisms as terms or proofs. The correspondence works at the equational level and is not the expression of a syntactic identity of structures as it is the case for each of Curry's and Howard's correspondences: i.e. the structure of a well-defined morphism in a cartesian-closed category is not comparable to the structure of a proof of the corresponding judgement in either Hilbert-style logic or natural deduction. To clarify this distinction, the underlying syntactic structure of cartesian closed categories is rephrased below.
Objects (types) are defined by
* <math>\top</math> is an object
* if <math>\alpha</math> and <math>\beta</math> are objects then <math>\alpha \times \beta</math> and <math>\alpha \rightarrow \beta</math> are objects
Morphisms (terms) are defined by
* <math>id</math>, <math>\star</math>, <math>eval</math>, <math>\pi_1</math> and <math>\pi_2</math> are morphisms
* if <math>t</math> is a morphism, <math>\lambda t</math> is a morphism
* if <math>t</math> and <math>u</math> are morphisms, <math>(t, u)</math> and <math>u \circ t</math> are morphisms
Well-defined morphisms (typed terms) are defined by the following (typing) rules (in which the usual categorical morphism notation <math>f : \alpha \to \beta</math> is replaced with sequent calculus notation <math>f :\!\!-~~ \alpha ~\vdash~ \beta</math>):
<br>
{| border=0 style="text-align:center" cellpadding="10" cellspacing="0" align=center
| <math>\frac{}{id:\!\!-~~ \alpha ~\vdash~ \alpha}</math>
| <math>\frac{t:\!\!-~~ \alpha ~\vdash~ \beta\qquad u:\!\!-~~ \beta ~\vdash~ \gamma}{u \circ t:\!\!- ~\alpha ~\vdash~ \gamma}</math>
|-
|
| <math>\frac{}{\star:\!\!-~~\alpha ~\vdash~ \top}</math>
|-
| <math>\frac{t:\!\!-~~\alpha ~\vdash~ \beta\qquad u:\!\!-~~\alpha ~\vdash~ \gamma}{(t,u):\!\!-~~ \alpha ~\vdash~ \beta \times \gamma}</math>
| <math>\frac{}{\pi_1:\!\!-~~ \alpha \times \beta ~\vdash~ \alpha}\qquad\frac{}{\pi_2:\!\!-~~ \alpha \times \beta ~\vdash~ \beta}</math>
|-
| <math>\frac{t:\!\!-~~ \alpha \times \beta ~\vdash~ \gamma}{\lambda t:\!\!-~~ \alpha ~\vdash~ \beta \rightarrow \gamma}</math>
| <math>\frac{}{eval:\!\!-~~ (\alpha \rightarrow \beta) \times \alpha ~\vdash~ \beta}</math>
|}
<br>
Finally, the equations of the category are
* <math>id \circ t = t</math>, <math>t \circ id = t</math>, <math>(v \circ u) \circ t = v \circ (u \circ t)</math>
* <math>\star \circ t = \star</math>
* <math>\pi_1 \circ (t, u) = t, \pi_2 \circ (t,u) = u, (\pi_1 \circ t, \pi_2 \circ t) = t</math>
* <math>eval \circ (\lambda t, id) = t, \lambda eval = id</math>
Now, there exists <math>t</math> such that <math>t :- \alpha_1 \times \ldots \times \alpha_n \vdash \beta</math> iff <math>\alpha_1, \ldots, \alpha_n \vdash \beta </math> is provable in implicational intuitionistic logic,.
==Examples==
Thanks to the Curry-Howard correspondence, a typed expression whose type corresponds to a logical formula is analogous to a proof of that formula. Here are examples.
===The identity combinator seen as a proof of <tt>α → α</tt> in Hilbert-style logic===
As a simple example, we construct a proof of the theorem <tt>α → α</tt>. In [[lambda calculus]], this is the type of the identity function '''I''' = λ''x''.''x'' and in combinatory logic, the identity function is obtained by applying ''S'' twice to '''K'''. That is, we have '''I''' = (('''S''' '''K''') '''K'''). As a description of a proof, this says that to prove <tt>α → α</tt>, we can proceed as follows:
* instantiate the second axiom scheme with the formulas <tt>α</tt>, <tt>β → α</tt> and <tt>α</tt>, so that to obtain a proof of <tt>(α → ((β → α) → α)) → ((α → (β → α)) → (α → α))</tt>,
* instantiate the first axiom scheme once with <tt>α</tt> and <tt>β → α</tt>, so that to obtain a proof of <tt>α → ((β → α) → α)</tt>,
* instantiate the first axiom scheme a second time with <tt>α</tt> and <tt>β</tt>, so that to obtain a proof of <tt>α → (β → α)</tt>,
* apply modus ponens twice so that to obtain a proof of <tt>α → α</tt>
In general, the procedure is that whenever the program contains an application of the form (''P'' ''Q''), we should first prove theorems corresponding to the types of ''P'' and ''Q''. Since ''P'' is being applied to ''Q'', the type of ''P'' must have the form α → β and the type of ''Q'' must have the form α for some <tt>α</tt> and <tt>β</tt>. We can then detach the conclusion, <tt>β</tt>, via the modus ponens rule.
===The composition combinator seen as a proof of <tt>(β → α) → (γ → β) → γ → α</tt> in Hilbert-style logic===
As a more complicated example, let's look at the theorem that corresponds to the '''B''' function. The type of '''B''' is (β → α) → (γ → β) → γ → α. '''B''' is equivalent to ('''S''' ('''K''' '''S''') '''K'''). This is our roadmap for the proof of the theorem (β → α) → (γ → β) → γ → α.
First we need to construct ('''K''' '''S'''). We make the antecedent of the '''K''' axiom look like the '''S''' axiom by setting α equal to <tt>(α → β → γ) → (α → β) → α → γ</tt>, and <tt>β</tt> equal to <tt>δ</tt>:
: <tt>α → β → α</tt>
: <tt>((α → β → γ) → (α → β) → α → γ) → δ → (α → β → γ) → (α → β) → α → γ</tt>
Since the antecedent here is just '''S''', we can detach the consequent:
: <tt>δ → (α → β → γ) → (α → β) → α → γ</tt>
This is the theorem that corresponds to the type of ('''K''' '''S'''). We now apply '''S''' to this expression. Taking '''S'''
: <tt>(α → β → γ) → (α → β) → α → γ</tt>
we put <tt>α</tt> = <tt>δ</tt>, <tt>β</tt> = <tt>α → β → γ</tt>, and <tt>γ</tt> = <tt>(α → β) → α → γ</tt>, yielding
: <tt>(δ → (α → β → γ) → (α → β) → α → γ) → (δ → (α → β → γ)) → δ → (α → β) → α → γ</tt>
and we then detach the consequent:
: <tt>(δ → α → β → γ) → δ → (α → β) → α → γ</tt>
This is the formula for the type of ('''S''' ('''K''' '''S''')). A special
case of this theorem has <tt>δ</tt> = <tt>(β → γ)</tt>:
: <tt>((β → γ) → α → β → γ) → (β → γ) → (α → β) → α → γ</tt>
We need to apply this last formula to '''K'''. Again, we specialize '''K''', this time by replacing <tt>α</tt> with <tt>(β → γ)</tt> and <tt>β</tt> with <tt>α</tt>:
: <tt>α → β → α</tt>
: <tt>(β → γ) → α → (β → γ)</tt>
This is the same as the antecedent of the prior formula, so we detach the consequent:
: <tt>(β → γ) → (α → β) → α → γ</tt>
Switching the names of the variables <tt>α</tt> and <tt>γ</tt> gives us
: <tt>(β → α) → (γ → β) → γ → α</tt>
which was what we had to prove.
===The normal proof of <tt>(β → α) → (γ → β) → γ → α</tt> in natural deduction seen as a λ-term===
We give below a proof of <tt>(β → α) → (γ → β) → γ → α</tt> in natural deduction and show how it can be interpreted as the λ-expression λ ''a''. λ''b''. λ ''g''.(''a'' (''b'' ''g'')) of type <tt>(β → α) → (γ → β) → γ → α</tt>.
a:β → α, b:γ → β, g:γ {{Unicode|⊢}} b : γ → β a:β → α, b:γ → β, g:γ {{Unicode|⊢}} g : γ
——————————————————————————————————— ————————————————————————————————————————————————————————————————————
a:β → α, b:γ → β, g:γ {{Unicode|⊢}} a : β → α a:β → α, b:γ → β, g:γ {{Unicode|⊢}} b g : β
————————————————————————————————————————————————————————————————————————
a:β → α, b:γ → β {{Unicode|⊢}} a (b g) : α
————————————————————————————————————
a:β → α, b:γ → β {{Unicode|⊢}} λ g. a (b g) : α
————————————————————————————————————————
a:β → α {{Unicode|⊢}} λ b. λ g. a (b g) : α
————————————————————————————————————
{{Unicode|⊢}} λ a. λ b. λ g. a (b g) : α
==External links==
*[http://www.thenewsh.com/~newsham/formal/curryhoward/ The Curry-Howard Correspondence in Haskell]
==References==
=== Seminal references ===
* {{Citation | last1=Curry | first1=Haskell | title=Proceedings of the National Academy of Sciences | chapter=Functionality in Combinatory Logic | year=1934 | volume=20 | pages=584-590}}.
* <cite id="CurryFeys_paragraph9E">{{Citation | last1=Curry | first1=Haskell B. | last2=Feys | first2=Robert | other1-last=Craig | other1-first=William | title=Combinatory Logic Vol. I | publisher=North-Holland | location=Amsterdam | year=1958}}, with 2 sections by William Craig, see paragraph 9E</cite>. <!-- How to explain to the citing mechanism to tell that William Craig wrote two sections of the book? -->
* De Bruijn, Nicolaas (1968), ''Automath, a language for mathematics'', Department of Mathematics, Eindhoven University of Technology, TH-report 68-WSK-05. Reprinted in revised form, with two pages commentary, in: ''Automation and Reasoning, vol 2, Classical papers on computational logic 1967-1970'', Springer Verlag, 1983, pp. 159-200.
* {{Citation | last1=Howard | first1=William A. | editor1-last=Seldin | editor1-first=Jonathan P. | editor2-last=Hindley | editor2-first=J. Roger | title=to H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism | origyear=1969 | publisher=[[Academic Press]] | location=Boston, MA | isbn=978-0-12-349050-6 | year=1980 | month=09 | chapter=The formulae-as-types notion of construction | pages=479–490}} (original manuscript from 1969). <!-- How to explain to the citing mechanism to tell that the paper had remained unpublished from 1969 to 1980? -->
*
=== Extensions of the correspondence ===
* {{Citation | last1=Griffin | first1=Timothy G. | title=Conf. Record 17th Annual ACM Symp. on Principles of Programming Languages, POPL '90, San Francisco, CA, USA, 17-19 Jan 1990 | year=1990 | chapter=The Formulae-as-Types Notion of Control | pages=47–57}}.
* {{Citation | last1=Parigot | first1=Michel | title=Logic Programming and Automated Reasoning: International Conference LPAR '92 Proceedings, St. Petersburg, Russia | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Lecture Notes in Computer Science | isbn=978-3-540-55727-2 | year=1992 | volume=624 | chapter=Lambda-mu-calculus: An algorithmic interpretation of classical natural deduction | pages=190–201}}.
* {{Citation | last1=Herbelin | first1=Hugo | editor1-last=Pacholski | editor1-first=Leszek | editor2-first=Tiuryn | editor2-first=Jerzy | title=Computer Science Logic, 8th International Workshop, CSL '94, Kazimierz, Poland, September 25-30, 1994, Selected Papers | publisher=[[Springer-Verlag]] | series=Lecture Notes in Computer Science | isbn=978-3-540-60017-5 | year=1995 | volume=933 | chapter=A Lambda-Calculus Structure Isomorphic to Gentzen-Style Sequent Calculus Structure | pages=61-75}}.
* {{Citation | last1=Gabbay | first1=Dov | last2=de Queiroz | first2=Ruy | title=Journal of Symbolic Logic | chapter=Extending the Curry-Howard interpretation to linear, relevant and other resource logics | year=1992 | volume=57 | pages=1319–1365}}. (Full version of the paper presented at ''Logic Colloquium '90'', Helsinki. Abstract in ''JSL'' 56(3):1139-1140, 1991.)
* {{Citation | last1=de Queiroz | first1=Ruy | last2=Gabbay | first2=Dov | editor1-last=Dekker | editor1-first=Paul | editor2-last=Stokhof | editor2-first=Martin | title=Proceedings of the Ninth Amsterdam Colloquium | chapter=Equality in Labelled Deductive Systems and the Functional Interpretation of Propositional Equality | year=1994|publisher=ILLC/Department of Philosophy, University of Amsterdam | isbn=9074795072 | pages=547-565}}.
* {{Citation | last1=de Queiroz | first1=Ruy | last2=Gabbay | first2=Dov | title=Bulletin of the Interest Group in Pure and Applied Logics | chapter=The Functional Interpretation of the Existential Quantifier | year=1995 | volume=3(2-3) | pages=243-290}}. (Full version of a paper presented at ''Logic Colloquium '91'', Uppsala. Abstract in ''JSL'' 58(2):753-754, 1993.)
* {{Citation | last1=de Queiroz | first1=Ruy | last2=Gabbay | first2=Dov | editor1-last=de Rijke | editor1-first=Maarten | title=Advances in Intensional Logic | chapter=The Functional Interpretation of Modal Necessity | isbn=978-0-7923-4711-8 | year=1997|publisher=[[Springer-Verlag]] |series=Applied Logic Series | volume=7 | pages=61-91}}.
* {{Citation | last1=de Oliveira | first1=Anjolina | last2=de Queiroz | first2=Ruy | title=Logic Journal of the Interest Group in Pure and Applied Logics | chapter=A Normalization Procedure for the Equational Fragment of Labelled Natural Deduction | publisher=[[Oxford Univ Press]] | year=1999 | volume=7(2) | pages=173-215}}. (Full version of a paper presented at ''2nd WoLLIC'95'', Recife. Abstract in ''Journal of the Interest Group in Pure and Applied Logics'' 4(2):330-332, 1996.)
=== Synthetic papers ===
* {{Citation | last1=De Bruijn | first1=Nicolaas Govert | editor1-last=Groote | editor1-first=Philippe de | title=The Curry-Howard isomorphism | publisher=Academia-Bruyland | series=Cahiers du Centre de logique (Université catholique de Louvain) | isbn=978-2-87209-363-2 | volume=8 | chapter=On the roles of types in mathematics | chapterurl=http://alexandria.tue.nl/repository/freearticles/597627.pdf | pages=27–54}}, the contribution of de Bruijn by himself.
*{{Citation | last1=Geuvers | first1=Herman | editor1-last=Groote | editor1-first=Philippe de | title=The Curry-Howard isomorphism | publisher=Academia-Bruyland | series=Cahiers du Centre de logique (Université catholique de Louvain) | isbn=978-2-87209-363-2 | volume=8 | chapter=The Calculus of Constructions and Higher Order Logic | pages=139–191}}, contains a synthetic introduction to the Curry-Howard correspondence.
* {{Citation | last1=Gallier | first1=Jean H. | editor1-last=Groote | editor1-first=Philippe de | title=The Curry-Howard isomorphism | publisher=Academia-Bruyland | series=Cahiers du Centre de logique (Université catholique de Louvain) | isbn=978-2-87209-363-2 | volume=8 | chapter=On the Correspondence between Proofs and Lambda-Terms | chapterurl=ftp://ftp.cis.upenn.edu/pub/papers/gallier/cahiers.pdf | pages=55–138}}, contains a synthetic introduction to the Curry-Howard correspondence.
=== Books ===
*{{Citation | editor1-last=De Groote | editor1-first=Philippe | title=The Curry-Howard Isomorphism | publisher=Academia-Bruylant | series=Cahiers du Centre de Logique (Université catholique de Louvain) | isbn=978-2-87209-363-2 | year=1995 | volume=8}}, reproduces the seminal papers of Curry-Feys and Howard, a paper by de Bruijn and a few other papers.
* {{citation | last1=Sörensen | first1=Morten Heine | last2=Urzyczyn | first2=Paweł | title=Lectures on the Curry-Howard isomorphism | publisher=[[Elsevier Science]] | year=2006 | origyear=1998 | isbn=978-0-44452-077-7 | volume=149 | series=Studies in Logic and the Foundations of Mathematics}}, notes on proof theory and type theory, that includes a presentation of the Curry-Howard correspondence, with a focus on the formulae-as-types correspondence
* Girard, Jean-Yves (1987-90). ''[http://www.monad.me.uk/stable/Proofs+Types.html Proof and Types]''. Translated by and with appendices by Lafont, Yves and Taylor, Paul. Cambridge University Press (Cambridge Tracts in Theoretical Computer Science, 7), ISBN 0 521 37181 3, notes on proof theory with a presentation of the Curry-Howard correspondence.
* Thompson, Simon (1991). ''[http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ Type Theory and Functional Programming]'' Addison-Wesley. ISBN 0-201-41667-0.
{{Wikibooks|Haskell|The Curry-Howard isomorphism}}
[[Category:Proof theory]]
[[Category:Logic in computer science]]
[[Category:Type theory]]
[[fr:Correspondance de Curry-Howard]]
[[pl:Izomorfizm Curry'ego-Howarda]]
[[zh:Curry-Howard同构]]