# Theorem Proving¶

## Equality¶

Idris allows propositional equalities to be declared, allowing theorems about programs to be stated and proved. Equality is built in, but conceptually has the following definition:

```
data (=) : a -> b -> Type where
Refl : x = x
```

Equalities can be proposed between any values of any types, but the only way to construct a proof of equality is if values actually are equal. For example:

```
fiveIsFive : 5 = 5
fiveIsFive = Refl
twoPlusTwo : 2 + 2 = 4
twoPlusTwo = Refl
```

## The Empty Type¶

There is an empty type, \(\bot\), which has no constructors. It is therefore impossible to construct an element of the empty type, at least without using a partially defined or general recursive function (see Section Totality Checking for more details). We can therefore use the empty type to prove that something is impossible, for example zero is never equal to a successor:

```
disjoint : (n : Nat) -> Z = S n -> Void
disjoint n p = replace {P = disjointTy} p ()
where
disjointTy : Nat -> Type
disjointTy Z = ()
disjointTy (S k) = Void
```

There is no need to worry too much about how this function works —
essentially, it applies the library function `replace`

, which uses an
equality proof to transform a predicate. Here we use it to transform a
value of a type which can exist, the empty tuple, to a value of a type
which can’t, by using a proof of something which can’t exist.

Once we have an element of the empty type, we can prove anything.
`void`

is defined in the library, to assist with proofs by
contradiction.

```
void : Void -> a
```

## Simple Theorems¶

When type checking dependent types, the type itself gets *normalised*.
So imagine we want to prove the following theorem about the reduction
behaviour of `plus`

:

```
plusReduces : (n:Nat) -> plus Z n = n
```

We’ve written down the statement of the theorem as a type, in just the same way as we would write the type of a program. In fact there is no real distinction between proofs and programs. A proof, as far as we are concerned here, is merely a program with a precise enough type to guarantee a particular property of interest.

We won’t go into details here, but the Curry-Howard correspondence [1]
explains this relationship. The proof itself is trivial, because
`plus Z n`

normalises to `n`

by the definition of `plus`

:

```
plusReduces n = Refl
```

It is slightly harder if we try the arguments the other way, because
plus is defined by recursion on its first argument. The proof also works
by recursion on the first argument to `plus`

, namely `n`

.

```
plusReducesZ : (n:Nat) -> n = plus n Z
plusReducesZ Z = Refl
plusReducesZ (S k) = cong (plusReducesZ k)
```

`cong`

is a function defined in the library which states that equality
respects function application:

```
cong : {f : t -> u} -> a = b -> f a = f b
```

We can do the same for the reduction behaviour of plus on successors:

```
plusReducesS : (n:Nat) -> (m:Nat) -> S (plus n m) = plus n (S m)
plusReducesS Z m = Refl
plusReducesS (S k) m = cong (plusReducesS k m)
```

Even for trivial theorems like these, the proofs are a little tricky to construct in one go. When things get even slightly more complicated, it becomes too much to think about to construct proofs in this “batch mode”.

Idris provides interactive editing capabilities, which can help with building proofs. For more details on building proofs interactively in an editor, see Theorem Proving.

## Theorems in Practice¶

The need to prove theorems can arise naturally in practice. For example,
previously (Views and the “with” rule) we implemented `natToBin`

using a function
`parity`

:

```
parity : (n:Nat) -> Parity n
```

However, we didn’t provide a definition for `parity`

. We might expect it
to look something like the following:

```
parity : (n:Nat) -> Parity n
parity Z = Even {n=Z}
parity (S Z) = Odd {n=Z}
parity (S (S k)) with (parity k)
parity (S (S (j + j))) | Even = Even {n=S j}
parity (S (S (S (j + j)))) | Odd = Odd {n=S j}
```

Unfortunately, this fails with a type error:

```
When checking right hand side of with block in views.parity with expected type
Parity (S (S (j + j)))
Type mismatch between
Parity (S j + S j) (Type of Even)
and
Parity (S (S (plus j j))) (Expected type)
```

The problem is that normalising `S j + S j`

, in the type of `Even`

doesn’t result in what we need for the type of the right hand side of
`Parity`

. We know that `S (S (plus j j))`

is going to be equal to
`S j + S j`

, but we need to explain it to Idris with a proof. We can
begin by adding some *holes* (see Holes) to the definition:

```
parity : (n:Nat) -> Parity n
parity Z = Even {n=Z}
parity (S Z) = Odd {n=Z}
parity (S (S k)) with (parity k)
parity (S (S (j + j))) | Even = let result = Even {n=S j} in
?helpEven
parity (S (S (S (j + j)))) | Odd = let result = Odd {n=S j} in
?helpOdd
```

Checking the type of `helpEven`

shows us what we need to prove for the
`Even`

case:

```
j : Nat
result : Parity (S (plus j (S j)))
--------------------------------------
helpEven : Parity (S (S (plus j j)))
```

We can therefore write a helper function to *rewrite* the type to the form
we need:

```
helpEven : (j : Nat) -> Parity (S j + S j) -> Parity (S (S (plus j j)))
helpEven j p = rewrite plusSuccRightSucc j j in p
```

The `rewrite ... in`

syntax allows you to change the required type of an
expression by rewriting it according to an equality proof. Here, we have
used `plusSuccRightSucc`

, which has the following type:

```
plusSuccRightSucc : (left : Nat) -> (right : Nat) -> S (left + right) = left + S right
```

We can see the effect of `rewrite`

by replacing the right hand side of
`helpEven`

with a hole, and working step by step. Beginning with the following:

```
helpEven : (j : Nat) -> Parity (S j + S j) -> Parity (S (S (plus j j)))
helpEven j p = ?helpEven_rhs
```

We can look at the type of `helpEven_rhs`

:

```
j : Nat
p : Parity (S (plus j (S j)))
--------------------------------------
helpEven_rhs : Parity (S (S (plus j j)))
```

Then we can `rewrite`

by applying `plusSuccRightSucc j j`

, which gives
an equation `S (j + j) = j + S j`

, thus replacing `S (j + j)`

(or,
in this case, `S (plus j j)`

since `S (j + j)`

reduces to that) in the
type with `j + S j`

:

```
helpEven : (j : Nat) -> Parity (S j + S j) -> Parity (S (S (plus j j)))
helpEven j p = rewrite plusSuccRightSucc j j in ?helpEven_rhs
```

Checking the type of `helpEven_rhs`

now shows what has happened, including
the type of the equation we just used (as the type of `_rewrite_rule`

):

```
j : Nat
p : Parity (S (plus j (S j)))
_rewrite_rule : S (plus j j) = plus j (S j)
--------------------------------------
helpEven_rhs : Parity (S (plus j (S j)))
```

Using `rewrite`

and another helper for the `Odd`

case, we can complete
`parity`

as follows:

```
helpEven : (j : Nat) -> Parity (S j + S j) -> Parity (S (S (plus j j)))
helpEven j p = rewrite plusSuccRightSucc j j in p
helpOdd : (j : Nat) -> Parity (S (S (j + S j))) -> Parity (S (S (S (j + j))))
helpOdd j p = rewrite plusSuccRightSucc j j in p
parity : (n:Nat) -> Parity n
parity Z = Even {n=Z}
parity (S Z) = Odd {n=Z}
parity (S (S k)) with (parity k)
parity (S (S (j + j))) | Even = helpEven j (Even {n = S j})
parity (S (S (S (j + j)))) | Odd = helpOdd j (Odd {n = S j})
```

Full details of `rewrite`

are beyond the scope of this introductory tutorial,
but it is covered in the theorem proving tutorial (see Theorem Proving).

## Totality Checking¶

If we really want to trust our proofs, it is important that they are
defined by *total* functions — that is, a function which is defined for
all possible inputs and is guaranteed to terminate. Otherwise we could
construct an element of the empty type, from which we could prove
anything:

```
-- making use of 'hd' being partially defined
empty1 : Void
empty1 = hd [] where
hd : List a -> a
hd (x :: xs) = x
-- not terminating
empty2 : Void
empty2 = empty2
```

Internally, Idris checks every definition for totality, and we can check at
the prompt with the `:total`

command. We see that neither of the above
definitions is total:

```
*Theorems> :total empty1
possibly not total due to: empty1#hd
not total as there are missing cases
*Theorems> :total empty2
possibly not total due to recursive path empty2
```

Note the use of the word “possibly” — a totality check can, of course, never be certain due to the undecidability of the halting problem. The check is, therefore, conservative. It is also possible (and indeed advisable, in the case of proofs) to mark functions as total so that it will be a compile time error for the totality check to fail:

```
total empty2 : Void
empty2 = empty2
```

```
Type checking ./theorems.idr
theorems.idr:25:empty2 is possibly not total due to recursive path empty2
```

Reassuringly, our proof in Section The Empty Type that the zero and successor constructors are disjoint is total:

```
*theorems> :total disjoint
Total
```

The totality check is, necessarily, conservative. To be recorded as
total, a function `f`

must:

- Cover all possible inputs
- Be
*well-founded*— i.e. by the time a sequence of (possibly mutually) recursive calls reaches`f`

again, it must be possible to show that one of its arguments has decreased. - Not use any data types which are not
*strictly positive* - Not call any non-total functions

### Directives and Compiler Flags for Totality¶

By default, Idris allows all well-typed definitions, whether total or not. However, it is desirable for functions to be total as far as possible, as this provides a guarantee that they provide a result for all possible inputs, in finite time. It is possible to make total functions a requirement, either:

- By using the
`--total`

compiler flag. - By adding a
`%default total`

directive to a source file. All definitions after this will be required to be total, unless explicitly flagged as`partial`

.

All functions *after* a `%default total`

declaration are required to
be total. Correspondingly, after a `%default partial`

declaration, the
requirement is relaxed.

Finally, the compiler flag `--warnpartial`

causes to print a warning
for any undeclared partial function.

### Totality checking issues¶

Please note that the totality checker is not perfect! Firstly, it is
necessarily conservative due to the undecidability of the halting
problem, so many programs which *are* total will not be detected as
such. Secondly, the current implementation has had limited effort put
into it so far, so there may still be cases where it believes a function
is total which is not. Do not rely on it for your proofs yet!

### Hints for totality¶

In cases where you believe a program is total, but Idris does not agree, it is
possible to give hints to the checker to give more detail for a termination
argument. The checker works by ensuring that all chains of recursive calls
eventually lead to one of the arguments decreasing towards a base case, but
sometimes this is hard to spot. For example, the following definition cannot be
checked as `total`

because the checker cannot decide that `filter (< x) xs`

will always be smaller than `(x :: xs)`

:

```
qsort : Ord a => List a -> List a
qsort [] = []
qsort (x :: xs)
= qsort (filter (< x) xs) ++
(x :: qsort (filter (>= x) xs))
```

The function `assert_smaller`

, defined in the prelude, is intended to
address this problem:

```
assert_smaller : a -> a -> a
assert_smaller x y = y
```

It simply evaluates to its second argument, but also asserts to the
totality checker that `y`

is structurally smaller than `x`

. This can
be used to explain the reasoning for totality if the checker cannot work
it out itself. The above example can now be written as:

```
total
qsort : Ord a => List a -> List a
qsort [] = []
qsort (x :: xs)
= qsort (assert_smaller (x :: xs) (filter (< x) xs)) ++
(x :: qsort (assert_smaller (x :: xs) (filter (>= x) xs)))
```

The expression `assert_smaller (x :: xs) (filter (<= x) xs)`

asserts
that the result of the filter will always be smaller than the pattern
`(x :: xs)`

.

In more extreme cases, the function `assert_total`

marks a
subexpression as always being total:

```
assert_total : a -> a
assert_total x = x
```

In general, this function should be avoided, but it can be very useful when reasoning about primitives or externally defined functions (for example from a C library) where totality can be shown by an external argument.

[1] | Timothy G. Griffin. 1989. A formulae-as-type notion of control. In Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ‘90). ACM, New York, NY, USA, 47-58. DOI=10.1145/96709.96714 http://doi.acm.org/10.1145/96709.96714 |