Nominal Sets, Equivariance Reasoning, and Variable Binding
1 Equivariance reasoning
FM techniques are a methodology of thinking about syntax and in particular about syntax with binding. They take their name from the original FM (Fraenkel-Mostowski) theory of sets presented in my thesis [4]. For this document we use a different way of presenting FM techniques based on the idea of a Nominal Set, which is a set equipped with certain algebraic properties (just as a group, ring, or field, is a set equipped with certain properties), see Definition 1.2. First we need background machinery:
Fix a countably infinite set of atoms . Write typical elements . For write () for the function such that and and for all other atoms . This is a bijection with inverse itself, write for the group generated by () for all under functional composition . Write typical elements and Id for the identity.
A Nominal Set is a pair of an underlying set and permutation action (written infix) of type and satisfying the usual axioms, namely ( and Id . The permutation action also satisfies a finiteness condition omitted here.1
The point is that finite labelled trees, and hence the standard model of syntax but also a natural model of proofs as trees, are Nominal Sets: the permutation action is given pointwise by the action on the labels. Thus for example natural numbers satisfy a trivial permutation action given by always. A datatype of trees for terms of the -calculus (using as variable names)
is also a Nominal Set with the permutation action given pointwise by the action on the atoms labelling the tree. Furthermore we can represent a theory of -equivalence on these terms as a subset of “well-formed” trees in the inductively defined set
namely those inductively constructed using the rules
where in (Lam) there is a side-condition that () () (thus ‘fresh’ for the conclusion). The usefulness of this way of looking at syntax and properties of syntax as Nominal Sets begins with the following trivial theorem:
If a property (on trees) is defined (inductively) using predicates whose validity is invariant under permuting atoms, then the property is invariant under permuting atoms.
Here “invariant under permuting. . . ” means “given some valid instance of the property, a permutation uniformly applied to its arguments yields another valid instance”.
We have an example in the property of well-formedness of proof-trees of = given in (3). is a valid instance of (Var) and if we apply () to this we obtain , which is also a valid instance of (Var). The case of (App) is simple. A permutation applied to a valid instance of (Lam) is also a valid instance of (Lam) because ()() if and only if ()().2
We now have a very concrete demonstration that proofs of = are invariant under permutation; we permute the atoms in the proof as a tree. We can take this further. Consider proving transitivity of = by induction on proof-trees. The induction predicate is (in words) “given a valid proof-tree Π concluding in , for all valid proof-trees concluding in , there exists a valid proof-tree concluding in ”. This property is constructed using predicates invariant under permutations (validity of proofs of =) and so is itself invariant under permutations. Thus from Theorem 1.3 we know if we have the inductive hypothesis of Π, we have it of Π for any permutation Π.
We proceed by induction on Π. The case of (Lam) for and causes problems: we may assume Π proves [[] and proves [[] and we assume the inductive predicate for Π, but we do not know so we cannot proceed. However, we can apply a permutation () to Π, and () to , for chosen completely fresh. Now we have valid proofs () Π concluding in [[] and () concluding in [[], and also the inductive predicate for () Π. We can now complete the proof of transitivity.
Just these ideas of permutations have already been adopted and put to use by other authors also in published work (see for example [6]).
2 Taking it further
There is an equivalence class of proofs concluding in , one for each fresh ; we can take it as an object in its own right. This is an instance of FM abstraction [] which exists for any Nominal Set by virtue of the permutation action, which lets us rename atoms and construct an equivalence class in the general case (see [2, Section 5]). We can apply this to syntax as well as proofs:
is a datatype of -terms up to -equivalence. An element of [] is (concretely) an equivalence class of pairs for a ‘bound atom’ fresh for the other atoms in the ‘body’ .
There are various ways of taking this further; Nominal Sets form a category, the Schanuel Topos. Because it is a topos we can construct a general theory of abstractions and equivariance reasoning within it (this is FMCat in [5, Section 2], see also [2, p.21]). Nominal Sets are also a special case of a general theory of FM sets, see [4] and [2]. Nominal Sets can be axiomatised in first-order logic, see [7]. A team in Cambridge has developed FreshML, a programming language based on these principles in which we can program using abstractions and permutations, see [1]. Finally, I am currently implementing FM sets in Isabelle, see [4]. Further reading can be found in any of the references below, and my homepage www.cl.cam.ac.uk/~mjg1003.
References
[1] FreshML homepage, http://www.freshml.org.
[2] M. J. Gabbay and A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001), 341–363.
[3] Murdoch Gabbay, FM for names and binding, cl.cam.ac.uk/~mjg1003/papers/talks/200212-jaist-talk.ps.
[4] Murdoch J. Gabbay, A theory of inductive definitions with alpha-equivalence, Ph.D. thesis, Cambridge, UK, 2000.
[5] Murdoch J. Gabbay, Theory and models of the -calculus using fraenkel mostowski generalised, Submitted to the commemorative volume for 35 years of Automath, F. Kamareddine (ed.)., September 2002.
[6] L. Cardelli, P. Gardner, G. Ghelli, Manipulating trees with hiding, FOSSACS 2003, to appear.
[7] A. M. Pitts, Nominal logic, a first order theory of names and binding, Information and Computation, To appear. (A preliminary version appeared in the Proceedings of the 4th International Symposium on Theoretical Aspects of Computer Software (TACS 2001), LNCS 2215, Springer-Verlag, 2001, pp 219–242.).
Notes
1See [3, eq. 3], [5, eq. 4], and ‘finite support’ in [2, Def. 3.3]. ↩
2This is not the case if we try to base the theorem on substitutions generated by [] instead of permutations generated by (]. ↩