Inductive datatypes in HOL — lessons learned in Formal-Logic Engineering

Stefan Berghofer and Markus Wenzel

Technische Universität München Institut für Informatik, Arcisstraße 21, 80290 München, Germany

                     http://www.in.tum.de/~berghofe/
                      http://www.in.tum.de/~wenzelm/

Abstract. Isabelle/HOL has recently acquired new versions of definitional packages for inductive datatypes and primitive recursive functions. In contrast to its predecessors and most other implementations, Isabelle/HOL datatypes may be mutually and indirect recursive, even infinitely branching. We also support inverted datatype definitions for characterizing existing types as being inductive ones later. All our constructions are fully definitional according to established HOL tradition. Stepping back from the logical details, we also see this work as a typical example of what could be called “Formal-Logic Engineering”. We observe that building realistic theorem proving environments involves further issues rather than pure logic only.

1 Introduction

Theorem proving systems for higher-order logics, such as HOL [5], Coq [4], PVS [15], and Isabelle [18], have reached a reasonable level of maturity to support non-trivial applications. As an arbitrary example, consider Isabelle/Bali [14], which is an extensive formalization of substantial parts of the Java type system and operational semantics undertaken in Isabelle/HOL.

Nevertheless, the current state-of-the-art is not the final word on theorem proving technology. Experience from sizable projects such as Isabelle/Bali shows that there are quite a lot of requirements that are only partially met by existing systems. Focusing on the actual core system only, and ignoring further issues such as user interfaces for theorem provers, there are several layers of concepts of varying logical status to be considered. This includes purely syntactic tools (parser, pretty printer, macros), type checking and type inference, basic deductive tools such as (higher-order) unification or matching, proof procedures (both simple and automatic ones), and search utilities — just to name a few.

Seen from a wider perspective, the actual underlying logic (set theory, type theory etc.) becomes only one element of a much larger picture. Consequently, making a theorem proving system a “success” involves more than being good in the pure logic rating. There is a big difference of being able to express certain concepts in principle in some given logic vs. offering our customers scalable mechanisms for actually doing it in the system.

Advanced definitional mechanisms are a particularly important aspect of any realistic formal-logic environment. While working in the pure logic would be sufficient in principle, actual applications demand not only extensive libraries of derived concepts, but also general mechanisms for introducing certain kinds of mathematical objects. A typical example of the latter would be inductive sets and types, together with recursive function definitions.

According to folklore, theorem proving is similar to programming, but slightly more difficult. Apparently, the same holds for the corresponding development tools, with an even more severe gap of sophistication, though. For example, consider the present standard in interactive theorem proving technology related to that of incremental compilers for languages such as ML or Haskell. Apparently, our theorem provers are still much more primitive and inaccessible to a wider audience than advanced programming language compilers. In particular, definitional mechanisms, which are in fact resembling a “theory compiler” quite closely, are often much less advanced than our users would expect.

An obvious way to amend for this, we argue, would be to transfer general concepts and methodologies from the established disciplines of Software and Systems Engineering to that of theorem proving systems, eventually resulting in what could be called Formal-Logic Engineering.

Getting back to firm grounds, and the main focus of this paper, we discuss the new versions of advanced definitional mechanisms that Isabelle/HOL has acquired recently: inductive or coinductive definitions of sets (via the usual Knaster-Tarski construction, cf. [17]), inductive datatypes, and primitive recursive functions. Our primary efforts went into the datatype and primrec mechanisms [2], achieving a considerably more powerful system than had been available before. In particular, datatypes may now involve mutual and indirect recursion, and arbitrary branching over existing types.^{1} Furthermore, datatype definitions may now be inverted in the sense that existing types (such as natural numbers) may be characterized later on as being inductive, too.

The new packages have been designed for cooperation with further subsystems of Isabelle/HOL already in mind: recdef for general well-founded functions [21, 22], and record for single-inheritance extensible records [13]. Unquestionably, more such applications will emerge in the future. The hierarchy of current Isabelle/HOL definitional packages is illustrated below. Note that constdef and typedef refer to HOL primitives [5], and axclass to axiomatic type classes [24].

[figure: constdef; typedef; coinductive; inductive; datatype; recdef; record; primrec; axclass]

1 Arbitrary (infinite) branching is not yet supported in Isabelle98-1.

The basic mode of operation of any “advanced” definitional package such as datatype is as follows: given a simple description of the desired result theory by the user, the system automatically generates a sizable amount of characteristic theorems and derived notions underneath. There are different approaches, stemming from different logical traditions, of how this is achieved exactly. These approaches can be roughly characterized as follows.

Axiomatic The resulting properties are generated syntactically only, and in-

troduced into the theory as axioms (e.g. [16]). Inherent The underlying logic is extended in order to support the desired ob-

jects in a very direct way (e.g. [20]). Definitional Taking an existing logic for granted, the new objects are repre-

sented in terms of existing concepts, and the desired properties are derived from the definitions within the system (e.g. [2]).

Any of these approaches have well-known advantages and disadvantages. For example, the definitional way is certainly a very hard one, demanding quite a lot of special purpose theorem proving work of the package implementation. On the other hand, it is possible to achieve a very high quality of the resulting system — both in the purely logical sense meaning that no “wrong” axioms are asserted and in a wider sense of theorem proving system technology in general.

The rest of this paper is structured as follows. Section 2 presents some examples illustrating the user-level view of Isabelle/HOL’s new datatype and primrec packages. Section 3 briefly reviews formal-logic preliminaries relevant for our work: HOL basics, simple definitions, inductive sets. Section 4 describes in detail the class of admissible datatype specifications, observing fundamental limitations of classical set theory. Section 5 recounts techniques for constructing mutually and indirectly recursive, infinitely branching datatypes in HOL, including principles for induction and recursion. Section 6 discusses some issues of integrating the purely-logical achievements into a scalable working environment.

2 Examples

As our first toy example, we will formalize some aspects of a very simple functional programming language, consisting of arithmetic and boolean expressions formalized as types α aexp and α bexp (parameter α is for program variables).

datatype α aexp = If (α bexp) (α aexp) (α aexp)
| Sum (α aexp) (α aexp)
| Var α
| Num nat
and  α bexp = Less (α aexp) (α aexp)
| And (α bexp) (α bexp)

This specification emits quite a lot of material into the current theory context, first of all injective functions Sum :: α aexp → α aexp → α aexp etc. for any of the datatype constructors. Each valid expression of our programming language is denoted by a well-typed constructor-term. Functions on inductive types are typically defined by primitive recursion. We now define evaluation functions for arithmetic and boolean expressions, depending on an environment e :: α → nat.

consts evala :: (α → nat) → α aexp → nat evalb :: (α → nat) → α bexp → bool

primrec evala e (If b a_{1} a_{2}) = (if evalb e b then evala e a_{1} else evala e a_{2}) evala e (Sum a_{1} a_{2}) = evala e a_{1} + evala e a_{2} evala e (Var v) = e v evala e (Num n) = n evalb e (Less a_{1} a_{2}) = (evala e a_{1} < evala e a_{2}) evalb e (And b_{1} b_{2}) = (evalb e b_{1} ∧ evalb e b_{2})

Similarly, we may define substitution functions for expressions. The mapping s :: α → α aexp given as a parameter is lifted canonically on aexp and bexp.

consts substa :: (α → α aexp) → α aexp → α aexp substb :: (α → α aexp) → α bexp → α bexp

primrec substa s (If b a_{1} a_{2}) = If (substb s b) (substa s a_{1}) (substa s a_{2}) substa s (Sum a_{1} a_{2}) = Sum (substa s a_{1}) (substa s a_{2}) substa s (Var v) = s v substa s (Num n) = Num n substb s (Less a_{1} a_{2}) = Less (substa s a_{1}) (substa s a_{2}) substb s (And b_{1} b_{2}) = And (substb s b_{1}) (substb s b_{2})

The relationship between substitution and evaluation can be expressed by:

lemma evala e (substa s a) = evala (λx. evala e (s x)) a ∧ evalb e (substb s b) = evalb (λx. evala e (s x)) b

We can prove this theorem by straightforward reasoning involving mutual structural induction on a and b, which is expressed by the following rule:

\begin{aligned}∀b a_{1} a_{2}. Q b ∧ P a_{1} ∧ P a_{2} & ⟹ & P (If b a_{1} a_{2}) \\ & ⋯ \\ ∀a_{1} a_{2}. P a_{1} ∧ P a_{2} & ⟹ & Q (Less a_{1} a_{2}) \\ & ⋯ \end{aligned} ; P a ∧ Q b

As a slightly more advanced example we now consider the type (α, β, γ)tree, which is made arbitrarily branching by nesting an appropriate function type.

datatype (α, β, γ)tree = Atom α | Branch β (γ → (α, β, γ)tree)

Here α stands for leaf values, β for branch values, γ for subtree indexes. It is important to note that γ may be any type, including an infinite one such as nat; it need not even be a datatype. The induction rule for (α, β, γ)tree is

∀a. P (Atom a) ∀b f. (∀x. P (f x)) ⟹ P (Branch b f)

P t

Note how we may assume that the predicate P holds for all values of f, all subtrees, in order to show P (Branch b f). Using this induction rule, Isabelle/HOL automatically proves the existence of combinator tree-rec for primitive recursion:

tree-rec :: (α → δ) → (β → (γ → (α, β, γ)tree) → (γ → δ) → δ) → (α, β, γ)tree → δ tree-rec f_{1} f_{2} (Atom a) = f_{1} a tree-rec f_{1} f_{2} (Branch b f) = f_{2} b f ((tree-rec f_{1} f_{2}) ∘ f)

In the case of Branch, the function tree-rec f_{1} f_{2} is recursively applied to all function values of f, i.e. to all subtrees. As an example primitive recursive function on type tree, consider the function member c which checks whether a tree contains some Atom c. It could be expressed as tree-rec (λa. a = c) (λb f f′. ∃x. f′ x). Isabelle/HOL’s primrec package provides a more accessible interface:

primrec member c (Atom a) = (a = c) member c (Branch b f) = (∃x. member c (f x))

3 Formal-Logic Preliminaries

3.1 The Logic of Choice?

This question is a rather subtle one. Actually, when it comes to real applications within a large system developed over several years, there is not much choice left about the underlying logic. Changing the very foundations of your world may be a very bad idea, if one cares for the existing base of libraries and applications.

HOL [5], stemming from Church’s “Simple Theory of Types” [3] has proven a robust base over the years. Even if simplistic in some respects, HOL proved capable of many sophisticated constructions, sometimes even because of seeming weaknesses. For example, due to simple types HOL admits interesting concepts such as intra-logical overloading [24] or object-oriented features [13]. Our constructions for inductive types only require plain simply-typed set theory, though.

3.2 Isabelle/HOL — Simply-Typed Set Theory

The syntax of HOL is that of simply-typed λ-calculus. Types are either variables α, or applications (τ_{1}, …, τ_{n})t, including function types τ_{1} → τ_{2} (right associative infix). Terms are either typed constants c_{τ} or variables x_{τ}, applications (t u) or abstractions λx.t. Terms have to be well-typed according to standard rules. Theories consist of a signature of types and constants, and axioms. Any theory induces a set of derivable theorems ⊢ φ, depending on a fixed set of deduction rules that state several “obvious” facts of classical set theory. Starting from a minimalistic basis theory, all further concepts are developed definitionally.

Isabelle/HOL provides many standard notions of classical set-theory. Sets are of type α set; infix f “ A refers to the image, vimage f A to the reverse image of f on A; inv f inverts a function; lfp F and gfp F are the least and greatest fixpoints of F on the powerset lattice. The sum type α + β has constructors Inl and Inr. Most other operations use standard mathematical notation.

3.3 Simple Definitions

The HOL methodology dictates that only definitional theory extension mechanisms may be used. HOL provides two primitive mechanisms: constant definitions and type definitions [5], further definitional packages are built on top.

• Constant definition We may add a new constant c to the signature and introduce an axiom of the form ⊢ c v_{1} … v_{n} ≡ t, provided that c does not occur in t, TV (t) ⊆ TV (c) and FV (t) ⊆ {v_{1}, …, v_{n}}.

• Type definition Let t-rep be a term of type τ set describing a non-empty set, i.e. ⊢ u ∈ t-rep for some u. Moreover, require TV (t-rep) ⊆ {α_{1}, …, α_{n}}. We may then add the type (α_{1}, …, α_{n})t and the following constants

\begin{aligned}Abs-t & :: & τ → (α_{1}, …, α_{n})t \\ Rep-t & :: & (α_{1}, …, α_{n})t → τ \end{aligned}  [figure: Abs-t; Rep-t; τ; t-rep; (α_{1}, …, α_{n})t]

to the signature and introduce the axioms

⊢ Abs-t (Rep-t x) = x  (Rep-t-inverse)
⊢ y ∈ t-rep ⟹ Rep-t (Abs-t y) = y  (Abs-t-inverse)
⊢ Rep-t x ∈ t-rep  (Rep-t)

Type definitions are a slightly peculiar feature of HOL. The idea is to represent new types by subsets of already existing ones. The axioms above state that there is a bijection (isomorphism) between the set t-rep and the new type (α_{1}, …, α_{n})t. This is justified by the standard set-theoretic semantics of HOL [5].

3.4 Inductive definitions

An inductive [17] definition specifies the least set closed under certain introduction rules — generally, there are many such closed sets. Essentially, an inductively defined set is the least fixpoint lfp F of a certain monotone function F, where lfp F = ⋂{x | F x ⊆ x}. The Knaster-Tarski theorem states that lfp F is indeed a fixpoint and that it is the least one, i.e. F (lfp F) = lfp F and

{F P ⊆ P \atop lfp F ⊆ P}  {F (lfp F ∩ P) ⊆ P \atop lfp F ⊆ P}

where P is the set of all elements satisfying a certain predicate. Both rules embody an induction principle for the set lfp F. The second (stronger) rule is easily derived from the first one, because F is monotone. See [17] for more detailes on how to determine a suitable function F from a given set of introduction rules. When defining several mutually inductive sets S_{1}, …, S_{n}, one first builds the sum T of these and then extracts sets S_{i} from T with the help of the inverse image operator vimage, i.e. S_{i} = vimage in_{i} T, where in_{i} is a suitable injection.

4 Datatype Specifications

4.1 General Form

A general datatype specification in Isabelle/HOL is of the following form:

datatype (α_{1}, …, α_{h})t_{1} = C_{1}^{1} τ_{1,1}^{1} … τ_{1,m_{1}^{1}}^{1} | … | C_{k_{1}}^{1} τ_{k_{1},1}^{1} … τ_{k_{1},m_{k_{1}}^{1}}^{1}
⋯
and  (α_{1}, …, α_{h})t_{n} = C_{1}^{n} τ_{1,1}^{n} … τ_{1,m_{1}^{n}}^{n} | … | C_{k_{n}}^{n} τ_{k_{n},1}^{n} … τ_{k_{n},m_{kn}^{n}}^{n}

where α_{i} are type variables, constructors C_{i}^{j} are distinct, and τ_{i,i′}^{j} are admissible types containing at most the type variables α_{1}, …, α_{h}. Some type τ_{i,i′}^{j} occurring in such a specification is admissible iff {(α_{1}, …, α_{h})t_{1}, …, (α_{1}, …, α_{h})t_{n}} ⊢⊢ τ_{i,i′}^{j} where ⊢⊢ is inductively defined by the following rules:

• non-recursive occurrences: Γ ⊢ ⊢ τ where τ is non-recursive, i.e. τ does not contain any of the newly defined type constructors t_{1}, …, t_{n}

• recursive occurrences: {τ} ∪ Γ ⊢ ⊢ τ

• nested recursion involving function types:

{Γ ⊢ ⊢ τ \atop Γ ⊢ ⊢ σ → τ} where σ is non-recursive

• nested recursion involving existing datatypes:

\begin{aligned}\{(τ′_{1}, …, τ ′ ; h̃)t̃_{1}, …, (τ′_{1}, …, τ ′ ; h̃)t̃ñ\} ∪ Γ & ⊢ ⊢ & τ̃_{1,1}^{1} [τ′_{1}/β_{1}, …, τ ′ ; h̃/βh̃] \\ & ⋯ \\ \{(τ′_{1}, …, τ ′ ; h̃)t̃_{1}, …, (τ′_{1}, …, τ ′ ; h̃)t̃ñ\} ∪ Γ & ⊢ ⊢ & τ̃ ñ ; k̃ñ,m̃ñ ; k̃ñ [τ′_{1}/β_{1}, …, τ ′ ; h̃/βh̃] \end{aligned} ; Γ ⊢ ⊢ (τ′_{1}, …, τ ′ ; h̃)t̃_{j′}

where t̃_{j′} is the type constructor of an existing datatype specified by

datatype (β_{1}, …, βh̃)t̃_{1} = D_{1}^{1} τ̃_{1,1}^{1} … τ̃_{1,m̃_{1}^{1}}^{1} | … | D1 ; k̃_{1} τ̃_{k̃_{1},1}^{1} … τ̃_{k̃_{1},m̃1 ; k̃_{1}}^{1}
⋯
and  (β_{1}, …, βh̃)t̃ñ = Dñ ; 1 τ̃ ñ ; 1,1 … τ̃ ñ ; 1,m̃ñ ; 1 | … | Dñ ; k̃ñ τ̃ ñ ; k̃ñ,1 … τ̃ ñ ; k̃ñ,m̃ñ ; k̃ñ

It is important to note that the admissibility relation ⊢⊢ is not defined within HOL, but as an extra-logical concept. Before attempting to construct a datatype, an ML function of the datatype package checks if the user input respects the rules described above. The point of this check is not to ensure correctness of the construction, but to provide high-level error messages.

Non-emptiness HOL does not admit empty types. Each of the new datatypes (α_{1}, …, α_{h})t_{j} with 1 ≤ j ≤ n is guaranteed to be non-empty iff it has a constructor C_{i}^{j} with the following property: for all argument types τ_{i,i′}^{j} of the form (α_{1}, …, α_{h})t_{j′} the datatype (α_{1}, …, α_{h})t_{j′} is non-empty.

If there are no nested occurrences of the newly defined datatypes, obviously at least one of the newly defined datatypes (α_{1}, …, α_{h})t_{j} must have a constructor C_{i}^{j} without recursive arguments, a base case, to ensure that the new types are non-empty. If there are nested occurrences, a datatype can even be non-empty without having a base case itself. For example, with α list being a non-empty datatype, datatype t = C (t list) is non-empty as well.

Just like ⊢⊢ described above, non-emptiness of datatypes is checked by an ML function before invoking the actual HOL typedef primitive, which would never accept empty types in the first place, but report a low-level error.

4.2 Limitations of Set-theoretic Datatypes

Constructing datatypes in set-theory has some well-known limitations wrt. nesting of the full function space. This is reflected in the definition of admissible types given above. The last two cases of ⊢⊢ relate to nested (or indirect) occurrences of some of the newly defined types (α_{1}, …, α_{h})t_{j′} in a type expression of the form (…, … (α_{1}, …, α_{h})t_{j′} …, …)t′, where t′ may either be the type constructor of an already existing datatype or the type constructor → for the full function space. In the latter case, none of the newly defined types may occur in the first argument of the type constructor →, i.e. all occurrences must be strictly positive. If we were to drop this restriction, the datatype could not be constructed (cf. [6]). Recall that in classical set-theory

• there is no injection of type (t → β) ↪ t according to Cantor’s theorem, if β has more than one element;

• there is an injection in_{1} :: (t → β) ↪ ((α → t) → β), because there is an injection (λc x. c) :: t ↪ (α → t);

• there is an injection in_{2} :: (t → α) ↪ ((t → α) → β), if β has more than one element, since (λx y. x = y) :: (t → α) ↪ ((t → α) → bool) is an injection and there is an injection bool ↪ β.

Thus datatypes with any constructors of the following form

datatype t = C (t → bool) | D ((bool → t) → bool) | E ((t → bool) → bool)

cannot be constructed, because we would have injections C, D ∘ in_{1} and E ∘ in_{2} of type (t → bool) ↪ t, in contradiction to Cantor’s theorem. In particular, inductive types in set-theory do not admit only weakly positive occurrences of nested function spaces. Moreover, nesting via datatypes exposes another subtle point when instantiating even non-recursive occurrences of function types: while datatype (α, β)t = C (α → bool) | D (β list) is legal, the specification of datatype γ u = E ((γ u, γ)t) | F is not, because it would yield the injection E ∘ C :: (γ u → bool) ↪ γ u; datatype γ u = E ((γ, γ u)t) | F is again legal.

Recall that our notion of admissible datatype specifications is an extra-logical one — reflecting the way nesting is handled in the construction (see §5.4). In contrast, [23] internalizes nested datatypes into the logic, with the unexpected effect that even non-recursive function spaces have to be excluded.

The choice of internalizing vs. externalizing occurs very often when designing logical systems. In fact, an important aspect of formal-logic engineering is to get the overall arrangement of concepts at different layers done right. The notions of deep vs. shallow embedding can be seen as a special case of this principle.

5 Constructing Datatypes in HOL

We now discuss the construction of the class of inductive types given in §4.1. According to §3.3, new types are defined in HOL “semantically” by exhibiting a suitable representing set. Starting with a universe that is closed wrt. certain injective operations, we cut out the representing sets of datatypes inductively using Knaster-Tarski (cf. [17]). Thus having obtained free inductive types, we construct several derived concepts, in particular primitive recursion.

5.1 Universes for Representing Recursive Types

We describe the type (α, β)dtree of trees, which is a variant of the universe formalized by Paulson [19], extended to support arbitrary branching. Type dtree provides the following operations:

Leaf :: α → (α, β)dtree

embedding non-recursive occurrences of types

In0, In1 :: (α, β)dtree → (α, β)dtree

modeling distinct constructors

Pair :: (α, β)dtree → (α, β)dtree → (α, β)dtree

modeling constructors with multiple arguments

Lim :: (β → (α, β)dtree) → (α, β)dtree

embedding function types (infinitary products)

All operations are injective, e.g. Pair t_{1} t_{2} = Pair t′_{1} t′_{2} ⟺ t_{1} = t′_{1} ∧ t_{2} = t′_{2} and Lim f = Lim f′ ⟺ f = f′. Furthermore, In0 t ≠ In1 t′ for any t and t′.

Modeling Trees in HOL Set-theory A tree essentially is a set of nodes. Each node has a value and can be accessed via a unique path. A path can be modeled by a function that, given a certain depth index of type nat, returns a branching label (e.g. also nat). The figure below shows a finite tree and its representation.

[figure: 1; 2; 1; 2; 1; 2; a_{1}; a_{2}; a_{3}; a_{4}]  T = \{(f_{1}, a_{1}), (f_{2}, a_{2}), (f_{3}, a_{3}), (f_{4}, a_{4})\} ; where ; \begin{aligned}f_{1} & = & (1, 0, 0, …) \\ f_{2} & = & (2, 1, 0, 0, …) \\ f_{3} & = & (2, 2, 1, 0, 0, …) \\ f_{4} & = & (2, 2, 2, 0, 0, …) \end{aligned}

Here, a branching label of 0 indicates end-of-path. In the sequel, we will allow a node to have either a value of type bool or any type α. As branching labels, we will admit elements of type nat or any type β. Hence we define type abbreviations

(α, β)node = (nat → (β + nat)) × (α + bool)
(α, β)dtree = ((α, β)node)set

where the first component of a node represents the path and the second component represents its value. We can now define operations

push  :: (β + nat) → (α, β)node → (α, β)node
push x n ≡ (λi. (case i of 0 ⇒ x | Suc j ⇒ fst n j), snd n)
Pair  :: (α, β)dtree → (α, β)dtree → (α, β)dtree
Pair t_{1} t_{2} ≡ (push (Inr 1) “ t_{1}) ∪ (push (Inr 2) “ t_{2})

The function push adds a new head element to the path of a node, i.e.

push x ((y_{0}, y_{1}, …), a) = ((x, y_{0}, y_{1}, …), a)

The function Pair joins two trees t_{1} and t_{2} by adding the distinct elements 1 and 2 to the paths of all nodes in t_{1} and t_{2}, respectively, and then forming the union of the resulting sets of nodes. Furthermore, we define functions Leaf and Tag for constructing atomic trees of depth 0:

Leaf :: α → (α, β)dtree  Tag :: bool → (α, β)dtree
Leaf a ≡ {(λx. Inr 0, Inl a)}  Tag b ≡ {(λx. Inr 0, Inr b)}

Basic set-theoretic reasoning shows that Pair, Leaf and Tag are indeed injective. We also define In0 and In1 which turn out to be injective and distinct.

In0 :: (α, β)dtree → (α, β)dtree  In1 :: (α, β)dtree → (α, β)dtree
In0 t ≡ Pair (Tag false) t  In1 t ≡ Pair (Tag true) t

Functions (i.e. infinitary products) are embedded via Lim as follows:

Lim :: (β → (α, β)dtree) → (α, β)dtree
Lim f ≡ ⋃{z | ∃x. z = push (Inl x) “ (f x)}
[figure: f x_{1}; f x_{2}; …; x_{2}; x_{1}]

That is, for all x the prefix x is added to the path of all nodes in f x, and the union of the resulting sets is formed.

Note that some elements of (α, β)dtree, such as trees with nodes of infinite depth, do not represent proper elements of datatypes. However, these junk elements are excluded when inductively defining the representing set of a datatype.

5.2 Constructing an Example Datatype

As a simple example, we will now describe the construction of the type α list, specified by datatype α list = Nil | Cons α (α list).

The Representing Set The datatype α list will be represented by the set list-rep :: ((α, unit)dtree)set. Since α is the only type occurring non-recursively in the specification of list, the first argument of dtree is just α. If more types would occur non-recursively, the first argument would be the sum of these types. Since there is no nested recursion involving function types, the second argument of dtree is just the dummy type unit. We define list-rep inductively:

Nil-rep ∈ list-rep ys ∈ list-rep Cons-rep y ys ∈ list-rep

Nil-rep  ≡ In0 dummy
Cons-rep y ys ≡ In1 (Pair (Leaf y) ys)

Constructors Invoking the type definition mechanism described in §3.3 introduces the abstraction and representation functions

Abs-list :: (α, unit)dtree → α list
Rep-list :: α list → (α, unit)dtree

as well as the axioms Rep-list-inverse, Abs-list-inverse and Rep-list. Using these functions, we can now define the constructors Nil and Cons:

Nil  ≡ Abs-list Nil-rep
Cons x xs ≡ Abs-list (Cons-rep x (Rep-list xs))

Freeness We can now prove that Nil and Cons are distinct and that Cons is injective, i.e. Nil ≠ Cons x xs and Cons x xs = Cons x′ xs′ ⟺ x = x′ ∧ xs = xs′. Because of the isomorphism between α list and list-rep, the former easily follows from the fact that In0 and In1 are distinct, while the latter is a consequence of the injectivity of In0, In1 and Pair.

Structural Induction For α list an induction rule of the form

P Nil ∀x xs. P xs ⟹ P (Cons x xs)
P xs

(list-ind)

can be proved using the induction rule

Q Nil-rep ∀y ys. Q ys ∧ ys ∈ list-rep ⟹ Q (Cons-rep y ys)

ys ∈ list-rep ⟹ Q ys

(list-rep-ind)

for the representing set list-rep derived by the inductive definition package from the rules described in §3.4. To prove list-ind, we show that P xs can be deduced from the assumptions P Nil and ∀x xs. P xs ⟹ P (Cons x xs) by the derivation

…

… ⟹ P (Cons y (Abs-list ys)) … ⟹ P (Abs-list (Cons-rep y (Rep-list (Abs-list ys)))) ∀y ys. P (Abs-list ys) ∧ ys ∈ list-rep ⟹ P (Abs-list (Cons-rep y ys)) Rep-list xs ∈ list-rep ⟹ P (Abs-list (Rep-list xs)) P xs

Starting with the goal P xs, we first use the axioms Rep-list-inverse and Rep-list, introducing the local assumption Rep-list xs ∈ list-rep and unfolding xs to Abs-list (Rep-list xs). Now list-rep-ind can be applied, where Q and ys are instantiated with P ∘ Abs-list and Rep-list xs, respectively. This yields two new subgoals, one for the Nil-rep case and one for the Cons-rep case. We will only consider the Cons-rep case here: using axiom Abs-list-inverse together with the local assumption ys ∈ list-rep, we unfold ys to Rep-list (Abs-list ys). Applying the definition of Cons, we fold Abs-list (Cons-rep y (Rep-list (Abs-list ys))) to Cons y (Abs-list ys). Obviously, P (Cons y (Abs-list ys)) follows from the local assumption P (Abs-list ys) using the assumption ∀x xs. P xs ⟹ P (Cons x xs).

In principle, inductive types are already fully determined by freeness and structural induction. Applications demand additional derived concepts, of course, such as case analysis, size functions, and primitive recursion.

Primitive Recursion A function on lists is primitive recursive iff it can be expressed by a suitable instantiation of the recursion combinator

list-rec :: β → (α → α list → β → β) → α list → β
list-rec f_{1} f_{2} Nil = f_{1}
list-rec f_{1} f_{2} (Cons x xs) = f_{2} x xs (list-rec f_{1} f_{2} xs)

As has been pointed out in [8], a rather elegant way of constructing the function list-rec is to build up its graph list-rel by an inductive definition and then define list-rec in terms of list-rel using Hilbert’s choice operator ε:

(Nil, f_{1}) ∈ list-rel f_{1} f_{2}

(xs, y) ∈ list-rel f_{1} f_{2}
(Cons x xs, f_{2} x xs y) ∈ list-rel f_{1} f_{2}
list-rec f_{1} f_{2} xs ≡ εy. (xs, y) ∈ list-rel f_{1} f_{2}

To derive the characteristic equations for list-rec given above, we show that list-rel does indeed represent a total function, i.e. for every list xs there is a unique y such that (xs, y) ∈ list-rel f_{1} f_{2}. The proof is by structural induction on xs.

5.3 Mutual Recursion

Mutually recursive datatypes, such as α aexp and α bexp introduced in §2 are treated quite similarly as above. Their representing sets aexp-rep and bexp-rep of type ((α, unit)dtree)set as well as the graphs aexp-rel and bexp-rel of the primitive recursion combinators are defined by mutual induction. For example, the rules for constructor Less are:

b_{1} ∈ aexp-rep b_{2} ∈ aexp-rep

In0 (Pair b_{1} b_{2}) ∈ bexp-rep

(x_{1}, y_{1}) ∈ aexp-rel f_{1}…f_{6} (x_{2}, y_{2}) ∈ aexp-rel f_{1}…f_{6}
(Less x_{1} x_{2}, f_{5} x_{1} x_{2} y_{1} y_{2}) ∈ bexp-rel f_{1}…f_{6}

5.4 Nested Recursion

Datatype (α, β)term is a typical example for nested (or indirect) recursion:

datatype (α, β)term = Var α | App β (((α, β)term)list)

As pointed out in [6, 7], datatype specifications with nested recursion can conceptually be unfolded to equivalent mutual datatype specifications without nesting. We also follow this extra-logical approach, avoiding the complications of internalized nesting [23]. Unfolding the above specification would yield:

datatype (α, β)term  = Var α | App β ((α, β)term-list)
and  (α, β)term-list = Nil′ | Cons′ ((α, β)term) ((α, β)term-list)

However, it would be a bad idea to actually introduce the type (α, β)term-list and the constructors Nil′ and Cons′, because this would prevent us from reusing common list lemmas in proofs about terms. Instead, we will prove that the representing set of (α, β)term-list is isomorphic to the type ((α, β)term)list.

The Representing Set We inductively define the sets term-rep and term-list-rep of type ((α + β, unit)dtree)set by the rules

In0 (Leaf (Inl a)) ∈ term-rep

ts ∈ term-list-rep In1 (Pair (Leaf (Inr b)) ts) ∈ term-rep

In0 dummy ∈ term-list-rep

t ∈ term-rep ts ∈ term-list-rep

In1 (Pair t ts) ∈ term-list-rep

Since there are two types occurring non-recursively in the datatype specification, namely α and β, the first argument of dtree becomes α + β.

Defining a Representation Function Invoking the type definition mechanism for term introduces the functions

Abs-term :: (α + β, unit)dtree → (α, β)term
Rep-term :: (α, β)term → (α + β, unit)dtree

for abstracting elements of term-rep and for obtaining the representation of elements of (α, β)term. To get the representation of a list of terms we now define

Rep-term-list :: ((α, β)term)list → (α + β, unit)dtree

Rep-term-list Nil = In0 dummy

Rep-term-list (Cons t ts) = In1 (Pair (Rep-term t) (Rep-term-list ts))

Determining the representation of Nil is trivial. To get the representation of Cons t ts, we need the representations of t and ts. The former can be obtained using the function Rep-term introduced above, while the latter is obtained by a recursive call of Rep-term-list. Obviously, Rep-term-list is primitive recursive and can therefore be defined using the combinator list-rec:

Rep-term-list ≡ list-rec (In0 dummy) (λt ts y. In1 (Pair (Rep-term t) y))
Abs-term-list ≡ inv Rep-term-list

It is a key observation that Abs-term-list and Rep-term-list have the properties

Abs-term-list (Rep-term-list xs) = xs

ys ∈ term-list-rep ⟹ Rep-term-list (Abs-term-list ys) = ys

Rep-term-list xs ∈ term-list-rep

i.e. ((α, β)term)list and term-list-rep are isomorphic, which can be proved by structural induction on list and by induction on rep-term-list. Looking at the HOL type definition mechanism once again (§3.3), we notice that these properties have exactly the same form as the axioms which are introduced for actual newly defined types. Therefore, all of the following proofs are the same as in the case of mutual recursion without nesting, which simplifies matters considerably.

Constructors Finally, we can define the constructors for term:

Var a  ≡ Abs-term (In0 (Leaf (Inl a)))
App b ts ≡ Abs-term (In1 (Pair (Leaf (Inr b)) (Rep-term-list ts)))

5.5 Infinitely Branching Types

We show how to construct infinitely branching types such as (α, β, γ)tree, cf. §2.

The Representing Set tree-rep will be of type ((α + β, γ)dtree)set. Since the two types α and β occur non-recursively in the specification, the first argument of dtree is the sum α + β of these types. The only branching type, i.e. a type occurring on the left of some →, is γ. Therefore, γ is the second argument of dtree. We define tree-rep inductively by the rules

In0 (Leaf (Inl a)) ∈ tree-rep

g ∈ Funs tree-rep In1 (Pair (Leaf (Inr b)) (Lim g)) ∈ tree-rep

where the premise g ∈ Funs tree-rep means that all function values of g represent trees. The monotone function Funs is defined by

Funs :: β set → (α → β)set
Funs S ≡ {g | range g ⊆ S}

Constructors We define the constructors of tree by

Atom a  ≡ Abs-tree (In0 (Leaf (Inl a)))
Branch b f ≡ Abs-tree (In1 (Pair (Leaf (Inr b)) (Lim (Rep-tree ∘ f))))

The definition of Atom is straightforward. To form a Branch from element b and subtrees denoted by f, we first determine the representation of the subtrees by composing f with Rep-tree and then represent the resulting function using Lim.

Structural Induction The induction rule for type tree shown in §2 can be derived from the corresponding induction rule for the representing set tree-rep by instantiating Q and u with P ∘ Abs-tree and Rep-tree, respectively:

∀a. Q (In0 (Leaf (Inl a)))
∀b g. g ∈ Funs (tree-rep ∩ {x | Q x}) ⟹ Q (In1 (Pair (Leaf (Inr b)) (Lim g)))
u ∈ tree-rep ⟹ Q u

The unfold/fold proof technique already seen in §5.2 can also be extended to functions: if g ∈ Funs tree-rep, then g = Rep-tree ∘ (Abs-tree ∘ g).

Primitive Recursion Again, we define the tree-rec combinator given in §2 by constructing its graph tree-rel inductively:

(Atom a, f_{1} a) ∈ tree-rel f_{1} f_{2}

f′ ∈ compose f (tree-rel f_{1} f_{2})
(Branch b f, f_{2} b f f′) ∈ tree-rel f_{1} f_{2}

The monotone function compose used in the second rule is defined by

compose  :: (α → β) → (β × γ)set → (α → γ)set
compose f R ≡ {f′ | ∀x. (f x, f′ x) ∈ R}

The set compose f R consists of all functions that can be obtained by composing the function f with the relation R. Since R may not necessarily represent a total function, compose f R can also be empty or contain more than one function.

However, if for every x there is a unique y such that (f x, y) ∈ tree-rel f_{1} f_{2}, then there is a unique f′ with f′ ∈ compose f (tree-rel f_{1} f_{2}). This is the key property used to prove that tree-rel f_{1} f_{2} represents a total function.

Even More Complex Function Types The construction described above can be made slightly more general. Assume we want to define the datatype t, whose datatype specification contains function types σ_{1}^{i} → ⋯ → σ_{m_{i}}^{i} → t, where 1 ≤ i ≤ n. The representing set t-rep then has the type

((…, (σ_{1}^{1} × ⋯ × σ_{m_{1}}^{1}) + ⋯ + (σ_{1}^{n} × ⋯ × σ_{m_{n}}^{n}))dtree)set

The representation of a function f_{i} :: σ_{1}^{i} → ⋯ → σ_{m_{i}}^{i} → t is

Lim (sum-case \underbrace{dummy … dummy}_{i−1 times} (Rep-t ∘ ((\underbrace{uncurry ∘ ⋯ ∘ uncurry}_{m_{i}−1 times}) f_{i})) \underbrace{dummy … dummy}_{n−i times})

where

uncurry :: (α → β → γ) → α × β → γ
sum-case :: (α_{1} → β) → ⋯ → (α_{n} → β) → α_{1} + ⋯ + α_{n} → β

are injective, i.e. uncurry f = uncurry g iff f = g, and sum-case f_{1} … f_{n} = sum-case g_{1} … g_{n} iff f_{1} = g_{1} ∧ … ∧ f_{n} = g_{n}.

6 Building a Working Environment

6.1 Inverting Datatype Definitions

The hierarchy of definitional packages, as illustrated in §1, and the dependency of auxiliary theories used for the construction are often in conflict. For example, we have used basic types such as nat, α + β, α × β for the universe underlying datatypes. Any of these could be characterized as inductive types, but had to be built “manually”, because datatype had not yet been available at that stage.

Of course, we would like to keep the Isabelle/HOL standard library free of any such accidental arrangements due to bootstrap problems of the HOL logic. Note that with most types being actual datatypes — offering the standard repertoire of derived concepts such as induction, recursion, pattern matching by cases etc. — the resulting system would become conceptually much simpler, with less special cases. Furthermore, proper datatypes may again partake in indirect recursion. Users certainly expect to be able to nest types via α + β and α × β.

We propose inverted datatype definitions as an answer to the above problem. Given a type together with freeness and induction theorems, the rep-datatype mechanism figures out the set of constructors and does all the rest of standard datatype constructions automatically. Thus we avoid cycles in theory/package dependencies in a clean way. Note that the same mechanism is used internally when unwinding indirect recursion (reconsider term-list vs. term list in §5.4).

From a purely logical point of view one would probably approach bootstrap issues differently. For example, [8] provides a very careful development of the theory underlying the datatype construction, reducing the requirements to a bare minimum, even avoiding natural numbers. Interestingly the actual implementation does not fully follow this scheme, but does use natural numbers.

6.2 Cooperation of Definitional Packages

As depicted in §1, some Isabelle/HOL packages are built on top of each other. For example, record [13] constructs extensible records by defining a separate (non-recursive) datatype for any record field. Other packages such as recdef [21, 22] refer to certain information about datatypes which are involved in wellfounded recursion (e.g. size functions). We see that some provisions have to be made in order to support cooperation of definitional packages properly.

In particular, there should be means to store auxiliary information in theories. Then packages such as datatype would associate sufficient source level information with any type, such as the set of constructors, induction rule, and primrec combinator. Thus we get a more robust and scalable system than by trying to weed through the primitive logical declarations emitted by the package. Isabelle98-1 does already support an appropriate “theory data” concept.^{2}

With extra-logical information associated with logical objects, we may also offer users a more uniform view to certain general principles. For example, “proof by induction” or “case analysis” may be applied to some x, with the actual tactic figured out internally. Also note that by deriving definitional mechanisms from others, such as record from datatype, these operations are inherited. Thus case analysis etc. on record fields would become the same as on plain datatypes.

7 Conclusion and Related Work

We have discussed Isabelle/HOL’s new definitional packages for inductive types and (primitive) recursive functions (see also [2]) at two different levels of concept.

At the logical level, we have reviewed a set-theoretic construction of mutual, nested, arbitrarily branching types together with primitive recursion combinators. Starting with a schematic universe of trees — similar to [19], but extended to support infinitely branching — we have cut out representing sets for inductive types using the usual Knaster-Tarski fixed-point approach [17, 8].

Stepping back from the pure logic a bit, we have also discussed further issues we considered important to achieve a scalable and robust working environment. While this certainly does not yet constitute a systematic discipline of “Formal-Logic Engineering”, we argue that it is an important line to follow in order to provide theorem proving systems that are “successful” at a larger scale. With a slightly different focus, [1] discusses approaches to “Proof Engineering”.

The importance of advanced definitional mechanisms for applications has already been observed many years ago. Melham [12] pioneers a HOL datatype

2 Interestingly, while admitting arbitrary ML values to be stored, this mechanism can be made type-safe within ML (see also [11]).

package (without nesting), extended later by Gunter [6, 7] to more general branching. Paulson [17] establishes Knaster-Tarski as the primary principle underlying (co)inductive types; the implementation in Isabelle/ZF set-theory also supports infinite branching. Völker [23] proposes a version of datatypes for Isabelle/HOL with nested recursion internalized into the logic, resulting in some unexpected restrictions of non-recursive occurrences of function spaces. Harrison [8] undertakes a very careful logical development of mutual datatypes based on cardinality reasoning, aiming to reduce the auxiliary theory requirements to a minimum. The implementation (HOL Light) has recently acquired nesting, too.

Our Isabelle/HOL packages for datatype and primrec have been carefully designed to support a superset of functionality, both with respect to the purely logical virtues and as its integration into a scalable system. This is intended not as the end of the story, but the beginning of the next stage.

Codatatypes would follow from Knaster-Tarski by duality quite naturally (e.g. [17]), as long as simple cases are considered. Nesting codatatypes, or even mixing datatypes and codatatypes in a useful way is very difficult. While [10] proposes a way of doing this, it is unclear how the informal categorical reasoning is to be transferred into the formal set-theory of HOL (or even ZF).

Non-freely generated types would indeed be very useful if made available for nesting. Typical applications refer to some type that contains a finitary environment of itself. Currently this is usually approximated by nesting (α × β) list.

Actual combination of definitional packages would be another important step towards more sophisticated standards, as are established in functional language compiler technology, for example. While we have already achieved decent cooperation of packages that are built on top of each other, there is still a significant gap towards arbitrary combination (mutual and nested use) of separate packages. In current Haskell compilers, for example, any module (read “theory”) may consist of arbitrary declarations of classes, types, functions etc. all of which may be referred to mutually recursive. Obviously, theorem prover technology will still need some time to reach that level, taking into account that “compilation” means actual theorem proving work to be provided by the definitional packages.

References

[1] H. P. Barendregt. The quest for correctness. In Images of SMC Research, pages 39–58. Stichting Mathematisch Centrum, Amsterdam, 1996.

[2] S. Berghofer. Definitorische Konstruktion induktiver Datentypen in Isabelle/HOL (in German). Master’s thesis, Technische Universität München, 1998.

[3] A. Church. A formulation of the simple theory of types. Journal of Symbolic Logic, pages 56–68, 1940.

[4] C. Cornes, J. Courant, J.-C. Filliâtre, G. Huet, P. Manoury, and C. Muñoz. The Coq Proof Assistant User’s Guide, version 6.1. INRIA-Rocquencourt et CNRS-ENS Lyon, 1996.

[5] M. J. C. Gordon and T. F. Melham (editors). Introduction to HOL: A theorem proving environment for higher order logic. Cambridge University Press, 1993.

[6] E. L. Gunter. Why we can’t have SML style datatype declarations in HOL. In L. J. M. Claesen and M. J. C. Gordon, editors, Higher Order Logic Theorem Proving and Its Applications, volume A-20 of IFIP Transactions, pages 561–568. North-Holland Press, 1992.

[7] E. L. Gunter. A broader class of trees for recursive type definitions for HOL. In J. Joyce and C. Seger, editors, Higher Order Logic Theorem Proving and Its Applications, volume 780 of LNCS, pages 141–154. Springer, 1994.

[8] J. Harrison. Inductive definitions: automation and application. In P. J. Windley, T. Schubert, and J. Alves-Foss, editors, Higher Order Logic Theorem Proving and Its Applications: Proceedings of the 8th International Workshop, volume 971 of LNCS, pages 200–213, Aspen Grove, Utah, 1995. Springer.

[9] J. Harrison. HOL done right. Unpublished draft, 1996.

[10] U. Hensel and B. Jacobs. Proof principles for datatypes with iterated recursion. In E. Moggi and G. Rosolini, editors, Category Theory and Computer Science, volume 1290 of LNCS, pages 220–241. Springer, 1997.

[11] F. Kammüller and M. Wenzel. Locales — a sectioning concept for Isabelle. Technical Report 449, University of Cambridge, Computer Laboratory, October 1998.

[12] T. F. Melham. Automating recursive type definitions in higher order logic. In G. Birtwistle and P. A. Subrahmanyam, editors, Current Trends in Hardware Verification and Automated Theorem Proving, pages 341–386. Springer, 1989.

[13] W. Naraschewski and M. Wenzel. Object-oriented verification based on record subtyping in higher-order logic. In J. Grundy and M. Newey, editors, Theorem Proving in Higher Order Logics, volume 1479 of LNCS. Springer, 1998.

[14] T. Nipkow and D. von Oheimb. Java_{ℓight} is type-safe — definitely. In Proc. 25th ACM Symp. Principles of Programming Languages. ACM Press, New York, 1998.

[15] S. Owre, S. Rajan, J. M. Rushby, N. Shankar, and M. Srivas. PVS: combining specification, proof checking, and model checking. In R. Alur and T. A. Henzinger, editors, Computer Aided Verification, volume 1102 of LNCS. Springer, 1996.

[16] S. Owre and N. Shankar. Abstract datatypes in PVS. Technical Report CSL-93-9R, Computer Science Laboratory, SRI International, 1993.

[17] L. C. Paulson. A fixedpoint approach to implementing (co)inductive definitions. In A. Bundy, editor, Proceedings of the 12th International Conference on Automated Deduction, volume 814 of LNAI, pages 148–161, Nancy, France, 1994. Springer.

[18] L. C. Paulson. Isabelle: A Generic Theorem Prover, volume 828 of LNCS. Springer, 1994.

[19] L. C. Paulson. Mechanizing coinduction and corecursion in higher-order logic. Journal of Logic and Computation, 7(2):175–204, 1997.

[20] F. Pfenning and C. Paulin-Mohring. Inductively defined types in the Calculus of Constructions. In Proceedings of Mathematical Foundations of Programming Semantics, volume 442 of LNCS. Springer, 1990.

[21] K. Slind. Function definition in higher order logic. In J. Wright, J. Grundy, and J. Harrison, editors, 9th International Conference on Theorem Proving in Higher Order Logics, TPHOLs’96, volume 1125 of LNCS. Springer, 1996.

[22] K. Slind. Derivation and use of induction schemes in higher-order logic. In 10th International Conference on Theorem Proving in Higher Order Logics, TPHOLs’97, volume 1275 of LNCS. Springer, 1997.

[23] N. Völker. On the representation of datatypes in Isabelle/HOL. In L. C. Paulson, editor, First Isabelle Users Workshop, 1995.

[24] M. Wenzel. Type classes and overloading in higher-order logic. In 10th International Conference on Theorem Proving in Higher Order Logics, TPHOLs’97, volume 1275 of LNCS. Springer, 1997.