HTML reading edition · 2 source pages · Open the source PDF

Nominal Sets, Equivariance Reasoning, and Variable Binding

Murdoch J. Gabbay mjg1003@cl.cam.ac.uk Computer Laboratory, Cambridge University, UK

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:

Definition 1.1

Fix a countably infinite set of atoms A. Write typical elements a, b, c, . . . ∈A. For a, b ∈A write (a b) for the function A →A such that a↦ →b and b↦ →a and n↦ →n for all other atoms n ≠ a, b. This is a bijection with inverse itself, write PA for the group generated by (a b) for all a, b ∈A under functional composition ◦. Write typical elements π, π′ ∈PA and Id ∈PA for the identity.

Definition 1.2

A Nominal Set is a pair ⟨X, · ⟩ of an underlying set X and permutation action · (written infix) of type PA × X →X and satisfying the usual axioms, namely π · (π′ · x) = π ◦π′ · x and Id · x = x. 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 N satisfy a trivial permutation action given by π · n = n always. A datatype of trees for terms of the λ-calculus (using A as variable names)

Λ ∼= A + Λ × Λ + A × Λ (1)

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

T ∼= A + T × T + A × T × T, (2)

namely those inductively constructed using the rules

a =α a (Var)t1 =α t′ 1t2 =α t′ 2t1t2 =α t′ 1t′ 2(App)t{c/a} =α t′{c/a′} λat =α λa′t′(Lam) (3)

where in (Lam) there is a side-condition that c ∉{a, a′} ∪n(t) ∪n(t′) (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:

Theorem 1.3

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). a =α a is a valid instance of (Var) and if we apply (b a) to this we obtain b =α b, 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 c ∉{a, a′}∪n(t)∪n(t′) if and only if π · c ∉{π · a, π · a′}∪n(π · t)∪n(π · t′).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 t =α t′, for all valid proof-trees Π′ concluding in t′ =α t′′, there exists a valid proof-tree Π′′ concluding in t =α t′′”. 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 t = λas and t′ = λa′s′ causes problems: we may assume Π proves s[c/a] =α s′[c/a′] and Π′ proves s′[c′/a′] =α s′′[c′/a′′] and we assume the inductive predicate for Π, but we do not know c = c′ so we cannot proceed. However, we can apply a permutation (d c) to Π, and (d c′) to Π′, for d chosen completely fresh. Now we have valid proofs (d c) · Π concluding in s[d/a] =α s′[d/a′] and (d c′) · Π′ concluding in s′[d/a′] =α s′′[d/a′′], and also the inductive predicate for (d c) · Π. 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 λat =α λa′t′, one for each fresh c; we can take it as an object in its own right. This is an instance of FM abstraction [A]X which exists for any Nominal Set X 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:

Λα ∼= A + Λα × Λα + [A]Λα(4)

is a datatype of λ-terms up to α-equivalence. An element of [A]Λα is (concretely) an equivalence class of pairs ⟨a, t⟩ for a ∈A a ‘bound atom’ fresh for the other atoms in the ‘body’ t ∈ Λα.

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 [b/a] instead of permutations generated by (b a) = [b/a, a/b]. ↩