FM-HOL, A HIGHER-ORDER THEORY OF NAMES
Abstract. FM (Fraenkel-Mostowski) set theory techniques were developed to give good support to inductive reasoning on formal syntax in the presence of -equivalence and variable binding. The original set theory has inspired a Higher-Order Logic (HOL) theory, FM-HOL, presented in this paper. FM-HOL has similar facilities for handling syntax-with-binding to the original set theory, but is mathematically more powerful, introduces several novel features, and is much better suited to machine automation. This paper concentrates on the mathematical aspect of FM-HOL, presenting it as an improved foundation in which to analyse syntax-with-binding.
1. Introduction
This paper is about the the problem of variable binding and -equivalence. Consider, for example, unwanted variable capture in the -calculus: we do not expect () to evaluate to , but to for some ‘fresh’, ‘local’ . The underlying function is capture-avoiding substitution [] which is expected to rename to . Old versions of LISP displayed this phenomenon, when LISP macros with local variables can see them accidentally captured by the global context into which they were expanded.
So what is happening mathematically, and how are we to specify elementary functions like substitution and -equivalence? One way is to take the type of variable names to be the natural numbers , and choose increasingly larger ‘fresh’ numbers as names. For example, we could define a type of terms for the -calculus by
(1)
and -equivalence = on Λ by
where ‘’ denotes some which is larger than any occuring in and and hence does not occur in .
But there are problems. For example do we mean “for all such ” or “for one such ”. The former choice is good for doing induction going down (where we want a strong hypothesis), the latter for doing induction going up (where we want a weak proof-obligation). There seems to be no happy compromise (see R5.6).
Here, at least, we can get away with [] denoting simple textual substitution, because we have assumed completely fresh for . Later on, when we define evaluation relations, we may have to consider full capture-substitution. The technical details of choosing fresh variable names only causes further problems. 3
All analyses agree in taking Λ of the form
(3)
De Bruijn indices typically model varset by and abstractions of (Λ) by Λ itself. This works because we so to speak ‘twist’ the meaning of the variable symbols under the binder Lam so that 0 refers to the abstracted variable symbol, 1 refers to variable 0, 2 to 1, and so on. This leads to rather ‘twisted’ inductive definitions out of this datatype, as we inductively ‘untwist’ going under abstractions (incrementing and decrementing variable numbers according as we add or remove abstractions from above them, at a likely cost of () in the size of the term).
HOAS models abstractions either as varset Λ or Λ Λ, where varset may be , or may be a new type. The technique tends to suffer technical difficulties, for further discussion see [3, paragraph 33.2].
There are many other approaches ranging from category theoretic constructions which work by moving into a more-or-less exotic foundational system (for just one example see [6]), to work by Pollack and others [9]. 3
FM is a new approach with a pleasantly elementary feel, and which seems close to informal practice. FM is not a particular theory, but a collection of principles which we try to realise in the context of a set theory, programming language, etc.
The original FM theory, which motivates most of the principles and definitions in this paper, was FM sets. FM stands for “Fraenkel-Mostowski”, who invented permutation models of set theory to prove the independence of the axiom of choice, see [14]. Sixty years later Pitts and I hijacked the idea of set-theoretic atoms to be variable names (varset in (3)), and the Fraenkel-Mostowski atom-permutation on the set universe to rename variable names on sets denoting terms of syntax ([] in (2)). See and in R3.3, and 2.
Existing literature on FM techniques includes [3] (my thesis), [1] and [2] (twin papers which first presented FM set theories in refereed publications), [11] (a first-order logic by Pitts with elements of FM), and [12] (on a version of ML extended with constructs inspired by FM for manipulating syntax up to -equivalence). The literature is growing. Besides this paper, [5] (a discussion of an implementation and testing of FM techniques in the machine environment Isabelle) has been submitted for publication. Work proceeds on the programming language and also principles of unification for logics with formulae describing binding, and tutorial papers are in preparation. 3
In this paper I discuss a recently-invented theory FM-HOL, a Higher-Order Logic (HOL) with elements of FM. It carries out a similar programme in HOL to that of the set theories [1] and [2]. But I see this paper as more than a change of foundations. We significantly extend FM with many novel definitions. For example the treatment of small sets of atoms in D4.2, the methods of construction of abstraction sets in 6, and the concept of ‘nameable atoms’ introduced in R7.8 and discussed in the surrounding text.
FM-HOL is also designed to be far better for computer implementation than FM sets. I argue the case for this in a description of an FM-HOL implementation in Isabelle [5]. I believe that this too is a very significant plus for FM-HOL and I refer the interested reader to that paper. 3
2. Overview
We write ‘ of type ’ as or : . FM-HOL has no polymorphic types but we will want to refer to type-indexed constants such as Inl() : (). We call this a type-scheme and write it () or just ().
FM theories have an equality type of atoms along with an action of permutations of at all types, written for some , see D3.1. is the varset of (3), its elements are intended to represent variable symbols of an object language whose syntax is constructed (as an inductive datatype) in FM-HOL. Thus the Λ of (1) can be implemented in FM as
(4)
The significance of the permutation action is a little more subtle. Consider a transposition () for : and its action on LamLam() in the Λ of (4). We shall prefer the informal notation () for readability. Observe that
(5)
Thus transposition provides a notion of atom-swapping which by being an isomorphism on avoids some of the problems of []() when [] identifies and to (). There is no loss in expressive power, e.g. in the third line of (2), () and () will do just as well as [] and []. There is a good case that atom-permutation is more elementary than capture-avoiding atom-substitution, and mathematically better-behaved than naïve atom-substitution. Cf. [2, Chapter 2].
Using this dedicated type of atoms and its permutation action at all types, we find in 6 that we can define a type of abstractions of of “elements with one distinguished bound atom ”. This plays the rôle of (abstractions of (Λ)) in (3) and allows us to define an inductive datatype of syntax-with-binding, e.g. an inductively defined type of -terms up to -equivalence (see (26), (30)). The motivation for using is that it seems better-behaved than many of the alternatives, for example in HOAS or itself (‘twisted’, as discussed above) in the de Bruijn indeces approach.
Furthermore, comes with well-behaved logical and functional tools for reasoning and programming with types of syntax-with-binding, e.g. the new quantifier whose excellent properties are described in 5. To my knowledge these tools are unique to the FM approach.
We finish the mathematical development in 7 with a discussion of axioms of definite and indefinite choice in HOL with FM, which are in some sense final elements in the development of a fully-fledged, implementable, theory.
For the reader unfamiliar with FM, this paper presents FM-HOL as a workable environment for manipulating syntax-with-binding. For the FM practitioner, the paper contains a new FM theory, as well as various new definitions and principles of proof which I have found useful and wish to showcase.
3. HOLlift
HOL is a classical higher-order logic with a type of atoms and a (polymorphic) constant lift : (where denotes the type of permutations of ):
For brevity write ‘’ as ‘’. Using the notation of N3.2, and lift satisfy the following axioms:
A finite list is a vector written or (). For , denotes applied pointwise on each element of .
denotes composition of permutations in .
is closed when as syntax it contains no free variables. Thus and are closed but ()() is not (though it -reduces to ). This is a property of syntax and not any underlying denotation.
It is convenient to write Id for the identity function : . We use this notation frequently to denote the Id on , which is in (e.g. R3.4).
So HOL is a HOL with a distinguished type of atoms and an atom-permutation action at all types (given by lift), just as discussed in R1.3 and 2. (L) is a standard property of a ‘permutation action’, (L) says it acts at in the reasonable way. Further standard properties of a permutation action, e.g. Id (N3.2), are considered in L3.5. 3
(LE) is the interesting axiom. In general mathematical terms, the standard permutation action on an -ary function is () (cf. Item 4 of L3.5). (LE) can be read as asserting that -permutation has no action on functions specified by a closed term and that in this sense the meta-language is blind to the identities of individual atoms.
In the light of Item 1 of L3.5 below, we now know—immediately, without any induction—that for example in (4),
Such equalities are very useful, as is the fact that they are immediate and do not require inductive proof: the inductive action we see in equalities such as
are given to us ‘for free’ by the theory by virtue of its equivariance.
3
Another significant feature of this theory is the fact that the permutation action is defined at all types, not just by induction on types of syntax. This allows us to permute atoms in elements that are not obviously syntactic. For example, we can rename atoms in elements of types of abstractions (first mentioned in 6). Just to look at the definition of elements of abstraction type, (21) and (22) in D6.1, it is by no means clear that is a syntactic entity in the same way as, say, (assuming are). Nevertheless, we can rename the atoms inside : using the permutation action. And indeed, we need the permutation action in the proofs of 6 to prove the necessary results which show that is ‘ with bound’, see R6.7.
Michael Norrish has suggested an alternative formulation of (LE). I do not discuss it here but it is important. See [5, 5.15] and future publications.
Various basic properties of the permutation action follow from D3.1:
1. Permutation distributes over meta-language functions: () (), for a closed term. Note in the case we have : the meta-language may not contain object-level variable symbols.
2. (and ).
3. Id.
4. Permutations acts on functions in the standard way: (), and ( ()).
1. Direct from (LE), applying to both sides.
2. From (LE) taking .
3. Combining Item 2 with (L). For Id see N3.2.
4. Again from (LE) taking () and using Item 2 to simplify.
We come to the second step of constructing our theory:
4. FM-HOL
We may call : a function into a predicate, or also a (HOL)-set. Sets are usually written : with elements : . We borrow set-theoretic notation. E.g. for a HOL-set , denotes (). We may write or for the ‘empty’ set , and or for . We borrow other notation as convenient, e.g. .
Define a predicate S : () given by
(6)
( means “there is an injection from to ”.)
We call small when S and large when S. A picture might illustrate the point:
S is a theory of small sets of atoms (object-level variable names). is ‘small’ when we can enumerate it, when is not enumerable, and also large enough to contain copies of itself.
A reader familiar with FM, perhaps from any one of [1], [2], or [4], will recognise this as a generalisation of the situation in FM set theory, where ‘small’=‘finite’. Here the slogan is ‘small’=‘well-orderable’.
This principle, and the details of the definition of smallness (6), give the notion of smallness excellent properties which make possible the development in the rest of this paper. D4.2 is one of the contributions of this paper to FM theory as a whole. 3
S is closed under finite unions and finite (nonempty) intersections. In fact, S is closed under unions indexed by small S. Proof from the properties of well-orderings. The slogan is “small unions of small sets are small”.
For and : a permutation on atoms write
(8) fixes for “”
For an arbitrary , read
(9) “ : fixes ” as “ supports ”
Using this notation we define Supp : () by
Supp() is a notion of the “variable names inside ”. Indeed,
For S, Supp( Supp(). Also, for terms of a datatype such as : Λ as defined in (4), Supp() is precisely the atoms occuring in . Proofs omitted. 3
But in (10) we take an intersection over small supporting . In the case S or Λ it is clear that at least one such exists. But what of arbitrary ? We introduce an axiom:
FM-HOL is HOL augmented with an axiom
(11) Supp() S
Every has some (not necessarily minimal) small supporting set. The slogan is “all elements have small support”.
Supp() supports and, by construction, is a minimal supporting set.
Using the technical lemmas and definitions below (for a comment on the fact that we can prove them, see R4.3).
1. For any : (), either Supp() or Supp().
2. For any : (), S iff S.
3. For all : (), either S or S, and not both.
4. Supp( Supp(), so is small and is large.
5. Hence is infinite and cannot be well-ordered.
6. For S, .
1. By calculation.
2. Observing the diagram (7).
3. Supp() S always by (11), use previous results in this list.
4. Observing Supp( and using the above.
5. That is large was observed above. Large sets cannot be well-ordered by definition (cf. (7)).
6. Again, see (7).
In view of L4.10 we write is large when it is not small, and write the set of large sets of atoms (cf. R4.16). Observe that ( S and recall from L4.10 that S .
Any small set injects into any large set .
By L4.10 we know and are small. By L4.4, () is small. We now consult the picture (7) to inject () into its complement () , and hence into .
The following technical result is highly significant. It brings together the properties of small sets of atoms (see (6) and (7)) with the permutation action to prove that for any we can ‘shift’ its support Supp( to a fresh .
Recall that any has small support by (11). From the proof of L4.12 we see that for any and any there is an with Supp() and such that .
Here means , , and is the identity off Supp() Supp(). Call a renaming permutation. It “shifts the support of to be (somewhere) inside ”, and this result asserts that for any , at least one such a exists:
This all works towards the following two results:
If and support then supports .
The proof is technical but I include it because it has a certain beauty. To visualise it, see the bracketed comment at the end of this proof. If or then we are done. So let . Consider some fixing and . We prove fixes , which completes the proof.
Choose large and disjoint from Supp(). Let be a renaming permutation for and , for as discussed in L4.13.
Observe that fixes . It follows by our assumption that supports that , whence
However, fixes . So by our assumption that supports , we have as required. (I would draw a picture of this proof. I suggest a two-dimensional Venn diagram, with small sets , represented by intersecting circles inside a large box .)
Any descending chain of small sets terminates. This property is inherited from the corresponding property of well-orderings (ordinals).
of L4.9. Suppose Supp() does not support . We examine the definition (10) and using L4.14 deduce the existence of a non-terminating descending chain of supporting sets above Supp(). This contradicts L4.15.
We now continue to develop a theory of syntax-with-binding using as object-level variable names. The reader may wonder why we called the large atoms instead of, say, L for large. stands for ‘new’ and gives rise to a novel quantifier whose theory we now develop: 3
5. # and
Recall from D4.11 we introduced the notation for the set of large sets of atoms.
Write or () for “”.
the quantifier has excellent properties:
distributes over all structure of the HOL logic. That is:
(16)
(17)
From L4.4 and L4.10 we can deduce that S and are closed under pairwise meets and joins, S and . This proves all formulae save the last. To prove that, observe that FM-HOL is classical so for any we know or , proceed by cases.
The significance of L5.2 is that we may choose two fresh atoms in different proofs of and , and it does not matter which ones because we can always use L5.2 to deduce ()(). Similarly, in a proof if we wish to prove from it suffices to prove () (), that is, to ‘choose a fresh atom’ and prove () ().
Write
and read this as “ is fresh for ” or sometimes “ is not ‘in’ ”.
Observe that a predicate : is just a set of atoms , hence subject to L4.10. We can use this and our new definition D5.3 to turn D5.1 into directed intro- and elim-rules for :
#(().
By L4.10 Supp() or Supp(). Since () and Supp() we have Supp(). Since Supp() S, we have as required.
(()) #().
We have assumed and Supp(). Since Supp() S we know Supp() so () as required.
Thus is a fully-fledged binder with well-defined intro- and elim-rules. Note how they pleasingly combine (the best) aspects of and rules. Recall R1.1. When doing induction, to prove () it suffices to establish it for one fresh , and conversely when we know () we have () for any fresh . In FM, we have the ‘happy compromise’ spoken of in R1.1. 3
We conclude by using to rewrite (2), a definition of = on the Λ of (1), in FM style on Λ of (4):
(19)
It remains however to bind atoms in syntax:
6. Construction of
Define
More generally, for types and , we may define
Define new type-constructors by
The coincidence between the special case of is deliberate, they are the same type, proof omitted.1
Supp() Supp() Supp() and in particular #. The proof is a simple corollary of the technical lemma Supp() Supp().
An alternative characterisation of is as the equivalence-class [] where
(24)
R binds only , read R() as “rename to (by ) in ”. It is defined by
where is defined in L4.13.
We prove an equivalence relation. We then use a technique similar to that in the proof of L4.12 to find such that and has support completely fresh for the context, and use this to deduce Supp() is disjoint from Supp([]). Clearly []. From all this we can conclude [].
Supp( Supp() Supp(). Proof using L6.4.
For : and a fixed : , . Proof omitted.
L6.3, L6.4, and L6.5 tell an attractive story: abstraction simply forms the pair , but also binds precisely those atoms which may occur free in .
L6.6 completes the picture and tells us that in particular, is the type of with one distinguished bound atom . 3
This morally justifies our usage of the following as a datatype of -terms up to -equivalence:
(26)
Here the term is represented by Lam(Var()). Var() plays the rôle of Lam(Var()) in (one flavour of) HOAS, Lam(Var(0)) in De Bruijn, or simply Lam Var() in a naïve representation.
The formal justification for the claim that is -terms up to -equivalence is by defining a function from Λ in (4) and (19) to (26)
and proving surjective and that its kernel is = as defined in (20). Details omitted. 3
Thus we have a definition of -terms Λ quotiented by =, Λ. The top-level structure of is not a quotient, but an inductive datatype. Thus the definition of some standard function on , e.g. capture-avoiding substitution, is purely inductive, but to construct it (see (30)) we need definite choice :
7. Axioms of choice and consistency
HOL and FM-HOL both have easy models in FM sets with types as sets and function types as sets of function-sets. Thus, these theories are consistent.
Write the semantic mapping function [[ ]] . Then [[ ]] is the set of atoms , [[ Tran ]] is set-transposition restricted to the function-set of its action on [[ ]] .
There is only one significant detail: types do have to be interpreted as equivariant sets (“[[ ]] is equivariant for all ”, see R3.4) so that for all and [[ ]] , [[ Tran ]] () [[ ]] always.
In an automated environment it is extremely useful to mediate between predicates and functions. That is, if we construct a predicate () we want to be able to derive from it a function symbol () such that ( ()). No sugar—we want an actual closed term : () (), and we want to be able to prove (()()) in the logic.
The two usual candidates for constructing such an are indefinite choice, also known as Hilbert’s , and definite choice, written . is a polymorphic constant symbol : ( ) with axiom (()) (). Given that, we take to be ().
is a polymorphic constant symbol : () such that (!()) (). We can take to be (), which lets us form a function-term from the term for its graph.
To me seems vital, because forming functions from graphs is common practice which an automated HOL should support. 3
HOL, and therefore FM-HOL, are inconsistent with Hilbert’s R7.2. Cf. the corresponding FM sets phenomenon in [2, Remark 4.6].
Consider two terms
Observe that both and are closed terms yet (). This contradicts (LE) for and ).
However. . .
Call a type pure when every is equivariant (for all :, () , see R3.4 and cf. [2, Remark 4.2]), standard examples are and . If and are pure then so is , proof omitted. Thus the type-class of pure types is closed under function-types. It is consistent to postulate Hilbert’s : () for of that class, proof omitted.
Thus in an automated environment with type-classes, such as Isabelle/HOL, we do not actually lose any theory, since the standard theories of real numbers, groups, and so on, are carried out in the pure types.
As the name suggests, FM-HOL lacks . But it is consistent to add it, as we discuss below, and we call the theory obtained FM-HOL.
Now adding to FM-HOL leads to no obvious inconsistencies in the logic. However, there is a snag proving consistency using the set-theoretic models we used in L7.1 to prove consistency of FM-HOL:
In a set-theoretic model of FM-HOL as discussed in L7.1, consider how to add [[ ]] for each type . This is a function-set in ([[ ]] [[ ]] ) [[ ]] .
In fact FM sets has definite choice so we might think we could simply interpret the HOL- as the function-set obtained restricting sets- to [[ ]] [[ ]] .
But is typed as a total function and most do not satisfy !(). What should [[ ]] ([[ ]] ) be for such a ? Sets- can default to some fixed set, e.g. . [[ ]] cannot, because the default value must be in [[ ]] . Consider the case . Whichever default atom [[ ]] we choose for “bad ” the closed term will not satisfy (LE) in the model, since for any , ()[[ ]] ]] .
There are (at least) two solutions. Pitts suggests a domain-theoretic semantics so that [[ ]] can default to . Personally I miss the simplicity of a set model of our HOL and want to preserve it if I can. I think I know how to do so, and with honour too: 3
Introduce a constant symbol : S with axiom
(28) : S
(Recall the notation of D4.2: means “ injects into ”.)
Now consider a system FM-HOL given by the above along with a modified version of FM-HOL such that (LE) is taken to be
(29) fixes ( () when closed.
(‘ fixes ’ defined in (8).) 3
Thus gives us a stock of “nameable atoms” for which equivariance (LE) need not apply, and such that we can consistently introduce into the meta-language closed terms (names) for them. 3
In this paper we introduce to solve the technical problem of modelling also for badly-typed (R7.2, R7.6), but it has independent motivations.
Suppose we want to represent in FM-HOL this common syntactic declaration: “Elements of are written ”. Are not really these ‘nameable atoms’? Similarly for other sources of distinguished atoms, such as ‘stderr’ ( is UNIX filehandles) or ‘Bool’ ( is base types) and so on. We might introduce a separate type such as and use a sum type for ‘, and . . . ’, or ‘system filehandles and user-defined ones’, etc. But in automation this carries a significant penalty in efficiency and readability (note for experts: and of course if we look at the actual set-theoretic denotation, using just ‘hacks’ in using the expressivity of the object-level).
An independent motivation for nameable atoms is as expressing atoms introduced by an external context or ‘local theory declaration’. This is best explained by example. To implement a theory of groups in some machine system it is convenient to open a ‘local theory’, in which is declared a group . We prove our theorems about this fixed but arbitrary , then close the theory. When we do so is eliminated and our theorems, say, are lifted over an extra hypothesis “ a group”, to become a group .
This avoids the clutter of a standing hypotheses “ a group” in the proof-script developing the theory of groups and is nowadays standard practice in proving environments, which a FM-HOL implementation should accommodate (see for example [8] or [7, ‘Sections’, 1.1.1]). 3
Returning to the task of giving semantics to , we can construct an FM set theory with corresponding set and set equivariance axiom (29), and allow [[ ]] to default to some value with support entirely in in the case of ‘badly-typed’ input [[ ]] . S ensures is at least as large as any set of names we can enumerate, so that we can always find a new default error-value no matter what is in the context.
FM-HOL with nameable atoms and unique choice , as described above, is consistent. Further details of the proof omitted.
Using we can now give a sensible definition of substitution on in (26), the type of -terms up to -equivalence:
—which is what we would expect the definition to look like in an FM programming language.
In the final clause of this definition, that for Lam, we have made some effort to present matters attractively, as a user of an implemented HOL datatypes package might expect to type in. The specification, expressed religiously in the FM language we have had the space to develop in this paper, is
This formula adds no particular mathematical context to the development: for new there always exists such that , the underlying technical result supporting this is the renaming lemma L4.13, and it does not matter which we use, cf. 5 and R5.6. We omit further discussion.
8. Implementing FM-HOL, Conclusions
An FM-HOL-like theory called Isabelle/HOL/FM has been implemented and is described in [5]. It is not quite an implementation of FM-HOL. It uses a HOL meta-language essentially identical to the FM-HOL of 4. However, it constructs an FM set theory in a type of individuals (‘the set universe’) i, rather than directly implementing FM structures (such as , D6.1) in its own types. This was for reasons partly historical and partly practical. Concerning history, the implementation started off as FM sets, see the discussion at the start of 1. Concerning practicality, the inductive definitions package of Isabelle set theory (see [10]) seems better-suited to theoretical work. It has an emphasis on flexibility and doing everything inside the Isabelle theory which means if we hack the Isabelle theory (e.g. to include elements of FM) the datatypes package changes with it relatively painlessly. In contrast the inductive definitions package of Isabelle/HOL ([13, Ch.6]) seems aimed at the end-user. It is highly-engineered with lots of powerful ML code and slick user interfaces which assume certain things of the theory which FM is liable to make false.
At my suggestion Berghofer, Paulson, and Wenzel kindly reengineered the Isabelle/HOL system to make it independent of (see L7.3) except, apparently, for a hidden dependency in the datatypes package. Implementing Isabelle/FM-HOL now seems feasible. Perhaps I should simply go right in, hack Isabelle/HOL to Isabelle/FM-HOL, and if some ML code breaks then so be it.
While writing, I have always had applications in mind: when I motivated a new constant symbol, or a particular way of doing things, it was usually with reference to implementation. And yet I have tried to show the beauty of this logic as an abstract entity in its own right. And this beauty charms me. I hope my reader has enjoyed the story too.
References
1. 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.
2. M. J. Gabbay and A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing ? (2001), ?–?, Special issue in honour of Rod Burstall. To appear.
3. Murdoch J. Gabbay, A theory of inductive definitions with alpha-equivalence, Ph.D. thesis, Cambridge, UK, 2000.
4., FM-HOL, a higher-order theory of names, 35 Years of Automath, Heriot-Watt University, Edinburgh, Scotland, April 2002, Submitted.
5., FM techniques in Isabelle, TPHOLS, August 2002, Submitted.
6. 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.
7. Paulin-Mohring Huet, Kahn, The COQ tutorial, v7.2, http://pauillac.inria.fr/coq/doc/tutorial.html, LogiCal Project.
8. Florian Kammüller, Markus Wenzel, and Lawrence C. Paulson, Locales: A sectioning concept for Isabelle, LNCS, vol. 1690, TPHOLS99, Springer, 1999.
9. James McKinna and Robert Pollack, Some lambda calculus and type theory formalized, Journal of Automated Reasoning 23 (1999), no. 3-4, 373–409.
10. Lawrence C. Paulson, (Co)Inductive definitions in ZF, Isabelle System.
11. A. M. Pitts, Nominal logic: A first order theory of names and binding, Theoretical Aspects of Computer Software, 4th International Symposium, TACS 2001, Sendai, Japan, October 29-31, 2001, Proceedings (N. Kobayashi and B. C. Pierce, eds.), Lecture Notes in Computer Science, vol. 2215, Springer-Verlag, Berlin, 2001, pp. 219–242.
12. A. M. Pitts and M. J. Gabbay, A metalanguage for programming with bound names modulo renaming, Mathematics of Program Construction. 5th International Conference, MPC2000, Ponte de Lima, Portugal, July 2000. Proceedings (R. Backhouse and J. N. Oliveira, eds.), Lecture Notes in Computer Science, vol. 1837, Springer-Verlag, Heidelberg, 2000, pp. 230–255.
13. Larry Paulson Tobias Nipkow, Isabelle HOL: The tutorial (draft), February 2001, To be published by Springer.
14. J. Truss, Permutations and the axiom of choice, Automorphisms of first order structures (H.D.Macpherson R.Kaye, ed.), OUP, 1994, pp. 131–152.
M.J.Gabbay, mjg1003@cl.cam.ac.uk, Computer Laboratory, Cambridge University, UK
Notes
Date: July 15, 2002.
Many thanks to Andrew Pitts and Michael Norrish for their comments. Thanks also to UK EPSRC grant GR/R07615 which partly funded this research.
1Generalised abstraction was discovered independently by Pitts. ↩