A New Approach to Abstract Syntax Involving Binders
Abstract
The Fraenkel-Mostowski permutation model of set theory with atoms (FM-sets) can serve as the semantic basis of meta-logics for specifying and reasoning about formal systems involving name binding, -conversion, capture avoiding substitution, and so on. We show that in FM-set theory one can express statements quantifying over ‘fresh’ names and we use this to give a novel set-theoretic interpretation of name abstraction. Inductively defined FM-sets involving this name-abstraction set former (together with cartesian product and disjoint union) can correctly encode object-level syntax modulo -conversion. 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.
1. Introduction
The message of this paper is that a modest change to classical set theory can yield benefits for the meta-theory of formal systems that involve name-binding (which most of them do). But of course such a change is not to be undertaken lightly, so we begin with a critique of the current state of the art. It is oriented towards the particular use of such a meta-theory that most concerns us: the formalisation, quite probably with machine-assistance, of proofs about the operational semantics of programming languages.
Background The theory and practice of specifying and reasoning about syntactical structures that do not involve binding constructs is well understood. The theory involves such indispensable concepts as user-declared algebraic data types [10] (inductively defined sets), structural recursion over such data, and proof by structural induction [1]; the practice can be seen in several general-purpose systems for machine-assisted proof (such as [12, 30]). 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 re-done for each object-language on a case-by-case basis. If only to make large, machine-checkable proofs feasible, a more sophisticated approach is called for.
One such approach involves representing object-level variables by variables in a meta-language 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—an idea going back to Church [2] and Martin-Löf [23] which 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 for our intended applications to operational semantics. There are recent proposals to overcome this shortcoming [24, 5]. They result in systems which are technically very interesting but force the designer of algorithms and proofs ‘modulo- -conversion’ to use forms of expression in our view 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. Of course, one can introduce a type of ‘names’ in a HOAS signature, as for example is done in [15]; 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 which we claim our approach overcomes in a simple way. Similar criticisms apply to approaches to binding based upon de Bruijn’s nameless terms or categorical combinators [4, 3, 7]: 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. 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 modulo renaming. We present these in an extensional framework with the expressive power of classical set theory which remains close to informal practice in its forms of expression. This, and the focus on -conversion, makes our work close in spirit to that of Gordon and Melham [11], 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 renaming become part of the underlying set theory (or higher order logic—since we believe one can use that rather than set theory as the basis of the approach described here, but we have yet to develop this formulation). This results in notions of structural recursion and induction that seem rather simpler than those in [11] (cf. Example 5.8 below).
Contributions of this paper We motivate our use of Fraenkel and Mostowski’s permutation model of sets (the ‘FM-universe’ as we call it) by considering the operation of permuting the variables in an expression and its relation to -conversion (Theorem 2.1). The fundamental notion of ‘finite support’ is recalled in Section 3 and used to define a quantifier for ‘fresh’ names (Definition 3.4). These concepts are used in the key definition of the paper: an apparently new set-theoretic notion of name-abstraction (Definition 4.2). Its importance is justified by the observation (of which Theorem 5.1 is a specific example) that data types of syntax modulo -conversion can be correctly modelled by sets in the FM-universe that are inductively defined by operators built up using this new abstraction set-former in combination with the usual operators for disjoint union and cartesian product. In this way, the standard initial algebra semantics of algebraic data types can be extended to encompass signatures involving binding operators. The notions of finite support and quantification over fresh names in the FM-universe enable us to formulate versions of structural recursion and induction for such signatures with binders. We give examples of this in Section 5. Section 6 sketches the relationship of our approach to recent work on modelling variable-binding abstract syntax in presheaf categories [7, 14]. Finally, Section 7 mentions some of the many things that remain to be done to develop our set-theoretic modelling of abstract syntax involving binders. One of our main motivations is to produce a meta-logic for specifying and reasoning about syntax and semantics (of programming languages involving binding constructs) that is close to informal practice when it comes to the crucial matter of structural recursion/induction. We claim that the ideas introduced here provide some interesting raw material along those lines; but it should be emphasised that many potentially difficult issues of ‘proof engineering’ lie between our notion of abstraction in the FM-universe and its application in mechanised proof assistants.
2. Permutative renaming
In the ’20s and ’30s Fraenkel and Mostowski devised their permutation model in order to prove the independence of the Axiom of Choice (AC) from the other axioms of set theory with atoms (ZFA) (and three decades later Cohen proved the harder result of independence of AC from set theory without atoms (ZF), via his celebrated forcing method; see [16, Section 6] for a brief survey of these matters). Our application of their model is rather far from this purpose! To motivate its use let us consider the paradigmatic example, namely the terms of the untyped lambda calculus, which we can take to be elements of the following inductively defined set of syntax trees:
where is some fixed, countably infinite set whose elements we call atoms (or ‘names’, but that term is too overloaded). Consider the following three versions of the notion of variable-renaming for elements of , where :
capture-avoiding substitution of for all free occurrences of in ;
textual substitution of for all free occurrences of in ;
interchange of all occurrences (be they free, bound, or binding) of and in .
Although the third version is possibly unfamiliar, it is in fact more basic than the other two because: firstly, one does not need to know whether any of the constructors defining are binders in order to define it; secondly, it can nevertheless be used to define -conversion, as the following result shows (cf. [13, p 36], which uses in place of for the same purpose).
Recall that -conversion, , is usually defined as the least congruence on that identifies with . Then coincides with the binary relation on inductively generated by the following axioms and rules.
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 to : this follows from the facts that preserves , and that if does not occur in , then .
This theorem suggests that matters to do with variable binding can be phrased in terms of the operation of variable-transposition , rather than the more familiar operation of variable-substitution (be it textual , or capture-avoiding ). 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 one essence of the notion of ‘variable’, namely that properties of syntax 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 sentences about syntax
the validity of which of course depends upon the nature of , but also, crucially, upon the fact that all the free variables of are listed in . Such notions belong to the rich mathematical theory of sets equipped with a permutation action, which we draw upon next. It is important to note that much of that theory would be inapplicable were one to try to base the development upon arbitrary (or even injective) functions from atoms to atoms, rather than upon permutations.
3. FM-sets
Given a group , recall that a -set is a set equipped with a -action, which by definition is a function mapping pairs to elements and satisfying for all and that and (where is the group identity and the group multiplication). We need this notion for the case , the group of all permutations of the set . (In Section 7 we need to consider products of such groups.) Note that is itself an -set if we define to be ; and then the set of lambda terms from the previous section is an -set via an action defined recursively from that one:
-sets like have an important finiteness property: their elements only involve finitely many different atoms. The following key notion expresses this property purely in terms of the action, and hence can be applied to any -set, whether or not it is given concretely in terms of syntax trees.
Let be an -set. A subset supports if for all
We say is finitely supported if there is some finite supporting . In fact one can prove that if is finitely supported, then there is a smallest finite subset of supporting it: we call this the support of , and denote it by (leaving implicit which -set is being referred to). We say that an atom is apart from , and write , if .
Recall the usual von Neumann cumulative hierarchy of sets, [35]. We can build the notions of ‘permutation action’ and ‘finite support property’ into a set-theoretic universe by replacing with the Fraenkel-Mostowski universe, , which by definition is the least -class (i.e. class with an -action) satisfying
where is disjoint union, and iff , , and is finitely supported for the action given by: . The elements of not in will be called FM-sets (over the set of atoms ).
The FM-universe can be built up as the union of transfinitely many stages, where at each successor ordinal we take all finitely supported subsets of the previous stage and a copy of . Each stage, and hence itself, comes equipped with an -action making all of its elements finitely supported. Note that an FM-set is not itself closed under the permutation action unless . The notion of support of an FM-set is quite subtle. Note in particular that may differ from the set of atoms in , the -transitive closure of . For example , but . contains a copy of the ZF universe , namely those FM-sets whose -transitive closure is disjoint from . We call such an a pure FM-set.
The usual constructions of ZF can be carried out within FM to build various sets. In particular we will make use of the set of natural numbers, and the usual constructions of cartesian products, disjoint unions, power- and function-sets.
Axiomatic FM-set theory To develop the properties of the FM-universe further, it is convenient to work in a setting where all set-theoretic constructions are guaranteed to preserve the finite support property and hence keep us within . One can achieve that with a suitable theory of atoms and FM-sets within classical first-order logic with equality. This theory is based upon ZFA—ZF set theory with Atoms (see [8], for example). This has a signature containing not only a binary relation symbol ‘ ’ for membership, but also a constant ‘ ’ for the set of atoms. ZFA has an axiom expressing the fact that only non-atoms can have elements; its other axioms are like those of ZF set theory, except that certain quantifications Q (for Q ) have to be restricted to Q when must range just over sets rather than over sets and atoms. The axioms of ZFA are given in an Appendix to this paper. They 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.1. We can get both properties by adding the following axiom to ZFA.
Define FM to be the first-order theory obtained from ZFA by adding the axioms
( Not Finite)
Here and elsewhere we write ‘’ to indicate a suitable formula in the language of ZFA expressing that is a finite subset of . Similarly, ‘’ stands for a suitable formula expressing the notion of apartness given in Definition 3.1: see the Appendix (noting that the theory given there generalises FM to many sorts of atoms). This in turn requires us to express in the language of ZFA the permutation action—or at least to express the result of transposing atoms and in , which can be done by -recursion: once again, see the Appendix for details. is a model of the theory FM just because is an infinite set and every element of is finitely supported.
Careful formulations of the definition of capture-avoiding substitution quite often make use of a choice function for picking out fresh variables: see [39, 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, because it contradicts the Axiom of Choice (AC). For example, the axiom ( Not Finite) implies that the set of cofinite subsets of is a set of non-empty sets; but there is no choice function in —a diagonalisation argument (using the fact that every graph of a function must be finitely supported) shows this. Proof assistants based on set theory or higher order logic often include Hilbert’s choice operator, , to provide anonymous notations for terms defined by formulas (see [21, Section 2.1]). Since the -operator can be used to prove AC, we cannot add it to FM without inconsistency. However, it would be both consistent and useful to augment the language of FM with a notation for terms that are uniquely defined by a formula.
In what follows we make implicit use of the theory FM: everything we do can be reduced to its rather spare language and axioms, but we avoid this in order not to obscure the ideas.
The -quantifier Many consequences of the finite support property of FM-sets are neatly expressed in terms of the following quantifier for ‘newness’ of atoms.
Let denote the FM-set of cofinite subsets of an FM-set , i.e. those for which is finite. For each formula of the language of FM, we write
for the formula expressing that is in .
So this -quantifier means “for all but finitely many atoms , ”. However, the nature of the set of atoms in endows the quantifier with very special properties. For one thing, since every FM-subset of has finite support, it is not hard to see that is either finite or cofinite. So is an ultrafilter and commutes with conjunction, disjunction and negation. More is true:
For any formula and list of distinct variables in the language of FM, consider the following formulas.
(where is a conjunction of apartness formulas, one for each variable in the list). Then in FM, (3) (4) (5); and if the free variables of are contained in , then also (5) (3) and hence in this case the three formulas are provably equivalent in FM.
One can extract introduction and elimination rules for the -quantifier from the above lemma, provided one uses sequents tagged with sets of possibly-free variables (a common practice in categorical logic [20])—e.g. sequents of the form , where is a finite set of formulas, a formula, and a finite set of variables containing those occurring freely in and . Then we can derive an introduction rule for of the form
(cf. the usual rule for -introduction) and an elimination rule of the form
(cf. -elimination). In these rules, means the finite set properly extending with a variable .
In view of the lemma, we are justified in reading as ‘for some/any new atom , it is the case that ’. This simultaneous - 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. We see this in subsequent sections, where we put the -quantifier to work.
4. Abstracting atoms
In Section 2 we saw that -conversion can be formulated in terms of the two notions of permuting variables and of the non-occurrence, or ‘apartness’, predicate. In Section 3 these two notions were lifted from the particular data type of -terms to an enveloping universe of sets. So now we can consider what ‘ -conversion of sets’ means, arriving at a new, set-theoretic notion of abstraction. By analogy with the relation used in Theorem 2.1 to characterise -conversion of -terms, consider the following binary relation on :
It is not hard to see that is an equivalence relation. We denote the -equivalence class of a pair by and call it the -abstraction determined by and . (We will see below that .) This is a form of ‘abstraction as information hiding’ (like that for abstract data types [28]), since turns out to behave like a pair in which the identity of is hidden. However, and quite remarkably, -abstractions also embody a notion of ‘abstraction as function’ (analogous to that occurring in higher order abstract syntax), as the following lemma shows. We write for the subclass of consisting of unary partial functions: i.e. is in if and only if it satisfies
Using the easily verified fact that if , then , together with the the ZFA axiom of Collection, one obtains the following.
Each -abstraction is an element of and has support .
Write for the subclass of consisting of all -abstractions , as ranges over and over . By the lemma, each is a function; and by construction its domain of definition is a subset of . In fact if , one can show that is the cofinite set , which by the lemma is . Thus if we can apply the function to any atom satisfying to obtain an element that we call the concretion of the -abstraction at . An -abstraction is in fact uniquely determined by some/any of its concretions, since one can prove in FM that for all
For any FM-set , the FM-set of -abstractions of elements of is:
(An application of the ZFA axiom of Collection is needed to see that this is a set rather than a proper class; moreover it is finitely supported, with .)
Thus the elements of are -abstractions satisfying and . In the rest of this paper we will only be concerned with the case when , in which case the condition is vacuously satisfied. The use of the same notation for the abstraction set former and for its elements is not ambiguous because is not an atom. Using the construct in combination with cartesian product and disjoint union, we can form inductively defined FM-sets that allow us to view sets of syntax modulo -conversion as algebraic data types in of a kind that is very close to the ‘classical’ theory in for syntax without binders. We give the paradigmatic example of this, untyped -terms modulo , in the next section.
5. Example: as an inductive FM-set
First, let us recall a little of the theory of inductively defined sets (for the simple case of finitary set operators). Given a function mapping FM-sets to FM-sets which is definable by a formula in FM, monotone for , and which preserves unions of countable ascending chains, then the least fixed point of exists; we call it the inductively defined FM-set determined by and denote it by . It can be constructed by the familiar Tarski formula: .
Now it follows from Definition 4.2 that is monotone and preserves unions of countable ascending chains of FM-sets. Therefore we can use it in combination with other such functions, such as cartesian product ( ) and disjoint union ( ), to form inductively defined FM-sets. For example, consider
As in Section 2, here we are using a notation for disjoint union in which the injection functions are named explicitly—by , , and in this case.
Consider the FM-set of untyped -terms, inductively defined as in (1). Then , the FM-set of equivalence classes modulo the equivalence relation of -conversion, is in bijection with the inductively defined FM-set .
Combine the proof of Theorem 2.1 with the definition of .
Under the bijection of Theorem 5.1, the set of (names of) free variables of an -equivalence class of -terms is identified with the support (in the sense of Definition 3.1) of the corresponding element of : see Example 5.9 below. In particular, corresponds to the subset of closed -terms modulo .
Initial algebra semantics Like cartesian product and disjoint union, the abstraction set-former is the object part of a functor on FM-sets and functions: its action on a function , is the function that maps each to the unique -abstraction satisfying . Thus each function on FM-sets built up using , , and is functorial; and a standard argument shows that the associated inductively defined FM-set is an initial algebra for this functor. In other words, for every , there is a unique such that
commutes. In particular we have:
The FM-set of -terms modulo -conversion is an initial algebra for the functor .
The usefulness of the initial algebra property of inductively defined FM-sets can be increased by analysing the nature of functions out of abstraction sets . For example, specifying an algebra for amounts to giving functions
and one would like to know when is induced via the quotient mapping from a function . As the following lemma shows, the concepts of finite support and -quantifier from Section 3 provide an answer.
For all functions in , there is a (necessarily unique) satisfying iff satisfies the condition
The condition (7) captures the idea that the value of the induced function at some should be independent of the choice of . The lemma specifies what does just when is ‘fresh’, but this is enough to tell us the effect of on any element of , because of the way the latter is defined.
Combining the initial algebra property of with the above lemma, we obtain the following principle of structural recursion for -terms modulo -conversion. (Compare it with the Recursion Scheme of [11, Section 3.1].) A similar principle can be derived for other inductively defined FM-sets involving the abstraction set-former.
Given functions , , and in with satisfying
then there is a unique such that
Moreover, the support of is contained in .
Given a subset in , to prove that is the whole of it suffices to show
This structural induction principle seems to correspond very closely to informal inductive arguments about -equivalence classes of -terms that proceed by picking representatives and applying structural induction at the level of abstract syntax trees, leaving mute the tedious proofs that such choices do not affect the argument. In effect, by restricting to equivariant properties (cf. (2)), FM-set theory ensures that all those choices of representatives are made in a way that does not affect meaning. In the rest of this section we give some simple examples.
Given and , if in Theorem 5.5 we take and make suitable choices for the functions , , and , we can deduce that there is a function that is the unique element satisfying
Condition (8) is satisfied in this case because by Lemma 4.1, holds for any and . From the above properties it follows that under the bijection of Theorem 5.1 between elements of and -equivalence classes of -terms , corresponds to the capture-avoiding substitution function . One property of capture-free substitution of -terms is that the only free occurrences of in are due to free occurrences of in . The analogue for of this property is the statement that if , then holds for all . This can be proved by structural induction on by taking in Corollary 5.6. Hence (by Lemma 3.5) holds for any . Thus by Lemma 5.4, induces a function for each . In this way we get a substitution function satisfying for all that . (Cf. the substitution function in [7, Section 3].)
In Theorem 5.5, taking and suitable choices for the functions , we can deduce that there is a unique function satisfying
Condition (8) is satisfied in this case for the same reason as in the previous example. By Lemma 3.5, the last property of above is equivalent to
but from the last part of Theorem 5.5 we have that (since the particular that determine all have empty support). Therefore we can strengthen this last defining clause for to:
So the formalism 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 defining a similar function by recursion using their axiomatisation of -conversion [11, Section 3.3].)
The principle of structural recursion embodied in Theorem 5.5 requires us not only to specify some functions of the correct type, but also to verify the condition (8) for one of them. In the previous two examples, this condition is satisfied simply because is never in the support of . Here is a different kind of example.
It is not hard to see that the support of a finite set of atoms is just itself. Hence is not in the support of . So in Theorem 5.5, taking and making suitable choices for the functions , it follows that there is a unique function satisfying
where in the last clause we have strengthened to using the same argument as in the previous example. This function gives a structurally recursive definition of the ‘finite set of free atoms’ for elements of . Using structural induction (Corollary 5.6) one can show for all that in fact (cf. Remark 5.2).
There is no function in picking out the ‘finite set of bound atoms’ of elements of , in the sense that it satisfies
We cannot use Theorem 5.5 to define such a function because in this case condition (8) would require (any ), which is certainly false. Indeed, we can argue by contradiction to see that no such function exists in : if it did, it would necessarily have finite support, so picking any atoms not in its support, we would have ; then satisfies and so
i.e. , contradicting the choice of and .
The results of this section can be extended to deal with signatures of -ary operators each of whose arguments is an -ary abstraction (for )—the ‘binding signatures’ considered in [7, Section 2]. An FM-set inductively defined using a set operator given by a suitable sum of products of and iterations of the operator is in bijection with the set of terms modulo -conversion over such a signature. This FM-set is an initial algebra for the functor associated with the set operator and from the shape of the latter 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 operators.
Our approach 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 FM versions of structural recursion and induction principles (we consider some possibilities in Section 7). However, we regard the sheer simplicity of the above examples (compared with analogous examples in other formalisms) as a good sign!
6. Relation to presheaf models
One origin of the work presented here lies in the ‘-calculus’, a calculus of higher order functions and dynamically created names introduced by the second author and Stark [32, 36] (see also [17]). In [37], Stark studies a model of the -calculus based on one of Moggi’s ‘dynamic allocation’ monads [29] 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 the work on modelling -calculus names in [6, 38] and the recent work on modelling variable-binding abstract syntax [7, 14], where other presheaf categories besides are considered.
Now, a somewhat overlooked model of the -calculus, mentioned in [33, 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 [18, Lemma 1.8] and [22, Section III.9]. Put more concretely, and this is the point, the objects of the Schanuel topos are -sets in which every element has finite support (Definition 3.1), and its morphisms are the -equivariant functions. Thus on the one hand, the Schanuel topos relates to the FM-universe much as the usual cumulative hierarchy relates to the topos of sets (see [19] 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 [7, 14] 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 presheaf toposes? It is well known that toposes correspond to theories in extensional, higher-order, intuitionistic logic [20]. 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 easy to calculate with, compared to 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 [7] as establishing, amongst other things, a very nice categorical algebra for the de Buijn view of variable-binding and substitution. Here however, we are motivated more by the desire for a useful logic of explicit bound names—mainly 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 abstraction), which is present the Schanuel toposes, but not in the presheaf toposes. We have chosen to use a set-theoretic rather than a topos-theoretic presentation here, because we think it is more accessible; but the same fundamental ideas underlie both and the Schanuel topos.
7. Further directions
Splitting the set of atoms To support syntax involving (finitely many) different sorts of variables one can use the following mild generalisation of the FM-universe. Fix an infinite set of disjoint, countably infinite sets (of atoms), and form a universe much as in Section 3
except that we work with -sets (and -classes) for the subgroup of consisting of permutations that respect the partition ; so is isomorphic to the product group . Clearly, this affects the meaning of the apartness relation ; and we have to replace and by and respectively, where . A corresponding generalisation of the first order theory FM to a theory of Fraenkel-Mostowski set theory with many Sorts of atoms (FMS) is given in an Appendix to this paper. As an example of the use of FMS, here are mutually inductively defined sets in for the types ( ) and terms () of Girard’s system F [9] modulo renaming of bound type variables and bound variables. The definition is parameterised by sets of atoms for type variables and variables respectively.
Equivariant SOS We believe that FM-set theory will be a useful setting for developing programming language semantics based on structural operational semantics [34]. 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 -quantifier we have introduced here. (Indeed, logic programming in the style of Miller and Nadathur [26] involving this quantifier may be possible.) It is also possible that the approach presented here will help extend the ‘functorial’ operational semantics of [40] to encompass languages involving binders.
FM type theory An extensional set theory is by no means the only setting in which to consider the notions of permutation action and finite support (although we believe it is the simplest place to start). We have begun to investigate what our approach might look like in the setting of constructive type theory [23, 30] and meta-programming [31]. For one thing, it is evident that Definition 4.2 generalises to a dependently typed version of abstraction
which bears the same relationship to the -quantifier as dependent function types () bear to universal quantification ( ). Another interesting possibility is to build information about the apartness relation into types whose set-theoretic interpretation is
This opens up the possibility of giving a decidable approximation to the apartness relation as part of a type system. It also allows us to introduce a term-former generalising the -quantifier:
where if is the type environment . Thus, rather in the spirit (though not the letter) of [25], one goal we are aiming for is an SML-like language [27] for meta-programming that combines user-declared data types with primitives for atomic types (i.e. sorts of atoms), abstraction types , and apartness . A practically important part of such a language will be pattern-matching definitions of (recursively defined) functions out of such data types, using ‘binding patterns’ for values of abstraction types and in which ‘freshness conditions’ like (8) are enforced statically by the type system. For example, given declarations
in this as yet non-existent language, and given the usual declaration for a list append function , we would want the following declarations of functions (for anonymously removing an atom from a list of atoms) and (for the free variables of a term)
to type check, with types and (cf. Example 5.9). Note the use of repeated variables of atomic type in patterns (equality of atoms is decidable!) and the use of ‘qualified patterns’ like to enforce that and are distinct. On the other hand, the declaration
should not type check, for the reasons given in Example 5.10.
8. Conclusion
Fraenkel and Mostowski’s permutation model of ZFA is 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 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 than the function space which is sometimes used to model name-abstraction. Amongst 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, while remaining pleasantly close to the familiar theory of first-order algebraic data types.
References
[1] R. M. Burstall. Proving properties of programs by structural induction. The Computer Journal, 12:41–48, 1969.
[2] A. Church. A formulation of the simple theory of types. Journal of Symbolic Logic, 5:56–68, 1940.
[3] P.-L. Curien. Categorical Combinators, Sequential Algorithms, and Functional Programming. Birkhäuser, 1993.
[4] N. G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indag. Math., 34:381–392, 1972.
[5] J. Despeyroux, F. Pfenning, and C. Schürmann. Primitive recursion for higher-order abstract syntax. In TLCA’97, LNCS vol. 1210, pages 147–163. Springer-Verlag, 1997.
[6] M. P. Fiore, E. Moggi, and D. Sangiorgi. A fully abstract model for the -calculus (extended abstract). In 11th Annual Symposium on Logic in Computer Science, pages 43– 54. IEEE Computer Society Press, Washington, 1996.
[7] M. P. Fiore, G. D. Plotkin, and D. Turi. Abstract syntax and variable binding. In this volume.
[8] M. P. Fourman. Sheaf models for set theory. Journal of Pure and Applied Algebra, 19:91–101, 1980.
[9] J.-Y. Girard. Interprétation fonctionelle et élimination des coupures dans l’arithmetique d’ordre supérieur. PhD thesis, Université Paris VII, 1972. Thèse de doctorat d’état.
[10] J. A. Goguen, J. W. Thatcher, E. G. Wagner, and J. B. Wright. Initial algebra semantics and continuous algebras. JACM, 24:68–95, 1977.
[11] A. D. Gordon and T. Melham. Five axioms of alpha-conversion. In TPHOLs’96, LNCS vol. 1125, pages 173– 191. Springer-Verlag, 1996.
[12] M. J. C. Gordon and T. F. Melham. Introduction to HOL. Cambridge University Press, 1993.
[13] C. A. Gunter. Semantics of Programming Languages: Structures and Techniques. MIT Press, 1992.
[14] M. Hofmann. Semantical analysis of higher-order abstract syntax. In this volume.
[15] F. Honsell, M. Miculan, and I. Scagnetto. -calculus in (co)inductive type theory. Technical report, Dipartimento di Matematica e Informatica, Università degli Studi di Udine, 1998.
[16] T. J. Jech. About the axiom of choice. In J. Barwise, editor, Handbook of Mathematical Logic, pages 345–370. North-Holland, 1977.
[17] A. Jeffrey and J. Rathke. Towards a theory of bisimulation for local names. In this volume.
[18] P. T. Johnstone. Quotients of decidable objects in a topos. Math. Proc. Cambridge Philosophical Society, 93:409–419, 1983.
[19] A. Joyal and I. Moerdijk. Algebraic Set Theory. Cambridge University Press, 1995.
[20] J. Lambek and P. J. Scott. Introduction to Higher Order Categorical Logic. Cambridge University Press, 1986.
[21] L. Lamport and L. C. Paulson. Should your specification language be typed? Technical Report 147, Digital SRC, 1998.
[22] S. MacLane and I. Moerdijk. Sheaves in Geometry and Logic. A First Introduction to Topos Theory. Springer-Verlag, 1992.
[23] P. Martin-Löf. Intuitionistic Type Theory. Bibliopolis, Napoli, 1984.
[24] R. McDowell and D. Miller. A logic for reasoning with higher-order abstract syntax. In 12th Annual Symposium on Logic in Computer Science, pages 434–445. IEEE Computer Society Press, Washington, 1997.
[25] D. Miller. An extension to ML to handle bound variables in data structures: Preliminary report. In Proceedings of the Logical Frameworks BRA Workshop, 1990.
[26] D. Miller and G. Nadathur. A logic programming approach to manipulating formulas and programs. In 4th Annual Symposium on Logic in Computer Science, pages 379–388. IEEE Computer Society Press, Washington, 1987.
[27] R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML (Revised). MIT Press, 1997.
[28] J. C. Mitchell and G. D. Plotkin. Abtract types have existential types. ACM Transactions on Programming Languages and Systems, 10:470–502, 1988.
[29] E. Moggi. An abstract view of programming languages. Lecture Notes, 46 pp, 1989.
[30] C. Paulin-Mohring. Inductive definitions in the system Coq; rules and properties. In M. Bezem and J. F. Groote, editors, TLCA’93, LNCS vol. 664, pages 328–345. Springer-Verlag, 1993.
[31] F. Pfenning. Elf: A language for logic definition and verified metaprogramming. In 4th Annual Symposium on Logic in Computer Science, pages 313–321. IEEE Computer Society Press, Washington, 1987.
[32] A. M. Pitts and I. D. B. Stark. Observable properties of higher order functions that dynamically create local names, or: What’s new? In MFCS’93, LNCS vol. 711, pages 122– 141. Springer-Verlag, 1993.
[33] A. M. Pitts and I. D. B. Stark. On the observable properties of higher order functions that dynamically create local names (preliminary report). In Workshop on State in Programming Languages, Copenhagen, 1993, pages 31–45. ACM SIGPLAN, 1993. Yale Univ. Dept. Computer Science Technical Report YALEU/DCS/RR-968.
[34] G. D. Plotkin. A structural approach to operational semantics. Technical Report DAIMI FN-19, Aarhus University, 1981.
[35] J. R. Shoenfield. Axioms of set theory. In J. Barwise, editor, Handbook of Mathematical Logic, pages 321–344. North-Holland, 1977.
[36] I. D. B. Stark. Names and Higher-Order Functions. PhD thesis, University of Cambridge, 1995.
[37] I. D. B. Stark. Categorical models for local names. Lisp and Symbolic Computation, 9(1):77–107, 1996.
[38] I. D. B. Stark. A fully abstract domain model for the -calculus. In 11th Annual Symposium on Logic in Computer Science, pages 36–42. IEEE Computer Society Press, Washington, 1996.
[39] A. Stoughton. Substitution revisited. Theoretical Computer Science, 59:317–325, 1988.
[40] D. Turi and G. D. Plotkin. Towards a mathematical operational semantics. In 12th Annual Symposium on Logic in Computer Science, pages 280–291. IEEE Computer Society Press, Washington, 1997.
Appendix: axiomatic FMS set theory
FMS is a single-sorted theory in first-order predicate calculus with equality whose signature consists of a binary relation and constants , and whose axioms are as follows.
Axioms of ZFA
(where not free in ).
Structure of the set of atoms
‘Freshness’ property
Here stands for
where the term denotes the set of finite subsets of and has a standard set-theoretic definition. This formula also uses terms for the transposition of -atoms in , which can be defined by -recursion: