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

Capture-Avoiding Substitution as a Nominal Algebra

Murdoch J. Gabbay1 and Aad Mathijssen2

1 School of Mathematical and Computer Sciences, Heriot-Watt University,

Edinburgh EH14 4AS, Scotland, Great Britain

murdoch.gabbay@gmail.com

2 Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

A.H.J.Mathijssen@tue.nl

Abstract. Substitution is fundamental to computer science, underlying for example quantifiers in predicate logic and beta-reduction in the lambda-calculus. So is substitution something we define on syntax on a case-by-case basis, or can we turn the idea of ‘substitution’ into a mathematical object?

We exploit the new framework of Nominal Algebra to axiomatise substitution. We prove our axioms sound and complete with respect to a canonical model; this turns out to be quite hard, involving subtle use of results of rewriting and algebra.

1 Introduction

Substitution is intuitively the operation v[a↦ →t] meaning:

Replace the variable a by t in v.

Is there an algebra which describes exactly the properties of v[a↦ →t] independently of what v and t are (λ-terms, formulae of a logic, or any mixture or variation thereof)?

Consider by way of analogy the notion of ‘a field’. This has an algebraic characterisation which tells us what properties ‘a field’ must have, independently of which field it is, or how it may be implemented (if we are programming). This is useful; for example the definition of ‘vector space’ is parametric over fields, and this step requires a characterisation of what fields are [1].

When we begin to algebraically axiomatise substitution some unusual difficulties present themselves. Consider the following informally expressed candidate property of substitution:

v[a↦ →t][b↦ →u] = v[b↦ →u][a↦ →t[b↦ →u]] provided a ∉fv(u).

This is not algebraic, because of the side-condition a ∉ fv(u). Here fv(u) is ‘the free variables of u’, which is a property of the syntax of u.

So is it the case that substitution cannot be axiomatised, and only exists as an incidental property of syntax used to talk about ‘real’ mathematical objects? But in that case, what is the status of the intuition which makes us agree that the property above should be satisfied by any self-respecting substitution action?

We shall argue that the following properties axiomatise substitution, all of substitution, and nothing but substitution. We express them in Nominal Algebra (given formal meaning in the rest of this paper):

(var↦→)⊢var(a)[a↦→T]=T(#↦→)a#X⊢X[a↦→T]=X(f↦→)⊢f(X1,...,Xn)[a↦→T]=f(X1[a↦→T],...,Xn[a↦→T])(f≠var)(abs↦→)b#T⊢([b]X)[a↦→T]=[b](X[a↦→T])(ren↦→)b#X⊢X[a↦→var(b)]=(ba)·X
Fig. 1. Axioms of SUB

For convenience we now give an informal reading:

(var ↦→): If a is a variable then a with a replaced by T, is T.

(# ↦→): If a is fresh for X then X with a replaced by T is X.

(f ↦→): Substitution distributes through term-formers (we can have as many as we like); f ranges over them.

(abs ↦→): Substitution distributes under abstraction, provided an ‘accidental capture-avoidance’ condition holds (b is fresh for T).

(ren ↦→): If b is fresh for X then X with a replaced by b is identical to X with a replaced by b and simultaneously b replaced by a.

Formally, Fig. 1 uses nominal terms [2] as a syntax, and nominal algebra [3] as an algebraic framework.

A number of questions now arise: a) Is this substitution? In what sense; are the axioms sound, and for what model? b) Are the axioms complete for that model? c) Do other (perhaps unexpected) models exist of the same axioms? d) Can the axioms be used to found theories of predicate logic, λ-calculus, unification, and so on?

Sections 2 and 3 define nominal terms and nominal algebra. Section 4 defines substitution as a nominal algebraic theory. Section 5 develops some highly non-trivial technical results. Section 6 answers a) by showing that on a canonical model, our axioms for substitution give rise to something which is recognisably substitution as we might expect it to behave. Section 7 further shows the harder property mentioned in b) that our axioms for substitution precisely characterise what is true of that concrete model. The Conclusions then describes related and future work. Questions c) and d) are answered positively in other papers [4, 5].

2 Nominal terms

We define a syntax of nominal terms. For simplicity fix a sort of atoms A and a (base) sort of terms T. Then sorts τ are inductively defined by:3

τ ::= T | A | [A]τ

We could admit more sorts of atoms, and base sorts other than T, if we wished.

Our syntax has term-formers: Fix term-formers fρ to each of which is associated some unique arity ρ = (τ1, . . . , τn)τ. We may write f : ρ for ‘f, which has arity ρ’. We assume term-formers:

sub : ([A]τ, T)τ (τ ∈{T, [A]T}) var : (A)T pair : (T, T)T binder : ([A]T)T

The two subs will be used to represent the substitutions from Fig. 1; the condition on τ is for simplicity only.

var, pair, and binder define a sufficiently rich language for our axioms of substitution to have an interesting action, but as mentioned in the Introduction almost anything else would do (e.g. see example signatures in [6]).

Finally, we can define the sorted syntax itself:

Fix some countably infinite set of atoms a, b, c, . . . ∈A. These model object-level variable symbols (the ones we axiomatise substitution for).

Fix a countably infinite collection of unknowns X, Y, Z, T, U, . . ..4 Intuitively these represent unknown terms. We assume unknowns are inherently sorted and infinitely many populate each sort: so X is shorthand for Xτ, and XA and XT are two different unknowns with confusingly similar names.

Terms t, u, v are inductively defined by the following grammar:

t ::= aA | (π · Xτ)τ | ([aA]tτ)[A]τ | (f(τ1,...,τn)τ(t1 τ1, . . . , tn τn))τ

Here we call (π · Xτ)τ a moderated unknown; π is described below. We have indicated sorts with a subscript but we shall usually omit them; we repeat the definition above without subscripts, for clarity:

t ::= a | π · X | [a]t | f(t1, . . . , tn).

A permutation π of atoms is a bijection on A with finite support meaning that for some finite set of atoms π(a) ≠ a, and for all other atoms π(a) = a; in other words, for ‘most’ atoms π is the identity. As usual write Id for the identity permutation, π-1 for the inverse of π, and π ◦π′ for the composition of π and π′, i.e. (π ◦π′)(a) = π(π′(a)). Id is also the identity of composition, i.e. Id ◦π = π and π ◦ Id = π. We may abbreviate Id · X to X. Importantly, we shall write (a b) for the permutation which maps a to b and vice versa, and maps all other c to themselves.

In Fig. 1 we have sugared sub([a]u, t) to u[a↦→t]. We suggestively name a term of this form an explicit substitution.

A few more simple notations are useful for later: We call the size of t its inductive rank.5 Write a ∈t (or X ∈t) for ‘a (or X) occurs in (the syntax of) t’. Occurrence is literal, e.g. a ∈ [a]a and a ∈π·X when π(a) ≠ a. Similarly write a ∉t and X ∉t for ‘does not occur in the syntax of t’. Write syntactic identity of terms t, u as t ≡u to distinguish it from provable equality. Important: we do not quotient terms in any way.

It may help to show how nominal terms relate to ‘ordinary’ syntax. For convenience identify atoms with variable symbols, then the syntax of the untyped λ-calculus is inductively defined by e ::= a | ee | λa.e. We define a map (-)′ to nominal terms by: a′ = var(a), (e1e2)′ = pair(e′ 1, e′ 2), (λa.e)′ = binder([a](e′)). Even for this simple signature of var, pair, and binder, there are interesting things to say. For example we shall see that binder([a]X) behaves much like the λ-context λa.- where - is a ‘hole’, and of course sub will allow us to state (and prove!) nontrivial properties of substitution in the presence of those holes. Example 4.1 gives three such properties; there are many more and our main result Theorem 7.5 asserts that we can prove all of them from our axioms.

3 Nominal algebra

We can now do algebra. For us, algebra is the logic of equality (no implication, no quantification). We consider a canonical syntax-based model later in Section 6 and find much of interest to say about it in Section 7 — other models of our axioms are the topic of other work [4].

A freshness (assertion) is a pair a#t of an atom and a term. Call a freshness of the form a#X (so t ≡X) primitive. Write ∆ for a (possibly infinite) set of primitive freshnesses and call it a freshness context. We may drop set brackets in freshness contexts, e.g. writing a#X, b#Y for {a#X, b#Y }. Also, we may write a, b#X for a#X, b#X. Define derivability on freshnesses in natural deduction style by:

(#ab)a#ba#t1 · · · a#tn(#f)a#f(t1, . . . , tn)(#[]a)a#[a]ta#t(#[]b)a#[b]tπ-1(a)#X(#X)a#π · X

Here f ranges over term-formers,6 t and t1, . . . , tn range over terms, X ranges over unknowns, and a and b permutatively range over atoms, i.e. a and b represent any two distinct atoms. We use similar conventions henceforth.

Write ∆⊢a#t when a derivation of a#t exists using the elements of ∆ as assumptions. Say that ∆ entails a#t or a#t is derivable from ∆; call this a freshness judgement.

An equality (assertion) is a pair t = u where t and u are terms of the same sort. Define derivability on equalities in natural deduction style by:

(refl)t=tt=u(symm)u=tt=uu=v(tran)t=vt1=u1···tn=un(congf)f(t1,...,tn)=f(u1,...,un)t=u(cong[])[a]t=[a]ua#tb#t(perm)(ab)·t=t[a#X1,...,a#Xn]∆···t=u(fr)(a∉t,u,∆)t=u

We may call this the core theory and refer to it as CORE. We may write ∆⊢CORE t = u for ‘t = u is derivable from assumptions ∆ in the core theory’; call this an equality judgement.

In (fr) square brackets denote discharge in the sense of natural deduction, as in implication introduction [7]; ∆ denotes the other assumptions of the derivation of t = u.7 This is useful because unknowns in a derivation intuitively represent unknown terms, but any finite collection of such terms can mention only finitely many atoms; (fr) expresses that we can always find a fresh one.

In (perm) read (a b) · t as ‘swap a and b in t’. It is defined on syntax by:

π · a ≡π(a) π · (π′ · X) ≡(π ◦π′) · X π · [a]t ≡[π(a)](π · t) π · f(t1, . . . , tn) ≡f(π · t1, . . . , π · tn)

So π propagates through the structure of t until it reaches an atom or a moderated unknown. We can easily verify that (π ◦π′) · t ≡π · (π′ · t) and Id · t ≡t.

Here is an example derivation, using the fact that [a]a ≡ (a b) · [b]b:

(#ab)a#b(#[]b)a#[b]b(#[]a)b#[b]b(perm)[a]a = [b]b

Provable equality in CORE coincides with provable equality on nominal terms in the sense of nominal unification [2], for details see elsewhere [3]. This corresponds in a suitable sense to α-equivalence, though in a non-trivial way since ⊢CORE [a]X = [b]X does not hold — but b#X ⊢CORE [a]X = [b](b a) · X does [2].

Nominal Algebra (NA) is the theory outlined above, along with the ability to impose axioms. Call a triple ∆⊢t = u where ∆ is finite an axiom. We may write ⊢t = u when ∆ is empty (the empty set). Call an instance of an axiom a step in a derivation where the conclusion is obtained from an axiom by instantiating unknowns by terms,8 and permutatively renaming atoms, such that the hypotheses are corresponding instances of freshness conditions of the axiom.

4 SUB: the theory of explicit substitution

NA substitution allows the axioms in Fig. 1. Here (f↦→) represents a schema of axioms, one for each term-former other than var; one particular example is (sub↦→). We make concrete choices of atoms a and b, of an unknown T of sort T, and of unknowns X, X1, . . . , Xn of appropriate sorts. We call the axioms and the resulting equality a theory of substitution and write it SUB.

Example 4.1

The following judgements are derivable in SUB:

1. a#Y ⊢SUB Z[a↦ →X][b↦ →Y ] = Z[b↦ →Y ][a↦ →X[b↦ →Y ]]

2. b#Z ⊢SUB Z[a↦ →X] = ((b a) · Z)[b↦ →X]

3. ⊢SUB X[a↦ → var(a)] = X

We give only the first derivation in full. We write σ for [b↦ →Y] and we use the unsugared syntax for the other substitutions.

(f↦→)sub([a]Z,X)σ=sub(([a]Z)σ,Xσ)a#Y(abs↦→)([a]Z)σ=[a](Zσ)(refl)Xσ=Xσ(congf)sub(([a]Z)σ,Xσ)=sub([a](Zσ),Xσ)(tran)sub([a]Z,X)σ=sub([a](Zσ),Xσ)

For part 2: We must prove b#Z ⊢SUB sub([a]Z, X) = sub([b](b a) · Z, X). By (congf), (refl), and (symm), it suffices to derive [b](a b) · Z = [a]Z. Using (perm) it suffices to derive a, b#[a]Z, which is easy.

For part 3: By (fr) we may assume b#X for some b ∉X, X[a↦ → var(a)], i.e. b ≠ a. By (tran) it suffices to derive X[a↦ → var(a)] = ((b a) · X)[b↦ → var(a)] and ((b a) · X)[b↦ → var(a)] = X. The former is an instance of part 2 of this example. For the latter it suffices to derive a#(b a) · X, by axiom (ren ↦→) and X ≡ (a b) · (b a) · X. By (#X), this follows from the assumption b#X.

5 SUBfr: explicit substitution rewritten

Equality has no algorithmic content so we have specified what is equal, but not how to verify it. Rewriting is algorithmic in that sense, given confluence. It is useful to give a rewrite system for SUB.

Nominal rewriting is like nominal algebra, but with a directed notion of equality; terms are taken up to equality in CORE. A rewrite rule ∇⊢l →r may trigger a rewrite in a term t when (an instance of) l is provably equal in CORE to some subterm of t, and the corresponding instance of ∇ is derivable using the ambient context of freshness assumptions ∆ (so ∇ is freshness conditions on the rewrite rule) [8, 9, 10]. Rewrite rules are given in Fig. 2. Write →∆ for the rewrite relation induced by rewrites in CORE, given ∆.

Say a freshness context ∆′ freshly extends ∆ when ∆′ = ∆∪∆′′ where ∆′′ may be empty, but if a#X ∈∆′′ then a ∉∆. Note that the rule (fr) precisely ‘introduces a ∆′′’. So b#X, a#X freshly extends a#X but a#Y, a#X does not.

(Rvar)⊢var(a)[a↦→X]→X(R#)a#Z⊢Z[a↦→X]→Z(Rf)⊢f(Z1,...,Zn)[a↦→X]→f(Z1[a↦→X],...,Zn[a↦→X])(f≠var,sub)(Rsub)a#Y⊢Z[a↦→X][b↦→Y]→Z[b↦→Y][a↦→X[b↦→Y]](Rabs)c#X⊢([c]Z)[a↦→X]→[c](Z[a↦→X])(Rren)b#Z⊢Z[a↦→var(b)]→(ba)·ZFig.2.SubstitutionasarewritesystemSUBfr
Lemma 5.1 (Rewriting is equality).

∆⊢SUB t = u is derivable if and only if t is related to u by the symmetric transitive reflexive closure of →∆′ for some ∆′ freshly extending ∆.

Say a property holds of a triple (∆, t, u) ‘provided ∆ has sufficient freshnesses’ when that property holds of some (∆′, t, u) for ∆′ freshly extending ∆. So for ∆, t, and u, equality between t and u SUB coincides with rewritability between them in SUBfr, provided that ∆ has sufficient freshnesses.

5.1 SUBe and strong normalisation up to SUBe

Substitution has the character of a computation and our re-casting SUB as a rewrite system recognises this. However substitutions also have an awkward ‘simultaneous’ character. For example

⊢SUBX[a↦→var(a′)][b↦→var(b′)][c↦→var(c′)]=X[c↦→var(c′)][b↦→var(b′)][a↦→var(a′)]

is derivable but there is no obvious direction to the equality and SUBfr does not strongly normalise on the terms.

Call a binary relation (by incredible coincidence write it →) strongly normalising when if for t1, t2, . . . we have t1→t2→t3→. . . then i exists such that if j ≥i then ti = tj. Clearly this is not the case of any →∆ from SUBfr.

Let SUBe be the NA theory with axioms in Fig. 3.

(Eswap) a#Y, b#X ⊢Z[a↦ →X][b↦ →Y ] = Z[b↦ →Y ][a↦ →X](Egarbage) a#Z ⊢Z[a↦ →X] = Z
Fig. 3. The theory SUBe
Lemma 5.2

The rules obtained from directing the equalities from SUBe, are admissible in SUBfr, i.e. every instance of the following can be obtained in SUBfr:

(Rswap) a#Y, b#X ⊢Z[a↦ →X][b↦ →Y ] →Z[b↦ →Y ][a↦ →X](Rgarbage) a#Z ⊢Z[a↦ →X] →Z

As a corollary, provable equality in SUBe implies provable equality in SUB.

We will show that → of SUBfr is strongly normalising up to provable equality in SUBe. Some auxiliary functions and notations are needed.

Fix ∆ and write a#v for ∆⊢a#v and ¬a#v for ∆⊬a#v. Let f range over all term-formers excluding sub (but including var), and let . denote the arithmetic product. Define |v|b by |v|b = 0 if b#v and only otherwise by:

|a|a = 1 |v[a↦ →t]|a = |t|a + 1 |v[a↦ →t]|b = |v|b(a#v)|v[a↦ →t]|b = |v|b(¬a#v, b#t) |v[a↦ →t]|b = |v|b+|t|b.|v|a+1 (¬a#v, ¬b#t)|f(v1, . . . , vn)|b = |v1|b + · · · + |vn|b + 1 |[a]v|b = |v|b + 1 |π · X|a = 1

Then the following inductive definition makes Theorem 5.3 a matter of easy arithmetic:

|f(v1, . . . , vn)| = |v1| + · · · + |vn| (n > 0) |f()| = 1 |[a]v| = |v||π · X| = 1 |a| = 1 |v[a↦ →t]| = |t|.|v|a + |v|
Theorem 5.3

If t →∆t′ then either ∆⊢SUBe t = t′ or |t|∆> |t′|∆. As a result SUBfr is strongly normalising up to provable equality in SUBe.

Write →∗∆ for the transitive reflexive (but not symmetric) closure of →∆. We note that ∆⊢SUBe t = u does not imply t →∗∆u or u →∗∆t. For a counterexample consider t ≡ var(a)[b↦ → var(c)] and u ≡ var(a)[b↦ → var(c′)].

5.2 Garbage and garbage-collection

Call the pair ∆⊢t a (nominal) term-in-context. Equalities, and rewrites, are on terms in context. Only if t is closed is context irrelevant.

Say that a term-in-context ∆⊢t has garbage when:

– for some subterm t′[a↦ →u] it is the case that ∆⊢a#t′, or

– for some subterm of the form π · X and some a ∈π · X, it is the case that both ∆⊢a#X and ∆⊢π(a)#X hold.

Otherwise say ∆⊢t has no garbage.

Example 5.4

Terms in the top line have no garbage, the others do:

⊢var(a)[a↦→X]⊢X[a↦→Y]a#X⊢(ab)·X⊢var(a)[b↦→X]a#X⊢X[a↦→Y]a,b#X⊢(ab)·Xa,b#X⊢((ab)·X)[c↦→var(c′)].

Alas the rewrite rule (Rsub) in SUBfr may introduce garbage (the innermost [b↦ →Y] acting on X). Alas also, α-equivalence (provable equality in CORE) may introduce garbage, for example a, b#X ⊢CORE (a b) · X = X.9

Say that ∆⊢t is a SUBfr-normal form when ∆⊢SUBe t = t′ for all t′ with t →∆t′. So a SUBfr-normal form may still rewrite with a rule from SUBfr ((R#) and (Rsub) to be precise) but that rewrite just has no effect up to provable equality in SUBe.

Lemma 5.5 (Garbage collection).

For any ∆⊢t there is some t′ a SUBfr-normal form with no garbage such that t →∗∆t′. Furthermore, if ∆⊢SUBe t = u is derivable then there is some SUBfr-normal form v with no garbage such that t →∗∆v and u →∗∆v.

5.3 Confluence

A standard way to prove confluence is to prove local confluence and strong normalisation. But SUBfr is not strongly normalising, see the example of Sect. 5.1. The interest of this proof is that we use SUBe to ‘cancel that out’.

Lemma 5.6

Rewrites of ∆⊢t in the nominal rewrite system SUBfr are locally confluent in a context with sufficient freshnesses, up to provable equivalence in CORE.

(Recall that the restriction on contexts is not a ‘real’ one, because we have (fr).)

Theorem 5.7

SUBfr is confluent in a context with sufficient freshnesses.

Proof

SUBfr is strongly normalising up to provable equality in SUBe by Theorem 5.3. It is locally confluent (in a context with sufficient freshnesses) by Lemma 5.6. By Newman’s Lemma [11] it is confluent up to provable equality in SUBe. Finally, we use the second part of Lemma 5.5. ⊓⊔

From this follow:

Theorem 5.8

SUB is conservative over CORE. That is, ∆⊢SUB t = u if and only if ∆⊢CORE t = u, assuming that neither t nor u mention explicit substitution.

Corollary 5.9 (Consistency).

For all ∆ there are t, u such that ∆⊬SUB t = u.

6 Ground terms

Call terms g and h ground terms when they do not mention unknowns or explicit substitutions. These are inductively characterised by

g ::= a | f(g, . . . , g) | [a]g

where f ranges over all term-formers except for sub.

We consider the meaning of explicit substitution on ground terms (making a connection between [a↦ →t] and actual capture-avoiding substitution on syntax).

Define a ‘free atoms of’ function fa(g) on ground terms inductively as follows:

fa(a) = {a} fa(f(g1, . . . , gn)) =[1≤i≤nfa(gi) fa([a]g) = fa(g) \ {a}

Define the support of g by supp(g) = {a | ⊬a#g}.

Lemma 6.1

fa(g) = supp(g).

For each finite set of atoms arbitrarily choose some canonical ‘fresh’ atom not in that finite set. Then define a ground substitution action g[h/a] on ground terms of sort T and [A]T by

var(b)[h/a] ≡var(b) var(a)[h/a] ≡h f(g1, . . . , gn)[h/a] ≡f(g1[h/a], . . . , gn[h/a])([a]g)[h/a] ≡[a]g ([b]g)[h/a] ≡[b](g[h/a]) (b ∉fa(h))([b]g)[h/a] ≡[c](g[var(c)/b][h/a]) (b ∈fa(h), c fresh),

where f ranges over all term-formers excluding var (and sub of course), and ‘c fresh’ means c is fresh for {a, b}∪ fa(g) ∪ fa(h) according to our arbitrary choice.

Theorem 6.2

⊢SUB g[h/a] = g[a↦ →h] is always derivable.

Proof

By straightforward induction on the structure of g, using Lemma 6.1. ⊓⊔

Define an α-equivalence relation g =α h inductively by:

a=αag1=αh1 · · · gn=αhnf(g1, . . . , gn)=αf(h1, . . . , hn)g=αh [a]g=α[a]hg[var(c)/a]=αh[var(c)/b] [a]g=α[b]h(c fresh)

Here ‘c fresh’ means c fresh for {a, b} ∪ fa(g) ∪ fa(h).

Theorem 6.3

g =α h if and only if ⊢SUB g = h is derivable.

Proof

By Theorem 5.8 ⊢SUB g = h is equivalent to ⊢CORE g = h. By results about nominal terms [2, 3] this happens precisely when g =α h. ⊓⊔

So intuitively: On ground terms ⊢SUB g = h is α-equivalence and explicit substitution is capture-avoiding substitution.

7 ω-completeness

How do we know that SUB really is an axiomatisation of substitution? We now give a soundness and completeness result. ω-completeness (notation from [12]) is ‘soundness and completeness with respect to the closed term model’.

We need a number of technical definitions and lemmas.

7.1 Meta-level substitution

Call a substitution σ a finitely supported function from unknowns to terms of the same sort. Here, finite support means that σ(X) ≡ Id · X for all but finitely many unknowns X, i.e. for ‘most’ X.

Write [t/X] for σ defined by σ(X) ≡t and σ(Y) ≡ Id · Y , for all Y ≢X.

Let tσ (‘σ applied to t’) be inductively defined by:

aσ≡a(π·X)σ≡π·σ(X)([a]t)σ≡[a](tσ)f(t1,...,tn)σ≡f(t1σ,...,tnσ)

We may call tσ an instance of t. The substitution action extends to freshness assertions, equalities, and so on. We extend notations and terminologies silently. Note that this does not avoid capture; ([a]X)[a/X] ≡ [a]a and in this formal sense X is ‘meta’ and really does represent an unknown term.

Call σ nontrivial on X when σ(X) ≢ Id · X. By assumption σ is nontrivial for only finitely many unknowns. Say that σ′ extends σ when σ′(X) ≡σ(X) whenever σ is nontrivial on X. Call σ closing for some collection of freshness and equality assertions S when σ(X) is a closed term for every X ∈S. We will not mention S when it is clear from the context.

Say a closing σ is ∆-consistent when ⊢a#σ(X) for all a#X ∈∆.

Lemma 7.1

Fix ∆, X, and closed term v. If ⊢a#v for every a#X ∈∆ then there is a ∆-consistent closing σ which extends [v/X].

7.2 Suspended explicit substitutions

Suppose a term-in-context ∆⊢t ≡ (π · t′)[a1↦ →t1] . . . [am↦ →tm] is such that ∆⊢ai#tj for all 1 ≤i, j ≤m. Here m may equal 0, in which case t ≡ (π · t′).

Then call the partial syntax (π · -)[a1↦ →t1] . . . [am↦ →tm] a suspended substitution; we generally let α and β vary over suspended substitutions. β will typically be (π′ · -)[b1↦ →u1] . . . [bn↦ →un]. Suspended substitutions have a natural action on terms t′α given by replacing - by t′.

Lemma 7.2

Assuming sufficient freshnesses, if ∆⊢t is a SUBfr-normal form with no garbage then every explicit substitution t mentions is in a subterm u such that ∆⊢CORE u = Xα and ∆⊢Xα has no garbage.

Proof

Otherwise there is a rewrite such that ∆⊢t →t′ where ∆⊬SUBe t = t′. ⊓⊔

Lemma 7.3

Suppose t and u are SUBfr-normal forms with no garbage. Then ∆⊢SUBe t = u precisely when one of the following hold:

1. t ≡a and u ≡a.

2. t ≡π · X and u ≡π · X.

3. t ≡ [a]t′ and u ≡ [a]u′ and ∆⊢SUBe t′ = u′.

4. t ≡ [a]t′ and u ≡ [b]u′ and ∆⊢SUBe (b a) · t′ = u′ and ∆⊢b#t′.

5. t ≡ f(t1, . . . , tn) and u ≡ f(u1, . . . , un) and ∆⊢SUBe ti = ui for 1 ≤i ≤n (f ≠ sub).

6. t ≡t′α and u ≡u′β and m = n > 0 and ∆⊢SUBe t′ = u′, and for every i there is a unique j such that π-1(ai) = π′-1(bj) and ∆⊢SUBe ti = uj — and similarly for every j.

Theorem 7.4

Equality in SUB is decidable.

Proof

Given ∆, t and u, we can calculate whether ∆⊢SUB t = u is derivable:

1. Rewrite t and u to SUBfr-normal forms t′ and u′, using Theorem 5.3.

2. Remove garbage from t′ and u′, using Lemma 5.5.

3. Check if the top-level term-formers of t′ and u′ satisfy the criteria stated in Lemma 7.3; for each of the new proof obligations ∆⊢SUBe t′′ = u′′ go to step 2.10

4. If all criteria checks were successful, return true; otherwise false. ⊓⊔

7.3 ω-completeness

ω-completeness is soundness and completeness with respect to a model made out of closed terms (terms which do not mention unknowns X); since syntax is the canonical example on which substitution is defined, soundness and completeness with respect to this model is a powerful argument that in theory SUB, we got it right. An NA judgement ∆⊢SUB t = u has the flavour of a universal quantification over the unknowns it mentions. Soundness for the closed terms model means: if ∆⊢SUB t = u is derivable then all instances of this equality (subject to ∆) on closed terms are derivable. Much harder to prove is that furthermore if all instances are derivable (subject to ∆), then so is ∆⊢SUB t = u.

Call SUB ω-complete when if ⊢SUB tσ = uσ is derivable for all ∆-consistent closing substitutions σ (for ∆, t and u), then ∆⊢SUB t = u is derivable.

Theorem 7.5

SUB is ω-complete.

Proof

By contraposition. Suppose not ∆⊢SUB t = u. We construct ∆-consistent σ such that not ⊢SUB tσ = uσ. It suffices to do this for some ∆′ which freshly extends ∆; for convenience assume ∆= ∆′. By the first part of Lemma 5.5 and by Lemma 5.1 we may suppose t and u are SUBfr-normal forms with no garbage. By Lemma 7.2 further assume they have the particular form mentioned in that result. By Lemma 5.2 also ∆⊢SUBe t = u is not derivable. So now we must prove

(∆⊬SUBe t = u)implies(∃σ closing and ∆-consistent. ⊬SUB tσ = uσ),

where t and u have the structure as described above.

We work by induction on the size of t and u. We proceed by case distinction (we omit routine cases, and calculations concerning size):

– t ≡a and u ≡b. By Theorem 6.3.

– t ≡ f(t1, . . . , tm) and u ≡ g(u1, . . . , un) (f, g ≠ sub). Apply any closing ∆-consistent σ (easy to manufacture), use Theorem 6.2 to remove all explicit substitutions, and then use Theorem 6.3 to conclude ⊬SUB tσ = uσ.

– t ≡ f(t1, . . . , tm) and u ≡ f(u1, . . . , um) (f ≠ sub). By part 5 of Lemma 7.3 ∆⊬SUBe ti = ui for some i. We use the inductive hypothesis and Theorems 6.2 and 6.3.

– t ≡ [a]t′ and u ≡ [b]u′. Using Lemma 7.3 ∆⊬SUBe (b a) · t′ = u′ or ∆⊬b#t′. If ∆⊬b#t′, then choose appropriate σ and use Theorems 6.2 and 6.3. If ∆⊬SUBe (b a) · t′ = u′ then we can remove possible garbage from (b a) · t′ without increasing size, apply the inductive hypothesis, and finally use Theorems 6.2 and 6.3.

– t ≡Xα and u ≡Xβ and m = n > 0. Using Lemma 7.3 and notation from that result, ∆⊢SUBe t = u precisely when ∆⊢SUBe ti = uj for every i, j such that π-1(ai) = π′-1(bj). So suppose i and j are such that ∆⊬SUBe ti = uj. Now using pair, var, and binder, generate v such that ai ∈ supp(v) and supp(v) is otherwise fresh (thus, disjoint from atoms mentioned in t and u). Choose ∆-consistent closing σ extending [v/X] using Lemma 7.1. Then by Theorems 6.2 and 6.3 we see that ⊬SUB tσ = uσ.

⊓⊔

8 Conclusions

Substitution underlies quantifiers in predicate logics, the λ-binder of the λ-calculus, unification, and lots more besides. It is a central, not incidental, feature of these systems. This paper throws a new and unexpected light on this profoundly important common denominator.

Future work on nominal techniques needs a nominal axiomatisation of substitution. This paper provides that and the work has already found application in concurrent work; we use it to ‘power’ a nominal axiomatisation of first-order logic [5], and we develop abstract (non-term-based) models of SUB in [4]. Such enterprises would not be mathematically secure without Theorem 7.5 to tell us that we got our foundations right.

We have considered one substitution and Theorem 7.5 tells us it is capture-avoiding substitution. We can think of other kinds of substitution, for example context substitution which does not avoid capture; the basic principles are clear in this paper and there are a great many possibilities for applying them elsewhere.

Note how we decompose an equational system into a rewrite system over a simpler equational system, and we fully exploit results of nominal rewriting and nominal algebra as well as detailed calculations on terms (such as the notion of measure we use to prove confluence). Similar techniques may be useful for other systems; they seemed to arise in our treatment of first-order logic [5].

We find the nominal terms treatment of binding pleasingly clean; a nominal term such as λ[a]X or ∀[a]X corresponds exactly and syntax-for-syntax to what we intend when we write λa.t and ∀a.φ, right down to the way in which t and φ are instantiated. Other approaches to binding involve some degree of emulation (index lifting in de Bruijn [13], type-raising in type-based techniques [14]). Thus a nominal treatment of substitution is worthwhile to investigate in itself.

8.1 Related work

Crabbé [15, 16] axiomatises substitution much like us and shares (in our terminology) atoms and freshness conditions. Crabbé does not treat binding.11 So our substitution is capture-avoiding. Also, for us atoms and freshness side-conditions are parts of a broader nominal framework whereas Crabbé expresses them in first-order logic; we feel that nominal techniques have given us a cleaner separation of the layers of complexity hidden in these deceptively simple ideas.

Feldman [17] gives an algebraic axiomatisation inspired by a concrete model of functions/evaluations. His axioms are closer in spirit to Cylindric Algebras [1] and Lambda Abstraction Algebras [18, 19]. The three approaches share an infinity of term-formers which are ‘morally’ precisely λ[a], -[a↦ → -], and ∃[a]. We see the advantage of our treatment as systematising and formalising precisely what rôle the atoms really have. In any case the approaches above cannot directly express (ren↦→), (#↦→), and (abs↦→), even though instantiations are derivable for closed terms by calculations parametric over their specific structure.

Combinatory Algebra (CA) [20] and related systems implement substitution by ‘pipes’ (e.g. the translation of λ-terms into CA [20]). General truths such as (#↦→) are only provable for fixed closed terms by calculations parametric over its specific structure.

Lescanne’s classic survey [13] and the thesis of Bloo [21] chart a vast literature on λ-calculi with explicit substitutions. These decompose β-reduction as a rule to introduce explicit substitution ( (λa.u)t →u[a↦ →t] ), and explicit rules for that substitution’s subsequent behaviour (which is to substitute, of course). These calculi are designed to measure the cost of a β-reduction (in an implementation, which may be based on de Bruijn indexes [22] or on named variable symbols). They do not axiomatise substitution, they implement it. For example, ‘confluence’ is a typical correctness criterion for a calculus, and ‘ω-completeness’ is not.

8.2 Future work

Nominal unification [2] is ‘merely’ unification of nominal terms up to CORE. Our confluence results are a step towards unification up to SUB. Nominal Unification is to be compared (in a sense we do not discuss here) with higher-order patterns [23]; we now suggest that unification up to SUB is to be compared with higher-order unification [24] — with the difference that SUB is weaker, because there is no λ and application, only their combination as ‘substitution’.There is no obstacle to taking SUB over itself — that is, to taking what we write in this paper as, say, (X[a↦ →Y ])[t/X] and expressing it in a stronger axiom system as (X[a↦ →Y ])[X↦ →T ] where T is a ‘stronger’ meta-variable. This relates to the NEW calculus of contexts [25] and hierarchical nominal rewriting [26] investigated by the first author, but much more is possible and there are many substitutions out there which we could axiomatise.Armed with SUB and the knowledge that it is correct in the sense of Theorem 7.5 we hope to develop logics and λ-calculi with a fundamentally new, beautiful, and mathematically advantageous, way of treating substitution and more generally internalising the meta-level.

References

[1] Burris, S., Sankappanavar, H.: A Course in Universal Algebra. Springer (1981) Available online.

[2] Urban, C., Pitts, A.M., Gabbay, M.J.: Nominal unification. Theoretical Computer Science 323(1–3) (2004) 473–497

[3] Gabbay, M.J., Mathijssen, A.: Nominal algebra. Submitted STACS’07 (2006)

[4] Gabbay, M.J., Marin, A., Rota Bulò, S.: A nominal semantics for simple types. Submitted STACS’07 (2006)

[5] Gabbay, M.J., Mathijssen, A.: One-and-a-halfth-order logic. In: PPDP ’06: Proceedings of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, New York, NY, USA, ACM Press (2006) 189–200

[6] Gabbay, M.J., Pitts, A.M.: A new approach to abstract syntax with variable binding. Formal Aspects of Computing 13(3–5) (2001) 341–363

[7] Hodges, W.: Elementary predicate logic. In Gabbay, D., Guenthner, F., eds.: Handbook of Philosophical Logic, 2nd Edition. Volume 1. Kluwer (2001) 1–131

[8] Fernández, M., Gabbay, M.J., Mackie, I.: Nominal rewriting systems. In: Proc. 6th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2004), ACM (2004) 108–119

[9] Fernández, M., Gabbay, M.J.: Nominal rewriting. Information and Computation (2005) Accepted for publication.

[10] Fernández, M., Gabbay, M.J.: Nominal rewriting with name generation: abstraction vs. locality. In: Proc. 7th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2005), ACM (2005) 47–58

[11] Newman, M.: On theories with a combinatorial definition of equivalence. Annals of Mathematics 43(2) (1942) 223–243

[12] Groote, J.F.: A new strategy for proving omega-completeness applied to process algebra. In Baeten, J., Klop, J., eds.: CONCUR ’90: Proceedings of the Theories of Concurrency: Unification and Extension. Volume 458 of LNCS., London, UK, Springer-Verlag (1990) 314–331

[13] Lescanne, P.: From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions. In: POPL ’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press (1994) 60–69

[14] Paulson, L.C.: The foundation of a generic theorem prover. Journal of Automated Reasoning 5(3) (1989) 363–397

[15] Crabbé, M.: Une axiomatisation de la substitution. Comptes rendus de l’Académie des Sciences de Paris, Série I 338 (2004) 433–436

[16] Crabbé, M.: On the notion of substitution. Logic Journal of the IGPL 12 n.2 (2004) 111–124

[17] Feldman, N.: Axiomatization of polynomial substitution algebras. Journal of Symbolic Logic 47(3) (1982) 481–492

[18] Lusin, S., Salibra, A.: The lattice of lambda theories. Journal of Logic and Computation 14 n.3 (2004) 373–394

[19] Salibra, A.: On the algebraic models of lambda calculus. Theoretical Computer Science 249(1) (2000) 197–240

[20] Barendregt, H.P.: The Lambda Calculus: its Syntax and Semantics (revised ed.). Volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland (1984)

[21] Bloo, R.: Preservation of Termination for Explicit Substitution. PhD thesis, Eindhoven University of Technology, Eindhoven (1997)

[22] de Bruijn, N.G.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the church-rosser theorem. Indagationes Mathematicae 5(34) (1972) 381–392

[23] Miller, D.: A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation 1(4) (1991) 497536

[24] Huet, G.: Higher order unification 30 years later. In: TPHOL 2002. Number 2410 in LNCS (2002) 3–12

[25] Gabbay, M.J.: A new calculus of contexts. In: Proc. 7th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2005), ACM (2005)

[26] Gabbay, M.J.: Hierarchical nominal rewriting. In: LFMTP’2006. (2006) 32–47

Notes

3 So sorts are just T, [A]T, [A][A]T, and so on, and similarly A, [A]A, and so on. ↩

4 Unknowns, atoms, and term-formers, are assumed disjoint. ↩

5 In plain english: the depth of a proof that t is in the set of terms, using the inductive definition above. ↩

6 More precisely, f is a meta-variable ranging over term-formers. ↩

7Insequentstyle,(fr)wouldbe∆,a#X1,...,a#Xn⊢t=u∆⊢t=u(a∉t,u,∆).8Instantiationofunknownsismostlywhatthereaderwouldexpect:textualreplace-mentofXbyt.SeeSect.7.1fortheformaldefinition.
↩ ↩

9 This is one reason SUB is a difficult beast to handle, and it took us quite a while to decide to split it up as a rewrite system over a provable equality, and then which provable equality to use. ↩

10 Garbage could be introduced by case 4 of Lemma 7.3, so we must remove it. ↩

11 He declares as much: ‘. . . we are not concerned with the notion of bound variable’ [16, page 2]. See also the axioms (there is no (abs↦→)) and the soundness and completeness result — Crabbé’s model is based on (in our notation) var and pair, whereas we consider a model based on var, pair, binder, and sub. ↩