# Joachim Breitner's Homepage

## Isabelle functions: Always total, sometimes undefined

Often, when I mention how things work in the interactive theorem prover Isabelle/HOL (in the following just “Isabelle”^{1}) to people with a strong background in functional programming (whether that means Haskell or Coq or something else), I cause confusion, especially around the issue of *what is a function*, are functions *total* and what is the business with *undefined*. In this blog post, I want to explain some these issues, aimed at functional programmers or type theoreticians.

Note that this is not meant to be a tutorial; I will not explain how to do these things, and will focus on what they mean.

### HOL is a logic of total functions

If I have a Isabelle function `f :: a ⇒ b`

between two types `a`

and `b`

(the function arrow in Isabelle is `⇒`

, not `→`

), then – by definition of what it means to be a function in HOL – whenever I have a value `x :: a`

, then the expression `f x`

(i.e. `f`

applied to `x`

) *is* a value of type `b`

. Therefore, and without exception, *every Isabelle function is total*.

In particular, it cannot be that `f x`

does not exist for some `x :: a`

. This is a first difference from Haskell, which does have partial functions like

^{2}. But the word “function”, in the context of Isabelle, refers to the mathematical concept of a function, and it helps to keep that in mind.

What is the difference?

- A function
`a → b`

in functional programming is an algorithm that, given a value of type`a`

, calculates (returns, evaluates to) a value of type`b`

. - A function
`a ⇒ b`

in math (or Isabelle) associates with each value of type`a`

a value of type`b`

.

For example, the following is a perfectly valid function definition in math (and HOL), but could not be a function in the programming sense:

```
definition foo :: "(nat ⇒ real) ⇒ real" where
"foo seq = (if convergent seq then lim seq else 0)"
```

This assigns a real number to every sequence, but it does not *compute* it in any useful sense.

From this it follows that

### Isabelle functions are specified, not defined

Consider this function definition:

```
fun plus :: "nat ⇒ nat ⇒ nat" where
"plus 0 m = m"
| "plus (Suc n) m = Suc (plus n m)"
```

To a functional programmer, this reads

`plus`

is a function that analyses its first argument. If that is`0`

, then it returns the second argument. Otherwise, it calls itself with the predecessor of the first argument and increases the result by one.

which is clearly a description of a computation.

But to Isabelle, the above reads

`plus`

is a binary function on natural numbers, and it satisfies the following two equations: …

And in fact, it is not so much Isabelle that reads it this way, but rather the `fun`

command, which is external to the Isabelle logic. The `fun`

command analyses the given equations, constructs a non-recursive definition of `plus`

under the hood, passes *that* to Isabelle and then proves that the given equations hold for `plus`

.

One interesting consequence of this is that different specifications can lead to the same functions. In fact, if we would define `plus'`

by recursing on the second argument, we’d obtain the the same function (i.e. `plus = plus'`

is a theorem, and there would be no way of telling the two apart).

### Termination is a property of specifications, not functions

Because a function does not evaluate, it does not make sense to ask if it terminates. The question of termination arises *before* the function is defined: The `fun`

command can only construct `plus`

in a way that the equations hold if it passes a termination check – very much like `Fixpoint`

in Coq.

But while the termination check of `Fixpoint`

in Coq is a deep part of the basic logic, in Isabelle it is simply something that this particular command requires for its internal machinery to go through. At no point does a “termination proof of the function” exist as a theorem inside the logic. And other commands may have other means of defining a function that do not even require such a termination argument!

For example, a function specification that is tail-recursive can be turned in to a function, even without a termination proof: The following definition describes a higher-order function that iterates its first argument `f`

on the second argument `x`

until it finds a fixpoint. It is completely polymorphic (the single quote in `'a`

indicates that this is a type variable):

```
partial_function (tailrec)
fixpoint :: "('a ⇒ 'a) ⇒ 'a ⇒ 'a"
where
"fixpoint f x = (if f x = x then x else fixpoint f (f x))"
```

We can work with this definition just fine. For example, if we instantiate `f`

with `(λx. x-1)`

, we can prove that it will always return 0:

```
lemma "fixpoint (λ n . n - 1) (n::nat) = 0"
by (induction n) (auto simp add: fixpoint.simps)
```

Similarly, if we have a function that works within the option monad (i.e. |Maybe| in Haskell), its specification can always be turned into a function without an explicit termination proof – here one that calculates the Collatz sequence:

```
partial_function (option) collatz :: "nat ⇒ nat list option"
where "collatz n =
(if n = 1 then Some [n]
else if even n
then do { ns <- collatz (n div 2); Some (n # ns) }
else do { ns <- collatz (3 * n + 1); Some (n # ns)})"
```

Note that lists in Isabelle are finite (like in Coq, unlike in Haskell), so this function “returns” a list only if the collatz sequence eventually reaches 1.

I expect these definitions to make a Coq user very uneasy. How can `fixpoint`

be a total function? What is `fixpoint (λn. n+1)`

? What if we run `collatz n`

for a `n`

where the Collatz sequence does *not* reach 1?^{3} We will come back to that question after a little detour…

### HOL is a logic of non-empty types

Another big difference between Isabelle and Coq is that in Isabelle, *every type is inhabited*. Just like the totality of functions, this is a very fundamental fact about what HOL defines to be a type.

Isabelle gets away with that design because in Isabelle, we do not use types for propositions (like we do in Coq), so we do not need empty types to denote false propositions.

This design has an important consequence: It allows the existence of a polymorphic expression that inhabits any type, namely

`undefined :: 'a`

The naming of this term alone has caused a great deal of confusion for Isabelle beginners, or in communication with users of different systems, so I implore you to not read too much into the name. In fact, you will have a better time if you think of it as `arbitrary`

or, even better, `unknown`

.

Since `undefined`

can be instantiated at any type, we can instantiate it for example at `bool`

, and we can observe an important fact: `undefined`

is not an *extra* value besides the “usual ones”. It is simply *some* value of that type, which is demonstrated in the following lemma:

`lemma "undefined = True ∨ undefined = False" by auto`

In fact, if the type has only one value (such as the unit type), then we know the value of `undefined`

for sure:

`lemma "undefined = ()" by auto`

It is very handy to be able to produce an expression of any type, as we will see as follows

### Partial functions are just underspecified functions

For example, it allows us to translate incomplete function specifications. Consider this definition, Isabelle’s equivalent of Haskell’s partial `fromJust`

function:

HOLCF, where you can give equational specifications of functional programs and obtain *continuous functions* between *domains*. In that setting, `⊥ ≠ ()`

and `partial2 = ⊥ ≠ total`

. We have done that to verify some of HLint’s equations.

### You can still compute with Isabelle functions

I hope by this point, I have not scared away anyone who wants to use Isabelle for functional programming, and in fact, you can use it for that. If the equations that you pass to `fun are a reasonable definition for a function (in the programming sense), then these equations, used as rewriting rules, will allow you to “compute” that function quite like you would in Coq or Haskell.

Moreover, Isabelle supports code extraction: You can take the equations of your Isabelle functions and have them expored into Ocaml, Haskell, Scala or Standard ML. See Concon for a conference management system with confidentially verified in Isabelle.

While these usually are the equations you defined the function with, they don’t have to: You can declare other proved equations to be used for code extraction, e.g. to refine your elegant definitions to performant ones.

Like with code extraction from Coq to, say, Haskell, the adequacy of the translations rests on a “moral reasoning” foundation. Unlike extraction from Coq, where you have an (unformalized) guarantee that the resulting Haskell code is terminating, you do not get that guarantee from Isabelle. Conversely, this allows you do reason about and extract non-terminating programs, like `fixpoint`

, which is not possible in Coq.

There is currently ongoing work about verified code generation, where the code equations are reflected into a deep embedding of HOL in Isabelle that would allow explicit termination proofs.

### Conclusion

We have seen how in Isabelle, *every function is total*. Function declarations have equations, but these do not *define* the function in an computational sense, but rather *specify* them. Because in HOL, there are no empty types, many specifications that appear partial (incomplete patterns, non-terminating recursion) have solutions in the space of total functions. Partiality in the specification is no longer visible in the final product.

### PS: Axiom `undefined`

in Coq

*This section is speculative, and an invitation for discussion.*

Coq already distinguishes between types used in programs (`Set`

) and types used in proofs `Prop`

.

Could Coq ensure that every `t : Set`

is non-empty? I imagine this would require additional checks in the `Inductive`

command, similar to the checks that the Isabelle command `datatype`

has to perform^{4}, and it would disallow `Empty_set`

.

If so, then it would be sound to add the following axiom

`Axiom undefined : forall (a : Set), a.`

wouldn’t it? This axiom does not have any computational meaning, but that seems to be ok for optional Coq axioms, like classical reasoning or function extensionality.

With this in place, how much of what I describe above about function definitions in Isabelle could now be done soundly in Coq. Certainly pattern matches would not have to be complete and could sport an implicit case `_ ⇒ undefined`

. Would it “help” with non-obviously terminating functions? Would it allow a Coq command `Tailrecursive`

that accepts any tailrecursive function without a termination check?

Isabelle is a metalogical framework, and other logics, e.g. Isabelle/ZF, behave differently. For the purpose of this blog post, I always mean Isabelle/HOL.↩︎

At least we do not violate this term as much as the imperative programmers do.↩︎

Let me know if you find such an

*n*. Besides*n*= 0.↩︎Like

`fun`

, the constructions by`datatype`

are not part of the logic, but create a type definition from more primitive notions that is isomorphic to the specified data type.↩︎

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.