Archive | Coq

# Baby’s First Proof

Unlike many languages that you learn, in Coq, things are truly different. Much like your first functional language after using nothing but imperative languages, you have to re-evaluate things. Instead of just defining functions, you have to prove properties of them. So, let’s take a look at a few basic ways to do that.

## Simpl and Reflexivity

Here we have two basic “tactics” that we can use to prove simple properties. Suppose we have some function `addition`. We’re all familiar with how this works; `2 + 2 = 4`, right? Prove it:

``````Lemma two_plus_two:
2 + 2 = 4.
Proof.

First, what is this `Admitted.` thing? Admitted basically tells Coq not to worry about it, and just assume it is true. This is the equivalent of your math professor telling you “don’t worry about it, Aristotle says it’s true, are you calling Aristotle a liar?” and if you let this make it into live code, you are a bad person. We must make this right!

``````Lemma two_plus_two:
2 + 2 = 4.
Proof.
simpl.
reflexivity.
Qed.``````

That’s better. This is a simple proof; we tell Coq to simplify the expression, then we tell Coq to verify that the left-hand-side is the same as the right-hand-side. One nice feature of Coq is that lets you step through these proofs to see exactly how the evaluation is proceeding. If you’re using Proof General, you can use the buttons `Next`, `Goto`, and `Undo` to accomplish this. If you put the point at `Proof.` and click `Goto`, Coq will evaluate the buffer up to that point, and a window should appear at the bottom with the following:

``````1 subgoals, subgoal 1 (ID 2)

============================
2 + 2 = 4``````

This is telling you that Coq has 1 thing left to prove: ` 2 + 2 = 4`. Click next, the bottom should change to:

``````1 subgoals, subgoal 1 (ID 2)

============================
4 = 4``````

Coq processed the `simpl` tactic and now the thing it needs to prove is that `4 = 4`. Obviously this is true, so if we click next…

``No more subgoals.``

`reflexivity` should succeed, and it does. If we click next one more time:

``two_plus_two is defined``

This says that this Lemma has been defined, and we can now refer to it in other proofs, much like we can call a function. Now, you may be wondering “do I really have to simplify `2 + 2`?” No, you don’t, `reflexivity` will simplify on it’s own, this typechecks just fine:

``````Lemma two_plus_two:
2 + 2 = 4.
Proof.
reflexivity.
Qed.``````

So, what’s the point of `simpl` then? Let’s consider a more complicated proof.

## Induction

``````Lemma n_plus_zero_eq_n:
forall (n : nat), n + 0 = n.``````

This lemma state that for any n, n + 0 = n. This is the same as when you’d write `∀` in some math. Other bits of new syntax is `n : nat`, which means that n has the type nat. The idea here is that no matter what natural number n is, n + 0 = n. So how do we prove this? One might be tempted to try:

``````Lemma n_plus_zero_eq_n:
forall (n : nat), n + 0 = n.
Proof.
reflexivity.
Qed.``````

One would be wrong. What is Coq stupid? Clearly n + 0 = n, Aristotle told me so! Luckily for us, this is a pretty easy proof, we just need to be explicit about it. We can use induction to prove this. Let me show the whole proof, then we’ll walk through it step by step.

``````Lemma n_plus_zero_eq_n:
forall (n : nat), n + 0 = n.
Proof.
intros n.
induction n as [| n'].
{
reflexivity.
}
{
simpl.
rewrite -> IHn'.
reflexivity.
}
Qed.``````

Place the point at `Proof` and you’ll see the starting goal:

``````1 subgoals, subgoal 1 (ID 6)

============================
forall n : nat, n + 0 = n``````

Click next and step over `intros n.`

``````1 subgoals, subgoal 1 (ID 7)

n : nat
============================
n + 0 = n``````

What happened here is `intros n` introduces the variable n, and names it n. We could have done `intros theNumber` and the bottom window would instead show:

``````1 subgoals, subgoal 1 (ID 7)

theNumber : nat
============================
theNumber + 0 = theNumber``````

The `intros` tactic reads from left to right, so if we had some `Lemma foo : forall (n m : nat), [stuff]`, we could do `intros nName mName.`, and it would read in n, and bind it to nName, and then read in m and bind it to mName. Click next and evaluate `induction n as [| n'].`

``````2 subgoals, subgoal 1 (ID 10)

============================
0 + 0 = 0

subgoal 2 (ID 13) is:
S n' + 0 = S n'``````

The `induction` tactic implements the standard proof by induction, splitting our goal into two goals: the base case and the n + 1 case. Similarly to `intros`, this will create subgoals starting with the first constructor of an ADT, and ending with the last.

## On Natural Numbers in Coq

Let us take a second to talk about how numbers are represented in Coq. Coq re-implements all types within itself, so `nat` isn’t a machine integer, it’s an algebraic datatype of the form:

``````Inductive nat : Set :=
| O : nat
| S : nat -> nat.``````

`O` is zero, `S O` is one, and `S (S (S (O)))` is three. There is a lot of syntax sugar in place that lets you write 49 instead of `S (S ( ... ( S O) ... ))`, and that’s a good thing.

The point of all of this is that we can pattern match on `nat` much like we can a list.

## More Induction

…anyways, all this brings us back to induction and this mysterious `as [| n'].` What this is doing is binding names to all the fields of the ADT we are deconstructing. The `O` constructor takes no parameters, so there is nothing to the left of the `|`. The `S` constructor takes a `nat`, so we give it the name `n'`. Click next and observe the bottom change:

``````1 focused subgoals (unfocused: 1)
, subgoal 1 (ID 10)

============================
0 + 0 = 0``````

The curly braces “focuses” the current subgoal, hiding all irrelevant information. Curly braces are optional, but I find them to be very helpful as the bottom window can become very cluttered in large proofs. Here we see the base case goal being to prove that 0 + 0 = 0. Obviously this is true, and we can have Coq verify this by `reflexivity.` Click next until the next opening curly brace is evaluated. We see the next subgoal:

``````1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 13)

n' : nat
IHn' : n' + 0 = n'
============================
S n' + 0 = S n'``````

So, what do we have here? This is the n + 1 case; here the n’ in `S n'` is the original n. A particularly bored reader may try to prove `forall (n : nat), S n = n + 1` and I’ll leave that as an exercise. However, this follows from the definition of `nat`.

Also of note here is `IHn'`. `IH` stands for induction hypothesis, and this is that n’ + 0 = n’. So, how do we proceed? Click next and observe how the subgoal changes:

``````1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 15)

n' : nat
IHn' : n' + 0 = n'
============================
S (n' + 0) = S n'``````

It brought the `+ 0` inside the `S` constructor. Notice that now there is `n' + 0` on the left hand side. Click next and watch closely what happens:

``````1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 16)

n' : nat
IHn' : n' + 0 = n'
============================
S n' = S n'``````

Here we use the induction hypothesis to rewrite all occurrences of `n' + 0`, which was the left hand side of the induction hypothesis as `n'`, which was the right hand side of the induction hypothesis. This is what the `rewrite` tactic does. Notice now that the subgoal is `S n' = S n'` which `reflexivity` will surely find to be true. So, what would happen if we had done `rewrite <- IHn'.`?

``````1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 16)

n' : nat
IHn' : n' + 0 = n'
============================
S (n' + 0 + 0) = S (n' + 0)``````

It rewrote all instances of `n'`, which was the right hand side of the induction hypothesis with `n' + 0` which was the left hand side of the induction hypothesis. Obviously, this isn’t what we want. I should note that you can undo this by rewriting to the right twice…

``````  {
simpl.
rewrite <- IHn'.
rewrite -> IHn'.
rewrite -> IHn'.
reflexivity.
}``````

…and it will technically work. But don’t do this, it’s silly and there’s no room for silliness in a rigorous mathematical proof.

Personally, I have a hard time keeping it straight what the left and right rewrites do. I sometimes find myself just trying one, and then the other if I guessed wrong. Think of it like this: `rewrite -> foo` rewrites the current goal, replacing all occurrences of the thing on the left hand side of the equation of `foo` with the thing on the right hand side of the equation. It changes from the left to the right. And vice-versa for `rewrite <-`, which changes from the right to the left.

# Getting Started With Coq and Proof General

Today we’ll be talking about Coq. Coq is a dependently typed programming language and theorem proof assistant. Given that I’ve just now got the toolchain installed, I’m hardly qualified to say much more than that. However, I am qualified to talk about installing the toolchain, which is precisely what I intend to do.

To get started with Coq, you’ll need the usual things: a properly configured editor and the Coq compiler. Installing these isn’t terribly difficult. First, let’s install the compiler. If you’re running Ubuntu, this is quite simple:

``\$ sudo apt-get install coq``

After this is done, you should have access to the compiler (`coqc`) and the REPL (`coqtop`):

``````\$ which coqc
/usr/bin/coqc
\$ which coqtop
/usr/bin/coqtop
\$ coqc --version
The Coq Proof Assistant, version 8.4pl4 (July 2014)
compiled on Jul 27 2014 23:12:44 with OCaml 4.01.0``````

OK! Now for the (slightly) harder part: our properly configured editor. Here we have two choices: CoqIDE or Proof General. CoqIDE is a simple IDE that ships with Coq, so if you’re satisfied with this, then feel free to stop reading now: CoqIDE comes with Coq and should be already installed at this point!

However, if you want to be truly cool, you’ll opt for Proof General. Proof General is an Emacs plugin. Unfortunately, Proof General is not available in Melpa, so we get to install it manually. Fortunately for us, Proof General is in the repos, so if you’re running Ubuntu you can just `apt-get` it:

``\$ sudo apt-get install proofgeneral proofgeneral-doc``

This will install Proof General, and set Emacs to load it up when you open a `.v` file. (My condolences to all those who write Verilog and Coq on the same machine) However, some configuration remains to be done. First fire up emacs and execute:

``M-x customize-group <enter> proof-general <enter>``

Expand `Proof Assistants` and ensure `Coq` is selected. Now open up a `.v` file and behold the glory!

Wait a minute, where’s my undo-tree? My rainbow-delimiters? My whitespace-mode? It’s not your imagination, Proof General has inexplicably ignored your fancy `.emacs` config. This is all a bit irritating, but you can work around it by re-adding these things to the `coq-mode-hook`:

``````(add-hook 'coq-mode-hook 'rainbow-delimiters-mode)