# ProofObjectsThe Curry-Howard Correspondence

"Algorithms are the computational content of proofs." —Robert Harper
Programming and proving in Coq are two sides of the same coin. Proving manipulates evidence, much as programs manipuate data.
Question: If evidence is data, what are propositions themselves?
Answer: They are types!
Look again at the formal definition of the even property.
Print even.
(* ==>
Inductive even : nat -> Prop :=
| ev_0 : even 0
| ev_SS : forall n, even n -> even (S (S n)).
*)

Suppose we introduce an alternative pronunciation of ":". Instead of "has type," we can say "is a proof of." For example, the second line in the definition of even declares that ev_0 : even 0. Instead of "ev_0 has type even 0," we can say that "ev_0 is a proof of even 0."
This pun between types and propositions — between : as "has type" and : as "is a proof of" or "is evidence for" — is called the Curry-Howard correspondence. It proposes a deep connection between the world of logic and the world of computation:
```                 propositions  ~  types
proofs        ~  data values
```
See [Wadler 2015] for a brief history and up-to-date exposition.
Many useful insights follow from this connection. To begin with, it gives us a natural interpretation of the type of the ev_SS constructor:
Check ev_SS.
(* ===> ev_SS : forall n,
even n ->
even (S (S n)) *)

This can be read "ev_SS is a constructor that takes two arguments — a number n and evidence for the proposition even n — and yields evidence for the proposition even (S (S n))."
Now let's look again at a previous proof involving even.
Theorem ev_4 : even 4.
Proof.
apply ev_SS. apply ev_SS. apply ev_0. Qed.
As with ordinary data values and functions, we can use the Print command to see the proof object that results from this proof script.
Print ev_4.
(* ===> ev_4 = ev_SS 2 (ev_SS 0 ev_0)
: even 4  *)

Indeed, we can also write down this proof object directly, without the need for a separate proof script:
Check (ev_SS 2 (ev_SS 0 ev_0)).
(* ===> even 4 *)
Similarly, recall that we can apply theorems to arguments in proof scripts:
Theorem ev_4': even 4.
Proof.
apply (ev_SS 2 (ev_SS 0 ev_0)).
Qed.

# Proof Scripts

When we build a proof using tactics, Coq internally constructs a proof object. We can see how this happens using Show Proof:
Theorem ev_4'' : even 4.
Proof.
Show Proof.
apply ev_SS.
Show Proof.
apply ev_SS.
Show Proof.
apply ev_0.
Show Proof.
Qed.
Tactic proofs are useful and convenient, but they are not essential: in principle, we can always construct the required evidence by hand, as shown above. Then we can use Definition (rather than Theorem) to give a global name directly to this evidence.
Definition ev_4''' : even 4 :=
ev_SS 2 (ev_SS 0 ev_0).
All these different ways of building the proof lead to exactly the same evidence being saved in the global environment.
Print ev_4.
(* ===> ev_4    =   ev_SS 2 (ev_SS 0 ev_0) : even 4 *)
Print ev_4'.
(* ===> ev_4'   =   ev_SS 2 (ev_SS 0 ev_0) : even 4 *)
Print ev_4''.
(* ===> ev_4''  =   ev_SS 2 (ev_SS 0 ev_0) : even 4 *)
Print ev_4'''.
(* ===> ev_4''' =   ev_SS 2 (ev_SS 0 ev_0) : even 4 *)

# Quantifiers, Implications, Functions

In Coq's computational universe (where data structures and programs live), there are two sorts of values with arrows in their types: constructors introduced by Inductively defined data types, and functions.
Similarly, in Coq's logical universe (where we carry out proofs), there are two ways of giving evidence for an implication: constructors introduced by Inductively defined propositions, and... functions!
For example, consider this statement:
Theorem ev_plus4 : n, even neven (4 + n).
Proof.
intros n H. simpl.
apply ev_SS.
apply ev_SS.
apply H.
Qed.
What is the proof object corresponding to ev_plus4?
We're looking for an expression whose type is n, even n even (4 + n) — that is, a function that takes two arguments (one number and a piece of evidence) and returns a piece of evidence!
Here it is:
Definition ev_plus4' : n, even neven (4 + n) :=
fun (n : nat) ⇒ fun (H : even n) ⇒
ev_SS (S (S n)) (ev_SS n H).
Or:
Definition ev_plus4'' (n : nat) (H : even n)
: even (4 + n) :=
ev_SS (S (S n)) (ev_SS n H).

Check ev_plus4''.
(* ===>
: forall n : nat, even n -> even (4 + n) *)

When we view the proposition being proved by ev_plus4 as a function type, one interesting point becomes apparent: The second argument's type, even n, mentions the value of the first argument, n.
While such dependent types are not found in conventional programming languages, they can be useful in programming too, as the recent flurry of activity in the functional programming community demonstrates.
Notice that both implication () and quantification () correspond to functions on evidence. In fact, they are really the same thing: is just a shorthand for a degenerate use of where there is no dependency, i.e., no need to give a name to the type on the left-hand side of the arrow:
(x:nat), nat
=  (_:nat), nat
=  nat → nat
Recall the definition of even:
Inductive even : nat → Prop :=
| ev_0 : even 0
| ev_SS : neven n → even (S (S n)).
What is the type of this expression?
fun (n : nat) ⇒
fun (H : even n) ⇒
ev_SS (2 + n) (ev_SS n H)
(1) n, even n
(2) n, even (2 + n)
(3) n, even n even n
(4) n, even n even (2 + n)
(5) n, even n even (4 + n)
(6) Not typeable

# Programming with Tactics

If we can build proofs by giving explicit terms rather than executing tactic scripts, you may be wondering whether we can build programs using tactics rather than explicit terms. Naturally, the answer is yes!
Definition add1 : natnat.
intro n.
Show Proof.
apply S.
Show Proof.
apply n. Defined.

Print add1.
(* ==>
add1 = fun n : nat => S n
: nat -> nat
*)

Compute add1 2.
(* ==> 3 : nat *)
Notice that we terminate the Definition with a . rather than with := followed by a term. This tells Coq to enter proof scripting mode to build an object of type nat nat. Also, we terminate the proof with Defined rather than Qed; this makes the definition transparent so that it can be used in computation like a normally-defined function. (Qed-defined objects are opaque during computation.)
This feature is mainly useful for writing functions with dependent types, which we won't explore much further in this book. But it does illustrate the uniformity and orthogonality of the basic ideas in Coq.

# Logical Connectives as Inductive Types

Inductive definitions are powerful enough to express most of the connectives we have seen so far. Indeed, only universal quantification (with implication as a special case) is built into Coq; all the others are defined inductively. We'll see these definitions in this section.

## Conjunction

To prove that P Q holds, we must present evidence for both P and Q. Thus, it makes sense to define a proof object for P Q as consisting of a pair of two proofs: one for P and another one for Q. This leads to the following definition.
Inductive and (P Q : Prop) : Prop :=
| conj : PQand P Q.
Notice the similarity with the definition of the prod type, given in chapter Poly; the only difference is that prod takes Type arguments, whereas and takes Prop arguments.
Print prod.
(* ===>
Inductive prod (X Y : Type) : Type :=
| pair : X -> Y -> X * Y. *)

This similarity should clarify why destruct and intros patterns can be used on a conjunctive hypothesis. Case analysis allows us to consider all possible ways in which P Q was proved — here just one (the conj constructor).
Similarly, the split tactic actually works for any inductively defined proposition with exactly one constructor. In particular, it works for and:
Lemma and_comm : P Q : Prop, PQQP.
Proof.
intros P Q. split.
- intros [HP HQ]. split.
+ apply HQ.
+ apply HP.
- intros [HP HQ]. split.
+ apply HQ.
+ apply HP.
Qed.
This shows why the inductive definition of and can be manipulated by tactics as we've been doing. We can also use it to build proofs directly, using pattern-matching. For instance:
Definition and_comm'_aux P Q (H : PQ) : QP :=
match H with
| conj HP HQconj HQ HP
end.

Definition and_comm' P Q : PQQP :=
conj (and_comm'_aux P Q) (and_comm'_aux Q P).
What is the type of this expression?
fun P Q R (H1and P Q) (H2and Q R) ⇒
match (H1,H2with
| (conj _ _ HP _conj _ _ _ HR) ⇒ conj P R HP HR
end.
(1) P Q R, P Q Q R P R
(2) P Q R, Q P R Q P R
(3) P Q R, P R
(4) P Q R, P Q Q R P R
(5) Not typeable

## Disjunction

The inductive definition of disjunction uses two constructors, one for each side of the disjunct:
Inductive or (P Q : Prop) : Prop :=
| or_introl : Por P Q
| or_intror : Qor P Q.
This declaration explains the behavior of the destruct tactic on a disjunctive hypothesis, since the generated subgoals match the shape of the or_introl and or_intror constructors.
Once again, we can also directly write proof objects for theorems involving or, without resorting to tactics.
What is the type of this expression?
fun P Q H ⇒
match H with
| or_introl HP ⇒ or_intror Q P HP
| or_intror HQ ⇒ or_introl Q P HQ
end.
(1) P Q H, Q P H
(2) P Q, P Q P Q
(3) P Q H, P Q Q P H
(4) P Q, P Q Q P
(5) Not typeable

## Existential Quantification

To give evidence for an existential quantifier, we package a witness x together with a proof that x satisfies the property P:
Inductive ex {A : Type} (P : AProp) : Prop :=
| ex_intro : x : A, P xex P.
This may benefit from a little unpacking. The core definition is for a type former ex that can be used to build propositions of the form ex P, where P itself is a function from witness values in the type A to propositions. The ex_intro constructor then offers a way of constructing evidence for ex P, given a witness x and a proof of P x.
The more familiar form x, P x desugars to an expression involving ex:
Check ex (fun neven n).
(* ===> exists n : nat, even n
: Prop *)

Here's how to define an explicit proof object involving ex:
Definition some_nat_is_even : n, even n :=
ex_intro even 4 (ev_SS 2 (ev_SS 0 ev_0)).

## True and False

The inductive definition of the True proposition is simple:
Inductive True : Prop :=
| I : True.
It has one constructor (so every proof of True is the same, so being given a proof of True is not informative.)
False is equally simple — indeed, so simple it may look syntactically wrong at first glance!
Inductive False : Prop := .
That is, False is an inductive type with no constructors — i.e., no way to build evidence for it.

# Equality

Even Coq's equality relation is not built in. It has the following inductive definition. (Actually, the definition in the standard library is a slight variant of this, which gives an induction principle that is slightly easier to use.)
Inductive eq {X:Type} : XXProp :=
| eq_refl : x, eq x x.

Notation "x == y" := (eq x y)
(at level 70, no associativity)
: type_scope.
The way to think about this definition is that, given a set X, it defines a family of propositions "x is equal to y," indexed by pairs of values (x and y) from X. There is just one way of constructing evidence for members of this family: applying the constructor eq_refl to a type X and a single value x : X, which yields evidence that x is equal to x.
Other types of the form eq x y where x and y are not the same are thus uninhabited.
We can use eq_refl to construct evidence that, for example, 2 = 2. Can we also use it to construct evidence that 1 + 1 = 2? Yes, we can. Indeed, it is the very same piece of evidence!
The reason is that Coq treats as "the same" any two terms that are convertible according to a simple set of computation rules.
These rules, which are similar to those used by Compute, include evaluation of function application, inlining of definitions, and simplification of matches.
Lemma four: 2 + 2 == 1 + 3.
Proof.
apply eq_refl.
Qed.
The reflexivity tactic that we have used to prove equalities up to now is essentially just shorthand for apply eq_refl.
In tactic-based proofs of equality, the conversion rules are normally hidden in uses of simpl (either explicit or implicit in other tactics such as reflexivity).
But you can see them directly at work in the following explicit proof objects:
Definition four' : 2 + 2 == 1 + 3 :=
eq_refl 4.

Definition singleton : (X:Type) (x:X), []++[x] == x::[] :=
fun (X:Type) (x:X) ⇒ eq_refl [x].

Which of the following is a correct proof object for the proposition
xx + 3 = 4
?
(1) eq_refl 4
(2) ex_intro nat (fun z (z + 3 = 4)) 1 eq_refl
(3) ex_intro nat (z + 3 = 4) 1 (eq_refl 4)
(4) ex_intro nat (fun z (z + 3 = 4)) 1 (eq_refl 4)
(5) ex_intro nat (fun z (z + 3 = 4)) 1 (eq_refl 1)
(6) none of the above
Which of the following propositions is proved by providing an explicit witness w using exist w?
(1) x: nat, ( n, x = S n) (x≠0)
(2) x: nat, (x≠0) ( n, x = S n)
(3) x: nat, (x=0) ~( n, x = S n)
(4) x: nat, x = 4 (x≠0)
(5) none of the above

## Inversion, Again

We've seen inversion used with both equality hypotheses and hypotheses about inductively defined propositions. Now that we've seen that these are actually the same thing, we're in a position to take a closer look at how inversion behaves.
In general, the inversion tactic...
• takes a hypothesis H whose type P is inductively defined, and
• for each constructor C in P's definition,
• generates a new subgoal in which we assume H was built with C,
• adds the arguments (premises) of C to the context of the subgoal as extra hypotheses,
• matches the conclusion (result type) of C against the current goal and calculates a set of equalities that must hold in order for C to be applicable,
• adds these equalities to the context (and, for convenience, rewrites them in the goal), and
• if the equalities are not satisfiable (e.g., they involve things like S n = O), immediately solves the subgoal.
Example: If we invert a hypothesis built with or, there are two constructors, so two subgoals get generated. The conclusion (result type) of the constructor (P Q) doesn't place any restrictions on the form of P or Q, so we don't get any extra equalities in the context of the subgoal.
Example: If we invert a hypothesis built with and, there is only one constructor, so only one subgoal gets generated. Again, the conclusion (result type) of the constructor (P Q) doesn't place any restrictions on the form of P or Q, so we don't get any extra equalities in the context of the subgoal. The constructor does have two arguments, though, and these can be seen in the context in the subgoal.
Example: If we invert a hypothesis built with eq, there is again only one constructor, so only one subgoal gets generated. Now, though, the form of the eq_refl constructor does give us some extra information: it tells us that the two arguments to eq must be the same! The inversion tactic adds this fact to the context.