There are a small number of people who might care about this, but, there is an XMPP server available for anybody who might want to talk types, theorem proving, etc. Here are the details:

You may register here: https://chat.typesofnote.com/#converse/register And you can log in to chat here: https://chat.typesofnote.com/

You are of course welcome to use any XMPP client you wish, but the converse web client is available for anybody who so chooses.

Why use this?

An advantage of XMPP is that you are able to use any XMPP client you desire — no vender lock in. Be happy. Here’s a few options:

- pidgin
- gajim
- profanity
- poezio
- converse.js
- conversations (Android, best gotten from f-droid)
- ChatSecure (iOS)
- Monal (iOS / Mac)
- adium (Mac)

I intend to keep all of the history available, so we can build up more sources of information for people getting into theorem proving and verification.

There probably won’t be many people hanging around, but that can change if you stick around :). Install a client on your phone and stick around, and maybe we’ll get somewhere!

Read more / comment »I realized that there wasn’t any mention of this on the home page here. Maybe it’s time we do that. There are some notes available from the DeepSpec Summer School in 2017. These notes were extracted from the slack, and actually contain a lot of tips and tricks.

Dig in here: https://www.typesofnote.com/dsss17-slack.html

Read more / comment »There are a couple of notions of truthiness in Coq. For example `Prop`

and `bool`

.

`bool`

and `Prop`

One advantage of `Prop`

over `bool`

is that `Prop`

is essentially a built in which works well with tactics like `rewrite`

in the case of equality.

`Type`

and `Prop`

Term erasing

Read more / comment »https://softwarefoundations.cis.upenn.edu/draft/lf-current/Tactics.html#lab139

By introducing a variable you are saying for a “particular” instance of that variable. Not for all such instances of the variable.

Thus, when introducing more than necessary prior to induction you may unintentionally weaken the induction hypothesis that you will get, making it impossible to prove your goal.

When you `destruct`

a compound expression you lose what the original equation was. For instance:

```
destruct (beq_nat 3 n).
```

will give you two subgoals. One where `(beq_nat 3 n)`

is replaced with `true`

, and one where it is replaced with `false`

.

Sometimes, however, you actually need the fact that ```
(beq_nat 3 n)
= true
```

in that branch of the proof, or that ```
(beq_nat 3 n) =
false
```

in the other branch of the proof. You can keep this information with:

```
destruct (beq_nat 3 n) eqn:Hbeq3.
```

Which will introduce in the context a hypothesis `Hbeq3`

which will be `beq_nat 3 n = true`

in the `true`

branch of the proof, and `beq_nat 3 n = false`

in the false branch.

Working with dependent types in Coq has been causing me a number of headaches — which I have found somewhat surprising coming from Agda / Idris.

I believe part of this is syntactic, and that Agda for instance kind of has you working with terms in a dependently typed language in the raw, unlike Coq which often has you using tactics, which are a bit of a step away from what’s actually going on. But the other part seems to be that Agda includes this so called “axiom K” by default, and Coq does not.

In Agda you might use the absurd pattern to deal with branches of a program which should never be executed due to a condition which will never hold. I.e., if the condition to enter the branch is true, then that condition implies False.

```
hd {X} (xs : list X) (length xs > 0) : X
```

For instance, in the case of a `hd`

function, which takes the first element of the list, you might have an argument that’s a proof that the length of the list is greater than 0. But, you still have to provide a case to the match on the list for when it’s empty.

Well, that’s okay. Because in Coq we can use an empty pattern match on False. So you might think you can do something like this:

```
Require Import List.
Lemma length_nil_not_gt_0 :
forall {X}, @length X nil > 0 -> False.
Proof.
intros X H. inversion H.
Qed.
Definition hd {X} (xs : list X) (pf : length xs > 0) : X :=
match xs with
| nil => match length_nil_not_gt_0 pf with end
| h :: t => h
end.
```

But this doesn’t quite work.

```
Error:
In environment
X : Type
xs : list X
pf : length xs > 0
The term "pf" has type "length xs > 0" while it is expected to have type
"length nil > 0".
```

For some reason Coq seems to not be recognizing that in this branch `xs = nil`

, and so it’s not replacing `xs`

with `nil`

when it’s typechecking.

So, how can we get around this? What seems to be happening is that `pf`

is getting tied to the type `length xs > 0`

at the beginning, at the very top level.

The way to get around this is to make `hd`

actually return a function, which takes a proof as an argument. This lets the `pf`

have a different type in each branch.

```
Require Import List.
Lemma length_nil_not_gt_0 :
forall {X}, @length X nil > 0 -> False.
Proof.
intros X H. inversion H.
Qed.
Definition hd {X} (xs : list X) : (length xs > 0) -> X :=
match xs with
| nil => fun pf => match length_nil_not_gt_0 pf with end
| h :: t => fun _ => h
end.
```

Read more / comment »
`intros`

Introduces variables and hypothesis. This takes them out of the goal and puts them in the context.

You can automatically destruct variables with patterns like ```
[x |
y]
```

which will split a sum type into its two constructors, and call the resulting variables `x`

and `y`

respectively, leading to two subgoals. A product type may also be destructed into its parts with `[x y]`

. These may be combined in arbitrary ways such as ```
[x | [x
y] | [x | y z]]
```

, depending on the type of what is being introduced. The empty pattern `[]`

may be used to destruct an impossible value, and automatically solve a branch, such as if you would be introducing `False`

.

`reflexivity`

Does reflexivity. If a goal has `x = y`

it will try to simplify (by normalization) both `x`

and `y`

. If their normal forms are syntactically identical, then this tactic will succeed and the goal will be completed.

E.g.,

```
1 + 1 = 2
```

Reflexivity will solve this because `1 + 1`

will evaluate to `2`

, and `2 = 2`

is obviously true because each side of the equality is syntactically identical.

`simpl`

Attempts to simplify the goal. This essentially just evaluates to weak head normal form. Useful for seeing next steps in a proof (hard to unwind definitions in your head sometimes), and it can be used to facilitate rewrites.

```
1 + 1 = 2
```

`simpl`

will transform this to `2 = 2`

.

`simpl`

sometimes won’t evaluate as much as you expect, because if it always evaluated as much as it possibly could you would end up with really long terms. So, simple has some heuristics to decide when to keep evaluating, and when not to.

`rewrite`

When we have `x = y`

it can be used to replace `x`

with `y`

in a goal, or vice versa.

```
H : x = y
=========
x = y
```

Then `rewrite H`

will leave us with the goal `y = y`

, and `rewrite <- H`

will leave us with `x = x`

.

`subst`

If you have

```
H : x = y
```

You can call `subst`

and it will substitute all variable equalities. This is a bit wild, but useful with other wild tactics like `inversion`

`apply`

Used to solve a goal by applying a theorem which has an identical conclusion to the current goal. Any hypothesis of the theorem will be added to the context.

This tactic can also be used on hypothesis in the context which then matches on the hypothesis of the theorem being applied and gives you a hypothesis in the context matching the goal of the theorem being applied.

```
H : x = y
=========
x = y
```

`apply H`

will solve the goal.

```
H : x = y -> y = z
H0 : x = y
==================
y = z
```

You could solve this in two ways with `apply`

:

`apply H`

will use the theorem`H`

to show that`y = z`

if`x = y`

, so it leaves you with`x = y`

in your goal. This can then be solved by applying`H0`

.`apply H in H0`

will use`H : x = y -> y = z`

to transform`H0 : x = y`

to`y = z`

. After this we can apply`H0`

to our goal.

`assumption`

This calls `apply`

on a hypothesis in the context that matches the goal. I.e., it finds the hypothesis for you.

`symmetry`

Reverses an equality. Using `symmetry`

will flip `x = y`

to `y = x`

.

This is useful for when you need to `apply`

a theorem, but the goal is in a different order than the theorem.

`destruct`

The `destruct`

tactic is used to perform case analysis in Coq. It will break a possible value into all cases for that type (one for each constructor of the type). This gives you multiple goals to prove; one for each constructor.

This can be used on variables, or compound expressions.

When using destruct on a compound expression it is also possible to save the original expression.

`destruct (f (x + y)) eqn:Hfxy`

`induction`

The `induction`

tactic is very similar to `destruct`

, except that it brings an induction hypothesis into the context for recursive data types.

`inversion`

`inversion`

provides reasoning with constructors taking into account the fact that constructors are injective and disjoint.

- Injective: for a constructor
`A`

,`A x = A y`

means that`x = y`

as well. - Disjoint: If you have two constructors
`A`

and`B`

, then you know that`A`

does not equal`B`

Thus the inversion tactic has several uses.

```
H : A x = A y
=============
x = y
```

When using `inversion in H`

this gives us a new hypothesis, `H1`

.

```
H : A x = A y
H1 : x = y
=============
y = y
```

It will also perform rewrites with the new hypothesis automatically, so our goal changed to `y = y`

as well, since it rewrote `x`

with `y`

using the new hypothesis `H1`

.

Inversion will apply this injective reasoning across multiple arguments in a constructor, and even recursively. So, if you have lists of three items that are equal you will get a hypothesis representing the equality of each item in the first list, with the equivalent item in the second list.

We can name the equations as well.

`inversion in H as [Hxy]`

will give:

```
H : A x = A y
Hxy : x = y
=============
y = y
```

If we have values constructed with two different constructors `A`

and `B`

, then we know that the values must be different. So if we have a hypothesis in the context with disjoint constructors, like so:

```
H: A x = B y
============
false = true
```

We can use `inversion H`

which will conclude that `H`

is a false hypothesis, and since we have a contradiction in our set of assumptions we may conclude the goal via the principle of explosion.

`generalize dependent`

The `generalize dependent`

tactic can be used to place a variable in the context back into the goal. This can be useful when you only want to introduce certain variables, like when you want to keep your induction hypothesis strong.

`unfold`

This tactic is used to expand a definition.

```
Definition square n := n * n
```

```
square (n * m) = square n * square m
```

`unfold square`

will yield

```
(n * m) * (n * m) = (n * n) * (m * m)
```

which will actually display as

```
n * m * (n * m) = n * n * (m * m)
```

due to the associativity of the operators.

This tactic can be very useful when you can simplify a definition based on rewriting a term inside the definition. For instance if the definition contains a `match`

like:

```
match test x with
| true => some_stuff
| false => other_stuff
end.
```

Then if you have `test x = true`

in the context you can simplify this `match`

to just `some_stuff`

.

`assert`

This tactic will introduce a hypothesis into the context, and then split the goal into two subgoals. The first subgoal is to prove that this hypothesis is true, and the second subgoal is the original goal.

`split`

Used to split a conjunction in a goal into two subgoals.

If the conjunction is in the context, and not the goal, then one would use `destruct`

instead.

`left`

and `right`

These tactics are used to pick a side of a disjunction in the goal to prove.

`exfalso`

Turns the goal into `False`

. This is useful when working with negations.

`exists`

Used in proofs with existential quantifiers. For instance if our goal was

```
exists x : nat, x = 2 + 2
```

Then `exists 4`

would substitute `4`

for `x`

, removing the existential quantifier, and leaving us with:

```
4 = 2 + 2
```

Which can then be solved with `reflexivity`

.

Theorems have arguments, since they’re really just types of functions. For example:

```
plus_comm : forall n m : n + m = m + n
```

When applying a theorem normally Coq guesses what the arguments to the theorem will be based on the first suitable instance it finds. This can be annoying because sometimes it applies it to the wrong part of the expression we want to prove!

So, instead of having Coq guess what `n`

and `m`

should be we can provide it with arguments.

```
rewrite (plus_comm p).
```

Will rewrite a term where `p`

is substituted for `n`

in the `plus_comm`

theorem.

```
plus_comm p : forall m : p + m = m + p
```

This works in pretty much any tactic, like `destruct`

, since theorems are just first class objects in Coq.