Formal Aspects of Computing (2001) 0: 1–23
A New Approach to Abstract Syntax with Variable Binding
Murdoch J. Gabbay and Andrew M. Pitts
Cambridge University Computer Laboratory, Cambridge, UK
Keywords: Abstract syntax; Alpha-conversion; Permutation actions; Set theory; Structural induction
Abstract. The permutation model of set theory with atoms (FM-sets), devised by Fraenkel and Mostowski in the 1930s, supports notions of ‘name-abstraction’ and ‘fresh name’ that provide a new way to represent, compute with, and reason about the syntax of formal systems involving variable-binding operations. Inductively defined FM-sets involving the name-abstraction set former (together with Cartesian product and disjoint union) can correctly encode syntax modulo renaming of bound variables. In this way, the standard theory of algebraic data types can be extended to encompass signatures involving binding operators. In particular, there is an associated notion of structural recursion for defining syntax-manipulating functions (such as capture avoiding substitution, set of free variables, etc.) and a notion of proof by structural induction, both of which remain pleasingly close to informal practice in computer science.
1. Introduction
This paper presents a simple variant of classical set theory that turns out to be very convenient for developing the metamathematics of formal systems involving variable-binding operations. The main message we wish to get across is that a relatively small change to classical set theory, involving the use of atoms (or urelements, as they are often referred to), can reap great benefits for this aspect of metamathematics. In particular we will see that in such a set theory it is possible to represent α-equivalence classes of abstract syntax trees as the elements of an inductively defined set, rather than just the quotient of such a set. Moreover, this can be done in such a way that the techniques of structural induction and recursion, which Burstall did so much to promote in computer science [Bur69, Bur77], extend in a pleasant fashion from conventional algebraic datatypes to ones involving variable-binding operations.
But of course using a different set theory, even though it is very close to the usual one, is not a step to be undertaken lightly; so we begin with a critique of the current state of the art. It is oriented towards
Correspondence and offprint requests to: Andrew M. Pitts, Cambridge University Computer Laboratory, J. J. Thompson Avenue, Cambridge CB3 0FD, UK. e-mail:
the particular use of such a metatheory of variable binding that most concerns us, namely machine-assisted proofs about the structural operational semantics [Plo81] of programming languages.
1.1. Background
The theory and practice of specifying and reasoning about syntactical structures that do not involve variable-binding constructs is well understood. The theory involves such indispensable concepts as algebraic data types [GTWW77], inductively defined sets, definition by structural recursion and proof by structural induction [Bur69]; the practice can be seen in several general-purpose systems for machine-assisted proof (such as [GoM93, PaM93]). This algebraic, ‘no binders’ machinery is often applied to syntax that does involve binders; but in that case it yields overly-concrete representations in which large numbers of essentially routine constructions and proofs to do with renaming bound variables, capture avoiding substitution, and so on, must be done and redone for each object-language on a case-by-case basis. To make large, machine-checkable proofs feasible, one has to take a more sophisticated approach.
One such approach involves representing object-level variables by variables in a metalanguage based on typed -calculus. This shifts renaming and substitution to the meta-level where their properties are established once and for all. This is the ‘higher order abstract syntax’ (HOAS) approach [PfE88] — an idea going back to Church [Chu40] and Martin- [Mar84] that has found its way into many of the current logical frameworks and proof assistants. Its big drawback, in its original form at least, is that one looses the ability to define functions on syntax by structural recursion and to prove properties by structural induction — absolutely essential tools, especially for applications to operational semantics. There are recent proposals to overcome this shortcoming [McM97, DPS97]. They result in systems that are technically very interesting but force the designer of algorithms and proofs ‘modulo-α-conversion’ to use forms of expression that are rather far from familiar informal practice. Indeed, the whole HOAS approach by its very nature disallows a feature that we regard of key practical importance: the ability to manipulate names of bound variables explicitly in computation and proof. The same criticism applies to approaches to variable binding based upon de Bruijn’s nameless terms [dB72] or categorical combinators [Cur93]: these are good for machine implementations, but not, we would argue, for representations intended for machine-assisted human reasoning.
Instead of the HOAS approach of moving both α-conversion and substitution to the meta-level, we will just promote the former, leaving notions of substitution to be defined (by structural recursion) on a case-by-case basis by the user. This does not seem too bad a compromise, since we show that it permits both a nice calculus of bound names and notions of structural recursion and structural induction for variable-binding constructs. We present these in a theory with the expressive power of classical set theory (without the axiom of choice) and which remains close to informal practice in its forms of expression. This, and the focus on α-conversion rather than substitution as primitive, makes our work close in spirit to that of Gordon and Melham [GoM96], who axiomatise a type of untyped -terms modulo α-conversion within Church’s higher-order logic. However, we take a more foundational approach, in that the necessary properties of α-conversion become part of the underlying set theory itself. This results in notions of structural recursion and induction that seem rather simpler than those in [GoM96] (cf. Example 6.10 below).
1.2. Overview of the paper
The Fraenkel-Mostowski permutation model of set theory was devised in order to prove the independence of the Axiom of Choice (AC) from the other axioms of Zermelo-Fraenkel set theory with atoms (ZFA) (and some decades later Cohen proved the harder result of independence of AC from set theory without atoms (ZF), via his celebrated forcing method; see [Jec77, Section 6] for a brief survey of these matters). Our application of the permutation model of set theory to abstract syntax with variable binding is rather far from this original purpose! To motivate its use, in Section 2 we consider a paradigmatic example of syntax involving variable binding, the lambda calculus, and show that α-conversion of -terms can be expressed in terms of the primitive operation of permuting a term’s variables, be they free, bound or binding (Proposition 2.2). This motivates the use of sets equipped with permutation actions as a general setting for discussing syntax: the basic notions, including the key notion of ‘finite support’, are reviewed in Section 3; and the Fraenkel-Mostowski cumulative hierarchy of sets with finite support is recalled in Section 4. That section introduces FM-set theory, an axiomatisation of the Fraenkel-Mostowski permutation model whose special features, compared with the usual Zermelo-Fraenkel set theory, are expressed in terms of a set of atoms, a ‘freshness’ predicate (meaning ‘atom is not in the (finite) support of object ’) and a quantifier (meaning ‘for all but finitely many atoms , holds’). As far as we know, the -quantifier is novel; it has a dual ‘some/any’ character (see Lemma 4.10), which gives it very pleasant logical properties that we exploit throughout the rest of the paper. Our main contribution occurs in Section 5, where we define a new notion of ‘atom-abstraction’ within FM-set theory. Then in Section 6 we show that atom-abstraction can be used in combination with Cartesian product and disjoint union to form inductively defined sets in the Fraenkel-Mostowski permutation model that represent syntax modulo α-conversion (Theorem 6.2). The standard theory of algebraic data types extends to encompass signatures involving binding operators. In particular, there are notions of structural recursion (Corollary 6.7) and induction (Theorem 6.8) for these inductively defined FM-sets that respect indistinguishability of α-variants and yet are pleasingly close to informal practice when manipulating α-equivalence classes via representatives with explicitly named bound variables. Section 7 discusses related work; and in Section 8, we conclude by mentioning some ways in which the theory presented here is being developed and applied.
2. Permutative Renaming
As a motivating example, consider the terms of the untyped lambda calculus [Bar84]:
where ranges over some countably infinite set of names of variables.
The countably infinite set will be fixed throughout this paper. We call its elements atoms.
Given , consider the following three versions of the notion of variable-renaming for -terms :
the textual substitution of for all free occurrences of in ; the capture-avoiding substitution of for all free occurrences of in ; the transposition of all occurrences (be they free, bound, or binding) of and in . For example, when is , then
We assume the reader is familiar with the first two notions of renaming (if not, see [Bar84], for example). Although the third version is possibly less familiar, it is in fact more basic than the other two, because: firstly, one does not need to know whether any of the operations in the underlying signature for -terms are supposed to be variable-binders in order to define it; secondly, it can nevertheless be used to define α-conversion, as the following result shows (cf. [Gun92, p. 36], which uses in place of for the same purpose). Recall that α-conversion, , is usually defined as the least congruence on the set of -terms that identifies with .
The relation of α-conversion between -terms, , coincides with the binary relation inductively generated by the following axioms and rules.
Proof. It is not hard to see that preserves and hence that is closed under the axioms and rules defining . Therefore is contained in . The converse follows by proving that is a congruence relating and : this follows from the easily verified facts that preserves , and that if does not occur in , then .
This proposition shows that matters to do with variable binding can be phrased in terms of the elementary operation of variable-transposition, , rather than the more complicated operation of variable-substitution, be it textual or capture-avoiding. Both are more complicated than transposition because they depend on the auxiliary definition of what are the free variables of a term. Note that transposition is an instance of the more general operation of permuting the atoms in according to a bijection , the result of which we write as . This ‘permutation action’ permits one to formalise an important abstractness property of metatheoretic assertions involving the notion of ‘variable’, namely that the validity of assertions about syntactical objects should be sensitive only to distinctions between variable names, rather than to the particular names themselves. Put more formally, this is the equivariance property of an assertion about terms :
the validity of which of course depends upon the nature of the assertion (in particular one would expect to be the only free metavariable in for (2) to be valid; cf. Lemma 4.7). Such notions belong to the rich mathematical theory of sets equipped with a permutation action, which we recall next. It is worth noting that much of that theory would be inapplicable were one to try to base the development upon arbitrary (or even injective) renaming functions from atoms to atoms, rather than upon permutations.
3. Permutation Actions and Finite Support
Let denote the group of all permutations of . Thus the elements of are bijections from to itself. The group multiplication takes two such bijections and and composes them — we write the composition of followed by as . The group identity is the identity function on , denoted by . As one may gather from the discussion above, we will be particularly concerned with the elements of that are transpositions: given , we write for the permutation that interchanges and , leaving all other atoms fixed:
A -set consists of a set equipped with an action of the group : this is a function mapping pairs to elements of and satisfying
for all and .
We will usually refer to a -set via its underlying set when the associated action is clear from the context.
Of the many examples of sets equipped with an action of the group , we mention some that will be relevant here.
(i) The set itself has a -action given by applying the permutation, qua function, to atoms:
(ii) The set of -terms , defined as in equation (1), possesses a -action defined by induction on the structure of by:
(iii) Note that if two -terms are α-equivalent, , then for any permutation one also has . It follows that induces an action on the quotient set :
(where we write for the α-equivalence class of the -term ).
(iv) If is a -set, with action , then we can endow its powerset with a -action by defining:
(v) If and are -sets, then we can endow the disjoint union with a -action by defining:
(vi) The unique function is a -action on the emptyset .
(vii) We say that is a sub--set of if and restricts to a function , for any . In that case with the restricted action is itself a -set. If is a set of -sets that is linearly ordered by this relation, then the union has a -action given by the actions on each (which agree where they overlap):
In general, an action of on a set gives us an abstract way of regarding the elements of as somehow ‘involving atoms from in their construction’, in as much as the action tells us how permuting atoms changes — which turns out to be all we need for an abstract theory of variable renaming and binding. An important part of this theory is the notion of finite support. This generalises the property of an abstract syntax tree that it only involves finitely many atoms in its construction to the abstract level of an element of any set equipped with a -action.
Given a -set and an element , a set of atoms is said to support if all permutations that fix every element of also fix :
We say that is finitely supported (in ) if there is some finite subset supporting it. The -set has the finite support property if all its elements are finitely supported.
If an element of a -set is finitely supported, then there is a least finite subset of supporting . We write for this (necessarily unique) finite set of atoms and call it the support of (leaving implicit which -set is being referred to).
Proof. We give a proof that emphasises the role of transpositions (see equation (3)) and the predicate ‘ is not in the support of ’, which play crucial roles in the theory we develop in this paper. Indeed, one can give an explicit formula for in terms of the action of transpositions on :
Thus for any , holds if and only if holds for all but finitely many . (Cf. the definition of the -quantifier given below in Definition 4.4.) We show that this definition of has the following three properties:
(i) If is a finite set of atoms supporting , then .
(ii) If , then .
(iii) If is a finite set of atoms supporting , then so is , for any .
So if is finitely supported, (i) together with finitely many applications of (iii) allows us to deduce that is indeed a finite set supporting and is the least such. We need (ii) in order to prove (iii).
Property (i) follows almost immediately from the definition of in equation (5). For suppose is a finite set of atoms supporting . If , then , so since supports , we have . Therefore implies is contained in and hence is finite, so that . Thus implies , as required.
To prove property (ii), clearly it suffices to consider the case when . So suppose and are distinct atoms not belonging to . By definition of , the set of atoms is finite; so we can find an atom not in this set, i.e. such that and
Since are all distinct, the permutations and are equal. Therefore from equation (6) we have
as required.
Finally, to prove property (iii), suppose is a finite set of atoms supporting , that , and that satisfies . We have to prove that . We may assume , for otherwise fixes every element of and hence , because is supported by . But then we also have , since otherwise , being an element of , would be fixed by , so that , and hence , contrary to assumption. By property (i) and assumption on , we have and hence . Therefore by property (ii), . So
But the permutation clearly fixes ; and it fixes every element of because and do so. So fixes all of and therefore, since supports , we have
Combining equations (7) and (8) yields , as required.
Consider the -sets in Example 3.2.
(i) has the finite support property, with for each .
(ii) has the finite support property: the support of a -term turns out to be the finite set of atoms occurring in it, whether as free, bound, or binding occurrences.
(iii) The quotient set also has the finite support property, with the support of an α-equivalence class of -terms being the finite set of atoms occurring freely in any representative of the class (it does not matter which).
(iv) A powerset does not necessarily have the finite support property even if does. For example, the only elements of finite support in are the subsets that are either finite or cofinite (i.e. whose relative complement is finite). However, note that given any -set , if is supported by a finite set of atoms , then is supported by the finite set , for any . Therefore the -action on restricts to one on the subset
and has the finite support property (whether or not does).
(v) If and have the finite support property, then so does their disjoint union : each is either of the form and supported by the finite set of atoms supporting in , or is of the form and supported by the finite set of atoms supporting in .
(vi) The empty set has the finite support property, for rather trivial reasons.
(vii) If each element of a linearly ordered set of -sets has the finite support property, then so does its union: each is supported by the finite set of atoms that supports it in any containing .
4. FM-Set Theory
The -sets with the finite support property are the objects of a category whose morphisms are the so-called equivariant functions — those functions satisfying for all and . At this point we could develop our theory of name-abstraction in terms of constructions within this category: see [PiG00, Appendix]. Instead, here we take a set-theoretic approach and construct a single, ‘large’ -set with the finite support property, in which our theory can be expressed using familiar, set-theoretic language. One benefit is that if a particular construction can be expressed in this language, then the action of permutations is inherited from the ambient universe without having to define it explicitly and without having to prove the associated finite support property. (Compare this with the approach to denotational metalanguages initiated by Scott [Sco93] in which questions of domain-theoretic continuity are made implicit.)
Recall the usual von Neumann cumulative hierarchy of sets [Sho77]:
More generally, given a set we can define a cumulative hierarchy of ‘sets involving atoms from ’:
where denotes disjoint union of sets and the powerset operation (see (v) and (iv) in Example 3.2). We can build the notions of ‘permutation action’ and ‘finite support property’ into such a set-theoretic hierarchy by taking to be the -set of atoms and replacing by the operation from Example 3.5(iv):
Because of the properties noted in Example 3.5, each is a -set with the finite support property and is a sub--set of when — enabling us to use the union operation at limit ordinals as in Example 3.5(vii). More generally, when we consider the union of all the we get one large -set (i.e. a -class) in which every element has finite support.
The union of all (as ranges over the ordinals) is called the Fraenkel-Mostowski universe (over the set of atoms ) and is denoted . Using the suggestive names and for the functions and giving the two inclusions into a disjoint union, from definition (11) we have that every element of is either of the form with , or of the form where is a finitely supported set of FM-sets formed at an earlier ordinal stage than (cf. Example 3.5(iv)). We call elements of the form FM-sets and elements of the form atoms (a slight abuse of terminology). We will just write for the -action on the Fraenkel-Mostowski universe; it satisfies
Given an element of the Fraenkel-Mostowski universe , let denote the transitive closure of under the appropriate membership relation, namely . Note that contains a copy of the von Neumann universe , consisting of those FM-sets for which is disjoint from . We call such an a pure FM-set.
The usual set-theoretic constructions can be carried out within to build various sets. In particular we will make use of the set of natural numbers, and the usual constructions of ordered pairs, Cartesian products, disjoint unions, power- and function-sets. To be more precise and to develop the properties of the Fraenkel-Mostowski universe further, we introduce a suitable theory of atoms and FM-sets within classical first-order logic with equality. This theory is based upon ZFA — Zermelo-Fraenkel set theory with Atoms (see for example [Fou80], or [JoM95, §5]). This has a signature containing not only a binary relation symbol ‘’ for membership, but also a constant for the set of atoms, . The axioms of ZFA are as follows:
Axiom (Sets) expresses the fact that only non-atoms can have elements (‘atoms are empty’); the other axioms are like those of the usual Zermelo-Fraenkel set theory, except that certain quantifications (for ) have to be restricted to when must range just over sets rather than over sets and atoms. This difference is mathematically innocuous, but makes it very hard to re-use machine-checked versions of Zermelo-Fraenkel set theory to develop a theory of the Fraenkel-Mostowski universe within a proof assistant. The first author’s implementation of such a theory within the Isabelle generic theorem prover [Gab00, Chapter III] gets round this problem by working in a non-well-founded setting and replacing ‘empty atoms’ by so-called Quine atoms [Qui63, Section 4] — objects satisfying — at the expense of having to alter the axiom of (-Induction).
The above axioms capture the basic, set-theoretic properties of without saying anything very specific about properties of the set of atoms itself, or of the permutation action. The properties relevant to our intended application depend upon the fact that is (countably) infinite and that every element of is finitely supported in the sense of Definition 3.3. We can capture these two properties with the following axioms, which use notation introduced in Definition 4.4:
Here and elsewhere we will freely augment the rather sparse language of ZFA with extensions involving new function and relation symbols (written in this font) uniquely defined by formulas of ZFA. In particular we make the following definitions.
Finite subsets. Define to be a term denoting the set of finite subsets of . One practically useful way of formulating this is to define to be the least set of subsets of containing the empty set and closed under the operations of adding an element of , , for each .
Cofinite subsets. Define to be a term denoting the set of cofinite subsets of , i.e. those such that the relative complement is in .
Permutation action. Define to be a term denoting the set of permutations of . In view of (12), the action of such permutations can be defined by -recursion as follows:
In particular, define to be a term denoting the result of interchanging in .
-quantifier. For each formula of the language of ZFA, define (‘for all but finitely many atoms , ’) to be the formula expressing that is a cofinite set of atoms.
Freshness relation. Define the formula (‘atom is fresh with respect to ’) as follows:
That this is a reasonable definition of ‘freshness’ may not be immediately apparent; however, the following proposition shows (amongst other things) that holds if and only if is not in the support of , as defined in Proposition 3.4.
The axioms of FM-set theory are by definition the axioms of ZFA plus the two axioms (A-Not-Finite) and (Fresh). Modulo the other axioms, axiom (Fresh) is equivalent to asserting that every has the finite support property of Definition 3.3, suitably formulated in the language of ZFA:
In particular the Fraenkel-Mostowski universe over an infinite set (Definition 4.1) satisfies these axioms if we interpret the membership relation ‘’ by the binary relation and the constant by the element .
Proof. To prove (14), first note that for any , if are distinct atoms satisfying , then (see the proof of property (ii) in the proof of Proposition 3.4). From this we can deduce the following two useful facts:
Note also that if we define as in equation (5), then by definition of we have
So if the right-hand side of (14) holds, then for each , the proof of Proposition 3.4 yields that ; and hence from (A-Not-Finite) , so that by (16) again, .
Conversely, if , then for each , by (16) and (17); and by (15) and (17), for any . So any permutation that is finite (i.e. with ) and that fixes each element of satisfies , because such a permutation is expressible as the composition of finitely many transpositions with . But axiom (Fresh) implies that any is finite: for if , it is not hard to see that ; so from (16) we have for cofinitely many atoms , so that is finite. Thus if (Fresh) holds then for each , defined as in (5) is a finite set of atoms supporting . Thus we do indeed have the left-to-right implication in (14).
In the literature, careful presentations of the definition of capture-avoiding substitution quite often make use of a choice function for picking out fresh variables: see [Sto88, Section 2], for example. The vague feeling that such concrete choices should be irrelevant crystallises here into the fact that such choice functions are inconsistent with FM-set theory, because its axioms contradict the Axiom of Choice (AC). For example, the axiom (A-Not-Finite) implies that the set of cofinite subsets of is a set of non-empty sets; but there can be no choice function for it — a diagonalisation argument (using the fact that the graph of any function from to must be finitely supported) shows this. (Indeed it can be shown that the axiom of countable choice is inconsistent with FM-set theory.)
Mechanised proof assistants based on set theory, or on higher-order logic, often include Hilbert’s choice operator, , to provide anonymous notations for terms defined by formulas (see [LaP99, Section 2.1]). Since the -operator can be used to prove AC, we cannot add it to FM-set theory without inconsistency. However, in a fully formal presentation of FM-set theory it would be both consistent and useful to augment the language of FM-set theory with a notation and axioms for forming terms uniquely defined by a formula. As mentioned in Definition 4.4, here we proceed in a semi-formal fashion and just introduce new notation on the fly, uniquely defined by formulas. Corollary 4.8 allows us to bound the support of terms involving such new notation by the support of the notation’s parameters. It is a consequence of the following equivariance property (cf. equation (2)), which is important in its own right.
Suppose is a formula of FM-set theory, with free variables contained in the list of distinct variables . Then
is provable in FM-set theory (where denotes the simultaneous (capture-avoiding) substitution of for all free occurrences of in , as ranges over ).
Proof. By induction on the structure of , using the following properties of the constant and relation symbols of the language:
Property (18) is a trivial consequence of the usual properties of equality; and properties (19) and (20) follow from the definition of the permutation action in Definition 4.4.
Suppose and are formulas of FM-set theory, with free variables contained in the indicated lists of variables, and that
holds. If we define the term to be the unique such that , so that , then
(where stands for a conjunction of freshness formulas, one for each variable in the list ). Hence , if .
Proof. Suppose and hold. We have to prove for the unique such that . By axiom (Fresh) we can find with . Since , by Lemma 4.7 we have . But by the uniqueness part of property (21): for not only does hold (by definition of ), but so also does (since Lemma 4.7 applied to gives and by property (15), because ). So we do indeed have .
As usual, an FM-set is a (partial) function if it only contains ordered pairs and is single-valued, i.e. if holds, where
Using (Collection) and (Separation), if holds then the domain of definition of is the uniquely defined FM-set of first components of elements of , i.e. . Similarly the image of is . If and , then there is a unique such that and in this case, as usual, we define the application notation to stand for this . From Corollary 4.8 we have
While we are about it, let us mention another piece of notation associated with functions. If and are FM-sets, then the function set is the FM-set defined by: .
In Definition 4.4 we introduced the notation to stand for a quantification over all but finitely many atoms. However, the nature of the set of atoms in FM-set theory endows this quantifier with very special properties, as Proposition 4.10 and Corollary 4.11 show.
For any formula and list of distinct variables in the language of FM-set theory, consider the following formulas:
Then in FM-set theory, . If the free variables of are contained in the list , then also
and hence in this case the three formulas are provably equivalent.
Proof. Note that by axiom (Fresh) and (16) (and the fact that cofinite sets are closed under finite intersection), we have . So if (25) holds, contains and hence is cofinite, i.e. (26) holds. Similarly, if (26) holds then is the intersection of two cofinite sets, hence is cofinite and hence by (A-Not-Finite) is non-empty: so (27) holds.
Now suppose the free variables of are contained in and that (27) holds. We use the equivariance property of formulas of FM-set theory given in Lemma 4.7 to deduce from that for any
where denotes the result of substituting for all free occurrences of and for all free occurrences of in , as ranges over . So if , since we also have , from (15) we get and hence (28) implies . So (27) does indeed imply (25).
The quantifier commutes with the propositional connectives: for all formulas and
are all provable in FM-set theory. Moreover, if all the elements of an FM-set have empty support (for example, if is pure in the sense of Remark 4.2), then commutes with existential and universal quantification over elements of :
Proof. These properties of the -quantifier follow easily from its dual nature established in Proposition 4.10. (For property (32), we also need to note that if holds, then so does .)
In view of Proposition 4.10, we are justified in reading as ‘for some/any fresh atom , it is the case that ’. This dual flavour of the -quantifier seems to exactly fit many situations where a statement about freshness of variables is required: we choose some fresh variable with a particular property, but later on may need the fact that any such variable will do. For example, when reasoning about α-conversion of -terms using the rules in Proposition 2.2 in a ‘top-down’ fashion, we satisfy the side-condition in the third rule by picking some fresh ; and when using them in a ‘bottom-up’ fashion, it is useful to know that any fresh will do. We will see further examples of this phenomenon in subsequent sections, where we put the -quantifier to work.
5. Abstraction Sets
In Proposition 2.2 we saw that α-conversion of -terms can be formulated in terms of the operation of transposing two variables in a term, together with the relation that a variable does not occur in a term. In view of Example 3.5(ii), equation (17) and Proposition 4.10, we can re-express the rule for α-conversion of -abstractions in Proposition 2.2 as
This suggests how to generalise the notion of α-conversion from the syntax trees of -terms to arbitrary objects in the Fraenkel-Mostowski universe introduced by Definition 4.1. Let be the binary relation on defined by
It is not hard to see that is an equivalence relation. The following lemma shows that its equivalence classes are FM-sets.
FM-set theory satisfies
Hence by the axiom (Collection), for each and there is an FM-set
which is the -equivalence class of the pair . We call the atom-abstraction determined by and .
Proof. We split the proof of (34) into two cases, according to whether or not. In the first case, the result follows from the easily verified implication
So suppose . If , then there is some with and
Since , by the equivariance property (Lemma 4.7) we also have and hence by (37), . From this we get , i.e. (since leaves fixed). So for the left-to-right implication in (34), it just remains to show that . But
Conversely, if and , then by axiom (Fresh) there is some with and
Therefore , i.e. , as required.
FM-set theory satisfies
Hence and therefore . Proof. First note that as a consequence of the equivariance property of Lemma 4.7 one has
So if , then by (34); thus holds, which is (38). Property (39) follows from property (22) and the easily verified fact that . Finally for (40), if and , i.e. , then by (41) we have ; hence by (36), , as required.
The definition of atom-abstraction embodies a form of ‘abstraction as information hiding’, since acts like a pair in which the name in the first component has been hidden, or made anonymous. However, atom-abstractions also embody a notion of ‘abstraction as function’, since (36) shows that each atom-abstraction is a partial function; and by construction, the domain of definition of this partial function is a set of atoms. In other words, using the notation of Example 4.9, holds. Indeed, by (35) and Corollary 5.2
We will use the following special notation for the result of applying such a partial function to an atom in its domain of definition.
For each FM-set , we can use the (Collection) axiom to deduce the existence of an FM-set of atom-abstractions of elements of , defined by:
One might wonder why the condition ‘ ’ is included in the above definition. It is needed to ensure that the concretion of an element of at a fresh atom lands us back in :
For note that because of the condition in (44), plus the fact that holds when (by Corollary 5.2), from Proposition 4.10 we have
Hence given and , then for some and with . By (43), ; and since , we have . But , since and ; and hence , as required for (45).
A form of -conversion holds for atom-abstraction/concretion, namely:
and hence the following extensionality principle holds:
Proof. Given and , by (44) we can find and with (and ). Then
Thus (47) holds by Proposition 4.10.
6. Inductively Defined FM-Sets
We can use the construct in combination with Cartesian product and disjoint union to form inductively defined FM-sets that allow us to view sets of syntax involving binders modulo α-conversion as algebraic data types in , generalising the ‘classical’ theory for syntax without binders. To see this, we first need to recall a little of the theory of inductively defined sets, within the context of FM-set theory.
Suppose is a definable function from FM-sets to FM-sets. In other words, suppose that there is a formula of FM-set theory with the indicated free variables and satisfying ; and suppose that for each , is the unique such that . Suppose further that the function is monotone for inclusions
and preserves unions of countable ascending chains
(Just as we require to be definable in FM-set theory, so we only consider countable chains of FM-sets that are definable in FM-set theory; so in particular there is one finite set of atoms supporting every , rather than one such set for each .) Then possesses a least (pre)fixed point, :
We call the inductively defined FM-set determined by . It can be constructed via the familiar Tarski formula:
The inductively defined FM-sets in which we are interested are all determined by functions that are also the object part of functors preserving inclusions. In other words, not only is a definable monotone function on FM-sets preserving definable countable chains, but also there is another definable function (traditionally also denoted by ) acting on functions between FM-sets:
that preserves composition:
and inclusion functions:
where is . In this case is the initial algebra for the functor : for every FM-set and function , there is a unique such that
commutes (i.e. ). Indeed, paralleling the construction of in (53), we have
Proof. The fact that preserves inclusions and unions of definable countable chains follows immediately from the characterisation of in (46) together with the fact (Corollary 4.11) that preserves implications and commutes with (because is pure). We extend it to a functor on FM-sets as follows. Given , define
That this does give an element of and that preserves composition and inclusion functions all follow from the properties of atom-abstractions established in Section 5 (see [Gab00, Section 10] for more details).
It is well known that set-functions built up from constants and projections using the operations of Cartesian product, , and disjoint union, , enjoy the above properties of monotonicity, preservation of unions of chains and functoriality; and hence such set-functions can be used to form inductively defined sets with the above initial algebra property. This is the starting point for the initial algebra semantics of algebraic signatures [GTWW77] within the usual ZF set theory and its model, the von Neumann hierarchy defined by equation (9). All this remains unchanged if we move from to the larger (cf. Remark 4.2) Fraenkel-Mostowski cumulative hierarchy and replace ZF by FM-set theory. But now the above lemma shows that within this larger setting of FM-sets we can also use the abstraction-set operation in the construction of and still be able to form the inductive FM-set as in (53), with its initial algebra property (54). In this way we are able to extend initial algebra semantics to deal with signatures with binding and in particular to get a purely inductive representation of the quotient modulo α-equivalence of the set of abstract syntax trees over such a signature. Rather than treat the case of arbitrary ‘binding signatures’ (for which see [Gab00, Section 10.2]), we will illustrate these ideas with respect to the paradigmatic example, the signature for the untyped -calculus.
Consider the FM-set of untyped -terms, given as the inductively defined FM-set where
Then the FM-set of equivalence classes of -terms modulo the equivalence relation of α-conversion, , is in bijection with the inductively defined FM-set , where
Proof. This follows by combining the characterisation of given by Proposition 2.2 with the definition of atom-abstraction in Section 5 in terms of the equivalence relation given by equation (33).
In passing from to the bijectively equivalent set , we replace the global use of quotienting by with local, inductive use of quotienting by . This is a simplifying step because the quotient sets (they are the quotient of by ) have some very pleasant properties. In particular, the following lemma gives a simple characterisation of functions of atom-abstractions in terms of functions of pairs .
For all functions in , there is a unique function satisfying
if and only if satisfies
Proof. First note that if such an exists, then applying Proposition 4.10 to (58), there is some with
But for any we always have (Corollary 5.2); and holds by assumption on ; hence by property (24), , i.e. . Thus satisfies
which by Proposition 4.10 again, is condition (59). There can be at most one function satisfying property (58), because by (44) we have that is a surjection from onto
. Conversely, suppose condition (59) does hold. Thus by Proposition 4.10 we have
Define an FM-set by
This is a single-valued relation, because if and , then by definition of , and using axiom (Fresh), we can find some and with , , and ; then by property (36) and hence . Moreover, for each there is some satisfying : for, picking and taking to be the concretion (Definition 5.3), we have by property (45) and hence by property (60), satisfies . Thus we have
so that (by Proposition 4.10). So is indeed an element of . Furthermore, property (58) holds of it: for if , then for any property (61) holds with and (since in that case by (38) and by (59)), so that , i.e. , as required.
Given satisfying property (59) and given , we use the notation
(where the variables and are bound in this expression) for the element specified by the above lemma. From property (58) we have that this ‘eliminator’ for the abstraction-set construct satisfies the conversion law
As a special case of this construct, given by taking in Lemma 6.3, we have that for each satisfying , there is a unique element of , that we denote by
(once again, is a bound variable in this expression), satisfying
In effect, the expression denotes the use of a ‘locally fresh’ atom in the expression ; and this is meaningful if the value of is independent of the choice of , in the sense that holds for some/any fresh atom .
For example, taking to be , by property (38) we have and hence there is an element . In fact there is a bijection given in one direction by
and in the other by
Expression-formers such as and are part of a term-calculus for atom-abstractions that forms part of the functional programming language proposed by the authors in [PiG00].
Returning to the inductively defined FM-set introduced in Theorem 6.2, from property (51) we have that is a disjoint union of three components
Let
denote the inclusion functions of the components into the disjoint union. Combining the least fixed point and initial algebra properties of with Lemma 6.3, we obtain the following principles of structural iteration, recursion and induction for our inductive FM-set representing -terms modulo α-conversion. (Compare them with the Recursion Scheme of [GoM96, Section 3.1].)
Given functions , , and in with satisfying
there is a unique such that
Proof. By Lemma 6.3, the condition (66) means that it induces a function . Then , and fit together to give a function from the coproduct to , i.e. a function . Then is the unique function given by the initial algebra property (54).
Note that this structural iteration principle for proves the existence of total functions out of even though in property (67), as far as -abstractions are concerned, we only have to specify what the function does for fresh bound variables. Indeed, we can slightly strengthen Theorem 6.5 by only requiring to be a partial function with , for which condition (66) still makes sense. However, if , as is the case in the examples below, then is in fact the whole of .
Given functions , , and in with satisfying
there is a unique such that
Proof. The passage from iteration to (primitive) recursion for initial algebras uses a standard trick relying upon the uniqueness part of the initial algebra property: define to be and consider , , and given by
Note that satisfies condition (66) because of property (38) and because satisfies (68). So let be the function uniquely defined by iteration from as in Theorem 6.5. Writing and for the projection functions and , one verifies that and the identity function both satisfy the conditions required of the function iteratively defined by , where is . (Note that this triple of functions is suitable for a structurally iterative definition because satisfies the necessary condition (66), thanks to property (38).) Hence . Using this one easily verifies that is the uniquely defined function with the required property (69).
Given a subset in , to prove that is the whole of it suffices to show
Proof. Condition (70) tells us that the inclusion
factors through (we use property (46) to see this for the third component of the disjoint union). Hence and therefore by property (52) we have . Thus .
This structural induction principle for seems to correspond well to informal inductive arguments about α-equivalence classes of -terms that proceed by picking representative names of bound variables and applying structural induction at the level of abstract syntax trees (i.e. structural induction for , as defined in Theorem 6.2), leaving mute the tedious proofs that such choices do not affect the argument. In effect, by restricting to objects with finite support (Definition 3.3) and equivariant properties (Lemma 4.7), FM-set theory ensures that such choices are guaranteed not to affect meaning, provided freshness conditions like property (66) in Theorem 6.5 are satisfied.
In the rest of this section we give some simple examples of the use of Theorems 6.5 and 6.8.
From the above properties it follows that under the bijection of Theorem 6.2 between elements of and α-equivalence classes of -terms , the function corresponds to the capture-avoiding substitution function . Note that in the clause for -abstractions , we only have to specify the result of substitution for the simple case that is fresh in order for to be defined on the whole of .
One property of capture-free substitution is that the only free occurrences of in are due to free occurrences of in . The analogue for of this property is
This can be proved by structural induction on by taking in Theorem 6.8 and making use of the easily verified fact that
Applying Proposition 4.10 to (71), we have for each that
Thus by Lemma 6.3, for each the element of given by induces a function . In this way we get a substitution function satisfying for all that . (Compare with the substitution function in [FPT99, Section 3].)
Condition (66) is satisfied in this case because is a pure FM-set (see Remark 4.2) and hence .
By Proposition 4.10, the last property of in the above conjunction is equivalent to
But Corollary 4.8 implies that holds for any . Therefore we can strengthen this last defining clause for to
Thus the formalism we have developed allows us to express very easily the properties we expect a size function to have on α-equivalence classes of -terms. Compare this example with the complications encountered by Gordon and Melham when defining a similar function by recursion using their axiomatisation of α-conversion [GoM96, Section 3.3].
In Theorem 6.5, take to be the set of finite sets of atoms, to be the singleton function , to be union and to be the subtraction function . Note that satisfies condition (66), because the support of a finite set of atoms is just itself and hence , for any . So there is a unique function satisfying
where in the last conjunct we have strengthened to using the same argument as in the previous example. This function gives a structurally iterative definition of the ‘finite set of free atoms’ for elements of . Using the structural induction principle of Theorem 6.8, one can show for all that in fact . Thus under the bijection of Theorem 6.2, the set of (names of) free variables of an α-equivalence class of -terms is identified with the support of the corresponding element of (cf. Example 3.5(iii)). In particular, corresponds to the subset of closed -terms modulo .
It is simple enough to define a function sending each -term to the finite set of atoms that occur in in binding position. Clearly this set is not invariant under α-conversion and so does not induce a function on . Correspondingly, there is no function in picking out the finite set of ‘binding atoms’ of elements of , in the sense that it satisfies
(Note that we cannot use Theorem 6.5 to define such a function because in this case condition (66) would require (any ), which is certainly false.) Indeed, we can argue by contradiction to see that no such function exists in : if it did, picking any atoms not in its support, we would have (by property (15)); then satisfies and so
i.e. , contradicting the choice of and .
The theory we have presented seems rather well adapted to expressing the ‘usual’ forms of recursion/induction for abstract syntax, while at the same time dealing with freshness of variables and variable renaming systematically, at the meta-level. Of course much more needs to be done to establish the utility of these structural recursion and induction principles (see Section 8). However, we regard the sheer simplicity of the above examples (compared with analogous examples in other formalisms) as a good sign! We finish this section by mentioning some extensions of the theory.
The terms of the lambda calculus are the terms over a signature with one binary operation (application) and one unary binder -abstraction). The results of this section can be extended to deal with more general signatures, consisting of operators (for some ) each of which takes arguments (for some ) with each argument an -ary abstraction (for some ) — these are the binding signatures considered in [FPT99, Section 2]. The function on FM-sets corresponding to such a signature takes the form
where
Generalising Theorem 6.2, one can show that the inductively defined FM-set determined by is in bijection with the set of terms modulo α-conversion over the binding signature. This FM-set is an initial algebra for the functor associated with ; and from the shape of the signature can be read off principles of structural recursion and induction like those above. Many-sorted signatures can be dealt with using FM-sets mutually inductively defined by several such functions. See [Gab00, Section 10] for more details.
To support syntax involving finitely many different sorts of variables one can use the following mild generalisation of the Fraenkel-Mostowski universe of Definition 4.1. Partition the set of atoms into a countably infinite set of infinite subsets:
Working with sets equipped with an action of the subgroup of consisting of permutations that respect the partition (so that is isomorphic to the product group ), we can repeat the development of Sections 3 and 4, forming a universe of sets with hereditarily finite support with respect to the action of . There is a corresponding generalisation of FM-set theory to Fraenkel-Mostowski set theory with many Sorts of atoms (FMS-set theory), whose axioms we will not give here. Within that theory one can develop the theory of transpositions , a freshness predicate , a quantifier and abstraction sets , where . The latter can be used in combination with Cartesian products and disjoint unions to form inductively defined sets in the universe just as in Section 6. For example, taking two distinct sorts of atoms, and naming type variables and term variables respectively, the mutually inductively defined FMS-sets
represent, respectively, the types and terms of the Girard-Reynolds polymorphic lambda calculus [Gir72, Rey83] modulo renaming of bound type variables and bound term variables. (The disjoint union inclusion functions have been named explicitly in (72) to indicate the intended meaning.)
7. Related Work
One origin of the work presented here lies in the ‘-calculus’, a fragment of ML [MTHM97] introduced by the second author and Stark [PiS93a, Sta95] to explore the properties, with respect to semantic equivalence of programs, of call-by-value higher order functions and dynamically created names (see also [JeR99]). In [Sta96a], Stark studies a model of the -calculus based on one of Moggi’s ‘dynamic allocation’ monads [Mog89] in the presheaf category , where is the category of finite ordinals and injective functions between them. Crucial ingredients of the dynamic allocation monad used there are the ‘object of names’, given by the inclusion functor , and the shift functor , given by . These ingredients also occur in subsequent work on modelling -calculus names in [FMS96, Sta96b] and, most relevantly, recent work on modelling variable-binding abstract syntax [FPT99, Hof99], where other presheaf categories besides are considered.
Now, a somewhat overlooked model of the -calculus, mentioned in [PiS93b, Examples 4.3], is the full subcategory of whose objects are the pullback preserving functors. This is equivalent to a well-known topos, sometimes called the Schanuel topos — the category of continuous -sets for the topological group of permutations of a countably infinite set topologised as a subspace of Baire space: see [Joh83, Lemma 1.8] and [MaM92, Section III.9]. Put more concretely, and this is the point, the objects of the Schanuel topos are -sets (Definition 3.1) in which every element has finite support (Definition 3.3), and its morphisms are the equivariant functions defined at the beginning of Section 4. Thus on the one hand, the Schanuel topos relates to the cumulative hierarchy of FM-sets defined by equation (11) much as the usual von Neumann cumulative hierarchy, defined by equation (9), relates to the topos of sets (see [JoM95] for more on the category theory of universes of sets); on the other hand, the Schanuel topos is a sheaf subtopos of the presheaf category , with the inclusion sending the FM-set of atoms to the object of names and the abstraction operator to the shift functor mentioned above.
Both the presheaf toposes used in [FPT99, Hof99] and the Schanuel topos (and indeed many other categories equipped with a faithful functor to ) support an initial algebra semantics for signatures with binding. So does the Schanuel topos, and its associated FM-set theory, have any advantage over these other, related categories? It is well known that toposes correspond to theories in extensional, higher-order, intuitionistic logic [LaS86]. Unlike presheaf toposes in general, the Schanuel topos models classical rather than intuitionistic higher-order logic; furthermore, its higher-order structure (function and power objects) is rather amenable to making calculations, compared with the higher-order structure of presheaf categories. Thus if one is looking for a single, general-purpose setting for modelling variable-binding syntax, the logic of the Schanuel topos is both a bit more powerful and familiar. One can view [FPT99] as establishing, amongst other things, a very nice categorical algebra for the de Buijn, ‘nameless’ style of treating variable-binding and substitution. By contrast, here we have presented a useful logic for variable-binding in which names occur explicitly. The motivation for such a ‘nameful’ rather than nameless style is partly to formalise existing common practice; but the logic can also serve as a basis for proving that de Bruijn-like formulations are correct with respect to more concrete representations. Crucial to all this is the notion of ‘finite support’ (leading to the -quantifier and our FM-set-theoretic notion of atom-abstraction), which is present in the Schanuel toposes, but not, apparently, in the presheaf toposes used in [FPT99] — or at least not with such pleasant properties.
Finally, it is worth emphasising that although we have chosen to use a set-theoretic rather than a topos-theoretic presentation here — because we think it is more accessible — the same fundamental ideas to do with names and name-abstraction underlie both FM-set theory and the Schanuel topos.
8. Conclusion and Further Developments
The Fraenkel-Mostowski permutation model of ZFA is well over sixty years old. Yet the use to which we have put it here seems new. The idea that one might want to treat syntax up to permutative renamings of variables is hardly original, but we hope we have demonstrated convincingly that the theory really takes off when one combines that idea with the subtle notion of ‘finite support’ inherent in the Fraenkel-Mostowski model. Using it, we introduced a useful quantifier for fresh names and a new set-forming operation for name-abstraction,
, whose properties seem better suited to modelling variable-binding than the function space that is often used for that purpose. Among other things, we saw that the theory of inductively defined FM-sets using this notion of abstraction can correctly model α-equivalence classes of variable-binding syntax. At the same time we remain pleasantly close to the familiar theory of first-order algebraic data types — witness Theorems 6.5 and 6.8, and Examples 6.9–6.12. We believe that the theory of inductively defined FM-sets will be a useful setting for developing programming language semantics based on structural operational semantics [Plo81]. Syntax-directed, rule-based inductive definitions of relations quite often contain side-conditions to do with freshness of variables, and the hope is that these can be assimilated and manipulated conveniently via the freshness predicate and the -quantifier we have introduced here. This approach seems particularly relevant for the labelled transition semantics of process calculi such as the -calculus and its relations [MPW92, AbG99, CaG00b]; both because complicated forms of binding to do with names and names restriction play a key role there and because analyses based on ‘name-abstraction as functions’ [HMS98, Des00] are not entirely satisfactory. The formalism of permutation actions and finite support has been rediscovered independently by Honda in his work on a general framework for processes [Hon00]. It also features in work on finite state transition systems for checking bisimilarity of -calculus processes in [MoP00]. Cardelli and Gordon have taken up some of the ideas presented here and used permutative renaming and the -quantifier as part of a modal logic for their ambient calculus [CaG00a].
This paper is a revised and expanded version of [GaP99]. Since that paper appeared, the theory we have described here has been developed and applied in two somewhat different directions. The first author has developed an implementation of FM-set theory within the Isabelle generic theorem prover [Pau94]. This required a good deal of ‘proof engineering’ to reuse the existing Isabelle ZF theory; an account may be found in Chapter III of the first author’s thesis [Gab00] (Chapter II of which contains a development of FM-set theory more detailed than the one given here). Secondly, we have begun to design an ML-style metalanguage, FreshML, for programming with recursively defined functions on inductively defined FM-sets. The ingredients of FreshML are described in [PiG00]. It has a type of atoms, a type constructor for atom-abstractions, and facilities for defining recursive functions involving locally fresh names and pattern-matching on atom-abstractions (cf. Remark 6.4). The FreshML type system infers not only conventional typing information, but also information about freshness assertions ; the crucial point is that the type system ensures that the language’s facilities for manipulating bound names can only be used in well-typed programs in ways that are insensitive to renaming those bound names.
References
[AbG99]Abadi, M. and Gordon, A. D.: A calculus for cryptographic protocols: the spi calculus. Information and Computation, 148:1–70, 1999.
[Bar84]Barendregt, H. P.: The Lambda Calculus: Its Syntax and Semantics (rev. edn). North-Holland, Amsterdam, 1984.
[Bur69]Burstall R. M.: Proving properties of programs by structural induction. Computer Journal, 12:41–48, 1969.
[Bur77]Burstall, R. M.: Design considerations for a functional programming language. In Proc. of the Infotech State of the Art Conference, Copenhagen, 1977.
[CaG00a]Cardelli, L. and Gordon A. D.: Logical properties of name restriction. In Typed Lambda Calculus and Applications, 5th International Conference, Vol. 2044 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2001.
[CaG00b]Cardelli, L. and Gordon, A. D.: Mobile ambients. Theoretical Computer Science, 240:177–213, 2000.
[Chu40]A. Church. A formulation of the simple theory of types. Journal of Symbolic Logic, 5:56–68, 1940.
[Cur93]P.-L. Curien. Categorical Combinators, Sequential Algorithms, and Functional Programming. , Basel, 1993.
[dB72]de Bruijn, N. G.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indag. Math., 34:381–392, 1972.
[Des00]Despeyroux, J.: A higher-order specification of the pi-calculus. In IFIP International Conference on Theoretical Computer Science, IFIP TCS’2000, Sendai, Japan, 2000.
[DPS97]J. Despeyroux, F. Pfenning, and C.. Primitive recursion for higher-order abstract syntax. In Typed Lambda Calculus and Applications, 3rd International Conference, Vol.1210 of Lecture Notes in Computer Science. Springer, Berlin, 1997, pp. 147–163.
[FMS96]Fiore, M. P., Moggi, E. and Sangiorgi, D.: A fully abstract model for the -calculus (extended abstract). In Eleventh Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, Washington, DC, 1996, pp. 43–54.
[Fou80]Fourman, M. P.:. Sheaf models for set theory. Journal of Pure and Applied Algebra, 19:91–101, 1980.
[FPT99]Fiore, M. P., Plotkin, G. D. and Turi, D.: Abstract syntax and variable binding. In 14th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, Washington, DC, 1999, pp. 193–202
[Gab00]Gabbay, M. J.: A Theory of Inductive Definitions with α-Equivalence: Semantics, Implementation, Programming Language. PhD thesis, Cambridge University, 2000.
[Gir72]Girard, J.-Y.: fonctionelle et des coupures dans l’arithmetique d’ordre . PhD thesis, VII, 1972.
[GoM93]Gordon M. J. C. and Melham T. F.: Introduction to HOL. A theorem proving environment for higher order logic. Cambridge University Press, Cambridge UK, 1993.
[GoM96]Gordon A. D. and Melham, T.: Five axioms of alpha-conversion. In Theorem Proving in Higher Order Logics: 9th Interational Conference, TPHOLs’96, Vol. 1125 of Lecture Notes in Computer Science. Springer, Berlin, 1996, pp. 173–191
[GaP99]Gabbay, M. J. and Pitts, A. M.: A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, Washington, DC, 1999, pp. 214–224.
[GTWW77] Goguen, J. A. , Thatcher, J. W., Wagner, E. G. and Wright, J. B.: Initial algebra semantics and continuous algebras. Journal of the Association for Computing Machinery, 24:68–95, 1977.
[Gun92]Gunter, C. A.: Semantics of Programming Languages: Structures and Techniques. Foundations of Computing. MIT Press, Cambridge, MA, 1992.
[HMS98]Honsell, F., Miculan, M. and Scagnetto, I.:-Calculus in (co)inductive type theory. Technical report, Dipartimento di Matematica e Informatica, degli Studi di Udine, 1998.
[Hof99]Hofmann, M.: Semantical analysis of higher-order abstract syntax. In 14th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, Washington, DC, 1999, pp. 204–213.
[Hon00]Honda, K.: Elementary structures in process theory (1): Sets with renaming. Mathematical Structures in Computer Science, 10:617–663, 2000.
[Jec77]Jech, T. J.: About the axiom of choice. In J. Barwise, editor, Handbook of Mathematical Logic. North-Holland, Amsterdam, 1977, pp. 345–370.
[JoM95]Joyal, A. and Moerdijk, I.: Algebraic Set Theory. Number 220 in London Mathematical Society Lecture Notes in Mathematics. Cambridge University Press, Cambridge, UK, 1995.
[Joh83]Johnstone, P. T.: Quotients of decidable objects in a topos. Math. Proc. Cambridge Philosophical Society, 93:409– 419, 1983.
[JeR99]Jeffrey, A. and Rathke, J.: Towards a theory of bisimulation for local names. In 14th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, Washington, DC, 1999, , pp. 56–66.
[LaP99]Lamport, L. and Paulson, L. C.: Should your specification language be typed? ACM Transactions on Programming Languages and Systems, 21(3):502–526, 1999.
[LaS86]Lambek, J. and Scott, P. J.: Introduction to Higher Order Categorical Logic. Cambridge University Press, Cambridge, UK, 1986.
[Mar84]Martin-, P.: Intuitionistic Type Theory. Bibliopolis, Naples, 1984.
[MaM92]MacLane, S. and Moerdijk, I.: Sheaves in Geometry and Logic. A First Introduction to Topos Theory. Springer, New York, 1992.
[McM97]McDowell, R. and Miller, D: A logic for reasoning with higher-order abstract syntax. In 12th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, Washington, DC, 1997, , pp. 434–445.
[Mog89]Moggi, E.: An abstract view of programming languages. Technical Report ECS-LFCS-90-113, Department of Computer Science, University of Edinburgh, 1989.
[MoP00]Montanari, U. and Pistore, M.:-Calculus, structured coalgebras and minimal HD-automata. In 25th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovak Republic, Vol. 1893 of Lecture Notes in Computer Science. Springer, Berlin, 2000.
[MPW92]Milner, M., Parrow, J. and Walker, D.: A calculus of mobile processes (parts I and II). Information and Computation, 100:1–77, 1992.
[MTHM97] Milner, R., Tofte, M., Harper, R. and MacQueen, D.: The Definition of Standard ML (Revised). MIT Press, Cambridge, MA, 1997.
[Pau94]Paulson, L. C.: Isabelle: A Generic Theorem Prover. Vol. 828 of Lecture Notes in Computer Science. Springer, Berlin, 1994.
[PfE88]Pfenning, F. and Elliott, C.: Higher-order abstract syntax. In Proc. ACM-SIGPLAN Conference on Programming Language Design and Implementation. ACM Press, New York, 1988, pp. 199–208.
[PiG00]Pitts, A.M.and Gabbay, M.J.: A metalanguage for programming with bound names modulo renaming. In R.Backhouse and J. N. Oliveira, editors, Mathematics of Program Construction. 5th International Conference, MPC2000,
Ponte de Lima, Portugal, July 2000. Vol. 1837 of Lecture Notes in Computer Science. Springer, Heidelberg, 2000, pp. 230–255.
[Plo81]Plotkin, G.D.: A structural approach to operational semantics. Technical Report DAIMI FN-19, Aarhus University, 1981.
[PaM93]Paulin-Mohring, C.: Inductive definitions in the system Coq; rules and properties. In M. Bezem and J. F. Groote, editors, Typed Lambda Calculus and Applications. Vol. 664 of Lecture Notes in Computer Science. Springer, Berlin, 1993, pp. 328–345.
[PiS93a]Pitts, A. M. and Stark, I. D. B. : Observable properties of higher order functions that dynamically create local names, or: What’s new? In Mathematical Foundations of Computer Science, Proceedings of the 18th International Symposium, . Vol. 711 of Lecture Notes in Computer Science. Springer, Berlin, 1993, pp. 122–141.
[PiS93b]Pitts, A.M.and Stark, I.D.B.: On the observable properties of higher order functions that dynamically create local names (preliminary report). In Workshop on State in Programming Languages, Copenhagen. ACM SIGPLAN. Technical Report YALEU/DCS/RR-968, Yale University Department of Computer Science, 1993, pp. 31–45.
[Qui63]Quine, W. V. O.: Set Theory and its Logic (rev. edn). Harvard University Press, Cambridsge, MA, 1963.
[Rey83]Reynolds, J. C.: Types, abstraction and parametric polymorphism. In R. E. A. Mason, editor, Information Processing 83. North-Holland, Amsterdam, 1983, pp. 513–523.
[Sco93]Scott, D. S.: A type-theoretical alternative to ISWIM, CUCH, OWHY. Theoretical Computer Science, 121:411–440, 1993.
[Sho77]Shoenfield, J. R.: Axioms of set theory. In J. Barwise, editor, Handbook of Mathematical Logic. North-Holland, Amsterdam, 1977, pp. 321–344.
[Sta95]Stark, I. D. B.: Names and Higher-Order Functions. PhD thesis, University of Cambridge, 1995. Also published as Technical Report 363, University of Cambridge Computer Laboratory, April 1995.
[Sta96a]Stark, I. D. B.: Categorical models for local names. Lisp and Symbolic Computation, 9(1):77–107, 1996.
[Sta96b]Stark, I. D. B.: A fully abstract domain model for the -calculus. In 11th Annual Symposium on Logic in Computer Science. IEEE Computer Society Press, Washington, DC, 1996, pp. 36–42.
[Sto88]Stoughton, A.: Substitution revisited. Theoretical Computer Science, 59:317–325, 1988.
Notes
This paper is dedicated to Rod Burstall. It is a revised and expanded version of Gabbay and Pitts [GaP99]. ↩
Of course, one can introduce a type of ‘names’ in a HOAS-style signature, as is done for example in [HMS98]; but as the authors of that work say (p. 26): ‘The main drawback of HOAS is the difficulty of dealing with metatheoretic issues concerning names.... As a consequence, some metatheoretic properties involving substitution and freshness of names...cannot be proved inside the framework and instead have to be postulated.’ It is precisely such problems with names that we claim our approach overcomes in a simple way. ↩
Instead of using set theory, one can use a higher-order logic based on Church’s simple theory of types [Chu40] as the basis of the approach described here, but we have yet to develop this formulation. ↩