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

Nominal Rewriting with Name Generation: Abstraction vs. Locality

Maribel Fernández and Murdoch J. Gabbay

Dept. of Computer Science

King’s College London Strand, London WC2R 2LS,UK

maribel,jamie@dcs.kcl.ac.uk

ABSTRACT

Nominal rewriting extends first-order rewriting with Gabbay-Pitts abstractors: bound entities are explicitly named (rather than being nameless, as for de Bruijn indices) yet rewriting respects α-conversion and can be directly implemented, thanks to the use of freshness contexts. In this paper we study two extensions to nominal rewriting. First we introduce a И quantifier for modelling name generation. This allows us to model higher-order functions involving local state, and has also applications in concurrency theory. The second extension introduces new constraints in freshness contexts. This allows us to express strategies of reduction and has applications in programming language design and implementation. Finally, we study confluence properties of nominal rewriting and its extensions.

Categories and Subject Descriptors

F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic—lambda calculus and related systems

General Terms

Theory

Keywords

Binders, α-conversion, first and higher-order rewriting, name generation, locality, confluence.

1. INTRODUCTION

Term rewriting systems (TRS) specify and reason about computation by working with trees labelled by variable and function symbols. Standard TRSs are first-order, but effort has been devoted to systems manipulating higher-order functions, where variables can be free or bound. Examples of higher-order rewriting formalisms combining first-order rewriting with a notion of bound variable are: Combinatory

Reduction Systems (CRS) [24], Higher-order Rewrite Systems (HRS) [27], Expression Reduction Systems (ERS) [22], and the rewriting calculus [10, 11]. The λ-calculus can be seen as a higher-order rewrite system with one binder called λ-abstraction.

Binders lead to α-conversion. First-order substitutions (i.e. replacements) may capture variables, so substitution in a higher-order system has to be carefully defined using renamings (α-conversion). In the higher-order formalisms mentioned above substitution is a meta-operation which relies on an implicit notion of α-conversion: terms are defined modulo renamings of bound variables. Several notions of explicit substitutions and explicit α-conversion have been defined for the λ-calculus (e.g. [1, 26, 12]) and more generally for higher-order rewrite systems (e.g. [30, 6]) with the aim of specifying the higher-order notion of substitution as a set of first-order rewrite rules. In most of these systems variable names are replaced by de Bruijn indices to make easier the explicitation of α-conversion, at the expense of readability.

Nominal rewriting is a new formalism for rewriting with bound variables, introduced in [14]. In nominal rewriting systems (NRSs) variables are named (whence ‘nominal’), substitution is first-order, and we deal with α-conversion by using an auxiliary freshness relation a#t between variables and terms (we say “a is fresh for the term t”). This freshness relation was introduced in [31, 18], and used to define a metalanguage for functional programming in [33], and to study unification problems in [36].

Nominal terms are first-order terms with built-in α-conversion. Our metalanguage does not include metasubstitutions and β-reductions (in contrast to notions of higher-order rewriting): in this sense, nominal rewriting systems are a middle ground between first-order and higher-order rewriting. The usual notion of higher-order substitution can be easily specified since α-conversion is in the meta-language.

Following [31, 18], we call the names that can be bound atoms and reserve the word variable for the identifiers that cannot be bound (known as variables and metavariables respectively in CRSs). In nominal terms the dependencies between variables and names are implicit, as in informal presentations of higher-order reductions. For example, λ-calculus β- and η-rules are written

app(λ([a]M), N) → subst([a]M, N)a#X ⊢ X → λ([a]app(X, a)).

Rewriting on nominal terms uses nominal matching [14, 36, 37], which does not need metasubstitutions and β-reduction but it does take into account freshness contexts. Selecting a nominal rewrite rule that matches a given term is an NP-complete problem in general [9]; however, by restricting to closed rules we can avoid the exponential cost: nominal matching is polynomial in this case [14]. Closed nominal rewriting turns out to be sufficiently close to first-order rewriting to share many of its properties, including a critical pair lemma [14], and a confluence theorem for orthogonal (i.e. left-linear and non-overlapping) systems which we prove in this paper. It is also expressive (see [14] for a translation of Klop’s Combinatory Reduction Systems) but has some limitations: rewrite rules have no mechanism for locally generating a fresh atom. This occurs in nature. For example in a rewrite system for the π-calculus [28] we might wish a reaction rule which we might write as ν[n]X →Иn.X, where И indicates that n must be fresh for all variables in the context in which the rewrite is introduced. Similar phenomena arise in programming languages, such as gensym in LISP, unit ref in ML, and many other forms of dynamic allocation both in the foundational and applied literatures.

In this paper we study two extensions to nominal rewriting:

(1) We consider the name generation construct И and make corresponding extensions to the freshness contexts to describe the scope of the names thus generated. Although И can be seen as a quantifier modelling locality of names, it is not a binder: we will show that abstracted names and local names have different behaviour.

(2) We extend just the contexts with new predicates specifying constraints for atoms in terms, for instance closedness.

In this way strategies of reduction such as closed reduction in the λ-calculus [16] may be concisely specified. This extension has applications in programming language design and implementation (see for instance [16]).

We study confluence properties of extended nominal rewriting: we give a critical pair lemma for extended NRSs and we prove that orthogonal systems are confluent.

In summary the main contributions of this paper are:

1. We formalise a notion of name generation and locality on nominal terms, with an associated notion of rewriting, with applications to distributed and higher-order programming.

2. We define two new predicates: a scope relation and a closedness relation, which can be used as constraints together with the freshness relation in contexts to specify strategies of reduction in rewrite rules.

3. A Critical Pair Lemma which ensures that extended nominal rewriting rules which do not introduce critical pairs are locally confluent.

4. A Confluence Theorem for orthogonal systems.

Related Work.

NRSs are related to algebraic λ-calculi [7, 8, 21, 3] where the β-reduction rule of the λ-calculus is combined with a set of term rewriting rules using standard first-order matching. Nominal rules are more general than these, since abstractions can be used in patterns, in the same way as in higher-order rewriting systems (e.g. CRSs [24], HRSs [27], ERSs [22], HORSs [34], and the ρ-calculus [10, 11]).

In contrast with higher-order rewriting systems, nominal rewriting does not need higher-order matching and higher-order substitutions. Instead, it relies on an extension of first-order matching that takes care of α-conversion without introducing β-reductions.

Although NRSs were not designed as explicit substitution systems, they are at an intermediate level between standard higher-order rewriting systems and their explicit substitution versions (e.g. [30, 6]), which implement in a first-order setting the substitution operation together with α-conversions using de Bruijn indices. Nominal rewriting is also related to Hamana’s Binding Term Rewriting Systems (BTRS) [19]. The main difference is that BTRSs use a containment relation that indicates which free atoms occur in a term (as opposed to a freshness relation which indicates that an atom does not occur free in a term).

The name generation operator И of extended nominal rewriting systems is related to the ν operator of Pitts and Stark’s ν-calculus [32] and ν the π-calculus restriction operator [28]. Apart from obvious differences between a simply typed λ-calculus, a process calculus, and a rewriting formalism, ν and И differ in their treatment of generated names: ν is a binder, whereas И is a scope construct.

Overview of the paper.

Section 2 presents nominal signatures and extended nominal terms. Section 3 defines α-equivalence as a logical notion first, then gives an algorithm to test α-equality. Nominal matching and unification algorithms are given in Section 4. Section 5 defines rewriting on extended nominal terms, and Section 6 studies confluence. Section 7 introduces closedness constraints and reduction strategies. We conclude the paper in Section 8.

2. EXTENDED NOMINAL TERMS

2.1 Signatures and terms

A Nominal Signature Σ is a set of function symbols typically written f. We do not assume that functions have sorts or arities in this paper (the original presentation [14] does but we shall not need them here).

So for example, a nominal signature for a fragment of ML has function symbols:

var app lam let letrec

Fix some signature Σ. Fix a countably infinite set X of term variables X, Y, Z. These will represent meta-level unknowns. Fix a distinct countably infinite set A of atoms a, b, c, f, g, h, . . .. These will represent object-level variable symbols. Consistent with later notation for terms, we write a ≡a to denote identity of atoms. We assume that Σ, X and A are pairwise disjoint.

A swapping is a pair of atoms, which we write (a b). Permutations π are generated by the grammar

π ::= Id | (a b)·π

We call Id the identity permutation. We call a pair of a permutation π and a variable X a moderated variable and write it π·X. Formally, swappings and moderated variables are just pairs, and permutations are just lists of swappings.

Extended Nominal Terms, also called tagged terms or just terms for short, are generated by the grammar

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

where we write A for a finite set of atoms which may be empty. We may write И∅.blah more succintly as blah, and similarly we may write Id·X as X.

Terms are called respectively atoms, moderated variables (or just variables for short), tuples, abstractions and function applications.

In the clause for tuples, n is called the length of the tuple and may equal 0 in which case we have the empty tuple (). We omit the brackets when n is 1 if there is no ambiguity. In the clause for function applications, f may be applied to the empty tuple in which case we may write f() as just f.

Note that an extended nominal term is a tree with nodes annotated by function symbols or (moderated) variables, so, syntax in the accepted sense — later we call it the term’s skeleton — but also annotated at every node with a finite sets of atoms. We shall call these sets tags. A term such that every tag is empty is in essence ordinary syntax and is isomorphic to a(n unextended) nominal term [14].

We denote V(t) the set of variables that occur in the term t. Ground terms are terms without variables, that is V(t) = ∅. A ground term may still contain atoms, for example a or И{a}.() are ground terms and X is not.

An abstraction [a]t is intended to represent t with a bound, and accordingly we call occurrences of a abstracted (or bound) and unabstracted occurrences unabstracted (or free). We do not work modulo α-conversion of abstracted atoms, so syntactic identity ≡ is not modulo α-equivalence. For example, [a]a ≢ [b]b. In nominal techniques, α-equivalence ≈α is a logical notion constructed on top of ≡ using a notion of context which we shall define soon.

A tagged term И{a}.t is intended to represent t with a local name it is calling a. We call occurrences of a scoped or local, and unscoped occurrences unscoped or global. As with abstraction, we do not work up to α-conversion of tags.

Abstraction is inherited from previous work [36, 14], tags are new to this paper. We give some examples:

•И{a}.a is a scoped copy of a. In future, we drop the set curly brackets and write Иa.a.

•Иb.b is a local name called b. Note that Иa.a ≢Иb.b.

•Иa.b is b with a local name a (which is not used, the reader might like to consider it ‘garbage’). Иa.b is not syntactically identical to Иc.b, Иb.b, or b.

•Иa, b.a generates a and b and discards b. Because the tags are sets, Иa, b.a ≡Иb, a.a. However, Иa, b.a ≢ Иa, b.b.

•Иa.(И∅.a,И∅.a) generates a and makes the pair (a, a).

• (Иa.a,Иa.a) generates two local names which are both (by coincidence) ‘a’.

•Иa.(a,Иa.a) is a tuple which generates locally a and places it in the first component. The second component is also a, but this is a different copy in its own local scope. Иa.(a,Иa.a) ≢ (Иa.a,Иa.a).

• Using the ML signature mentioned above, we can write (lam[a]Иb.(app(var(a), app(var(b), X)))) which we will

abbreviate λ[a]Иb.a(bX). This term can be used to represent a function which has an argument a and generates a local name b (i.e. ref in ML).

2.2 Substitution and swapping

Substitution of an unknown X for a term s in a term t is a function that satisfies:

(ИA.a)[X↦→s] ≡ИA.a (ИA.(ft))[X↦→s] ≡ИA.(f(t[X↦→s]))

(ИA.(t1, . . . , tn))[X↦→s] ≡ИA.(t1[X↦→s], . . . , tn[X↦→s])(ИA.[a]t)[X↦→s] ≡ИA.[a](t[X↦→s])(ИA.π·X)[X↦→ИB.s] ≡И(A ∪π·B).π·s.

A substitution is generated by the grammar

σ ::= Id | σ[X↦→s].

σ has an action on terms given elementwise from the definition above and satisfying sId ≡s. We write substitutions postfix as just shown, and write ◦ for composition of substitutions: t(σ ◦σ′) ≡ (tσ)σ′.

The intuition of a moderated variable π·X is that we would like to rename the atoms in X, but we do not yet know what X is. If a substitution [X↦→s] instantiates X, as in the last clause of the definition above, we apply π to s. A permutation has an action on terms, denoted π·t defined in the natural way from the component swappings. The action of swappings on terms is defined inductively by:

(a b)·ИA.n ≡И(a b)(A).(a b)(n)(a b)·ИA.(ft) ≡И(a b)(A).(f(a b)·t)(a b)·ИA.(t1, . . . , tn) ≡И(a b)(A).((a b)·t1, . . . , (a b)·tn)(a b)·ИA.[n]t ≡И(a b)(A).[(a b)(n)](a b)·t(a b)·ИA.π·X ≡И(a b)(A).((a b) · π)·X.

Here we have applied swappings to atoms and sets of atoms (a b)(n) and (a b)(A). The action on sets is pointwise, and the action on atoms satisfies:

(a b)(a) ≡b (a b)(b) ≡a and (a b)(c) ≡c (c ≢a, b).

For example, (a b)·λ[a]Иb.abX ≡λ[b]Иa.ba(a b)·X.

2.3 Positions

A skeletal position p is generated by the grammar

p ::= ϵ | p.n

where n is a number. A position is a pair of a skeletal position and a finite (possibly empty) set of atoms A. We write s|p,A for the subterm of s at position (p, A).

Skeletal positions are usually called positions, we assume the reader is familiar with [13, 23]; see also [2]. ‘Skeletal’ refers to the tag-less ‘skeleton’ of a term: so ϵ is the root position; 1 indicates going under a function symbol or an abstraction [a]s; i refers to ith position in (s1, . . . , sn); permutations are ignored. Having arrived at a certain place p in the skeleton, ‘A’ means remove the atoms A from the tag at that (skeletal) position.

We omit a formal definition but give examples: If s ≡Иa, b.(Иa.X, Y ) then s|ϵ,∅≡s, s|ϵ,{a} ≡Иb.(Иa.X, Y ), s|ϵ,{a,b} ≡И∅.(Иa.X, Y ), and s|ϵ,{a,b,c} is undefined. s|ϵ.1,∅≡ Иa.X, s|ϵ.1,{a} ≡X, s|ϵ.2,∅≡Y , and s|ϵ.3,∅ is not defined. If s′ ≡ [a]t then s′|ϵ,∅≡s′ and s′|ϵ.1,∅≡t.

We write s[t]p,A for the result of replacing the subterm of s at (p, A) by t, merging the tags. We may omit A when it is empty, writing s[t]p instead of s[t]p,∅. For example if s is as above, then s[Z]ϵ ≡Z, s[Z]ϵ,{a} ≡Иa.Z, s[Иb.Z]ϵ,{a} ≡ Иa, b.Z, s[Иc.Z]ϵ,{b} ≡Иb, c.Z.

3. ALPHA-EQUIVALENCE

Syntactic equality s ≡t is a structural (rather than logical) fact. α-equivalence is a logical notion, which we define below.

3.1 A logical presentation

Constraints are generated by the grammar

P, Q, C ::= a#t | a@t | s ≈α t.

We call # a freshness predicate, @ a scoping (or locality) predicate, and ≈α an equality predicate. They will be defined formally below. The intended interpretation of

• a#t is “if a occurs in t then each occurrence is either in a tag, or abstracted”. For example, a#b, a#Иa.b, not a#Иa.a, however a#Иa.[a]a. We sometimes write a, b#s instead of a#s, b#s.

• a@t is “if an occurrence of a is unabstracted in t then it is in a tag”. For example, a@Иa.b and a@Иa.a, a@[a]a, but not a@a. We abbreviate a@s, b@s as a, b@s.

• s ≈α t is “s and t are α-equivalent” (see below).

In the following rules, and consistent with notation used above, we write a#И∅.Id·X as a#X, a@И∅.Id·X as a@X, И∅.Id·X ≈α t as X ≈α t, and s ≈αИ∅.Id·Y as s ≈α Y .

a#s is specified by deduction rules as follows:

a#ИA.a(#⊥)Pa#ИA.ba#s a#ИA.fsa#s1 · · · a#sna#ИA.(s1, . . . , sn)a#ИA.[a]sa#s a#ИA.[b]sπ−1(a)#X a#ИA.π·X

This definition is like the one in [14] except that terms have tags added; to calculate # we simply throw them out.

a@s is specified by deduction rules as follows:

a#X(#@)a@Xa@ИA.a(@⊥) a ∉APa ∈Aa@ИA.sa@s1 · · · a@sna ∉Aa@ИA.(s1, . . . , sn)a@sa ∉Aa@ИA.fsa@sa ∉Aa@ИA.[b]sa ∉Aa@ИA.ba ∉Aa@ИA.[a]sπ−1(a)@Xa ∉Aa@ИA.π·X

All rules except for (#И), (#⊥) and (И⊥) are echoed in algorithmic form in the next subsection.

Finally we define ≈α inductively as follows, where in all the rules except the last s and t are terms with an empty tag at the root (i.e. И∅.s, И∅.t).

s1 ≈α t1 · · · sn ≈α tn(s1, . . . , sn) ≈α (t1, . . . , tn)s ≈α t fs ≈α fta ≈α as ≈α t [a]s ≈α [a]ts ≈α (a b)·t a#t [a]s ≈α [b]tds(π, π′)#X π·X ≈α π′·XИ∅.s ≈αИ∅.t B\A@И∅.s A\B@И∅.tA ∪B ≠ ∅ИA.s ≈αИB.t

We have used the difference set of two permutations:

ds(π, π′)def=˘ n˛˛ π(n) ≠ π′(n)¯.

For example, ds((a b), Id) = {a, b}, so (using the rules above) we can deduce (a b)·X ≈α X from assumptions a#X and b#X and we also have as expected [a]a ≈α [b]b. Other examples of α-equivalence are: Иa.b ≈α b, and Иa, b.a ≈α Иa.a, but note that Иa.a ≉αИb.b.

Say constraints of the form a#ИA.a, a#X, a@X, and a@ИA.a with a ∉A, are reduced. We write ∆, ∇, Γ for sets of reduced constraints, we may call them contexts. If there are no constraints of the form a#ИA.a, and a@ИA.a with a ∉A in ∆we say it is consistent.

Call a set Pr of constraints a problem. We write ∆ ⊢Pr when proofs of P exist for all P ∈Pr, using elements of ∆as assumptions, and we say that ∆ entails Pr. Since the rules above decompose syntax, an algorithm to check entailment can be easily built using this logical presentation. We give an operational definition of the predicates #, @ and ≈α in the next subsection.

We now state some properties of #, @ and ≈α which are needed later. In particular, we show that ≈α is a congruence.

Lemma 3.1

If ∇⊢a#t then ∇⊢a@t.

Proof

We examine the derivation rules for @ and # and see that a proof of a#t can be transformed rule-for-rule to a proof of a@t. We may use (#И) to deduce a@X from some a#X ∈∇.End of proof

Lemma 3.2

Suppose ∇ is a reduced context.

1. ∇⊢a#π·t if and only if ∇⊢π−1(a)#t.

2. ∇⊢a@π·t if and only if ∇⊢π−1(a)@t.

3. ∇⊢a#ИA.s if and only if ∇⊢a#ИB.s.

4. If ∇⊢a#t and ∇⊢t ≈α t′ then ∇⊢a#t′.

5. If ∇⊢a@t and ∇⊢t ≈α t′ then ∇⊢a@t′.

Proof

The first, second, and third parts are by routine inductions on derivations.

The fourth part is by mostly routine induction on derivations. We use the first part for the case of И∅.[a]s ≈αИ∅.[b]t, and the third part for the case of ИA.s ≈αИB.t.

The fifth part follows from the second part in a similar way. We consider two example cases:

Suppose ∇⊢x@ИA.t and ∇⊢ИA.t ≈αИA′.t′ are derivable where at least one of A and A′ is nonempty. Then ∇⊢c@t′ for every c ∈A′ \ A, and ∇⊢c@t for every c ∈A \ A′, and ∇⊢И∅.t ≈αИ∅.t′. There are now three cases:

• If x ∈A′ then ∇⊢x@ИA′.t′ and we are done.

• If x ∈A and x ∉A′ then ∇⊢x@t′ and so ∇⊢ x@ИA′.t′ and we are done.

• If x ∉A and x ∉A′ then ∇⊢x@t and ∇⊢И∅.t ≈α И∅.t′ and we use the inductive hypothesis.

Suppose ∇⊢x@И∅.[a]t and ∇⊢И∅.[a]t ≈αИ∅.[a′]t′. Then ∇⊢t ≈α (a a′)·t′ and ∇⊢a#t′.

• If x ≡a we are done.

• If x ≡a′ we use the previous lemma to derive ∇⊢a@t′ using the derivation of ∇⊢a#t′, then extend to a derivation of ∇⊢a@[a′]t′.

• If x ∉{a, a′} we use the inductive hypothesis to deduce ∇⊢x@И∅.(a a′)·t′, the second part of this lemma to deduce ∇⊢x@t′, and finally extend to a derivation of ∇⊢x@И∅.[a′]t′ as required.

End of proof

Lemma 3.3

For fixed ∇, ≈α is an equivalence relation and ∇⊢s ≈α t implies ∇⊢π·s ≈α π·t.

Proof

Reflexivity is easy. For transitivity, we use induction on derivations and the previous lemma for the case of ИA.[x]s ≈αИA′.[x′]s′ ≈αИA′′.[x′′]s′′. The final part is also by induction; only the case of [a]s ≈α [b]t is in any way non-trivial, we use the previous lemma.End of proof

Corollary 3.4

• ∆⊢s ≈α π−1·π·s′ if and only if ∆⊢s ≈α s′.

• ∆⊢s ≈α π·s′ if and only if ∆⊢π−1·s ≈α s′.

• ∆⊢ds(π, π′)#s then ∆⊢π·s ≈α π′·s.

• ∆⊢A \ A′@s and ∆⊢A′ \ A@s then ∆⊢ИA.s ≈α ИA′.s.

• For fixed ∆, ≈α is a congruence. Thus, if ∆⊢t ≈α t′ then ∆⊢s[t]p ≈α s[t′]p.

Proof

The first four parts are by routine inductions using the previous results. The last part is by induction on the syntax of s and uses the previous cases.End of proof

3.2 An algorithmic presentation

We specify simplification rules on problems by:

a#ИA.b, Pr =⇒ Pra#ИA.fs, Pr =⇒ a#s, Pra#ИA.(l1, . . . , ln), Pr =⇒ a#l1, . . . , a#ln, Pra#ИA.[b]s, Pr =⇒ a#s, Pra#ИA.[a]s, Pr =⇒ Pra#ИA.π·X, Pr =⇒ π−1(a)#X, Pr
a@ИA.s, Pr =⇒ Pr a ∈Aa@ИA.b, Pr =⇒ Pr a ∉Aa@ИA.fs, Pr =⇒ a@s, Pr a ∉Aa@ИA.(l1, . . . , ln), Pr =⇒ a@l1, . . . , a@ln, Pr a ∉Aa@ИA.[b]s, Pr =⇒ a@s, Pr a ∉Aa@ИA.[a]s, Pr =⇒ Pr a ∉Aa@ИA.π·X, Pr =⇒ π−1(a)@X, Pr a ∉A
(l1, . . . , ln) =⇒ l1 ≈α s1, . . . ,≈α (s1, . . . , sn), Pr ln ≈α sn, Prfl ≈α fs, Pr =⇒ l ≈α s, Pr[a]l ≈α [a]s, Pr =⇒ l ≈α s, Pr[b]l ≈α [a]s, Pr =⇒ (a b)·l ≈α s, a#l, Pra ≈α a, Pr =⇒ Prπ·X ≈α π′·X, Pr =⇒ ds(π, π′)#X, PrИA.s ≈αИB.t, Pr =⇒ B\A@И∅.s, A\B@И∅.t,И∅.s ≈αИ∅.t, Pr A ∪B ≠ ∅

Here, on the left commas indicate disjoint set union, on the right they indicate possibly non-disjoint set union.

These rules define a reduction relation on problems: We write Pr =⇒Pr′ if Pr′ is obtained from Pr by applying a simplification rule. We denote by ∗=⇒ its transitive and reflexive closure.

For example, the last rule reduces the problem {Иa.a ≈α И∅.a,И∅.a ≈αИ∅.a} to {a@И∅.a,И∅.a ≈αИ∅.a}. Other examples are:

a#(X, [a]Y )∗=⇒a#X a#fa∗=⇒a#aa#((a b)·X, (b c)·Y )∗=⇒b#X, a#Y

These reduction rules are derived from the deduction rules in the last subsection, but there are differences; we omit a rule a@X, Pr =⇒a#X, Pr, which would correspond to (#И), and also rules corresponding to (#⊥) and (@⊥). If we didn’t, the important lemmas below would not hold.

Lemma 3.5

The simplification rules above are confluent and strongly normalising (reduction order does not matter).

Proof

By Newman’s Lemma [29] we need only show termination, because there are no critical pairs. The rules form a hierarchical system in the sense of [15], from which it follows that if the first two groups of rules are terminating and non-duplicating (they are) and do not use in the right-hand side any symbol defined in the third group (i.e. equality ≈α; they do not), then if the rules defining the equality symbol satisfy the general recursive scheme, then the whole system is terminating. The general recursive scheme requires that recursive calls in right-hand sides use strict subterms of the left-hand side arguments, and this is the case.End of proof

Write ⟨Pr⟩nf for the unique normal form of Pr, and ⟨P⟩nf for ⟨{P}⟩nf, i.e. the result of simplifying it as much as possible. We will say that an equality И∅.s ≈αИ∅.t is clashing when the terms s and t have different term constructors at the root (e.g. [a]u ≈α (v, w), X ≈α ft, a ≈α X, etc.) or they are two different atoms (e.g. a ≈α b) or two different variables (e.g. π·X ≈α π′·Y), or applications with different function symbols (e.g. ft ≈α gs).

Lemma 3.6

(Normal Forms). ⟨a#s⟩nf consists of reduced freshness constraints and ⟨a@s⟩nf consists of reduced scoping constraints. ⟨s ≈α t⟩nf may contain any mixture of reduced freshness constraints, reduced scoping constraints, and clashing equalities.

Proof

Any non-reduced freshness or scoping constraint can be simplified using the rules in the first two groups. Similarly, a non-clashing equation can be simplified with a rule in the third group.End of proof

Therefore ⟨Pr⟩nf can always be partitioned into ∆ ∪Eq where ∆is a (possibly empty) context and Eq a (possibly empty) set of clashing equalities Eq.

Lemma 3.7

Assume Pr =⇒Pr′. Then

Γ ⊢Pr if and only if Γ ⊢Pr′.

Proof

By inspection of the rules.End of proof

Theorem 3.8

Let ⟨Pr⟩nf = ∆∪Eq where ∆ is a context and Eq is a set of clashing equalities.

1. If ∆ is consistent then:

∆⊢Pr if and only if Eq = ∅.

2. ∆⊢P for all P if and only if ∆ is inconsistent.

Proof

The first part is proved by induction on the length of the derivation Pr∗=⇒⟨Pr⟩nf: using Lemma 3.7, ∆⊢Pr if and only if ∆ ⊢Eq. The result follows from the fact that if s ≈α t is clashing then there is no consistent ∆such that ∆⊢s ≈α t.

For the second part, we use the rules (#⊥) and (@⊥).End of proof

Corollary 3.9

Let Γ be a consistent context.

Γ ⊢Pr if and only if ⟨Pr⟩nf ≡∆ and Γ ⊢∆.

Proof

Consequence of Theorem 3.8 and Lemma 3.7.End of proof

4. UNIFICATION

A unification problem Pr is a problem as previously defined but replacing the equality constraint s ≈α t by the unification constraint s ?≈? t. A solution to a unification problem Pr is a pair (Γ, σ) of a consistent context and a substitution such that Γ ⊢Pr′σ where Pr′ is obtained from Pr by changing unification predicates into equality predicates, and Pr′σ is the problem obtained by applying the substitution σ to the terms in Pr′. If there is no consistent context satisfying this property, we say that Pr is unsolvable. We write U(Pr) for the set of unification solutions to Pr.

Write ∆ ⊢σ ≈α σ′ when ∆ ⊢Xσ ≈α Xσ′ for all X. Write Rt(s) for the tag associated to the root of s (so Rt(Иa, b.(Иc, a.U, V )) = {a, b}).

Write (Γ, σ) ≤ (Γ′, σ′) when there exists a substitution σ′′ such that Γ′ ⊢ Γσ′′, Γ′ ⊢σ ◦σ′′ ≈α σ′ and Rt(Xσ) ⊆ Rt(Xσ′) for every X. We see that this defines a partial order on solutions (sometimes called instantiation ordering). Say a solution to a problem is principal when it is smaller than or equal to all other solutions to that problem. A solution (Γ, σ) is idempotent when Γ ⊢σ ◦σ ≈α σ.

We will show below that every solvable unification problem has a principal idempotent solution, and give an algorithm to find it.

The simplification rules given in the previous section can be adapted to solve unification problems: we need to add instantiating rules, labelled with substitutions.

И∅.π·Y ?≈?И∅.s, PrY↦ →π−1·s=⇒ Pr[Y↦ →π−1·s] (Y ∉s)

И∅.l ?≈?И∅.π·X, PrX↦→π−1·l=⇒ Pr[X↦→π−1·l] (X ∉l)

The conditions in the rules are usually called occurs check.

Note that we do not intend to solve apartness or scope constraints. Indeed, to solve apartness and scope constraints we need instantiating rules for these predicates too. Instead, we will solve the equalities in a problem, and require that the solution satisfy the apartness and scope constraints in the problem. This is what we need in rewriting.

We will use the set of simplification rules given in the previous section (where we replace ≈α by ?≈?), together with the instantiation rules, as a unification algorithm.

Lemma 4.1

The unification rules are confluent and strongly normalising.

Proof

Standard: at each step either the number of unsolved variables X in the problem decreases, or a non-reduced constraint simplifies towards reduced constraints.End of proof

To solve a problem Pr, we will apply the rules until we obtain an irreducible problem. We write ⟨Pr⟩sol = (Pr′, σ) if Pr′ is the (unique) normal form of Pr using the unification rules, and σ is obtained by concatenating the labels in some reduction sequence from Pr to Pr′. We can characterise the normal form Pr′ of Pr under the unification rules:

Lemma 4.2

(Unification Normal Forms). ⟨a#s⟩sol consists of reduced freshness constraints and ⟨a@s⟩sol consists of reduced scoping constraints. ⟨s?≈? t⟩sol may contain any mixture of reduced freshness constraints, reduced scoping constraints, and clashing equalities such that if one side is a variable the other side contains this variable.

Proof

Similar to Lemma 3.6: Any non-reduced freshness or scoping constraint or non-clashing equality can be simplified as previously. Clashing equalities of the form π·X ?≈? t or t ?≈? π·X where X ∉V(t) can be reduced using an instantiation rule.End of proof

Therefore we can decompose ⟨Pr⟩sol as a triple (∆, Eq, σ) where ∆is a context, Eq a set of equations, and σ a substitution.

We will show that the unification algorithm correctly checks whether a problem is solvable or not, and moreover it computes a principal, idempotent solution, if one exists. In the proof we will use the following lemmas:

Lemma 4.3

1. Let Eq be a non-empty set of unification constraints in normal form. Then Eq has no solution.

2. Let ∆ be an inconsistent context. Then ∆ has no solution.

Proof

By Lemma 4.2, the equalities in Eq are clashing or fail the occur check. Since no consistent context can entail an instance of such an equality, Eq is not solvable.

The second part is directly by definition of solution, and the fact that from a consistent context we cannot derive an inconsistent one.End of proof

Lemma 4.4

(π·t)σ ≡π·(tσ).

Proof

π acts top-down and accumulates on moderated variables. σ acts bottom up on the variable symbols in the moderated variables. The two operations commute. A formal proof is easy by induction on syntax.End of proof

Lemma 4.5

If ∆⊢ (π·X)σ ≈α tσ then ∆⊢ [X↦→π−1·t] ◦ σ ≈α σ.

Similarly, if ∆⊢sσ ≈α (π·Y )σ then ∆⊢[Y↦ →π−1·s] ◦ σ ≈α σ.
Proof

Suppose ∆ ⊢ (π·X)σ ≈α tσ and write σ′ for [X↦→π−1·t] ◦σ. We simplify Xσ′ up to ≈α in the context ∆;

Xσ′ ≈α (π−1·t)σ ≈α π−1·(tσ) ≈α π−1·((π·X)σ) ≈α π−1 ◦π·(Xσ) ≈α Xσ.

(We make heavy use of the previous lemma to rearrange the brackets.) The second part is similar.End of proof

Lemma 4.6

(Preservation of solutions). Assume

Prθ=⇒Pr′.

1. If (Γ, σ) ∈U(Pr) then (Γ, σ) ∈U(Pr′) and Γ ⊢θ ◦ σ ≈α σ.

2. If (Γ, σ) ∈U(Pr′) then (Γ, θ ◦σ) ∈U(Pr).

Proof

The first part follows from the previous lemma. For the second part, suppose Γ ⊢Pr′σ and suppose θ = [X↦→π−1·s] so that ({s ≈α s} ∪Pr′) = Pr[X↦→π−1s]. It is easy to verify that Γ ⊢s ≈α s, so Γ ⊢Pr(θ ◦σ).End of proof

Corollary 4.7

Let Pr be a unification problem, and ⟨Pr⟩sol = (∆, Eq, σ).

U(Pr) ≠ ∅ if and only if ∆ is a consistent context and Eq = ∅.

Proof

By induction on the length of the derivation Pr∗=⇒ ⟨Pr⟩sol. We use Lemma 4.3 and Lemma 4.6 part 1 for the “only if”, and Lemma 4.6 part 2 for the “if”.End of proof

Lemma 4.8

If ⟨Prσ⟩nf = ∆ then ⟨Pr⟩nf = Pr′ and ⟨Pr′σ⟩nf = ∆ for some Pr′.

If ⟨Pr⟩sol = (∆, ∅, σ) then ⟨Prσ⟩nf = ∆.
Proof

The first part is a consequence of the confluence of =⇒.

The second part can be proved by induction on the derivation Pr∗=⇒⟨Pr⟩sol. A step π·X ?≈? t, PrX↦→π−1·t=⇒ Pr[X↦→π−1·t] is replaced by t ≈α t, Pr[X↦→π−1·t] ∗=⇒Pr[X↦→π−1·t].End of proof

Theorem 4.9

(Principality). Let Pr be a unification problem, and ⟨Pr⟩sol = (∆, ∅, σ) such that ∆ is a consistent context.

1. (∆, σ) ∈U(Pr), and

2. if (Γ, σ′) ∈U(Pr) then (∆, σ) ≤ (Γ, σ′).

Proof

For the first part, note that (∆, Id) ∈U(∆) if ∆ is a consistent context. Hence by Lemma 4.6 (and induction) (∆, σ) ∈U(Pr).

For the second part, if (Γ, σ′) ∈U(Pr) then:

• Γ ⊢σ◦σ′ ≈α σ′, by Lemma 4.6 part 1 (and induction). Note in particular that Γ ⊢σ ◦σ ≈α σ, that is, σ is idempotent.

• Γ ⊢Prσ′ by definition of solution, and Γ ⊢⟨Prσ′⟩nf by Corollary 3.9. Also, Γ ⊢⟨Prσ′⟩nf ≈α ⟨Pr(σ ◦σ′)⟩nf = ⟨(Prσ)σ′⟩nf, and by Lemma 4.8 part 2, ⟨Prσ⟩nf = ∆. Therefore, by Lemma 4.8 part 1, ⟨∆σ′⟩nf = ⟨(Prσ)σ′⟩nf, and we get Γ ⊢⟨∆σ′⟩nf. Hence Γ ⊢∆σ′ by Corollary 3.9.

• Finally, Rt(Xσ) ⊆ Rt(Xσ′) for every X since σ is created by the instantiation rules with empty tags.

Therefore (∆, σ) is a principal and idempotent solution.

End of proof

5. REWRITING

5.1 Matching problems

Given terms-in-context ∇⊢l and ∆ ⊢s such that V(∇, l)∩ V (∆, s) = ∅, a matching problem between them is the pair (∇⊢l, ∆⊢s). We write it (∇⊢l) ?≈(∆⊢s). The solution to this matching problem, if it exists, is a pair (∆′, θ) which is a principal solution in the sense of the last section to the unification problem ∇, l ?≈? s, such that

• Xθ ≡X for X ∈V (∆, s) and

• ∆⊢∆′, lθ ≈α s is derivable.

• ∆⊢∇θ is derivable.

The first condition ensures that our solution is a matching. The second condition controls when l matches with s. The third condition controls when the conditions ∇ are satisfied. When this third condition is satisfied we say the matching is triggered. (Soon, ∇⊢l will be the left-hand of a rewrite rule ∇⊢l →r, and then we say the rule is triggered.)

For example: (⊢Иa.a) ?≈ (⊢Иb.b) has no solution; (⊢ Иb.b) ?≈ (⊢Иb.b) has a solution θ = Id; and (⊢Иa, b.X′) ?≈ (⊢Иb, a.X) has solution θ = [X′↦→X]. All of the following problems have solution (a@X, [X′↦→X]):

(⊢Иa.X′) ?≈(a#X⊢X) (⊢X′) ?≈(a#X⊢Иa.X) (⊢X′) ?≈(a@X⊢Иa.X)

See [14] for more examples.

5.2 Rewrite rules

A(n extended) rewrite rule R ≡∇⊢l →r is a tuple of a consistent context ∇, and extended terms l and r such that V(r, ∇) ⊆V(l).

Suppose R = ∇⊢l →r is a rewrite rule, s and t are terms, and ∆is a context. We say s rewrites with R to t in the context ∆, and we write ∆ ⊢sR→t when:

1. V(R) ∩V (∆, s) = ∅ (we can assume this with no loss of generality).

2. There exists a position (p, A) in s and a matching solution (∆′, θ) to (∇⊢l) ?≈(∆⊢s|p,A).

3. ∆⊢s[rθ]p,A ≈α t.

This is essentially the same definition as for (unextended) nominal rewriting [14], modulo slight changes to account for the tags.

Write R(a b) for that rule obtained by swapping a and b in R throughout. For example, if R ≡b@X ⊢ [a]X → Иb.(a b)·X then R(a b) ≡a@X ⊢ [b]X →Иa.(b a)·X. Say a set of rewrite rules is equivariant when it is closed under ∗(a b) for all atoms a and b.

A rewrite system R is an equivariant set of rewrite rules. A set of rewrites gives rise naturally to a rewrite system by closing under equivariance. We shall elide this step, saying ‘R has the rewrite blah’ to mean ‘the rewrite system obtained by closing R under equivariance has the rewrite blah’. This usage is established [14].

We now consider some simple examples, and give applications of extended nominal rewriting in the following subsection.

• The rewrite system a →a has the rewrites n →n for any n. This is because of equivariance: if a →a ∈R then so is n →n for any n. It also has the rewrite Иa.a →Иa.a, using position (ϵ, {a}).

• The rewrite system a →Иa.a has the rewrites a → Иa.a and also Иa.a →Иa.a.

• The rewrite system [a]X →Иa.X has the rewrite [a]X →Иa.X. It also has the rewrite b#X ⊢ [a]X → Иb.(b a)·X. This is because b#X ⊢ [a]X ≈α [b](b a)·X. The following is an important correctness result:

Theorem 5.1

If ∆⊢sR→t then ∆⊢C[s] R→C[t].

Proof

By unpacking the definition of rewriting.End of proof

5.3 Applications

Modelling name generation in the π-calculus.

A reaction system for an asynchronous π-calculus is given by the signature

in, out, par, rep, ν

and the following rewrite rules, where we abbreviate par(s, t) as (s | t), in(a, [c]t) as a[c].t, out(a, b) as ab and rep(t) as !t to get the standard π-calculus notation. We assume par is associative and commutative, and work modulo a structural congruence as usual; the details are omitted since they are not relevant to this paper.

ab | a[c].Y →Y {c↦→b} ν[c]X →Иc.X !X →!X | Xa#P ⊢P | (Иa.Q) →Иa.(P | Q).

Here {c↦→b} is an explicit substitution with reactions including (X | Y){c↦→b} →X{c↦→b} | Y {c↦→b} and (ν[a]X){c↦→b} → ν[a](X{c↦→b}).

Call the last rule the scope extrusion rule, the first rule the reaction rule, and the second rule the name-generation rule. Let us consider the name-generation and scope extrusion rules and demonstrate in the context of extended nominal rewriting why they have these names.

Note that c is abstracted in ν[c]X. Nominal rewriting, including the extension in this paper, works on terms up to provable α-equivalence; thus if ∆ ⊢ν[c]R →Иc.R is a valid rewrite and ∆ ⊢d#R is deducible, then ∆ ⊢ν[d](d c)·R → Иd.(d c)·R is a valid rewrite. Thus, the name-generation rule ‘generates a fresh d’. И defines the scope of d and the scope extrusion rule allows us to extend it.

The fly in our ointment is that the scope extrusion rules do not allow renaming a scoped name (d, for example) to a ‘fresher’ d′ such that, say, d′#P is provable where d#P was not. This is known as name-clash and it is ‘unfair’ since we could always have chosen d′ originally.

We can add a freshening rewrite rule

F ≡b#P ⊢Иa.P →Иb.(b a)·P (1)

to allow post-factum renaming. A weaker alternative is to strengthen the scope extrusion rules:

b#P, Q ⊢P | (Иa.Q) →Иb.(P | (b a)·Q)

(‘Weaker’, because we get rewrites of the transitive closure of F with the original scope extrusion rules, but not quite all of them.)

Name generation in Pitts and Starks’s ν-calculus.

A reaction system for Pitts and Starks’s ν-calculus [32] is

(λ[a]X)Y →X{a↦→Y } ν[a]X →Иa.X.

Again, {a↦→Y } is an explicit substitution. Reaction rules include a#Y ⊢ (λ[a]X){b↦→Y } →λ[a](X{b↦→Y }) and a#Y ⊢ (ν[a]X){b↦→Y } →ν[a](X{b↦→Y }).

As in the implementation of the π-calculus above we have faithfully modelled abstraction in the syntax by abstraction in the rewrite system; for example a is abstracted in λ[a]s and ν[a]s. We consider alternatives in the Conclusions.

Rewriting is a little too weak in its treatment of scoped atoms, because they cannot be renamed to avoid name-clash. Accordingly, we shall base our theory of confluence on rewriting in the presence of rule F from (1). We shall see this rule has a non-trivial and delicate interaction with the definitions we have set up so far, giving us precisely what we want.

6. CONFLUENCE

6.1 Uniform rewrite rules

We shall give a well-behavedness condition on rewrite rules which we call uniformity, but first we prove properties of ⊢ which give uniformity its power.

Lemma 6.1

• If ∆⊢Pr and ∆, ⟨Pr⟩nf ⊢Pr′ then

∆⊢Pr′.

• If ∆, ⟨a#s⟩nf ⊢a#t then ∆, ⟨a#C[s]⟩nf ⊢a#C[t]. Similarly for @.

• If ∇⊢a#l then ⟨∇σ⟩nf ⊢a#lσ. Similarly for @.

Proof

• By Corollary 3.9, if ∆⊢Pr then ∆ ⊢ ⟨Pr⟩nf. We modify the deduction of ∆, ⟨Pr⟩nf ⊢Pr′ to replace any use of assumptions in ⟨Pr⟩nf with a (part of) the deduction of ∆ ⊢⟨Pr⟩nf.

• We work by induction on C, write X for the ‘hole’ in C. We consider three interesting representative cases. If C ≡a then ⟨a#C[s]⟩nf is a#a and ∆, ⟨a#a⟩nf ⊢a#a trivially. If C ≡ (a, X) then a#a ∈⟨a#C[s]⟩nf so ∆, ⟨a#C[s]⟩nf ⊢⟨a#C[t]⟩nf by (#⊥). If C ≡ [a]X then ⊢a#C[t] is easily derivable.

• By induction on s using the highly syntax-directed nature of the deduction rules, and using the first part.

End of proof

Part 1 of the lemma above is a very thinly disguised Cut. Part 2 is, we think, rather striking. Part 3 is perhaps less surprising.

Say a rule R ≡∇⊢l →r is uniform when ∇, ⟨a@l⟩nf ⊢ a@r for all a. Examples of uniform rules are:

[a]X →Иa.X a#X ⊢Иa.X →X a@X ⊢Иa.X →Xa →a a →Иb.b

For example consider a →a. c@a ⊢c@a for all c ≢a, and a@a ⊢a@a by (@⊥). Consider a →Иb.b. x@a ⊢x@Иb.b is provable for x ≡a by (@⊥), for x ≡b, and for x ∉{a, b}. Examples of rules that are not uniform are:

[a]X →XИa.X →X a →b

If (1) R is an equivariant set of uniform rewrite rules and

(2) F ∈R then call R uniform. Henceforth, fix some uniform set of rewrite rules.

Lemma 6.2

If ∆⊢s →t then ∆, ⟨a@s⟩nf ⊢a@t and ∆, ⟨a#s⟩nf ⊢a@t for all a.

Proof

If ∆⊢s →t then for some R ≡∇⊢l →r ∈R there is some position (p, A) in s and substitution σ such that ∆ ⊢∇σ and ∆ ⊢s|p,A ≈α lσ.

By the definition of uniformity, ∇, ⟨a@l⟩nf ⊢a@r. By the first and third parts of Lemma 6.1, ∆, ⟨a@lσ⟩nf ⊢a@rσ. By the second part of that same result, ∆, ⟨a@s⟩nf ⊢a@t. We use similar reasoning to deduce ∆, ⟨a#s⟩nf ⊢a@t, only we use the first part of that lemma again, and Lemma 3.1.End of proof

In fact, we can prove something rather stronger, if we assume the context can allow us to deduce enough freshness information. Say ∆ has enough fresh atoms with respect to some finite set of atoms A and finite set of unknowns V when there exists a set of atoms A′ with at least as many elements as A such that A∩A′ = ∅ and ∆ ⊢a′#X for every a′ ∈A′ and X ∈V .

Lemma 6.3

If ∆⊢s →t then there is a t′ such that

∆⊢s →tF→∗t′, ∆, ⟨a@s⟩nf ⊢a#t′ and ∆, ⟨a#s⟩nf ⊢a#t′ for all a ∈s, provided that ∆ has enough fresh atoms with respect to the atoms and variables in s, t.

Proof

As for the last lemma but using rule F to freshen atoms as illustrated in the example below.End of proof

For example, using the notation of this lemma: consider a uniform rewrite system with the trivial rewrite rule ∅⊢ X →X (which is uniform). If s ≡Иa.X and ∆ ≡b#X (which has enough fresh atoms for a and X, namely b) then t =Иa.X and t′ =Иb.(b a)·X.

Henceforth we suppose ∆provides us with all the fresh atoms we need. In the case of finite terms and finite sequences of rewrites, if we run out we can always try again with a larger ∆.

6.2 Critical Pairs

Fix a rewrite system R. Write ∆ ⊢s →t1, t2 for the appropriate pair of rewrite judgements. Call a valid pair ∆⊢s →t1, t2 a peak. Suppose

1. Ri = ∇i ⊢li →ri for i = 1, 2 are copies of two rules in R such that V(R1) ∩V(R2) = ∅ (R1 and R2 could be copies of the same rule).

2. (p, A) is a position in l1.

3. l1|p,A ?≈? l2 has solution (Γ, θ) so Γ ⊢l1|p,Aθ ≈α l2θ.

4. ⟨∇iθ⟩nf is consistent for i = 1, 2; write ∇′ i respectively.

Then call the pair of terms-in-context

∇′ 1, ∇′ 2, Γ ⊢(r1θ, l1[r2θ]p,A)

a critical pair. If (p, A) = (ϵ, ∅) and R1, R2 are copies of the same rule, or if (p, A) is the position of a variable in l1 then we say the critical pair is trivial.

The condition ⟨∇iθ⟩nf be consistent is important. b#X ⊢ f(X) →X and ⊢f(b) →c do not generate a peak; f(X) ?≈? f(b) does have a solution (∅, [X↦→b]), but ⟨b#f(b)⟩nf = {b#b} is not consistent.

Say a uniform nominal rewrite system R is locally confluent when if ∆ ⊢s →t and ∆ ⊢s →t′, then u exists such that ∆ ⊢t →∗u and ∆ ⊢t′ →∗u. We say such a peak is joinable.

Say a uniform nominal rewrite system is confluent when if ∆⊢s →∗t and ∆ ⊢s →∗t′, then u exists such that ∆⊢t →∗u and ∆ ⊢t′ →∗u.

Trivial critical pairs are not necessarily joinable in NRSs. For instance with rules

b#X ⊢(X, b) →c and f(a) →b

the trivial critical pair (c, (b, b)) obtained by unifying f(a) with b#X ⊢X is not joinable. We obtain exactly the same phenomenon with the condition b@X replacing b#X in this example.

The following result is the reason we consider uniform rules and use rule F from (1):

Lemma 6.4

In a uniform rewrite system trivial critical pairs are joinable.

Proof

Suppose there is a trivial critical pair

∇′ 1, ∇′ 2, Γ ⊢(r1θ, l1[r2θ]p,A)

between rules Ri = ∇i ⊢li →ri for i = 1, 2, where (p, a) is the position of a variable in l1.

The only reason we might not be able to apply R1 in l1[r2θ]p,A is if some freshness or scope condition in ∇1 is unsatisfiable after R2, which was satisfiable before R2. For uniform rules, Lemma 6.3 guarantees that this cannot happen (up to rule F): we can always rewrite r2θ using F and then apply R1. Therefore the critical pair is joinable.End of proof

This is the reason we are interested in critical pairs:

Theorem 6.5

(Critical Pair Lemma). If all nontrivial critical pairs of a uniform nominal rewrite system are joinable, then it is locally confluent.

Proof

Suppose ∆ ⊢s →t1 and ∆ ⊢s →t2 is a peak (and as usual assume the context has enough fresh atoms). Then:

1. There exist Ri = ∇i ⊢li →ri and positions pi, Ai in s, for i = 1, 2.

2. There exist solutions σi to (∇⊢ (s[li]pi,Ai, s[ri]pi,Ai)) ?≈ (∆⊢ (s, ti)) for i = 1, 2.

Now there are two possibilities:

1. p1 and p2 are in separate subtrees. Local confluence holds by a standard diagrammatic argument taken from the first-order case [2]. We need Corollary 3.4 to account for the weaker notion of equality.

2. p1 is a prefix of p2 or vice versa, we consider only the first possibility. Suppose that p1 = ϵ, the general case follows using Corollary 3.4. There are two possibilities: Either this is a non-trivial critical pair, joinable by assumption, or it is a trivial critical pair, we use Lemma 6.4

End of proof

In fact, we need to study rule F a little more closely, to deal with two problems, before tying up the results with the Corollary below.

We call a critical pair F -trivial if it is either trivial in the sense defined above, or if at least one of the rewrites is F.

Problem 1. Rule F has (F -trivial) critical pairs with any rule ∇⊢l →r in which l mentions tags, simply because F can freshen them. Solution. The following lemma implies that F -trivial critical pairs are always joinable:

Lemma 6.6

If ∆⊢sF→s′ then ∆⊢s′F→s (rule F is reversible).

Proof

By calculations involving the following easily-verified technical fact b#s ⊢ (a b)·(b c)·s ≈α (a c)·s.End of proof

So we can strengthen the critical pair lemma to only check joinability of critical pairs that are not F -trivial. We may be lax and just say ‘trivial’ and ‘nontrivial’ for ‘F -trivial’ and ‘not F -trivial’, e.g. in the corollary below.

Problem 2. R is necessarily nonterminating because F can be applied to any term with a tag, forever (given enough fresh atoms). Solution. R gives rise to an F ∗-abstract rewrite system obtained from R but counting one or more instances of F in sequence as one F ∗-abstract rewrite (we count F→∗ as a single ‘abstract’ rewrite step). Say R is terminating up to F ∗ when its F ∗-abstract rewrite relation is terminating. By Newman’s Lemma [29] we can deduce confluence of a locally confluent and F ∗-terminating uniform rewrite system. We may be lax and write ‘terminating’ for F ∗-terminating.

Corollary 6.7

Fix a uniform nominal rewrite system.

1. If nontrivial critical pairs are joinable then it is locally confluent.

2. If it is in addition terminating then it is confluent, and every term has a unique normal form modulo ≈α and rewrites with F.

This result holds of rewrite systems in the previous sense

[14], which are the special case of the system here without И.

6.3 Orthogonal Systems

We now treat a standard confluence criterion in rewriting theory [13, 23] (see also [24, 27]).

Say a rule R ≡∆⊢l →r is left-linear when each variable occuring in l occurs only once. For example, a#X, b#X ⊢ X → (X, X) is left-linear but ⊢ (X, X) →X is not.

We say a uniform, nominal rewrite system with only left-linear rules and no non-trivial critical pairs is orthogonal.

Theorem 6.8

An orthogonal uniform nominal rewrite system is confluent.

The proof occupies the rest of this section. Henceforth, we only consider uniform rewriting.

We define a parallel reduction relation as follows:

∆⊢s F→∗t(refl)∆⊢s ⇒t∆⊢(si ⇒ti)1≤i≤n(tup)∆⊢(s1, . . . , sn) ⇒(t1, . . . , tn) ∆⊢(si ⇒ti)1≤i≤n∆⊢(t1, . . . , tn)Rϵ→F→∗u(tup’)∆⊢(s1, . . . , sn) ⇒u
∆⊢s ⇒t(abs)∆⊢[a]s ⇒[a]t∆⊢s ⇒t ∆⊢[a]tRϵ→F→∗u(abs’)∆⊢[a]s ⇒u
∆⊢ИA.sFϵ→∗ИA′.s′∆⊢s′ ⇒t′∆⊢ИA′.t′ Fϵ→∗ИB.t(new)∆⊢ИA.s ⇒ИB.t∆⊢ИA.sFϵ→∗ИA′.s′∆⊢s′ ⇒t′∆⊢ИA′.t′ Fϵ→∗Rϵ→F→∗u(new’)∆⊢ИA.s ⇒u
∆⊢s ⇒t(fun)∆⊢fs ⇒ft∆⊢s ⇒t ∆⊢ftRϵ→F→∗u(fun’)∆⊢fs ⇒u

We have used some new notation: ∆ ⊢sRϵ→t means ‘s rewrites to t using R at position ϵ, ∅’. In the case of rule F, ∆⊢sFϵ→t means s rewrites to t using F at position ϵ, A, for some A.

In Lemma 6.11 we say an instance of (tup’), (abs’), (new’), or (fun’) is for R when it uses that rule.

Lemma 6.9

F→∗⇒F→∗⊆⇒.

Proof

By induction on the derivation of ⇒. The interesting cases are (new) and (new’); we use the technical fact from the proof of Lemma 6.6.End of proof

In a proof we are about to give, we shall have obtained t and u such that t ⇒u, and we shall say that we assume the atoms in u are ‘sufficiently fresh for blah’. We mean that we choose a ⇒ rewrite such that atoms in u are chosen fresh enough not to clash with certain background assumptions in that proof.

Lemma 6.10

If ∆⊢s →t then ∆⊢s ⇒t, and if ∆⊢s ⇒t then ∆⊢s →∗t. As a corollary, ∆⊢s ⇒t if and only if ∆⊢sR→∗t.

Proof

By induction on the position of the rewrite, and by induction on the derivation of ⇒.End of proof

Lemma 6.11

If the system is uniform and orthogonal then ⇒ is strongly confluent: if ∆⊢s ⇒t and ∆⊢s ⇒t′, then there exists some u such that ∆⊢t ⇒u and ∆⊢t′ ⇒u. Hence ⇒ is confluent.

Proof

By induction on the derivation of ∆ ⊢s ⇒t. We consider one case. Suppose the derivation ends in (tup). By the syntax-driven nature of deduction there are three possibilities for the last rule in the derivation of ∆ ⊢s ⇒t′: (tup), (tup’), and (refl):

(1) If ∆⊢s ⇒t′ has a derivation ending in (tup) then the inductive hypothesis for ∆ ⊢si ⇒ti and ∆ ⊢si ⇒t′ i give us ui such that ∆ ⊢ti ⇒ui and ∆ ⊢t′ i ⇒ui. We use (tup) and are done.

(2) If ∆⊢s ⇒t′ has a derivation ending in (tup’) for R ≡∇⊢l →r, that is ∆ ⊢s ⇒ (t′ 1, . . . , t′ n) and ∆ ⊢ (t′ 1, . . . , t′ n) Rϵ→F→∗t′, then θ exits such that

∆⊢∇θ, (t′ 1, . . . , t′ n) ≈α lθ, rθF→∗t′.

We now proceed as illustrated and explained below:

(s1, . . . , sn) (t′ 1, . . . , t′ n)≈αlθRϵrθF∗t′(t1, . . . , tn)(u1, . . . , un) ≈αlθ′Rϵrθ′

We apply the inductive hypothesis to close ∆ ⊢ti, t′ i ⇒ui, using Lemma 6.9 (F→∗⇒F→∗⊆⇒) to ensure the tags in ui are sufficiently fresh that Lemma 6.10 (→∗=⇒) and Lemma 6.3 can be used to deduce of ui all freshness and locality assumptions deducible of t′ i.

Since rules are left-linear R still applies: ∆ ⊢ (u1, . . . , un) Rϵ→ rθ′ and ∆ ⊢ (t1, . . . , tn) ⇒rθ′ by (tup) for R (for some substitution θ′). Finally, we use orthogonality, Lemma 6.9, and Lemma 6.6 (F is reversible) to close with a rewrite t′ ⇒rθ′.

(3) If ∆⊢s ⇒t′ is derived using (refl) then trivially s ≡t′ and ∆ ⊢t′ ⇒t using the same rules as were used to derive ∆ ⊢s ⇒t, and ∆ ⊢t ⇒t is derivable using (refl).

The other cases are similar; the case of (new) and (new’) uses the lemma below.End of proof

We now come back to our theorem:

Proof

If the uniform rewrite system has only left-linear rules and no non-trivial critical pairs, then ⇒ is confluent by Lemma 6.11. Since →∗⊆⇒ and →⊆→∗ by Lemma 6.10, → is confluent.End of proof

7. EXTENSIONS: CLOSED, AND IS-IN

We will now show that, thanks to the use of contexts, the framework of nominal rewriting can be easily adapted to express strategies of rewriting. As an example, we will show how to define in this framework the system λca of closed reduction for the λ-calculus [16]. λca-terms are λ-terms with explicit constructs for substitutions, copying and erasing. Reduction on λca is defined in [16] using a set of conditional rule schemes, shown in Table 1, where x, y, z denote variables, and t, u, v denote terms.

Table 1: λca-reduction

Name Reduction ConditionBeta (λx.t)v →cat[v/x] FV (v) = ∅Var x[v/x] →cavApp1 (tu)[v/x] →ca(t[v/x])u x ∈FV (t)App2 (tu)[v/x] →cat(u[v/x]) x ∈FV (u)Lam (λy.t)[v/x] →caλy.t[v/x]Copy1 (δy,z x .t)[v/x] →cat[v/y][v/z]Copy2 (δy,z x′ .t)[v/x] →caδy,z x′ .t[v/x]Erase1 (ϵx.t)[v/x] →catErase2 (ϵx′.t)[v/x] →caϵx′.t[v/x]

We can formally define λca using a nominal rewriting system, where we add two new kinds of constraints: •t (read t is closed), with the intended meaning “a#t for every atom a”, and a ∈t (read a is unabstracted in t), the negation of a#t.

We extend the deduction and simplification rules from section 3 respectively with:

(∆⊢a#t)a∈S (•R) A(t, ∆) ⊊S ∆⊢•t •t, Pr =⇒{a#t}a∈P r,t, a′#t, Pr

Here S is any set of atoms strictly containing the atoms in t and ∆. In effect we need A(t, ∆) and one fresh atom; if ∆ ⊢ a#t for a ∉A(t, ∆) a renaming argument gives ∆ ⊢b#t for all other b ∉A(t, ∆). This is reflected in the simplification rule, which is more algorithmic and chooses one fresh atom.

•t is intuitively ∀a. a#t. The rule for closure •t is slightly different from the usual predicate logic rule for ∀ because atoms behave here as constants and not variables. With that in mind the definitions are quite natural. We can extend the deductions with rules including

a ∈tia ∈(t1, . . . , tn)a ∈aa ∈t a ∈Иa.t

and similarly extend the simplification rules. We can extend contexts with these new constraints and use them in ∇s of rewrite rules ∇⊢l →r to control triggering.

A closed reduction strategy can be specified, this time as a finite nominal rewrite system (we only show rules Beta, App1 and App2):

Beta •V ⊢(λ[x]T)V →caT[V/x]App1 x ∈T ⊢(TU)[V/x] →ca(T[V/x])UApp2 x ∈U ⊢(TU)[V/x] →caT(U[V/x])

8. CONCLUSIONS AND FUTURE WORK

The technical foundations of this work are derived from work on nominal logic [31] and nominal unification [36]. Nominal rewriting was presented in [14]. Here we extended nominal terms and the nominal unification algorithm with a new construct to model scope of names. We also showed that the nominal rewriting framework can be easily adapted to model reduction strategies: the context used to trigger rules allows us to express in a natural way constraints in the application of the rules.

There is interest in extending Structural Operational Semantics with abstraction and name-generation and Nominal Rewriting could provide (yet another!) forum for it. The authors have considered efficient implementation of И; there is no space here (we treated orthogonality instead) but the issue needs to be addressed for implementability. We have shown how rewriting can be extended with contexts (in the case of this paper, #, ∈, and •; other constraints can be added to model other domains) and annotations on terms (ИA), and we have shown how to retain classic properties of first-order rewriting (in this case, critical pairs and orthogonal rewriting results). We can encode useful structure in rules (name abstraction and generation, and rewrite strategies). It should be possible to consider different extensions, using the same idea of rewriting-in-context.

Abstraction vs. И.

In conclusion we would like to ask: What are the properties of name-abstraction versus those of name-generation? The theory of ≈α for name-abstraction is generated by a#[a]X and a#X, b#X ⊢X ≈α (a b)·X. The theory of ≈α for name-generation is generated by a@Иa.X and a#X ⊢X ≈α Иa.X. (This statement could easily be made formal.)

It is certainly not the case that a#X ⊢X ≈α [a]X. It is also not the case that a@X, b@X ⊢X ≈α (a b)·X. (Though rule F gives us something similar, by allowing us to rename tagged atoms.) So abstraction and name-generation are different. How do they interact in our system?

И and abstraction are independent in that neither depends on the other for its construction. They coexist in our system with quite subtle interactions. The relevant results are: # implies @ by Lemma 3.1, which comes down to a deduction rule (#@). @ implies # indirectly through Lemma 6.3, which comes down to a rewrite rule F.

Indeed equality itself is rather subtle; it is constructed in layers starting with ≡, syntactic identity an intrinsic property of terms, then ≈α defined using a context and handling abstraction [a]s, and finally rule F which is built into the rewriting and deals with И (as we see from Lemma 6.3 and the final parts of §6.2 and §6.3). Finding these different layers, and understanding their interactions, were the authors’ principal technical difficulties designing the system.

Can И model abstraction, or vice versa? Abstraction cannot directly model И, because И does not abstract and of course abstraction does. The converse does not hold, since И with α-renaming rules could model the abstraction part of abstraction, but we still have a@X ⊢X ≈αИa.X, which abstraction should not satisfy.

Recall our reaction systems for the π-calculus and the ν-calculus from §5.2. We used abstraction to model the π-calculus term νa. P as ν[a]P because the a is normally considered α-convertible in the π-calculus literature. But in fact we could have used И directly and saved ourselves the rewrite ν[a]X →Иa.X:

ab | a[c].Y →Y {c↦→b} !X →!X | Xa#P ⊢P | (Иa.Q) →Иa.(P | Q)a#Q ⊢(Иa.P) | Q →Иa.(P | Q).

We cannot model the λ-calculus ‘abstract a in t’ as λИa.t, since λИa.b ≈α λb is provable. We can model νa. t in the ν-calculus with И as νИa.t, the reaction is (λ[a]X)Y → X{a↦→Y }.

9. REFERENCES

[1] M. Abadi, L. Cardelli, P-L. Curien, and J-J. Lévy, Explicit substitutions, Journal of Functional Programming 1 (1991), no. 4, 375–416.

[2] F. Baader and T. Nipkow, Term rewriting and all that, Cambridge University Press, 1998.

[3] F. Barbanera, M. Fernández, and H. Geuvers, Modularity of strong normalization in the algebraic-λ-cube, Journal of Functional Programming 6 (1997), 613–660.

[4] H. P. Barendregt, Pairing without conventional constraints, Zeitschrift für mathematischen Logik und Grundlagen der Mathematik 20 (1974), 289–306.

[5] C. Bertolissi, H. Cirstea, and C. Kirchner, Translating combinatory reduction systems into the rewriting calculus, RULE 2003, Valencia, Spain, 2003.

[6] E. Bonelli, D. Kesner, and A. Ríos, From higher-order to first-order rewriting, LNCS vol. 2051, 2001.

[7] V. Breazu-Tannen and J. Gallier, Polymorphic rewriting conserves algebraic strong normalization, Theoretical Computer Science 83:1 (1991).

[8] V. Breazu-Tannen and J. Gallier, Polymorphic rewriting conserves algebraic confluence, Information and Computation 82 (1992), 3–28.

[9] J. Cheney, The complexity of equivariant unification. Proceedings of ICALP 2004, LNCS, 2004.

[10] H. Cirstea and C. Kirchner, The Rewriting Calculus - Part I, Logic Journal of the Interest Group in Pure and Applied Logics 9 (2001), 363–399.

[11] H. Cirstea and C. Kirchner, The Rewriting Calculus - Part II, Logic Journal of the Interest Group in Pure and Applied Logics 9 (2001), 401–434.

[12] R. David and B. Guillaume, A λ-calculus with explicit weakening and explicit substitution, Mathematical Structure in Computer Science 11(1) (2001), 169–206.

[13] N. Dershowitz and J.-P. Jouannaud, Rewrite Systems, Handbook of Theoretical Computer Science: Formal Methods and Semantics, vol. B, 1989.

[14] M. Fernández, M. J. Gabbay and I. Mackie,Nominal Rewriting Systems, ACM Symposium on Principles and Practice of Declarative Programming (PPDP’04), ACM Press, 2004.

[15] M. Fernández and J-P. Jouannaud. Modular Termination of Term Rewriting Systems Revisited. ADT’94, LNCS 906, 1994.

[16] M. Fernández, I. Mackie and F-R. Sinot, Closed Reduction: Explicit Substitutions without alpha-conversion, MSCS 2005 (to appear).

[17] M. J. Gabbay, The π-calculus in FM, Thirty-five years of Automath (Fairouz Kamareddine, ed.), Kluwer, 2003.

[18] M. J. Gabbay and A. M. Pitts, A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, vol. 13, pp. 341–363, 2002.

[19] M. Hamana, Term rewriting with variable binding: An initial algebra approach, PPDP 2003.

[20] J.-P. Jouannaud and C. Kirchner, Solving equations in abstract algebras: a rule based survey of unification, Computational Logic: Essays in Honor of Alan Robinson, 1991.

[21] J.-P. Jouannaud and M. Okada, Executable higher-order algebraic specification languages, 6th IEEE Symposium on Logic in Comp. Sci., 1991, pp. 350–361.

[22] Z. Khasidashvili, Expression reduction systems, Proceedings of I.Vekua Institute of Applied Mathematics (Tbisili), vol. 36, 1990, pp. 200–220.

[23] J.-W. Klop, Term Rewriting Systems, Handbook of Logic in Computer Science, Oxford University Press, 1992.

[24] J.-W. Klop, V. van Oostrom, and F. van Raamsdonk, Combinatory reduction systems, introduction and survey, Theoretical Computer Science 121 (1993), 279–308.

[25] J-W. Klop, Combinatory reduction systems, Mathematical Centre Tracts, vol. 127, Amsterdam, 1980.

[26] P. Lescanne, From λσ to λυ a journey through calculi of explicit substitutions, POPL’94, 1994.

[27] R. Mayr and T. Nipkow, Higher-order rewrite systems and their confluence, TCS 192 (1998), 3–29.

[28] Milner, Parrow, and Walker, A Calculus of Mobile Processes, II, Inf. and Comp. 100:1 1992, 41–77.

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

[30] B. Pagano, Des calculs de substitution explicite et de leur application à la compilation des langages fonctionnels, Ph.D. thesis, Université de Paris 6, 1998.

[31] A. M. Pitts, Nominal logic, a first order theory of names and binding, Information and Computation 186 (2003), 165–193.

[32] A. M. Pitts and I. D. B. Stark, Observable Properties of Higher Order Functions That Dynamically Create Local Names, or: What’s new?. LNCS, vol. 711, 1993, pp 122–141.

[33] A. M. Pitts and M. J. Gabbay, A metalanguage for programming with bound names modulo renaming, MPC2000, LNCS 1837, 2000, pp. 230–255.

[34] F. van Raamsdonk, Confluence and normalisation for higher-order rewriting, Ph.D. thesis, Free University of Amsterdam, 1996.

[35] M. R. Shinwell, A. M. Pitts, and Murdoch Gabbay, FreshML: Programming with binders made simple, ICFP 2003, pp. 263–274.

[36] C. Urban, A. M. Pitts, and M. J. Gabbay, Nominal unification, CSL’03 & KGC. LNCS 2803, 2003, pp. 513–527.

[37] C. Urban, Nominal matching, in preparation, 2004.

Notes

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 2002 ACM X-XXXXX-XX-X/XX/XX ...$5.00.