Permissive nominal terms

HTML reading edition · 18 source pages · Open the source PDF
apport de rechercheISSN0249-6399ISRNINRIA/RR--6682--FR+ENGThème SYMINSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET EN AUTOMATIQUEPermissive nominal termsGilles Dowek — Murdoch J. Gabbay — Dominic P. MulliganN° 6682 October 2008

Permissive nominal terms

Gilles Dowek∗ , Murdoch J. Gabbay† , Dominic P. Mulligan†

Thème SYM — Systèmes symboliques

Équipe-Projet TypiCal

Rapport de recherche n° 6682 — October 2008 — 15 pages

Abstract: We present a simplified version of nominal terms with improved properties. Nominal terms are themselves a version of first-order terms, adapted to provide primitive support for names, binding, capturing substitution, and alpha-conversion. Nominal terms lack certain properties of first-order terms; it is always possible to ‘choose a fresh variable symbol’ for a first-order term and it is always possible to ‘alpha-convert a bound variable symbol to a fresh symbol’. This is not the case for nominal terms. Permissive nominal terms preserve the flavour and the basic theory of nominal terms, including two levels of variable symbol, freshness, and permutation — but they recover the ‘always fresh’ and ‘always alpha-rename’ properties of first- and higher-order syntax, and they simplify the theory by eliding freshness contexts and by supporting a notion of term-unifier based on substitution alone, rather than the nominal terms’ substitution and freshness conditions. No expressivity is lost moving to the permissive case.

Key-words: Unification algorithms, nominal techniques, permissive nominal terms

http://www.lix.polytechnique.fr/~dowek

http://www.gabbay.org.uk

http://www.macs.hw.ac.uk/~dpm8

∗ École polytechnique, 91128 Palaiseau Cedex, France † School of Mathematics and Computer Science, Heriot-Watt University, Edinburgh, UK

Centre de recherche INRIA Saclay – Île-de-France

Parc Orsay Université 4, rue Jacques Monod, 91893 ORSAY Cedex

Téléphone : +33 1 72 92 59 00

Les termes nominaux permissifs

Résumé : On propose une amélioration et une simplification de la notion de terme nominal. Les termes nominaux étendent les termes du premier ordre avec des notions primitives de nom, de liaison, de substitution autorisant les captures et d’alpha-conversion. Hélas, un certain nombre de propriétés des termes du premier ordre ne sont pas vérifiées par ces termes nominaux : il est toujours possible de choisir une variable indépendante d’un terme du premier ordre et il est toujours possible d’alpha-convertir une variable liée dans un terme en un symbole indpendant de ce terme, mais ces propriétés ne sont pas vérifiées par les termes nominaux. Les termes nominaux permissifs gardent les idées fondamentales des termes nominaux, en particulier l’idée de distinguer deux niveaux de variables, ou les notions de variable indépendante d’un terme et de permutation, mais ils restaurent la possibilité de choisir une variable indépendante d’un terme et d’alpha-convertir une variable liée dans un terme en un symbole indépendant de ce terme, comme pour avec les termes du premier ordre ou d’ordre supérieur. Leur théorie se simplifie du fait de l’introduction de contextes d’indpendance, en particulier la notion d’unificateur pour les termes nominaux permissifs repose exclusivement sur la notion de substitution, alors qu’elle reposait, pour les termes nominaux, sur les notions de substitution et de conditions d’indépendance. L’expressivité de ces termes nominaux permissifs est toutefois la même que celles des termes nominaux originaux.

Mots-clés : Algorithme d’unification, technique nominale, terme nominal permissif

1 Introduction

Unification of first-order terms is a fundamental building-block of the theory of logic and computation. It combines expressivity with excellent mathematical properties. Yet some applications are closed to first-order unification, at least at the first glance, because they involve name-abstraction (binding) — sometimes, we just want in-built theoretical support for reasoning up to α-equivalence. Famously, getting this to work is not at all as easy as, and may be mathematically a far deeper issue than, is often supposed.

One solution is higher-order unification, which is unification up to αβη-equivalence [Dow01]. However, higher-order terms are very expressive, and their unification is complex; it can be undecidable, decidable but without most general unifiers, or decidable and with most general unifiers subject to restrictions [Mil91]. What is more, the native notion of substitution — capture-avoiding substitution — does not precisely match the instantiation (capturing substitution) which often features in informal practice. For example we can set ourselves the informal unification problem

“How can we make λx.λy.(y -1) equal with λx.λx.(x -2)?”

with the intention being that the ‘holes’ -1 and -2 be substituted in a capturing manner.

Nominal unification was developed to extend first-order unification just enough that we can directly represent unification problems like that above, while preserving as much as possible of the flavour of first order unification. The slogan is ‘ϵ away from informal practice’. Full details of nominal unification, including an extended essay on its advantages and disadvantages relative to higher-order unification and also with respect to de Bruijn encodings of binding in first-order terms [dB72], can be found in the original journal paper [UPG04] and subsequent published discussions [Pit02, BU07, Che05]. We do not intend to further reflect on that discussion but it may be worth noting that nominal terms have been made the basis of rewriting, logic-programming, and algebraic frameworks [FG07, CU03, GM07, Mat07, CP07] with good properties. This provides some pragmatic evidence that nominal terms can be put to good mathematical use.

This paper proposes a (deceptively innocuous) change to nominal terms which we call permissive nominal terms. These preserve the flavour of nominal terms but they are also significantly different in many ways; we discuss how and why shortly. First, we briefly reprise nominal terms so that we can compare them easily with the permissive version. We need some by now standard definitions [UPG04]:

Definition 1

Fix a countably infinite set A of atoms. We use a permutative convention that a, b, c, . . . range permutatively over atoms. That is, for example ‘a and b’ means ‘a pair of any two distinct atoms’.

Fix a countably infinite set of unknowns. X, Y, Z, . . . will range permutatively over unknowns.

Fix a set of term-formers. f, g, h will range permutatively over term-formers.

We assume that atoms, unknowns, and term-formers are all disjoint.

Definition 2

Call a bijection on atoms π a permutation when π is finitely-supported. That is, for all but finitely many atoms it is the case that π(a) = a.

π, π′, τ, . . . will range over permutations.

Nominal terms [UPG04] are inductively defined by:

r, s, . . . ::= a | π · X | [a]r | f(r, . . . , r).

Atoms represent variable symbols, term-formers represent functions, unknowns represent meta-variables, and abstraction [a]r represents binding. For example:

• If app is a term-former then the nominal term app(a, b) can represent the λ-calculus expression xy (x applied to y).

• If lam is a term-former then the nominal term app(lam([a]a), b) can represent the λ-calculus expression (λx.x)y.

app(lam([a]a), b) and b are not equal nominal terms, any more than (λx.x)y and y are identical λ-calculus expressions.1

Nominal terms have a sophisticated theory of α-equivalence =α. For example

b#X ⊢[a]X =α [b](b a) · X

is valid. b#X is a freshness side-condition; b#X represents the informal judgement that y ∉ fv(r). (b a) is a permutation meaning ‘map a to b and b to a’. The equality above represents the informal judgement2

‘if y ∉ fv(t) then λx.t is α-equivalent with λy.[y/x]t’.

The implicit quantification over all t is reflected in the use of X, which can be instantiated (a capturing substitution). If we set X to be a — the freshness side-condition b#a is indeed valid — then we obtain [a]a =α [b]b, which represents the correct informal judgement

‘λx.x is α-equivalent with λy.y’.

A problem:

• Freshness contexts are not fixed, and this causes complexity in proofs (we always have to prove things about a term-in-context, rather than just about a term) and complicates the theory of equality between terms ([a]X =α [b](b a) · X is true if b#X is in the freshness context, and false otherwise). It would be simpler to fix freshness information once and for all at the beginning of a paper, then never change it — or the notion of α-equality between terms — again.

• Nominal terms lack some ‘minor’ properties of first- and higher-order terms; we can always pick a fresh variable symbol for a term, and we can always α-rename a bound variable symbol in a term, to be fresh. For example, if we have a λ-term expression λx.t then we can always choose a fresh y, and we can always α-rename to λy.[y/x]t.

In nominal terms this is not so. b#X is neither true nor false; it is an assumption about what X may be instantiated to. We cannot obtain a b such that b#X unless we make a freshness assumption that b#X. Likewise, we cannot immediately α-convert a in [a]X until we obtain some b#X from the freshness context; in the empty freshness context we are stuck.3

Our solution; a sketch of permissive nominal terms: We fix freshness conditions once and for all (Definition 3) then elide them as a permissions sorting condition on unknowns (Definitions 4 and 5). Thus unknowns take the form of XS where S a set of atoms is the permissions sort of X. Permissions sorts are not cofinite sets of atoms, they are sets of ‘every other atom’ in a suitable sense (Definition 3). A substitution (a map instantiating unknowns) is only admitted if it instantiates each XS to a term whose free variable symbols are in S (Definition 17). As a result we can always choose a fresh atom for a term, we can always α-convert, and α-equivalence is inherent rather than depending on a freshness context (Definition 9, Lemma 10, and Corollary 11). Furthermore the notion of solution to a unification problem is based on substitutions (Definition 29) — the corresponding notion for nominal terms is based on substitution-and-freshness [UPG04, Definition 3.1] and is more complex.

In this paper we lay down definitions and basic properties, going as far as to verify that if a unifier exists then a most general (principal) unifier exists, which is also the key result of [UPG04]. There seems no reason why a theory of rewriting should not also be developed similarly to [FG07] and the authors have begun to apply these permissive ideas in some extended case studies, using permissive nominal terms as the basis of novel logics and λ-calculi, taking full advantage of their greater closeness to traditional syntax. The indications are promising.

A disadvantage we see to permissive nominal terms is that permissions sorts use the set comb of ‘every other atom’ (Definition 3), and this is incompatible with the finite-support property of nominal sets [GP99, Definition 3.1]. This is not a paradox; in this paper we build permissive nominal terms in the meta-level, where we can have any subsets of atoms that we like. However it is unfortunate because, unlike nominal terms, permissive nominal terms can be directly qotiented by α-equivalence just as for first- and higher-order terms, and so it would be satisfying and perhaps useful to apply the Gabbay-Pitts model of abstract syntax up to α-equivalence [GP01]. The second author developed an infinitary generalisation of nominal sets [Gab07] which can serve to model permissive nominal terms, and also in fact it is possible to encode permissive nominal terms in (ungeneralised) nominal sets with a very slight effort; these considerations may be included in a journal version of this paper. In this conference paper we seek to make the definitions available, and make a case that this different putting-together of the ideas behind nominal terms works surprisingly well and merits further investigation.

Related work

We have discussed the connection with nominal terms [UPG04] and in the body of the paper we will draw out similarities and differences as we come to them. This work bears the stamp of nominal techniques; two levels of variable symbol (atoms at level 1 and unknowns at level 2), a capturing substitution (instantiation), and α-equivalence managed by permutations and freshness assertions. Like (permissive) nominal terms, higher-order patterns have many of the good properties of first-order terms [Mil91]. A significant difference is that the notion of unification is based squarely on capture-avoiding substitution rather than the (permissive) nominal term capturing substitution and this gives the system’s behaviour a very different flavour. The interested reader is also referred to a recent paper [LV08] which goes some way to teasing out formal connections between these two approaches.

Hamana’s β0 unification of λ-terms with holes adds a capturing substitution [Ham01]. Level 2 variables (which are instantiated) are annotated with level 1 variable symbols that may appear in them; permissive nominal terms move in this direction in the sense that permissions sorts also describe which level 1 variable symbols (we call them atoms in this paper) may appear in them, though with our permissions sorts there are infinitely many that may, and infinitely many that may not. Another significant difference is that the treatment of α-equivalence in Hamana’s system is not nominal (not based on permutations) and unlike our systems, Hamana’s does not have most general unifiers. Similarly Qu-Prolog [NR96] adds level 2 variables, but does not manage α-conversion in nominal style and also, for better or for worse, the system is more ambitious in what it expresses and thus loses mathematical properties (unification is semi-decidable, most general unifiers need not exist).

We refer the interested reader to extended discussions in [UPG04, Section 4]. Permissive nominal terms certainly seem closer to first- and higher-order terms than nominal terms, but they have their own character and are not a special case of previous work.

2 Permissive nominal terms

Definition 3

Fix a bijection γ between natural numbers N = {0, 1, 2, . . .} and A. Define4

comb = {γ(2i) | i ∈N} ⊆A.

Intuitively, comb is a set of ‘every other atom’. Define Permissions inductively by:

comb ∈PermissionsS ∈Permissions S \ {a} ∈PermissionsS ∈Permissions S ∪{a} ∈Permissions

Thus, Permissions is the collection of sets of atoms that differ finitely from comb. We can choose Permissions to be one of many other subsets of the powerset of all atoms; our choice in Definition 3 serves our needs. For Lemma 10 and Corollary 11 to work, it is important that every S ∈ Permissions be such that A \ S is infinite.

Definition 4

For each permissions set S ∈ Permissions fix a countably infinite set of unknowns of permissions sort S. We assume unknowns of distinct permissions sort are distinct. We let XS, Y S, ZS range permutatively over unknowns of sort S. That is, ‘XS and Y S’ means ‘two distinct unknowns of sort S’.

Note that if S, S′ ∈ Permissions and S ≠ S′ then XS and XS′ are distinct unknowns (with misleadingly similar names). If the superscript of an unknown is unimportant or understood then we drop it.

Definition 5

Let permissive nominal terms be defined by:

r, s, t, . . . ::= a | π · XS | [a]r | f(r, . . . , r).

a denotes any atom, S any permissions set, XS any unknown, and f any term-former. We write ≡ for syntactic identity, that is, r ≡s when r and s are identical terms.

Remark 6

Note in passing that if we pick a bijection between A and comb (we can do this because both are countably infinite sets) then we can translate nominal terms in freshness contexts to the permissive framework, bijectively in a suitable formal sense. We omit details in this conference paper, but the intuition is this: we can view nominal terms as a proper subsystem of permissive nominal terms, modulo some minor technical wizardry to help things match up.

Definition 7

Let r be a term. Define the free atoms fa(r) by:

fa(a) = {a} fa(π · XS) = {π(a) | a ∈S}fa([a]r) = fa(r) \ {a} fa(f(r1, . . . , rn)) = fa(r1) ∪· · · ∪fa(rn)
Definition 8

Define a permutation action on terms by:

π · a ≡π(a) π · (π′ · XS) ≡(π◦π′) · XSπ · (f(r1, . . . , rn)) ≡f(π · r1, . . . , π · rn) π · [a]r ≡[π(a)](π · r)

Write id for the identity permutation such that id(a) = a always. Write (a b)·r for the swapping permutation that swaps a and b in the term r. If S ⊆A write π · S for {π(a) | a ∈S}.

Definition 9

If π and π′ are two permutations define ds(π, π′) their difference set by

ds(π, π′) = {a ∈A | π(a) ≠ π′(a)}.

We let α-equivalence =α be inductively defined by:

r =α s(=α[]aa)[a]r =α [a]s(b a) · r =α s (b ∉fa(r))(=α[]ab)[a]r =α [b]s(=αaa)a =α ar1 =α s1· · · rn =α sn(=αf)f(r1, . . . , rn) =α f(s1, . . . , sn)
(ds(π, π′) ∩S = ∅)(=αX)π · XS =α π′ · XS

The validity of r =α s is independent of freshness assumptions, which are now built in to the permissions sorts of the unknowns in r and s. This has quite a different flavour from nominal terms’ α-equivalence which is always in a context of freshness assumptions [UPG04, Figure 2]. Lemma 10 and Corollary 11 are properties that ‘ordinary syntax’ has, that nominal terms do not have, and that permissive nominal terms recover. Lemma 10 states ‘we can always pick a fresh variable’. Corollary 11 states ‘we can always α-rename’.

Lemma 10

For any r, there exist infinitely many b such that b ∉ fa(r).

Proof. By an easy induction on r. We consider only the case r ≡XS. fa(π · XS) = π · S. There are infinitely many b such that such that b ∉π · S.

Corollary 11

For any r and a there exists infinitely many fresh b (so b ∉ fa(r)) such that for some s, [a]r =α [b]s.

Proof. By Lemma 10 and (=α[]ab).

We conclude this section with results whose proofs are essentially identical to those of corresponding properties for nominal terms [UPG04, e.g. Lemma 2.8 and Theorem 2.11]. That is, our changes do not affect basic results about nominal terms:

Lemma 12

π′ · (π · r) ≡ (π′◦π) · r

Lemma 13

π · fa(r) = fa(π · r).

Lemma 14

If r =α s then π · r =α π · s.

Lemma 15

If ds(π, π′) ∩ fa(r) = ∅ then π · r =α π′ · r.

Lemma 16

=α is transitive, reflexive, and symmetric.

3 Substitutions

Definition 17

A substitution σ is a finitely-supported mapping from unknowns to terms such that

for every XS it is the case that fa(σ(XS)) ⊆S.

Finitely-supported means there is a finite set of unknowns D such that if X ∉D then σ(X) = id · X.

σ will range over substitutions. If fa(t) ⊆S we write [XS↦ →t] for the substitution mapping X to t and any other Y to id · Y . Similarly if fa(t) ⊆S and fa(u) ⊆T then we write [XS↦ →t, Y T↦ →u] for the substitution mapping XS to t, Y T to u, and any other Z to id · Z, and so on. We will also write id for the identity substitution, the substitution mapping all unknowns to themselves. It will always be clear from context whether id refers to the identity substitution or the identity permutation.

For example if a ∈ comb then [Xcomb↦→a] is a substitution and [Xcomb\{a}↦→a] is not.

Definition 18

Define a substitution action inductively by:

aσ ≡a f(r1, . . . , rn)σ ≡f(r1σ, . . . , rnσ) ([a]r)σ ≡[a](rσ)(π · XS)σ ≡π · σ(XS)
Lemma 19

π · (rσ) ≡ (π · r)σ.

Proof. By a routine induction on r like that in [GM08].

Distinctly from the case of nominal terms, a substitution only exists if it respects permissions sorts and α-equivalence:

Theorem 20

1. fa(rσ) ⊆ fa(r).

2. r =α s implies rσ =α sσ.

Proof. The first part is proved by a routine induction on r. We consider only the case that r ≡π · XS. By definition fa(π · XS) = π · S. By assumption in Definition 17, since σ is a substitution we know that fa(σ(XS)) ⊆S. Using Lemma 13, it follows that fa(π · σ(XS)) ⊆π · S and π · S ⊆π · S always.

The second part is by a routine induction on the derivation of r =α s. We use Lemma 19, and we use part 1 of this result and Lemma 15 for the case of (=αX), and part 1 for the case of (=α[]ab).

Definition 21

Define fV (r) inductively by:

fV (a) = ∅ fV (π · XS) = {X}fV ([a]r) = fV (r) fV (f(r1, . . . , rn)) = fV (r1) ∪· · · ∪fV (rn)
Theorem 22

If Xσ1 =α Xσ2 for all X ∈ fV (r), then rσ1 =α rσ2.

Proof. By an easy induction on r. The case of r ≡π · X uses Lemma 14.

4 Permissive nominal unification problems

Definition 23

An equality predicate is a pair r ?=? s. An freshness predicate is a pair a #? r. A problem Pr is a finite set of equality and freshness predicates.

We may omit set brackets when we write problems down. For example, b #? Xcomb is a problem; [a]Xcomb?=? [b]Xcomb is a problem; and Xcomb?=? a, a #? Xcomb is a problem.

Definition 24

Call the rules in Figure 1 simplification rules for problems. Write Pr =⇒Pr′ when Pr′ is obtained from Pr by applying a simplification rule. Write ∗=⇒ for the transitive and reflexive closure of =⇒.

Lemma 25

=⇒ is strongly normalising.

That is: there is no infinite chain Pr1 =⇒Pr2 =⇒Pr3 =⇒. . ..

Proof. By induction on derivations, checking that reduction rules strictly reduce a natural measure based on (n, s) where s is the maximum size of term appearing in the problem, and n is the number of terms of that size, lexicographically ordered.

(?=?a) a ?=? a, Pr =⇒Pr(?=?f) f(l1, . . . , ln) ?=? f(s1, . . . , sn), Pr =⇒l1 ?=? s1, . . . , ln ?=? sn, Pr(?=?[]aa) [a]l ?=? [a]s, Pr =⇒l ?=? s, Pr(?=?[]ab) [a]l ?=? [b]s, Pr =⇒(b a) · l ?=? s, b #? l, Pr(?=?X) π · XS ?=? π′ · XS, Pr =⇒{a #? XS | a ∈ds(π, π′) ∩S}, Pr(#?a) a #? b, Pr =⇒Pr(#?X) a #? π · XS, Pr =⇒Pr (π-1(a) ∉S)(#?[]aa) a #? [a]l, Pr =⇒Pr(#?[]ab) a #? [b]l, Pr =⇒a #? l, Pr(#?f) a #? f(l1, . . . , ln), Pr =⇒a #? l1, . . . , a #? ln, Pr
Figure 1: Simplification rules for problems
Theorem 26

=⇒ is confluent and strongly normalising. That is: if Pr∗=⇒ Pr1 and Pr∗=⇒Pr2 then there exists some Pr3 such that Pr1∗=⇒Pr3 and Pr2∗=⇒Pr3, and each Pr rewrites to a unique normal form.

Proof. For each predicate there is at most one applicable rewrite rule, hence reductions are locally confluent. (That is: if Pr =⇒Pr1 and Pr =⇒Pr2 then there exists some Pr3 such that Pr1∗=⇒Pr3 and Pr2∗=⇒Pr3.) The result follows from Newman’s Lemma [New42] and Lemma 25.

5 Unification of permissive nominal terms

Definition 27

Call a substitution σ idempotent when XSσ ≡XSσσ for all XS.

Definition 28

Write

Prσ for {rσ =α sσ | r =α s ∈Pr} ∪{a #? rσ | a #? r ∈Pr}.
Definition 29

A (unification) solution to a problem Pr is an idempotent substitution σ such that:5

• If r ?=? s ∈Pr then rσ =α sσ.

• If a #? r ∈Pr then a ∉ fa(rσ).

Write Sol(Pr) for the set of solutions to Pr. We will call Pr solvable when Sol(Pr) is non-empty (i.e. when a solution to Pr exists).

Remark 30

A solution to Pr is a substitution which ‘makes the equalities and freshness problems valid’, just as for first- and higher-order unification; this is simpler than the notion of solution in in nominal unification [UPG04, Definition 3.1], based on ‘a substitution + a primitive freshness context’. Note also (I3) below in Definition 35, which does not appear in the theory of nominal unification.

Permissive nominal terms have a distinctly ‘nominal’ flavour but we design them to have simpler behaviour, and of a kind which is closer to the theory of first- and higher-order unification: One of the motivations for considering nominal terms is the slogan ‘ϵ away from informal practice’. In several respects, permissive nominal terms manage to get even closer to informal practice. We now proceed with the proofs, culminating with Theorem 42.

Lemma 31

If Pr =⇒Pr′ then Sol(Pr) = Sol(Pr′).

Proof. By a long but routine verification we check all the simplification rules in Figure 1 and see that σ solves Pr if and only if σ solves Pr′.

Definition 32

Define the instantiation ordering on solutions by

σ1 ≤σ2 when σ′ exists such that XSσ1σ′ =α XSσ2 for all XS.

We may also write σ1 ≤σ′ σ2 if the substitution σ′ is important. Intuitively σ1 ≤σ2 when σ1 ◦σ′ =α σ2 for some σ′. Note that substitutions post-compose.

Lemma 33

≤ is reflexive and transitive.

Proof.

• Reflexive. We take σ′ = id and use Lemma 16.

• Transitive. Suppose σ1 ≤σ2 and σ2 ≤σ3. So there exist σ′ and σ′′ such that

XSσ1σ′ =α XSσ2and XSσ2σ′′ =α XSσ3for every XS. By Lemma 16 and Theorem 20 we have XSσ1σ′σ′′ =α XSσ3 for every XS.
Definition 34

A principal (or most general) solution to Pr is a solution σ ∈ Sol(Pr) such that σ ≤σ′ for all other σ′ ∈ Sol(Pr).

Definition 35

Let instantiating rules be:

(I1) π · XS ?=? s, PrXS↦→π-1·s=⇒ Pr[XS↦ →π-1 · s] (XS ∉fV (s), π-1 · fv(s) ⊆S)(I2) r ?=? π · XS, PrXS↦→π-1·r=⇒ Pr[XS↦ →π-1 · r] (XS ∉fV (r), π-1 · fv(r) ⊆S)(I3) a #? π · XS, PrXS↦→XS\{π-1(a)}=⇒ Pr[XS↦ →XS\{π-1(a)}] (XS\{π-1(a)} ∉fV (Pr), π-1(a) ∈S)

As is standard, we call ‘XS ∉ fV (r)’ the occurs check. In (I3), XS\{π-1(a)} is a choice of a fresh unknown of the correct sort. Note that the case of π-1(a) ∉S is handled by (#?X) in Figure 1.

Note that (I3) is absent from nominal unification [UPG04, Figure 3]; there, a#X is recorded as part of the solution (rule (#?-suspension)).

Here a, b, c ∈ comb and we write S = comb \ {a} and T = comb.

λ[a]λ[b](XSb) ?=? λ[b]λ[a](aY T )(?=?f,?=?[]aa)=⇒ {λ[a](((b a) · XS)a) ?=? λ[a](aY T ), b #? λ[b](XSb)}(?=?f,?=?[]aa,?=?f,#?f,#?[]aa)=⇒ {(b a) · XS?=? a, a ?=? Y T }(I1), XS↦→b=⇒ { a ?=? Y T }(I2), Y T↦ →a=⇒ {} Solution: [XS↦ →b, Y T↦ →a]λ[c]λ[b](bXS) ?=? λ[c]λ[c](cY T )(?=?f,?=?[]aa)=⇒ {λ[b](bXS) ?=? λ[c](cY T )}(?=?f,?=?[]ab)=⇒ {c((b c) · XS) ?=? cY T , c #? bXS}(?=?f,?=?a,I1), Y T↦ →(b c)·XS=⇒ {(b c) · XS?=? (b c) · XS, c #? bXS}(?=?X,#?f,#?a)=⇒ {c #? XS}(I3), XS↦→XS\{c}=⇒ {} Solution: [Y T↦ →(b c) · XS\{c}, XS↦ →XS\{c}]λ[a]λ[b](bXS) ?=? λ[a]λ[a](aY T )(?=?f,?=?[]aa)=⇒ {λ[b](bXS) ?=? λ[a](aY T )}(?=?f,?=?[]ab)=⇒ {a((b a) · X) ?=? aY, a #? bXS}(?=?f,?=?a, I1), Y T↦ →(b a)·XS=⇒ {(b a) · X ?=? (b a) · X, a #? bX}(?=?X,#?f,#?a)=⇒ {a #? XS}(#?X)=⇒ {} Solution: [Y T↦ →(b a) · XS]
Figure 2: Examples of the permissive nominal unification algorithm in action.
Definition 36

Define a unification algorithm as follows:

1. Reduce the problem using simplification rules from Figure 1, as much as possible.

2. Reduce the problem using an instantiation rule from Defininition 35.

3. Repeat steps 1 and 2 as much as possible. If we reduce the problem to ∅ then we succeed and return the functional composition in order of all substitutions annotating instantiation rules; otherwise we fail.

We give three examples of the unification algorithm in action in Figure 2. The interested reader can compare these with corresponding examples in [FG07, Figure 1, page 29]. Reductions always terminate because at each step either a formula becomes smaller, or the number of unknowns in the problem is reduced by one.

Lemma 37

Suppose that

σ1 ≤σ′ σ2σ1(XS) ≡XSX ∉fV (t).

Then [XS↦ →t]◦σ1 ≤σ′ [XS↦ →t]◦σ2.

Proof. Unpacking Definition 32, we see that we must show

Y ([X↦ →t]◦σ1◦σ′) =α Y ([XS↦ →t]◦σ2) for all Y

There are two cases:

• The case Y ≡XS. We must show tσ1σ′ =α tσ2. This follows by Theorem 22.

• The case Y ≢XS. We must show Y σ1σ′ =α Y σ2. This is by assumption.

Definition 38

Write σ −XS for the substitution such that

• (σ −XS)(XS) ≡XS and

• (σ −XS)(Y T) ≡σ(Y T) for all other Y T.

Lemma 39

π·XSσ′ =α sσ′ and X ∉ fV (s) imply σ′ =α [XS↦→π-1·s]◦(σ′−XS).

Proof. We reason as follows:

π · XSσ′=α(π · XS)([XS↦ →π-1 · s]◦(σ′ −XS)) Lemma 12≡ s(σ′ −XS)≡ s[XS↦ →π-1 · s]◦(σ′ −XS) XS ∉fV (s)≡ sσ′
Lemma 40

If Prσ=⇒∗Pr′ and σ′ ∈ Sol(Pr′) then σ◦σ′ ∈ Sol(Pr).

Proof. Suppose Prσ=⇒∗Pr′. There are two cases:

− The case for (I1) and (I2). The following conditions hold:

−Pr = {π · X ?=? r} ∪Pr′′ or Pr = {r ?=? π · X} ∪Pr′′, −X ∉fV (r), −σ ≡[X↦ →π-1 · r], and −Pr′ = Pr′′σ.

Suppose also that σ′ ∈ Sol(Pr′). Then σ′ is idempotent and Pr′′(σ◦σ′) = Pr′σ′. It is easy to verify that σ ◦σ′ is idempotent. By Lemmas 19 and 14 we conclude (π · X)(σ◦σ′) =α r(σ◦σ′) and the result follows.

− The case (I3). Suppose Pr = {a #? π · XS} ∪Pr′′ and Prσ=⇒Pr′′σ with σ ≡ [XS↦ →XS\{π-1(a)}] and π-1(a) ∈S. Further, suppose σ′ ∈ Sol(Pr′′σ).

Then σ◦σ′ ∈ Sol(Pr′′) and it suffices to show that a#(π · XS\{π-1(a)})σ′. This follows immediately from Definition 17, and we have the result.

Theorem 41

If Prσ=⇒∗∅ then σ ∈ Sol(Pr).

Proof. By induction on the length of the path in σ=⇒∗. − Path length 0. Then Pr = ∅ and σ ≡ id. The result follows. − Path length k + 1. There are two cases: − The non-instantiating case. Suppose Pr =⇒Pr′σ=⇒∗∅. By Lemma 31, Sol(Pr) = Sol(Pr′), and the result follows by the inductive hypothesis.

− The instantiating case. Suppose Prσ=⇒Pr′σ′=⇒∗∅ and σ′′ = σ◦σ′. It follows by the inductive hypothesis that σ′ ∈ Sol(Pr′) and the result follows by Lemma 40.

Theorem 42

If Prσ=⇒∗∅ then σ is a principal solution to Pr. Unpacking Definition 34 this means that σ ∈ Sol(Pr) and if σ′ ∈ Sol(Pr) then σ ≤σ′.

Proof. By Theorem 41 σ ∈ Sol(Pr). We work by induction on the path length of Prσ=⇒∗∅ showing that it is principal. − Path length 0. Then Pr = ∅ and σ = id. Suppose σ′ ∈ Sol(Pr). Then XS(id ◦σ′) ≤XSσ′ for all XS. The result follows. − Path length k + 1. There are two cases:

− The non-instantiating case. Suppose Pr =⇒Pr′σ=⇒∗∅ where Pr =⇒Pr′ is a non-instantiating simplification. By inductive hypothesis, σ is a principal solution of Pr′, and by Lemma 31, σ is also a principal solution of Pr. The result follows.

− The instantiating case. There are two cases:

− The cases (I1) and (I2). Without loss of generality, suppose Pr ∪{π · XS ?=? r}σ=⇒Prσ and Prσ′=⇒∗∅, where σ ≡ [XS↦ →π-1 · r]. Further, suppose σ′′ ∈ Sol(Pr∪{π·XS ?=? r}). By Lemma 40, σ′′−XS ∈ Sol(Prσ), therefore by inductive hypothesis and Theorem 41, σ′ ≤σ′′ −XS. By Lemma 37, σ◦σ′ ≤σ◦(σ′′ −XS). By Lemma 39, σ′′ =α σ◦(σ′′ −XS) hence σ◦(σ′′ −XS) ≤σ′′. Therefore, using Lemma 33, we have σ◦σ′ ≤σ′′, as required.

− The case (I3). Suppose Pr ∪{a #? XS}σ=⇒Prσ and Prσ′=⇒∗∅, where σ ≡ [XS↦ →XS\{a}], π-1(a) ∈S, and XS\{a} ∉ fV (Pr). By inductive hypothesis σ′ is a principal solution for Prσ. By Lemma 40 σ◦σ′ ∈ Sol(Pr∪ {a #? XS}). The result follows by Lemma 31.

Theorem 43

Given a problem Pr, if the algorithm of Definition 36 succeeds then it returns a principal solution; if it fails then there is no solution.

Proof. If the algorithm fails then it does so because it reduces Pr to a problem that can have no solution because it contains an equality or freshness predicate of the form f(. . .) ?=? g(. . .), f(. . .) ?=? [a]s, f(. . .) ?=? a, a #? a, or π·XS ?=? s where π-1 · fa(s) ⊈S (we elide symmetric cases). In that case by Lemmas 31 and 40 no solution to Pr can exist. If the algorithm succeeds, the result follows by Theorem 42.

References

[BU07]Stefan Berghofer and Christian Urban. A head-to-head comparison of de Bruijn indices and names. Electronic Notes in Theoretical Computer Science, 174(5):53– 67, 2007.

[Che05]James Cheney. Nominal logic and abstract syntax. SIGACT News (logic column 14), 36(4):47–69, 2005.

[CP07]Ranald A. Clouston and Andrew M. Pitts. Nominal equational logic. Electronic Notes in Theoretical Computer Science, 172:223–257, 2007.

[CU03]J. Cheney and C. Urban. System description: Alpha-Prolog, a fresh approach to logic programming modulo alpha-equivalence. Technical Report DSIC-II/12/03, Departamento de Sistemas Informaticos y Computacion, Universidad Politecnica de Valencia, 2003.

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

[Dow01]Gilles Dowek. Higher-order unification and matching. In Handbook of automated reasoning, pages 1009–1062. Elsevier, 2001.

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

[FG07]Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205(6):917–965, 2007.

[Gab07]Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205:982–1011, July 2007.

[Gab08]Murdoch J. Gabbay. Nominal algebra and the HSP theorem. Journal of Logic and Computation, 2008. To appear.

[GL08]Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. Electronic Notes in Theoretical Computer Science, 196:19–35, 2008.

[GM07]Murdoch J. Gabbay and Aad Mathijssen. A formal calculus for informal equality with binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162– 176, 2007.

[GM08]Murdoch J. Gabbay and Dominic P. Mulligan. Two-and-a-halfth Order Lambda-calculus. In Workshop on Functional and Logic Programming (WFLP), 2008. To appear.

[GP99]Murdoch J. Gabbay and Andrew M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214–224. IEEE Computer Society Press, 1999.

[GP01]Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341– 363, 2001.

[Ham01]Makoto Hamana. A logic programming language based on binding algebras. In TACS’01, volume 2215 of Lecture Notes in Computer Science, pages 243–262. Springer, 2001.

[LV08]Jordi Levy and Mateu Villaret. Nominal unification from a higher-order perspective. In Proceedings of RTA’08, volume 5117 of Lecture Notes in Computer Science. Springer, 2008.

[Mat07]Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.

[Mil91]Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1(4):497 – 536, 1991.

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

[NR96]Peter Nickolas and Peter J. Robinson. The Qu-Prolog unification algorithm: formalisation and correctness. Theoretical Computer Science, 169(1):81–112, 1996.

[Pit02]Andrew M. Pitts. Equivariant syntax and semantics. In Proceedings of ICALP’02, pages 32–36. Springer, 2002.

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

Centre de recherche INRIA Saclay – Île-de-France

Parc Orsay Université - ZAC des Vignes 4, rue Jacques Monod - 91893 Orsay Cedex (France)

Centre de recherche INRIA Bordeaux – Sud Ouest : Domaine Universitaire - 351, cours de la Libération - 33405 Talence Cedex Centre de recherche INRIA Grenoble – Rhône-Alpes : 655, avenue de l’Europe - 38334 Montbonnot Saint-Ismier Centre de recherche INRIA Lille – Nord Europe : Parc Scientifique de la Haute Borne - 40, avenue Halley - 59650 Villeneuve d’Ascq Centre de recherche INRIA Nancy – Grand Est : LORIA, Technopôle de Nancy-Brabois - Campus scientifique

615, rue du Jardin Botanique - BP 101 - 54602 Villers-lès-Nancy Cedex Centre de recherche INRIA Paris – Rocquencourt : Domaine de Voluceau - Rocquencourt - BP 105 - 78153 Le Chesnay Cedex Centre de recherche INRIA Rennes – Bretagne Atlantique : IRISA, Campus universitaire de Beaulieu - 35042 Rennes Cedex Centre de recherche INRIA Sophia Antipolis – Méditerranée : 2004, route des Lucioles - BP 93 - 06902 Sophia Antipolis Cedex

Éditeur INRIA - Domaine de Voluceau - Rocquencourt, BP 105 - 78153 Le Chesnay Cedex (France)

http://www.inria.fr

ISSN 0249-6399

Notes

1For fully general theories of computation and equality on nominal terms, see nominal rewriting and nominal algebra [FG07, GM07, Mat07, Gab08]. ↩

2We use examples from the λ-calculus only as a paradigmatic instance of the general theory which nominal terms model. Note that [y/x] is a renaming, not a permutation (permutations are bijective, renamings are not). The case for prefering permutations to develop a theory of α-equivalence has been made in detail in the literature, for example in [Che05]. ↩

3We encountered this before and dealt with it in two ways. In [GM07, Figure 2, axiom (fr)] and in [GM08, e.g. Lemma 25 and Theorem 33] we ‘freshly extend’ the freshness context. Alternatively we can extend nominal terms syntax with an explicit fresh names construct as in for example [GL08, FG05]. ↩

4Nominal sets [GP01] famously only allow elements with finite support. However, we are working at the meta-level, where we can talk about any subset or function that we wish. ↩

5The condition that σ be idempotent is not absolutely necessary, but it is technically convenient. Our algorithms will generate idempotent solutions so we lose no generality that we care about here. ↩