Nominal Unification
University of Cambridge, Cambridge, UK.
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 an existing idea and introducing a key new idea. The existing idea is terms involving explicit substitutions of names for names, except that here we only use explicit permutations (bijective substitutions). The key new idea 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 the classical first-order unification algorithm 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.
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 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 [6], or context substitution [12, Sect. 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:
Here , and are metavariables standing for unknown programming language expressions. The binders and may very well capture free occurrences of when we instantiate the schematic rule by replacing the metavariable with an expression. For instance, using the rule scheme in a bottom-up search for a proof of
we would use a substitution that does involve capture, namely , to unify the goal with the conclusion of the rule—generating the new goal 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
is the same as (2). We might think (erroneously!) that the conclusion of rule (1) is the same as 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 , and then apply this substitution to the hypothesis to obtain a wrong goal, . 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, rule (1) would be replaced by
Now goal (3) becomes and there is no problem unifying it with the conclusion of (4) via a capture-avoiding substitution of for , for and for .
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 [5] 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 [6, 13, 15, 26]. 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 explicit permutations of names. The idea of using name-permutations, and in particular name-swappings, when dealing with -conversion dates back to [9] and there is growing evidence of its usefulness (see [3, 4], 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 and , where , and are distinct. If we apply the substitution (renaming all free occurrences of to be ) to them we get and , 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 that swaps all occurrences of and (be they free, bound or binding) to the terms above gives and , 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. This seems to be the key novelty of our approach. Although it arises naturally from the work reported in [10, 23], it is easy to see directly why there is a need for computing with freshness, given that we take a ‘nominal’ approach to binders. (In other words we stick with concrete versions of binding and -equivalence in which the bound entity is named explicitly, rather than using de Bruijn-style representations, for example as in [6, 26].) A basic instance of our generalised form of -equivalence identifies, for example, with provided is fresh for , where the subterm indicates an explicit permutation—namely the swapping of and —waiting to be applied to . We write ‘ is fresh for ’ symbolically as ; the intended meaning of this relation is that does not occur free in any (ground) term that may be substituted for . If we know more about we may be able to eliminate the explicit permutation in ; for example, if we knew that holds as well as , then can be replaced by . It should already be clear from these simple examples that in our setting the appropriate notion of term-equality is not a bare equation, , but rather a hypothetical judgement of the form
where is a freshness environment, i.e. a finite set of freshness assumptions. For example is a valid judgement of our nominal equational logic. Similarly, judgements about freshness itself will take the form
To summarise: We will represent languages involving binders using the usual notion of first-order terms over a many-sorted signature. These give us terms with: distinguished constants naming bindable entities, that we call atoms; terms expressing a generic form of binding of an atom in a term ; and terms representing an explicit permutation of atoms waiting to be applied to whatever term is substituted for the variable . Section 2 presents this term-language together with a syntax-directed inductive definition of the provable judgements of the form (5) and (6) which for ground terms (i.e. ones with no variables) agrees with the standard relations of -equivalence and ‘not a free variable of’. However, on open terms our judgements differ from these standard relations and appear to be an extension that has, in this form, not yet been studied in the literature (including [10, 24, 23]). Section 3 considers unification problems in this setting. Solving equalities between abstractions () entails solving both equalities () and freshness problems (). Therefore our general form of nominal unification problem is a finite collection of individual equality and freshness problems. Such a problem 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 and hold for each individual equality and freshness in the problem . 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 which is very similar to the first-order algorithm given in the now-common transformational style [18]. (See [17, Sect. 2.6] or [1, Sect. 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. 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.
Quiz Assuming that and are distinct variables, is it possible to find -terms that make the following pairs of terms -equivalent?
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?
2 Nominal equational logic
We take a concrete approach to the syntax of binders in which bound entities are explicitly named. Furthermore we separate the names of bound entities from the names of variables, which is inspired for example by 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 [10]) 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 [25, 8], 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).
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 ), each of which has an arity of the form . Here ranges over (compound) sorts given by the grammar
Terms of sort are binding abstractions of atoms of sort over terms of sort . We will explain the syntax and properties of such terms in a moment.
Here is a nominal signature for expressions in a small fragment of ML:
The function symbol constructs terms of sort representing value identifiers (named by atoms of sort ); constructs application expressions from pairs of expressions; , and construct terms representing respectively function abstractions (), local value declarations ( ) and local recursive function declarations (). The arities of the function symbols specify which are binders and in which way their arguments are bound. This kind of specification of binding scopes is of course a feature of higher-order abstract syntax [22], 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. To make this point clear we deliberately use a first-order syntax for terms, and not higher-order abstract syntax, although we often refer to abstractions, binders and free atoms by analogy with the -calculus.
Given a nominal signature, we assume that there are countably infinite and pairwise disjoint sets of atoms (typical symbol ) for each sort of atoms , and variables (typical symbol ) for each sort . The terms over a nominal signature and their sorts are inductively defined as follows, where we write to indicate that a term has sort .
Unit value .
Pairs , if and .
Data , if is a function symbol of arity and .
Atoms , if is an atom of sort .
Atom-abstraction , if is an atom of sort and .
Suspension , if is a finite list whose elements are pairs of atoms, with and of the same sort, and is a variable of sort . In the case that is the empty list , we just write for .
Recall that every finite permutation can be expressed as a composition of swappings ; the list of pairs of atoms occurring in a suspension term specifies a finite permutation of atoms waiting to be applied once we know more about the variable (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 role in the theory. Since, semantically speaking (see Remark 1 below about semantics), 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 (cf. Fig. 1 below); the terms in Definition 2 are all normalised in this way, with explicit swappings ‘piled up’ in front of variables giving what we have called suspensions.
We wish to give a definition of -equivalence for terms over a nominal signature that 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 () need to contain hypotheses about the freshness of atoms with respect to variables (); and the same goes for our judgements about freshness itself (). Figure 2 gives a syntax-directed inductive definition of equivalence and freshness using judgements of the form
where and are terms of the same sort over a given nominal signature, is an atom, and the freshness environment is a finite set of freshness constraints , each specified by an atom and a variable. Rules (-abstraction-2), (-suspension) and (-suspension) in Fig. 2 make use of the following definitions.
Recall from Definition 2 that we specify finite permutations of atoms by finite lists representing the composition of finitely many swappings , with and of the same sort. Since we will apply permutations to terms on the left, the order of the composition is from right to left. So with this representation, the composition of a permutation followed by a swap is given by list-cons, written ; 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 . The permutation action, , of a finite permutation of atoms on a term is defined as in Fig. 1; it pushes the list into the structure of the term until it ‘piles up’ in front of suspensions (applying the actual permutation that represents to atoms that it meets on the way). The disagreement set of two permutations and (used in rule (-suspension) in Fig. 2) is defined by
Note that every disagreement set of the lists and is a subset of the finite set of atoms occurring in either of the lists, since if does not occur in those lists, then from Fig. 1 we get . To illustrate the use of disagreement sets, consider
which holds by (-suspension), because the disagreement set of and is .
is an equivalence relation; it is preserved by all of the term-forming operations in Definition 2; and it respects the freshness relation (i.e. if and , then ). Both and are preserved by the permutation action given in Fig. 1 in the following sense: if , then ; and if , then .
Although reasoning about and is rather pleasant once the above facts are proved, establishing them first is rather tricky—mainly because of the large number of cases, but also because the facts in the lemma depend on each other which prevents to use any ‘short-cut’; in addition some further properties of the permutation action and disagreement sets need to be established first (statements omitted).1
The main reason for using suspensions in the syntax of terms is to enable a definition of substitution of terms for variables which 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.
A substitution is a sort-respecting function from variables to terms with the property that for all but finitely many variables . We shall write for the finite set of variables satisfying . If consists of distinct variables and for , we shall sometimes write as
We write for the result of applying a substitution to a term ; this is the term obtained from by replacing each suspension in (as ranges over ) by the term got by letting act on the term using the definition in Fig. 1. For example, if and , then .
Given substitutions and , and freshness environments and , we write
to mean that (for a) holds for each and (for b) holds for all .
Substitution commutes with the permutation action: . Substitution preserves and in the following sense:
if and , then ;
if and , then .
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 Lemma 1 and the fact that, by definition, it satisfies rules (-abstraction-1) and (-abstraction-2). Further evidence is provided by the following theorem, which shows that for ground terms agrees with the following more traditional definition of -equivalence.
Define the binary relation between the terms over a nominal signature to be the least sort-respecting congruence relation satisfying whenever is an atom (of the same sort as ) not occurring at all in the term . Here indicates the result of replacing all free occurrences of with in .
If and are ground terms (i.e. terms with no variables and hence no suspensions) over a nominal signature, then the relation of Definition 5 holds if and only if is provable from the rules in Fig. 2. Furthermore, is provable if and only if is not in the set of free atoms of .
The proof is similar to the proof of [10, Proposition 2.2].
For non-ground terms, the relations and differ. For example always holds, whereas is not provable unless . This disagreement is to be expected, since we noted in the Introduction that is not preserved by substitution, whereas from Lemma 2 we know that is.
3 Unification
Given terms and of the same sort over a nominal signature, can we decide whether or not there is a substitution of terms for the variables in and that makes them equal in the sense of the relation introduced in the previous section? Since instances of in general 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 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.
A unification problem over a nominal signature is a finite set of atomic problems, each of which is either an equational problem where and are terms of the same sort over the signature, or a freshness problem where is an atom and a term over the signature. A solution for consists of a pair where is a freshness environment and is a substitution satisfying
Such a pair is a most general solution for if given any other solution , then there is a substitution satisfying and . (Here we have used the notation of (9); and denotes the substitution composition of followed by , given by .)
There is an algorithm which, given any nominal unification problem, decides whether or not it has a solution and if it does, returns a most general solution.
We describe an algorithm using labelled transformations directly generalising the presentation of first-order unification in [17, Sect. 2.6], which in turn is based upon the approach in [18]. (See also [1, Sect. 4.6] for a detailed exposition, but not using labels.) We use two types of labelled transformation between unification problems, namely
where the substitution is either the identity , or a single replacement ; and where the freshness environment is either empty , or a singleton . The legal transformations are given in Fig. 3. This figure uses the notation to indicate disjoint union of problem sets; and the notation to indicate the problem resulting from applying the substitution to all the terms occurring in the problem .
Given a unification problem , the algorithm proceeds in two phases. 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 with 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 with failure; otherwise overall it has constructed a transformation sequence of the form
(where does not contain any equational subproblems) and the algorithm returns the solution .
It is not hard to devise a well-founded ordering on nominal unification problems to show that each phase of the algorithm must terminate. So one just has to show that
(a) if the algorithm fails on , then has no solution; and
(b) if the algorithm succeeds on , then the result it produces is a most general solution.
When failure happens it is because of certain subproblems that manifestly have no solution (e.g. in the first phase, with , and or with occurring in ; in the second phase, ). Therefore part (a) is a consequence of the following two properties of transformations, where we write for the set of all solutions for a problem :
For part (b), one first shows
From these and the fact that , one gets that if a sequence like (10) exists, then is in . Furthermore from (11) and (12), we get that any other solution satisfies and , so that is indeed a most general solution.
Using the first three function symbols of the nominal signature of Example 1 to represent -terms, the Quiz at the end of the Introduction translates into the following four unification problems over that signature, where and are distinct atoms of sort and are distinct variables of sort :
Applying the nominal unification algorithm described above, we find that
has no solution;
has a most general solution given by and ;
has a most general solution given by and ;
has a most general solution given by and .
Derivations for and are sketched in Fig. 4. Using the Adequacy Theorem 1, one can interpret these solutions as the following statements about the -terms from the quiz.
Quiz answers
1. There is no -term making the first pair of terms -equivalent.
2. The only solution for the second problem is to take and .
3. For the third problem we can take to be any -term, so long as we take to be the result of swapping all occurrences of and throughout .
4. For the last problem, we can take to be any -term that does not contain free occurrences of , so long as we take to be the result of swapping all occurrences of and throughout , or equivalently (since is not free in ), taking to be the result of replacing all free occurrences of in with .
Nominal unification unifies variables, but it does not unify atoms. Indeed the operation of identifying two atoms by renaming does not necessarily preserve the validity of the judgements in Fig. 2. For example, holds if
; but renaming to be in this judgement we get , which does not hold so long as . Referring to Definition 2, 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 is such a variable, then it cannot appear in abstraction position, i.e. as . 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) 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 , where , and are variables of atom sort; this has two incomparable solutions, namely and .
4 Related work
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 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. However it imposes a restriction on the form of -terms to be unified; namely 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 restriction, but that it rules out some useful programming idioms. For us, the main disadvantage of is one common to most approaches based on higher-order abstract syntax: one cannot directly express the common idiom of possibly-capturing substitution of terms for metavariables. Instead one has to replace metavariables, , with function variables applied to distinct lists of (bound) variables, , and use capture-avoiding substitution.
Hamana [13, 14] manages to add possibly-capturing substitution to a language like Miller’s . 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 [8]. The mathematical foundation for our work appeared concurrently [9] 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.
Relevant to nominal unification is also the work by Dowek et al [6, 7], which presents two unification algorithms for (a -calculus with de-Bruijn indices and explicit substitutions): one for encoding higher-order unification problems into , and the other for encoding higher-order pattern unification problems. Although unification problems in are solved, like in nominal unification, by textual replacements of terms for variables, a ‘pre-cooking’ operation ensures that the textual replacements can be (faithfully) related to capture-avoiding substitutions. We conjecture that nominal unification problems can be encoded into Dowek et al’s variant of the higher-order pattern unification using a non-trivial translation that makes use of specific features of de-Bruijn indices and explicit substitutions. The details of this encoding still remain to be investigated. But even if it turns out that it is possible to simulate nominal unification in , the calculations involved in translating our terms into and then using their unification algorithm are far more intricate than our simple algorithm that solves nominal unification problems directly. We do not expect that a similar encoding is possible into Miller’s original higher-order pattern unification algorithm.
5 Conclusion
In this paper we have proposed a solution to the problem of finding 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’ is the main novelty—it arises from the work reported in [10, 23]. It leads 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.
Currently we 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 following Prolog-like program, which implements a simple typing algorithm for -terms.
Interesting is the third clause. 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 to the context Gamma. Second, 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
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 [24] and . We are also interested in the special case of ‘nominal matching’ and its application to term-rewriting modulo -equivalence.
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 easier2 rather than for efficiency. In any case, it remains to be investigated whether the swapping and freshness computations that we have added to ordinary, first-order unification result in greater than linear-time complexity.
Acknowledgements: We thank Gilles Dowek, Roy Dyckhoff, Dale Miller, Francois Pottier and Helmut Schwichtenberg for comments on this work; and Andy Gordon for coining the term ‘nominal’ [11] which we have highjacked. This research was supported by UK EPSRC grants GR/R29697 (Urban) and GR/R07615 (Pitts and Gabbay).
References
1. F. Baader and T. Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.
2. H. P. Barendregt. The Lambda Calculus: Its Syntax and Semantics. North-Holland, 1984.
3. L. Caires and L. Cardelli. A spatial logic for concurrency II. In Proceedings of CONCUR 2002, volume 2421 of LNCS, pages 209–225. Springer-Verlag, 2002.
4. L. Cardelli, P. Gardner, and G. Ghelli. Manipulating trees with hidden labels. Submitted.
5. G. Dowek. Higher-order unification and matching. In A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, chapter 16, pages 1009–1062. Elsevier, 2001.
6. G. Dowek, T. Hardin, and C. Kirchner. Higher-order unification via explicit substitutions. In 10th Symposium of LICS, pages 366–374. IEEE Computer Society Press, 1995.
7. G. Dowek, T. Hardin, C. Kirchner, and F. Pfenning. Higher-order unification via explicit substitutions: the case of higher-order patterns. In Proceedings of JICSLP, pages 259–273, 1996.
8. M. P. Fiore, G. D. Plotkin, and D. Turi. Abstract syntax and variable binding. In 14th Symposium of LICS, pages 193–202. IEEE Computer Society Press, 1999.
9. M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax involving binders. In 14th Symposium of LICS, pages 214–224. IEEE Computer Society Press, 1999.
10. M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13:341–363, 2002.
11. A. D. Gordon. Nominal calculi for security and mobility. In DARPA Workshop on Foundations for Secure Mobile Code, pages 10–14, Naval Postgraduate School, Monterey, 1997.
12. C. A. Gunter. Semantics of Programming Languages: Structures and Techniques. Foundations of Computing. MIT Press, 1992.
13. M. Hamana. A logic programming language based on binding algebras. In Proceedings of TACS 2001, volume 2215 of LNCS, pages 243–262. Springer-Verlag, 2001.
14. M. Hamana. Simple -unification for terms with context holes. In 16th International Workshop on Unification (UNIF 2002), 2002. Unpublished proceedings.
15. M. Hashimoto and A. Ohori. A typed context calculus. TCS, 266:249–271, 2001.
16. F. Honsell, M. Miculan, and I. Scagnetto. An axiomatic approach to metareasoning on nominal algebras in HOAS. In Proceedings of ICALP 2001, volume 2076 of LNCS, pages 963–978. Springer-Verlag, 2001.
17. J. W. Klop. Term rewriting systems. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, Volume 2, pages 1–116. OUP, 1992.
18. A. Martelli and U. Montanari. An efficient unification algorithm. ACM Trans. Programming Languages and Systems, 4(2):258–282, 1982.
19. S. Michaylov and F. Pfenning. An empirical study of the runtime behaviour of higher-order logic programs. In Proc. Workshop on the Prolog Programming Language, pages 257–271, 1992. CIS Technical Report MS-CIS-92-86.
20. D. Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1:497–536, 1991.
21. R. Milner, J. Parrow, and D. Walker. A calculus of mobile processes (parts I and II). Information and Computation, 100:1–77, 1992.
22. F. Pfenning and C. Elliott. Higher-order abstract syntax. In Proc. ACM-SIGPLAN Conference on Programming Language Design and Implementation, pages 199–208. ACM Press, 1988.
23. A. M. Pitts. Nominal logic: A first order theory of names and binding. In Proceedings of TACS 2001, volume 2215 of LNCS, pages 219–242. Springer-Verlag, 2001.
24. A. M. Pitts and M. J. Gabbay. A metalanguage for programming with bound names modulo renaming. In Proceedings of MPC2000, volume 1837 of LNCS, pages 230–255. Springer-Verlag, 2000.
25. G. D. Plotkin. An illative theory of relations. In Situation Theory and its Applications, volume 22 of CSLI Lecure Notes, pages 133–146. Stanford University, 1990.
26. M. Sato, T. Sakurai, and Y. Kameyama. A simply typed context calculus with first-class environments. Journal of Functional and Logic Programming, 2002(4), 2002.
Notes
1 A machine-checked proof of all the results using the theorem prover Isabelle can be found at . ↩
2 See for the Isabelle proof scripts. ↩