A Theory of Inductive Definitions With -equivalence:
Semantics, Implementation, Programming Language.
A PhD thesis by Murdoch J. Gabbay, 10 August 2000.
DPMMS and Trinity College,
Cambridge University, England.
This document was compiled from source on 10 August 2000. Copies will be printed, bound, and submitted for the title of PhD in Mathematics from Cambridge University, England. Other copies will be passed to those interested. Those interested are invited to write to me at Trinity College, Cambridge, or e-mail m.j.gabbay@dpmms.cam.ac.uk.
I remind the reader that my examiners may well suggest corrections to this document so it need not necessarily be the final version of my thesis. If the reader is wondering, DPMMS stands for the “Department of Pure Maths and Mathematical Statistics”.
Other work published on this field is [66] and [18]. See also the homepage of Andrew Pitts, [68].
c Copyright Murdoch J. Gabbay, August 2000.
FOR THE LAYMAN: If you are not a layman I would not read this; the same things are said better in 1. Otherwise, and if you want to know what this pamphlet is about, read on. When we calculate, the representation we choose for the objects we calculate with makes a big difference. E.g. consider numbers; 1 2 3 . Arithmetic using roman numerals is much harder than in base ten. There are many other representations, all good for different purposes; computers do base two better than base ten so microchips do binary arithmetic.
Numbers are a powerful tool. Another such tool is language (imagine this thesis without it). How do we represent sentences of a language? We can use a pen to write just as we can use our fingers with base ten. How about computers? Current theories of syntax on computers have problems. The reader might take the obvious inspiration from word processors and suggest representing sentences as strings of ASCII characters, but this is kludgy because it does not allow immediate access to the grammatical structure of the sentence (just as roman numerals do not seem in practice to allow immediate access to the arithmetic structure of numbers). There are many better representations, but all seem to suffer from problems with what I shall call, without explanation ‘variable binding’.
I present a new theory which allows us to represent languages with variable binding. In fact the presentation of the theory is 60 pages at most. The rest of this document tries to show that it works.
So: why is this thesis interesting? Considering how much we humans use languages, anything that lets computers (and us humans) manipulate them better is a Good Thing.
To Jim and Andrew, and to Cambridge, where anyone can learn anything.
Contents
Chapter II. Semantics: FM set theory25
8.2. Semantics of syntax in ZFA32
9.3. Calculating Supp for particular sets37
10.2. Initial algebras for binding signatures61
11.1. Name-for-name substitution82
11.2. Significance of ‘for free’83
11.3. Restricted set of permutations84
12. Inductive reasoning in FM89
12.2. Inductive reasoning on the syntax of FMLtiny91
13.1. Advanced theory of Supp98
Chapter III. Implementation: Isabelle/FM101
15.1. Axioms and Constants of Isabelle/ZFQA105
15.4. Discussion of foundation112
15.5. Further discussion of foundation114
16.1. The theory of Isabelle/FM120
16.11. The theory of finite sets136
18.1. Meta-level types of atoms139
18.2. Restrict permutation to types of atoms only141
18.3. Extend permutation to function types142
19. The -calculus in Isabelle144
19.2. Discussion of Term.ML148
20. Future work: Releasing Isabelle/FM as a tool153
Chapter IV. Programming Language: FreshML157
26. Bisimulation and Contextual Equivalence190
26.3. The Equivalence and the Relation 194
27. Proof of and hence congruence206
29. The Sanity Clause, proved221
30.2. Combine typing and apartness?222
30.3. Incorporate apartness into types?222
30.4. Define # ‘co-inductively’?223
32.1. FM’s great problem: inaccessible228
33. Other approaches and the literature231
33.6. Fiore, Plotkin and Turi241
33.7. The axiomatic approach242
34. Accomplishments of this thesis243
Chapter I
Introduction
1. First words
This thesis is about inductive structures with -conversion.
By ‘inductive structures’ I mean the whole ensemble of (co)inductively defined sets1, datatypes, and (co)inductive reasoning on them.
Inductive structures are ubiquitous, part of the basic toolkit of modern computer science. We see them in the abstract syntax of formal languages of all kinds, models of computer circuits ([48], the gates plug circuits together to form new circuits just like term-formers plug terms together to form new terms), constructive theories of finite sets (see [59, 2.9.2, p.58]), datatypes in programming languages, lists, queues and natural numbers in mathematical theory, evaluation and transition relations in operational semantics, typing judgements on formal languages, labelled transition systems in process algebras, theories of bisimulation, and so on. Inductive structures have even been made the basis of an underlying universe in CIC (the Calculus of Inductive Constructions, [9],[77]), with great success.
Why do we do this? Because it is useful. If we have an inductively defined set we have a set with a well-defined inductive reasoning principle, one which furthermore is easily generated on a computer in an automated manner. There are many different flavours but the basic recipe is the same: structural induction, pattern-matching, primitive recursion, recursion, coinduction, and so on.
Given this, is it not surprising that the world has continued turning while datatypes of abstract syntax, and thus all inductively defined structures arising from them, are not particularly amenable to inductive treatment? I discuss how this is so in 4 below.
In this document I present a novel solution to the problem of abstract syntax with variable binding. The solution, which I shall henceforth call ‘FM’, seems to offer significant advantages in simplicity and power over currently existing tech-nology.
Before I get into maths, I make a few general comments about this document.
1. Provenance of the material. My thesis is the product of three years working with Andrew Pitts [68] in the Computer Laboratory of Cambridge University. It is divided into five parts of which Chapter I and Chapter V are the introduction and conclusion. Chapter II, Chapter III and Chapter IV are devoted respectively to the ‘semantics’, ‘implementation’ and ‘programming language’ of the title.
Pitts and I developed the material presented in Chapter II and Chapter IV together, I was entirely on my own in Chapter III. Roughly speaking, these three sections took me a year each.
2. Notation. I have typeset new definitions and other pertinent information in bold font. Read this: To make it a little easier to find equations (some of which are named, not numbered) I have labelled references to them with the page on which the equation appears: (Fresh)35, (204)205. Similarly for footnotes and figures: ft211,2 Fig.226.
I found 3 had trouble typesetting references to lemmas, theorems and the like. They were too long and caused line overruns. So I shortened them. Thus R14.6 means ‘Remark 14.6’. Similarly ‘L’ means ‘Lemma’ as in L8.1.4, ‘T’ means ‘Theorem’ as in T21.9, ‘C’ means ‘Corollary’ as in C9.2.9, and ‘N’ means ‘Notation’ as in N9.2.8. ‘Fig.’, ‘p’ and ‘ft’ stand for ‘Figure’, ‘page’ and ‘footnote’ respectively.
All of theorems, corollaries, lemmas, remarks, and so on—for this paragraph call them all ‘theorems’—are numbered consecutively within subsections as ‘Section.Subsection.Theorem Number’; thus T3.14.15 is the fifteenth theorem of the fourteenth subsection of section three. Sections are numbered consecutively not within chapters. Before the first subsection of a section deems the subsection number to be zero (and if there is no subsection in a section, the subsection number is zero throughout it). In this case the zero is dropped; thus T3.14 denotes the fourteenth theorem of section three, which does not occur in a subsection.
3. Abuses of grammar and language.
I have used the ‘remark’ environment (e.g. R1.1) to number important paragraphs so I can refer to them later. In this I may have abused English, since my ‘remarks’ are not necessarily ‘asides’. In reflection of this grand stature and to make scoping clear, I typeset a symbol at the end, like this: 3
4. Underlying universe. I shall mostly use sets and a little bit of category theory to develop the ‘FM idea’—thus Chapter II introduces a set theory and interprets datatypes of syntax with binding as initial algebras in the corresponding category of sets. This is merely because I found the simplest presentation to be as sets and I do want my presentation to be simple. No mathematical or ideological commitment is implied. E.g. a dependently typed version of FM is an obvious target for future work (35).
2. Thanks
The two heroes of the drama which has been my PhD studies are without doubt Jim Roseblade and Andrew Pitts. Jim taught me ring theory as an undergraduate and has been not only a gracious teacher and friend over the past seven years, but also very useful. He put me in touch with Andrew Pitts. Without Jim, what the reader has before them would most probably not exist. For that and a great deal more, I thank him.
Andrew has been my teacher for the past three years, and he has been a good one. I am a demanding student and I have imposed on him more than I had a ‘right’ to. He never complained, on the contrary, his attention has been positively lavish. When I told him how I appreciated this he accepted the thanks but pointed out that he is unusually interested in the material of this thesis and therefore gave it particular attention. I think this need not change my gratitude in the slightest.
Other people who have taken significant time and trouble over me are: Martin Hyland for getting me the PhD position and keeping my set theory honest. Larry Paulson whose matter-of-fact willingness to help, when he could, has sometimes verged on the surreal (Larry also sent me style and files which were useful producing this document). Tobias Nipkow for a very pleasant and informative correspondence including but not limited to Isabelle. John Harrison and Konrad Slind for discussing HOL and theorem-proving systems with me. Randy Pollack for our discussions on LEGO and my implementation. Tom Forster for discussing set theory with me. All these people deserve respect for their knowledge, and I thank them for sharing it with me. But they also displayed an interest for my work which did as much good for my soul as the knowledge they imparted did for this document. To these people and some others I have not named, thank you.
I would also like to thank—again—Andrew Pitts, Larry Paulson, Tobias Nipkow and Martin Hyland, this time for reading and commenting on sections of the thesis. I have considered all and acted on nearly all their suggestions. I hope they will not hold the difference against me.
3. Aims and target group
I have invented something new. Above all this document must be a thesis presenting this novel work for a PhD degree, but I have tried also to accommodate the following design aims:
1. I want to disseminate knowledge of my invention in the hope that people will use it. I have tried to keep things readable.
2. My target group is computer scientists, not necessarily theoretically inclined. Thus I assume familiarity with functional programming languages, in particular ML ([57], [54]). I do not assume knowledge of set theory4, category theory, or any other underlying universe except where this is absolutely necessary.
3. Working against this is the fact that as a PhD thesis this document is expected to include for future reference the details of proofs too malignant to inflict upon the readerships of journals.
4. FreshML, first pass
This section tries to put the rest of the thesis in context by showing what the general ideas and problems are, and informally describing the kind of solution FM proposes.
In Chapter IV we design an ML-like programming language FreshML with facilities for handling datatypes of abstract syntax with variable binding.5 FreshML is designed using FM set theory, described in Chapter II. Here I motivate both by discussing the problems they address. Other solutions include de Bruijn indices and Higher Order Abstract Syntax (HOAS) but a discussion of them would disturb the flow of the development and has its own section 33.
Consider two datatypes:
Observe that Nat and ONat have identical semantics , the set of natural numbers.6
If their semantics are identical, what’s the difference between them? It lies in the programs we can write, or put another way the functions we can define out of them. For example it is a little harder to define xx oNat than it is on Nat:
On the other hand, it’s a little harder (barely) to define the predicate “is even” on Nat:
When we design programs to manipulate datatypes our first design choice is the datatype’s structure. A good one makes programs easy to write. A bad one can make them almost impossible.
We now try to construct the syntax of the untyped -calculus.
We declare in our informal language:
So (semi-formal) typing rules for forming values are:
Can we define substitution subst1:lam1*Nat*lam1->lam1, which given arguments t2,x,t1’ calculates the syntax obtained by substituting t2 for x in t1’?
The problem, and it is a familiar one, is variable capture. In the third clause we cannot blindly replace every x in s by t because it may be that there are occurrences of y in t that would be wrongly ‘captured’ by the outermost binder Lam1(y,-). Let us consider an example of this in abstract terms:
So what is [yx]yx? The traditional response is
“[yx]yx is equal to y where is any variable symbol that isn’t equal to y.”
This should give us pause for thought for two reasons. Firstly we’re having trouble defining the substitution function on our datatype lam1. Maybe we somehow have the wrong datatype. Secondly, do we really not care what is? If so evaluation is nondeterministic.
We now abandon our pseudo-programming-language and consider just the underlying semantics of the datatypes in question. As commented in ft613 we ignore the complexities of real programming languages and consider a very simple semantics in sets. The semantics of lam1 is therefore a set which we shall write
(2) lam1 X Var1 of App1 of X X Lam1 of X
This is notation for the set built up using only the rules
We have a fairly free choice for Var1, App1 and Lam1 so long as they are injective and pairwise disjoint on the set-universe, meaning that (for example) App1(x y) Lam1(u t) for all sets x y u and t. Reasonable choices would be Inl(), Inr(Inl()) and Inr(Inr()) where xInl(x) and xInr(x) are left and right injection functions into set disjoint sum implemented perhaps as x(x) and x(x). We go into no more detail on the matter. We construct such sets in 10.2. 3
We now have two objects associated to a term t:lam1:
1. The syntax of the term itself, t, which for this document is an abstract syntax tree in a computer or other external universe.
2. Its semantics in the set lam1, written [[ t ]] or just t.
There is a third object floating around which I shall call the denotation of t. We build our datatypes to reflect in a formal framework entities taken from nature. In the case of lam1 we are trying to capture the untyped -calculus, so the denotation of Lam1(a,Var1(a)) is the function aa living “in nature”. 3
We shall adhere to the following convention:
We use typewriter font for syntax like lam1 and App1(Var1(a),Var1(a)). We write their set-theoretic semantics/implementations [[ lam1 ]] or lam1.
In summary, we have syntax written Lam1(a,Var(a)), semantics written Lam1(a,Var1(a)), and denotation written aa.
The standard terminology for these three objects can be confusing. The denotational object containing aa and aba, in other words the untyped -calculus, is routinely called “the syntax of the untyped -calculus”. It is completely different from the syntax of terms of the datatype lam1. To complete the confusion, the set lam1 is often referred to as a “set of syntax”. But really the same situation exists with, say, the number two, which exists as (at least) three things: arithmetic expression 2 (syntax), set (semantics), and the number 2 (denotation). 3
The semantics of lam1 is not lam1, it is lam1. This is one reason we have trouble defining substitution on it. We need a datatype with semantics lam1. But also remember the example of Nat and oNat: it is certainly necessary that the semantics of our datatype be isomorphic to lam1, but in addition it must be defined with an inductive structure that allows us to write the programs we wish to write.
Many realisations of such datatypes exist in the literature, see 33. As promised at the beginning of the section we concentrate on FreshML here.
The solution we propose is this: we introduce into the language a new ‘type of atoms’ written Atm. It has no term-formers so all values of type Atm are variables x. The intended semantics [[ Atm ]] is an infinite set of distinct symbols with no internal structure which we shall usually write . They are meant to represent variable symbols but to avoid confusion with the variable symbols of the overlying language we call them atoms. We let ourselves compare atoms for equality and make Atm an equality type so we have the term-forming rule
Now we introduce a type former “abstraction type of X” written [Atm]X. The rule for forming terms of type [Atm]X is
The intended semantics of a.t is “[[ t ]] with the atom [[ a ]] bound”, the intended semantics of [Atm]X is “the set of a.t for a:Atm and t:X”. Whatever these really are, we write them at and []X so that [[ a.t at and [[ [Atm]X]X .
Consider what this means for the type [Atm]Atm. Terms of it are pairs (a,b) written a.b. Their semantics are more subtle. Suppose a,b and c are variables of type Atm representing pairwise distinct atoms in [[ Atm ]] , write them a b and c. Then aa is supposed to be a with a bound, so it is equal to bb and cc. ac is c with a bound. Because a c and b c this is equal to bc but not equal to cc. This behaviour is precisely that of -terms, where aa, bb and cc are all equal up to -equivalence, and distinct from ac and bc, which are equal.
Now consider another version of a datatype for the -calculus:
We declare in our informal language:
(We shall repeat this rigorously in D10.3.4.) So (semi-formal) typing rules for values of this type are
Comparing (1)14 and (5)17 we see the difference is in Lam1 and Lam2. It makes little difference to the syntax of the language: values of type [Atm]lam2 are by (4)16 precisely a.V for V:lam2. The values of lam2 are in 1-1 correspondence with those of lam1, we just write Lam2(a.t) instead of Lam1(a,t). The semantics are different. Equalities like aa bb mean that lam2 ‘quotients itself’ by -equivalence as it is built (cf. D10.3.4). 3
Since the semantics of Lam2(a.a) and Lam2(b.b) are equal we expect them to be contextually equivalent. Our language is unformalised so we cannot pursue this question further here. We return to it in Chapter IV and in particular T21.9. 3
Instead, let us consider some examples of how we can use the apparatus we have already assembled to write some programs.
Here variables of abstraction type have names tagged with a ’ for easy identifica-tion. This code says
1. An abstraction Lam2(t’) evaluates to itself.
2. To evaluate App2(t1,t2), evaluate t1. If it does not evaluate to an abstraction Lam2(s’) raise an exception. If it does, substitute t2 for the distinguished bound variable of s’ and proceed with evaluation.
So subst2:lam2*[Atm]lam2->lam2 should have semantics a function that substitutes a term for the distinguished bound atom of an atom-abstracted term.
Recall the typing of subst1 as lam1*Nat*lam1. That function carries out capture-avoiding substitution t for a in s. We could formulate a function subst2’:lam2*Atm*lam2 along similar lines, but since we now have abstraction types we might as well use them.
We can implement subst2 as follows:
We declare a function subst2 in our informal language as follows:
This declaration brings us to the question of patterns of abstraction type. They are of the form
It is usual to only allow linear patterns (patterns such that each variable symbol x appears at most once) so as not to make all types equality types by the back door, e.g. consider this false polymorphic declaration:
FALSE fun eqfun (x,x) => true
| eqfun (x,y) => false; We now relax this restriction and admit nonlinear patterns on the condition that the nonlinear variables are typed as Atm. Since Atm is intended to be an equality type is this not a problem.
We also place a ‘freshness’ or ‘newness’ condition on the a in the pattern a.p. We can think of it as meaning
“When inventing a name for a bound atom, we may as well choose a completely fresh one. So when we pattern-match some atom-abstraction against a.p we can assume a is not free in anything else in the context at the time we choose it.”
3
This is reminiscent of Barendregt’s ‘variable convention’, see [1]. He is working in ZF and instructs the reader to assume that names of bound and free names of variables are distinct. The idea there being, as here, that “we might as well”. However, the slogan above is more than just a convention because it occurs in the rigorous context of a new set theory. We make the idea of “choose a fresh atom” rigorous via the quantifier in 9.4. See also R12.3.2, which restates R4.12 rigorously. We shall also see a mechanism allowing programmers to explicitly insist that an atom be chosen fresh in FM (fresh a t, see C9.6.7) and later in FreshML (fresh a in t, see 22.1).7
We can now read subst2 as follows: the name of the variable for which to substitute t is passed to subst2 bound and therefore nameless. The pattern-matching at abstraction types in each clause in the definition of subst2 creates a new name a for this bound variable. Then the clauses read:
1. The ‘freshness’ condition (R4.12) means that a and b can be assumed nonequal, so return Var2(b).
2. If a is the variable under Var2, output t.
3. Substitution distributes over application.
4. Choose an entirely new name for the other bound variable b, take the resulting inner term t and substitute in it for a as shown.
Compare lam2, subst2 and eval2 above with the corresponding definitions term, and betaapply, see Fig.120, which are at the heart of Isabelle98-
1. term is a -calculus but implemented in de Bruijn style and not the naïve datatype of lam1. It is also a typed and with some bells and whistles so the comparison between it and lam1 or lam2 is not direct. Nevertheless, the definition of requires three ancillary functions where subst2 is defined directly.
We are now ready to construct an underlying universe within which to give all this a rigorous semantics. We shall call it FM set theory (cf. Item 4 on p.11). It contains a set of atoms intended to model the type of atoms Atm (see p.16) along with axioms to make sense of the abstraction types [Atm]X (see p.16). And there will be more, such as a new term-former fresh (C9.6.7) and a new quantifier (D9.4.2). 3
I shall refer to a treatment of syntax as ‘name-carrying’ when we deal with terms containing names of bound variables. Thus for example in D4.2 we build a set of syntax lam1 of
the -calculus and interpret the abstraction type as Nat*X or Atm*X. That was a name-carrying representation. Things can get a little ambiguous: we might class lam1 (R4.7) as name-carrying even though terms are quotiented by -equivalence. The reason is that the structure of the quotient set forces us to take representatives most of the time we want to prove anything useful.
Because FM datatypes of syntax are up to -equivalence and do not contain the names of bound variables, I shall call them ‘nameless’ or (of course) ‘FM’. This is accurate but misleading because FM allows us to give bound variables names at will. We saw this for example in the last clause of D4.11 where we invent the name b for a bound variable in an abstraction b.s. I shall call this ‘ZF-style’ or, following a suggestion by Pitts, ‘nameful’ reasoning. Thus the slogan is
FM has nameless terms but permits nameful reasoning on them. We continue this discussion after we develop FM, see R12.1.3 and later on R32.1.3. The first concrete illustration of the slogan above is in R12.4.1.
Of course, the original nameful reasoning arises when the datatype is of (standard ZF) name-carrying terms like lam1 (D4.2), cf. 33.4. 3
5. A brief resumé of
This section is not an overview of the thesis as such, for that see 6 below. I have informally discussed what this thesis is about in 4. Now, in this section, I try to give my reader some idea of what the rigorous mathematics to follow looks like without said reader having to read said rigorous mathematics in full.8
5.1. FM-logic.
FM-logic is First Order predicate Logic (FOL)—not a particular FOL though I assume my FOL to be classical and typed—augmented to facilitate reasoning about syntax with binding. FM-logic is extended with one or more types of atoms, write one of them (D8.1.1) as an example. Types of atoms are intended to represent variable symbols in the underlying syntax. We may need many of them because the underlying language may have many types of variables (type variables, term variables, even sets of constant symbols, etc, see R16.1.2.).
FM-logic is also augmented with a quantifier (D9.4.2), used as follows:
The reading of this is “for all/some new atom(s) a, (a) holds”. ‘All’ will be called the ‘universal’ reading of . ‘Some’ will be called the ‘existential’ reading of (T9.4.6, R9.4.10).
Note that ‘new’ and ‘fresh’ are used synonymously. So we shall also read the formula above as “for all/some fresh atom(s)”.
By the universal reading we have that distributes over conjunction. By the existential reading we have that distributes over disjunction. Combining the two readings we have that even commutes with negation and therefore implication. Thus commutes freely with the propositional part of FOL (C9.4.5, C9.4.11). interacts less trivially with the predicate part of FOL (R9.4.12).
seems to be unique to FM, I am not aware of it or anything like it in other approaches to syntax with binding—the notable exception being Pollack’s work (33.5), in which the spirit of is very visible. It is mostly through that FM gains its particular ‘personality’. really is astonishingly well-behaved, and as a direct result of that the treatment of binding in FM comes out particularly clean and easy.
The down-side to is that, being unique to FM, the reader will not recognise it. Some people take this as a threat; “the simple things were discovered long ago, so if I don’t recognise it, it’s complicated”. This is not the case, this thesis is elementary mathematics. Technical in places, as it must be, but elementary nonetheless.
5.2. FM-sets.
It is FM set theory constructed in Chapter II which gives and FM-logic a rigorous semantics (as assertions about FM sets). In particular of course has a semantics which ‘justifies’ it and puts it in the context of a variety of set-operators, including a permutation action (D8.1.8) and Supp and # (N9.2.4).
FM set theory has abstraction types []X (D9.6.1). They play the same rôle as Plotkin’s (33.6), X in de Bruijn, X in name-carrying (R4.14) representations, and X or X X in HOAS. []X has one term-former at (D9.5.1) which takes a term t and atom a and creates a term t at which is t with the name of the variable symbol a ‘bound’. It genuinely is bound in the sense that, for one simple example aa bb [] are identical sets. Throughout this document we label abstractions with a star as in “x ax []X ” (N9.5.3). FM also provides a destructor @ (D9.5.14) which takes an abstraction t and an atom a and returns t@a, which is the term obtained by giving the bound variable in t the name a.
[]X displays particularly nice algebraic properties similar to (and inherited from) those of . It commutes (up to set-isomorphism) with product X Y , disjoint sum X Y and function types X Y (C9.6.9).
At this point everything comes together and we build quite an extensive theory of datatypes-with-binding in FM sets (10). The datatypes obtained have nameless terms because of the way []X destroys the name of abstracted atoms. However, we can obtain ordinary-looking inductive principles (e.g. (45)68) by using and @ to choose new names for the bound atoms and thus manipulate these nameless terms as if bound variables did have names. The good behaviour of makes it work.
Incidentally, we can move from FM-logic to FM-programming. We introduce a term-former fresh used as fresh a f (a) (C9.6.7). This invents a new name a and uses it to calculate f (a). The choice of a is supposed to be arbitrary so we insist for fresh a f (a) to be well-formed that x be bound in f (x). and fresh are connected by (32)52.
In the course of this thesis we actually devote a lot of attention to this nascent programming language. An informal discussion is in 4. The various term-formers are given rigorous (and sometimes technical) set-theoretic semantics throughout Chapter II some of which I have just referenced. We also see many examples of programs in 22.2 and 24.2. Of course all of Chapter IV is devoted to a particular programming language FreshML.
I discuss inductive reasoning in FM in a relatively nontechnical but still rigorous way in 12.
6. Overview of thesis
I conclude Chapter I with an ‘overview of the thesis’. This section is nothing more than a systematic annotated table of contents.
In 4 I discuss the problem this thesis addresses and introduce an informal ML-like language designed to motivate the rest of the document. In 5 I resumé a few of the more technical details of the solution. Finally, in this section, I give an overview of the thesis, section by section.
In Chapter II I introduce FM set theory. It is based on an underlying set theory ZFA (see 8) extended with an extra axiom (Fresh)35 which turns ZFA into FM (see 9). In 10 I discuss datatypes of syntax with binding by constructing a rigorous framework for declaring and building them in FM. In 11 I pause to ask a few questions about why I did things in the way I did. In 12 I return to the theme of datatypes and use 10 to build a datatype for a (deliberately) trivial programming language. I then use it as a concrete example with which to illustrate inductive reasoning on datatypes with binding. Finally in 13 I tie up a few loose ends.
In Chapter III I discuss my Isabelle implementation of FM sets, Isabelle/FM. In its gross structure Isabelle/FM mirrors FM set theory. It is constructed as Isabelle/ZFQA (15) extended with an extra axiom to full Isabelle/FM (16). The two sections are very different because the first concerns re-engineering an existing theory, and the second constructing one from scratch. In 17 I discuss one or two simple ideas which helped me control and efficiently use the Isabelle system. In 18 I discuss some ideas that did not work, and why. In 19 I discuss one of my attempts to use Isabelle/FM to declare a real datatype with binding and how well it worked. In 20 I summarise the snags remaining in Isabelle/FM and explain how to eliminate them.
Chapter IV concerns the design of a programming language with datatype declarations and associated term-formers and destructors allowing programming with syntax with binding. A design of an industrial strength ready-to-use language is not given, that is a topic of future research. Instead I introduce a much simpler language FreshML, designed to be amenable to a rigorous theoretical analysis and in particular a proof of a technical correctness result T21.9. The syntax is defined in 22.1 and some reasonably nontrivial programs expressed using it in 22.2. Typing judgements are developed in 23 and 24. A big-step evaluation judgement is introduced in 25. This all lays the groundwork for 26, 27 and 28, which between them define notions of operational and contextual equivalence and prove them equal. Note that 26.6 gives an overview of the whole proof from about one-third of the way in. After all that, it is easy in 29 to restate and prove our correctness result. 30 records the reasons for some of my design decisions and 31 discusses how all of Chapter IV could (and should) be automated using Isabelle/FM.
Chapter V reviews some of the problems of FM (32), compares FM to other approaches to syntax with binding (33), describes what I see as the main accomplishments of my thesis (34), and concludes with a ‘to do’ list (35).
Chapter II
Semantics: FM set theory
7. Introduction
FM set theory is similar to ZF set theory except in so far as it is different9, which is not terribly far. It will in due course provide semantics for all the phenomena discussed in 4. The underlying logic of FM set theory is identical to that of ZFA, ZF set theory with atoms10, so we start with that.
8. ZFA set theory
8.1. Axioms of ZFA.
We may write “x is -related to y” meaning ‘x y’.
Of the rules in Fig.226 only (AtmInf)26 is unusual.
(X ) is the set of finite subsets of X defined by induction using two rules
Throughout this document the meaning of “x is a finite set” is precisely “x (x)”. This is in fact equivalent in ZFA and later in FM to “x is in bijective correspondence with a subset of the natural numbers”, proof omitted. These issues are important because FM set theory (9) lacks AC (11.4).
So (AtmInf)26 insists that is not in its own own set of finite subsets.11 Otherwise the theory is standard. clearly corresponds to the ‘type of atoms’ Atm mentioned on p.16. Here are some of its properties:
Atoms a have no -related elements; they are empty. There is a unique empty set which is not an atom. This is the empty set .
Some distinguish two classes in the underlying model: ‘Atoms’ which are elements of , and ‘Sets’, which are everything else. I disapprove. In this document all elements of the underlying model of a set theory are ‘sets’, including elements of which are also called ‘atoms’. Thus atoms are sets. 3
Write for the ZFA universe over which variables in ZFA logic range when functions and predicates are given semantics on a particular model. I shall write even when no such semantics is in sight because the notation is useful. For example, we can now write “x ” for “x a set” and F : for a function-class from ZFA sets to ZFA sets.13
The following remark sketches some pure set theory which the reader can safely ignore if he or she wishes.
Using the axioms of ZFA we can construct a function-class V : Ordinals such that
This is the cumulative hierarchy inside ZFA. We can also prove the proposition
Thus is provably equal to the class V () constructed using ZFA on it and in that sense we can say
“A model of ZFA looks like a standard cumulative hierarchy from within ZFA.” This hereby entitles the reader to do the same. V () is usually called the th stage of the cumulative hierarchy and written . 3
We shall do a similar thing when we consider FM, see R9.1.7.
Call the set of permutations of by the name . We can extend the action to all sets in a standard way by distributing over the -structure of sets. The principle of -induction in ZFA ensures this definition is sensible:
(The second clause is subsumed by the third.) We shall see in due course that we shall mostly be concerned with the case a transposition (a b).
For x ) write x for ().
This is a fundamental property of ZFA:
Informal proof. From the construction of the permutation action D8.1.8 we can prove that and for all u v, u v u v. Because the action is permutative and therefore injective we can prove u v u v. This covers all the symbols of the language of ZFA that take arguments. We now argue by induction on the syntax of the language that for each we could produce a proof of (6)28.
This is a ‘meta-result’; it is not and cannot be proved in the logic of ZFA because it works by induction on that logic’s syntax. Its validity is mostly independent of the particular axioms of the set theory; it is a property of the language and will still hold when we add an axiom and turn ZFA into FM (T9.1.6).
For a predicate x(x): booleans write for the predicate x(x) constructed syntactically as []. In this notation equivariance is
(7) “() is provable in ZFA for all .”
Function-classes f are modelled by predicates describing the graph of f , so that
The permutation action on translates into an action on (the graph of) the function as follows (f is unary for simplicity):
that is, (f )(x(f (x))
By equivariance (T8.1.10) (x y) (xy) and so we have
We can combine (9)29 with (8)29 to obtain:
For a function symbol F with arguments x defined in the language of ZFA and introduced into its theory the discussion above tells us commutes with F:
If F is parameterised15 this becomes
We call this equivariance of functions.
This situation arises rather frequently because we often introduce defined function symbols into the theory (i.e. , , , , and so on).
These results are extremely useful for proofs by direct calculation, e.g. L13.1.1. In Isabelle/FM and Isabelle/ZFQA almost all proofs are by direct calculation and these results are at the core of the development. See R16.6.3.
Now one mark of good mathematics is when the same result reappears in different contexts. We have discussed function-classes, but permutation acts on and on function-sets within it. This action agrees with class-action, as we now show.
For x a set we say x is equivariant when x x (cf. N9.2.8).
I could write both a concrete and an abstract proof. I favour the first because it shows what really happens to the sets and the second to show the higher truth of the result. Both points of view are important. I hope the reader will excuse me if I include both. In future I shall not. 1 One way of doing it. The standard implementation of f is its graph
The action on sets distributes over and maps to another graph
When we unpack this (writing x) we obtain
Here it is not necessarily the case that f f any more than x x for sets in general but if f is equivariant (N8.1.14) then
2 Another way of doing it. The discussion above depended on the implementation of f as a graph and is in that sense not a general result. Another argument is more attractive and more general. We consider only unary functions for simplicity. Let be a predicate in the language of ZFA
Suppose for some f x y, is true. Equivariance tells us that
So permutation acts16 on a set-function f such that
If it happens that f is equivariant as a set this becomes
8.2. Semantics of syntax in ZFA.
By R8.1.7 we can picture sets as trees whose leaves are labelled with x . acts on sets by acting on the labels (where ). 3
Recall the set lam1 constructed somewhat informally in (3)15. It gave semantics to the datatype lam1 (D4.2) representing -terms. We did not have then. It is convenient to reimplement using it.
We declare in our informal language:
A semantics for this datatype, the set of syntax for the datatype lam3, is the set lam3 built up using the rules
1. We call a term t:X a syntactic term or term and X a type.
2. We call a set in its semantics t X a term or semantic term and X a set of syntax.
So lam3 is a set of syntax for the -calculus not up to -equivalence. We can take Var3, App3 and Lam3 to be Inl(), Inr(Inl()) and Inr(Inr()) (cf. R4.3).
Recall from R4.4 that a term t is assumed to be an abstract syntax tree. Using R8.2.1 to imagine sets as trees, Var3 etc. bolt their arguments together with unique -structure that emulate the syntactic labels on the nodes of t. Variable names, i.e. atoms, occur on the leaves of both set and abstract syntax trees. The permutation action on semantic terms relabels these leaves, just as it does in the abstract syntax. The commutativity results of R8.1.13 prove this rigorously.
However, the permutation action acts on all sets, whether they represent abstract syntax or not. Thus we have a general theory of ‘renaming variable names in sets’ independent of any particular syntax and crucially, not defined by induction
on the terms of a particular datatype. Any theorems we prove about permutation immediately become theorems about abstract syntax—whatever the datatype.
Now consider -equivalence on the set of syntax lam3. Here are three notions of variable-renaming for elements t of lam3, where a : [a]t capture-avoiding substitution of for all free occurrences of a in t. at textual substitution of for all free occurrences of a in t. ( a)t interchange of all occurrences (be they free, bound, or binding) of a and in t. The third version may be unfamiliar but it is more basic than the other two for two reasons:
1. We need not know which constructors of lam3 are binders to define it.
2. Nevertheless we can use it to define -conversion, as the following result shows (cf. [22, p 36], which uses a() in place of ( a)() for the same purpose).
Recall that -conversion, , is usually defined as the least congruence on Λ that identifies Lam3(a t) with Lam3( [a]t). Then coincides with the binary relation on lam3 inductively generated by the following rules:
It is not hard to see that (b a)() preserves = and hence that = is closed under the axioms and rules defining . Therefore is contained in =.
We prove the converse by showing is a congruence relating Lam3(a t) to Lam3(b [ba]). This follows from two facts: if c does not occur in t then (c a)t [ca]t, and the permutation action ( )() preserves (by an appropriate case of R8.1.13).
We see redefined in a different context (using ) in D26.3.1.
We can define ‘permute variable names’ on a particular datatype or the set-universe using -induction. In T8.2.5 we defined -equivalence on a particular datatype. Can we translate this too on the set-universe?
We call a translation of a syntactic concept to the semantic universe ‘synthetic’. So permutation is a synthetic notion of renaming of variables. In 9 below we shall define synthetic notions of “free variable symbols of a set”, “-equivalence of two sets”, “variable-symbol abstraction in a set”, “pick a fresh variable name”, and so on.
The advantage of a synthetic version of a notion is that we can prove results about it which will hold for all its concrete realisations on particular datatypes. This is nice in theory, useful in practice, and wonderful in automation. 3
9. Elementary FM set theory
9.1. Axioms of FM.
Till now our set of permutations has been (D8.1.8). We now concentrate on a restricted permutation set :
Write for the subgroup of (D8.1.8) generated by the transpositions (a b), for a b . Of course inherits the action on the universe.
We can read the meaning of this definition as
“If U and x is any set then “U supports x” when for all permutations , if fixes U pointwise then fixes x.”
ZFA does not have the finite support property. A subset of which is neither finite nor cofinite does not have finite support. We do not discuss this further, but the reader is referred to L9.4.3. There we show that such subsets do not exist in FM. They cannot, (Fresh)35 outlaws them.
An obvious question is why we cut down to from when we define support. is much easier to work with and it makes no difference in the end, see 11.3.
Since is generated by transpositions we can reformulate Φ as
3
Note that Φ( x). Does this mean that all sets are trivially finitely supported? No, because is infinite by (AtmInf)26. But we now add precisely this as an axiom (Fresh)35. This turns ZFA into FM.
As we did for ZFA in R8.1.7 we can build a function-class V : Ordinals taking to the th stage of the cumulative hierarchy , this time in . We can also prove in FM that . This entitles the reader to imagine a model of FM to be a standard cumulative hierarchy, at least while we reason inside FM. As in R8.1.7 I shall use the notation even when no such model is in sight, for notational convenience.
In 11.5 we shall do something more subtle. We shall take a particular and build a cumulative hierarchy inside it, using a slightly different powerset function than pow (see L11.5.11 and surrounding text). This hierarchy will not be the whole universe , nor is it a model of ZFA—but it is a model of FM. That will prove relative consistency of FM wrt ZFA. 3
9.2. Support and #.
R9.1.3 states that all sets in have finite support. In fact they have a unique smallest supporting set:
In this proof x is understood so we write Φ(X x) as Φ(X ). We need only consider transpositions (a b) because they generate . We show for a b U V that (a b)x x. There are various cases to consider.
1. Suppose a U b U . By assumption, (a b)x x.
2. Suppose a V b V . By assumption, (a b)x x.
3. Suppose a U b V . Since U and V are finite and by (AtmInf) is not, we can pick some c such that c U and c V and a c b. By previous cases we know that (c a)x x and (c b)x x, and so that
as required.
4. Suppose a V b U . Similar to the previous case.
The proof above uses the following elementary technical lemma about transposition actions:
For all a b c d ,
Similarly,
Omitted. This is the terribly important Isabelle/ZFQA result , see 16.6.
The following is a trivial corollary of (AtmInf)26 ( infinite) and the construction of Supp:
For all sets x there is a cofinite A such that for all a A, a Supp(x).
Having introduced these function/predicate-classes we can immediately deduce:
1. If a b#x then (a b)x x.
2. If a#x and (b#x) then (a b)x x.
3. If (a b)x x then at least one of (a#x) or (b#x).
We say X is an equivariant set when Supp(X , or put another way when a#X for all a .
This notion of equivariance coincides precisely with that of N8.1.14:
A set x is equivariant if and only if for all , x x. In particular this holds if and only if for all a b , (a b)x x.
We unfold the definition of Φ( x) in D9.1.2 and use the fact that is generated by transpositions.
9.3. Calculating Supp for particular sets.
It is useful to calculate Supp for specific sets. Recall the reformulation of Φ in R9.1.4 as
(We implicitly type a b c n as atoms in .)
Recall also from 9.2 that Supp(x) is the unique smallest set such that Φ(Supp(x) x). So the following proof-methods suggest themselves:
From minimality of Supp, if Φ(V x) for V () then Supp(x) (V ). To show therefore that a Supp(x) we need only exhibit V () such that a V and for all b V , (b )x x.
From Item 3 of L9.2.7 if (a b)x x then either a or b is in the support of x. Therefore, to show a Supp(x) it suffices to exhibit some b Supp(x) such that (a b)x x.3
We can now calculate Supp(U ) for U ().
Clearly Φ(U U ) so by the first proof-method of R9.3.1 Supp(U ) U . Now for the reverse inclusion. Suppose a U b U . Then b Supp(U ) U and clearly (a b)U U . Hence by the second proof-method U Supp(U ).
As an immediate corollary we have
Now suppose f : is a function-class defined in the language of FM. Then equivariance (L8.1.12) tells us that
Suppose Φ(V ) for all . The above commutativity result then implies that Φ(V f (x)). By the first proof-method we have
In the case n = 1 this simplifies to
We can read this as “support cannot increase”. Beware! If g is a function-set it need not be equivariant. In this case the appropriate result is Supp(g(x)) Supp(g) Supp(x). We can see this holds by taking f to be application f g xg(x) in L9.3.4.
The relation between support and an injective function-class is of particular interest because semantics of term-formers for datatypes are of this type.
Let f be a function-class as in L9.3.4 which is also injective. Then
We consider n = 1 only, the general case is similar. Write x for . By L9.3.4 Supp(f (x)) Supp(x).
For Supp(x) Supp(f (x)) we use the second proof-method of R9.3.1. If Supp(x then Supp(x) Supp(f (x)). So suppose we have a Supp(x). Pick some b Supp(x). Clearly
and so
Recall that b Supp(x) and Supp(f (x)) Supp(x). So b Supp(f (x)). By the second proof-method above we obtain a Supp(f (x)). We have proved
and this gives us the reverse inclusion as required.
If f is not injective anything can happen.18 E.g. take f x so Supp(f (x by L9.3.2.
For a , Supp(aa. In particular for a b , b#a b a.
At the end of 9.2 I claimed that Supp provided a synthetic version of the ‘free variables of’ function FV on syntax. We have only built the semantics lam3 for lam3 so let us try it out. Using the lemmas above we can prove by induction on the structure of semantic terms in lam3 that the support of t lam3 is precisely the set of atoms appearing in it.
(19)
The only problem seems to be with the last fact. Surely it should read Supp(t) a? No, this is correct. In Lam3(a,t), a is free in a syntactic sense; Lam3(a,Var3(a)) and Lam3(b,Var3(b)) are not equal. We may define equivalence relations that equate them and functions that satisfy f(Lam3(a,t))=f(t)-a, and we may write f as FV, but that is a different matter.
The cynical reader may be inclined to ask “so what’s the use, seeing as the free-variables function is technically correct but not the one we’re interested in?”. The answer is that FM set theory will continue to deliver the goods (culminating in D10.7.2 and the subsequent development), but we have to advance one step at a time. 3
Supp has many more nice properties. Some of them are discussed in 13.
9.4. The -quantifier.
We now show that FM has a notion of “(z a) where a is fresh for z” which we have already seen in our construction of -equivalence on lam3 in (15)33.
X Y is a cofinite subset of Y when Y X is finite. For a set X we define (X ) to be the set of cofinite subsets of X .
This is the ‘freshness’ quantifier promised at the beginning of this subsection. We shall call it the quantifier, read “the new quantifier”.
For a predicate in the logic of FM, we define
(20) a a powcof()
We can read this definition as
“[New atom a, (a)] holds precisely when the set of a such that (a) holds is cofinite.” The reader is warned that he or she will see a(a) written not only as “for new a, (a)” but also as “for fresh a, (a)”. We use the two terminologies synonymously.
This new quantifier is of great significance and has very nice logical properties. The following technical lemma is the key to developing them. It generalises L9.3.2.
If U then either
Note that in view of the fact that Supp(U ) is always finite (N9.2.4), the two cases above occur when U is finite and cofinite respectively.
By N9.2.4 we know U has some Supp(U ) such that Φ(Supp(U ) U ) (D9.1.2). Suppose
Since Supp((a b)U ) L (a b)Supp(U ) Supp(U ) we know (a b)U U . So
We treat only the first alternative, the proof for the second is similar. So a Supp(U ), a U and b U . Since a U we can use equivariance of to deduce
Now a Supp(U ) so ( a)U U (L9.2.7). It follows that this equation is
We can rewrite this to U Supp(U ). Since Φ(U U ) and Supp(U ) is the smallest set such that Φ(U Supp(U )) it follows that U Supp(U ).
The proof proceeds from the other alternative in a similar manner and shows that Supp(U U .
All subsets of are either finite or cofinite. If U is finite then Supp(U U . If U is cofinite then Supp(U U .
By C9.4.4 is an ultrafilter and so a commutes with conjunction, disjunction, implication and negation, as well as preserving top and bottom .
Thus a, a () a, and so on.
(21) (22)41 is clear, since is finite, so x is finite, so
It follows given (21)41 that a is in () as required.
(22) (23)41 is even easier. is infinite by (AtmInf)26. By assumption a is in () and by the finite support property so is a a#x. So (23)41 follows.
(23) (21)41 follows by equivariance (T9.1.6). Suppose
Let a be the a in question.19 Then equivariance dictates that
Using the notation of T9.4.6, we can add dummy variable dependencies z, so for (x a) a predicate with free variables included in x a,
(25) a
(26) a a#x a#z
3
The following result is central. It wraps up the characteristic - duality of in a convenient package.
In particular, when faced by a(x a), if we fix x we can pick a new apart from x and also any other finite collection z and we know
Note that in the rest of this document I may not bother to give a and distinct names.
Suppose a(x a). We can universally expand using (24)42. By (AtmInf) is infinite and by T9.2.1 the combined supports of xz are finite. Recall from N9.2.4 that a#x a Supp(x), so we can choose some particular #xz and state
as required.
Conversely, if we know (x ) and #x (and possibly some other z), we may use the existential expansions of , (26)42 or (23)41, to deduce a(x a).
If does not depend on a then
A corollary of L9.4.8.
Thanks to T9.4.6, R9.4.7 and L9.4.8 we can read as
“For all new a, ” ,
“For all but finitely many a, ”, or
“For some new a, ”
as we please, where ‘new’ means “is apart from (N9.2.4) the free variables of the formula in the scope of the quantifier”. Note that in due course the terminology ‘fresh’ will also appear in a slightly different context, and can be considered synonymous with ‘new’. 3
Continuing C9.4.5, it follows from the discussion above that can extend its scope arbitrarily over conjunction and disjunction, etc (so long as no variables are accidentally captured, of course). E.g.
Here I have (used R9.4.7 and) bulked out the variable dependencies of and to some common superset x.
Consider a predicate
Note that inside we cannot assume a#x because x is not free in the scope of the -quantifier. Similarly for . T9.4.6 does give us formulae like
3
Recall the terminology ‘synthetic’ introduced in R8.2.6. The -quantifier is a synthetic “pick a fresh variable name”. Unlike Supp and permutation this concept does not correspond to any universally agreed entity in the world of syntax and programming languages. Its effects are usually obtained through something like a choice function (cf. 11.4) for ():
(NOT IN FM) f : () such that U f (U ) U
Note that f is not a function-set in FM, that is the point! It can live quite happily in ZFA (8) acting perhaps on the model of FM in ZFA (HFS, see 11.5).
We can use to construct a synthetic version of -equivalence. For sets x y let (x y) denote the pair-set. We observe in passing that by L8.1.12 we know (a b)(x ya b)x (a b)y).
Let be the following relation-class on FM:
is reflexive, symmetric and transitive and hence an equivalence relation.
Reflexivity and symmetry are trivial. For transitivity, suppose (a x) (b y) (c z). Then
C9.4.5 tells us that commutes with conjunction so
and so (a x) (c z) as required.
We proved that coincides with traditional -equivalence for lam3 in T8.2.5. Now that we have (15)33 is superseded by
9.5. Atom-abstraction.
Recall the definition of in D9.4.13 and the associated (standard) notation (x y) for pairs.
For a write the -equivalence class of (a x) as ax and call it the -abstraction (read “atom-abstraction” or just “abstraction”), of x by a. This defines a new function-class
For a and x any set, the class ax is a set.
ax is a subclass of
which is a set. By collection ax is a set.
Write AbsClass for the class of -abstractions, i.e. the sets satisfying (x) where
We shall usually name variable symbols intended to range over AbsClass x y z unless we are thinking of them as functions f , see L9.5.4.
f AbsClass is a function-set.
It suffices to show that for all a , if (a x) (a ) then . Suppose for this paragraph we know this. Then know f is a function-class with domain . Replacement tells us Codom(f ) and since f Dom(f ) Codom(f ) , separation tells us f and we have the result.
So suppose (a x) (a ). We unfold D9.4.13 and obtain
By L9.4.8 we can choose #a x such that
But of course permutations are bijections so x as required.
Together D9.4.13 and L9.5.4 allow us to view an abstraction in two ways:
1. As a(n equivalence-class of) pair(s): “ax is like (a x) but with the identity of a hidden.” This is reminiscent of ‘abstraction as information hiding’ like that for abstract data types in [55]).
2. As a function: “ax is a function that takes a variable name and substitutes it in the ‘hole’ as appropriate.” This is reminiscent of HOAS (cf. 33.2).3
We already know from L9.3.4 and L9.3.6 that Supp(ax) a Supp(x). More is true:
For a and x FM,
By the technical result L9.5.7 that follows, this amounts to proving
We use L9.4.8 to pick #a x and use equivariance to simplify this to
Unpack the definition of (D9.4.13). It now suffices to prove
c (c )( a)x c a)x so by L9.4.8 we pick such that
# a x amounts (L9.3.6) to a and #x. We can now apply L9.2.3 to deduce
and hence obtain the result.
The following technical lemma, used in the preceding proof, adds one more (rather useful) proof-method to the two described in R9.3.1. In the proofs of L9.5.4 and L9.5.6 I used L9.4.8, we could do the same here but it seems nicer to go back to T9.4.6 and bring out the - duality of directly:
By L9.5.6 and the comment which precedes it.
This answers R9.3.7:
It is useful to have a more concrete characterisation of abstractions. The following corresponds precisely to a result first found useful in Isabelle/FM (see 16.9 and the discussion of on p.134).
Write
Then ax ax.
Left-to-right inclusion. Observe that (a x) ax (reflexivity of in L9.4.14). Now C9.5.9 tells us Supp(ax Supp(x) a and combined with L9.2.7 we know
(Repeated use of) R8.1.13 yields
Therefore, for b a and for b#x, (b (b a)x) ax and therefore
Right-to-left inclusion and equality. Suppose (b (b a)x) ax for b a b#x. We want to show (b y) ax, which amounts to showing that
Strip by choosing some c#a x b by L9.4.8. Now if b a there is nothing to prove because (a a)x x and we know as in the previous half of the proof that (a x) ax. So we may safely assume b a, which amounts by L9.3.6 to b#a, and also b#x. Now (c b)(b a)x c a)(c b) by (18)36. But c b#x so by Item 1 of L9.2.7 we have (c b)x x. Therefore we must show
This is trivial (case of C9.4.5).
The following corresponds to in Isabelle/FM, see R16.9.2 and the preceding discussion starting p.134. It has a few useful corollaries:
ax by precisely when [b#x or b a] and y b a)x.
Let x AbsClass be an abstraction. Then x is a function-set with domain precisely Supp(x).
We can extract a new function-class from C9.5.13:
If f is an -abstraction and b#f we write f @b for the result of applying f as a function to b. We call this the “concretion of f at b”.
(ax)@b b a)x for b Supp(x) a.
This lemma has a form of dual:
For x AbsClass (N9.5.3) an abstraction and a#x,
This result has two useful corollaries:
For x AbsClass an abstraction and a ,
For x y AbsClass abstractions
It is clear from C9.5.9 that atom-abstraction is a synthetic version of the abstraction term-former a.t first suggested in (4)16. Now, perhaps for the first time, FM pays a convincing dividend. Concretion @ is clearly a synthetic version of the destructor for the abstraction term-former in (4)16, call it @, and we can work back to deduce a good typing rule for it. It would look something like this:
where a#x’ is a syntactic version of #. We need this condition so that x’ ]] is defined at a a ]] . So notice that our underlying set theory will mean that we cannot concrete an abstraction at a if a occurs free in it (specifically see 9.5.17). The underlying reason is that abstraction and concretion are implemented using permutations (b a) (D9.5.1 and L9.5.15) and not name-for-name substitution [ba]. Cf. 11.1.
It remains to construct the abstraction-set function-class corresponding to the abstraction-type [Atm]X for which a.t was a term-former.
9.6. Abstraction sets.
For a set X we define the abstraction set or abstraction type of X to be
[]X is intended to capture the idea of
“Elements x X with one distinguished abstracted (bound) atom (variable name).” We can use T9.4.6 and R9.4.12 to rewrite this definition as
Looking at (4)16, the following false definition seems plausible:
The problem is, we want []X to provide a semantics for the type [Atm]X and in particular for the typing rules (4)16 and (28)49. Both []X and []X satisfy the former rule but only []X satisfies the latter. We provide a lemma for []X and a counterexample for []X .
By counterexample. Take X a. Then
C9.5.12 tells us this is a two-element set which we can informally write aa ba. Suppose b and b#X a. Then b a and therefore b X , but (aa)@b b.
Incidentally, [] a is (by C9.5.12 and writing informally) the singleton ba.
These questions are academic because ‘normal’ types such as Nat, Atm and lam3 have equivariant semantics for which []X and []X coincide because Supp(X in that case. In fact (4)16 is simplistic and valid only in an equivariant typing system (i.e. such that the denotations of all types are equivariant). With dependent types like (x:Atm)(x~=a) we must reconsider the intro-rule. FM pays another dividend. 3
The following result is not needed in the subsequent development, but it ties up the discussion of []X as a set quite nicely:
For a set X and a#X ,
We conclude this section by analysing the function-sets out of []X . This will be useful when we extend []() to a functor on SetsFM (D10.1.1) in L10.1.5.
There is a surjection onto functions : []X Y from functions f : X Y such that (f ) where is defined by
In addition there is a bijection between equivariant (N9.2.8) : []X Y and equivariant f : X Y such that (f ).
Note that by T9.4.6 we can read (f ) as
To f : X Y such that (f ) we associate the function
Here is a unique choice function that returns the unique x such that (x) if this exists and otherwise. See R11.4.3.
We must show that maps to Y , not just Y , i.e. for all x []X there exists unique y such that a y f (a x@a).
Existence. Choose a#f x and take y f (a x@a). Observe from (f ) we know a#y. We must verify
b y f (b x@b) equivalent by T9.4.6 to
So choose b a.
Uniqueness. Suppose y Y satisfy
By C9.4.5 distributes over and so
We can now use L9.4.8 to choose some appropriate a#y f , and deduce y as required.
Conversely, to f : []X Y associate
For the surjection it suffices to show f . We know (x) is that unique y such that
But then y f (x) as required.
For the bijection, it suffices to show that and are equivariant if and are, and that f . Equivariance follows by L9.3.4 (no increase of support). Suppose now that f is equivariant. (a x) equals (ax), which is that unique y such that
Use L9.4.8 to choose fresh b#f a x y. Since Supp(f , (f ) implies that for any a, a#f (a x). Thus
as required.
There is a surjection from partial functions
f : Y such that a a#f (a) to elements Y
and a bijection between equivariant f such that a a#f (a) and equivariant elements of Y .
When we write fresh a f (a) we say this is a “legal use of fresh” to mean that a a#f (a) (so fresh a f (a) is well-defined).
We write
fresh a f (a)
Very usefully, fresh a f (a) satisfies the following characteristic equality:21
(32) af (a fresh b f (b) or use L9.4.8 to pick new , and f ( fresh b f (b)
We can read fresh a f as
“Pick a new a and calculate f (a). It doesn’t matter which a we choose because a#f (a).” fresh is an object-level version of the meta-level -quantifier. It shares many of its nice properties. For example:
For function-sets f : X and g : Y ,
In the case that X A B and Y B C,
fresh has many more nice properties, we explore one other in L9.6.10.
[]X is well-behaved too:
[]() is remarkably well-behaved:
In the first case the bijection is given by
F fresh a (a (z@a) a (z@a)) : [](X Y ) []X []Y G fresh a (a(x@a y@a)) : []X []Y [](X Y ) (where and are projection functions from X Y to X and Y respectively). The second case is similar. I omit the proofs and move on the the third bijection.
The fact that the third bijection exists is really very nice, let me seize the moment and point out just how excellently the equational theory of FM turns out. The bijection is given by
We now prove that F (G(g g and G(F (f f. I shall do so in a very equational style. 1 We prove that F (G(g)) and g are extensionally equal, i.e. for all x []X
by expanding the definitions of F and G and simplifying. First we expand F and G on the LHS:
We now apply (for demonstration purposes, the first flavour of) the characteristic equality of fresh (32)52 twice, and deduce
We use L9.4.8 to choose new such that # (and so and #, see L9.3.6), and also #X g x and indeed apart from anything else we wish. We know
Now we have something we can simplify.
So we can simplify the LHS as
so as required LHS RHS.
2 We prove that G(F (f f. By C9.5.18 it suffices to show that for new c, G(F (f))@c f@c, that is,
So let us use L9.4.8 to choose new c#f X Y and anything else we want, and let us pick some x X (note we choose x after c so we do not know c#x). We want to prove
As before we expand the LHS and obtain
Now there is an instructive complication. We might like to, as in the previous case, eliminate fresh using (32)52 and L9.4.8 to replace a b by . We can do so for a but not for b; it is under the scope of x:[]X stuff , which means that for each different x we would need to choose a different fresh . Since x is not fixed within the -abstraction, we cannot pick a particular . However, we can eliminate fresha and -reduce x:[]X fresh b [b(f@b)(x@b)](x), and finally use L9.5.15 to obtain
Now we can reduce (T )@c to (c )T using L9.5.15;
and then pull the permutation in using equivariance L8.1.12. Bear in mind that c#X f so by L9.2.7 (c )X X and (c )f f. We obtain
We now -reduce to obtain
Now we can eliminate freshb for #c x f X and simplify using L9.5.15 to obtain
We now use equivariance L8.1.12 and the fact that ( c)( c Id to obtain
as required.
We can encapsulate the result which is not true in the ‘instructive complication’ in case 2 of C9.6.9 above in a lemma extending L9.6.8:
For f (ax y) and t(b ax) terms with free variables contained in (the sets of pairwise distinct variables) a yx and b ax (so in particular b is not in the free variables of f ), we have
10. Datatypes in FM
10.1. Introduction.
In this section we develop a framework for declaring a class of datatypes with variable binding and constructing FM-sets of syntax for them.
Henceforth we shall be less meticulous about N8.2.4 and may refer to “sets of syntax” as “syntax”, to “semantic terms” as “terms”, etc.
The idea of datatypes as initial algebras goes back to [20]. It is a useful way of thinking which is now standard. The set-theoretic universe corresponds naturally to a category of FM-sets SetsFM defined below in D10.1.1. Since it is convenient to develop datatypes in a category-theoretic context, we continue the development of FM set theory treating as a category SetsFM.
Recall the theory of categories C, see for example [43, I, p.7] and [3, Vol I,Def 1.2.1]. We write the collection of objects of C as Obj(C) and the collection of arrows from X to Y as C(X Y ).
We introduce a category of FM-sets, written SetsFM. Objects of SetsFM are the FM-sets . The arrows from X to Y are the set-functions f : X Y :
We shall adhere to the convention of N4.5 of writing syntax blah and the corresponding SetsFM-semantics as [[ blah ]] or blah. We also follow the convention of naming variables of abstraction type with starred names as in x, or primed names x’ in typewriter font.
We introduce a set of basic type symbols written BTypeSymb,
and a set of basic types written BType
Here is a unit set with one element and U is intended to represent some unit type with one element *. It is useful to define a function
We introduce a set of strings str Strings, which we assume for the sake of argument consist of ASCII text strings such as Var2 and Lam3. Finally, we hypothesise an infinite collection of binding signature variables X Y Z BindVar.
We have developed no theory yet, but here are a few binding signatures we might like to write:
1. The untyped -calculus not up to -equivalence.
2. The untyped -calculus up to -equivalence.
3. Terms of a simple -calculus up to -equivalence (see for example [7, 2, p.4] or the original [53, Part I, p.10]).
(35) Zero of U + Out of A x A x X of A x [A]X Silent of X of [A]X + Par of X x X + Sum of X x X Match of A x A x X + Mismatch of A x A x X
Clearly binding signatures are designed to allow us to build sets of syntax in FM, we shall do this in 10.2.
The standard development of algebras in categories demands that we associate to a functor SetsFM SetsFM. We abuse notation and write it X As our notation suggests X will be ‘bolted together’ out of disjoint sum, product, and n-ary abstraction sets, see D10.1.3. First we must develop the theory.
We write
The functorial actions of disjoint sum + and product are derived from the function-classes in a standard way given in Fig.559. The functorial action of []() is also given and proved well-defined and functorial in the following lemma:
To verify this is a functor we must show four things:
But a#af (x@a) always (L9.5.6). Thus, the fresh in Fig.559 is legal (C9.6.7).
f SetsFM(X Y []f SetsFM([]X []Y ) We just have to show that af (x@a) []Y , i.e. that f (x@a) Y . But this is certainly the case if x@a is well-defined and in X , i.e. if a#x []X . But this holds because a was chosen fresh for all variables outside the scope of fresh a af (x@a), which include x X .
[] id Unpack the definition of the functorial action and of fresh (C9.6.7).
Unpack the definition of the functorial action, use the fact that distributes over logical connectives (C9.4.5), simplify with L9.5.15.
We are now in a position to associate to a binding signature an endofunctor on SetsFM.
Warning! We employ the shorthand given in N10.1.7.
For Z a set we may write B(Z ) for (X (Z ) and N (Z ) for (X (Z ).
The construction of X means it is full of leading 1 and . We shall drop them for convenience. We shall also write []0(X ) and [A]0(X ) as X , []1(X ) as []X , and [A]1X as [A]X .
So, to choose an entirely random example, the functor associated to
Var3 of (App3 of X x X (Lam3 of [A]X ))
has an action on objects given by
written in shorthand as (something like)
The syntax captured by is more general than it first appears: does not allow a single binder to capture two arguments as in [](X Y ), or a choice of argument as in [](X Y ). But C9.6.9 tells us that []() distributes over and +, so this should not matter. The only issue is whether out intuition agrees that binding should display this behaviour. We just consider [](X Y ). This is intended to model
“Elements x X and y Y with one common distinguished bound variable”. Of course we can give this distinguished bound variable a different name in x and y if we wish using -conversion, so this should indeed be equivalent to
“Elements x X with a distinguished bound variable and y Y with a distinguished bound variable”.
10.2. Initial algebras for binding signatures.
Write End(SetsFM) for the category of endofunctors and natural transformations of SetsFM expressible in the language of FM. Thus functors and natural transformations in End(SetsFM) are assumed given by (possibly parameterised) function-classes in the language of FM.
End(SetsFM) has an initial object 0, which is X the constant functor taking objects to and arrows to the empty function : . It has a terminal object 1 which is X 1 the constant functor taking objects to and arrows to the singleton function (1 1) : 1 1.
So X are elements of End(SetsFM). We now consider a subcategory of End(SetsFM) which has some attractive properties and then show that X is in this subcategory (and enjoys its properties).
We call F End(SetsFM) pre-syntactic when
1. F maps inclusions to inclusions and inclusion maps to inclusion maps. That is, if X Y and SetsFM(X Y ) denotes the inclusion map then F (X ) F (Y ) and F ( .
2. F preserves unions of countably ascending chains. That is, for h some function-set out of such that a b implies h(a) h(b),
Write PreSyn for the full subcategory of End(SetsFM) with objects the pre-syntactic endofunctors.
Recall that for a category C and an endofunctor F on C the category of F -algebras Alg(F ) is the following category: Objects f g Obj(Alg(F )) are arrows F (X ) X and F (Y ) Y for X Y Obj(C). Arrows h Alg(F )(f g) are arrows h C(X Y ) such that the following square commutes
The standard definition of an abstract datatype described by is the (underlying set of the) initial object of Alg(X 23
This motivates us to prove the following general theorem, adapted from [60, 2,3]:
If F PreSyn then Alg(F ) has an initial object the identity function on a set init(F ) such that F (init(F init(F ). Furthermore the set init(F ) is equal to F n().24
To save space we jump the gun a little and write
How do we know this really is an initial algebra and fixedpoint of F ?
Property 1 guarantees that init(F ) is a colimit of the diagram
with cone the trivial subset inclusion functions.
Property 2 guarantees that init(F ) is itself a fixedpoint of F .
Now take X and some f : F (X ) X . Observe X so there is an arrow, call it : X . We can use all this to build another cone over (36)62, into X :
So there is a unique : init(t) X such that the colimit diagram commutes. This is equivalent to the initial algebra property:
Now we set about proving C10.2.7 ([]() is pre-syntactic).
[]() satisfies N10.2.2 property 1: []() is monotone and
For the first part we must show
We unpack the definition of []() using the rewritten version of (30)49. Suppose X Y . We must show
Since X Y we know
From C9.4.5 we know that distributes over implication and hence that
and this gives us monotonicity.
For the second part, we unpack the functorial action on an inclusion map. Let f : X Y be the inclusion map . Then from L10.1.5,
From the definition C9.6.7 we see fresh axx is just the inclusion xx, as required.
[]() satisfies N10.2.2 property 2: for h some function-set out of such that a b implies h(a) h(b),
Monotonicity (L10.2.5) gives us one half of the inclusion
because for each m, h(m) h(n).
Now suppose x []h(n). h is a function-set and has finite support so choose a with a#h x. By C9.5.17 there exists an x such that x ax. Also, there exists an m such that x F (m). But then
and this gives us the reverse inclusion
[]() is pre-syntactic.
We conclude this subsection by showing that for a binding signature (D10.1.3), the endofunctor associated to it X (D10.1.6) is pre-syntactic (N10.2.2).
For all sets C, the constant functors X C that take objects to C and arrows to the identity on C are in PreSyn.
We verify the conditions of N10.2.2 individually.
PreSyn has finite products and finite sums.
For the first part it suffices to verify that the initial object 0 x is pre-syntactic, and that for F G PreSyn their product in End(SetsFM) (which is X Y FX FY ) is pre-syntactic. Proof omitted.
For the second part it suffices to verify that the terminal object 1 x1 (N10.2.1) is pre-syntactic, and that for F G PreSyn, their sum in End(SetsFM) (which is X Y FX FY ) is pre-syntactic. Proof omitted.
PreSyn is closed under functor-composition: if F G PreSyn then F G PreSyn.
We inspect the two conditions of N10.2.2 individually and see they are preserved by functor-composition.
[]n() PreSyn.
X is inductively generated using operations under which, as we have just proved, PreSyn is closed.
Recall from T10.2.4 that
(Here we use the shorthand of N10.1.7 and write Bn() for (X n().)
We shall briefly work through a small example of a set built using a particular binding signature in 10.3 below. In D10.3.2 and R10.3.3 we shall consider what a typical element of some B looks like as a set.
10.3. Iteration.
We shall use the notation of N10.1.7 and D10.2.13 mostly without comment.
The universal property of B X gives rise directly (and in a standard way) to an iterative scheme for defining functions out of it. Suppose
Then a function f : B(Z ) Z is equivalent to k functions
and by initiality of B, for each such k-tuple there exists a unique : B Z such that the following diagram commutes:
The nonstandard part is that the N Xi may now contain []nX . T9.6.6 and C9.6.7 characterise all functions out of []X but in practice—as in the latter half of this subsection—we find ourselves mostly concerned with ‘normal’ functions f : X Y lifted using the using the functorial action of []() (L10.1.5) to []f : []X []Y .
A typical is of N X1 of N Xk . We write the injection functions from N i(B) to B as
Write the injection into the i-th component of a k-fold disjoint sum
So in fact and (using N10.1.7)
(41) B(X (N 1(X (N k(X ))
For those who appreciate maths you can see, touch and taste, we combine
(39)65 and (41)66 to characterise the t such that there exists a binding signature with t B:
Let the set of pre-syntactic sets PreStx be generated by the following inductive rules (expressed in BNF grammar style, but this is sets, not syntax):
We define the class of syntactic sets Stx (a subset of PreStx) in a similar style as follows:
(The notation is introduced in N10.3.1. BType is defined in D10.1.2. Nested abstractions as are defined in N10.5.1.)
An informal reading of D10.3.2 is that t B is of the form
where N i(B) is of the form
for itself of the form of t. Here c is some constant in a type T BType and a is a similar constant for the special case of . 3
We could now try defining some general algorithm for manufacturing iterative schemes out of a I choose not to. I propose it would be more enlightening to work through a small example, so we devote the rest of the subsection to working out the iterative scheme for the untyped -calculus.
Recall the binding signature for the -calculus up to -equivalence given on p.57:
(42) Var of A + App of X x X + Lam of [A]X so in this case
This implements in FM the datatype lam2 declared informally in D4.8. So L is the set inductively constructed by the three rules
These visibly correspond to the three rules of (5)17 and as promised terms ‘quotient’ themselves by -equivalence because of the binding-like behaviour of the abstraction-set.
To obtain the iterative scheme for L we consult (40)66 and see it splits into the following three diagrams:
which together express the following predicate in the language of FM:
The final clause is direct from the functorial action of []() in L10.1.5. There is one more manipulation we could carry out if we wished. We could apply (32)52 to rewrite the last clause and obtain
After D4.8 we declared a function subst2 on lam2. We can now iteratively define a substitution function subst on L. For t L, a let subst(t a) where S : L(L) L is defined by the three functions
(46)
So App and Lam, but is something new. By its definition fits in a diagram like (40)66, so and make the following diagrams commute:
Accordingly, or just using the iterative scheme (44)68 directly, we deduce that satisfies the following iterative equations:
(48) (Lam(s Lam(fresh b (b(s@b))) or using (32)52
Since b is chosen fresh it does not occur in t and is not equal to a: the rule for Lam is just the rule for substitution
from D4.11.
10.4. Induction.
Now let us derive a principle of logical induction for L, the datatype constructed in 10.3 above. We continue the notation of that subsection and in particular the commuting diagram (40)66. Consider the special case Z where is the (any) two-element set of truth values in the FM universe, say and . Note that and are equivariant; a# for all a (N9.2.8).
We define f : B(] as follows:
Since b@a and n# for all n we know this is a legal use of fresh (C9.6.7).
This last clause looks complicated but it simplifies. I shall work through the details of how, though I fear that by doing so I risk making something easy look hard. The main flow of discussion resumes at (53)70 (and culminates in (55)71).
We can apply L9.6.10 to the last clause of (51)69.
and use L9.5.15.
But t are free under the scope of the fresh so we may assume (technically by
(32)52) that a n# t. By L9.2.7 we know
the fresh n is dummy (use (32)52) and we have
We can now rewrite (51)69 as follows:
Observe that Φ(x) so by uniqueness of above,
This observation is the core of an inductive principle for L. Now for a little more theory.
For : X a predicate-set in ,
We anticipated the following notation when we wrote “ ” in (50)69 and “ () ()” in (53)70.
For : X , (x) is not a predicate but a set—one of or —in . Nevertheless we may abuse notation and write ‘(x)’, read “(x) holds”, to mean the predicate “(x” and similarly ‘(x)’ for the predicate “(x”.
In this notation the statement of L10.4.1 above becomes
and we can combine (53)70 and (54)70 to see that (51)69 gives a normal-looking inductive principle:
10.5. Adequacy.
Recall the examples of binding signatures on p.57. As promised they now have associated initial algebras. In the first two cases they rigorously construct a set of syntax for datatypes declared in our informal programming language in 4. Recall that the boldface notation B for initial algebras of was introduced in D10.2.13.
The untyped -calculus not up to -equivalence.
The set M is lam3, the set of syntax for the datatype lam3 (see D8.2.3 and D8.2.2 respectively).
The untyped -calculus up to -equivalence.
The set L is the set of syntax for lam2 (see D4.8).
Terms of a simple -calculus up to -equivalence.
(56) Zero of U + Out of A x A x X of A x [A]X Silent of X of [A]X + Par of X x X + Sum of X x X Match of A x A x X + Mismatch of A x A x X
This may look quite good, but the question is
“How do we know the sets M,L,P really are what we said they are, i.e. syntax possibly up to -equivalence?” We need an adequacy result relating sets of syntax built ‘naïvely’ with () to those built using []().
Let a ) be a list of atoms of length n and x X . We continue N10.1.7 and write ax for
and x@a for
We also write
and
fresh a f for fresh fresh fresh f
For the compound and fresh quantifiers the ordering of a does not logically matter and the may be assumed distinct (proof omitted). It may occur that a is the empty list. In that case ax denotes x, and similarly for and fresh.
For example for as above, A rigorous inductive definition of the map B is easy but I hope not needed.
By induction on the syntax of and details omitted.
Now fix and write
We now show that (10.3) generates an equivalence relation on the naïve datatype that is recognizable as -equivalence. The only real difficulty is not itself but the fact that there is no conveniently available general account of -equivalence with which to compare it, besides itself!
By the initial algebra property of the naïve datatype (‘naïve datatype’ D10.5.2, ‘initial algebra’ D10.2.13), there is a unique : B such that the following diagram commutes:
For f : A B a set-function recall that the kernel of f written Ker(f ), is an equivalence class on A. As a relation we write it and define it by
From the commuting square (57)73 above, Ker) is the smallest congruence on containing Ker(). So what is Ker()? It is the identity except on N (X ) for A]nX a clause in in There N An x X and on
Unpack abstractions ax as equivalence-classes (D9.5.1) and observe that ax by precisely when for c (see N10.5.1),
(for an appropriate definition of (x y) as ( )( ), given that all elements occuring in both lists are pairwise distinct). Then observe that name-permutation and name-substitution for c a new name coincide for syntax, and hence that this condition is precisely
This brings us back to a more traditional construction of -equivalence.
We have seen this before in T8.2.5 in the special case of naïve binding signature for the untyped -calculus. We have the following result:
For any binding signature and corresponding naïve signature B (D10.5.2), the datatypes and B are related by
where is -equivalence on the naïve datatype of terms.
From the results above.
We have now given a “general account of -equivalence”. This means
“Binding signatures are a framework within which we can declare and construct a nontrivial class of syntax in FM. Given a we can automatically generates -equivalence on the corresponding naïve datatype B for free.”
10.6. Taking Stock.
Now -equivalence is no mystery to me or to the reader. Given a specific grammar we know precisely what it should be on the datatype of naïve terms (D10.5.2), and we can define it quite rigorously—on a case-by-case basis. 10.5 presented a general recipe (based on FM) which could be used, say, as the underlying theory of an automated procedure for constructing datatypes up to -equivalence. I know of at least two contexts where we would want to do this:
1. Design and implementation of programming languages intended for manipulating syntax.
2. Theorem-proving environments (such as Isabelle, Chapter III).
We can program general procedures and operations involving -equivalence once-and-for-all to be instantiated as the user declares new datatypes. Similarly, we can prove theorems about -equivalence once-and-for-all to be instantiated for particular binding signatures.
I know Isabelle best, so let us imagine an extended datatypes package (see [59, 2.8 p47]) that takes a binding signature and returns, say,
1. The datatype (D10.2.13).
2. An [iterative/recursive] [proof/function] scheme on it (10.3).
3. A corresponding naïve datatype with an associated “-equivalence” map onto the binding datatype plus useful theorems and results—perhaps to model pretty-printing and parsing (T10.5.8).
We can easily imagine a corresponding package for a programming language.
This is not earth-shattering. The first two points on the list above are already ubiquitous among theorem-proving environments and virtually universal in programming languages. To my knowledge the third item is not usually provided (it certainly does not exist in Isabelle)—but there is no reason it should not be. The datatypes-up-to-binding would have to be implemented in ZF, perhaps using de Bruijn (33.1), but it is feasible.
FM scores in this third point because it has the -quantifier and the fresh-term former (D9.4.2 and C9.6.7), which enable us to express these programs and theorems in an easy and natural manner.26
10.7. Everything for free.
In this subsection we demonstrate FM set theory and FM binding signatures by constructing some ubiquitous classes of functions on datatypes. This could conceivably be the underlying theory of a datatypes package for an automated proof environment or a programming language.
For a a list of sets and X a set, we write
By L10.7.4 below, () is (the underlying set) of a -algebra and gives rise to a function (10.3) B () which we write FV and call “the free variables function”.
We also construct fv by -induction on PreStx (D10.3.2) as shown in Fig.876.
The use of fresh in Fig.876 is legal by following lemma:
1. X () a a#X a.
2. X powcof() a (a#X a).
Recall the notation of D10.1.6.
( is a X -algebra over (). That is, for all binding signatures
By induction on the syntax of
For any FV is the iteratively defined function we would normally write to construct the free variables function out of t B.
By observing that the iterative definition of FV on any particular B coincides with our expected notion of ‘free variables’. We just need L9.3.6 to tell us Supp(aa for a .
This purely syntactic notion coincides with a visibly corresponding function on PreStx:
For any FV defined on B coincides with fv.
fv itself coincides with Supp on its domain of definition PreStx.
fv coincides with Supp.
By induction on PreStx. The details of the induction depend on our particular realisation of syntax (, () as function-classes on ).
A more elegant though less rigorous proof is this: any realisation of syntax must use injective disjoint functions (see R4.3), which conserve support by L9.3.5. So an induction on any appropriate PreStx set must work.
This is not merely satisfying, it is useful. We now have no less than three proof-methods for FV: iteration, -induction on fv, and theorems about Supp. In the language of R8.2.6, fv and Supp are synthetic versions of FV.
For a binding signature let the closed terms of B, written Closed(B), be the set
The following lemma would be useful in a theorem-proving environment for porting results about free variables directly from Supp, so we do not even have to consider binding signatures.
Trivial by L10.7.7.
Just as Supp is defined on the universe and fv is defined on PreStx and both coincide with each other and coincide with FV for particular datatypes (see R8.2.6), so we can define functions [[ ba ]] on the universe and [[ ba ]] on PreStx (D10.3.2) that coincide with [ba]:
For any binding signature the functions [[ ba ]] and [ba] coincide on B.
Fix a binding signature and its initial datatype B. We work by induction on B with inductive hypothesis
Now we do not know what is but we know any t is of the form
fresh (a)
Here we use N10.5.1 to write . The are finite lists of variables of type which are chosen fresh. By induction hypothesis we also know
(see N10.5.1). Now if [[ ba ]] and [ba] act on t in the same way given that they act the same way on the , we are done. So we refer to Fig.979 and see that both functions satisfy
We consider [[ ba ]] and omit the case [ba] (which is very fiddly, we use L10.1.5). Write f ba ]] . From Fig.979 we see
Now the were chosen fresh for f t so by Fig.979 we can pull f inside the abstraction and we are done.
We can now prove theorems about [ba] either by iteration on B or -induction on PreStx.
[ba] is defined for particular datatypes and [[ ba ]] is defined on PreStx. The obvious definition of a function on the entire universe, we wrote it [[ ba ]] , is this:
This is wrong, it does not coincide with [ba] and [[ ba ]] defined above. The problem is discussed in 11.1.
Now the last item on our list is “substitution for free”. It is much harder to inductively construct some by induction on in the style of Fig.876 or Fig.979 because the parameter t B depends on a particular if we consider the clause for ( in Fig.979 we might imagine a corresponding
—but this is nonsense. Firstly, t . Secondly we cannot replace Dom(( on the right by B Dom(( because (t y) will in due course be wrapped in by the final clause for (str of 27
For the sake of argument, let us just take the synthetic version as primitive and carry on.
There are many results about this function we might like to have. We only consider one, which is useful in 12.6. The reader will easily recognise this as a standard result:
For x t PreStx and a
By induction on s PreStx using the inductive structure of PreStx in D10.3.2.
See D12.6.2 for a brief continuation of this development.
For a binding signature of the form
such that each is either equal to A or does not mention the symbol A at all, and for b and s t B, [tb]s is in B and is precisely what we understand by ‘substitution of t for b in s’.
Similar to the proof of L10.7.12.
The syntactic condition on makes sure it is of a form for which we can sensibly talk about substitution. For example the result makes no sense for defined in
An interesting question is how we might extend substitution [ta] to a function on the universe just as Supp (N9.2.4) extends fv (D10.7.2). We may get some useful mileage out of a suitably modified version of (61)83 but like that equation, this is an idea for future work. In the meantime we have more than enough to automate a lot of standard syntactic functions, and have shown how we might do others if necessary.
11. Questions
11.1. Name-for-name substitution.
Rather than (b a) why not base FM on name-for-name substitution [ba] (see (59)80, there it is written [[ ba ]] ):
Recall from T8.2.5 that -equivalence = on syntax is usually defined in terms of a “name-for-name substitution” operator usually written [ba]. We hinted in T8.2.5 and then proved in some generality in T10.5.8 that we can just as well construct = using the permutation action of FM set theory. But given that tradition uses [ba], is it possible to carry out a programme of extending ZFA to FM’ where FM’ is like FM only based on [ba] instead of (b a)?
The obvious approach is to duplicate the development of , Supp and # based on [ba]. So we have
This is identical to (20)40 and we proceed. It is simplest to use the alternative characterisation of # in terms of given in R9.5.8. # is defined by
(#,) a#x b [ba]x x and
But observe that
In fact for all a , (a#) and so ( (). Disaster! We lose the finite support property and therefore T9.4.6. This theorem is more-or-less the heart of FM, without it we have nothing.
Let us labour the point a little. Consider and ax (D9.4.13 and D9.5.1) reformulated:
() (a x )(b y) defc [ca]x cb]y
Take x y . Then (a)(b) precisely when a b. ax is the -equivalence class of (a x), so a(a).
Consider this more sophisticated alternative to [ba]:
This is no good for building FM from scratch because it uses Supp, but it does satisfy [ba] and does coincide with the iterative [ba] and -recursive [[ ba ]] of D10.7.10. I invite the reader to imagine automating this definition and using it as the basis for a general theory of name-for-name substitution without syntax. I leave an investigation of this to future work.
11.2. Significance of ‘for free’.
We spent 10.7 and all of 11 until now (we change the subject after this subsection) building various versions of well-known syntactic operations. We considered systematic inductive definitions out of datatypes, inductive definitions on a useful class of sets PreStx (D10.3.2) which coincide with the datatype definitions for all datatypes, and also pure set-function classes defined on the entire universe which coincide with the previous two where they are defined.
Sometimes, we even defined these function classes two or three times in different contexts, for example FV, fv and Supp (proved identical on their domains in L10.7.6 and L10.7.7). I have said why but it bears repeating: when we define a function by induction on a datatype our only method of proof is inductive reasoning on the structure of that datatype. This is a hassle for at least two reasons. First, the datatype may be complex. Second, with each new datatype we must prove our theorems again using its new inductive principle. i.e. We may have proved FV(xt FV(t) x for one -calculus, but if we define another calculus, or start work on the -calculus, we have to prove the result all over again.
If we have automated the construction of a class of functions across datatypes and proved once-and-for-all that they coincide with some function-class defined on the set-universe (as we did for FV in 10.7, equating it with Supp), we can reason just by the properties of the function-class.
This is excellent news, especially for those using theorem-proving environments.
11.3. Restricted set of permutations.
When we constructed FM set theory in 9.1 we introduced the notion of ‘supporting set’. We defined ‘U supports x’ in Fig.335 to mean Φ(U x) where
Recall that is the full set of permutations on and is the restricted set generated by the transpositions.
Why did we restrict to and does it make a difference? Well, is generated by transpositions and for this is not necessarily true. If we build support using we can effectively assume all permutations are transpositions. If the reader examines Chapter II he or she will see that we do just this. Using is the ‘elementary’ option and it makes our lives easier.
The extra axiom that turns FM into ZFA is (Fresh)35, which insists that all sets x have some finite supporting set (and hence, by T9.2.1, have a least finite supporting set Supp(x)). In particular, the must have finite support, so in FM is smaller than in ZFA. In fact and are provably equal in FM (proof omitted). So using does not actually make any difference once we are in FM.
But what about building the theory from scratch? Suppose we use in
a corresponding (Fresh)35’, and hence a theory . Then:
1. Because in FM, any model of FM is a model of FM’. This gives us a relative consistency result.
2. (U x) implies Φ(U x) provably in FM’ and so (Fresh)35’ implies (Fresh)35 provably in FM’.
3. We can duplicate the entire development of support based on Φ only in FM’ and can be certain that it all makes sense from the previous two points. We conclude by duplicating the proof that .
4. Therefore and are provably equal in FM’, so
is provable in FM’. So FM and FM’ are identical logical theories. I find this rather amusing. If we do not restrict to , we can prove that we could have by pretending that we had.
11.4. FM and AC.
Does (Fresh)35 contradict the axiom of choice AC? Yes:
There is no function-set
such that
This should not surprise us; FM is named after Fraenkel and Mostowski, who devised ZFA in the ’20s and ’30s and used their ‘permutation models of set theory’ to prove the independence of the Axiom of Choice (AC) from the other axioms of ZFA (and three decades later Cohen proved the harder result of independence of AC from set theory without atoms (ZF), via his celebrated forcing method; see [38, Section 6] for a brief survey). Here, we have turned their constructions to an entirely new end.
Quite often, careful formulations of the definition of capture-avoiding substitution use a choice function for picking out fresh variables, e.g. [75, Section 2]. The vague feeling that such concrete choices should be irrelevant crystallises here into the fact that such choice functions are inconsistent as we have just shown in T11.4.1.
In particular Hilbert’s choice operator x cannot be added to FM because it can be used to build choice functions. Proof assistants based on set theory or higher order logic often use to provide anonymous notations for terms defined by formulas (see [41, Section 2.1]). 3
A unique choice or definite description operator is consistent with FM (proof omitted). For a predicate on in the logic of FM (possibly with parameters in z)
i.e. x(x) is the unique y such that if such a unique y exists.
Isabelle/FM inherits one from Isabelle/ZF (it is called The, see [59]). Because Isabelle functions have to be total The returns in the case that a unique y does not exist. I use in the proof of T9.6.6 and find it convenient to adopt this influence in the paper proof and let return when no unique choice exists (traditionally we might leave it undefined). Cf. R15.2.4 and R16.1.3. 3
11.5. Consistency of FM.
This subsection is conducted in ZFA set theory. Suppose ZFA is consistent. Choose some particular model (cf. R8.1.7).
In this section we use ZFA to construct a subclass of which satisfies the FM axioms. This proves relative consistency of FM wrt ZFA.
Let the class of hereditarily finitely supported sets in ZFA be written HFS and defined by
Recall that Φ(x U ) means “U supports x”, see D9.1.2. In accordance with standard practice we shall abuse and write x HFS for HFS(x).
We immediately have the following proof-method for HFS:
x HFS precisely when x is finitely supported and for all y x,
We shall use it often, usually without referencing this remark explicitly. 3
R11.5.2 has the useful corollary that HFS is downwards -closed: x HFS and y x implies y HFS.
If f is a function-class on (and no other variables) and each is finitely supported then f ( ) is finitely supported.
Define a new function-class on ZFA as
restricted to HFS maps to HFS. i.e.
We use R11.5.2. Suppose x HFS. Then x is finitely supported and all z x are in HFS. But if y x is finitely supported then all z in y are in x and so in HFS and hence y HFS. We have just proved that all y (x) are in HFS and L11.5.4 says (x) is finitely supported, so again by R11.5.2 we know (x) HFS as required.
From L11.5.6 it immediately follows that if x HFS then (xy x y HFS.
a is supported by a and is empty, is supported by and has atoms as elements, so
The class HFS contains and is closed under all the rules of FM set theory for the ZFA interpretations of and . Thus HFS is a model of FM set theory in .
We verify HFS contains and is closed under the rules of Fig.226 and Fig.335.
For the reader not familiar with such proofs, the general idea is “if you put HFS in, you get HFS out”, hence the word ‘closed’ in the statement of the result. Thus, variables and parameters will usually range over HFS, not . However—and this can cause confusion—when we use ZFA function-classes to build sets which we then prove are in HFS , e.g. , any universally or existentially quantified variables in the ZFA function-classes’ definition range over .
For a concrete example consider (Powerset)26. The statement “HFS is closed under (Powerset)26” actually means
(65) x HFSy HFSz HFS z y w z w x
—so in principle a proof of this from ZFA axioms is complicated by the possibility that might be z with z HFS such that, say, z y but not w z w x. However because HFS is downwards -closed (C11.5.3) this cannot happen. pow(x), the ZFA powerset function-class, does not satisfy (65)87, we use (x) (D11.5.5) instead.
I shall not go through these details in the rest of the proof.
1. HFS by L11.5.8.
2. HFS is closed under (Fresh)35 by construction.
3. HFS is closed under (Sets)26, (Extensionality)26, (AtmInf)26. Follow using C11.5.3.
4. HFS is closed under (Infinity)26. is equivariant (N9.2.8, ‘equivariant’ means ‘has empty support’) and hereditarily equivariant for the obvious meaning of this terminology by analogy with D11.5.1. A set with empty support certainly has finite support, so HFS, and this validates (Infinity)26 of HFS .
5. HFS is closed under (Union)26. Suppose x HFS. Then x is finitely supported and all y x are in HFS. So all z y for y x are in HFS. By L11.5.4 (x) is finitely supported. All z (x) are in HFS by our previous observation. Thus (x) HFS.
6. HFS is closed under (Pairset)26. The standard pairset function in is x y (x yx yx. Suppose x y HFS. Then x y are finitely supported. By L11.5.4 so are (x y), x and x y.29 So xx y are in HFS. Now (x yx yx so (x y) HFS.
7. HFS is closed under (Powerset)26. By L11.5.6, C11.5.7, and (65)87 above.
8. HFS is closed under (Collection)26. For a predicate let f be the function-class on taking x to y x (y). If is parameterised we fix the parameters and assume them to be in HFS and therefore finitely supported.30 Suppose x HFS. Then every y x is in HFS and x is finitely supported. L11.5.4 implies that f (x) is finitely supported. Furthermore as already observed, y f (x) is in x and so in HFS. Therefore f (x) HFS.
9. HFS is closed under (Replacement)26. Let F be a function-class from HFS to HFS. As in the case of (Collection)26 if it is parameterised we assume the parameters are in HFS. For x HFS every y x is in HFS. By assumption F (y) HFS. By L11.5.4 the set F (y) y x is finitely supported. Therefore it is in HFS.
10. HFS satisfies (-Induction)26. By L11.5.11 below HFS is equal to the cumulative hierarchy (D11.5.10 below) built up in ZFA from using ((64)87). Such a cumulative hierarchy clearly satisfies -induction.
This concludes the proof.
Write for the cumulative hierarchy built up from using instead of pow. ‘M’ stands for ‘model’.
HFS.
HFS and as proved in Case 7 above, HFS is closed under . Thus is a subclass of HFS.
Conversely we must show that HFS . This is proved by ZFA -induction on with inductive hypothesis
The proof is elementary but omitted.
FM set theory is consistent wrt ZFA set theory.
A corollary of T11.5.9. Given a model of ZFA, HFS provides a model of FM.
12. Inductive reasoning in FM
Now we change direction and consider a simple but prototypical case study of inductive reasoning on inductively defined sets with -equivalence.
Chapter IV contains a long proof of an interesting result (T21.9) about a programming language FreshML. The proof is in FM; the datatype of terms of FreshML is defined up to -equivalence using the tools of 10 and reasoning is carried out in the theory of FM, including the -quantifier. So Chapter IV is a huge case study. Our prototypical example is FMLtiny, a drastically simplified version of FreshML. We shall construct its syntax and typing and evaluation relations for it, all in FM, and prove a few results about them. We shall dot our i’s and cross our t’s here and take this as a license not to in Chapter IV.
12.1. The syntax of FMLtiny.
1. No sooner do I define a notation than I abuse it. Fig.1190 is naughty because the initial algebras Ty Tm and Vl respectively defined by and are constructed by
mutual induction, which we did not formally develop in 10. I had mutual induction in mind when I set up labelled with a variable symbol X . I gloss over the issue, quoting Bekić’s theorem which shows how mutual inductive definitions can be encoded in ordinary inductive definitions (see [78, 10.1, p.162]).
2. It is unclear whether Vl and Tm are separate datatypes, or whether Vl is an inductively defined subset of Tm. I gloss over this too.3
This is a more interesting point:
Observe from in Fig.1190 that the term-former for (fixedpoint) function abstraction Fix takes as arguments a type and a double abstraction t of a term. A more traditional writing of this is
fix f (x : ) in t
where underlined variables are bound.31 I shall call this ‘nameful style’; though bound variables have no names, we present them as if they did. I shall call the style of Fig.1190 ‘nameless style’. This follows the terminology first mentioned in R4.14.
The nameful presentation is more familiar and I use it to define FreshML in
Fig.31164. There is nothing wrong with explicit variable names so long as we understand that they are bound. So a ‘nameful’ presentation of the grammar for terms of Fig.1190 is this:
(66) t TheUnit x fix f (x : ) in t t t
They are identical declarations, the difference is stylistic. We shall see more about nameful reasoning in FM in the course of this section, see for example R12.4.1.
3
12.2. Inductive reasoning on the syntax of FMLtiny.
What is induction on the syntax of terms? We consult 10.4 and in particular (55)71 and (details omitted) deduce the following induction scheme:
In N4.5 we set up a notation that Var App and Fix are pure syntax term-formers modelled in FM by functions Var App and Fix. Now that we have binding signatures (D10.1.3), adequacy for syntax (T10.5.8) and all the other apparatus of 10, we can be comfortable that our FM syntactic sets are an accurate reflection of abstract syntax ‘in nature’. So we just write Var, App, Lam for the set-function versions of the term-formers too, as in (67)92 above. Cf. R21.11.
We prove the first assertion only, by FM-induction on t with inductive hypothesis
1 Suppose t TheUnit. Then t[V x t and the result is trivial.
2 Suppose t x. Then t[V x V . Observe that values V are terms (cf. Item 2 of R12.1.2). So the result follows.
3 Suppose t . Then t[V x [V x] [V x]. We work by induction on the syntax so we have the inductive hypothesis for and . Therefore [V x] and [V x] are both terms and so is their application.
4 Suppose t Fix( t). This is the interesting case. By the clause for Fix of (67)92 it suffices to choose atoms f u fresh for the current context, so in particular f u#t x V , and verify the inductive hypothesis of t assuming the inductive hypothesis of t@f )@u (so t fix f (u : ) in ).
We therefore assume [V x] is a term. Now from f u#x it follows by L9.3.6 that f u x. Also from f u#V it follows by L10.7.7 that f u FV(V ). So there are no problems with variable capture and
Since the RHS is a term, so is the LHS. This gives us the result.
12.3. Typing of FMLtiny.
Typing contexts are partial functions with finite domain from to types Ty, written in standard style as a finite list Γ. Write the typing contexts .
Typing judgements are a subset of Tm Ty inductively defined by the rules of Fig.1293. We write for the valid typing judgements of FMLtiny.
Recall that the inductive rule
is shorthand for x(x) (x)
in ZF. The language of FM has the -quantifier, so for x y x we may now write inductive rules
The rule for Fix in Fig.1293 written in traditional ZF -style is
Now Γ f : u : is only well-formed when f u Dom(Γ). Traditionally we insist that we only ever write Γ x : when x Dom(Γ). This amounts to adding a side-condition x Dom(Γ).
We can imitate this in FM by writing out t in nameful style (R12.1.3) with explicit variable names:
We do this in Chapter IV, for example in (126)180, (125)180 and (133)181. It looks just the same as normal rules. But FM is different. The understanding is we are just writing out t with explicit variable names which may as well be chosen new! So we really mean:
f u are new for everything except t (see R9.4.12). So f u#Γ and by L12.4.2 this implies that f u Dom(Γ) and the side condition is taken care of.
The slogan is:
Unless otherwise indicated, bound variable names explicitly appearing in an inductive rule are assumed to be created new for variables outside the scope of the binding for that variable, cf. R4.12.
3
In Fig.1293 we do it ‘properly’ with Fix( t). In Chapter IV everything is nameful, in accordance with ordinary practice, but the slogan above is observed throughout, the difference is merely stylistic. It is implicitly used (without any comment) wherever binders occur, for example in (125)180, (126)180, (133)181, or (148)188. 3
12.4. Type uniqueness.
(D12.3.1) is an inductively defined set, a least-fixedpoint of an appropriate monotone operator. How do we reason about such a set? By induction over its rules given in Fig.1293, just as we normally would. The -quantifier in the rule for Fix makes absolutely no odds besides allowing us to assume f and u are new when we reason about them.33 It is at precisely at this point that we first see how FM allows us to manipulate nameless terms in a nameful way. See R4.14 and R12.1.3. 3
If Γ is a function-set with finite domain (the obvious candidate being of course an FMLtiny typing context) and a#Γ then a Dom(Γ).
This result is often applicable because we often have x#Γ, where x was chosen new by a rule such as (72)94. For an example consider the case of Fix in T12.4.3 below. Cf. also 13.2.
For Γ t and such that Γ t : ,
By induction on the typing rules using inductive hypothesis
1 Suppose Γ t : is deduced using (68)93. Trivially t TheUnit and Unit. By pattern-matching against the rules for any other Γ TheUnit : it is the case that Unit. We skip to the last typing rule.
2 Suppose Γ t : is deduced using (71)93. Then t Fix( t) and . We now choose new f u#t t Γ and write t f (u) so that
We have the inductive hypothesis for the judgement
This is well-formed because f u#Γ so by L12.4.2, f u Dom(Γ).
This version is less convenient but it is traditional ZF in the sense that the inductive rule is of standard nameful form FreeVars Assumptions Conclusions. x# y are FM predicates but that has nothing to do with the induction rule itself.
Now suppose Γ t : . Because of the syntactic form of t we know this was deduced by an application of (71)93. We follow back the deduction and apply the inductive hypotheses in the standard way. This gives the result.
12.5. What FM gives us.
What has FM given us? Not that much, but that should not surprise us since if FMLtiny got any simpler it would cease to exist. FM has simply delivered what it always promised: proofs by pure structural induction and general tidying up of the treatment of bound variables. Thus T12.2.1 would normally be proved by induction on term length, here we have seen it proved by pure structural induction. In T12.4.3, itself by structural induction, newness of f and u ensured well-formedness of the typing context. There are more complex results out there as well. For example in a type-substitution property
we would find both the qualities above useful. The industrial-strength application of FM is in Chapter IV and it contains precisely this result, twice for two different judgements, and proved by pure structural induction on the derivation (T23.1.14 and L24.1.8, also C24.1.9). We see other and more sophisticated uses of as well, e.g. in D26.3.1 and its interaction with, say, evaluation in T26.4.7.
Returning to FMLtiny, the fact that we got what we wanted in a prosaic way is part of the basis for my claim that FM is ‘simple’ and ‘natural’.
Now is a good opportunity to mention that FM does deliver a little more than just structural induction. We have equivariance (L8.1.12) for the datatypes and functions and predicates on them (modulo parameterisation of course) as well. FMLtiny is too simple for this to matter, but in a more complex language it may give us a few more results ‘for free’ than we expected. For example in a language with dynamically allocated local state, where new locations would be modelled by new atoms, equivariance could come in jolly useful. Consider for example [67, p.5, Lemma 1], which is a correctness result for evaluation with respect to different choices for new locations. 3
12.6. Evaluation of FMLtiny.
This subsection ostensibly studies evaluation on FMLtiny, but I really use it to study the interaction of FM-abstractions with standard deduction rules.
We define Closed terms and values, CTm and CVl respectively, by
CTm t Tm Supp(t CVl V Vl Supp(V
Here we use “FV for free” (see L10.7.7 and the preceding discussion), which allows us to use Supp directly without bothering to inductively define a “free variables” function.
To define evaluation we use [ta] the “substitution for free” defined in D10.7.13. However, it is convenient to use a slightly different flavour of this function:
We define name-free substitution using [ta] (D10.7.13) by
Because a is fresh, a#t and by L10.7.14 we deduce a#[ta](x@a). So the use of fresh is legal (C9.6.7) and (73)97 is well-defined. The variable to be substituted for is ‘marked’ by being bound (cf. subst2, D4.11).
We see why we prefer @@ to [ta] in (75)97 and R12.6.5. It behaves well:
For s t PreStx and a ,
By induction over s PreStx using the inductive structure of the set (D10.3.2). We use the inductive hypothesis
The proof is a bit messy and I give no details.
In (75)97 we use FM dialect but we can rephrase it in nameful ZF style (R4.14) using L12.6.3 to rewrite @@ in terms of substitution and the convention of R12.3.2 to expand abstractions with implicitly fresh atoms f x;
meaning
(77) f xt
cf. R9.4.12 (binding under ). This is what is happening in (147)188 and many other rules of FreshML, cf. R25.5. 3
13. More set theory
I finish Chapter II by clearing up a few loose ends. We start in 13.1 with L13.1.1, which relates the support of x to the supports of its elements (always a useful sort of equality to know in set theory). 13.2 uses L13.1.1 to develop the theory of the support of syntactic sets.
13.1. Advanced theory of Supp.
For all x,
The base case is L9.3.6. Concerning the second clause, the right-to-left inclusion Supp( Supp(y)) Supp(x) is L9.3.4 for f x Supp(y).
The left-to-right inclusion Supp(x) Supp( Supp(y)) is as follows. Let us write
Suppose there exists some a such that
Choose some b Supp(x). Then (by L9.2.7)
Since (a b)x (a b)y y x (D8.1.8) we can choose y x such that (a b)y x and therefore (a b)y y. Also by construction of we know Supp(y) and since a b Supp() we have (using (13)30 for )
Now is a subset of so by L9.4.3 either
We consider only the first case, the second case is similar. Because of this,
Now because (a b)y y we know at least one of a and b is in Supp(y), and therefore b or a is in (a b)Supp(y). Hence
However, Supp() Supp(x) and b Supp(x), so we have a contradiction. This is nearly but not quite suitable as a definition by -induction, although if we define support first on atoms and subsets of —call this preliminary function —then we can actually make the definition (Possible but unused def)
This is not the definition of Supp, see T9.2.1.
13.2. Theory of finite sets.
L13.1.1 has consequences for the theory of finite sets:
For F a finite set,
A corollary of (Possible but unused def)99, the fact that a finite union of finite sets is finite, and the fact (L9.3.2) that for X a finite subset of , (X X .
And why is this interesting?
It often happens where we use variable binding that we need to “choose a fresh atom (i.e. variable name) a”. The precise meaning of “choose a fresh atom a” in our new theory FM is “choose a apart from Γ t X Y Z and everything else in the context” (i.e. a#Γ t X Y Z , see T9.4.6 or L9.4.8). We saw this in L12.4.2 for example.
C13.2.1 allows us to translate a#Γ to something more concrete. For example, if Γ is a finite set of pairs (x) then by C13.2.1 a#Γ precisely when a#(x) for all (x) Γ. Pairset is an injective function-class so by L9.3.5 this is the case precisely when a#x and a#. Now variable symbols are interpreted by atoms, so x is an atom, and by L9.3.6 a#x iff a x. Suppose for the sake of argument that the typing system is not dependent and satisfies Supp( for all types (as was the case in FMLtiny in 12). Then we have “a#Γ iff a does not occur in Γ”.
This is nothing new, we proved it all in L12.4.2. But typing contexts are more complex in Chapter IV and we use the extra power of C13.2.1 to extend the results. See C23.1.10 and L24.1.5.
We can argue similarly about “a apart from t” (i.e. a#t) for t a term. Abstract syntax in FM is built up using injective function-classes34 so for t a semantic term (N8.2.4) we can use L9.3.5 and C9.5.9 to relate a#t to “a does not occur free in t”.
Thus we may start in the sparkling springs of FM, leave for the fuming fu-maroles of traditional practice, and then return, all safe in the knowledge that our mathematical rigour will neither capsize or be eaten out from beneath us.
Chapter III
Implementation: Isabelle/FM
14. Introduction
Having developed FM in Chapter II, there are at least two ways we may proceed.
1. We can implement an established programming language extended with facilities for handling datatypes of syntax with binding. Any programmer manipulating syntax-like structures would benefit.
2. We can implement FM set theory or a derivative of it in a theorem-proving environment, at once formally ‘verifying’ the mathematics and allowing formal methods to be applied to datatypes of syntax with binding in a practical setting.
The first option is big and requires collaboration between Pitts and me and practitioners requiring specific features. Dr Pitts and I have written a paper on the subject, see [66]. See also Chapter IV.
I have carried out this second option, the results are presented here. We shall see FM set theory implemented inside Isabelle, we call it Isabelle/FM. We shall present the mathematics of the implementation (subtly different from the FM presented in Chapter II) and some of the technical considerations that shaped its design.35
Isabelle/FM differs theoretically from FM set theory as presented in 8 and 9, for various reasons listed below with cross-references to more extensive discussions.
1. Isabelle/FM is a little stronger than FM; it has many types of atoms. This makes it possible to attack state of the art case studies. See R16.1.2.
2. Some hacking was used. For an example see R15.5.1.
3. Isabelle/FM uses Quine atoms. See 15.2.
4. Isabelle/FM has many more constant symbols than FM. See R16.1.1.3
We constructed FM set theory as ZFA+New (89 respectively), where ZFA is ZF set theory with an infinite set of atoms and New is the axiom (Fresh)35, which give FM its unique power and might be called the “theory of the -quantifier”.
The implementation mirrors this. Isabelle/FM was created by reengineering Isabelle/ZF to be Isabelle/ZFQA, ZF with Quine atoms (see 15.2 for a discussion of the nature of Quine atoms and why we used them), and later extending ZFQA with New, the theory of the quantifier. 3
Note that as R14.3 mentions, Isabelle/FM is based on a reengineered, extended version of an existing theory Isabelle/ZF (one of the theories of the Isabelle distribution, [37]). The version of Isabelle/ZF from which I derived Isabelle/FM was Isabelle98-1. All the work described took place in the context of that particular release.
If Isabelle is installed on the reader’s system the Isabelle/ZF files are in $/src/ZF. The precise value of $ depends on the in-stallation. It will be a directory called Isabelle-version, probably in one of the /usr/local, /usr/local/share or /usr/share paths. 3
Isabelle scripts are a sequential development cycle of declaring new types and constants (a Foo.thy ‘theory declaration’ file) and proving results about them (a corresponding Foo.ML ‘proof script’ file). We must decide: shall we declare all types and constants in some Head.thy file and then develop the theory of the various constants in appropriate Script01.ML to Scriptab.ML files? Or shall we declare types and constants as late as possible in individual Scriptab.thy files? Call the former strategy ‘All-at-once’ and the latter ‘Just-in-time’.
Concerning Isabelle/ZF, the type declarations of all standard constructs of set theory (, , etc) are made ‘all at once’ in ZF.thy although the axioms controlling them and more out-of-the way technical constants (such as ‘less than’ on ordinals or the internalised relation-set version of ), are declared ‘just in time’. This has the advantage of laying out all the familiar type and constant declarations in a single initial file.
In contrast Isabelle/FM follows a strict ‘just in time’ strategy. Constants and their controlling axioms are declared in separate Script.thy files and their theory developed in a corresponding Script.ML file. This leads to neater code and makes theory dependencies clearer (e.g. we have a rule of thumb that a result belongs in the earliest script where all its constants have been declared—and if placed it earlier, it won’t compile). 3
We start by reengineering Isabelle/ZF to Isabelle/ZFQA so we should consider some of the issues involved when we modify a line in a .thy file of an existing (and extensive) implementation. This will change one or both of the statement of and proofs of results which mention the constants or axioms we modify, creating work rewriting the proof scripts which tends, fatally, to propagate exponentially through the scripts. Once a result is changed subsequent proof-script changes and a domino effect sets in. This is to be avoided, sometimes we can:
Although Isabelle proof scripts are very technical they do tend to mirror a paper development. This manifests itself in their structure, and a script usually builds up to a fairly limited number of crucial mostly semantically significant results (e.g. introduction/elimination or unfolding rules). Although there is no real provision for ‘local theorems’ scripts usually observe a discipline of only using these results in the subsequent development. We shall call them interface results, as opposed to non-interface results, which are used locally but not in other scripts.
A classic example is pair.ML, the Isabelle/ZF script developing the theory of ordered pairs. Technical details of the set-theoretic implementation of ordered pairs (see in Fig.15108 for the Isabelle/Quine version, slightly different from the Isabelle/ZF version) are completely hidden. Only implementation-independent results such as fst(a b a
qed_goalw "fst_conv" thy [fst_def] "fst(<a,b>) = a" (fn _=> [ (Blast_tac 1) ]);
are of interest. The implementation of Isabelle/ZFQA ordered pairs differs from that of Isabelle/ZF and this provoked work in pair.ML but the interfacing results were unchanged and the disturbance did not propagate.
When we modify an Isabelle theory, one of two things will occur:
1. A change propagates exponentially to all parts of the script logically ‘down-stream’ of the original modification (usually by getting into the interface results). We call this a non-local modification.
2. A change propagates exponentially at first, but then dies out. We call this a local modification.
No change is best, but of the two, local is clearly better. I have found that a semantically innocuous change need not be local, nor need a semantically radical change be non-local. We now consider some types of modification: 3
Experience shows that a semantically innocuous but very non-local change is the addition of an extra condition or indeed any modification to an existing condition, in an interface result.36 Because proof in Isabelle is by resolution this extra condition provokes an extra or modified subgoal each time the modified result is used. In the best (but still very unpleasant) case we must write a little bit of extra script each time to eliminate the subgoal.37 In the worst case the extra subgoal makes clever applications of the automated theorem proving tools fail38 and forces the user to think very hard about how these complicated applications, which he or she did not design, worked and what went wrong. If in addition this extra condition appears in one of the interface results, or worst of all systematically propagates to all the interface results, it is liable to spread uncontrollably and provoke a complete code rewrite.39 Instances of this kind of problem, thankfully mostly averted, arose for example in foundation (see 15.4 and in particular R15.4.2), Quine vs Empty atoms (see R15.2.3 and R15.2.3), (see p.115), and Memrel (see the discussion in and around R15.5.1). My only really bad ‘domino-rewrite-everything-from-scratch’ incident was rank, discussed on p.119. 3
Further examples will arise as we discuss the development.
15. Isabelle/ZFQA
Isabelle/ZFQA is Isabelle/ZF ([59]) re-engineered with Quine atoms (D15.2.1). We now discuss its design.
15.1. Axioms and Constants of Isabelle/ZFQA.
We start by considering the constants and axioms of ZFQA, the simple theory underlying FM. Its constants are illustrated in Fig.15108 and Fig.16109.40 This table is adapted from the original version for ZF copied by kind permission of the author from [59, Section 2.2, Fig 2.1, P.22]. The significance of the various constants is discussed there. Changes and additions appear underlined.
The differences between ZFQA and the original ZF file are slight. We just add a constant symbol Atm of type i, which declares a set of atoms. A weaker declaration with Atm a predicate of type i o
would allow a proper class of atoms but there are good reasons to wish Atm to be a set. For example it lets us define Supp in the way we do, see Fig.20122 and 16.8.
3
Adding a new constant is innocuous in practice, though it may be devastating in theory. E.g. in the presence of an anti-choice axiom the mere declaration of a properly axiomatised choice function makes the theory inconsistent. But previously existing proofs will not mention this new addition to the theory and will compile as before (even if we can now also prove False); the declaration of an additional constant cannot ‘break’ a theory (the same is not true of systems with a more ‘active’ metatheory such as Twelf,
[33]). 3
The axioms of ZFQA are presented in Fig.15108 and Fig.16109. Like Fig.14106 they are adapted from the original [59, Section 2.2, Fig 2.3,2.4, P.26,27].
Most of the axioms are discussed in [59, Part 2.2, “Syntax of set theory”], we only discuss the points of difference from the original ZF files.
We shall start with , the axiom we add to control the elements of the new constant Atm discussed in 15.2. We shall use the occasion in R15.2.3 to justify implementing ZFQA and not ZFA (see D15.2.1). In 15.3 and 15.4 we discuss the two instances where existing definitions of Isabelle/ZF had to be modified in the change to Isabelle/ZFQA.
15.2. Discussion of .
Atoms a are Quine atoms when it is the case that a a, and empty atoms when a has no -related elements (i.e. is empty, though nevertheless not equal to the empty set).
In FM we used empty atoms (8). In Isabelle/FM we use Quine atoms. We call “ZF with empty atoms” by the name ZFA and “ZF with Quine atoms” by the name ZFQA. The slogan is
“We choose empty atoms in Chapter II and Quine atoms in Chapter III.”
is the axiom that states that atoms in Isabelle/ZFQA are Quine:
This contrasts with of the ZFA set theory of Fig.226 and in particular (Sets)26 which imply
Non-wellfounded sets?! And FM is supposed to be easy? I see the point but it is obvious to me, and I hope it will become so to the reader, that Quine atoms are a completely innocuous form of non-wellfounded behaviour (in particular I prove consistency of ZFQA wrt ZFA in R15.2.5). Worrying about them is a red herring. Furthermore, they were a vital design choice without which Isabelle/FM would not exist. R15.2.3 and R15.2.4 below explain why.
Quine atoms are the better choice for Isabelle/ZFQA. Suppose instead we implemented Isabelle/ZFA. As discussed in ft36104 and ft37105 the ZFA-rule for extension in Fig.15108 would have to be (something logically equivalent to)
BAD_extension (A:Atm & B:Atm & A=B) |
(A~:Atm & B~:Atm & A <= B & B <= A)" Sets that are not atoms are extensionally equal, sets that are atoms are equal precisely when they are equal. The set-equality intro rule equalityI would change to something like
originalZF equalityI newZFA equalityI "[| A<=B ; B<=A ; A~:Atm ; B~:Atm |] ==> A=B"
In the language of R14.6 this would be highly non-local. Uses of extension permeate the implementation and each would have to be patched. Results depending directly or indirectly on extensionality would require extra conditions to keep them true, and these modified results would in turn create work each time they are used.
Worse still, any other development building on Isabelle/ZF would be incom-patible with Isabelle/ZFA. It would almost certainly use extension and hence could not be easily imported. This will not be the case with Isabelle/ZFQA. As we mentioned in R15.1.2, an extra constant Atm will not stop scripts that do not mention it from compiling—so long as the parts of the theory that they do refer to are unchanged. 3
Empty atoms cause failure in other ways. Consider the set-theoretic -operator, realised in Isabelle/ZF by Union. We would expect that x x but it follows from in Fig.15108 that for a:Atm, Union(a) 0.
In R15.2.3 we showed that empty atoms would provoke non-local change to extension, forcing work patching proof scripts and results. We now see that empty atoms cast doubt on the implementation of the very basic term-former Union.
The problem cannot be ignored. Consider The, the Isabelle/ZF -term-former, defined in Isabelle/ZF as follows:
the_def "The(P) == Union({y . x:{0}, P(y)})" Now suppose
At this point ZFA and Isabelle/ZFA diverge, since
We opt for Quine atoms. 3
‘Quine atoms’ have a distinguished history. They may be unfamiliar to the reader but are not exotic. Quine discusses them in [72, 4, p.31], where he favours them for just that feature which so suits them for Isabelle/FM, namely leaving extensionality intact. Concerning the consistency of Quine atoms, the reader need only consider in ZFA the predicate
Any formula in the logic of ZFQA true of all models of ZFQA (call this ‘valid’) is mapped to a valid sentence of ZFA by replacing every by . In particular, if ZFQA is inconsistent, is one of these formulae, and it must map to a valid ZFA formula . So long as we believe ZFA is consistent this cannot happen. 3
15.3. Discussion of .
In 15.2 we argued that Isabelle/ZFQA is better than Isabelle/ZFA for implementation. That is not to say that the Quine atoms of Isabelle/ZFQA do not have a price, and part of it is that the axiom must now change. We consider how, why, and the change’s implications. Let us consider the original and the new.
originalZF Pair_def newZFQA Pair_def The first point is the difference between the original Isabelle/ZF definition of pairs (rewritten in traditional notation)
and the standard set-theoretic implementation,
It is true that a a and a are extensionally equal, but a,a and a are different terms. The ‘symmetric’ form is easier to work with.41
Unfortunately, using the original in the presence of Quine atoms breaks some interface theorems. For instance for a:Atm,
so two results in pair.ML,
are no longer true. I have looked and cannot find them used by the rest of the theory so it might not be affected. Some strange results would become provable though, for example
Sigma(Atm,%x.(x)) Atm
but so long as we do not actually prove them our scripts, this need not trouble us (there is some small danger of them creeping in through an automated proof tool).
However, the loss of and troubled me sufficiently that I decided to modify the definition to save them by modifying as shown above. This provoked considerable, but entirely local, changes in pair.ML.
15.4. Discussion of foundation.
Clearly in the presence of Quine atoms such that a a, the traditional formulation of foundation
fails. Just take A a . We use a modified version.
There are two subtleties to the axiom’s design:
1. Why is foundation not written as follows? not_foundation1 "A=0 | (EX x:A. x:Atm | (ALL y:x.y~:A))"
Isabelle’s primary proof-method, resolution, deconstructs terms’ syntax from the top down (as opposed to unfolding definitions or simplification, which act from the bottom up). It is good strategy to push changes down into the syntax. Changes to proofs are thus delayed to when the proof-state is more reduced (perhaps even solved), and when as many instantiations of unknowns as possible have been settled by the original designers’ code.
2. Why is foundation not written as follows? not_foundation2 "A=0 | (EX x:A. ALL y:x.(x:Atm | y~:A))"
An Isabelle proof-state is an ordered list of subgoals and the standard style of manual proof is to attack them in order. If x:Atm comes before , new subgoals arising from x:Atm will tend to appear first in the proof-state, ahead of original subgoals arising from for which code already exists. It is better, as in Case 1 of this list, to postpone change.
We edify this with a principle!
When we modify an Isabelle script it is best to provoke script changes later rather than sooner. This means that:
1. We have access to a more developed theory.
2. Changes have less time to propagate exponentially, so less results have to be modified.
3. On the level of individual proofs, the proof-state is more reduced and unknowns are more likely to be instantiated.
Point 3 is especially important in the common case that a modification provokes a number of trivial typing subgoals, e.g. x~:Atm. My usual strategy has been to structure the proof so they are postponed till the end of a proof and eliminate them uniformly with an automated proof tool. These tools have trouble with unknowns (they are a second-order phenomenon after all), and in the worst case may not fail, but succeed by instantiating an unknown inappropriately, which completely breaks the rest of the proof. 3
To the casual reader R15.4.2 might not seem important, but it is a powerful strategy and underlies a whole style of programming. As such it characterises a great difference between Isabelle and paper: not only is the semantic significance of a proposition important, but at a time when theorem-proving environments are only just easy enough for humans to use, the fine details of the syntax can be decisive.
foundation is fundamental but appears relatively late in the implementation. The change to it described in R15.4.1 is non-local; everything that depends on (a.k.a. :) being well-founded, such as script on rank and ordinals, must be rewritten. However, nearly all of this occurs later. In keeping with R15.4.2 this is, if not good, at least not too bad. And yet there is a price to pay. We consider part of it now and the nastiest effects in 15.5. 3
In fact the first problem comes in the first script file ZF.ML. There is just one result stating that the empty set has no -related elements:
not_mem_empty Remarkably, this is not an axiom, but follows from foundation (and extensionality). See ZF.ML for more details. My early versions of foundation broke the proof. Unfortunately it is by an automated proof tool called . These are difficult to trace and debug and even though is well-documented the proof stayed broken. In fact my first version of foundation was semantically incorrect, but even the corrected versions did not work. It was one of the early victories of R15.4.2 that the original proof-script worked for the final version of foundation, whose design it guided.
I have slipped into the first person and the above is essentially anecdotal. Unfortunately, writing proof-script in Isabelle can be low-level.42 Debugging is slow and errors rarely educational. Most mistakes are made in tiredness or stupidity.
The reader should be aware and beware that at least half of the development time of Isabelle/FM—my time—was spent chasing really silly bugs. With discipline and experience, as always, one learns habits of programming that minimise the risks of creating such errors, but the system does not force these habits on the programmer in the same way that, say, ML tries to. 3
15.5. Further discussion of foundation.
We now come to one of the most demanding parts of the implementation of Isabelle/ZFQA. As mentioned in R15.4.3 the change to foundation provoked by Quine atoms has non-local effects. The sections most seriously affected are Ordinal.ML, dealing with the theory of ordinals, and the later Epsilon.ML, dealing with -induction and rank. The problem in both cases is that ceases to be well-founded in the presence of Quine atoms. We shall consider how each proof-script was mended, starting with Ordinal.ML, but first we consider a case where a proof-script was not changed.
WF.ML, which deals with the theory of well-founded relations and which is used by both Ordinal.ML and Epsilon.ML, compiles without modification in Isabelle/ZFQA; the theory of well-founded relations remains the same regardless of whether is well-founded. But now is not well-founded because of Quine atoms and we might like to change WF.ML’s definition of “well-founded relation”. This is introduced as a predicate wf of type in WF.thy, where its one argument is intended to be an internal relation-set. The Isabelle/ZF definition, unchanged in Isabelle/ZFQA, reads
wf_def "wf(r) == ALL Z. Z=0 | (EX x:Z.ALL y. <y,x>:r --> ~y:Z)" Now suppose this were changed to:
OTHER_wf_def "wf(r) == ALL Z. Z=0 |
(EX x:Z.ALL y. <y,x>:r --> (~y:Z | y:Atm))" The form of this definition, it is clear, is chosen so as to make :, the Isabelle/ZFQA -relation, be ‘OTHER-well-founded’ (cf. R15.4.1). We entertain this thought because:
1. Much of Epsilon.ML compiles without change (I’ve tried).
2. One might argue that the usual notion of well-foundedness is not so appropriate in the presence of Quine atoms.
Against this speak the following:
1. We may need the theory of well-founded relations anyway. For example, recursion on syntactic datatypes is ultimately based on well-foundedness of a relation (essentially “is a subterm of”)—so we should be careful before changing it, we may need the original form.
2. Quine atoms are a convenience only and have nothing to do with FM as such. We may even wish to remove them in a future rewrite. Should we twist basic definitions to accommodate them?
3. A change to the definition of ‘well-foundedness’ has an impressive potential for confusion.
4. Purely in practice—and never mind everything else, this reason is telling— many of the results in WF.ML quote almost verbatim but slightly changed, for example wf_induct" "[| wf(r); !!x.[| ALL y. <y,x>: r --> P(y) |] ==> P(x)
OTHER_wf_induct" "[| wf(r);
!!x.[| ALL y. <y,x>: r --> (P(y) | y:Atm) |] ==> P(x)
These explicitly quoted instances would change with and propagate systematically to conditions in many interface results. This is, as discussed in R14.7, exceedingly undesirable. So WF.thy remained unchanged. WF.ML compiles smoothly.
Now consider Ordinal.ML. Five constants are introduced in Ordinal.thy;
1. : is internalised by Memrel::i=>i, where Memrel(A) is axiomatised as a relation-set between elements of A.
2. ‘Is a transitive set’ is introduced as a predicate Transset::i=>o
3. ‘Is an ordinal’ is introduced as a predicate Ord::i=>o.
4. The notion of ‘less than’ on ordinals is introduced as a binary predicate .
5. ‘Is a limit ordinal’ is introduced as a predicate Limit::i=>o.
The definitions in Ordinal.thy are presented in Fig.17116 along with the original Isabelle/ZF versions (tagged ZF ). Note the unusual definition of Ord, clearly chosen to work well in Isabelle.43
Atoms are ordinals according to the original ZF definition ; a a is a transitive set all of whose elements are transitive sets. If atoms are ordinals then desirable properties of break, such as antisymmetry and irreflexivity. Typing conditions like i~:Atm are no option because of the non-local changes they would cause. We therefore restrict the predicate Ord as seen in in Fig.17116 so it is true only of the ‘original’ ordinals. Note that the following (logically equivalent) version,
BAD_Ord_def "Ord(i) == i~:Atm & Transset(i) & (ALL x:i. Transset(x))" is utterly unsuitable, the difference in effort between using and is at least an order of magnitude. See R15.4.2.
Memrel causes the second problem. In ZF the relation-set internalising on A is always well-founded. In ZFQA it is not; consider A a for a , for which Memrel(A) . The proof of the following result breaks:
wf_Memrel "wf(Memrel(A))" This is an important interface result and a change to it would have serious non-local consequences, e.g. in Epsilon.ML where rank and -recursion are developed.
The solution I chose is a hack of which I am particularly proud. We change Memrel as shown in Fig.17116. Memrel still thinks that atoms are empty and that is well-founded even as : disagrees. A critical group of interface results, including , remains unchanged, and this prevents most modifications from propagating. I call this a ‘hack’ because traditional set theorists would never dream of doing such a thing (nor did we in Chapter II in FM)—but they are not programming in Isabelle.44
However, the ‘hack’ has some moral justification aside from its great technical utility: as already remarked Quine atoms are orthogonal to Isabelle/FM as such. We insulate the internal universe from the details of its implementation. 3
We need to add typing conditions like i~:Atm in some results (for example , see Ordinal.ML) but the changes are local to the script and limited because most are of the form “[Ord(i) and/or ] imply P”. Since Ord(i) and already imply i j , there is usually no need to add this as an extra condition. Once these results are syntactically unchanged (even though the mean-ings of their constant symbols have shifted) later results whose proofs use them do not break, and the changes quickly die out.
Now we consider Epsilon.ML. This deals with -recursion on the set universe and rank. A somewhat edited list of the constants introduced is in Fig.18118. We briefly consider each.
1. eclose(A) is the transitive closure of A under the relation-class :.
2. rank(a) is the rank of a. Since rank is defined by -recursion, no longer well-founded, its definition must be reconsidered.
3. transrec takes a set a::i and function and returns a set transrec(a,H)::i, which has the unfolding property that for a , transrec(a,H) = H(a, lam x:a. transrec(x,H))
This is of course -recursion. We consider eclose first. We can think of this as a function that unfolds a set times and puts all the bits in a big union. Whereas we modified Memrel so it thinks atoms are empty, we have not changed eclose. For a:Atm, eclose(a) is equal to a and not 0. Changing eclose would cause an inconvenient code rewrite and leaving it seems to cause no trouble (probably because the only property of -closure we use in practice is that it contains the transitive closure of ).
transrec is interesting both for its definition and for the effect that the change to Memrel has on its behaviour. From Fig.18118 we see transrec(a,H) is defined by well-founded recursion on
“the restriction of [the internalisation of :] to [the transitive closure of a] with [the recursion function H]”.
Now transitive closure of a is taken using : which thinks atoms are Quine, while Memrel the internalisation of : thinks they are empty. Clearly transrec could do strange things on atoms. Before we check whether this mismatch has strange consequences it is interesting to consider what the quote above actually means by comparing this construction with the pencil-and-paper development of recursion in ZF. 3
The standard development of -recursion in ZF (not ZFQA) is as follows. We construct in the language of set theory the class of all function-sets defined on a (transitively closed) portion of the universe that satisfy an appropriate recursive unfolding rule. These function-sets, usually called trial functions, correspond exactly to transrec(a,H). In the language of set-theory we then use foundation to show that all such function-sets must agree on the intersection of their domains. Hence we see that there exists a unique function-class with the unfolding property (though in the language of ZF we cannot say that).
In Isabelle all this reasoning is simply left out. The Isabelle/ZF implementation does not ‘justify’ -recursion on the type i. The implementors just extract this internal computation and write it up in Isabelle code as . 3
We return to R15.5.2. Memrel and : disagree on atoms. The former considers them empty, the latter considers them Quine (see R15.5.1). Now consider the definition and the unfolding rules for transrec, side by side.
transrec_def transrec(a,H) == wfrec(Memrel(eclose(a)), a, H) unfold rule transrec(a,H) = H(a, lam x:a. transrec(x,H)) We see that the unfolding rule uses : whereas the definition uses Memrel. There is a risk that my hack of R15.5.1 will come back to haunt me in the behaviour of transrec on a:Atm. But things resolve themselves surprisingly well. The unfolding rule on a:Atm is precisely what it would be if atoms were empty:
a:Atm ==> transrec(a,H) = H(a, 0) This enables us to program the behaviour of transrec on elements of Atm with a simple boolean test on a in H.
Rank is a problem. It is defined by -recursion as follows:
rank rank(a) ==transrec(a,%x f. Union({z. y:x, (x~:Atm & z=succ(f‘y))})) ZFrank(a)==transrec(a,%x f. UN y:x.succ(f‘y)) The reader will see that the Isabelle/ZFQA version of is completely rewritten, in violation of R15.4.2. Both definitions start with transrec but this similarity is illusionary because the standard proof-method with transrec is to unfold it, which brings the Union/UN difference right to the top of the term. Isabelle operates on syntax top-down. If the top-level term-formers change, so do the proofs; this is a simple and brutal characteristic of the system. I did mend the section on rank, and this was very difficult, but it is not needed for the development of datatypes of syntax up to variable binding. We have in the end been forced to completely rewrite a definition and its proofs, but have postponed this for so long that there is very little of the theory left to worry about. The rank of atoms is set (somewhat arbitrarily) to zero.
16. Isabelle/FM
In 15 I discussed how I re-engineered Isabelle/ZF to Isabelle/ZFQA. This section discusses how this becomes Isabelle/FM.
16.1. The theory of Isabelle/FM.
As briefly discussed in R14.2 the theory behind Isabelle/FM is not quite FM (9). We now reconsider how and why.
First of all, and this is of no consequence, pencil-and-paper developments of set theory tend to limit the number of constants to (and perhaps ), introducing extra constants as macros with the excuse of ‘notational convenience’ and the injunction that they don’t exist, really. Isabelle/FM on the other hand is full of constant symbols. This is fundamental but need not concern us further. Cf. ft1227. 3
The main difference is that Isabelle/FM makes provision for many types of atoms. It is quite common to have variable symbols of different sorts, for example term and type variable symbols x and respectively, and Isabelle/FM provides support for this.
Recall that Isabelle/ZFQA collects all atoms into a single set Atm::i. In Isabelle/FM this set is partitioned into disjoint infinite sets. When the quantifier is introduced in 16.7 it takes as argument one of these sets and picks a fresh atom from it. 3
The rules and constants of Isabelle/FM are presented in Fig.19121 and
Fig.20122. We use Isabelle syntax. The theory is a linear development from where the most basic constants are declared, up to , which is an empty theory documenting the dependencies and sequence of development. Following our ‘just-in-time’ strategy of R14.5, constants are declared only in the theory file of the script that develops their theory.
We now discuss the files in turn and comment on their design. Recall that an Isabelle theory is a collection of pairs of a .thy and .ML file. The .thy file adds new constants, definitions, rules, and macros to the theory. The .ML file (the ‘proof-script’) proves results involving them.
16.2. .
This theory consists only of a .thy file with no associated .ML file. The intended denotation of AtmPart is the set of types of Atm (see R16.1.2). The associated axioms state that the elements of AtmPart are infinite subsets of Atm. We do not yet insist that they be a partition, i.e. that they be pairwise disjoint and their union be equal to Atm, though this becomes necessary later on in .
Since X:AtmPart is typically an infinite and not cofinite subset of Atm, AtmPart’s structure seems to contradict C9.4.4 (subsets of are finite or cofinite). In Isabelle/FM we will effectively restrict permutations to respect types X:AtmPart (see
16.6 and 18.2), so it is subsets of X that will be necessarily finite or cofinite, not Atm.
16.3. .
This file contains some ZF theorems that were found to be useful but do not appear in the original Isabelle/ZF distribution. Examples are
Upair(A,B)=Upair(B,A) X~:Fin(X) ==> X~=0 u:Fin(X) ==> u-v : Fin(X) y:Fin(A*B) ==> domain(y):Fin(A)
16.4. .
The theory of the set Atm is developed. Examples are Atm_inf Atm~:Fin(Atm) Atm_not_0 Atm~=0 Atm_not_Atm Atm~:Atm FinAtm_ex_new_elt u:Fin(Atm) ==> (EX x:Atm. x~:u) FinAtmPart_ex_new_elt [| u:Fin(X) ; X:AtmPart |] ==> (EX x:X. x~:u) Results like and are part of Isabelle/FM and not Isabelle/ZFQA. No axioms of ZFQA prohibit Atm from being empty. Only when we add AtmPart and its axioms do we know Atm is infinite and therefore nonzero. is difficult to prove because, using Quine atoms, it amounts to Atm~=Atm. The automated tools tend to loop on this. This problem occurs in the early proof scripts until we develop enough of the theory of Atm to abstract away from the concrete implementation.
The last two examples are perhaps the first interesting results of Isabelle/FM. In themselves they merely rephrase and , but they will be used in the theory of NEW, where u will be the support of a set and x will be a fresh atom. Both results are special cases of the following more general lemma:45
[| u:Fin(Atm) ; X:AtmPart |] ==> EX x:X. x~:u
16.5. .
Newfor::[i,i=>o]=>i is a technical precursor to NEW. Recall from D9.4.2 that (rephrasing slightly)
Newfor(X,P) is the set of a:X such that not P(a), where we intend X to be a type of atoms in AtmPart and P to be a proposition on X.
Although the results of Newfor.ML are quite simple, for example
Newfor(X,P) <= X Newfor(X , %x.(P(x) & Q(x))) <= Newfor(X,P) Un Newfor(X,Q) Newfor(X,P) <= Newfor(X,%x.(P(x) & Q(x))) they will later translate directly to more impressive results about . E.g. the second one is a distributivity lemma for over logical conjunction (cf. C9.4.5).
16.6. .
The real work starts here. The permutation action of atoms is defined by -recursion precisely as in D8.1.8 in FM (except that the permutation is restricted to transpositions from the start, cf. D9.1.1. Note that Perm ignores the partitioning of Atm and we can permute any two atoms whether or not they are in the same X:AtmPart. There is an argument for restricting Perm, it is made in 18.2. See also R16.6.2. Note also that we sugar Perm(a,b,x) to (a b).x.
Directed proof-search with Perm is rather problematic:
1. In the very earliest results we unfold the definition of a:Atm as a and automated tools loop on this. Just imagine what this axiom would do to the sanity of a substitution-based simplifier (cf. 16.4). This problem disappears as soon as we abstract away from the implementation of atoms.
2. Because (a b)x b a)x it can sometimes occur that we have (a b)x in the assumptions and (b a)x in the conclusions. We can’t just put their equality into the search space because it causes looping. By careful struc-turing of the results I was able to avoid this.
3. The real problem is that (a b)x y x a b)y. Again, we cannot add this to the search space because the tools would loop. Such situations occur repeatedly (see R16.6.3 below) and are a real problem. I discuss my solutions to this problem in 17.
Sadly our results often cry out for automation:
1. Perm is defined by cases on elements of Atm (consider its nested if-then-else structure in Fig.19121) so proofs of elementary results which unfold Perms definition are often by cases. If three or even four permutations occur together (for examples see the list below, especially ), cases can multiply.
2. The Isabelle/FM analogues of the commutativity results of R8.1.13 are an important class of results. Unfortunately equivariance as proved in T8.1.10 for ZFA and FM cannot be proved in Isabelle (see R16.6.3). The next best thing is a uniform automated proof method. See 17.
3
Results of are of roughly three kinds. We consider two of them here, and the third in R16.6.3. Most of the proofs of the following displayed one or both of the difficulties discussed in R16.6.1.
Perm_idem Perm_idem_twist "(a b).(b a). x = x" Perm_ab_ba Perm_commute The standard proof technique in the first two results is by cases on elements of Atm. For the rest we consider x:Atm first46 and then use -induction. There is nothing unexpected here. The devil is in the execution and the sheer volume of lemmas.
Permutation Perm ignores AtmPart. So belongs to ZFQA more than FM. However, the line dividing Isabelle/ZFQA and Isabelle/FM is more implementational: Isabelle/ZFQA is the modified Isabelle/ZF and Isabelle/FM carries on from there. However, see 18.2. 3
Now we come to the equivariance or commutativity results. Together they represent a significant fraction of the developmental effort. They are precisely the commutativity results of R8.1.13. Now in ZFA this was a corollary of a general result T8.1.10, which was proved by induction on the syntax of the language of ZFA set theory starting from some basic constants which were obviously equivariant. But the datatype of the syntax of Isabelle terms is of course not an Isabelle type, so we cannot do this!47 So these results must be proved individually (this is hard). The Isabelle/ZFQA analogue of (13)30 must be proved symbol by symbol, for example the case is called (Fig.21126) and proved by -induction. 3
Examples of equivariance results are given in Fig.21126. See 19.2 for a concrete instance where we need an equivariance result in a case study. Their proofs present these difficulties:
1. They are numerous, one for each constant.
2. They are often difficult to automate (see R16.6.6 and also 17).
3. Some commutativity results cannot be stated. That of RepFun should be (a b).RepFun(A,f) == RepFun((a b).A,(a b).f)
but this is badly typed because is a function and Perm(a,b), being of type , cannot be applied to it. A new proof is needed for each instantiation of f in the code. Similar problems occur with replacement, The(P), UN x:A. B(x), Sigma(A,f), and similar.48 The list also includes lfp(a::i,h::i=>i) and transrec(a::i,H::[i,i]=>i) with disastrous consequences for our Isabelle/FM theory of datatypes, because we cannot prove general equivariance results for datatypes and functions out of them respectively. See 18.3 and 19.1.
4. They are inexhaustible. We frequently declare new constants and must prove equivariance for each. Sometimes this is trivial by unfolding definitions. Sometimes, bearing in mind point 3 above, it is not.
We take a moment to continue Item 3 above and mention the interesting halfway case of , which should be
(a b).Collect(A,P) == Collect((a b).A,(a b).P)
(the second version uses syntactic sugar). But Collect types as , which is bad (see Item 3 above). Still, we can prove this:
Perm_Collect The RHS uses the replacement term-former Replace::[i,[i,i]=>o]=>i. The term means
So we have a rule to pull permutations inside collections, but the top-level term former changes from Collect to Replace. This change will invalidate any subsequent parts of an existing proof, if we are modifying one, and complicates proofs we write ourselves.49 3
There are two possible notions of equivariance for a (nullary) constant C:
[| a:Atm ; b:Atm |] ==> (a b).C=C and
[| a:X ; b:X ; X:AtmPart |] ==> (a b).C=C
Because permutations need not respect types of atoms (we can quite happily transpose a and b in C for a:X and b:Y of distinct types X,Y:AtmPart) these are not the same. E.g. C=Atm fulfils both and C=Y:AtmPart fulfils only the second. We can be confident that constants inherited from ZF set theory will be equivariant in the unconditional sense. More sophisticated objects such as Supp and Disj (16.8) are not. This whole issue would vanish if we made permutation respect types of atoms, see 18.2. 3
Suppose we have expressions with Perm at the top and bottom respectively and we want to prove . The standard proof method is to unfold definitions and push Perm inside using a library of results.
Unfortunately, if the constants are axiomatised so that there is nothing to unfold, or if one of them has an argument of function type so that the equivariance result could not be stated (see point 3 of the list above), we must use extensionality. At this point we encounter all the difficulties of proof search with Perm discussed in R16.6.1. This happens sufficiently often to be a programming burden. We discuss the matter further in 17. 3
Having discussed why this proof-script is difficult, let us consider why it is not even harder. Isabelle has no subtyping, so Perm is typed as : a and b can not only be different types of atom, they can be any set. Results must account for this, e.g. with typing conditions like a:Atm. So for example, this would occur:
ZF_Perm_subset "X<=Y <-> (a b).X <= (a b).Y" OTHER_Perm_subset "[|a:Atm ; b:Atm|] ==> X<=Y <-> (a b).X <= (a b).Y"
The problem is twofold. First, these conditions spawn subgoals with resolution. Second, the automated proof tools include a simplifier (called ) which rewrites arbitrarily deep inside a term using a supplied library of equalities and logical equivalences. This tool is unique and important because it does not, like all other facilities in Isabelle, operate strictly top-down on terms. But it does
not handle conditional rewrite rules such as quite as well as unconditional ones.
The reader without first-hand experience of Isabelle should understand that this is important. The choice of the ‘irrelevant’ behaviour of Perm literally deter-mined the practicality of the entire enterprise. The two obvious candidates for badly types a or b are to make %x.Perm(a,b,x) the constant empty set function or the identity on i. The latter proved more convenient, virtually eliminating typing conditions. cf. 18. 3
16.7. .
We come to the theory of the quantifier, although we cannot get very far because the critical axiom corresponding to (Fresh)35 appears in the later script 16.8. merely establishes introduction and elimination rules for NEW, but this is not entirely straightforward.
Consider the syntax in Fig.19121. New is declared taking as arguments X:i and . We intend that X:AtmPart and that P is a proposition on X, so New(X,P) picks a fresh atom a:X and tests whether P(a).
New is implemented in terms of existing constants:
New(X,P) == Newfor(X,P):Fin(Atm) clearly corresponding to D9.4.2 in FM on p.40. Note that we do not use Newfor(X,P):Fin(X). Since Newfor(X,P)<=X<=Atm this is equivalent, but the other version is much more convenient.
The four major results of the script are given in Fig.22128. simply axiomatises the definition of New. NewI and NewD are clearly derived from it and are suitable for intro and destruct rules. is a basic result, part of C9.4.5.
We consider first. It is very useful:
Suppose a subgoal has just one condition resolving with New. Then we apply destruct resolution with NewD to simplify the condition to
EX u:Fin(Atm). (ALL a:X. (a~:u --> P(a))) and proceed from there by elim-resolving with the bounded existential quantifier to produce a constant unknown u.
Now suppose the subgoal has two or more such conditions. If we apply NewD and eliminate EX in each individually we will have distinct unknowns u1, u2, etc. But using we could make these unknowns equal. This extremely useful technique is programmed into a simple ML-function .50 3
Now to the most powerful tool so far.
Suppose a conclusion of a subgoal resolves with (the conclusion of) NewI. Resolution produces two subgoals with conclusions u:Fin(Atm) and (ALL a:X. (a~:u --> P(a))) for P suitably instantiated by the resolution.
The standard proof-method, very successful, is this:
1. Instantiate u to the union of all Supp(x) where Supp is support (T9.2.1 and 16.8) and the x are the free variables of type i appearing in the proposition resolving with P.
2. Solve the first subgoal by a standard automated method.
3. Simplify the second subgoal with ballI and impI (which intro-resolve against ALL and ).
The ML-function automates this. The technical details are complex (and interesting) and correspond only in an abstract sense to the recipe shown above.
If P resolves with a term containing higher-order unknowns this proof-method fails because Supp::i=>i cannot be applied to them in Step 1. In this case we use one of simpler precursors to .
Corresponding functions exist for NewD, for example . 3
We can now manipulate NEW almost as conveniently as ALL and EX.
16.8. .
Isabelle/FM takes shape here. We introduce many types of atoms, #, the atom-apartness relation (#, see N9.2.4), Supp, support (Supp, see T9.2.1), and the finite support property (see R9.1.3) which is equivalent to the crucial FM-axiom (Fresh)35.
We introduce axioms asserting that AtmPart partitions Atm.51 AP(a) is that unique X:AtmPart such that a:Atm is in X. We arbitrarily set when x~:Atm (cf. R16.6.7), so for all a:
AP_subset_Atm "AP(a)<=Atm" AP_iff "a:Atm <-> a:AP(a)" a_APc_eq a_APc_c_Atm "a:AP(c) ==> c:Atm" a_APc_a_Atm "a:AP(c) ==> a:Atm"
We now have various characterisations of atoms a:Atm: a:Atm, a:AP(a), a:AP(n) and n:AP(a) for any n.52 3
We introduce a#x, apartness. # queries AP for the type of a and therefore does not take it as an argument. If a~:Atm then we set a#x to True. Otherwise, we use the following definition (see Fig.19121)
NEW b:AP(a). ((b a).x = x) corresponding to the following characterisation of #:
This is an old friend last seen in L9.5.7. Results proved include
Disj_Atm_char Disj_subsetAtm "X:Fin(Atm) ==> a#X <-> a~:X" Disj_Perm_fix Perm_Disj Disj_Perm_I
The first two results characterise apartness for the special cases Atm (recall the characterisation of a:Atm of R16.8.1) and Fin(Atm). The standard proof method with such results is to break them into two implications, of course, and then do the following with each subgoal.
1. Unfold the definition of #,
2. Use and (in that order to get variable dependencies right) to simplify to a subgoal in FOL (without New).
3. Solve using standard methods.
When proving a result involving New (which any result involving # implicitly does) we face a difficulty. Suppose we wish to intro-resolve against New x.P(x,y,z). This should reduce to
but by resolution it is impossible to extract the free variables of P.
The standard method is therefore to (unfold # and then) eliminate New immediately using the programs developed in . They extract the set of free variables by inspecting the syntax of a subgoal with an ML-program and we can then proceed normally. 3
We saw in FM in L9.2.7. Its Isabelle/FM proof is far harder and forced me to develop much of , as well as the strategy of R16.8.2. Because of a#x and b#x we also need (see R16.7.1). The typing conditions a:AP(c) and b:AP(c) insist a and b be in the same type X:AtmPart of atoms. Otherwise the conclusion does not follow.53
is another equivariance result (see R16.6.3). is an example of a family of useful intro and elim rules. We now develop a library of results like these:
and like these:
Note that some likely-looking results are not true:
We have considered # a great deal, what about Supp? Supp(x) is simply the atoms of any type not apart from x, collected into a set (were Atm a proper class this would be impossible, see R15.1.1). We could define Supp as follows:
NOT_Supp_def "NOT_Supp(X,x) == {a:X. ~(a#x)}"
Supp_def "Supp(x) == {a:Atm. ~(a#x)}" So takes as argument an X:AtmPart and returns only atoms of that type. This is a needless complication which we consider no further. Because Supp is defined just using #, its theorems are directly derived from the theory of #.
Supp and # are a natural pair. In 16.9 we shall see Abs and Con (atom abstraction and concretion). On paper we tend to define such pairs separately, prove their duality, and develop their properties in parallel. In Isabelle, because of the constructive style, we tend to choose one of the pair as ‘dominant’ and define the other in terms of it. The standard method with a defined constant is to unfold its definition, so the theory of the non-dominant of the pair becomes a list of corollaries. 3
16.9. .
The final declarations of Isabelle/FM are made here. Atom abstraction and concretion Abs::[i,i]=>i and Con::[i,i]=>i are introduced (D9.5.1 and D9.5.14) along with sugar [a]x and , a predicate Abstraction::i=>o which is true precisely on sets of the form [a]x (N9.5.3), and the abstraction-set set former Abst::i=>i (D9.6.1).
Notice that completely differs from the FM-definition D9.5.1. We prove the two versions equivalent in L9.5.11. We see the discussion of on p.134 below.
We seem to have developed the theory sufficiently that paper and Isabelle converge. In previous files most results were quite tedious. This file is full of interesting ones many of which are familiar from Chapter II. A selection is in
The first group concerns the general theory of abstractions: an intro and destruct rule, and an example of a typical result (L9.5.4 living in Isabelle/FM). Because of the typing Abs::[i,i]=>i we need to control the case a~:Atm.
is the inevitable equivariance result. As with many of the later equivariance results the proof is extremely complex.55 Just for once, we consider it in full. See Fig.24134. This works, but it is clearly unstructured nonsense. It took days to write, and with each fundamental change to the the theory (one of them is discussed in 18 below) or the claset, the proof broke and took days to fix.
The standard technique with a complex proof is to simplify the problem to simpler results. But the problem is already simple (that is, the statement of is not long or compound): the proof is complex, and being so unstructured has no obvious modularisation.
So we try to find a simpler lemma that gives us a better handle on , perhaps some characterisation of equality between abstractions [a]x. was the result, but its proof reduces, slowly and horribly, to .
Sometimes we must unfold all the definitions and take the consequences. With skill we can minimise the work but it will always be unpleasant. This pattern—a simple result which is difficult to prove and
apparently impossible to break up into simpler problems—is a recurring theme I observe in the initial stages of an Isabelle development. 3
By now many sets are defined by collection or replacement. Because and are inelegant (see R16.6.4), equivariance results are particularly prone to suffer from R16.9.1, and this is part of the reason they are such a nuisance (see R16.6.3).
Now we move on to . Recall from D9.5.1 that an FM abstraction set ax is an equivalence class of (a x) under , where is the relation
This is no good for Isabelle. The equivalence class is not a set and cannot be expressed as an element of i. We can implement it as where P(a,x,a’,x’) is suitably axiomatised, and then prove x.P(x) (for well-typed arguments!) is a set. In order to do this though we would either have to exhibit the set U directly and prove it extensionally equal to x.P(x), or concoct some argument using the theory of universes univ(Atm) and collection.
It is clearly simpler to take U as the definition. The reader will see from in Fig.20122 that we do just that, using the concrete characterisation of abstraction we saw in L9.5.11.
and ’ (Fig.23133) are one half of the proof that U and the domain of truth of P are equal. Although semantically interesting they are of no practical use because proof in Isabelle is by resolution and we do not often encounter conclusions of the form NEW c:AP(n).(c a).x = (c b).y.
Intro and elim rules are useful. They are implementation-independent, provide standard methods for simplifying goals, and (if well-designed) give good automated proof-search. They tend to be the real interface results (see R14.6) and to are cases in point. 3
(Fig.23133) is a special case of an equivariance result. It is pivotal (used in the proofs of and the very important ). I had terrible trouble with and and obtained horrible proofs for them. It seemed to be a case of R16.9.1. Then I realised I could deduce both using . The proof is still nasty but we only have to do it once. 3
is L9.5.6 and an important intro rule. For once, the Isabelle/FM and FM proofs are not dissimilar. We use . It is one part of , which itself has a long and involved proof and is precisely C9.5.9. With these two results the apartness behaviour of atom-abstraction [a]x is under control. is easy to prove and semantically satisfying, but not immediately useful. The same holds of and .
is rather interesting. It provides an intro rule for equality of abstractions alternative to and related results.
The other results are fairly straightforward. Abstraction(X,x) means “x is an abstraction of type X”. Concretion is hardly used. Firstly, it only makes sense to write when x is an abstraction, and if we know this we can replace x by [c’]x’ and simplify to (c’ c).x’. Secondly, we are designing these files to provide support for abstract datatypes. Most reasoning with abstract datatypes is by resolution, which amounts to pattern-matching. Patterns match only with values, which can be of the form [a]x but not .
The ‘irrelevant’ behaviour of abstraction and concretion (R16.6.7) is not ad-dressed in the files at all, because it turns out not to be an issue.
16.10. .
In 16.9 we developed abstraction and concretion. In this final file we develop abstraction types (D9.6.1). The difficult files were , and . is easy by comparison. Some of the more interesting results are:
Perm_Abst
(a b).Abst(AP(n’),X) = Abst(AP(n’),(a b).X)" Abst_nosupport "x#X ==> x#Abst(AP(n),X)" Con_I "[| x:Abst(AP(n),X) ; a#X ; a#x ; a:AP(n) |] ==> x<a>:X" Abst_bad_typing "n~:AP(n) ==> Abst(AP(n),X)=0" Abst_mono "X<=Y ==> Abst(AP(n),X) <= Abst(AP(n),Y)" Abst_E "[| x:Abst(AP(n),X) ;
is the equivariance result, its proof is dreadful. Note that we do not have AP((a b).n’) on the RHS because AP(n’) is equivariant (whether n’ is an atom or not). is actually a useful intro-rule needed for the theory of datatypes with binding. is useless in practice. controls the irrelevant behaviour. is L10.2.5 and needed for the datatypes package (see monos in Fig.25144), presumably for the same reasons we proved the theorem in FM. seems to be useless in practice.
16.11. The theory of finite sets.
We conclude the discussion of Isabelle/FM proper. The appropriate FM notion of ‘finite set’ differs from the usual ZF one—namely that the set has finite cardinality. The theory of cardinalities is badly hit by the addition of atoms and FM finite support arising from (Fresh)35 because, although Atm may be countably finite from the outside, it cannot be bijected with Nat or any other ordinal inside the set-universe (we can think about the support of the bijecting function-set and create a proof similar to that of T11.4.1).
A finite set can still be bijected with a finite subset of Nat with a function-set of finite support, so we could pursue a theory of “cardinalities of finite sets”. Instead I chose to characterise ‘X is finite’ by X:Fin(X), that is X (X ), and developed a script of results such as
[| Y<= X ; X:Fin(X) |] ==> Y:Fin(Y) In Isabelle finite sets are inductively defined, so I use this theory to prove L13.2.1 and its corollary L24.1.5. I used this to implement the beginnings of Chapter IV. However, for the reasons discussed in R19.3.1 (not to mention limits of time), I have not implemented all of Chapter IV.
17. Automation and Perm
Having described the structure of Isabelle/FM I shall indulge myself by describing one a simple idea in proof-technique that made a big difference. Recall from Fig.19121 and 16.6 that the permutation action is defined by -recursion on i just as in FM it is defined on in D8.1.8.
Permutation appears mostly in equivariance results, which are numerous. How do we program the automated proof tools to handle a typical result? Consider from .ML:
Perm_Union "(a b). Union(A) = Union ((a b).A)" Isabelle/FM has nothing like T8.1.10 (see R16.6.3) so as with any other goal we must dissect its syntax. In this case this means using extensionality. First we split the equality into two set inclusions, then we reduce the set inclusions to implications:
1. !!x. x:(a b).Union(A) ==> x:Union((a b).A)
2. !!x. x:Union((a b).A) ==> x:(a b).Union(A)
The problem is the same for any term-former ?Con, in this case ?Con Union: we have a lot of results for conclusions and assumptions of the form x:?Con(?A), but almost none for x:(a b).?Con(?A). The solution is simple, we (somehow) pull all permutations to the left of : as shown:
1. !!x. (a b).x:Union(A) ==> x:Union((a b).A)
2. !!x. x:Union((a b).A) ==> (a b).x:Union(A)
Now everything is of the form ?x:Union(?A) and we can apply standard intro and elim rules to simplify the proof-state to this:
Again we pull permutations to the left, and the rest is trivial.
So I developed a collection of libraries with which to program this algorithm (and others as required) into the automated proof tools. A standard example is Perm_epsilon_LR "(a b).x:y ==> x:(a b).y" If we intro-resolve this against a conclusion it “pulls Perm to the left”. Note also if we destruct-resolve against an assumption it “pulls Perm to the right”.56
The other major term-former is equality . There the issue is slightly different because the proof-tools will substitute for x in a subgoal if they encounter an assumption of the form , but not of the form . The algorithm is therefore to pull permutation to the right in assumptions. In conclusions we may prefer permutation on left, because the automated simplifier works with theorems of the form [|Subgoals|] ==> Complex = Simple. So I developed libraries of (elim) rules to pull permutation to the right in assumptions and (intro) rules to pull it to the left in conclusions.
This can cause conflict if we need to resolve a conclusion (with Perm on the left) with an assumption (with Perm on the right). In a future code rewrite I should give some thought to this.
We find similar libraries useful for, say #. For example:
Used appropriately they can pull permutation to the left or right of an assumption or conclusion of the form c#(b a).x or (b a).c#x. Note that the typing conditions a:AP(n) and b:AP(n) will spawn two typing subgoals with each application. This is a real nuisance, I discuss how to eliminate it in 18.2.
We might use these to solve this subgoal 6:
6. !!x’ aa xa.
(which arises with 15 other similar subgoals just before the end of the proof of , see Fig.23133). We substitute b for aa, and then pull the permutation from acting on x on the right of the sixth assumption (where it does no good at all), to the left. We have
!!x’ aa xa.
We can then simplify (a b).a to b, so we have a#x and b#x in the assumptions. We have a result
Disj_Perm_fix This allows us to simplify to . The conclusion is so the subgoal is solved. In this way all sixteen cases can be handled automatically by with in the destruct rules and in the intro rules.57
Perhaps the reader thinks this trivial? In a way it is, but what a difference is makes! Twelve-line proofs collapsed to one-liners overnight. Consider the proof of :
Goal "(a b). Union(A) = Union ((a b).A)"; br equalityI 1; by (auto_tac (Perm_claset(),Perm_simpset())); qed "Perm_Union"; Here () is a standard library of intro- and elim-rules implementing the strategies above. () is a standard library of simplification rules (whose design I shall not discuss), for example . Clearly this proof is quite robust and standardised. It works just as well for , , and many more.
18. Alternative approaches
In 15 and 16 we described Isabelle/FM as it is. Of course this misses interesting ideas which for whatever reason were not included. Let us now consider some of them.
18.1. Meta-level types of atoms.
We go back to the moment we have fin-ished Isabelle/ZFQA and are about to begin Isabelle/FM. We intend to develop the theory of permutation and partition Atm::i into many types (R16.1.2). How? The following strategy was the one I originally adopted. It was extensively developed, but then discarded and does not exist in the source code. .thy declares a new class
classes
atmc < term Recall that the type of sets i is of arity term, so this declares a collection of types atmc, each of which is on a par with i in the Isabelle meta-system. We intend ’a::atmc to be types of atoms, implemented as separate Isabelle types in their own right. We declare a polymorphic casting function @::’a::atmc=>i along with suitable axioms for injectivity and so forth. It is convenient also to declare an inverse to the casting function -@.
"@" :: ’a::atmc => i "-@" :: i => ’a::atmc
Cast_inj Cast_inv_char "@-@a=a" Cast_to_Atm "@a:Atm"
Functions in Isabelle are total. If f is badly-behaved off its intended domain we may in theory need typing conditions in its results, which is inconvenient (see R14.7 and R16.6.7). With meta-types of atoms Perm need not be typed as
Perm :: [i, i, i] => i which leaves great possibility for inappropriate input in the first two arguments which ‘should morally be atoms’ but may be anything. Instead we can declare Perm :: [’a::atmc,’a::atmc,i] => i There is now no question of inappropriate input.
Results that might need typing conditions, such as
Perm_bij "[| a:Atm ; b:Atm |] ==> x=y <-> (a b).x = (a b).y" Perm_Diff "[| a:Atm ; b:Atm |] ==>
Disj_Perm_interpolate "[| b#x ; c#x ; b:AP(n) ; c:AP(n) ; a:AP(n’) |] ==>
lose their typing conditions (although the meta-level typing conditions look messy)
Perm_bij "x=y <-> (a::’a::atmc b::’a::atmc).x = (a b).y" Perm_Diff "(a::’a::atmc b::’a::atmc).(X-Y) = ((a b).X) - ((a b).Y)" Disj_Perm_interpolate "[| (b::’n::atmc)#x ; (c::’n::atmc)#x |] ==>
(b c). (c a). x = (b a::’m::atmc).x" and less conditions is good (R14.7 and R16.6.7).
So why is this bad? Isabelle’s meta-language is too weak to really support it. For example, the useful result
cannot be rephrased as
’n1::atmc~=’n2::atmc ==>
because there is no equality between meta-level types ’n1::atmc, ’n2::atmc.
Supp and related functions have problems. For example, Isabelle has no subtyping so we cannot collect all ’a::atmc into a supertype Atoms. Supp must be polymorphic over ’a::atmc and no longer returns the global support. Furthermore, types cannot be passed directly as arguments to functions. We use indirect and inelegant means:
Supp :: [’a::atmc=>i,i] => i Here the first argument is a dummy function (probably @) that instantiates ’a::atmc in Supp.
Isabelle does not display type information by default. Type information can be switched on, but then all variables are completely typed and even simple results become unreadable. Debugging was very difficult indeed.
I switched once I had realised I could manipulate the ‘irrelevant’ behaviour of Perm::[i,i,i]=>i. By making Perm(a,b) the identity for a and b not both atoms we get the best of both worlds. In 18.2 below I discuss how I might make the ‘irrelevant’ behaviour even better.
18.2. Restrict permutation to types of atoms only.
Recall that Isabelle/FM has many types of atoms (R16.1.2). Isabelle/ZFQA does not; that is, Perm as implemented does not respect them and will permute atoms of one type for another. We could move types of atoms to Isabelle/ZFQA, i.e. extend the ‘irrelevant’ behaviour (R16.6.7), to make Perm(a,b) the identity for a,b:Atm not of the same type X:AtmPart.
This probably would not introduce extra typing conditions (for example into ) because the irrelevant behaviour of Perm is so well-behaved. The definition of Perm would become something like:
CURRENT_Perm_def
"Perm(a,b,x) == if(a:Atm & b:Atm, transrec(x, %y f. (
if(y:Atm,if(y=a,b,if(y=b,a,y)),f‘‘y) )),x)" TYPED_Perm_def
"Perm(a,b,x) == if(EX X:AtmPart. (a:X & b:X), transrec(x, %y f. (
if(y:Atm,if(y=a,b,if(y=b,a,y)),f‘‘y) )),x)" The bounded existential quantifier would complicate proofs in .ML that unfold , but the effects would be local. I have in fact tried a similar approach. I moved AP from .thy to .thy and used it to implement Perm as follows:
ALTERNATIVE_Perm_def
"Perm(a,b,x) == if(a:AP(b) , transrec(x, %y f. (
)),x)" I developed this quite extensively but then dropped it. was a total disaster because of the ‘a:AP(b)’. Permutation is symmetric on its first two arguments and this condition caused parity difficulties in automated proof-search. That is, the proof-state reduced to subgoals of the form
We cannot just add as an intro-rule, it is instant death to proof-search through looping.58 Of course we could always replace the offending clause with something symmetric like EX n.a:AP(n) & b:AP(n), but then we might as well use .
What I did not appreciate is the reward in the later theory where we can drop typing conditions in many important results. E.g.
AP_Perm_I Disj_Perm_fix "[|a#x ; b#x ; a:AP(c) ; b:AP(c)|] ==> (a b).x = x" Perm_Disj Abs_relocate_binder
Perm_Abs
simplify to
respectively.
So Perm should be made to respect types of atoms in the next code rewrite.
18.3. Extend permutation to function types.
Recall from 16.6 we commented that equivariance results for some constants of Isabelle/FM cannot be stated. Consider for example what the equivariance rule should be for transrec::[i,[i,i]=>i]=>i (which is discussed on p.118).
(a b).transrec(t,H) = transrec((a b).t,(a b).H) This is badly typed because and , so (a b).H is badly-typed. Recall that when we developed FM set theory on paper we built the permutation action by -induction just as we did in Isabelle/FM, but then found it useful to extend it to functions and predicates (D8.1.8 and the subsequent text). The action was
So why don’t we extend Perm similarly? Well, there is room for discussion how we will handle the extension itself. Do we just define it for functions like so; Perm’ :: [i,i,i=>i]=>(i=>i) Specific_axiom "Perm’(a,b,f::i=>i)(x)=Perm(a,b,(f(Perm(a,b,x))))" or do we try something cleverer and more general like
Perm’ :: [i,i,i=>’a]=>(i=>’a) HO_axiom "(Perm’(a,b,f::i=>’a))(x)=Perm’(a,b,f(Perm’(a,b,x)))" LO_axiom "Perm’(a,b,x::i)=Perm(a,b,x)" But this does not actually matter because it brings us nothing. To avoid details we argue very abstractly. Suppose we generalise Perm to all types by lifting from i as above. Then instead of writing the above, we can do as we did in (9)29 and write
(a b).transrec = transrec (Isabelle/FOL gives us equality on higher-order types). Perm on higher types is defined by its action at lower types based on i so to prove the statement above we must apply transrec to arguments (a,H), unfold definitions, and so on. The only thing we can do with a function is apply it to arguments, so if we get anywhere it must necessarily be to a commutativity result of the form of those in Fig.21126, where permutation acts only on elements of i. Of course if our goal contains function variables we can’t even do that.
Now let us be more concrete and illustrate this with the specific case of transrec. Suppose we have established enough theory to allow us to state the attractive formula
(a b).transrec(t,H) = transrec((a b).t,(a b).H) as a goal in Isabelle. We have to prove it. The proof-method for transrec is unfolding, and (assuming for simplicity t~:Atm) we obtain
(a b).H(t, lam x:t. transrec(x,H)) =
((a b).H) ((a b).t, lam x:t. transrec(x,(a b).H)) We now have no option but to unfold the definition of permutation on H and obtain
(a b).H(t, lam x:t. transrec(x,H)) =
(a b).H(t, (a b).(lam x:t. transrec(x,(a b).H))) We skip the details, but this reduces to
H(t, lam x:t. transrec(x,H)) =
H(t, lam x:t. transrec((a b).x,(a b).H)) Since H is a function variable symbol, we have no option but to take the last step of reducing this to
(a b).transrec(t,H) = transrec((a b).t,(a b).H) and we are back where we began.
If of course we are trying to prove the statement above for a particular instantiation of H to %x y.T then we do not have to take this last step. However, we might as well just reformulate the initial equivariance result to avoid applying Perm to H in the first place.
In fact I more-or-less go through the loop above (for lfp not transrec) in 19.2 trying to prove in that subsection’s notation that (a b).term=term.
I tried to extend Perm to the type as in (79)142 and developed the theory, but I discovered it was pointless just as described above. Now if permutation were taken as primitive over all types, of course, with some appropriate axiomatisation, then this story would completely change—and I would have been spared the discomfort of the equivariance results. See 20.
19. The -calculus in Isabelle
After much work the stage is set for the raison d’être of Isabelle/FM: datatypes.59
The untyped -calculus has been our running example until now, so let us use the power of Isabelle/FM to actually declare a datatype (a.k.a ‘L’, last seen D10.3.4) as an Isabelle datatype term. All the following takes place in scripts named Term.thy and Term.ML.
19.1. Term.ML.
The Isabelle code is in Fig.25144. First we declare a set aTerm::i, intended to be an atom aTerm:Atm so that AP(aTerm) is its type of atoms and can serve as a set of syntactic variable symbols.60 We do not add an axiom aTerm:Atm so AP(aTerm) may be empty (see 16.8). Such an axiom can of course be added later if needed.
We then declare the set term::i of terms. The datatype declaration calls an ML program referred to as “the Isabelle/ZF datatypes package” which axiomatises term as an appropriate least fixedpoint and proves a few of its basic properties using a default method over which the user has some control via the lists monos, and . I shall call this the user-interface for this section. For edited versions of these properties see Fig.26146.
The datatypes package displays the usual problem of automation in Isabelle—no good error messages or trace—but its code is quite readable. Obviously the unfamiliar abstraction set-former Abst(AP(aTerm),term) in term (Fig.25144) confused the program and I had to figure out what results to put in the user-interface to make it work again. Most of my learning curve was understanding the code sufficiently to rewrite it to produce a crude trace61 and see what had to be done. It is a tribute to the design of the package that I could make it handle abstraction-types using the interface and proof-method provided, i.e. without hacking code except to get enough trace to understand the power of the tool. 3
The results of Fig.26146 are enough for us to inductively reason on term. However, with no functions yet defined out of it (e.g. substitution), we have few interesting theorems to prove except one:
Perm_term "[| a:AP(n) ; b:AP(n) |] ==> (a b).term = term" Disj_term "a#term" Supp_term "Supp(term)=0"
These are three results but only technically so. They are all logically equivalent (quite easily, see Fig.27149) and I shall collectively call them “equivariance of term”.62
Because of the dependencies of the definitions in Isabelle/FM, proofs of the second and third results must reduce to a proof of the first so we restrict attention to . There are two ways of proceeding:
1. Unfold definitions repeatedly (beginning with term.defs) and use a library of equivariance results (which we saw in FM in R8.1.13 and again in Isabelle/FM in R16.6.3) to reduce the problem to triviality. This approach is elegant and fails, we discuss why below.
2. Use extensionality to reduce the problem to two subproblems:
In fact we can be clever and use idempotence of permutation to prove from by a single automated tactic (see Fig.27149). We still have to prove . Proof by hand is out of the question because of the number of cases involved, even for this simple datatype. Automated proof is not easy either. We shall return to the proof below. So why does option 1 fail? We unfold term using term.defs and obtain a subgoal of the form
[| a:AP(aTerm) ; b:AP(aTerm) ; x:lfp(univ(Atm),h) |]
==> (a b).x:lfp(univ(Atm),h) We now use results from to pull the permutation into the least fixedpoint operator.
WRONG [| a:AP(aTerm) ; b:AP(aTerm) ; x:lfp(univ(Atm),h) |]
==> x:lfp((a b).univ(Atm),(a b).h) I have developed the theory of universes in Isabelle/FM and so we can reduce (a b).univ(Atm) to univ(Atm). The (a b).h however is badly-typed and nonsense: Perm(a,b)::i=>i63 cannot be applied to as discussed in Item 3 on p.125.
Our only option is to unfold the definition of lfp using
lfp_def "lfp(D,h) == Inter({X:Pow(D). h(X)<=X})" and hope that the problem goes away (Inter is the Isabelle/ZF version of ). Unfortunately it does not. We can use
Perm_Inter "(a b).Inter(A) = Inter((a b).A)" but we then we come up against Collect (written here in sugared notation)
(a b).{X:Pow(D). h(X)<=X} In R16.6.4 we remarked that this term-former is somewhat problematic. This is a case in point. When we apply 64 we obtain
[|a:AP(aTerm) ; b:AP(aTerm) ; x:Inter({X:Pow(univ(Atm)). h(X)<=X})|]
==> x:Inter({Y. X:Pow(univ(Atm)), h(X)<=X & Y=(a b).X}) To stop things getting too technical we switch into ordinary set-theoretic notation. We need to show that (omitting typing conditions on a and b and the set-universe typing condition in the collection term),
But of course x (a b)X (a b)x X and if we think about it the equation above is just
which is above. We have gained nothing! We shall discuss this further in 20.
We have shown that option 1 of the list above reduces in Isabelle/FM to option 2, which amounts to proving the result
Perm_term_elt1 "[| a:AP(n) ; b:AP(n) |] ==> x:term ==> (a b).x:term" by induction on x:term. We accordingly use term.induct and obtain the following:
> be term.induct 1; Level 1 [| a:AP(n); b:AP(n); x:term |] ==> (a b).x:term
1. !!aa. [|a:AP(n); b:AP(n); aa:AP(aTerm)|] ==> (a b).tVar(aa):term
2. !!aa ba. [| a:AP(n); b:AP(n); aa:term; (a b).aa:term; ba:term; (a b).ba:term |] ==> (a b).tApp(aa, ba):term
aa:Abst(AP(aTerm), {u:term . (a b).u:term}) |] ==> (a b).tAbs(aa):term
The first two subgoals are not difficult; We can expand the definitions of tVar and tApp using term. and then use standard equivariance techniques. The third subgoal is a little harder because the set inside the Abst is not just (a b).term. Nevertheless there is a simple automated proof of it. With this result it is fairly simple to derive . The full code is in Fig.27149.
Having settled equivariance there is little else for Term.ML to do. We prove a few injectivity results of the form
tApp_inj "tApp(x,y) = tApp(x’,y’) ==> x=x’ & y=y’" by a standard automated method because they’re useful later, and that’s about it.
19.2. Discussion of Term.ML.
(Fig.27149) is important in various ways, we consider just one. Suppose we have t:term and a:AP(aTerm). We can easily prove tLam([a]t):term. Suppose further that c:AP(aTerm) and c#[a]t. We
shall certainly encounter situations where is of interest, e.g. evaluating tApp(tLam([a]t),c). But we cannot sensibly discuss (c a).t until we know (c a).t:term. We deduce this by pulling the permutation to the right of : and using . Other examples abound.
The case study continues. I have constructed various inductively defined functions out of term, including a size function, a free variables function, and a substitution function illustrated in Fig.28150.
The datatypes package of Isabelle98-1/ZF does not include facilities for declaring functions out of abstract datatypes directly, they must be declared as inductive relations and proved functional by hand.
Each of the sets in Fig.28150 was a terrible struggle. For example Size, the size function. Before I could even begin to prove results about it I had to go back to Isabelle/ZFQA and extend the adap-tation of Isabelle/ZF to include the theory of ordinal arithmetic (and everything leading up to it). 3
I have proved that the relations in Fig.28150 are functions, proved their equivariance results, and established some of their simpler properties. For example:
a:AP(aTerm) ==> <tVar(a),fx>:FV ==> fx=a and so on. My personal favourite is this:
Size_Omega_is_9 "a:AP(aTerm) ==> <tApp(tAbs([a] (tApp(tVar(a),tVar(a)))),
tAbs([a] (tApp(tVar(a),tVar(a)))) ), ?x>:Size"; During the proof, the Isabelle system instantiates the unknown ?x step by step to the number nine. The result has little to do with FM set theory, but is a lovely little demonstration of the unity of logic and computation. It also shows it is possible to implement a deterministic programming language in Isabelle along with an executable big-step reduction relation.
Back to FM. Note how the definition of substitution in Fig.28150 is the same as the iterative equations defining substitution on L in (49)69 except that I have expanded newness explicitly in terms of # (the theoretical justification for this being T9.4.6).
By expanding a we forfeit the useful ability to assume a apart from extra variables in the context (C9.4.11) as well as the ability to assume different new variables are equal (see in R16.7.1, a practical instance of which appears in a later paper proof in R23.1.13).
Why did I do this? The datatypes package takes its rules in the meta-language:
(80) ; ; |] ==> Conclusion
instead of Isabelle/FOL;
(81) ( & & ) --> Conclusion
so on the face of it, to accommodate (49)69 we would have to program into the meta-language of Isabelle itself—or change the datatypes package to accept rules in FOL+New.
The first alternative is not particularly appealing. The second is in principle just a small programming job: we write a small filter to detect rules of the form of (81)151, possibly with quantifiers up front, and apply (16.7) and various other intro rules to reduce it to the form of (80)151. But this is all rather pointless because it automates the wrong thing—getting rid of a the moment it is handed to the datatypes package. We want to preserve a, leave it in the inductive principle of the datatype, and unpack it at the last moment during some inductive proof so that we may assume a apart from any extra variables in the context of that particular proof.
So forget that idea, we do not need it:
FM has exceedingly nice properties which mean that even though the datatypes package only understands standard ZF, so to speak, it can still be made to handle FM datatypes with a minimum of fuss. C9.4.5 tells us that distributes over conjunction and implication. So we can ask the programmer (or program into the datatypes package the ability) to rephrase a rule of the form
to the logically equivalent form
By C9.4.5 we can also distribute down through conjunctions and disjunctions in and if we wish. We the designers of the system can easily put , and (16.7) into the datatypes package code65 which will automatically reconstitute the original rule (82)152 in the course of a proof placing a#x in the assumptions for every x in the context of that proof. 3
I conclude this subsection with one more incidental comment, a forward reference to Chapter IV.
Sometimes when ZF forces us to choose ‘fresh variables x’, FM allows us not to. For example in (75)97 we do not need to declare names for new atoms because they remain hidden in the abstraction t. In ZF dialect we would have to write something like (77)98.66 I merely wish to point out that traditionally we always unpack abstractions and then re-bind the new atoms as appropriate. FM not only gives us so we can do this much more cleanly than before, it also gives us the option of not doing so gratuitously. I next take up this issue in R25.5. 3
19.3. Conclusion.
Developing the theory of was far harder than I expected. I should not have been surprised. Being the first application ever of Isabelle/FM, it naturally threw up many of its weaknesses and forced me to rewrite the code many times. Because of the rather concrete nature of Isabelle proof, to correct even a small strategic mistake (let alone a large one) can often mean trawling through all the code making hundreds of changes.
One of the major changes was a systematic organisation and development of the standard libraries of results discussed in 17. These libraries have names like (this collection of results helps pull permutations to the left of , : and # in conclusions by intro-resolution) and thus allow us to easily implement ideas like “Pull all the permutations to the left of the set-inclusion”. These fairly simple measures had a dramatic simplifying effect and reduced code-length sometimes by a factor of ten, just by helping me effectively apply the automated tools.
I began more substantial case studies than the -calculus. For example I declared the syntax and operational behaviour of the -calculus, and also the inductive types of syntax and operational behaviour of an FreshML-like language (see Chapter IV). I did some work, and learnt for example that coinductively defined sets seem to present no new difficulties over inductively defined sets. The real problem was the equivariance results (R16.6.3), they just get bigger and badder. Then I realised how to get rid of them forever, see 20 below. The necessary work would have taken more time than I had. So I stopped. 3
20. Future work: Releasing Isabelle/FM as a tool
In the last section I said the next step was to make a real tool of Isabelle, something that real people can use to do real syntax. I also said that the real problem with Isabelle/FM as it now exists is the equivariance results. Their proofs must be simplified:
“Yes, Isabelle/FM lets you manipulate syntax with binding without worrying about silly technical ZF lemmas to do with choosing new variable names. But you do have to spend ages on technical FM lemmas to do with permuting variable names.” No, we can’t have that. An obvious solution is to develop a uniform automated proof-method for equivariance. Unfortunately this is impossible as things stand, recall R16.6.6. The best we can do is an automated proof for the kinds of datatypes users tend to define. In the course of my case studies I have already gone some of the way to doing this but I have fundamental objections to basing a system on the idea:
1. It would take thought and we could get it wrong.
2. I have executed such automated proofs for moderately nontrivial datatypes (datatypes of terms and typings of an FreshML-type language, for example) and they were slow. The proofs would presumably get slower as n2 or similar in the complexity of the type. Still, computers get faster every day.
3. What happens to the user with a new kind of datatype which we did not consider? I was in this position wishing to declare datatypes of syntax involving abstraction Abst(U,X) (D9.6.1 and 16.10), which of course the (ZF) datatypes package did not know about. I hacked code for a week (thankfully just to get a trace, I did not have to change any algorithms, see R19.1.1).
4. Not all equivariance results concern datatypes. The user is free to axiomatise any set they wish, proving equivariance could be very tricky.
In Chapter II we used T8.1.10 and T9.1.6 to give us equivariance ‘for free’ by the properties of the logic of FM itself. We cannot reason about the meta-language of Isabelle/FM in Isabelle/FM, but we can axiomatise the properties we need.
I suggest the following. We extend Isabelle/FM to Isabelle/FM, at the beginning of which are (something like) the declarations of Fig.29155. From these axioms we can for example prove
In addition we add an ML function Equivar:string -> thm that takes a string, parses it to an Isabelle term t, and checks that t has no free variables or scheme variables (see ‘scheme’ in the index of [59]), returning the theorem if so and False if not.67
We would introduce object-level types of atoms in AtmPart::i just as in FM (9) along with casting functions to biject them with ’a::atmc as in 18.1. We would introduce object-level permutation Perm::[i,i,i]=>i just as in ZFA (8). Now the casting functions mean Perm and PERM coincide on atoms, and by equivariance for : the action of PERM distributes over -structure just like Perm. By -induction Perm and PERM coincide.
Thus in 19.1, Fig.27149 instead of the code leading up to qed "" we would just have
introduced. Furthermore, in some sense this is all completely equivalent to the proposal in the body of the text. But we would have kept our hands off the meta-system.
Pollack strongly recommends to me the approach of this footnote on the grounds that the meta-system should be inviolate. Paulson does not seem to care, quote “so long as it’s consistent”; there is a difference in attitude here to the whole enterprise of mechanised mathematics. My thanks to them both for talking to me about this.
Note incidentally that the theory of -terms as constructed would break because I added a constant aTerm:Atm to the theory and this is not equivariant (see Fig.25144). This is my error, but it is superficial. I should have made aTerm:AtmPart be a type of atoms instead. This can be done and it’s no big deal. 3
1. The meta-language of Isabelle is a higher-order logic (HOL). Have we just ad-dressed the question of “how to implement HOL/FM”? No. There is no axiom in the meta-language corresponding to (Fresh)35.
2. So what have I really done? We really do just give the meta-level T8.1.10 which, both paper and Isabelle agree, most comfortably sits there and not lower down in the object level.
The theory of remains definitely object-level inside sets, and indeed Fig.29155 mentions no meta-level axiom of the form of (Fresh)35 for ’a::atmc (it could, but that would bring us very little, discussion omitted).
Of course we could use this extended meta-level to build any FM-style theory, not just Isabelle/FM (e.g. Isabelle/HOL-FM).
The plans for the future are therefore these: We clean up the code and restrict permutation to types of atoms, see 18.2). We package equivariance into the meta-level as discussed above to make a general ‘FM toolkit’ not specific to set theory. We add a theory of fresh (T9.6.6, R19.2.3) to Isabelle/FM. We also extend the datatypes package as described in and around R19.2.2.
It would also be very convenient to mechanise 10.7 in Isabelle/FM (Fig.29155) along with standard automated methods to prove that the various functions defined ‘for free’ on or PreStx correspond to the usual functions a developer would normally define on a datatype. Thus for example Isabelle/FM datatypes would automatically have a FV function defined iteratively by the system on request along with theorems proving it equal to Supp.
We can then carry out a few large case-studies. Isabelle/FM would then be a proven tool ready for general use. 3
It sounds so easy.
Chapter IV
Programming Language: FreshML
21. Introduction
In Chapter II we constructed FM. Now we examine one aspect of what we might call its ‘computational content’—how we can interpret programming languages and their operational semantics in it.
In Chapter IV we construct the datatypes of terms and values of a language FreshML in FM, build—still in FM—an operational semantics for it, and prove one significant correctness result T21.9 about that operational semantics. This proof is a prime target for automation, see 31.
Chapter IV is carried out in FM and uses the extra power that gives us. The reader is reminded that in §12 I laid groundwork for this, discussed inductive reasoning in FM, and how the ‘totally ordinary’ look is achieved (for example we use R12.3.2). 3
For the future we might like to do to an established programming language what FM does to ZF, i.e. extend it with intuitive facilities for handling binding68 while leaving everything looking more-or-less the same. The fact that the “informal programming language” of 4 seems quite reasonable and non-technical (at least to me) suggests this is feasible. Note too that other approaches to the problem of datatypes with binding (33) have not given us anything like FreshML or even the informal programming language, which suggests that this thesis is on to a good thing.
Pitts and myself have begun work on such a language, see [66], but I do not discuss that here. The aim of Chapter IV is more modest. We return to R4.10. Recall from there that although we do not and indeed cannot give the informal language of 4 a rigorous semantics69 we can think of a program loosely as a function out of an FM-set. This is a powerful idea. I used it heavily to motivate my development of FM (Chapter II). Conversely, as FM has developed it has shown us what features our language should have. E.g. fresh (C9.6.7) would probably not have occured to us without FM.
We call the language we shall construct FreshML.
FreshML has an (informal) denotational semantics as sets and functions in FM. For closed values (of lower-order-types), for which termination and typing contexts are no issue, we write the semantics of a value V as ⟦V⟧ . For example, FreshML has an ‘atom-binding’ term-former aV and
(ax introduced in D9.5.1). We may abuse notation where convenient and write
⟦t⟧ for t not necessarily a closed value. 3
The point R4.10 makes is that if contextual equivalence does not appropriately match informal denotation—if there are V and such that ⟦V ⟧ but V , vice versa, or both—then something is wrong. And indeed it might be that perfectly reasonable assumptions about type-constructors, type-destructors, operational semantics and the like unexpectedly interact to demolish even our informal ideas of what the programs denote.
In FreshML we take a collection of these reasonable assumptions and mathematically prove that we “get reasonable behaviour out”, which is formalised in T21.9 below. The general idea of the result is that denotation and contextual equivalence are precisely equal in an appropriately restricted sense. The issue is not useability nor expressivity, except in so far as FreshML is not a trivial language. 3
FreshML is based on a fragment of ML, enhanced with new features (inspired by FM) to support a type of -terms up to -equivalence which we shall write . We shall show that the following result holds (restated more rigorously in T29.25):
70 Given
an appropriate language FreshML whose types include a datatype with informal denotation L (D10.3.4), untyped -terms up to -equivalence,
an appropriate operational semantics, and
an appropriate inductive definition of contextual equivalence for that operational semantics,
then for all closed values-in-context of type
it is the case that contextual equivalence and -equivalence71 coincide:
In other words:
“Terms of the untyped -calculus up to -equivalence are fully and faithfully represented by closed values of the appropriate FreshML datatype modulo contextual equivalence.”
We conduct this work in FM; datatypes of terms and values, the operational semantics, contextual equivalence, are all inductively defined FM sets and we exploit in an integral way the full power of FM logic and the quantifier.72
This is a shift of emphasis. In Chapter II our primitive notion of syntax was abstract syntax in some external universe (see Item 1 in R4.4) and terms were written t. The FM-semantics we constructed were a derived notion intended to model this syntax in a controlled environment, so to speak. We called the FM semantics of syntax ‘semantic terms’ (N8.2.4), they were written t t⟧ .
Now that we have FM, binding signatures (D10.1.3), T10.5.8, and so forth we throw away t and take as primitive the FM sets. 3
I see a particular potential for confusion here because in R21.7 we introduce the concept of the denotation ⟦V ⟧ of V a closed value of FreshML. Firstly there is a certain clash between this notation and the notation [[ V ]] , which is now primitive and written V . Worse, not only are syntax and denotation in the same universe, the denotation itself may be a set of syntax. The particular case which should most concern us is closed values of type . They biject with M on p.57, the -terms not up to -equivalence. Meanwhile
the type’s values’ informal denotation bijects with L (D10.3.4), the -terms up to -equivalence. Cf. R22.1.6 and ft71160. 3
Our FM here has many types of atoms (R16.1.2). We need this to hypothesise two types of atoms Var and AtmC to implement syntactic sets of variable symbols and constant symbols respectively.
Now the language FreshML will have a type of atoms Atm (see Fig.30161). The constant symbols in AtmC will all be of type Atm and we shall need an FM type of atoms for the denotation of the FreshML type Atm.73 In principle this is a third type of atoms. However, FM does not admit a bijective function-set between distinct types of atoms—such a bijection would have nonfinite support, proof omitted but similar to that of T11.4.1, cf. also 16.11. Thus and AtmC must actually be identical and the function mapping a to ⟦a⟧ must be the identity. We shall ignore this and preserve distinct symbols for AtmC the set of syntax and the denotation. 3
22. Syntax
22.1. Definition.
The type system is minimal and unsurprising except for the constants Atm and and the type-former [Atm].
1. is a type of -terms. Its intended denotation is the FM-set L of (42)67 , namely untyped -terms up to -equivalence. Looking ahead for a moment to R22.1.6, we shall see that terms of type are actually isomorphic to untyped -terms not up to -equivalence.
2. Atm is a type of atoms. Its intended denotation is (8 also R21.13). The only closed values of type Atm will be a collection of constants a b c AtmC.
3. We call [Atm] abstraction types. The intended denotation corresponds to the abstraction-set former []X of D9.6.1.3
As stated in R21.7, a rigorous denotational semantics for FreshML demands domain theory and we ignore this.
We shall need some constructor symbol constants to build a set of terms.
We declare a set of term constructors. Abusing notation we equate the constructor symbol with its sugared (e.g. possibly infix term-constructor functional) notation:
(84) TermCon True False0 Succ() () :: Var() App() Lam()
As promised in R21.13 we declare two types of atoms in FM, one for variable symbols x y z Var and and the other for constant symbols a b c AtmC. The type system will in due course (24) assign constants a b c type Atm. We introduce a notation for a useful syntactic class of variables-or-constants xa xb Var AtmC:
(85) a b c AtmC
Finally we define terms t and values V as datatypes with binding in FM:74
In those figures, binding occurrences of variable symbols are written underlined, as in (fix f (x : ) in t).75 The free variables function on terms (and values) is written FV(t), we can obtain it ‘for free’ by D10.7.2. Atom-abstraction xct is not binding on xc—we shall call it synthetically binding instead (see 23 and R23.1.1). We write the set of closed terms and closed values
CTerms t Terms t : and
respectively.76
The following ground has already been well-covered, but I should not assume the reader is completely familiar with the rest of the document and I go over this again:
FM sets have a transposition action (a b)x (a b assumed to be atoms of the same type, i.e. Var, AtmC, Atm or ) introduced in D8.1.8 which literally goes through the -structure of x swapping a for b and b for a (R8.2.1). In particular our inductive types in FM inherit this action ‘for free’ (cf. 10.7), there is no need to inductively define it over the structure of individual types. So suppose x t is a term. We use this transposition action on t much as the reader may have used name-for-name substitution [ba], and indeed the two are equal if b is fresh and does not occur in t (cf. 11.1 for why we do not build FM and in particular Terms using [ba]). 3
xcV does not bind xc in V ; aVar(a) is not the same term as bVar(b).77 So the terms of correspond
to elements of the naïve datatype (D10.5.2) of -terms not up to -equivalence. Recall that the intended denotation of is untyped -terms up to -equivalence.
So, the Sanity Clause T21.9 states that contextual equivalence on closed values coincides with equality in our denotation. The language cannot access the name of an atom synthetically bound by an abstraction term-former a(), so that they really are in this (operational) sense ‘bound’. 3
We drive the point home. x FV(xV ) even for V CVal a closed value. xV is always an open term.
We use “reduced syntax”; term-formers take values instead of general terms wherever possible. So for example ( ) is a well-formed term (and value) and ( ) is not. We can use let x t in to recover expressivity. E.g. ( ) can be encoded as
let in let in ( )
I shall usually sugar nested lets to (expressions along the lines of) let in ( ) without comment. See e.g. (Concat)166.
Reduced syntax is useless for programming (we drown in Lets) though FreshML could be an intermediate language for some more user-friendly syntax. It simplifies the theory; sequential evaluation behaviour is concentrated in one term-former (let x in ). So for example in evaluation relation in Fig.36188 equation (149)188 is not
but the rather simpler Fst( )
C.f. R16.6.7 where we see the same principle of ‘avoiding conditions where possible’ appear in the context of implementing proofs in a theorem-proving environment. The difference is magnified every time we do induction over the evaluation relation, notably in the rather complicated and very important T27.14. 3
If t is a term, x Var a variable symbol and V a value then t[V x] (where [] denotes the usual capture-avoiding substitution) is a well-formed term. Furthermore, if U is a value then U [V x] is also a value.
By mutual induction on the reduced syntax of t and U , or alterna-tively ‘for free’ (D10.7.13).
22.2. Discussion.
Let us consider some likely-looking programs we can write in FreshML, some which we would like to be typeable and some not. 1 We can write the functions we used to biject [](X Y ) with []X []Y in C9.6.9:
(Bij1) fix f (x : [Atm]()) in fresh u in (uFst(x@u) uSnd(x@u)) (Bij2) fix f (x : ([Atm] [Atm])) in fresh u in u(Fst(x@u) Snd(x@u)) 2 We can write substitution Subst(t y)() on :
3 We can write “list concat” and using it a “list of free variables” function:
4 We can write a “body of an abstraction” function:
(FALSE BV) fix f (x : [Atm]) in fresh u in x@u
which should not type! u is chosen fresh so we need u#x@u for the function to have an informal denotation (T9.6.6), and this is not generally the case. The moral is
“We may invent abitrary fresh variable names but they must not escape the scope of their declaration.” Similarly we would expect (fresh u in u) not to type.
5 We can write a plausible (but we hope untypeable) “list of bound variables” function:
We have very simple pattern-matching in FreshML which does not include matching of abstraction-types, but the reader can see from the examples so far that we have been implementing it anyway by systematically using fresh u in () to invent a fresh variable and concretion ()@a to destroy the abstraction.
It does no harm to consider the same program written in the informal programming language of 4 using pattern-matching at abstraction types:
We would expect the typing system to reject this.
In 23.1 we inductively construct an apartness judgement in which is part of the the typing system (24) and rejects the undesirables from the list above.
23. Apartness judgements
23.1. Definition.
Recall from R9.2.10 that # is an FM version of “is not in the free variables of”, and a#x can be read as “a is synthetically bound/is not synthetically free in x”. Using the informal denotation we extend this terminology to FreshML and say that a is synthetically bound in the term aV . 3
The denotation of V @a is ⟦V⟧@⟦a⟧. In fact ⟦a a by R21.13 and I shall in future write a for both. By D9.5.14, x@a is defined only for a#x. This should be reflected in the language or there will be terms (such as ba@a for b a) that can have no denotation. Similarly, the denotation of fresh a in t is fresh a ⟦t⟧, and this is only well-defined when a a#⟦t⟧. Before a typing system we must develop some syntactic approximation to FM-apartness # (N9.2.4). It can only be an approximation because apartness at higher types in undecidable.
In the rest of this section we shall inductively define a syntactic approximation to apartness judgements and synthetic binding in FM as described in R23.1.1 and R9.2.10. We shall also call these ‘apartness judgements’, we write them
Γ t#xc
Their intended interpretation will be “In the context Γ# the possibly open term t does not contain xc synthetically free inside it”. The apartness context Γ# encodes information about the atoms synthetically bound in possible values for variable symbols, which may occur free in the term t. xc may be a variable symbol x (which we should imagine to be of type Atm) or an atom constant symbol a. 3
There are some subtleties to this. Consider the term
It should be the case that ⟦t⟧#⟦a⟧, but we can see that a occurs outside the syntactic scope of a in t. Hence, we cannot say “xc is synthetically bound if it occurs under the scope of a synthetic binder”, corresponding to “x is syntactically bound if it occurs under the scope of a syntactic binder”. Our decision to use reduced syntax (R22.1.7) forces let x in to be a primitive term-former, and this leaves us no choice but to have a cut-like rule (102)170 in the definition of the apartness judgements (Fig.32169 and Fig.33170).
An apartness context is a finite subset of (VarAtmC)2 written Γ# such that for all xc VarAtmC, (xc xc) Γ#, see R23.1.5 below. We write the set of apartness contexts Ctx#.
The intended interpretation of Γ#, abuse notation and write it ⟦Γ#⟧, is
3
Note that the definition of a typing context prevents (xc xc) Γ#. Since the informal meaning of (xc yc) Γ# is ⟦xc⟧#⟦yc⟧ allowing this would allow into our context. This is undesirable, cf. Item 2 of 23.2. 3
A apartness judgement is a triple
where Γ Ctx# is an apartness context (D23.1.3), t Terms is a possibly open term and xc Var AtmC is a variable symbol or atom constant symbol. We write an apartness judgement
Γ t#xc and read it “t is apart from xc in the context Γ#”.
The valid apartness judgements are inductively defined in Fig.32169 and Fig.33170 using the notation in N23.1.8. The intended meaning of a apartness judgement is
“values for variables ⟦Γ ⟦t⟧#⟦xc⟧ We shall write t#xc as t#xc where this is convenient.
There is now a clash of notation between Γ t#xc, read as above as “t is apart from xc in the context Γ#”, and x#y (N9.2.4) read as “x is apart from y”. I rely on the context ( of the discourse, not Γ#) to disambiguate. 3
We use the following shorthand notations in Fig.32169 and Fig.33170 and the development that follows:
1. We write xc for an arbitrary finite set of xc.
2. We write
3. We write
and
4. We write
5. We write
Γ xa#xc for Γ xa#xc and Γ xa#xc for Γ# xa#xc
but in both cases insist additionally that there is no za such that (xa za) Γ#.
6. We write
where [tx] is a substitution of x for t.
7. t[t’/z] normally denotes substitution of for z in t. In the case of (xa xc) in an apartness context only, (xa xc)[V z] shall mean (xa[V z] xc[V z]) only if V zc Var AtmC and otherwise (xa xc) (because it makes no sense to substitute a value not equal to an atom in an apartness context.
8. similarly for the expression xc[V z] in an apartness judgement Γ t#xc[V z].
9. If xc#Γ# we write
L23.1.9 below is rather more than enough to guarantee that (xc xc) Γ##xc and so this is well-formed. The following result generalises L12.4.2 although the proof is completely different.
If R X Y is a finite relation then a#R iff a#x y for all (x y) R.
As FM sets zc#Γ# iff zc xc yc for all xc yc Γ#.
L12.4.2 is a similar result for FMLtiny. It often happens that we know zc#Γ# because we pick bound variables fresh in expressions such as fresh x in t and (let x in ), cf. (72)94. E.g. in T23.1.12 below. We continue developing this in L24.1.5.
Now we prove apartness judgement weakening. We never use this result (although it is nice to know it is true). I use the proof to restate some of the points made in 12 about inductive reasoning in FM.
Please note! Here in T23.1.12 and often elsewhere I shall prove properties of an inductively defined X a subset of some D by induction “with inductive hypothesis (x)” (where x D). Often, (x) will be of the form x X (x); e.g. (113)172.
I really mean it. The property I prove of X is (x), not (x).78 However, in the proof itself I shall tend to elide complexities, e.g. compare (113)172 and (114)172. 3
By induction on Γ t#xc using induction hypothesis
(113) Γ t#xc Γ t#xc
We consider only the case of (99)169 in any detail. Suppose we know
(114) Γ t#xc and Γ
Now suppose t fresh x in .
Here is the point: Because we are using FM syntax, t is actually New(t) for t [Var]Terms—see the discussion of these issues in 12, in particular R12.1.3 and R12.3.2. (99)169 is shorthand for
(Real (99))
and so x is chosen new and apart from everything free in the current context, including x#t Γ (but not apart from t, which is not in the context, cf. R9.4.12). Item 5 of N23.1.8 states that for Γ##x and #x to be well-formed, we need x#Γ . We know this. So
Γ##x t#xc
We know #x is well-formed too and from its definition (Item 5 of N23.1.8) we have Γ##x #x and this gives us the result by the inductive hypothesis.
In a normal ZF presentation without some confusion might arise over whether x can occur in , since the only explicit condition on it is that Γ . Similarly for (102)170, where well-formedness of Γ x#xc follows from x#Γ, which is automatic because let x in is actually Let( t). In a ZF presentation we would need a side-condition.
I think the point has been made. Should the reader become confused in the more complex proofs to follow about newness, he or she is referred to the above as a prototypical example of ‘the genre’.
Having said this, case New in T23.1.14 below is significantly more sophisticated than anything we have seen until now. There we need to choose x fresh in fresh x in twice. We use (23)41 the first time to choose any fresh x, and use (21)41 the second time to choose the same x, observing that it is fresh for the context in which it is declared new the second time. See below.79
3
We need the following result for T25.6 (soundness of apartness wrt evaluation), L24.1.8 (typing substitution property) and also C24.1.9 (overall substitution property of typing/apartness judgements).
For V a possibly open value and t a possibly open term, if
z#zc t#yc and V #zc then [V z] t[V z]#yc[V z].
By induction on apartness judgements Γ t#yc using the hypothesis
(115) ycΓ t#yc Γ z#zc) V #zc [V z] t[V z]#yc[V z] 1 Consider the case (96)169. Suppose t xcW and suppose we have Γ yc zc such that
Because Γ t#yc holds it must be the case that
By induction hypothesis we have
[V z] W [V z]#yc[V z] If it happens that yc z and V xc then we can deduce
Γ[V z ] xc[V z ]W [V z ]#yc[V z ] by (97)169. Otherwise we can use (96)169.
2 Consider the case (99)169. Suppose we have Γ yc zc such that
We want to show
[V z] t[V z]#yc[V z] Choose x fresh such that t fresh x in . This means, by the existential form of (23)41 that we may assume x is apart from every variable in the current context, which includes Γ z yc and zc, and we do so. Because x is fresh, (fresh x in )[V z fresh x in [V z], so this equation really means
[V z] fresh x in [V z]#yc[V z] To prove this it suffices to show
The second part is easy because x is fresh. We now prove the first part. Since Γ t#yc we can resolve with (Real (99))173 using the universal form of (21)41. This tells us that for some #Γ t yc,
Γ## #yc We choose equal to the previous x.80 Γ##x (N23.1.8) is well-formed because x#Γ#, and furthermore x# zc. So x occurs in them nowhere (L23.1.9, C13.2.1 and L9.3.6) and
We quantified over the zc in the induction hypothesis (115)174 so we immediately have that
Now since x is apart from V and z,
and we have
[V z] t[V z]#yc[V z] as required.
3 Consider the case (102)170. Suppose we have Γ yc zc such that
and suppose t let x in ) for x fresh (so apart from z etc, but not because t is really Let( ). We want to show
[V z] t[V z]#yc[V z] First of all, because x is chosen fresh and x#t1 V ,
so this equation really means
To show this it would suffice to prove for some xc that
[V z] [V z]#xc[V z] and ( x#xc)[V z] [V z]#yc[V z]
Since Γ t#yc it must be the case that for some xc,
Γ #xc and Γ x#xc #yc
This first fact is a conjunction of judgements over all xc xc (N23.1.8) and because we quantified over the yc in our inductive hypothesis (115)174, we have
(115)174 for each. We can deduce
[V z] [V z]#xc[V z]
Recall that know Γ x#xc #yc—the comma is legal because x#Γ# (see N23.1.8 and C23.1.10). We can rewrite this:
We therefore have the inductive hypothesis for this too, so we can deduce
[V z] x#xc[V z] [V z]#yc[V z]
As we observed above, this is enough to deduce
[V z] t[V z]#yc[V z]
as required.
The other cases are longer or shorter, but they do not involve any new ideas.
23.2. Discussion.
Perhaps we should briefly run through these rules. We have not yet developed typing contexts (24) so we tend to consider closed terms. 1 Atom Constants. Obvious. Denotational justification L9.3.6.
But incidentally, why did we allow constants c AtmC in the language, seeing as they were so deliberately excluded from the language of FM? It was convenient to do so and did not compromise the design aims of FreshML (see 30.1 and R21.8).
2 Variables. Note that x#y y#x does not hold. Continuing R23.1.5 note that we can never deduce
The only rule that resolves against this is (87)169 and this has the side condition (x x) Γ#—but apartness contexts satisfy (x x) Γ# (see D23.1.3). x#x is nonsense denotationally81, so as in any logical system if we allow into our context we can anticipate trouble.82 We see this manifest itself in the technical details of typing (FALSE BV)166, which are dissected in a discussion culminating in (145)185.
3 Booleans. a#True for all a is equivariance (N9.2.8).
4 Natural Numbers. Similar to Bool. The case-destructor deserves some comment.
Note from Item 5 of N23.1.8 that Γ x#zc makes sense when (x zc) Γ# for any zc. Yet the rule itself has no side-condition to guarantee it. But this is automatic; being a bound variable symbol in a conclusion of an inductive rule, by R12.3.2 it must be chosen fresh for Γ V x xc and everything else in the context at the moment of choice. In other words, it is a ‘new’ variable and only because of FM may we be quite confident it does not matter which ‘new’ variable we choose.
The remaining issue is whether (Γ#)#x in FM implies the necessary side-condition. It does, we use C23.1.10.
5 Function Types. This is less obvious. f #a for f a function is not decidable, so we do not even try to capture the behaviour of FM apartness. The side-condition of (94)169 merely asserts “Γ f #xc when we can be completely and utterly certain that this is the case”.
Thinking in sets for a moment, note that a Supp(f ) for f xax even though for all x, a#f (x). Apartness rules based on ‘extensional application reducing to lower types’ would be false. In particular anything similar to this version of (94)169 is wrong:
(FALSE)
We pay a certain price for our uncouthness. For example, we cannot prove
(116) fix f (x : ) in Fst((0 a))#a
even though the atom a is clearly thrown away. More significantly, because the rule for application is equally crude, we cannot deduce
(117) (fix f (x : ) in 0) a#a
This means for example that for some ‘pretty printing’ function f taking closed terms in to de Bruijn terms expressed as elements of (Nat)List, we shall never be able to deduce
even though f (t) is a list of natural numbers and therefore has a necessarily equivariant denotation.83 We could extend the language with a rule stating that all terms of type Nat are apart from all xc of type Atm, but this brings problems of its own—we have no typing system yet, and if we can extend the language once, we can extend it again with exceptions which may allow calculations of type Nat to have nontrivial support (see [66, 8]). These issues are all further research (35).
6 Abstraction Types. Direct from L9.3.4 for (96)169 and L9.5.6 for (97)169.
7 Atom-Binding. Γ##x means “if x is new for the context Γ ”. t#x means “ and synthetically bound in the term t ”. The conclusion means “ then we can abstract over all new x”.
8 The other rules. I hope fairly intuitive.
24. Typing Judgements
24.1. Definition.
Typing judgements occur in a typing context ( Γ#). As usual is a finite partial function from term variables x Var to types . We call this the pure typing part of the typing context. Γ# is an apartness context (D23.1.3), which we shall call the apartness part of the typing context.
Γ# must satisfy the condition that for all (xc yc) Γ#,
Recall from R23.1.4 that the intended meaning of (xc yc) Γ# is ⟦xc⟧#⟦yc⟧ (N9.2.4).
Typing contexts will be written in list form
where x : indicates that (x) and xc#yc indicates that (xc yc) Γ#.
Typing judgements are 3-tuples (Γ t) where Γ is a typing context, t is a term, and is a type. We shall write them
They are inductively defined according to the rules in Fig.34180 and Fig.35181 using the notation of N24.1.2.
We say a term (or value) t is typeable in an environment Γ if there is a such that
We write for the set of closed terms typeable as . Similarly for .
Here is a thoroughly routine lemma (but it is useful):
For U a value and Γ a context then
1. Γ U : Atm iff U c AtmC.
2. Γ U : Bool iff U True or U False.
3. Γ U : Nat iff U or U Succ( (0)).
4. Γ U : iff U fix f (x : ) in t for Γ f : x : t : .
5. Γ U : iff U ) such that Γ and Γ .
6. Γ U : ()List iff U or U :: such that Γ and Γ ()List.
7. Γ U : [Atm] iff U a for Γ .
8. Γ U : iff Var,App or U Lam() for Γ [Atm].
The right to left implication is in every case trivial by the typing rules.
The left to right implication follows by induction on the typing relation with induction hypotheses precisely equal to the implication. We prove the cases one at a time in sequence, since we need the case of [Atm] and to handle .
The following lemma does for typing what C23.1.10 did for Γ# and L12.4.2 before it did for Γ in FMLtiny.
If Γ#) is an ordered pair of finite relations then a#Γ if and only if a#x y for all (x y) and all (x y) Γ#.
We need L24.1.5 in the development to follow, but we saw this kind of thing twice before in FMLtiny and 23 and I shall no longer necessarily make a meal of it.
For all Γ, t, and xc, if
Γ t : and Γ t#xc
then xc Dom() AtmC.
By induction on Γ t#xc using the hypothesis
For Γ t and such that Γ t : ,
By induction on Γ t : using the hypothesis
The design choices that ensure this theorem holds are that is labelled with a type, as are values of function-type fix f (x : ) in t. It would be more friendly for the user not to have to supply these type annotations, but harder on whoever is reading this proof, because non-uniqueness of typing makes it slightly more complex. For a simple example see R26.4.2.
For t a term and V a value such that
Γ z : #zc t : and Γ V : #zc
it is the case that
By induction on typing judgements Γ t : using the hypothesis
(144) Γ t : z#zc) V : #zc
Consider the case (128)180. Suppose t xcW and suppose we have Γ such that
Because Γ t : holds it must be the case that for some type ,
By induction hypothesis we have
[V z] W [V z] : and [V z] xc[V z] : Atm
We can then deduce
[V z] xc[V z]W [V z] : [Atm]
Consider the case (129)180. Suppose t W @xc and suppose we have Γ such that
Because Γ t : holds it must be the case that
Γ W : [Atm] and Γ W #xc
By inductive hypothesis and T23.1.14 we know
[V z] W [V z] : [Atm] and [V z] W [V z]#xc[V z]
It follows that
as required.
Consider the case (133)181. Suppose we have Γ such that
We want to show
Now choose fresh x apart from zc z , with t let x in . Then (let x in )[V zlet x [V z] in [V z]) so this equation really means
To show this it would suffice to prove for some xc and that
[V z] [V z] : #xc[V z] and ( x : #xc)[V z] [V z] :
Since Γ t : it must be the case that for some xc,
Γ #xc and Γ x : #xc
This first fact is a conjunction of judgements over all xc xc (N23.1.8) and we have the inductive hypothesis (144)183 for each. We can deduce
[V z] [V z] : #xc[V z]
We also know Γ x : #xc . We have the inductive hypothesis for this too,84 so we can deduce
[V z] x : #xc[V z] [V z] :
As we observed above, this is enough to deduce
as required.
For t a term and V a value such that
Γ z : #zc t : #yc and Γ V : #zc
it is the case that
Γ[V z] t[V z] : #yc[V z]
24.2. Discussion.
Now that we have typing judgements we can type the example programs of 22.2. Going through them on paper would take far too much space. Let us briefly consider (Bij1)165:
t fix f (x : [Atm]()) in fresh u in (uFst(x@u) uSnd(x@u)) We wish to type this as a closed term:
so we resolve against (126)180 to strip the function-abstraction and obtain
f : [Atm]() [Atm] [Atm] x : [Atm]()
fresh u in (uFst(x@u) uSnd(x@u)) : [Atm] [Atm] We resolve against (130)180 and obtain the following proof-obligation:
f : [Atm]() [Atm] [Atm]#u x : [Atm]()#u u : Atm
(uFst(x@u) uSnd(x@u)) : [Atm] [Atm]#u This is shorthand for two obligations (see N24.1.2), a pure type judgement and a pure apartness judgement. I leave it to the reader to work through the rest of the details, they are not difficult.
More interesting are the FreshML terms which do not type, since it is they who cause all the trouble with “how do we know it does not matter which new name we pick” in naïve ZF-like theories of binding. Consider (FALSE BV)166: fix f (x : [Atm]) in fresh u in x@u We try to type it just as above and eventually reach the following obligation:
The problem is the apartness judgement, which we now separate out:
The only rule we can resolve with this is (98)169, which gives us the obligations
(145) Γ x#u and Γ u#u
We can discharge the first with (87)169 since (x u) Γ#. We can never discharge the second, see Item 2 on p.176.
The other ‘false’ programs fail to type for the same reasons, and this is good. However, sometimes the logic of apartness judgements is less powerful than we might like. For example (116)177 fails to type because (104)170 is too crude and does not break V into ( ) even though it could. But we were asking for trouble writing such a silly program. (117)177 is more serious. It fails to type because we have no way of expression in the type system that “f is such that no matter what the support of the argument x, f (x) has no support”. For similar reasons, considering (Subst(t y))166, we cannot deduce (FALSE) t : #u s : u : Subst(t u)(s)#u In conclusion, apartness judgements are not too bad on datatypes but hopeless on functions. Cf. 30.3.
Since the typing system has this weakness at higher orders, should we worry that the Sanity Clause T21.9 is not significant for future more sophisticated languages where better behaviour at higher-orders strengthens contextual equivalence? Actually, not necessarily. In contextual equivalence we quantify over all possible contexts C []. So if C [] contains function applications such that C [t] refuses to type, a Kleene-equivalent form [] without the applications may well still do so. Of course FreshML is no good for programming, but we knew that already.
On the other hand, perhaps things are not that bad for programming either. Perhaps in FreshML a slightly different method of programming is more appropriate. Perhaps, instead of passing the atom name to Subst ‘naked’, we should bind it in the argument instead. What does this mean? Consider the following:
((t)) fix f (x : [Atm]) in fresh v in Case x of
Even in our weak typing system, we can deduce (VALID) t : #u s : u : Atm Subst(t)(us)#u But this is an unfinished story which I cannot tell here.
From now on we will show fewer examples and concentrate on developing the operational theory of the language, culminating in the Sanity Clause in 29.
25. Evaluation
We use the standard abbreviation
for nested let-expressions, for example in (147)188.
However, the following at least is true:
For all values V and ,
Let us just explore these rules a little.
We use let x V in t to carry out substitutions ‘within the syntax of the language’ rather than the ‘meta-level’ alternative t[V x]. This is nonstandard. For example, the standard presentation of the rule for applications would be
Now this is written in nameful style (R4.14) which as discussed in R12.6.5 really means
f
However, I have chosen to use the equivalent rule
which is really
f
This leaves the question of why I use the nonstandard formulation using Let instead of @@. My instinct is that if this proof were implemented in a theorem-proving environment (31), the form I select would be easier to work with. Cf. also R19.2.4.
The reader is also invited to compare the phrasings of (148)188 and (75)97 in the light of R12.6.5 (the two rules correspond in the sense that they are where I have concentrated -reduction). 3
For t a closed term and V a closed value, if
t V and Γ t#yc
then
Γ V #yc
By induction on the evaluation relation with inductive hypothesis
We consider only one case, (148)188.
Suppose t V . Suppose we have Γ yc such that
Γ t#yc
Now we choose a fresh x such that t let x in . ‘Fresh’ means x is apart from all variables in the current context which includes Γ V and yc.
There must exist such that
and [x] V
Then it must be the case that there is some xc such that
Γ #xc and Γ x#xc #yc
We have the inductive hypothesis for each judgement Γ #xc for xc xc so from this first fact follows
Γ #xc We can also apply T23.1.14 to the second fact and deduce
Γ#[V x] [V x]#yc[V x] However, x was chosen apart from Γ# and yc so it does not appear in Γ# (L23.1.9) and is not equal to yc (L9.3.6) so this is just
Γ [V x]#yc We can now apply the inductive hypothesis again to deduce
Γ V #yc as required.
For t CTerms a closed term and V CVal a closed value, if
t V and Γ t : then
26. Bisimulation and Contextual Equivalence
26.1. Basic Definitions.
Consider a context Γ as a list:
We write (xc) for if xc Dom() and Atm if xc c AtmC. We equate functions Dom() CVal with lists of closed variables of length n.
Then we say ) is a Γ-closure when m n, and for 1 i n,
and for each (x yc) Γ#
Write the set of Γ-closures as
Closures(Γ)
If Γ t : and Closures(Γ) we write t for t[] and call this a closure of t.
The intended meaning of Closures(Γ) is
“The are possible values of the in Γ. t is therefore the closed term obtained by instantiating the accordingly.”
Let denote the set of type-respecting relations
Given R we write
When (t ) R(Γ) we write
When we wish to include the condition that Γ t #xc we write
Γ t R #xc
We write for the subset of of such relations on closed terms.
We introduce so to conveniently talk about relations between terms-in-context of the same type. Since only these relations interest us, all relations on terms-in-context are henceforth type-respecting. A corollary of this is that if Γ t R holds, it must be the case that Γ t . 3
Now T24.1.7 tells us that the typing of a term in a given context is unique if it exists, so actually the in Γ t R is redundant. We leave it in anyway, except in the case when , i.e. the terms t are known to be closed. In that case we may abbreviate
Γ t R to t R
Evaluation as a relation is in (D26.1.2).
So when we write t V we may assume they have the same type.
26.2. The Relation ctx.
Contextual equivalence is traditionally defined using ‘contexts’ with ‘typed holes’, []. Call this the “context-and-hole approach”, as opposed to the “adequate-congruence approach”
used in D26.2.2. The problem with contexts-and-holes is that they are usually only informally defined; see [64, p.250-252, ‘PCFL Contexts’] (the paper on which my overall method of proof is based) or [63, p.4 Def 2.1]. What do I mean? For example, hardly anyone gives a complete grammar for forming contexts. If I followed contexts-and-holes I would have to choose to either render it impossible from the start to prove T21.9 with complete rigour by using a hand-wavy definition of contexts, or to give a proper grammar for them. The latter choice amounts to the adequate-congruence approach I have followed, with one important philosophical difference: adequate-congruences bring contextual equivalence in line with the relations it is eventually proved equal to (C28.24)—a (co)inductively defined relation on syntactic datatype.87 3
(D26.2.2) is transitive and reflexive.
The method is standard. For reflexivity it suffices to show that the identity relation is an adequate congruence. It is certainly a congruence (Fig.37193), so we consult D26.1.6 and see it is adequate as well.
For transitivity we must apply the same argument to the set
Again, this is an adequate congruence.
We shall not pursue the contextual preorder immediately. Instead we shall define a notion of bisimulation on terms-in-context, first between closed terms and then extending to open terms by syntactic instantiation of free variable symbols with closed values. Ultimately, we shall seek to prove that the bisimulation defined below (, D26.4.1) and the contextual preorder defined above (, D26.2.2) coincide.
26.3. The Equivalence se and the Relation kl.
We devote a short subsection to and . is a technical construction which will soon be useful, specifically in T26.4.7 and T27.11. is a standard relation which we take the opportunity of this clearing in the mathematics to introduce.
Let be the least equivalence relation on closed values of type that is a congruence and satisfies the following rule:88
If two values V are such that V we say V and are synthetically equivalent.
The relation of D26.3.1 above is an equivalence relation.
In C9.4.5 we proved that (x Φ) (x Ψ) x (Φ Ψ), and this suffices to establish the result.
Actually, we proved back in T8.2.5 (before any of this theory) that coincides with -equivalence on untyped -terms, which itself coincides with equality in the denotation L (-terms up to -equivalence, D10.3.4) by the general nonsense of T10.5.8.
Why do we not simply write ? Because -equivalence on terms of FreshML is a completely different creature to do with FreshML variables, and nothing to do with atoms in FM represented in the language by a AtmC (and variables x : Atm). So we needed a new symbol for the concept. 3
We also define the Kleene ordering on closed terms-in-context, written as follows:
We write s t : when s t : and t s : .
is transitive and reflexive.
Easily from the definition D26.3.4.
26.4. The Relation .
Recall that is a type-respecting relation on closed terms-in-context (see D26.1.2), which means that judgements should be written
for appropriate . However, because of T24.1.7 (type uniqueness) we can deduce from s or t, so we just write
Bear in mind that we can deduce from the judgement s t that s and t are closed typeable terms of the same (unique) type. 3
implements a notion of equivalence on terms based on ‘reducing’ a term’s type (by evaluating it and attacking the value’s structure in a manner appropriate to the type) until we can do so no longer, and then observing the result. Then the coinductive definition expresses the slogan
“s t when any behaviour s can display, t can display.”
3
is equivariant:
To prove this we jump all the way back to Chapter II and L8.1.12. In the terminology of that lemma is an unparameterised 0-ary function-constant and by that lemma (a b). is equivariant so
Permutation commutes with pairset by R8.1.13 so we are done.
is transitive and reflexive.
We observe that the set
is a post-fixed point of Φ, as is the set
The following technical lemma is one half of T26.4.7:
For t a closed term and U a closed value respectively,
The main use of the following theorem is in T27.11, a corresponding result for .
The results to be proved are all of the form A (B C ), so split into two implications. Those of the form A (C B) follow from L26.4.6 above. So now we may assume this and proceed to prove the A (B C ) part.
Each case is by induction on the typing Γ U : using the predicate A (B C ) as induction hypothesis. We use L24.1.4 to relate the type to the syntactic form of U , L25.4, and the fact that Φ(.
1 Consider the case of Nat. By induction on the typing Γ U : using induction hypothesis
So suppose U : Nat. Then by the typing rules it must be the case that
for Nat. We treat only the second case. Since Φ( we know
Let be one such. Since we know by L26.4.6 that and hence by L25.4 that . So V Succ( U and t U as required. We consider only one other case, the only one of any novelty.
2 Consider the case . L24.1.4 has three possibilities for U : ; U Var(a), U App( ), and U Lam(a). We consider only this last one.
So suppose
By this third fact we know there is some value V (which is of abstraction type and so by L24.1.4 is) of the form b, such that
t Lam(b) and a b
We follow back and deduce that
By L25.4 and the induction hypothesis we can deduce
Recall from the definition of (D26.3.1) that this is precisely the condition for
This gives us the result.
The relation is a subrelation of . That is, .
If s then s t t, and similarly if t .
We shall need the following result to prove the very similar, but much more complex, T27.14.
For all closed terms t and values V if
t V and t
then there exists some such that
and V
We draw a diagram of this result because it is important.
26.5. The Relation .
Recall we defined Γ-closures in D26.1.1 and the set of type-respecting relations in D26.1.2.
Consider R a relation on closed terms-in-context. We can extend it to an open extension R on possibly open terms-in-context as follows:
precisely when for all Γ-closures ,
1. R inherits transitivity and reflexivity from R if R possesses these properties.
2. R and R coincide on closed terms.
3. If R S then R S o.
By unpacking D26.5.1 above.
Let be the open extension of (D26.5.1).
By L26.5.2 inherits reflexivity and transitivity from .
3
If Γ t then Γ t .
For t CTerms and a type, if t then
Direct from L26.5.2.
We shall use this later.
is adequate (D26.1.6).
Let be the open extension of . It too inherits transitivity and reflexivity from and coincides with it on closed terms.
We can usefully lift more properties to the open extensions.
is a subrelation of . That is, .
Inherited from L26.4.8 ().
This result underlies L27.13, where we use it to switch between -equivalent terms on the left of . Cf. R26.4.10.
If Γ s then
and similarly if t .
For U and values, if
Γ U Γ U #xc and Γ u : #xc t
then
(U and must be values to guarantee that t[U u] and [u] are terms in our reduced syntax, see T22.1.8)
From D26.5.3 (def. ).
26.6. Pause for Breath.
Between us here and 28, that is 26.7 and 27, is a considerable mass of inductive proofs. Perhaps we should consider where we are and where we are going.
We know very little about beyond its definition, that it is the largest adequate congruence (D26.2.2). We certainly have little idea about its properties on closed values of type , which is what the Sanity Clause (T21.9) is all about. Using our current terminology, the theorem states that on closed values of type , and -equivalence coincide (R26.3.3).
Now from Fig.39198 and T26.4.7 we know a lot about on . The relevant line of the figure is
In the case that t is a closed value V it evaluates only to itself by L25.4, so this equation becomes precisely the Sanity Clause:
Seeing as we want to prove the Sanity Clause, wouldn’t it be convenient if on closed values of type ? Well, we could prove this if we knew (D26.5.3) since by L26.5.6, and coincide on closed terms.
(D26.2.2) is coinductively defined so we show (D26.5.3) is closed under its rules and we have . is a congruence and adequate. We already proved is adequate in L26.5.7, but we do not know it is a congruence. This is rather hard (it all comes together in the end of the proof of L28.16).
For the converse , we shall show in L28.19 that is its own open extension. Meanwhile is the open extension of the coinductively defined (D26.4.1). Set inclusion is preserved by taking open extensions (L26.5.2) so it suffices to show that restricted to closed terms is contained in (L28.20), which means proving it is closed under the monotone operator Φ (Fig.38196) used to coinductively define . We do this after a few preparatory lemmas in C28.24.
With reference to R26.2.3, this proof method is only possible because we constructed coinductively.
In theory the method is simple. We define another relation using , show one-by-one that it inherits all the good properties of , but also that it is a congruence. We then use these good properties to show they are equal. This is important: most of the results to follow are just results about , repeated for and the reader is invited to use this correspondence to understand the structure of the proof. The only results not lifted from the theory of are T26.7.4 () and of course L27.10 ( congruence).
It is quite easy really, but checking all the cases does take up a lot of space. I advise the casual reader not to take anything between now and 29 too seriously, since I would much prefer them awake.
26.7. The Relation .
We need the following lemma in the case [Atm] of T27.11.
If
then
For all , and Γ such that
it is the case that
By induction on , using transitivity of (R26.5.4).
For all t and Γ, if Γ t : then
By induction on the derivation of Γ t : , using reflexivity of (R26.5.4).
If Γ then Γ .
From the nature of the inductive rules defining , using the corresponding result, evident from D26.5.3, for .
27. Proof of and hence congruence
For U and values, if
Γ U Γ U #xc and Γ u : #xc t then
(U and must be values to guarantee that t[U u] and [u] are terms in our reduced syntax, see T22.1.8.)
By induction on the derivation of ∆ t (due to the syntax-directed nature of the rules this is similar to induction on the syntax of t) with fixed U and inductive hypothesis
In the proof below I shall elide ∆and the universal quantifier, assuming ∆= Γ u : #xc from the start, effectively working with an informal hypothesis of the form
We consider only a smattering of cases.
1 Suppose t xc. Then the result follows directly from a corresponding result for , L26.5.11.
2 The cases t True False 0 are trivial.
3 Suppose t Case V of 0 Succ(x). We suppose that
Γ U Γ U #xc and u : # Γ t Using (187)204 we know there are t t yc and such that
u : #xc Γ x : Nat#yc t : and
and that
(205) u : #xc Γ Case V of 0t Succ(x)t
By inductive hypothesis we conclude that
Γ [U u] t[u] : and Γ x : Nat#yc [U u] t [u] :
and from (205)207 we can use the definition of to deduce that
The result follows by the definition of .
4 Suppose t fresh x in s. Suppose that
Γ U Γ U #xc and u : # Γ t We resolve with (199)205 and deduce the existence of an such that
Γ#x : Atm s Γ#x : Atm s #x u : #xc Γ fresh x in By induction hypothesis we know that
Γ#x : Atm s[U u] [u] : and Γ#x : Atm s[U u] [u]#x and by the definition of we know that
Γ fresh x in [u] [u] : The result follows by the construction of (D26.7.1).
5 Suppose t fix f (x : ) in s. Suppose that
We resolve with (202)205 and see that
and the side-condition of (202)205 holds. We can now apply the induction hypothesis to conclude
and since the appropriate side-condition still holds for these new terms, we can deduce the required result.
Unlike , the relation is a congruence:
restricted to closed terms satisfies all the lemmas of given in Fig.39198. In full this means:
1. For B one of True and False (so a value), if B Bool then B.
2. For N a value, if N Nat then N .
3. If aW [Atm] then there are , such that and for c new (c a)W (c ) .
4. For L a value, if L then there is a value L such that .
5. If ()List then .
For :: a value, if :: ()List then there exist values V such that , ()List, and ::
6. For P ) a value, if P then there exist values P P such that (P P) and P : for i 2.
7. For F fix f (x : ) in s, if F then there exists fix f (x : ) in such that and for all U ,
In view of L26.5.6 ( and coincide on closed terms) we shall use and synonymously on closed terms. 1 Type Bool. Suppose B True Bool. We resolve with (182)204 and deduce
True Bool
Since and True are closed terms it follows by L26.5.6 ( and coincide on closed terms) that
True Bool
Finally by T26.4.7 we know that True. The case B False is similar.
2 Type Nat. We work by induction on the derivation of using the hypothesis
We do only one case, that of N Succ(M ). Suppose
N t : Nat
It must be the case that for some ,
M Nat and Succ() t : Nat
By induction hypothesis we know M and, these both being values, M . From T26.4.7 it follows that
as required.
3 Type [Atm]. Suppose we have aW [Atm]. We follow back the deduction of and deduce the existence of a such that
W and a [Atm] We apply T26.4.7 ( on values) to this second fact and deduce the existence of and a new c such that
We also know from L26.7.2 ( equivariant) and W deduced above that
We can now apply T26.7.4 () to obtain the desired result.
4 Type . By induction on using the hypothesis
We do only one case, the more subtle one. Suppose
Then by L26.7.8 and the structure of the typing rules we know
We resolve with (193)204 and deduce that for some a,
M [Atm] and Lam()
We apply T26.4.7 to this second fact to conclude that for Lam() and some ,
t and
From the first fact on the other hand we can follow back and see there is some a such that
U : and [Atm]
By induction hypothesis on this first fact U and therefore
( is a congruence by construction). By the second fact and T26.4.7 we know
so by L25.4
so
L
is transitive, so from L we deduce L , as required.
5 Type ()List. The first case is similar to the boolean one. Consider the second. Suppose
:: ()List We resolve with (196)205 and deduce there exist V and such that
V : V : ()List and
V :: ()List By T26.4.7 we know there exist V such that and V :: We now apply T26.7.4 to obtain the result.
6 Type . As for the second case of list types above.
7 Type . Suppose F fix f (x : ) in s . We resolve with
(202)205 and deduce that there exists an such that
and
We apply L27.10 and deduce
We also use T26.4.7 to deduce that exists such that
fix f (x : ) in and for all U
(fix f (x : ) in )U (fix f (x : ) in )U : It only remains now to use the case of function application in L27.10 to also deduce that
(fix f (x : ) in s)U (fix f (x : ) in )U : and apply T26.7.4 () to complete the result.
For a type a and values V , if
then V and have the same top-level term-former.
Directly from T27.11.
The following is a technical result which bridges a slight mismatch between the form of Φ at function types in Fig.38196 and the form that would be most useful in the case of function application in T27.14. It is not a case of L27.10.
If
and
then
Recall C26.4.11 and (180)200. restricted to closed values satisfies a similar property:
For t a closed term and V a closed value, if t V then for all , if t then there exist such that
By induction on t V . In the light of L26.5.6 ( and coincide on open terms) we shall use the judgements t and t synonymously. 1 If t V there is nothing to prove.
2 Suppose t if True then else and suppose t V . Therefore V . Suppose also t and V : . From (184)204 we see there exist t t such that
and
if then t else t
By C27.12 we conclude that True.
Now we know V and t : , so we can apply the inductive hypothesis to deduce that there is some V such that t and V .
Furthermore we know
t if True then t else t and t
so we know by C26.4.11 that for a such that V . We now use T26.7.4 to complete the result.
3 The case t if False then else is similar.
4 We skip to the case t Case U of 0 Succ(x) where U Succ(W ). Suppose
So t, t and must exist such that
and
We apply T27.11 to this third fact and deduce that U .
Now we know t V , so we follow the evaluation relation and see that
We use L27.10 to deduce
(recall that U Succ(W ) and using the induction hypothesis we know there exists V such that let x W in t , and V .
Following the same pattern as the previous case, we know
and using L26.4.8 () and R26.5.4 ( transitive) we deduce
From this, let x W in t , and C26.4.11 we conclude there exists a such that and
We apply T26.7.4 to obtain the desired result.
5 Suppose
where U Lam(aW ) and suppose that for some V and ,
We follow back and deduce that there exist t , t, t and such that
and
(206) (x : [Atm]#xc t : )
We can now use L27.10 to deduce that
We know from the evaluation relation that let x U in V , so we apply the inductive hypothesis to conclude that for some ,
Now we know let x in t from L26.4.8, and the fact that U and have the same top-level term-former (C27.12). We can apply C26.4.11 to let x in t and let x in t to deduce the existence of such that
and
We now apply T26.7.4 to obtain the desired result.90
6 Suppose t R U where R fix f (x : ) in s). We assume
From this second fact we deduce values fix f (x : ) in and exist such that
and
We use L27.13 (the hard work of this case is hidden in that lemma) to deduce that
From t V we can deduce that
By inductive hypothesis therefore we know that there is some such that
Since respects -equivalence (L26.4.8) we know from that
and hence, by C26.4.11 we know there is a value such that
and
It remains only to apply T26.7.4 () to complete the result.
7 Suppose t fresh x in s. Suppose also that
From this second fact we deduce the existence of an such that
x : Atm s x : Atm s #x
and
fresh x in
Now we follow back the evaluation relation and deduce that for a new c,
For this new c it is also the case, by T27.9, that
So by induction hypothesis there is some such that
Now we also know that [cx] fresh x in , so we can apply C26.4.11 as in the previous cases and deduce the existence of a such that and , which gives the result using T26.7.4 as in the previous cases.
8 Suppose t :: and t V . Since t is already a value, t V . Suppose further
t ()List
Then there exist V such that
V : and V ()List
and
V :: ()List
We use L27.10 to deduce t :: V :: ()List and proceed using C26.4.11 and T26.7.4 as in the other cases.
9 Suppose t U @c for U a value. Suppose further that
We follow back and deduce the existence of a such that
U [Atm] and @c We use L26.7.8 and L26.5.5 and the typing rules for concretion to deduce that U #c.
We can now apply L27.10 to deduce U @c @c : and then proceed using C26.4.11 and T26.7.4 as in the other cases.
The relation coincides with .
We have already shown in L26.7.6, so we need only establish the reverse inclusion. It suffices to show this inclusion on closed terms only, because is defined in terms of relating closures of terms with appropriate (D26.5.3), and enjoys the same substitutive properties (T27.9).
So we need to show on closed terms. To do this it suffices to show that restricted to closed terms is a post-fixed point of the operator Φ used in Fig.38196 to coinductively generate . This follows from T27.11 and T27.14.
28. Proof of ctx
contains .
(D26.5.8) is a subrelation of .
If Γ s then
and similarly if t .
Now for a useful corollary of C28.18:
Write for restricted to closed terms. Then , the open extension of (D26.5.1), is equal to .
The only difficulty in this proof is the number of definitions and lemmas we must unpack. We prove the two inclusions and separately.
By L26.5.2, coincides with on closed terms, so it is adequate (D26.1.6) because is. From the definition of an open extension in terms of closures we see that is a congruence (N26.2.1). Since is the largest adequate congruence, we know .
For we use the power of let x in to carry out ‘by hand’ the instantiations of free variables executed by a closure . Suppose Γ is some context with () () and
Γ s ctx t :
and suppose ) is a Γ-closure (D26.1.1). By applying the rules of Fig.37193 repeatedly we can deduce that
Γ (let x V x V1 in s)
By C28.18 we have
But on the closed terms s and t. was an arbitrary closure so we can quantify over it. Thus if Γ s t : then for all Γ-closures Γ s t : , and this means precisely
Γ s ctx-cl t :
So as required.
This gives us what we were after:
If restricted to closed terms is a subset of then .
In the case that two terms s t are closed we can use N26.1.4 to write s t : as s t. In the light of this and the results above we shall abandon the notation and write s t as s t.
Every type is populated by a closed value; there exists some V CTerms such that
By induction on .91
If s t CTerms are closed terms and
s t and s U then there is some V such that
t V and U V
It follows from the rules in Fig.37193 that
s t let x s in True let x t in True By construction is adequate (D26.1.6) so let x s in True True (and it does) then let x t in True True. It follows from the evaluation rule for (let x in ) (148)188 in Fig.36188 that t evaluates to some value V . Then U V from C28.18.
and coincide.
is L28.16. To show it suffices by L28.20 to show that restricted to closed terms (call this restriction , see N28.21) is a subset of . We can show this by proving that is a postfixed point of Φ as defined in Fig.38196. Since all terms we consider are closed we use N26.1.4 to write s t : as s t.
Suppose s t. We seek to prove (s t) Φ(). If s does not evaluate then (s t) Φ() automatically from the definition of Φ. So we suppose s U and work by induction on U . 1 Suppose s True. Since is adequate (D26.1.6) it follows that t True. Similarly for False.
2 Suppose s 0 Succ(N ) for N : Nat. Since is adequate, t N . This settles the cases s 0 and s Succ(U ).
3 Suppose s c for c AtmC. We use L28.23 and deduce there is some d AtmC such that t d and c d. We now apply the rules of Fig.37193 and deduce
if c c then True else False if d c then True else False is by definition adequate so if the LHS evaluates to True, and it does, then so must the RHS. From this it follows from the structure of the evaluation rules that c d, as required.
4 Supposes U ::. We use L28.23 and deduce there is a value V :: or V such that t V and U V . Using Fig.37193 we deduce
Case U of B :: Case V of B ::
where B is some value of type (L28.22).
We use L28.23 again, combined with the evaluation rules, to deduce that V :: and
U1 ctx V1
We may similarly deduce that U V2.
The cases U and U Var() App() Lam() are similar and easier.
5 Suppose s U ). We use exactly the same argument as in the previous case. We apply L28.23 to deduce there exists a V ) such that t V . We then use Fig.37193 we deduce
Fst(U ) Fst(V )
From this, using L28.23 once more and the evaluation rules, it follows that
U1 ctx V1
We may similarly deduce that U V2.
Recall that we are proving that is a post-fixed point of Φ defined in
Fig.38196. The pattern of proof is precisely the same as in the previous cases, so from now on we simply give the appropriate ‘context’, built using the rules of Fig.37193, that verifies the conditions of Fig.38196 for each possibility for U .
6 Suppose s U fix f (x : ) in . For all W we have
UW VW
7 Suppose s U a. For new c and V b,
U @c ctx V @c
We then apply L28.23 and deduce
(c a) (c b)
as required.
29. The Sanity Clause, proved
Let us go back now and finish what we started in 21:
The syntax of FreshML is defined in 22.1.
The typing rules are defined in 24.1.
The evaluation rules are defined in 25.
The contextual preorder is defined in 26.2.
-equivalence on closed values of the type (recall, representing possibly open terms of the untyped -calculus), written , is defined in D26.3.1.
Given this, for all closed values U V CTerms such that U V : ,
FreshML is intended as a prototypical example of a language with the features that FM (Chapter II) inspires, as well as providing the object of a particularly large case-study in inductive reasoning in FM. The Sanity Clause brings this all together by proving, using FM, that a language it has inspired really does represent it in a ‘sane’ way.
30. Questions
30.1. ML-style evaluation?
FM set theory has no constants of type and FreshML has constants a b c AtmC of type Atm. So we may wonder:
“We use ‘equivariance’ in L26.7.2 yet T9.1.6 (equivariance FM) depends—simplistically put—on there being no constant symbols in in the language of FM. Isn’t there something wrong here?”
The technical answer is:
“No. FreshML is modelled as an object-language inside FM set theory, and therefore has no connection with the language of FM itself.”
But the relation of FreshML and FM is a little incestuous. After all, we began our discussion of FreshML in 21 by suggesting terms could denote functions in FM set theory. If the denotation of the FreshML constants of a b c AtmC is not FM constants a b c AtmC—then what is it? The technical answer above says, correctly, that they are FM variables ranging over the set AtmC just as x y z range over Var.
Still, we could eliminate syntactic constants symbols a b c AtmC, they would be replaced by syntactic variables x y z :Atm in the typing context. (163)188 would change because c AtmC is outlawed. Evaluation would carry an ML-style evaluation context associating to some variables x Var constants a AtmC, and our notion of ‘closed value’ would change accordingly.
But FreshML was never designed from programming. It was designed for proving the Sanity Clause (29). I did not want labelled evaluations and ‘closed’ values that actually contain free variables in my proofs.
30.2. Combine typing and apartness?
We defined apartness judgements first and then used them to define typing judgements (23 and 24). Why not combine them and define them together? I.e. why not take the judgement
Γ t : #xc as primitive, not shorthand (Item 1 of N24.1.2).
We can do this but it causes problems. Because , , , and are all defined on typeable pairs of terms of the same type, if apartness and pure typing judgements are defined together we carry apartness judgements #xc in all the inductive and coinductive reasoning on types. Now we can always strengthen our inductive hypothesis and universally quantify over xc where necessary. I have tried this. However, the ‘black lace’ effect of a hundred ‘#xc’s on every page was most unpleasant, and since I have proved what I need without doing this, it is also demonstrably unnecessary.
30.3. Incorporate apartness into types?
We could extend the typing system to include types like #xc #yc. We could then type
and use this to deduce
We might similarly be able to type ‘silly’ (but acceptable) functions like (116)177 and not-so-silly functions like the pretty-printing function mentioned just below
I have tried designing such a type system, it turned out to be rather complicated. We should be mindful of this idea for future languages, if only to understand why it might be impractical. In ((t))186 I hint at how this complexity may be unnecessary after all.
30.4. Define # ‘co-inductively’?
That is, instead of taking the basic apartness judgement to be t#x, why not take it to be (t#x) or—loosely speaking because t is in FreshML not FM—x Supp(t).
The reader is welcome to consider Fig.32169 and Fig.33170 and think how we might reformulate them in terms of these ‘negative’ apartness judgements. Let us write a x for a Supp(x). Should we change apartness contexts to Γ, finite sets of ordered pairs written x y, so an apartness judgement Γ t xc means “if y Supp(x) for all (x y) Γ then xc Supp(t)”?
We might even keep Γ# but make apartness judgements of the form Γ t xc, meaning “if x#y for all (x y) Γ# then xc Supp(t)”.
I shall make just these two remarks:
The natural thing to have on the right seems to be #. Consider the condition Γ yc#xc in (98)169.
The most natural thing to have on the left seems also to be #. Consider the contexts Γ##x in (99)169 and Γ xc#yc in (100)169.
31. FreshML and automation
In conclusion there are a few points I would like to make about the Sanity Clause (T29.25) and automation, particularly in Isabelle/FM (Chapter III).
1. Chapter IV cries out to be automated. It is long, it is complex, it has a lot of relatively trivial cases. Has the reader checked every line of this proof? If so, can they guarantee that they are correct? What? That is my responsibility? And why believe me? So the size and yes, monotony of this proof invites automation. The reader is also invited to observe that (thanks to FM) every proof we have seen is by strict induction or coinduction (as appropriate) on a (co)inductively defined set.92 By ‘strictly’ I mean that I never used any subsidiary ‘renaming’, ‘weakening’ or ‘congruence’ lemmas. For example, we prove T23.1.12 but never use it.93 The proofs are always the same: apply the (co)inductive principle and then resolve away the subgoals until there is nothing left. In other words this whole proof is no more than standard resolution-based theorem-proving, but carried out on paper instead of a computer.
Note also that this uniformity is characteristic of syntax without variable binding, but has been conspicuous by its absence from developments of syntax with binding. The fact that the proof has been boring and easily automated is therefore very good. See Item 3 below.
2. Why is the proof so long?
1. The representation of these (co)inductive proofs on paper is not particularly compact. For example the cases in the proof of T27.11, when written in full, occupy about half a page each—but they are nothing more than “resolve against to produce two subgoals. Eliminate the first by resolving against and the second by resolving against ”, and so on.
2. We (often) have to write out the proof-state at each step. A theorem-proving environment would do that for us. For example (206)214.
3. Paper does not have ALLGOALS, REPEAT, ORELSE or so that part of themselves which the proofs of the cases have in common cannot be distilled to a single “by (ALLGOALS tactic)” at the head of a proof (followed by specialised code to clean up the debris). Instead we must redescribe the tactic for each case or omit the proof (with an excuse like “proof just like the last case” or “proof trivial”). E.g. consider the proofs of T27.9 or the more complicated T27.14. In this latter proof there is a telling sentence half-way through case 4: “Following the same pattern as the previous case”. In my experience the cases of these large inductive proofs do have a general ‘shape’ in common which paper expresses worse than computers.
3. If this proof is “standard resolution-based theorem proving”, why is more of the literature not automated (e.g. [64], [65], [42])? They did not have FM, which gives us structural inductive principles. Without it we either dishonestly rename bound variables or do induction on the length of a derivation rather than its structure. Both are messy. With ‘neat’ proofs like those of Chapter IV, who needs ‘messy’?
4. Could this proof be carried out using de Bruijn datatypes of syntax (33.1)? After all, the de Bruijn datatypes have semantics isomorphic to the FM datatypes. We commented in p.13 that it is not enough that a datatype be isomorphic to what we want, it must have the right inductive structure. The structural inductive principle for a de Bruijn datatype does not correspond to ‘taking subterms’, which complicates inductive hypotheses.
5. Could this proof be carried out in HOAS?
Not in its present form. We would have to abandon set theory and Isabelle to avoid exotic terms ([49, 11.2.2, p.132 or Example 11.8, p.135] or [12, 5, p.8]). The real point is that HOAS does not give inductive reasoning principles (though see [15]). Cf. 33.2.
Of course we might be able to carry out a different proof of the Sanity Clause (something like [34]94)—but HOAS has nothing like the facilities necessary to support this proof.
6. Why have I not implemented Chapter IV in FM?
I know what has to be done to implement this proof, see R19.3.1 and R20.3, but I also know I do not have the time to do it in this thesis. With the modifications of R20.3 in place an implementation would not even be particularly difficult. I have already developed all the underlying results (e.g. I have mechanised 13.2, a nontrivial task which I do not discuss) and designed the proof in detail on paper. I did so with an Isabelle/FM implementation specifically in mind, not only in the strict structural-induction style of my proofs (see Item 1 of this list) but also in some of the fine detail of the inductive sets’ design.
I shall indulge myself and show one of these details. This one is rather amusing, perhaps the reader noticed it. (162)188 is of the form
The second version is superficially ‘simpler’ but were the reader to program it into a resolution-based system he or she would quickly discover that it refuses to intro-resolve with anything that does not have conclusion with RHS of the form (b a)V . This is not at all what we meant, of course.
Chapter V
Conclusions
32. Commentary on FM
32.1. FM’s great problem: inaccessible.
At the end of 5.1 I said that FM is ‘new’, but insisted it is not ‘exotic’, ‘difficult’ or ‘strange’. On the contrary, FM seems to capture our intuitions about binding very well.
But that is not the whole story. FM does demand a dedicated system, and even if this system’s use is easy its initial construction need not be.
What does that mean? For example to ‘do’ FM-style datatypes with binding in a set theory I needed to construct FM set theory first. ZF was not up to the job. That was not too bad, but when I wanted to automate this in Isabelle I had to implement Isabelle/FM first—and that took a whole year. Of course this job is behind us and the rest of the world can benefit from my work without shedding a tear for me, but the list goes on: What if the reader wants COQ or HOL, not ZF? I have nothing to offer (for the moment). Similarly, before we write programs on FM-style datatypes we have to implement a language that supports them.95 And so on. This contrasts with other most other approaches to syntax with binding (33), which can be used for the most part on any current system. 3
The following terminology will be useful. I shall use it for the rest of this document mostly without comment.
I shall call an approach to binding inaccessible if we cannot use it right now on our average system, and accessible if we can. Thus FM is inaccessible and de Bruijn nameless terms (33.1) are.
So a drawback to FM is that it is inaccessible.
The following merely reiterates R4.14, only this time we have the development of FM behind us.
Call a term a nameless term if bound variables really are bound (e.g. de Bruijn terms, 33.1, or FM-style terms). Call a term a name-carrying term when bound variables are not bound and their names are therefore ‘carried’ in the abstract syntax of the term (e.g. 33.4). FM datatypes allow us to freely invent new names for bound variables and hence treat them as if they did have names. We call this a ‘nameful’ reasoning style.
Datatypes with nameless terms are usually setwise isomorphic to corresponding name-carrying datatypes up to -equivalence. Recall from R4.14 that FM
gives us all the benefits of nameless terms while still allowing us to reason in a nameful manner, as if about a name-carrying datatype.96
32.2. Usefulness of FM.
In this subsection I shall consider various situations in which FM is more, or less, useful. Suppose that 1 we want syntax as a means to an end.
For example, in [53] Milner and Parrow define the syntax of and a transition system for -calculus (incidentally, using name-carrying terms) and then prove results about them. They do not care about the syntax as such, it is simply a way of capturing “on paper” the object “in nature” which they want to study. Similarly in say, [7].
These researchers would conceivably be quite content to use FM-logic as an algebraic system for reasoning about bound names. They certainly do not have to understand the minutiae of FM sets to do this, any more than one has to understand the minutiae of ZF to use FOL.
accurately captures our intuitions about manipulating bound names and a manifestation of this is that reasoning in FM-logics seems almost indistinguishable on paper from the material currently produced by researchers.97 It seems plausible to me that researchers could use FM-logic with a minimum of fuss, and produce material comprehensible to those who do not know FM.
2 we want to write a program to manipulate syntax-with-binding.
As in the previous scenario FM is a means to an end. Assuming that an FM-style language becomes available (and this is the big ‘if’; there are none at the moment, see R32.1.1), the programmer can just write his or her program.
The reader can see example programs written informally in the kind of language I envisage in 4. Programs in a weaker but rigorously constructed language are in 22.2 and 24.2.
There are subtleties to FM-style languages. But in my opinion—and after looking at the examples I would hope the reader might agree I may be right—a practical programmer would quickly get the idea.
The real world is a messier place than the theory to which most of this thesis is devoted. I discuss how FM-style languages might contribute to the one application of syntax with which I am most familiar, namely theorem-proving systems, in the course of 33.4.
3 syntax itself is our object of study.
Here, certainly, a researcher would have to become familiar with the technical details of FM in whatever universe the researcher prefers, let us stick with sets for the sake of argument.
The development of FM sets in Chapter II is certainly long and technical (cf. Item 3 of 3). Of course a really rigorous development of any underlying universe is technical. Yet that misses the point. We are not doing set theory for its own sake, we just want to give semantics to syntax. Thus what interests us is ultimately not the precise set-theoretic implementation of abstraction-sets, any more than that of pair-sets or lists. These implementations are quite arbitrary except that they must have the right algebraic and logical properties, because it is these properties that interest us. So I would urge the reader not to worry too much about the length of Chapter II. The real issue is the beauty, or at least the utility, of the results we prove about our complicated constructions. And they come out rather well.98
32.3. FM not panacea.
I believe in FM, it has been very successful. Yet as successful as it is, sometimes it may just be irrelevant. So let me mention just two examples that on just fine without FM.
If we only ever need to substitute for closed terms, capture of free variables— and -equivalence—is not a problem. In particular substitution for closed values/terms is all we need for proving some properties of run-time systems, for example type-soundness. According to Tobias Nipkow ([32]), the Bali project
[71] has verified type-soundness for a simplified but significant subset of Java, and they never had to think about -equivalence once. Java is imperative and so one imagines it would be quite well-suited to this because binding plays a little less of a rôle than it would in a more functional language. Nevertheless, their subset has methods and objects and local variables are bound in them. But because run-time behaviour is their object of interest they avoid most of the problems which FM addresses. This is not to say that the Bali project need not use FM. Its abstraction types might simplify the handling of bound variables. Then again, maybe they would not; the designers might want to label bound variables with names for pretty-printing as discussed in and around R33.4.1, and as discussed there, that might effectively bring us back where we started to ZF-style name-carrying terms. Then again, maybe not.
Another example of an application that would not need FM is a theorem-prover called SATCHMO, [4], brought to my attention by Francois Bry. The system is 12 lines of Prolog (Bry apologised for the length and explained it would be shorter but for pretty-printing) and took two years to write. Bry assures me that SATCHMO makes sophisticated non-evident use of Prolog; it is a genuine system, not just a front-end. However, it hijacks Prolog’s syntactic system and therefore has no need for its own datatype of terms,99 and sidesteps this entire thesis.
It is not that I see a shortage of applications for FM. On the contrary, I think it will be very useful. I merely wish to emphasise that FM is a good solution, but only to a particular problem.
33. Other approaches and the literature
First I shall reference a few articles and web sites. [62] is a survey of ‘logical frameworks’ with some emphasis on the issue of syntax. Logical Frameworks have a homepage [56] with a useful link [73] to researches in the area. Incidentally “logical framework” is used in a more specific sense than “theorem-proving environment”, see the homepage. In concrete terms this means that [56] does not include COQ, among others. However, there is a link there to the COQ homepage
[27] anyway. I should also mention a relatively early paper [75] by Stoughton. In the introduction he discusses the problem of substitution and binding and gives references.
Recall the terminology ‘accessible’, ‘inaccessible’, ‘name-free term’ and ‘name-carrying term’ established in N32.1.2 in N32.1.3.
Now we consider the various other approaches to syntax with binding.
33.1. De Bruijn.
The idea was originally presented in de Bruijn’s [11]. The de Bruijn-style type of untyped -terms is
(207) X Var of Lam of X App of X X
There are many variants but the usual idea is that Var(n) represents the (n i)th variable name if there are i occurrences of Lam above this Var(n) in the abstract syntax of the term for i n, and represents the variable bound by the nth Lam up from Var(n) otherwise. Thus n encodes either a pointer to a particular binding operator Lam or a reference to a free variable.
De Bruijn techniques are accessible (N32.1.2) and produce nameless terms with semantics isomorphic to the syntax-up-to--equivalence. They are widely used in programming applications, program-verifications, and more.
However de Bruijn datatypes have a rather revolting inductive structure which makes it difficult to write programs using them (cf. Nat and oNat on p.13). For example, if we want to unpack the body of an abstraction (e.g. remove in a term representing xt), we have to write a program to go through the term relabelling all the indices (as seen in Fig.120). 3
So advantages are:
Terms are nameless, we do not have to worry about respecting -equivalence and a class of bugs is ruled out.
For a given application there are only a finite number of functions we need out of the datatype (possibly just substitution, ‘body of a -term’, ‘top-level term-former’, ‘is-well-formed’ and a couple more). We may cry and beat the walls while we define them, but then it’s over and we can get on with things.
This is true in verification as well. There the functions on syntax are defined by and limited to those declared in the specification of the program. and disadvantages are:
People can get used to almost anything including this, but still, programs come out messy. See R33.1.1 and Fig.120.
This messiness is not just a cosmetic issue. When we unpack a body of an abstraction we have to relabel variables as described in R33.1.1. With huge terms (such as arise in hardware verification) this causes efficiency problems. For this reason HOL-light ([29]) uses name-carrying terms and not de Bruijn, we shall return to this in 33.4.
In a theoretical treatment of syntax the goal may be not only to define a function but to then study it. If the definition of the function is revolting so is its analysis (see R33.1.2). Ironically de Bruijn introduced his indices in
[11] precisely to reason about nameless terms and a particular relation on them (Church-Rosser for the -calculus). However, the twisted inductive principles of de Bruijn seem too much for modern researchers. They prefer either name-carrying techniques (as in [53]) or HOAS (as in [34], see also 33.2).
However, Hirschkoff’s recent thesis [24] (in French, resuméd to some degree in [25]) uses de Bruijn-style to execute a complete analysis of the -calculus and bisimulation equivalence in COQ. Apparently 75% of the author’s COQ lemmas control de Bruijn indices. The man must have incredible patience. I am sure no-one wants to go through what he must have gone through again. But if they use de Bruijn, they will. 3
I shall discuss de Bruijn further when I compare it to name-carrying techniques in 33.4.
I mention in conclusion that Bird and Paterson in [2] build a de Bruijn style datatype with a clever structure which avoids many of the problems discussed above. It has its disadvantages but the point is that sheer cunning can get good results. See in particular [2, 4, p.10].
33.2. HOAS.
HOAS stands for Higher-Order Abstract Syntax. Miculan’s thesis [49] is an excellent document and [49, Chapter 11, p.125] is devoted to a clear discussion of HOAS. A roughly similar but more concise, advanced discussion is in [12]. [51] is a clear historical and technical account of HOAS techniques.100
[52] is a paper discussing logics for reasoning on HOAS and includes references for that part of the field. I also recommend a survey of Logical Frameworks [62], in particular [62, 5, p.8] is a discussion of HOAS with plenty of references. [45] is not a survey article in itself but [45, 5, p.8] is a survey.101
HOAS is a large field to which I cannot do justice here. I shall briefly mention the basic idea, otherwise I refer the non-expert reader to [49, Chapter 11, p.125] as a good exposition with plenty of examples. From now on I shall assume the reader is familiar with HOAS.
Briefly, HOAS is when we interpret binding term-formers as functions (‘meta-level abstractions’, as it is often put). The datatype of syntax of -terms becomes
(208) X Lam of (X X App of X X
[49, 11.2.1] describes in the vocabulary of COQ ([27]) how things go horribly wrong with this approach. We see the same problem in sets: the function space X X is too large and the fixedpoint does not exist. [49, Example 11.6, p.131] is a case where the approach of (208)233 does work, but often it does not. One attempt at solution is to hypothesise a type of atoms Var and redeclare our datatype as
(209) X Lam of Var X App of X X
Features of HOAS usually portrayed in a positive light are:
1. Substitution is handled by the meta-language.
2. -equivalence is handled by the meta-language.
3. Object-level variables disappear and are replaced by meta-level variables.
This does not impress me. 1 HOAS datatypes do not have inductive structure and do not yield structural recursion principles.
The types Var X and X X do not have inductive structure. This means the datatypes of (208)233 and (209)233 have no structural inductive principles. Functions out of them cannot be defined by structural induction.
For an example of how researchers try to get around this see Despeyroux and Hirschowitz [14]. This does not seem to quite work. A later attempt is Despeyroux, Pfenning and Schürmann [15] (short version) and [13] (long version). I would very much like to dissect their paper but there is no space here. One manifestation of the problems HOAS has with recursion is that we cannot write down simple pattern-matching iterative definitions like those of 4 or even 22.2 because of the functional type in the recursive definition. Despeyroux et al therefore try to sidestep pattern-matching. Instead they ‘replace’ the constructors of the initial datatype (e.g. -terms) with constructors of the target type (e.g. natural numbers), which produces an ‘iterative’ function from the first (-terms) to the second (natural numbers). (This is their example cntvar.)
It is complicated.
The authors’ -calculus is not given any underlying semantics (aside from itself), which is unsatisfactory. Without an underlying (or if the reader prefers, alternative) semantics, how do we know there isn’t a much better -calculus just round the corner. There probably is. How do they set about finding it? [26] independently addresses this point and produces presheaf semantics for the work in [13].102
2 Therefore, is difficult to reason about and define functions on HOAS datatypes.
Surely not? In [13] and [15] Despeyroux et al present a methodology for recursion on HOAS datatypes and [26] gives it a semantics. Is this not just what we wanted? Well, I already mentioned that [13] is not quite recursion as such, it is something a little different to do with ‘replacement’ rather than ‘pattern-matching’. Yet I myself am anxious to convince the reader that
“FM is not quite ZF, but close enough to be useful and anyway it’s quite harmless so don’t worry about it”
—so perhaps I had better be open-minded about eccentricities in other people’s work. And indeed, I do not object to the ‘exotic’ primitive recursion of Despeyroux et al. It’s perfectly reasonable, it just comes out complicated. Abstraction types []X have far better algebraic properties than function-types X X (see C9.6.9) and FM delivers completely standard iterative definitions without a hint of a struggle (see 10 for details, 5.2 for an overview).
Thus in [15, p.8 and p.9] the informal iterative definitions of two functions plus and cntvar, which serve in [15] as the beginning of the rest of their paper, would in FM just be the definitions of the desired functions: for example I define a function FVlist similar to cntvar in (FVlist)166. Instead of the number of free variables it returns a list of them. If the reader can pardon the concrete syntax, it is clearly just the informal definition of cntvar given in [15]. Notice that no pure HOAS system can ever define FVlist because in HOAS variables have no object-level names.
Similarly FreshML (Chapter IV) is a typed -calculus corresponding to (though completely different from and almost melodramatically simpler than) that of [15]. It is derived from from FM-sets, not plucked out of thin air and then given semantics as is the case for [15] and [26].
We move on from [15]. Honsell, Miculan and Scagnetto place a different emphasis in [34]. They are concerned with practical reasoning on a particular HOAS datatype of terms for the -calculus. I know this paper quite well because I mirrored some of it on paper in FM and even began to implement my paper development in Isabelle/FM. As they say in their conclusions, the great benefit of HOAS is that it gives them nameless terms but without the trouble de Bruijn causes (cf. 33.1 and in particular R33.1.2). The price is that their datatype does not have inductive principles, so they axiomatise the properties and functions they need (e.g. “is in the free names of”).
It is interesting that their axioms are reminiscent of certain useful properties of FM, although in FM they are all derived, ultimately from the ‘FM axiom’ (Fresh)35. E.g. unsat on p.20 corresponds to C9.2.5.
3 HOAS leads to complicated reasoning and programming principles.
Never mind programming, what about logic? HOAS terms are at least second-order, so we cannot reason about them with First Order Logic (like we do in FM). Thus HOAS generates a need for new logics with enough strength at higher orders to manipulate the terms, but not so much that they become too powerful. After ‘logic’ comes ‘logic programming’, e.g. unification. If the logic is too powerful unification becomes undecidable—how do we unify terms of type X X or Var X ?
Relatively recent research in this area includes McDowell’s thesis [44], McDowell and Miller’s [45] and the same authors’ most recent paper [46].
FM-abstraction types are first-order objects and FM-logic (5.1) has been quite sufficient to manipulate them logically. Some discussion of this is in 12. The logic of FM is also classical. The logic FO of the papers referenced above is not.
4 HOAS has exotic terms.
This problem is peculiar to HOAS. See and [49, 11.2.2, p.132 and 11.3.1 p.135] (elementary) or [14, 2.2, p.6] (more advanced). This is a tremendous problem for HOAS for various reasons. I mention just one of them: they put a lot of junk in a HOAS datatype that should not be there. If we want to reason about this datatype we need some way of eliminating exotic terms from consideration. Why?
Our theorem may well not be true of them.
They are not constructed using the term-formers of the datatype and as such are part of the ‘no structural recursion’ problem discussed in Item 1.
Now let us consider some of the so-called ‘advantages’ of HOAS listed on p.233.
5 Object-level variables disappear.
Observe in (208)233 and (209)233 that there is no Var term-former. If we want open terms in HOAS we model them as functions f : term term, see [14, 1 p.3].103 I do not like this. It is just another complication.
6 Substitution is handled by the meta-language.
I think the reason this is pleasing is that, were it not the case (and without recursion) HOAS would be completely stuck. This is no blessing, it is utter damnation averted. For other approaches which give inductive principles of one kind or another, substitution is just one of a number of interesting functions we might define out of a datatype.
Sometimes HOAS gives us substitution even when we do not want it. For example, in the -calculus we want to bind channel names without allowing name-for-process substitution. This is discussed in [49, Chapter 11, p.128, Examples 11.1 and 11.2].
7 -equivalence is handled by the meta-language.
Yes. HOAS terms are nameless! This brings the list to an end. The reader should be clear precisely what I am criticising. It is standard to give (for example) and on a type X semantics as higher-order functions
where b is the type of truth values. Thus x X is interpreted as (x :X ). This idea is very successful (it goes back to Church’s famous paper [8]). Note that it concerns the semantics of binders. HOAS concerns the semantics of the syntax of binders. The latter is under scrutiny here. Let me illustrate this with an example. The Isabelle/FOL universal quantifier All is typed as . This is a classic higher-order encoding of the quantifier. However, the syntactic term-former we manipulate is just a function from term to term with associated typing conditions. True higher-order syntax would be if All took an ML-function from term to term and returned a term in term.
One of the important techniques of science is to ‘explain’ phenomena in terms of ‘simpler’ concepts. Thus ‘AN OBJECT IS BLUE’ is ‘explained’ in terms of wavelengths of light reflected. FM ‘explains’ binding in terms of and . De Bruijn ‘explains’ it in terms of point-ers to variables. HOAS is different. Its great claim is that it ‘explains’ variables in terms of variables in the meta-language—but is this not suspiciously like ‘ex-plaining’ ‘AN OBJECT IS BLUE’ by saying ‘THE OBJECT IS COMPOSED OF BLUE PARTICLES’? This paragraph may be just words, but see [49, 11.1, p.127] for a concrete manifestation of what I am worrying about. 3
In spite of all I have said, sometimes, with the right language and the right meta-language, HOAS can work. For example in her thesis [19],104 Gardner shows that terms of FOL are in bijection with terms of ELF (a logical framework she introduces in her thesis, see [19, Chapter 3, p.45]) in -normal form (i.e. what I would probably call ‘values’), see [19, T5.1.9, p.101]. Furthermore the proofs of FOL can be represented with complete accuracy in the framework [19, T5.2.7, p.119]. Similar results hold of HOL (E5.1.10 and E5.2.8 respectively). Even so in C5.1.8, E5.2.6, or T5.2.13 Gardner discusses how the results can break down for other logical systems. I would refer the interested reader to Miculan’s thesis [49]. It contains what seems to be a systematic programme of attempts to represent various logics in CIC, the results of which enquiry are summarised in [49, 18.1, p.200].
33.3. Combinators.
Since -conversion causes so much trouble, why not use combinators ([10])?
We can. Camilleri and Melham decided to do just that in [5].
If we just want to avoid sinking into that particular bog which this thesis hopes to drain and landscape over, fine. But as a philosophical position it is untenable. It commits us to reasoning using combinatory logics, programming using, say, combinatory versions of C and ML—perhaps even abolishing the words ‘every’, ‘a few’, ‘all’, and ‘some’ from the English language (and similar) and replacing them by combinatory versions.
Assuming that interest in traditional methods and languages persists, the problem of syntax with -equivalence is there to be solved.
33.4. Name-carrying terms.
Recall the terminology ‘name-carrying’ and ‘nameless’ from N32.1.3. In name-carrying techniques abstraction types are interpreted by X or X (or similar).
For an excellently clear exposition on the difficulties traditional name-carrying terms have with -equivalence I refer the reader to the slides of a talk by Pollack
[74] and also Stoughton’s [75, 1].
I consider practical applications first. In 33.1 and particularly R33.1.1 I mentioned that de Bruijn-style terms can suffer efficiency problems because we cannot break up terms without relabelling indices. In name-carrying terms this is not a problem, the body of Lam(x,M) is just M. Name-carrying has its own problems:
Equality testing, matching, or unification are up to -equivalence (with associated computational cost).
The datatype must be wrapped in an abstract datatype (with some fixed collection of basic interface functions) to preclude programs which may not respect -equivalence. This reduces programming flexibility and
the interface theorems are complicated, to handle renaming of bound names. Bugs are possible and a computational price guaranteed.
So in practical applications there is a trade-off between de Bruijn and name-carrying terms. Isabelle uses de Bruijn, I am told that HOL88 (the original HOL) used name-carrying terms, HOL90 switched to de Bruijn. Apparently HOL98 went back to de Bruijn but was worked on by people from the COQ system and now uses explicit substitutions in a way I have not researched. HOL-Light uses name-carrying terms.
However, users like to see terms printed with explicit variable names so even the systems that ostensibly use ‘nameless de Bruijn’ often label the bound variables with names anyway. De Bruijn guarantees we respect -equivalence, and the labels help us pretty-print.
3
Does FM have anything to contribute? FM-style languages simply give the ‘up to -equivalence’ of de Bruijn but with the added extra of ‘natural recursive principles’ and ‘ and fresh’. Investigations in FM-style programming suggests it works excellently (for informal examples see 4, for examples in a rigorously defined language see 22.2. See also [66]). A project has been applied for to implement an FM-style language based on ML.
Thus one can expect programs in FM to be easier to handle than de Bruijn, and if we want name-carrying terms we can adopt the trick mentioned above of using nameless terms with extra name-carrying labels. Such programs should be easier to write, debug, and indeed to formally verify. Note that if we do use extra name-carrying labels we re-introduce the problems of -conversion and all the tedious programming involved. However, this problem is now at a more superficial level in the sense that it is with ‘pretty-printing labels’ rather than the core underlying representation (which is FM, nameless, and correct).
Would these programs run faster? Not necessarily. The FM-language will still use an underlying representation of elements of a datatype, probably similar to those manipulated directly in current systems. It might (or might not) be that compiled FM code would not be very different from what we have now. Compared to a name-carrying technique an FM-version would presumably be more efficient because the underlying datatype could be left exposed (not wrapped in any computationally expensive abstract datatype).105
I suspect that programmers have got used to not being able to do certain things and that FM languages will generate their own demand in ways I could not necessarily foresee now.
Now we leave programming and turn to theory. For most researchers syntax is a means to an end. They usually use name-carrying terms ([53]) or name-carrying terms up to -equivalence ([7]) and work with representatives. Up to a point the two options are equivalent because in the former technique the authors rename bound variables. In both techniques proofs tend to be by induction on the length of terms.
Besides being a nuisance these proofs have been known to wrong-foot authors, though I believe today’s generation has learnt some caution in this regard. For example [76, p.161-166] is a proof of a substitution lemma which is really by induction on length but claimed to be by structural induction.
If a paper has one particular object of study, e.g. ‘bisimulation’ in [53], the authors just have to prove (by induction on length of terms) that their object of interest is appropriately ‘blind’ to renaming bound variables, at which point they can continue their development essentially by structural recursion/induction, renaming where necessary. For an example see [53, 3.1, p.19], just after Theorem 1,
“ we shall freely identify alpha-convertible agents ”. If the paper studies many different objects or a whole class of them, things are harder. For example Chapter IV involves the relations , , , , and (plus spear-carriers). Without FM we would presumably have had to prove ‘blindness’ for each.
For such researchers FM provides the FM-style logic. One such was used in this thesis in Chapter II to construct FM set theory and in Chapter IV to prove an operational extensionality result T29.25 for an example language (itself an FM-style programming language). Some of its features are sketched in 5.1. A summary is:
We have the option of treating terms as name-carrying or nameless as convenient. From the former we have all the benefits of induction on terms and writing terms with explicit names. From the latter we have the option of writing terms without names (for when we do no care what they are), and a guarantee we can never violate -equivalence. We discuss this during 12.1 and the second half of 12.2.
The logic has excellent properties which justify reasoning steps whose validity might not otherwise be obvious (e.g. R23.1.13).
Reasoning using FM logic looks and feels exactly like what practitioners do anyway (once they have proved their technical ‘blindness’ results, see above). In the second half of 12.2 I show how we can phrase FM rules in a traditional way. All of Chapter IV is carried out in FM and it looks completely standard—except for when I occasionally take advantage of the extra power of FM to short-circuit what would otherwise be a few pages of mathematics (cf. 12.5, in particular R12.5.1).
33.5. McKinna and Pollack.
Still on the subject of name-carrying terms, one approach that deserves special mention is the work of McKinna and Pollack, see [74] (slides of a talk) and [47]. They pursue name-carrying terms in ZF to their logical conclusion. In [47] they present, by working through a particular example, a general methodology for carrying out structural induction on terms up to -equivalence.
The trick that makes it work is an echo of T9.4.6 (duality of between and ). They prove it by induction on term length for each individual datatype. Their methodology is a serious practical tool: in conversation, Pollack told me he had used his method to verify a typechecker in LEGO, a development of 6000 lemmas which took one-and-a-half years to carry out. See [69] (there a figure of 3000 is quoted, I presume it has grown since 1995).
The unique property of McKinna’s and Pollack’s work among non-FM approaches is that, like FM, they try to remain faithful to how we really seem to handle syntax with binding in the real world. The fact that they come back from this analysis with structures reminiscent of FM vindicates this document, and indeed this document vindicates theirs.
33.6. Fiore, Plotkin and Turi.
Fiore, Plotkin and Turi have done work on presheaf models of abstract syntax with binders. See [17]. On p.234 (just after the itemised list) I comment that presheaves have such rich structure, you can make them do anything you like if you are clever enough. The challenge is to find a presheaf with a good model of syntax with binding. This is what [17] tries to do.
On the subject of presheaves, there is a mathematical presentation of FM in presheaf style, see Gabbay and Pitts [18, 6], which I do not discuss in this thesis. In fact, I made a conscious decision to present my material in the ‘lightest’ style I can and it seemed to me that presheaves are ‘heavier’ than sets. In [17] Fiore et al present their material in a relatively sophisticated mathematical style and this may generate the impression that it is completely different from the material in this thesis. However, the two approaches are quite similar. Many constructions in both correspond. Their operator ([17, p.196]) corresponds in its behaviour and construction to my []() (D9.6.1). I owe the general idea of binding signatures ([17, 2]) to them. Their treatment of substitution ([17, 3]) is more abstract than mine but amounts to much the same object as I defined in D12.6.2.
I suggest that my underlying universe is nicer than theirs, in particular FM logic is classical whereas the internal logic of their category is not. They also do not have .
33.7. The axiomatic approach.
It deserves mention that various authors have tried ‘axiomatising’ -equivalence in one way or another. The authors do not try to ‘explain’ binding in terms of this axiomatisation. Either:
1. they want to systematically analyse the behaviour of binding, or
2. they are in COQ (or some similar system), want to make some definition work, and find they need this or that axiom to do so.
Gordon and Melham’s [21] is a good example of case 1 above, carried out in the context of HOL ([28]). We can see how they do not ‘explain’ binding because they do not ‘explain’ renaming of bound variables, they just avoid it; see their 1.2. Wahid Taha brought to my attention some work, see [16], by Pašalić, Sheard and Taha, where they try to capture binding behaviour in the framework of a -calculus. There are several examples of case 2 above, in particular Honsell, Miculan and Sagnetto do precisely this in [34] as already commented on in Item 2 of 33.2.
I should also mention a relatively old paper by Stoughton, [75] (I get the impression it was rather ahead of its time). This axiomatises simultaneous substitution. Miller has tried extending standard ML with abstraction types to achieve the same effect as FreshML, see [50]. As in case 2 above, the idea is not to explain anything, just to get things done.
34. Accomplishments of this thesis
1. I define and develop the theory of a set-universe FM (Chapter II). It enables purely inductive definitions of datatypes of syntax with -conversion by standard initial algebra methods, so the datatypes have standard recursive/iterative/inductive principles.
2. This universe is elementary in that it looks just like ZF. In particular it does not force its (considerable) extra power on practitioners (e.g. through unfamiliar notation, strange ways of doing things, etc.) if they do not want to use it.
3. The new set-universe and its associated logic accurately and simply capture our natural intuitions about syntax with binding.
4. Changing the subject, I present an alpha-stage Isabelle implementation of FM set theory, called Isabelle/FM (Chapter III).
5. I include a discussion of the various monsters I slayed in the course of the implementation. Some of them are pure proof-engineering and have nothing to do with FM as such. Some concern how FM interacted with mechanised proof.
6. Isabelle/FM includes nearly all the theory of Isabelle/ZF (as well as the extra FM structure), including facilities for declaring datatypes of syntax—only this time, thanks to the extra structure, with binding.
7. I have conducted several experiments defining datatypes of syntax up to binding and explored functions and predicates defined on them by their inductive structure. From all this I come to definite conclusions and proposals about the design of a beta-version of Isabelle/FM, and FM-style mechanised mathematics in general (20).
8. Changing the subject once more, I demonstrate how an FM-style programming language might look (4) and rigorously define a toy programming language as a first step on this path (Chapter IV).
9. I demonstrate the behaviour of this toy language (22.2, 24.2) and show how it allows us to program inventing fresh names for bound variables at our convenience. It all works out very naturally.
10. Chapter IV proves a technical correctness result (T21.9) designed to reassure us that we have understood the subtle points mentioned above.
11. This technical correctness result is carried out using FM-set theory and logic. FM really does make the proofs easier and cleaner.
35. Future work
1. Continue the investigation of FM underlying universes by pursuing FM sets further and developing FM-HOL and an FM dependently typed universe (à la Martin-Löf).
2. Bring Isabelle/FM to beta-version so people could use it (20). Possibly implement other mechanised versions of FM such as FM-HOL.
3. Develop the underlying theory for (and implement a version of) the FM-style programming language which this document nibbles at and lays the technical groundwork for (based on ML, a project has been applied for).
4. Further demonstrate the advantages of FM for paper mathematics by carrying out real mathematics using FM.
5. Lots more.
And that, gentle reader, was my thesis.
Murdoch J. Gabbay 10 August 2000 Cambridge University, England
— The End —
List of Figures
1 Substitution in Isabelle98-1/Pure 20
4 D10.1.3 - Binding Signatures 58
5 Functorial action of , + and []() 59
6 D10.1.6 - Functor associated to a binding signature 60
7 D10.5.3 - Scheme for canonical out of naïve datatype 73
8 D10.7.2 - Free Variables FV For Free 76
9 D10.7.10 - Name-for-Name Substitution [ba] For Free 79
10 D10.7.13 - Substitution [ta] For Free 81
11 D12.1.1 - Types, Terms, and Variables of FMLtiny 90
12 D12.3.1 - Typing Judgements of FMLtiny 93
13 D12.6.4 - Evaluation Relation of FMLtiny 97
15 Rules and axioms of ZFQA 108
16 Further definitions of ZFQA 109
21 A few equivariance results of Isabelle/FM 126
26 Results of Datatypes Package for term 146
27 Code of an equivariance result 149 28 Functions out of term 150
29 Declarations of Isabelle/FM 155
30 D22.1.1 - Types of FreshML 161
31 D22.1.4 - Terms and values of FreshML 164
32 D23.1.6 - Apartness Judgements 1 169
33 D23.1.6 - Apartness Judgements 2 170
37 D26.2.2 - Contextual Preorder 193
Bibliography
1. H. P. Barendregt, The lambda calculus: Its syntax and semantics (revised ed.), Studies in Logic and the Foundations of Mathematics, vol. 103, North-Holland, Amsterdam, 1984.
2. Richard Bird and Ross Paterson, De Bruijn notation as a nested datatype, Journal of Functional Programming 9 (1999), no. 1, 77–91.
3. Francis Borceux, Handbook of categorical algebra I,II,III, CUP, 1994.
4. Francois Bry and Rainer Manthey, Satchmo: A theorem prover implemented in prolog, 9th Int. Conf. on Automated Deduction (CADE), Argonne, IL, Springer-Verlag LNCS 310, May 1988, pp. 415–434.
5. Juanito Camilleri and Tom Melham, Reasoning with inductively defined relations in the hol theorem prover, Tech. Report 265, University of Cambridge Computer Laboratory, August 1992.
6. Luca Cardelli and Andrew D. Gordon, Logical properties of name restriction (not yet published), Microsoft Research, Cambridge.
7. G. L. Cattani and P. Sewell, Models for name-passing processes: Interleaving and causal (extended abstract), Fifteenth Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 2000.
8. A. Church, A formulation of the simple theory of types, Journal of Symbolic Logic 5 (1940), 56–68.
9. Thierry Coquand and Gérard Huet, The Calculus of Constructions, Information and Computation 76 (1988), no. 2/3, 95–120.
10. H. B. Curry and R. Feys, Combinatory logic, vol. 1, North Holland, 1958, (Second edition,
1968).
11. N. G. de Bruijn, Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem, Indag. Math. 34 (1972), 381–392.
12. J. Despeyroux, A. Felty, and A. Hirschowitz, Higher-order abstract syntax in Coq, Typed Lambda Calculus and Applications, 2nd International Conference (M. Dezani-Ciancaglini and G. D. Plotkin, eds.), Lecture Notes in Computer Science, vol. 902, Springer-Verlag, Berlin, 1995, pp. 124–138.
13. J. Despeyroux, F. Pfenning, and C. Schürmann, Primitive recursion for higher-order abstract syntax, Technical Report CMU-CS-96-172, Carnagie Mellon University, September 1996.
14. Joëlle Despeyroux and André Hirschowitz, Higher-order abstract syntax with induction in Coq, Proceedings of the 5th International Conference on Logic Programming and Automated Reasoning (Kiev, Ukraine) (Frank Pfenning, ed.), Springer-Verlag LNAI 822, July 1994, pp. 159–173.
15. Joëlle Despeyroux, Frank Pfenning, and Carsten Schürmann, Primitive recursion for higher-order abstract syntax, Proceedings of the Third International Conference on Typed Lambda
Calculus and Applications (TLCA’97) (Nancy, France) (R. Hindley, ed.), Springer-Verlag LNCS, April 1997, An extended version is [13], pp. 147–163.
16. Walid Taha Emir Pasalic, Tim Sheard, An untyped cbv operational semantics and equational theory of datatypes with binders (technical development), Tech. Report CSE-00-007, OGI Computer Science and Engineering, 1999.
17. M. P. Fiore, G. D. Plotkin, and D. Turi, Abstract syntax and variable binding, 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 1999, pp. 193–202.
18. M. J. Gabbay and A. M. Pitts, A new approach to abstract syntax involving binders, 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 1999, pp. 214–224.
19. Philippa Gardner, Representing logics in type theory, Ph.D. thesis, University of Edinburgh, July 1992, Available as Technical Report CST-93-92.
20. J. Goguen, J. Thatcher, , and E. Wagner, An initial algebra approach to the specification, correctness and implementation of abstract data types, Current Trends in Programming Methodology IV (1978), 80–149.
21. A. D. Gordon and T. Melham, Five axioms of alpha-conversion, Theorem Proving in Higher Order Logics: 9th Interational Conference, TPHOLs’96, Lecture Notes in Computer Science, vol. 1125, Springer-Verlag, Berlin, 1996, pp. 173–191.
22. C. A. Gunter, Semantics of programming languages: Structures and techniques, Foundations of Computing, MIT Press, 1992.
23. P. R. Halmos, Naïve set theory, Springer Verlag, March 1987.
24. D. Hirschkoff, Mise en œuvre de preuves de bisimulation, Ph.D. thesis, École Nationale des Ponts et Chaussées, January 1999, in French.
25. Daniel Hirschkoff, A full formalization of pi-calculus theory in the Calculus of Constructions, Proceedings of the 10th International Conference on Theorem Proving in Higher Order Logics (TPHOLs’97) (Murray Hill, New Jersey) (E. Gunter and A. Felty, eds.), August 1997, pp. 153–169.
26. M. Hofmann, Semantical analysis of higher-order abstract syntax, 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 1999, pp. 204–213.
27. COQ Homepage, http://coq.inria.fr/.
28. HOL Homepage, http://www.cl.cam.ac.uk/Research/HVG/HOL/HOL.html#index.
29. HOL-Light Homepage,
http://www.cl.cam.ac.uk/users/jrh/hol-light/index.html.
30. John Harrison Homepage, http://www.cl.cam.ac.uk/users/jrh/.
31. Konrad Slind Homepage, http://www.cl.cam.ac.uk/users/kxs/.
32. Tobias Nipkow Homepage, http://www4.informatik.tu-muenchen.de/~nipkow/.
33. Twelf Homepage, http://www.cs.cmu.edu/~twelf.
34. F. Honsell, M. Miculan, and I. Scagnetto, -calculus in (co)inductive type theory, Tech. report, Dipartimento di Matematica e Informatica, Università degli Studi di Udine, 1998.
35. D. J. Howe, Proving congruence of bisimulation in functional programming languages, Information and Computation 124 (1996), no. 2, 103–112.
36. Douglas J. Howe, Equality in lazy computation systems, Proceedings, Fourth Annual Symposium on Logic in Computer Science (Asilomar Conference Center, Pacific Grove, California), IEEE Computer Society Press, 5–8 June 1989, pp. 198–203.
37. Isabelle Cambridge Homepage,
http://www.cl.cam.ac.uk/research/hvg/isabelle/cambridge.html.
38. T. J. Jech, About the axiom of choice, Handbook of Mathematical Logic (J. Barwise, ed.), North-Holland, 1977, pp. 345–370.
39. T. J. Jech, Set theory, Academic Press, 1978.
40. P. T. Johnstone, Notes on logic and set theory, CUP Mathematical Textbooks, 1987.
41. L. Lamport and L. C. Paulson, Should your specification language be typed?, Tech. Report 147, Digital SRC, 1998.
42. Søren Bøgh Lassen, Relational reasoning about functions and nondeterminism, Ph.D. thesis, Department of Computer Science, University of Aarhus, 1998.
43. Saunders Mac Lane, Categories for the working mathematician, Springer, 1971.
44. Raymond McDowell, Reasoning in a logic with definitions and induction, Ph.D. thesis, University of Pennsylvania, 1997.
45. Raymond McDowell and Dale Miller, A logic for reasoning with higher-order abstract syntax, 12th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press, Washington, 1997, pp. 434–445.
46., A logic for reasoning with higher-order abstract syntax: An extended abstract, Proceedings of the Twelfth Annual Symposium on Logic in Computer Science (Warsaw, Poland) (Glynn Winskel, ed.), June 1997, pp. 434–445.
47. James McKinna and Robert Pollack, Some lambda calculus and type theory formalized, Tech. report, 1997.
48. Thomas F. Melham, Using recursive types to reason about hardware in higher-order logic, Tech. Report TR135, Cambridge University Computer Lab, April 1990.
49. Marino Miculan, Encoding logical theories of programs, Ph.D. thesis, Università di Pisa-Genova-Udine, Thesis TD-7/97, March 1997.
50. D. Miller, An extension to ML to handle bound variables in data structures: Preliminary report, Proceedings of the Logical Frameworks BRA Workshop, 1990.
51. Dale Miller, Abstract syntax for variable binders, CL2000, Springer-Verlag, 2000, To appear.
52. Dale Miller and Catuscia Palamidessi, Foundational aspects of syntax, Computing Surveys 31 (1999).
53. R. Milner, J. Parrow, and D. Walker, A calculus of mobile processes (parts I and II), Information and Computation 100 (1992), 1–77.
54. R. Milner, M. Tofte, R. Harper, and D. MacQueen, The definition of standard ML (revised), MIT Press, 1997.
55. J. C. Mitchell and G. D. Plotkin, Abstract types have existential types, ACM Transactions on Programming Languages and Systems 10 (1988), 470–502.
56. Logical Frameworks Page, http://www.cs.cmu.edu/~fp/lfs.html.
57. L. C. Paulson, ML for the working programmer, 2nd ed., Cambridge University Press, 1996.
58. Lawrence C. Paulson, Isabelle reference manual, Isabelle99 edition, Part of the Isabelle Distribution (see [37]).
59., Isabelle’s logics: FOL and ZF, Isabelle99 edition, Previously “Isabelle’s Object-Logics”, Isabelle98-1 Edition. Part of the Isabelle Distribution (see [37]).
60., A fixedpoint approach to implementing (co)inductive definitions, Proceedings of the 12th International Conference on Automated Deduction (Nancy, France) (Alan Bundy, ed.), Springer-Verlag LNAI 814, June 1994, pp. 148–161.
61. Simon Peyton-Jones, http://research.microsoft.com/~simonpj/.
62. Frank Pfenning, The practice of logical frameworks, Proceedings of the Colloquium on Trees in Algebra and Programming (Linköping, Sweden) (Hélène Kirchner, ed.), Springer-Verlag LNCS 1059, April 1996, Invited talk, pp. 119–134.
63. A. M. Pitts, A note on logical relations between semantics and syntax, Logic Journal of the Interest Group in Pure and Applied Logics 5 (1997), no. 4, 589–601.
64., Operationally-based theories of program equivalence, Semantics and Logics of Computation (P. Dybjer and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1997, pp. 241–298.
65., Parametric polymorphism and operational equivalence, Mathematical Structures in Computer Science 10 (2000), 1–39.
66. A. M. Pitts and M. J. Gabbay, A metalanguage for programming with bound names modulo renaming, Mathematics of Program Construction, MPC2000, Proceedings, Ponte de Lima, Portugal, July 2000 (R. Backhouse and J. N. Oliveira, eds.), Lecture Notes in Computer Science, vol. ?, Springer-Verlag, Heidelberg, 2000, pp. ?–?
67. A. M. Pitts and I. D. B. Stark, Observable properties of higher order functions that dynamically create local names, or: What’s new?, Mathematical Foundations of Computer Science, Proc. 18th Int. Symp., Gdańsk, 1993, Lecture Notes in Computer Science, vol. 711, Springer-Verlag, Berlin, 1993, pp. 122–141.
68. Andrew M. Pitts, http://www.cl.cam.ac.uk/~ap.
69. R. Pollack, A verified typechecker, Proceedings of the Second International Conference on Typed Lambda Calculi and Applications (M. Dezani-Ciancaglini and G. Plotkin, eds.), TLCA’95, 1995.
70. Robert Pollack, http://www.dcs.ed.ac.uk/home/rap/.
71. Bali Project, http://www4.informatik.tu-muenchen.de/~isabelle/bali/.
72. Willard Van Orman Quine, Set theory and its logic, revised ed., Harvard University Press, Cambridge, MA, 1963.
73. Logical Frameworks Researchers, http://www.cs.cmu.edu/~fp/lfs-people.html.
74. Robert and James McKinna, Names, binding and substitution, February 1998, Unpublished slides of a talk, available as bindingTalk.ps via [70].
75. A. Stoughton, Substitution revisited, Theoretical Computer Science 59 (1988), no. 3, 317–325.
76. Joseph E. Stoy, Denotational semantics: The Scott-Strachey approach to programming language theory, The MIT Press, 1977.
77. Benjamin Werner, Une théorie des constructions inductives, Ph.D. thesis, Université de Paris VII, 1994.
78. Glynn Winskel, The formal semantics of programming languages: An introduction, MIT Press, 1993.
Notes
1When I write ‘sets’ I mean “sets or whatever fulfills the same function in the reader’s favourite universe”. ↩
3 Thank you to the designers of . ↩
4Beyond the basic idea of a set as a collection of objects axiomatised in some first-order language. See [39] and [40]. ↩
5Note that FreshML is designed to be easy to prove things about, in particular T21.9. It is not designed necessarily to be easy to program in. A real programming language (also called ‘FreshML’) is future work under development, see [66]. ↩
6 Of course the semantics of programming languages are far more complicated than that but it is irrelevant here. The reader may also prefer to think in terms of, say, categories rather than sets. This makes no odds here, and since I shall go on to construct a set theory (Chapter II) I choose to think in sets. There is some discussion of presheaf models of this work in [18, 6], I do not expand on that work in this thesis. ↩ ↩
7In our paper [66] Pitts and I discuss the design of an ML-like language similar to this one in much more detail. There we use linear patterns and a system of ‘guards’ on them to achieve more-or-less the same effect as the nonlinear patterns and freshness condition (R4.12) used here. ↩
8Though that would be jolly nice. ↩
9The basis of mathematics is the tautology. ↩
10See the index of [72] under ‘individuals’. If that work did not introduce atoms, it discusses them as if they were new. ↩
11Why not use an axiom insisting that ? It is inconsistent with FM. See 11.4. ↩
12Readers not familiar with the methods of set theory may be disturbed by the use of function symbols like in (AtmInf)26, since in D8.1.1 we claimed the signature contains only and —no . It is standard to introduce extra symbols so long as they are defined entirely in terms of existing ones—so they are macros/syntactic sugar or at least conservative extensions to the theory. We should be at least peripherally aware of the precise nature of the language we are using so that we can prove metatheoretic results by induction on its structure, e.g. equivariance in T8.1.10. Cf. R16.1.1. ↩ ↩
13The point being e.g. in the second case that we actually mean a binary predicate (x y) in the logic of ZFA giving the graph of F , but if the reader can obtain a model of (somewhere in some external universe), there really will be an associated external function F : arising from the predicate. ↩
or the logic of FM, see the comment in bold font below and T9.1.6. ↩
15Parameters are often left implicit, so in theory there is scope for error applying this result. In practice this seems not to be a problem. For example (D26.7.1) has quite a complicated definition but it is crystal clear (at least to me, I hope the reader will agree) that it is not parameterised. ↩
16Independently of the particular implementation of functions in the set-theory. ↩
17cf. D23.1.6 where we build a syntactic approximation to this relation. There we shall sometimes find it convenient to write apartness judgements x#a instead of a#x. ↩
18Within the limits set by L9.3.4. ↩
19 We can’t add a constant a and appropriate axiom to the signature because that would destroy equivariance. So we add a variable symbol and appropriate axiom instead. Actually, this point is rather important. ↩
20The reader might wonder what the quantifier is doing; we do not seem to morally use it. But we do: it guarantees that c#x y so that the concretions x@c and y@c exist (D9.5.14 and C9.5.13). ↩
given in two flavours. In Part 1 of the proof of C9.6.9 I explicitly convert the first flavour into the second, see (33)54. Sometimes I favour the first, for complete rigour about what is new for (everything free in the scope of the fresh/ binder, at least), sometimes I prefer the second, for convenience. ↩
22The idea is from [17, 2, p.5]. ↩
23Initial objects are unique only up to isomorphism. This is not an issue, we shall treat initial objects as ‘morally unique’. ↩
24The paranoid reader might worry how we know that the class F n() is a set. F restricted to Nat is clearly a function-set (proof omitted), we can now apply (Replacement)26 and take . Let us not worry about this issue. ↩
25Recall that Obj(SetsFM) is the FM sets and SetsFM((Z ) B(Z )) is the collection of function-sets from (Z ) to B(Z ). ↩
26Cf. oNat on p.13. Examples permeate the text. For informal examples see D4.8 and D4.11. The mathematics leading up to T10.5.8 is clean and slick, in ZF that would be absolutely impossible. See also 22.2. For a moment of particular drama see R23.1.13. ↩
27Incidentally, in p.72 can have no synthetic counterpart since different binding signatures can share a common naïve signature. ↩
28Incidentally, we see a related issue in [49, Cor 11.3, p.128 and 11.1,14] in HOAS. One form of HOAS binding is to interpret it by a function space like X X . We get name-for-term substitution ‘for free’—but on the other hand we have to have name-for-term substitution for free. In the case of the -calculus (the example in [49] is ‘Dynamic Logic’ in Chapter 7) this is not what we need. This problem does not arise in FM. We do have ‘name-for-term’ substitution for free on the datatype of processes, because [ta] (D10.7.13) is defined on all of PreStx. However, nothing says the sets so obtained must be in our datatype or in any other way significant, and in the case of terms of the -calculus as declared in the binding signature on (35)58, they are not. ↩
29We don’t need L11.5.4 to see this. If U supports x (Φ(U x)) and V supports y (Φ(V y)) then from D9.1.2 it is evident that Φ(U V z) for z x y)xx y. ↩
30Recall from the beginning of the proof that we’re trying to prove “HFS is closed under (Collection)26”, so we assume all free variables and parameters range over HFS and prove what we get out is also in HFS. ↩
31This notation is not definitive because it does not specify the scope of the binding, cf. ft75163. ↩ ↩
for no particular reason. ↩
33If this does not convince the reader, consider that for any rule x(x y) (x y) by T9.4.6 it is actually logically equivalent to the rule (x# y) (x y) ↩
34Except, note, for atom-abstraction ax (D9.5.1). This is ‘injective up to -equivalence’. We designed it to be. ↩
35Isabelle experts will probably find Chapter III slow in places. I urge tolerance. This is a feature not a bug; I want this chapter accessible to the non-expert. ↩
36 For example, if we add atoms to ZF set theory the axiom of extensionality changes from A B A B B A to A B A B A B B A ↩ ↩
so the proof of the result (A BC DA C B D becomes more complicated, because we first have to verify that (A B) and (C D) . Of course this should be easy to prove, but if five hundred results are involved it becomes a burden. ↩ ↩
38For example, in Isabelle/ZF we can prove that a False automatically. This is implicitly used in a highly automated proof of in ZF.ML, right at the beginning of the implementation. It caused me endless trouble because the proof kept on breaking with no indication of the hows and whys ↩
reimplementation can become impractical with astonishing rapidity. ↩
40In the actual implementation files the name of the theory has not been changed from the original ‘ZF’. ↩
41This claim is direct from the original Isabelle/ZF file ZF.thy. From my own experience I can agree. ↩
imperative, technical, difficult to debug, difficult to modify. ↩
43It comes from Halmos [23]. ↩
44But we used empty atoms in FM. Are then not Quine atoms a ‘hack’? Indeed so! It has been suggested that both are good solutions, not hacks. I’m happy to accept that, but propose we call them ‘hacks’ but not ‘kludges’. The real reason for this preference is that using ‘hack’ in connection with my Isabelle work gives it a ‘je ne sais quoi’ of swashbuckling romance which makes up for the ‘pourquoi moi’ of actually doing it. Do not begrudge me my small fantasies. ↩
45This has Atm on the LHS. does not. ↩
46We prove this special case using a standard tactic I developed to split it into a multitude of subcases according as a and b are [1. not atoms], [2. atoms not equal to x], or [3. atoms equal to x], and then by automation with a standard library of basic results about permutation on atoms. Without this technique would not bear thinking about. ↩
but what we can do is add equivariance as an axiom. See 20. ↩
48Note however that in the list above does appear to apply permutation to a function h. Of course here h::i is an internal function-set. ↩
49See 19 and in particular p.147. See also R16.9.1 and the discussion following it. ↩
50Destruct-resolution with obtains a new condition from two old ones, but also leaves one of the old conditions hanging around littering the proof-state. It’s just the way the rules of resolution work out. What does is tidy up. ↩
51Elements pairwise disjoint and union equal to Atm. ↩
52There is also the low-level a, which we avoid. It is implementation-dependent and bad for proof-search. ↩
53In 18.2 I discuss a better way of setting things up that would eliminate the typing conditions. ↩
54a#x is defined as a Supp(x). We define independently and connect it to # in L9.5.7. ↩
55For me, this is the indication that there’s something wrong with the Isabelle/FM treatment of equivariance. The proof of a basic result should get simpler as the theory develops. When the reverse happens, there’s something wrong. See 18.2 and 20. ↩
56Hence is actually in two libraries: and . LEFT and RIGHT denote the direction the transposition travels. S is a technical flag meaning ‘safe’ (see [58, 11, ‘The Classical Reasoner’], in particular 11.4, first paragraph) I stands for ‘intro’ and D for ‘destruct’. ↩
57Isabelle experts may wonder how we can simplify to using pure resolution, with as shown, in . I wrote a couple of two-line ML functions which take a list of simplification rules (like ) and a list of contexts (like "%x.?y:[?a]x") and return a long list of intro (or elim) rules that implement all possible simplifi-cations within the possible contexts. You just pass this list to , et voilà, simplification with a tableau theorem prover! Has it been invented before? It was terribly useful, maybe it should be provided as a standard facility. ↩
58I was thinking of this when I wrote Item 2 of R16.6.1. ↩
59The Isabelle/ZF datatypes package is under continuous development so the version my implementation inherited from Isabelle98-1/ZF (R14.4) may differ from any the reader may be using. ↩
60I should have made aTerm::AtmPart. Taking aTerm::i was a strategic error and should be changed in the next code rewrite. See R20.2. ↩
61Perhaps the designers of Isabelle would like to include this facility in future versions? ↩
62The ideas of 18.2 (make Perm respect types of atoms) would pay off here. would lose its typing conditions because Perm(a,b) would be the identity for a, b badly typed. This would simplify subsequent proofs, see R16.6.7. ↩
63Recall that (a b).u is sugar for Perm(a,b,u). So Perm(a,b), sugared, is . ↩
64 "(a b).x:A. P(x)y. " see R16.6.4. ↩
65I know the code quite well (R19.1.1). ↩
66In strict ZF we would not even have a -quantifier. ↩
67We could simulate the effects of Equivar by declaring a rule (a b).Const=Const for every Const in the theory and giving the result names in some systematic way. The ML program would then access these results through this systematic naming system to prove the required result. This makes for a lot of rule declarations and we would have to make new ones for each constant ↩
abstraction, concretion, fresh, etc. ↩
69We have no theory of FM domains so cannot handle nontermination. We would not necessarily anticipate difficulties developing such a theory, but proper denotational semantics are complicated in themselves. ↩
70Who says there’s no such thing? ↩
71 To avoid confusing people with the truth I place this comment in a footnote: here “-equivalence” does not refer to terms of FreshML, which are in the ‘meta-level’. It refers to -equivalence of ‘object-level’ closed values of type representing (possibly open, possibly unevaluated) terms of the -calculus. See R22.1.6. This relation on closed values of type will be written , rigorously constructed in D26.3.1, and used in the rigorous restatement of this result, T29.25. enters into the proof via Fig.38196. ↩ ↩
72As in FMLtiny (R12.1.2 Item 1) terms and values are defined in Fig.31164 by mutual induction. We did not consider mutually inductive definitions in 10. However as discussed there they can be encoded in ordinary inductive definitions so in theory the mathematics is powerful enough to include our syntax. ↩
73Recall that syntax and denotation are living in the same universe, cf. R21.12. ↩
74In 10 we did not consider binding signatures for mutually inductive definitions such as that of D22.1.4. We can encode them using ordinary inductive definitions (Item 1 of R12.1.2), so 10 is powerful enough to include the syntax we are defining now. We gloss over the issue. ↩
75Binding in FM datatypes has a precise meaning, that is what this thesis is all about. See R12.1.3. Note that this underlining notation is ambiguous because it does not specify the scope of the binding (cf. ft3191). The scoping is as I hope the reader would expect, the only slightly complicated binding is that let x in binds x in but not . I.e. Let is a function on [Var]Terms Terms (cf. 12). ↩ ↩
76Here I do not get closed terms and values ‘for free’ from D10.7.8 as I did in D12.6.1 for FMLtiny. If we automated this proof (31) we might prefer to do so because it sidesteps the typing relation. However, if I did that here the reader might ask to see a proof that the version using empty typing contexts above is identical to the free version, and that would be a tangent. ↩
77This means quite precisely “aVar(a) and bVar(b) not identical FM sets”. See R21.11. The informal denotations are equal: ⟦aVar(abVar(b)⟧. ↩
78Having things this way does no harm and sometimes the extra power is useful. ↩
79This is rather exciting, which is quite remarkable considering how boring syntax usually is. FM gives us something that even nonrigorous ZF does not: even if we are comfortable choosing ‘new’ variables in ZF and never mind about the rigour, there is no mechanism for deciding whether another variable we choose ‘new’ can safely be assumed equal to the old new variable. What allows us to do this in FM is simply that is a quantifier with a well-defined syntactic scope, which we can easily observe if we write our propositions carefully. Furthermore, this scope distributes over conjunction (C9.4.5) so we can turn two new variables into one new variable where appropriate. In fact we have seen this all before in Isabelle/FM. See 16.7 and in particular R16.7.1. The ability to assume two new variables equal was used time and time again in Isabelle/FM in situations just like T23.1.14. ↩
81Indeed, for all atoms a Supp(aa (L9.3.6). ↩
82In particular, results about apartness judgements which state that we can’t prove something will need conditions to exclude nonsense contexts. ↩
83Thanks to Simon Peyton-Jones, ([61]) for raising this ‘pretty-printing’ function question during a conversation. ↩
84Using the fact that ( x : #xc) z# x# The issue is as in T23.1.14 the commas separating the parts of these contexts, which have a particular meaning (N23.1.8). x was chosen fresh for all variables in the context at the time of its declaration, which included , z, and zc, so by C23.1.10 and C13.2.1 this equality works. ↩
85This is standard terminology in the field though what I call ‘adequate’ is more usually called ‘preadequate’. See for example [42, p41 4.1] and [65, p8 Def2.2(iii)]. ↩
86In D26.2.2 it is not obvious that a largest R closed under the rules of Fig.37193 exists. Suppose S T are such. Is it the case that S T is closed under the rules? No. Consider (170)193. It may be that
but not
Thus S T is not necessarily closed under (170)193.
There is a ‘patch’ for this. Call the rules in Fig.37193 by the name Rules. We consider a modified version Rules’. Where there are two troublesome conditions like in (170)193 in Rules, Rules’ splits the rule in two:
There is clearly a largest set closed under Rules’, call it . A set closed under Rules is closed under Rules’ so if we can show is closed under Rules as well, it must be the largest such. It suffices to show that is transitive. This is easily done by showing that the relation
is closed under Rules’. Lassen has this problem in [42] and addresses it in some generality in [42, p.29, 3.7]. ↩
87We see this trivially in L26.2.4. More seriously, the reader is referred to the proofs of L28.19 and C28.24. ↩
88When doing induction on we would like backwards proof search to be linear. The side condition a keeps the rule disjoint from simple congruence. ↩
89I have not only lifted Dr Pitts’ method, but could never have controlled it without his guidance (it is not easy to understand, at least the first time). I take the opportunity to thank him. ↩
90Are you reading this? Incredible! Here’s a joke for your entertainment: “Which is worse, ignorance or apathy? Who knows? Who cares?” ↩
91Note in passing that if we had fixedpoints at every type (we only have fixedpoints at function types) this result would be trivial, we would just use fix x : x. ↩
92Except naturally for those having nothing to do with inductively defined sets such as L23.1.9, C23.1.10 and L24.1.5, or L26.5.2. Except also for L26.4.4, which we could prove by co-induction only FM gives it to us ‘for free’. ↩
93The one ‘renaming’ lemma we do use is L26.4.4 but it describes -equivalence on values of type , which represent -terms not up to -equivalence. In a strong sense this is the whole point of FreshML. ↩
94Note, one could argue that [34] is an ‘investigation’ rather than a ‘proof’. Discussion omitted. ↩
95This has not yet been done, work includes Chapter IV and [66]. ↩
96Though there are necessary limits to this emulation, see R33.4.1. ↩
97Concrete evidence supporting this claim appears in this thesis. The mathematics of Chapter IV is conducted entirely FM-style (see R21.4) yet proofs like that of T24.1.7, L24.1.8, T27.11 look traditional. ↩
98At the time of going to press there is a draft paper [6]. There the authors import what they need of FM techniques and logics to apparently satisfactory effect, and without having to build all of FM set theory. So it really does seem to work. ↩
99Unlike Isabelle, say, which hijacks the ML command-line but uses it as a semi-imperative meta-language to manipulate an ML datatype of terms. ↩
100Which is very up-to-date. So much so in fact that it is unpublished at the time of writing. It is available on the net. ↩
101No misprint, the page and section numbers really are the same in both. ↩
102 However, the construction is ad hoc in the sense that presheaf categories can give semantics for almost everything. In a sense, a system that explains everything, tells us nothing. ↩
103This takes the philosophy of HOAS, to model object level variables using meta-level variables, to its logical conclusion. ↩
104Thanks to Randy Pollack for drawing my attention to this work. ↩
105Thanks to John Harrison ([30]) and Konrad Slind ([31]) for educating me about HOL-light and HOL. ↩