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

Theoretical Computer Science 323 (2004) 473–497

www.elsevier.com/locate/tcs

Nominal unification

Christian Urbana , Andrew M. Pittsa,∗ , Murdoch J. Gabbayb

aUniversity of Cambridge, Marconi Laboratory, William Gates Bldng, JJ Thomson Ave., Cambridge CB3 OFD, UK

bINRIA, Paris, France

Received 3 October 2003; received in revised form 8 April 2004; accepted 11 June 2004

Communicated by P.L. Curien

Abstract

We present a generalisation of first-order unification to the practically important case of equations between terms involving binding operations. A substitution of terms for variables solves such an equation if it makes the equated terms α-equivalent, i.e. equal up to renaming bound names. For the applications we have in mind, we must consider the simple, textual form of substitution in which names occurring in terms may be captured within the scope of binders upon substitution. We are able to take a “nominal” approach to binding in which bound entities are explicitly named (rather than using nameless, de Bruijn-style representations) and yet get a version of this form of substitution that respects α-equivalence and possesses good algorithmic properties. We achieve this by adapting two existing ideas. The first one is terms involving explicit substitutions of names for names, except that here we only use explicit permutations (bijective substitutions). The second one is that the unification algorithm should solve not only equational problems, but also problems about the freshness of names for terms. There is a simple generalisation of classical first-order unification problems to this setting which retains the latter’s pleasant properties: unification problems involving α-equivalence and freshness are decidable; and solvable problems possess most general solutions. ⃝c 2004 Elsevier B.V. All rights reserved.

Keywords: Abstract syntax; Alpha-conversion; Binding operations; Unification

1. Introduction

Decidability of unification for equations between first-order terms and algorithms for computing most general unifiers form a fundamental tool of computational logic with

∗ Corresponding author. E-mail address: andrew.pitts@cl.cam.ac.uk (A.M. Pitts).

0304-3975/$ - see front matter c⃝ 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.tcs.2004.06.016

many applications to programming languages and computer-aided reasoning. However, very many potential applications fall outside the scope of first-order unification, because they involve term languages with binding operations where at the very least we do not wish to distinguish terms differing up to the renaming of bound names. There is a large body of work studying languages with binders through the use of various λ-calculi as term representation languages, leading to higher-order unification algorithms for solving equations between λ-terms modulo αβη-equivalence. However, higher-order unification is technically complicated without being completely satisfactory from a pragmatic point of view. The reason lies in the difference between substitution for first-order terms and for λ-terms. The former is a simple operation of textual replacement (sometimes called grafting [7], or context substitution [12, Section 2.1]), whereas the latter also involves renamings to avoid capture. Capture-avoidance ensures that substitution respects α-equivalence, but it complicates higher-order unification algorithms. Furthermore it is the simple textual form of substitution rather than the more complicated capture-avoiding form which occurs in many informal applications of “unification modulo α-equivalence”. For example, consider the following schematic rule which might form part of the inductive definition of a binary evaluation relation ⇓ for the expressions of an imaginary functional programming language:

app(fn a.Y, X ) ⇓V let a = X in Y ⇓V.(1)

Here X , Y and V are metavariables standing for unknown programming language expressions. The binders fn a.(−) and let a = X in (−) may very well capture free occurrences of the variable named a when we instantiate the schematic rule by replacing the metavariable Y with an expression. For instance, using the rule scheme in a bottom-up search for a proof of

let a = 1 in a ⇓1, (2)

we would use a substitution that does involve capture, namely

[X := 1, Y := a, V := 1],

in order to unify the goal with the conclusion of the rule (1)—generating the new goal app(fn a.a, 1) ⇓ 1 from the hypothesis of (1). The problem with this is that in informal practice we usually identify terms up to α-equivalence, whereas textual substitution does not respect α-equivalence. For example, up to α-equivalence, the goal

let b = 1 in b ⇓1 (3)

is the same as (2). We might think (erroneously!) that the conclusion of rule (1) is the same as let b = X in Y ⇓V without changing the rule’s hypothesis—after all, if we are trying to make α-equivalence disappear into the infrastructure, then we must be able to replace any part of what we have with an equivalent part. So we might be tempted to unify the conclusion with (3) via the textual substitution [X := 1, Y := b, V := 1], and then apply this substitution to the hypothesis to obtain a wrong goal, app(fn a.b, 1) ⇓ 1. Using λ-calculus and higher-order unification saves us from such sloppy thinking, but at the expense of having to make explicit the dependence of metavariables on bindable names via the use of function variables and application. For example, (1) would be replaced by something like

app (fn λa.F a) X ⇓V let X (λa.F a) ⇓V (4)

or, modulo η-equivalence

app (fn F) X ⇓V let X F ⇓V.
(5)

Now goal (3) becomes let 1 λb.b ⇓ 1 and there is no problem unifying it with the conclusion of (4) via a capture-avoiding substitution of 1 for X , λc.c for F and 1 for V.

This is all very fine, but the situation is not as pleasant as for first-order terms: higher-order unification problems can be undecidable, decidable but lack most general unifiers, or have such unifiers only by imposing some restrictions [20]; see [6] for a survey of higher-order unification. We started out wanting to compute with binders modulo α-equivalence, and somehow the process of making possibly-capturing substitution respectable has led to function variables, application, capture-avoiding substitution and βη-equivalence. Does it have to be so? No!

For one thing, several authors have already noted that one can make sense of possibly-capturing substitution modulo α-equivalence by using explicit substitutions in the term representation language: see [7,13,15,23,25,31]. Compared with those works, we make a number of simplifications. First, we find that we do not need to use function variables, application or βη-equivalence in our representation language—leaving just binders and α-equivalence. Secondly, instead of using explicit substitutions of names for names, we use only the special case of explicit permutations of names. The idea of using name-permutations, and in particular name-swappings, when dealing with α-conversion was described in [11] and there is growing evidence of its usefulness (see [3,4,33], for example). When a name substitution is actually a permutation, the function it induces from terms to terms is a bijection; this bijectivity gives the operation of permuting names very good logical properties compared with name substitution. Consider for example the α-equivalent terms fn a.b and fn c.b, where a, b and c are distinct. If we apply the substitution [b↦→a] (renaming all free occurrences of b to be a) to them we get fn a.a and fn c.a, which are no longer α-equivalent. Thus renaming substitutions do not respect α-equivalence in general, and any unification algorithm using them needs to take extra precautions to not inadvertently change the intended meaning of terms. The traditional solution for this problem is to introduce a more complicated form of renaming substitution that avoids capture of names by binders. In contrast, the simple operation of name-permutation respects α-equivalence; for example, applying the name-permutation (a b) that swaps all occurrences of a and b (be they free, bound or binding) to the terms above gives fn b.a and fn c.a, which are still α-equivalent. We exploit such good properties of name-permutations to give a conceptually simple unification algorithm.

In addition to the use of explicit name-permutations, we also compute symbolically with predicates expressing freshness of names for terms. Such predicates certainly feature in previous work on binding (for example, Qu-Prolog’s not_free in predicate [8], the notion of “algebraic independence” in [30, Definition 3], and the “non-occurrence” predicates of [16]). But once again, the use of such a freshness predicate based upon name swapping rather than renaming, which arises naturally from the work reported in [11,27], gives us a simpler theory with good algorithmic properties. It is easy to see why there is a need for computing with freshness, given that we take a “nominal” approach to binders. (In other words we use concrete versions of binding and α-equivalence in which bound entities are named explicitly, rather than using de Bruijn-style representations, as for example in [7,31].) A basic instance of our generalised form of α-equivalence identifies fn a.X with fn b.(a b) · X provided b is fresh for X , where the subterm (a b) · X indicates an explicit permutation—namely the swapping of a and b—waiting to be applied to X . We write “b is fresh for X ” symbolically as b # X ; the intended meaning of this relation is that b does not occur free in any (ground) term that may be substituted for X . If we know more about X we may be able to eliminate the explicit permutation in (a b) · X ; for example, if we knew that a # X holds as well as b # X , then (a b) · X can be replaced by X .

It should already be clear from these simple examples that in our setting the appropriate notion of term-equality is not a bare equation, t ≈t′, but rather a hypothetical judgement of the form

∇⊢t ≈t′(6)

where ∇ is a freshness environment—a finite set {a1 # X1, . . . , an # Xn} of freshness assumptions. For example

{a # X, b # X } ⊢fn a.X ≈fn b.X (7)

is a valid judgement of our nominal equational logic. Similarly, judgements about freshness itself will take the form

∇⊢a # t . (8)

Two examples of valid freshness judgements are {a # X } ⊢a # fn b.X and ∅⊢a # fn a.X .

The freshness environment ∇ in judgements of the form (6) and (8) expresses freshness conditions that any textual substitution of terms for variables must respect in order for the right-hand side of the judgement to be valid after substitution. This explicit use of freshness makes the operation of textual substitution respect our generalised form of α-equivalence. For example, if we were naïvely to regard the terms fn a.X and fn b.X as α-equivalent, then applying for example the capturing substitution [X := a] or [X := b] results into two terms that are not α-equivalent anymore. (A similar observation partly motivates the work in [32].) However, if we assume a # X and b # X as in (8), then all problematic substitutions are ruled out. In this way we obtain a version of α-equivalence between terms with variables that is respected by textual substitutions (see Lemma 2.14 below), unlike the traditional notion of α-equivalence.

1.1. Summary

We will represent languages involving binders using the usual notion of first-order terms over a many-sorted signature, but with certain distinguished constants and function symbols. These give us terms with: distinguished constants naming bindable entities, that we call atoms; terms a.t expressing a generic form of binding of an atom a in a term t; and terms π · X representing an explicit permutation π of atoms waiting to be applied to whatever term is substituted for the variable X . Section 2 presents this term-language together with a syntax-directed inductive definition of the provable judgements of form (6) and (8) which for ground terms (i.e. ones with no variables) agrees with the usual notions of α-equivalence and “not a free variable of”. However, on open terms our judgements differ from these standard notions. Section 3 considers unification in this setting. Solving equalities between abstractions a.t ≈? a′.t′ entails solving both equalities t ≈? (a a′) · t′ and freshness problems a #? t′. Therefore our general form of nominal unification problem is a finite collection of individual equality and freshness problems. Such a problem P is solved by providing not only a substitution σ (of terms for variables), but also a freshness environment ∇ (as above), which together have the property that ∇⊢σ(t) ≈σ(t′) and ∇⊢a # σ(t′′) hold for each individual equality t ≈? t′ and freshness a #? t′′ in the problem P. Our main result with respect to unification is that solvability is decidable and that solvable problems possess most general solutions (for a reasonably obvious notion of “most general”). The proof is via a unification algorithm that is very similar to the first-order algorithm given in the now-common transformational style [18]. (See [17, Section 2.6]or [1, Section 4.6] for expositions of this.) Section 4 considers the relationship of our version of “unification modulo α-equivalence” to existing approaches. Section 5 assesses what has been achieved and the prospects for applications.

1.2. Quiz

To appreciate the kind of problem that nominal unification solves, you might like to try the following quiz about the λ-calculus [2] before we apply our algorithm to solve it at the end of Section 3.

Assuming a and b are distinct variables, is it possible to find λ-terms M1, . . . , M7 that make the following pairs of terms α-equivalent?

(1) λa.λb.(M1 b) and λb.λa.(a M1),

(2) λa.λb.(M2 b) and λb.λa.(a M3),

(3) λa.λb.(b M4) and λb.λa.(a M5),

(4) λa.λb.(b M6) and λa.λa.(a M7).

If it is possible to find a solution for any of these four problems, can you describe what all possible solutions for that problem are like? (The answers are given in Example 3.8.)

2. Nominal equational logic

We take a concrete approach to the syntax of binders in which bound entities are explicitly named. Furthermore we do not assume that the names of bound entities are necessarily variables (things that may be substituted for), in order to encompass examples like the π-calculus [21], in which the restriction operator binds channel names and these are quite different from names of unknown processes. Names of bound entities will be called atoms. This is partly for historical reasons (stemming from the work by the second two authors [11]) and partly to indicate that the internal structure of such names is irrelevant to us: all we care about is their identity (i.e. whether or not one atom is the same as another) and that the supply of atoms is inexhaustible.

Although there are several general frameworks in the literature for specifying languages with binders, not all of them meet the requirements mentioned in the previous paragraph. Use of the simply typed λ-calculus for this purpose is common; but as discussed in the Introduction, it leads to a problematic unification theory. Among first-order frameworks, Plotkin’s notion of binding signature [28,9], being unsorted, equates names used in binding with names of variables standing for unknown terms; so it is not sufficiently general for us. A first-order framework that does meet our requirements is the notion of nominal algebras in [16]. The nominal signatures that we use in this paper are a mild (but practically useful) generalisation of nominal algebras in which name-abstraction and pairing can be mixed freely in arities (rather than insisting as in [16] that the argument sort of a function symbol be normalised to a tuple of abstractions).

Definition 2.1

A nominal signature is specified by: a set of sorts of atoms (typical symbol ν); a disjoint set of sorts of data (typical symbol δ); and a set of function symbols (typical symbol f), each of which has an arity of the form τ →δ. Here τ ranges over (compound) sorts given by the grammar τ ::= ν | δ | 1 | τ × τ | ⟨ν⟩τ . Sorts of the form ⟨ν⟩τ classify terms that are binding abstractions of atoms of sort ν over terms of sort τ. We will explain the syntax and properties of such terms in a moment.

Example 2.2

Here is a nominal signature for expressions in a small fragment of ML [22]:

sort of atoms: vid sort of data: exp function symbols: vr : vid → exp

app : exp × exp →exp fn : ⟨vid⟩exp →exp lv : exp × ⟨vid⟩exp →exp lf : ⟨vid⟩((⟨vid⟩exp) × exp) →exp.

The function symbol vr constructs terms of sort exp representing value identifiers (named by atoms of sort vid); app constructs application expressions from pairs of expressions; fn, lv and lf construct terms representing respectively function abstractions (fn x => e), local value declarations (let val x = e1 in e2 end) and local recursive function declarations (let fun f x = e1 in e2 end). The arities of the function symbols specify which are binders and in which way their arguments are bound. For example, in the expression (let fun f x = e1 in e2 end) there is a binding occurrence of the value identifier f whose scope is both of e1 and e2; and a binding occurrence of the value identifier x whose scope is just e1. These binding scopes are reflected by the argument sort of the function symbol lf. This kind of specification of binding scopes is of course a feature of higher-order abstract syntax [26], using function types ν→τ in simply typed λ-calculus where we use abstraction sorts ⟨ν⟩τ. We shall see that the latter have much more elementary (indeed, first-order) properties compared with the former.

Definition 2.3

Given a nominal signature, we assume that there are countably infinite and pairwise disjoint sets of atoms (typical symbol a) for each sort of atoms ν, and variables (typical symbol X ) for each sort of atoms ν and each sort of data δ. The terms over a nominal signature and their sorts are inductively defined as follows, where we write t : τ to indicate that a term t has sort τ. Unit value ⟨⟩ : 1. Pairs ⟨t1, t2⟩ : τ1 × τ2, if t1 : τ1 and t2 : τ2. Data f t : δ, if f is a function symbol of arity τ →δ and t : τ. Atoms a : ν, if a is an atom of sort ν. Atom-abstraction a.t : ⟨ν⟩τ, if a is an atom of sort ν and t : τ. Suspension π · X : τ, if π = (a1 b1)(a2 b2) · · · (an bn) is a finite list whose elements (ai bi) are pairs of atoms, with ai and bi of the same sort, and X is a variable of sort τ, where τ is either a sort of data or a sort of atoms (i.e. τ ::= ν | δ).

Recall that every finite permutation can be expressed as a composition of swappings (ai bi); the list π of pairs of atoms occurring in a suspension term π · X specifies a finite permutation of atoms waiting to be applied once we know more about the variable X (by substituting for it, for example). We represent finite permutations in this way because it is really the operation of swapping which plays a fundamental rôle in the theory. Since, semantically speaking, swapping commutes with all term-forming operations, we can normalise terms involving an explicit swapping operation by pushing the swap in as far as it will go, until it reaches a variable (applying the swapping to atoms that it meets on the way); the terms in Definition 2.3 are all normalised in this way, with explicit permutations “piled up” in front of variables giving what we have called suspensions. In case the permutation π in a suspension is the empty list, we just write X for π · X .

Definition 2.4

The permutation action, π · t, of a finite permutation of atoms π on a term t is defined as in Fig. 1, making use of the following notations. The composition of a permutation π followed by a swap (a b) is given by list-cons, written (a b) :: π. (Note that we apply permutations to terms on the left, and hence the order of the composition is from right to left.) The composition of π followed by another permutation π′ is given by list-concatenation, written as π′@π. The identity permutation is given by the empty list []; and the inverse of a permutation is given by list reversal, written as π−1.

nomu-figure-1[] · a def= a ((a1 a2) :: π) · a def= a1if π · a = a2a2if π · a = a1π · a otherwiseπ · ⟨⟩def= ⟨⟩ π · ⟨t1, t2⟩def= ⟨π · t1, π · t2⟩ π · (f t) def= f (π · t) π · (a.t) def= (π · a).(π · t) π · (π′ · X ) def= (π@π′) · X
Fig. 1. Permutation action on terms, π · t.
nomu-figure-2∇⊢⟨⟩≈⟨⟩(≈-unit)∇⊢t1 ≈t′ 1∇⊢t2 ≈t′ 2∇⊢⟨t1, t2⟩≈⟨t′ 1, t′ 2⟩(≈-pair)∇⊢t ≈t′∇⊢f t ≈f t′ (≈-function symbol)∇⊢t ≈t′∇⊢a.t ≈a.t′ (≈-abstraction-1)a ≠ a′∇⊢t ≈(a a′) · t′∇⊢a # t′∇⊢a.t ≈a′.t′(≈-abstraction-2)∇⊢a ≈a (≈-atom)(a # X ) ∈∇for all a ∈ds(π, π′) ∇⊢π · X ≈π′ · X(≈-suspension)∇⊢a # ⟨⟩(#-unit)∇⊢a # t1∇⊢a # t2∇⊢a # ⟨t1, t2⟩(#-pair)∇⊢a # t ∇⊢a # f t (#-function symbol)∇⊢a # a.t (#-abstraction-1)a ≠ a′∇⊢a # t ∇⊢a # a′.t(#-abstraction-2)a ≠ a′∇⊢a # a′ (#-atom)(π−1 · a # X ) ∈∇ ∇⊢a # π · X(#-suspension)
Fig. 2. Inductive definition of ≈ and #.

Permutation actions have excellent logical properties (stemming from the fact that they are bijections). We exploit these properties in our definition of α-equivalence for terms over a nominal signature, which is respected by substitution of terms for variables even though the latter may involve capture of atoms by binders. To do so we will need to make use of an auxiliary relation of freshness between atoms and terms, whose intended meaning is that the atom does not occur free in any substitution instance of the term. As discussed in the Introduction, our judgements about term equivalence (t ≈t′) need to contain hypotheses about the freshness of atoms with respect to variables (a # X ); and the same goes for our judgements about freshness itself (a # t). Fig. 2 gives a syntax-directed inductive definition of equivalence and freshness using judgements of the form

∇⊢t ≈t′and ∇⊢a # t

where t and t′ are terms of the same sort over a given nominal signature, a is an atom, and the freshness environment ∇ is a finite set of freshness constraints a # X , each specified by an atom and a variable. Rule (≈-suspension) in Fig. 2 makes use of the following definition.

Definition 2.5

The disagreement set of two permutations π and π′ is the set of atoms

ds(π, π′) def= {a | π · a ≠ π′ · a}.

Note that every disagreement set ds(π, π′) is a subset of the finite set of atoms occurring in either of the lists π and π′, because if a does not occur in those lists, then from Fig. 1 we get π · a = a = π′ · a. To illustrate the use of disagreement sets, consider the judgement

{a # X , c # X } ⊢(a c)(a b) · X ≈(b c) · X .

This holds by applying rule (≈-suspension) in Fig. 2, since the disagreement set of the permutations (a c)(a b) and (b c) is {a, c}.

Remark 2.6 (Freshness environments).

Note that the freshness environment on the left-hand side of judgements in the rules in Fig. 2 does not change from hypotheses to conclusion. So in the same way that we assume variables have attached sorting information, we could dispense with the use of freshness environments entirely by attaching the freshness information directly to variables. However, we find the use of freshness environments more elegant (for one thing, without them two variables with the same name but different freshness information would have to be regarded as different). They also make life simpler when we come on to nominal unification problems and their solutions in the next section.

Below we sketch a proof that ≈ is an equivalence relation. At first sight this property might be surprising considering the “unsymmetric” definition of the rule (≈-abstraction-

2). However it holds because of the good logical properties of the relation ≈ with respect to permutation actions. Although reasoning about ≈ is rather pleasant once equivalence is proved, establishing it first is rather tricky—mainly because of the large number of cases, but also because several facts needed in the proof are interdependent. 1

We first show that permutations can be moved from one side of the freshness relation to the other by forming the inverse permutation, and that the freshness relation is preserved under permutation actions.

Lemma 2.7

(1) If ∇⊢a # π · t then ∇⊢π−1 · a # t .

(2) If ∇⊢π · a # t then ∇⊢a # π−1 · t .

(3) If ∇⊢a # t then ∇⊢π · a # π · t .

Proof. (1) and (2) are by routine inductions on the structure of t, using the fact that π · a = b iff a = π−1 · b ; (3) is a consequence of (2) and the fact that permutations are bijections on atoms.

According to the definition of the permutation action given in Fig. 1, if we push a permutation inside a term, we need to apply the permutation to all atoms we meet on the way. Suppose we apply two distinct permutations, say π and π′, to a term t, then in general π · t and π′ · t are not α-equivalent—the disagreement set ds(π, π′) characterises all atoms which potentially lead to differences. However, if we assume that all atoms in ds(π, π′) are fresh for t, then we can infer that the permutation actions produce equivalent terms. This is made precise in the following lemma.

Lemma 2.8

Given any π and π′, if ∇⊢a # t holds for all a ∈ds(π, π′), then ∇⊢π · t ≈π′ · t.

Proof. By induction on the structure of t, for all π and π′ simultaneously, using the fact about disagreement sets that for all atoms a, b, if a ∈ds(π, (π · b π′ · b) :: π′) then a ∈ds(π, π′).

An example of this lemma is that ∇⊢π · (a b) · t ≈ (π · a π · b) · π · t is a valid judgement, because the disagreement set ds(π@(a b) , (π · a π · b) :: π) is empty.

The next lemma shows that ≈ respects the freshness relation.

Lemma 2.9

If ∇⊢a # t and ∇⊢t ≈t′, then ∇⊢a # t′.

Proof. Routine induction on the definition of ≈ using Lemma 2.7.

For showing transitivity of the relation ≈, it will be necessary to define a measure that counts all term constructors occurring in a term.

Definition 2.10

The size of a term t is the natural number |t| defined by:

|π · X |, |a|, |⟨⟩|def= 1,|a.t|, |f t|def= 1 + |t|,|⟨t1, t2⟩|def= 1 + |t1| + |t2|.

Notice that the size of a term is preserved under permutation actions (i.e. |π · t| = |t|) and respected by the relation ≈ in the sense that if ∇⊢t ≈t′ then |t| = |t′|.

Theorem 2.11 (Equivalence).

∇⊢−≈− is an equivalence relation.

Proof. Reflexivity is by a simple induction on the structure of terms. Transitivity is by an induction on the size of terms: a slight complication is that many subcases need to be analysed (for example five subcases when dealing with abstractions) and also that transitivity needs to be shown by mutual induction with the fact that ≈ is preserved under permutation actions, that is

given any π, if ∇⊢t ≈t′ then ∇⊢π · t ≈π · t′ . (9)

We illustrate the proof of transitivity for the case when ∇⊢a1.t1 ≈a2.t2 and ∇⊢ a2.t2 ≈a3.t3 hold, with a1, a2 and a3 all distinct atoms, and we have to prove ∇⊢ a1.t1 ≈a3.t3. By the (≈-abstraction-2) rule we can infer from the assumptions the following facts:

(i) ∇⊢t1 ≈ (a1 a2) · t2, (ii) ∇⊢a1 # t2,

(iii) ∇⊢t2 ≈ (a2 a3) · t3, (iv) ∇⊢a2 # t3.

Below we give the steps that prove ∇⊢a1.t1 ≈a3.t3:

(a) ∇⊢ (a1 a2) · t2 ≈ (a1 a2)(a2 a3) · t3 by (iii) and IH (9),

(b) ∇⊢t1 ≈ (a1 a2)(a2 a3) · t3 by (i), (a) and IH (transitivity),

(c) ds((a1 a2)(a2 a3) , (a1 a3)) = {a1, a2} by definition,

(d) ∇⊢a1 # (a2 a3) · t3 by (ii), (iii) and Lemma 2.9,

(e) ∇⊢a1 # t3 by (a2 a3) · a1 = a1, (d) and Lemma 2.7(i),

(f) ∇⊢ (a1 a2)(a2 a3) · t3 ≈ (a1 a3) · t3 by (c), (iv), (e) and Lemma 2.8,

(g) ∇⊢t1 ≈ (a1 a3) · t3 by (b), (f) and IH (transitivity),

(h) ∇⊢a1.t1 ≈a3.t3 by (e), (g) and (≈-abstraction-2).

The other cases are by similar arguments. Symmetry is then by a routine induction on the definition of ≈ using Lemma 2.8 and transitivity.

Now it is relatively straightforward to obtain the following properties of our equivalence relation with respect to permutation actions.

Corollary 2.12

(1) ∇⊢t ≈π−1 · π · t′ if and only if ∇⊢t ≈t′ .

(2) ∇⊢t ≈π · t′ if and only if ∇⊢π−1 · t ≈t′ .

(3) Given any π and π′, if ∇⊢π · t ≈π′ · t then for all a in ds(π, π′) we have ∇⊢a # t.

Proof. (i) Follows immediately from Lemma 2.8 and transitivity; (ii) follows from (9) and (i); and (iii) is by a routine induction on the structure of t using Lemma 2.9.End of proof

The main reason for using suspensions in the syntax of terms is to enable a definition of substitution of terms for variables that allows capture of free atoms by atom-abstractions while still respecting α-equivalence. The following lemma establishes this. First we give some terminology and notation for term-substitution.

Definition 2.13

A substitution σ is a sort-respecting function from variables to terms with the property that σ(X ) = X for all but finitely many variables X . We write dom(σ) for the finite set of variables X satisfying σ(X ) ≠ X . If dom(σ) consists of distinct variables X1, . . . , Xn and σ(Xi) = ti for i = 1..n, we sometimes write σ as

σ = [X1 := t1, . . . , Xn := tn]. (10)

We write σ(t) for the result of applying a substitution σ to a term t; this is the term obtained from t by replacing each suspension π · X in t (as X ranges over dom(σ)) by the term π · σ(X ) got by letting π act on the term σ(X ) using the definition in Fig. 1. For example, if σ = [X := ⟨b, Y⟩] and t = a.(a b) · X , then σ(t) = a.⟨a, (a b) · Y⟩. Given substitutions σ and σ′, and freshness environments ∇ and ∇′, we write

(a) ∇′ ⊢σ(∇) and (b) ∇⊢σ ≈σ′ (11)

to mean, for (a), that ∇′ ⊢a # σ(X ) holds for each (a # X ) ∈∇ and, for (b), that ∇⊢σ(X ) ≈σ′(X ) holds for all X ∈ dom(σ) ∪ dom(σ′).

Lemma 2.14 (Substitution).

Substitution commutes with the permutation action: σ(π · t) = π · (σ(t)). Substitution also preserves ≈ and # in the following sense:

(1) if ∇′ ⊢σ(∇) and ∇⊢t ≈t′, then ∇′ ⊢σ(t) ≈σ(t′),

(2) if ∇′ ⊢σ(∇) and ∇⊢a # t, then ∇′ ⊢a # σ(t).

Proof. The first sentence follows by a routine induction on the structure of t. The second follows by induction on the definition of ≈ and # using Lemma 2.8.

We claim that the relation ≈ defined in Fig. 2 gives the correct notion of α-equivalence for terms over a nominal signature. This is reasonable, given Theorem 2.11 and the fact that, by definition, it satisfies rules (≈-abstraction-1) and (≈-abstraction-2). Further evidence is provided by the following proposition, which shows that for ground terms ≈ agrees with the following more traditional definition of α-equivalence.

Definition 2.15 (Naïve α-equivalence).

Define the binary relation t =α t′ between terms over a nominal signature to be the least sort-respecting congruence relation satisfying a.t =α b.[a↦→b]t whenever b is an atom (of the same sort as a) not occurring at all in the term t. Here [a↦→b]t indicates the result of replacing all free occurrences of a with b in t.

Proposition 2.16 (Adequacy).

If t and t′ are ground terms (i.e. terms with no variables and hence no suspensions) over a nominal signature, then the relation t =α t′ of Definition 2.15 holds if and only if ∅⊢t ≈t′ is provable from the rules in Fig. 2. Furthermore, ∅⊢a # t is provable if and only if a is not in the set FA(t) of free atoms of t, defined by:

FA(⟨⟩)def= ∅,FA(⟨t1, t2⟩)def= FA(t1) ∪FA(t2),FA(f t)def= FA(t),FA(a)def= {a},FA(a.t)def= FA(t) −{a}.

Proof. The proof is similar to the proof of [11, Proposition 2.2].

For non-ground terms, the relations =α and ≈ differ! For example a.X =α b.X always holds, whereas ∅⊢a.X ≈b.X is not provable unless a = b. This disagreement is to be expected, since we noted in the Introduction that =α is not preserved by substitution, whereas from Lemma 2.14 we know that ≈ is.

3. Unification

Given terms t and t′ of the same sort over a nominal signature, can we decide whether or not there is a substitution of terms for the variables in t and t′ that makes them equal in the sense of the relation ≈ introduced in the previous section? Since instances of ≈ are established modulo freshness constraints, it makes more sense to ask whether or not there is both a substitution σ and a freshness environment ∇ for which ∇⊢σ(t) ≈σ(t′) holds. As for ordinary first-order unification, solving such an equational problem may throw up several equational subproblems; but an added complication here is that because of rule (≈-abstraction-2) in Fig. 2, equational problems may generate freshness problems, i.e. ones involving the relation #. We are thus led to the following definition of unification problems for nominal equational logic.

Definition 3.1

A unification problem P over a nominal signature is a finite set of atomic problems, each of which is either an equational problem t ≈? t′ where t and t′ are terms of the same sort over the signature, or a freshness problem a #? t where a is an atom and t a term over the signature. A solution for P consists of a pair (∇, σ) where ∇ is a freshness environment and σ is a substitution satisfying

• ∇⊢a # σ(t) for each (a #? t) ∈P and

• ∇⊢σ(t) ≈σ(t′) for each (t ≈? t′) ∈P.

We write U(P) for the set of all solutions of a problem P. (∇, σ) ∈U(P) is a most general solution for P if given any other solution (∇′, σ′) ∈U(P), then there is a substitution σ′′ satisfying ∇′ ⊢σ′′(∇) and ∇′ ⊢σ′′ ◦σ ≈σ′. (Here we are using the notation of (11); and σ′′ ◦σ denotes the substitution composition of σ followed by σ′′, given by (σ′′ ◦σ)(X ) def= σ′′(σ(X )).) A solution (∇, σ) ∈U(P) is idempotent provided ∇⊢σ ◦σ ≈σ.

We describe an algorithm which, given any nominal unification problem, decides whether or not it has a solution and if it does, returns a most general (and idempotent) solution. The algorithm uses labelled transformations, directly generalising the presentation of first-order unification in [17, Section 2.6] which in turn is based upon the approach in [18]. (See also [1, Section 4.6] for a detailed exposition, but not using labels.) We use two types of labelled transformation between unification problems, namely

Pσ=⇒P′and P∇=⇒P′
nomu-figure-3(≈?-unit) {⟨⟩≈? ⟨⟩} ⊎Pε =⇒P(≈?-pair) {⟨t1, t2⟩≈? ⟨t′ 1, t′ 2⟩} ⊎Pε =⇒{t1 ≈? t′ 1, t2 ≈? t′ 2} ∪P(≈?-function symbol) {f t ≈? f t′} ⊎Pε =⇒{t ≈? t′} ∪P(≈?-abstraction-1) {a.t ≈? a.t′} ⊎Pε =⇒{t ≈? t′} ∪P(≈?-abstraction-2) {a.t ≈? a′.t′} ⊎Pε =⇒{t ≈? (a a′) · t′, a #? t′} ∪P provided a ≠ a′(≈?-atom) {a ≈? a} ⊎Pε =⇒P(≈?-suspension) {π · X ≈? π′ · X } ⊎Pε =⇒{a #? X | a ∈ds(π, π′)} ∪P(≈?-variable){t ≈? π · X } ⊎P {π · X ≈? t} ⊎P}σ=⇒σP with σ = [X := π−1 · t] provided X does not occur in t(#?-unit) {a #? ⟨⟩} ⊎P∅=⇒P(#?-pair) {a #? ⟨t1, t2⟩} ⊎P∅=⇒{a #? t1, a #? t2} ∪P(#?-function symbol) {a #? f t} ⊎P∅=⇒{a #? t} ∪P(#?-abstraction-1) {a #? a.t} ⊎P∅=⇒P(#?-abstraction-2) {a #? a′.t} ⊎P∅=⇒{a #? t} ∪P provided a ≠ a′(#?-atom) {a #? a′} ⊎P∅=⇒P provided a ≠ a′(#?-suspension) {a #? π · X } ⊎P∇=⇒P with ∇= {π−1 · a # X }
Fig. 3. Labelled transformations.

where the substitution σ is either the identity ε, or a single replacement [X := t]; and where the freshness environment ∇ is either empty ∅, or a singleton {a # X }. The legal transformations are given in Fig. 3. This figure uses the notation P ⊎P′ to indicate the union of problems P and P′ that are disjoint (P ∩P′ = ∅); and the notation σP to indicate the problem resulting from applying the substitution σ to all the terms occurring in the problem P.

Given a unification problem P, the algorithm proceeds in two phases. 2 In the first phase it applies as many σ=⇒ transformations as possible (non-deterministically). If this results in a problem containing no equational subproblems, then it proceeds to the second phase; otherwise it halts signalling failure. In the second phase it applies as many ∇=⇒ transformations as possible (non-deterministically). If this does not result in the empty problem, then it halts signalling failure; otherwise overall it has constructed a transformation sequence of the form

Pσ1=⇒· · ·σn=⇒P′∇1=⇒· · ·∇m=⇒∅ (12)

(where P′ does not contain any equational subproblems) and the algorithm returns the solution (∇1 ∪· · · ∪∇m, σn ◦· · · ◦σ1).

To show the correctness of this algorithm, we first establish that all sequences of unification transitions must terminate.

Lemma 3.2

There is no infinite series of unification transitions.

Proof. Since every reduction sequence consists of two (possibly empty) subsequences, namely one containing only σ=⇒-steps and the other only ∇=⇒-steps, we can show termination for both subsequences separately. For every unification problem P we define a measure of the size of P to be the lexicographically ordered pair of natural numbers (n1, n2), where n1 is the number of different variables used in P, and n2 is the size (see Definition 2.10) of all equational problems in P, that is

n2def=∑(t≈?t′)∈P|t| + |t′| .

In every σ=⇒-step this measure decreases: the (≈?-variable) transition eliminates (completely) one variable from the unification problem, and therefore n1 decreases; the (≈?-suspension) transition may eliminate a variable and also decreases the size n2; all other transitions leave the number of variables unchanged, but decrease n2. For the ∇=⇒-steps the size

∑(a#?t)∈P|t|

decreases in every step. Taking both facts together means that every reduction sequence must terminate.

The following lemmas help us to show that the algorithm gives correct results upon termination.

Lemma 3.3

If ∇⊢σ(π · X ) ≈σ(t) then ∇⊢σ ◦ [X := π−1 · t] ≈σ.

Proof. We have to prove that both substitutions agree (modulo ≈) on all variables in dom(σ) ∪{X }. The only interesting case is for the substitutions applied to X , when we need to show that ∇⊢σ(π−1 · t) ≈σ(X ). By Lemma 2.14 we can commute the permutation to the outside and move it to the other side of ≈ by Lemma 2.12—this gives ∇⊢σ(t) ≈π · σ(X ). The case then follows from the assumptions by symmetry and commuting the permutation inside the substitution.

Lemma 3.4

Given a unification problem P, (∇, σ) ∈U(σ′P) holds if and only if (∇, σ ◦σ′) ∈U(P).

Proof. Simple calculation using the fact that σ(σ′(t)) = (σ ◦σ′)(t).

The following two lemmas show that the unification transformations can be used to determine whether or not solutions exists and to describe all of them if they do exist.

Lemma 3.5

(i) If (∇′, σ′) ∈U(P) and Pσ=⇒P′, then (∇′, σ′) ∈U(P′) and ∇′ ⊢σ′◦σ ≈σ′.

(ii) If (∇′, σ′) ∈U(P) and P∇=⇒P′, then (∇′, σ′) ∈U(P′) and ∇′ ⊢σ′(∇).

Proof. We just give the details for two unification transitions: the case for (≈?-suspension) follows from Lemma 2.12 (iii); and the (≈?-variable) case is a consequence of Lemmas 3.3 and 3.4.

Lemma 3.6

(i) If (∇′, σ′) ∈U(P′) and Pσ=⇒P′, then (∇′, σ′ ◦σ) ∈U(P).

(ii) If (∇′, σ′) ∈U(P′), P∇=⇒P′ and ∇′′ ⊢σ′(∇), then (∇′ ∪∇′′, σ′) ∈U(P).

Proof. Once again, we just give the details for two unification transitions: the (≈?-suspension) case follows from Lemma 2.8; and the (≈?-variable) case follows from Lemma 3.4 and the fact that t[X := π−1 · t] = t, which holds by the side-condition on the (≈?-variable) transition about the non-occurrence of X in t.

The following theorem establishes the correctness of the nominal unification algorithm and is the central result of the paper.

Theorem 3.7 (Correctness).

Given a unification problem P

(i) if the algorithm fails on P, then P has no solution; and

(ii) if the algorithm succeeds on P, then the result it produces is an idempotent most general solution.

Proof. When failure happens it is because of certain subproblems that manifestly have no solution (namely in the first phase, a ≈? a′ with a ≠ a′, and π · X ≈? f t or f t ≈? π · X with X occurring in t; in the second phase, a #? a). Therefore part

(i) is a consequence of Lemma 3.5. For part (ii) one gets that a sequence like (13) exists, and thus (∇, σ) = (∇1 ∪· · · ∪∇m, σn ◦· · · ◦σ1) is in U(P) by Lemma 3.6 and the fact that (∅,ε) ∈U(∅). Furthermore from Lemma 3.5, we get that any other solution (∇′, σ′) ∈U(P) satisfies ∇′ ⊢σ′(∇) and ∇′ ⊢σ′ ◦σ ≈σ′, so that (∇, σ) is indeed a most general solution. Since one of those solutions is the most general solution (∇, σ), we also know that ∇⊢σ ◦σ ≈σ and hence that (∇, σ) is idempotent.

We now apply the nominal unification algorithm to solve the quiz questions from the Introduction.

Example 3.8

Using the first three function symbols of the nominal signature of Example 2.2 to represent λ-terms, the Quiz at the end of the Introduction translates into the following four unification problems over that signature, where a and b are distinct atoms of sort vid and X1, . . . , X7 are distinct variables of sort exp:

P1def= {fn a.fn b.app⟨X1, vr b⟩≈? fn b.fn a.app⟨vr a, X1⟩},P2def= {fn a.fn b.app⟨X2, vr b⟩≈? fn b.fn a.app⟨vr a, X3⟩},P3def= {fn a.fn b.app⟨vr b, X4⟩≈? fn b.fn a.app⟨vr a, X5⟩},P4def= {fn a.fn b.app⟨vr b, X6⟩≈? fn a.fn a.app⟨vr a, X7⟩}.
nomu-figure-4P1ε=⇒{fn b.app⟨X1, vr b⟩≈? fn b.app⟨vr b, (a b) · X1⟩, a #? fn a.app⟨vr a, X1⟩} (≈?-abstraction-2)ε =⇒{app⟨X1, vr b⟩≈? app⟨vr b, (a b) · X1⟩, a #? fn a.app⟨vr a, X1⟩} (≈?-abstraction-1)· · · · · · · · ·ε=⇒{X1 ≈? vr b, vr b ≈? (a b) · X1, a #? fn a.app⟨vr a, X1⟩} (≈?-pair)σ=⇒{vr b ≈? vr a, a #? fn a.app⟨vr a, vr b⟩} with σ = [X1 := vr b] (≈?-variable)ε=⇒{b ≈? a, a #? fn a.app⟨vr a, vr b⟩} (≈?-function symbol)FAILP4ε=⇒{fn b.app⟨vr b, X6⟩≈? fn a.app⟨vr a, X7⟩} (≈?-abstraction-1)ε=⇒{app⟨vr b, X6⟩≈? app⟨vr b, (b a) · X7⟩, b #? app⟨vr a, X7⟩} (≈?-abstraction-2)· · · · · · · · ·ε=⇒{b ≈? b, X6 ≈? (b a) · X7, b #? app⟨vr a, X7⟩} (≈?-function symbol)ε=⇒{X6 ≈? (b a) · X7, b #? app⟨vr a, X7⟩} (≈?-atom)σ=⇒{b #? app⟨vr a, X7⟩} with σ = [X6 := (b a) · X7] (≈?-variable)∅=⇒{b #? ⟨vr a, X7⟩} (#?-function symbol)· · · · · · · · ·∅=⇒{b #? a, b #? X7} (#?-function symbol)∅=⇒{b #? X7} (#?-atom)∇=⇒∅ with ∇= {b # X7} (#?-suspension)
Fig. 4. Example derivations.

Applying the nominal unification algorithm described above, we find that

• P1 has no solution;

• P2 has a most general solution given by ∇2 = ∅ and σ2 = [X2 := vr b, X3 := vr a];

• P3 has a most general solution given by ∇3 = ∅ and σ3 = [X4 := (a b) · X5];

• P4 has a most general solution given by ∇4 = {b # X7} and σ3 = [X6 := (b a) · X7].

Derivations for P1 and P4 are sketched in Fig. 4. Using the Adequacy property of Proposition 2.16, one can interpret these solutions as the following statements about the λ-terms mentioned in the quiz.

Quiz answers

1 There is no λ-term M1 making the first pair of terms α-equivalent. 2 The only solution for the second problem is to take M2 = b and M3 = a. 3 For the third problem we can take M5 to be any λ-term, so long as we take M4 to be the result of swapping all occurrences of a and b throughout M5. 4 For the last problem, we can take M7 to be any λ-term that does not contain free occurrences of b, so long as we take M6 to be the result of swapping all occurrences of b and a throughout M7, or equivalently (since b is not free in M7), taking M6 to be the result of replacing all free occurrences of a in M7 with b.

Remark 3.9 (Separation of the algorithm into two phases).

We organised the algorithm into two phases: equation-solving followed by freshness-solving. Note that the second phase is crucial for the soundness of the algorithm. Consider for example the unification problem consisting of two terms which are not α-equivalent:

{a.b ≈? b.a}. (13)

After applying the transformation (≈?-abstraction-2) one needs to solve the problem {a ≈? a, a #? a}, whose first component is solved by (≈?-atom). Failure is only signalled by the algorithm in the second phase when attempting to solve the unsolvable freshness problem {a #? a}. The second phase, i.e. solving all freshness problems, ensures that the unifiers calculated by the algorithm are sound with respect to our notion of α-equivalence.

We used this separation of the algorithm into two phases in order to make the correctness proof easier. More efficient algorithms would seek to minimise the amount of redundant calculations before failures are signalled, by solving freshness problems more eagerly. However, care needs then to be taken not to remove freshness constraints from problems too early. For example, consider the following unification problem, which has no solution.

{a #? X, a ≈? X }. (14)

If one applies first (#?-suspension) followed by (≈?-variable), then one gets a wrong result, namely ({a # X }, [X := a]). The problem is that the substitution [X := a] has not been properly propagated to the freshness constraint a # X . If freshness problems are solved more eagerly, then proper propagation of substitutions into freshness constraints needs to be taken into account.

Remark 3.10 (Atoms are not variables).

Nominal unification unifies variables, but it does not unify atoms. Indeed the operation of identifying two atoms by renaming one of them to be the other does not necessarily preserve the validity of the judgements in Fig. 2. For example, ∅⊢a.b ≈c.b holds if b ≠ a, c; but renaming b to be a in this judgement we get ∅⊢a.a ≈c.a, which does not hold so long as a ≠ c. Referring to Definition 2.3, you will see that we do allow variables ranging over sorts of atoms; and such variables can be unified like any other variables. However, if A is such a variable, then it cannot appear in abstraction position, i.e. as A.t. This is because we specifically restricted abstraction to range over atoms, rather than over arbitrary terms of atom sort. Such a restriction seems necessary to obtain single, most general, solutions to nominal unification problems. For without such a restriction, because of rule (≈-abstraction-2) in Fig. 2 we would also have to allow variables to appear on the left-hand side of freshness relations and in suspended permutations. So then we would get unification problems like {(A B) · C ≈? C}, where A, B and C are variables of atom sort; this has two incomparable solutions, namely (∅, [A := B]) and ({A # C, B # C},ε).

4. Related work

4.1. Higher-order pattern unification

Most previous work on unification for languages with binders is based on forms of higher-order unification, i.e. solving equations between λ-terms modulo αβη-equivalence (=αβη) by capture-avoiding substitution of terms for function variables. Notable among that work is Miller’s higher-order pattern unification used in his Lλ logic programming language [20]. This kind of unification retains the good properties of first-order unification: a linear-time decision procedure and existence of most general unifiers. This good behaviour of higher-order pattern unification is the result of equations being solved only modulo =αβ0η (where β0-equivalence is the restricted form of β-equivalence that identifies (λx.M)y and M[y/x] with y being a variable) and of λ-terms being restricted such that function variables may only be applied to distinct bound variables. An empirical study by Michaylov and Pfenning [19] suggests that most unifications arising dynamically in higher-order logic programming satisfy Miller’s restrictions, but that it rules out some useful programming idioms.

The main difference between higher-order pattern unification and nominal unification is that the former solves a set of equations by calculating a capture-avoiding substitution, while the latter calculates a possibly-capturing substitution and some freshness constraints. Moreover, unifiers in higher-order pattern unification solve equations with respect to =αβ0η; whereas in nominal unification, unifiers solve equations with respect to the equivalence ≈ defined in Fig. 2, which agrees with α-equivalence on ground terms (see Proposition 2.16), but differs from it on open terms, since unlike α-equivalence, it is respected by possibly-capturing substitutions (see Lemma 2.14). For us, the main disadvantage of higher-order pattern unification is the one common to most approaches based on higher-order abstract syntax that was discussed in the Introduction: one cannot directly express the common idiom of possibly-capturing substitution of terms for metavariables. Instead one has to encode metavariables X as function variables applied to distinct lists of (bound) variables, X x1 . . . xn, and use capture-avoiding substitution. At first sight, there seems to be a simple encoding for doing that. Consider for example the purely equational nominal unification problem

a.X ≈? b.b, (15)

which is solved by (∅, [X := a]). The literal encoding as the higher-order pattern unification problem λa.X =αβ0η?λb.b does not work of course, because there is no capture-avoiding substitution that solves this problem. However, X can be made dependent on a yielding the unification problem

λa.(Xa) =αβ0η? λb.b, (16)

which is solved by the capture-avoiding substitution of λc.c for X . If one further applies to λc.c the atom a used by the encoding, then one can read back the original solution [X := a] by applying some β-reductions. There are however several problems with this encoding. First, the encoding in general results in a quadratic blow-up in the size of terms. For example the nominal unification problem

a.b.⟨X, Y⟩≈? a.b.⟨a, b⟩ (17)

solved by the unifier (∅, [X := a, Y := b]) needs to be encoded so that X and Y depend on both a and b. This gives the higher-order pattern problem

λa.λb.⟨X a b, Y a b⟩=αβ0η? λa.λb.⟨a, b⟩. (18)

In the general case, the encoding needs to make metavariables dependent on all atoms occurring in a nominal unification problem, regardless of whether they actually occur in an individual equational problem. For example, if X occurs elsewhere within the scope of abstractions of c, d, e and f, then X needs to be encoded as (X a b c d e f) even though an individual equational problem might contain only a and b. Secondly, and more importantly, we cannot see how to encode our freshness constraints using this kind of higher-order patterns. (Note that in nominal unification, freshness constraints do not necessarily come from analysing abstractions, rather they can be chosen arbitrarily.)

A more promising target for a reduction of nominal unification to some form of higher-order pattern unification is λσ, a λ-calculus with de-Bruijn indices and explicit substitutions. Dowek et al. [8] present a version of higher-order pattern unification for λσ in which unification problems are solved, as in nominal unification, by textual replacements of terms for variables; however a “pre-cooking” operation ensures that the textual replacements can be faithfully related to capture-avoiding substitutions. It seems possible that the freshness (as well as the equational) problems of nominal unification can be encoded into higher-order pattern unification problems over λσ, using a non-trivial translation involving the use of the shift operator and the introduction of fresh unification variables. The details of this encoding still remain to be investigated. Furthermore, it is not clear to us how to translate solutions obtained via the encoding back into solutions of the original nominal unification problem. But even if it turns out that it is possible to reduce nominal unification to the algorithm of Dowek et al., the calculations involved in translating our terms into λσ patterns and then using higher-order pattern unification seem far more intricate than our simple algorithm that solves nominal unification problems directly. The conclusion we draw is that an encoding of nominal unification problems into higher-order pattern unification problems (using de Bruijn indices and explicit substitutions) might be possible, but such an encoding is no substitute in practice for having the simple, direct algorithm we presented here.

4.2. Hamana’s β0-unification of λ-terms with “holes”

Hamana [13,14] manages to add possibly-capturing substitution to a language like Miller’s Lλ. This is achieved by adding syntax for explicit renaming operations and by recording implicit dependencies of variables upon bindable names in a typing context. The mathematical foundation for Hamana’s system is the model of binding syntax of Fiore et al. [9]. The mathematical foundation for our work appeared at the same time (see [11]) and is in a sense complementary. For in Hamana’s system the typing context restricts which terms may be substituted for a variable by giving a finite set of names that must contain the free names of such a term; whereas we give a finite set of names which the term’s free variables must avoid. Since α-conversion is phrased in terms of avoidance, i.e. freshness of names, our approach seems more natural if one wants to compute α-equivalences concretely. On top of that, our use of name permutations, rather than arbitrary renaming functions, leads to technical simplifications. In any case, the bottom line is that Hamana’s system seems more complicated than the one presented here and does not possess most general unifiers.

4.3. Qu-Prolog

The work [23,24] on unification in Qu-Prolog is most closely related to that reported here. Qu-Prolog is a mature logic programming language addressing many problems we set out in the Introduction. To begin with, Qu-Prolog’s unification algorithm unifies terms modulo α-equivalence and may produce solutions that, as in nominal unification, depend on freshness constraints (in Qu-Prolog such constraints are represented by a predicate called not_free_in). Furthermore, metavariables are substituted in a possibly-capturing manner. However, there are also a number of differences between nominal unification and unification in Qu-Prolog. The most obvious difference is that the term language in Qu-Prolog is richer than our term language over nominal signatures; for example Qu-Prolog allows variables in binding position and permits explicit substitutions of terms for variables. This richness of the term language leads to a number of difficulties. First, the unification problems in Qu-Prolog are only semi-decidable (whereas the nominal unification problems are decidable) and as a result the algorithm employed in Qu-Prolog can leave as unsolved some unification problems that are “too difficult”. This means the unification transformations in Qu-Prolog, while shown not to delete any solutions nor to introduce any new ones, do not always lead to problems from which an explicit solution can be obtained. Secondly, as we illustrated in Remark 3.10, the possibility of forming terms with unification variables in binding position means that most general solutions may not exist.

Another difference arises from the fact that in Qu-Prolog binders are renamed via capture-avoiding substitutions. This means that fresh names need to be introduced during unification in order to respect α-equivalence. This is not necessary in nominal unification, because the permutation operation already respects α-equivalence. In fact the introduction of fresh atoms during unification leads to a more complicated notion of most general solution. Consider the following variant of the (≈?-abstraction-2) transformation:

(≈? −abstraction −2′) {a.t ≈? a′.t′} ⊎Pε =⇒{(a b) · t ≈? (a′ b) · t′, b #? t, b #? t′} ∪P

which is applicable provided a ≠ a′ and b is a fresh atom, not occurring elsewhere in the problem. This rule is essentially the refinement step that unifies two abstracted terms in Qu-Prolog (see, [23, p. 105]). If we were to use (≈?-abstraction-2′) instead of (≈?-abstraction-2) in our nominal unification algorithm, then when applied to the problem

{ a. X ≈? b.Y }. (19)

It would produce the solution ({a # Y, c # Y}, [X := (a c)(b c) · Y]). While this solution solves the problem, it is not a most general solution according to Definition 3.1—we lost the information that c is a completely fresh atom. On the other hand, applying transformation (≈?-abstraction-2) to (19) leads to ({a # Y}, [X := (a b) · Y])—a most general solution.

Overall, the theory of Qu-Prolog’s unification is more complex than that of nominal unification: in nominal unification we do not need to resort to a semantic notion of α-equivalence in order to show the correctness of the nominal unification algorithm; and the use of permutations makes our ≈-relation much simpler compared with Qu-Prolog’s use of the traditional notion of α-equivalence extended to terms with metavariables.

5. Conclusion and future work

In this paper we have proposed a new solution to the problem of computing possibly-capturing substitutions that unify terms involving binders up to α-conversion. To do so we considered a many-sorted first-order term language with distinguished collections of constants called atoms and with atom-abstraction operations for binding atoms in terms. This provides a simple, but flexible, framework for specifying binding operations and their scopes, in which the bound entities are explicitly named. By using variables prefixed with suspended permutations, one can have substitution of terms for variables both allow capture of atoms by binders and respect α-equivalence (renaming of bound atoms). The definition of α-equivalence for the term language makes use of an auxiliary freshness relation between atoms and terms which generalises the “not a free atom of” relation from ground terms to terms with variables; furthermore, because variables stand for unknown terms, hence with unknown free atoms, it is necessary to make hypotheses about the freshness of atoms for variables in judgements about term equivalence and freshness. This reliance on “freshness”, coupled with name-swapping rather than renaming, lead to a new notion of unification problem in which instances of both equivalence and freshness have to be solved by giving term-substitutions and (possibly) freshness conditions on variables in the solution. We showed that this unification problem is decidable and unitary.

Cheney et al. [5,10] are investigating the extent to which nominal unification can be used in resolution-based proof search for a form of first-order logic programming for languages with binders (with a view to providing better machine-assistance for structural operational semantics). Such a logic programming language should permit a concrete, “nominal” approach to bound entities in programs while ensuring that computation (which in this case is the computation of answers to queries) respects α-equivalence between terms. This is illustrated with the Prolog-like program in Fig. 5, which implements a simple typing algorithm for λ-terms. The third clause is the interesting one. First, note the term (lam x.M), which unifies with any λ-abstraction. The binder x, roughly speaking, has in the “nominal” approach a value which can be used in the body of the clause, for example for adding (pair x A) to the context Gamma. Secondly, the freshness constraint x # Gamma ensures that Gamma cannot be replaced by a term that contains x freely. Since this clause is intended to implement the usual rule for typing λ-abstractions

{x : A} ∪Γ ▷ M : B Γ ▷ λx.M : A ⊃B
nomu-figure-5type Gamma (var X) A :- mem (pair X A) Gamma. type Gamma (app M N) B :- type Gamma M (arrow A B), type Gamma N A. type Gamma (lam x.M) (arrow A B) / x#Gamma :- type (pair x A)::Gamma M B.mem A A::Tail. mem A B::Tail :- mem A Tail.
Fig. 5. An example αProlog program.

its operational behaviour is given by: choose fresh names for Gamma, x, M, A and B (this is standard in Prolog-like languages), unify the head of the clause with the goal formula, apply the resulting unifier to the body of the clause and make sure that Gamma is not replaced by a term that contains freely the fresh name we have chosen for x. Similar facilities for functional programming already exist in the FreshML language, built upon the same foundations: see [33] and www.freshml.org. We are also interested in the special case of “nominal matching” and its application to term-rewriting modulo α-equivalence.

5.1. A note on complexity

If these applications show that nominal unification is practically useful, then it becomes important to study its complexity. The presentations of the term language in Section 2 and of the algorithm in Section 3 were chosen for clarity and to make the proof of correctness 3 easier, rather than for efficiency. One source of increased efficiency is to delay the application of permutations: instead of pushing permutation inside terms until they reach suspension as we do here, one should just push them under the first constructor (pairing, function symbol application, or atom-abstraction) in order to proceed with the next step of decomposition. However, the main inefficiency of the algorithm presented in Section 3 comes from the lack of sharing in terms and substitutions. Thus the unification problem taken from [25]

{f(X1, X1) ≈? X2, f(X2, X2) ≈? X3, . . . , f(Xn−1, Xn−1) ≈? Xn}

which illustrates that the naïve algorithm for classical first-order unification has exponential time complexity, also applies to the algorithm for nominal unification given here. If one adapts a representation for terms using techniques developed in [25] or [18], which are based on directed acyclic graphs, then one easily arrives at an algorithm with quadratic time complexity. The reason for the quadratic, rather than linear, time-complexity is that permutations need to be applied to some atoms when deciding whether the rules (≈?-abstraction-1) or (≈?-abstraction-2) are applicable, and these permutations (represented as lists of swappings) might grow linearly with the number of nodes. Using a representation of permutations that allows for a more efficient calculation of their action on atoms does not improve the quadratic time complexity, because it makes the operation of composing two permutations become linear, while this can be done in constant time when using the list-of-swappings representation. For higher-order patterns, Qian managed to develop a unification algorithm with linear time-complexity [29]. It seems that adapting Qian’s algorithm to nominal unification via an encoding of nominal terms into higher-order patterns as discussed in Section 4 will not solve this problem. For the encoding makes the resulting higher-order patterns quadratically longer than the original nominal terms, so this method would only provide another algorithm with quadratic time complexity.

To sum up, there is a version of nominal unification with quadratic time complexity, but it is still an open question whether a version can be developed with linear time complexity.

Acknowledgements

A preliminary version of this paper appeared as [34]. We thank James Cheney, Gilles Dowek, Roy Dyckhoff, Dale Miller, Frank Pfenning, Francois Pottier and Helmut Schwichtenberg for comments on this work. This research was supported by UK EPSRC grants GR/R29697 (Urban) and GR/R07615 (Pitts and Gabbay).

References

[1] F. Baader, T. Nipkow, Term Rewriting and All That, Cambridge University Press, Cambridge, 1998.

[2] H.P. Barendregt, The Lambda Calculus: Its Syntax and Semantics, North-Holland, Amsterdam, 1984.

[3] L. Caires, L. Cardelli, A spatial logic for concurrency (part II), in: L. Brim, P. Janc̆ar, M. Kr̆etínský, A. Kuc̆era (Eds.), CONCUR 2002—Concurrency Theory, Proc. 13th Internat. Conf., Brno, Czech Republic, August 20–23, 2002, Lecture Notes in Computer Science, Vol. 2421, Springer, Berlin, 2002, pp. 209–225.

[4] L. Cardelli, P. Gardner, G. Ghelli, Manipulating trees with hidden labels, in: A.D. Gordon (Ed.), Foundations of Software Science and Computation Structures, Proc. 6th Internat. Conf., FOSSACS 2003, Warsaw, Poland, Lecture Notes in Computer Science, Vol. 2620, Springer, Berlin, 2003, pp. 216–232.

[5] J. Cheney, C. Urban, αProlog, a fresh approach to logic programming modulo α-equivalence, in: J. Levy, M. Kohlhase, J. Niehren, M. Villaret (Eds.), Proc. of UNIF 2003, no. DSIC-II/12/03 in Departamento de Sistemas Informáticos y Computación Technical Report Series, Universidad Politécnica de Valencia, 2003, pp. 15–19.

[6] G. Dowek, Higher-order unification and matching, in: A. Robinson, A. Voronkov (Eds.), Handbook of Automated Reasoning, North-Holland, Amsterdam, 2001, pp. 1009–1062 (Chapter 16).

[7] G. Dowek, T. Hardin, C. Kirchner, Higher-order unification via explicit substitutions, in: 10th Annual Symp. on Logic in Computer Science, IEEE Computer Society Press, Washington, 1995, pp. 366–374.

[8] G. Dowek, T. Hardin, C. Kirchner, F. Pfenning, Higher-order unification via explicit substitutions: the case of higher-order patterns, in: Proc. of JICSLP, 1996, pp. 259–273.

[9] M.P. Fiore, G.D. Plotkin, D. Turi, Abstract syntax and variable binding, in: 14th Annual Symp. on Logic in Computer Science, IEEE Computer Society Press, Washington, 1999, pp. 193–202.

[10] M. Gabbay, J. Cheney, A proof theory for nominal logic, in: Nineteenth Annual IEEE Symp. on Logic in Computer Science, IEEE Computer Society Press, Washington, 2004.

[11] M.J. Gabbay, A.M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Comput. 13 (2002) 341–363.

[12] C.A. Gunter, Semantics of Programming Languages: Structures and Techniques, Foundations of Computing, MIT Press, Cambridge, 1992.

[13] M. Hamana, A logic programming language based on binding algebras, in: N. Kobayashi, B.C. Pierce (Eds.), Theoretical Aspects of Computer Software, Proc. 4th Internat. Symp., TACS 2001, Sendai, Japan, October 29–31, 2001, Lecture Notes in Computer Science, Vol. 2215, Springer, Berlin, 2001, pp. 243–262.

[14] M. Hamana, Simple β0-unification for terms with context holes, in: C. Ringeissen, C. Tinelli, R. Treinen, R.M. Verma (Eds.), Proc. of UNIF 2002, 2002, unpublished proceedings.

[15] M. Hashimoto, A. Ohori, A typed context calculus, Theoret. Comput. Sci. 266 (2001) 249–271.

[16] F. Honsell, M. Miculan, I. Scagnetto, An axiomatic approach to metareasoning on nominal algebras in HOAS, in: F. Orejas, P.G. Spirakis, J. Leeuwen (Eds.), Proc. 28th Internat. Colloq. on Automata, Languages and Programming, ICALP 2001, Crete, Greece, July 2001, Lecture Notes in Computer Science, Vol. 2076, Springer, Heidelberg, 2001, pp. 963–978.

[17] J.W. Klop, Term rewriting systems, in: S. Abramsky, D.M. Gabbay, T.S.E. Maibaum (Eds.), Handbook of Logic in Computer Science, Vol. 2, Oxford Univercity Press, Oxford, 1992, pp. 1–116.

[18] A. Martelli, U. Montanari, An efficient unification algorithm, ACM Trans. Programming Languages and Syst. 4 (2) (1982) 258–282.

[19] S. Michaylov, F. Pfenning, An empirical study of the runtime behaviour of higher-order logic programs, in: D. Miller (Ed.), Proc. Workshop on the λProlog Programming Language, University of Pennsylvania, 1992, pp. 257–271, CIS Technical Report MS-CIS-92-86.

[20] D. Miller, A logic programming language with lambda-abstraction, function variables, and simple unification, J. Logic and Comput. 1 (1991) 497–536.

[21] R. Milner, J. Parrow, D. Walker, A calculus of mobile processes (parts I and II), Inform. and Comput. 100 (1992) 1–77.

[22] R. Milner, M. Tofte, R. Harper, D. MacQueen, The Definition of Standard ML (Revised), MIT Press, Cambridge, 1997.

[23] P. Nickolas, P.J. Robinson, The Qu-Prolog unification algorithm: formalisation and correctness, Theoret. Comput. Sci. 169 (1996) 81–112.

[24] R. Paterson, Unification of schemes of quantified terms, in: Proc. of UNIF 1990, 1990, unpublished proceedings.

[25] M.S. Paterson, M.N. Wegman, Linear unification, J. Comput. Syst. Sci. 16 (2) (1978) 158–167.

[26] F. Pfenning, C. Elliott, Higher-order abstract syntax, in: Proc. ACM-SIGPLAN Conf. Programming Language Design and Implementation, ACM Press, New York, 1988, pp. 199–208.

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

[28] G.D. Plotkin, An illustrative theory of relations, in: R. Cooper, Mukai, J. Perry (Eds.), Situation Theory and its Applications, CSLI Lecture Notes, Vol. 22, Stanford University, 1990, pp.133–146.

[29] Z. Qian, Unification of higher-order patterns in linear time and space, J. Logic and Comput. 6 (3) (1996) 315–341.

[30] A. Salibra, On the algebraic models of lambda calculus, Theoret. Comput. Sci. 249 (2000) 197–240.

[31] M. Sato, T. Sakurai, Y. Kameyama, A simply typed context calculus with first-class environments, J. Funct. Logic Programming 4 (2002).

[32] M. Sato, T. Sakurai, Y. Kameyama, A. Igarashi, Calculi of meta-variables, in: M. Baaz (Ed.), Proc. Comput. Sci. Logic and 8th Kurt Gödel Colloq. (CSL’03 & KGC), Vienna, Austria, Lecture Notes in Computer Science, Vol. 2803, Springer, Berlin, 2003, pp. 484–497.

[33] M.R. Shinwell, A.M. Pitts, M.J. Gabbay, FreshML: programming with binders made simple, in: Eighth ACM SIGPLAN Internat. Conf. on Functional Programming (ICFP 2003), Uppsala, Sweden, ACM Press, New York, 2003, pp. 263–274.

[34] C. Urban, A.M. Pitts, M.J. Gabbay, Nominal unification, in: M. Baaz (Ed.), Proc. Comput. Sci. Logic and 8th Kurt Gödel Colloq. (CSL’03 & KGC), Vienna, Austria, Lecture Notes in Computer Science, Vol. 2803, Springer, Berlin, 2003, pp. 513–527.

Notes

1 In addition some further simple properties of permutations and disagreement sets need to be established first. A machine-checked proof of all results using the theorem prover Isabelle can be found at http://www.cl.cam.ac.uk/users/cu200/Unification. ↩

2 See Remark 3.9 for discussion of this use of two phases. ↩

3 See http://www.cl.cam.ac.uk/users/cu200/Unification for the Isabelle proof scripts. ↩