Permissive nominal terms and their unification: an infinite, co-infinite approach to nominal techniques
Source watermark: DRAFT
Abstract
Nominal terms extend first-order terms with binding. They lack some properties of first- and higher-order terms: Terms must be reasoned about in a context of ‘freshness assumptions’; it is not always possible to ‘choose a fresh variable symbol’ for a nominal term; it is not always possible to ‘-convert a bound variable symbol’ or to ‘quotient by -equivalence’; the notion of unifier is not based just on substitution.
Permissive nominal terms closely resemble nominal terms but they recover these properties, and in particular the ‘always fresh’ and ‘always rename’ properties. In the permissive world, freshness contexts are elided, equality is fixed, and the notion of unifier is based on substitution alone rather than on nominal terms’ notion of unification based on substitution plus extra freshness conditions.
We prove that expressivity is not lost moving to the permissive case and provide an injection of nominal terms unification problems and their solutions into permissive nominal terms problems and their solutions.
We investigate the relation between permissive nominal unification and higher-order pattern unification. We show how to translate permissive nominal unification problems and solutions in a sound, complete, and optimal manner, in suitable senses which we make formal.
Keywords: Nominal unification, higher-order pattern unification, permissive nominal techniques
$Thanks to the anonymous referees.
1. Introduction
1.1. About nominal terms and permissive nominal terms
Many formal languages feature names and binding: examples include quantification, -abstraction, sets comprehension
In contrast, variables cannot be bound in first-order terms: In first-order logic, variables are bound in propositions by quantifiers and not at all in terms; first-order rewriting does not allow binding as it is based on first-order terms; and, many programming languages and proof systems allow datatypes of terms, but only of first-order terms.
This motivates logics where variables can be bound by any function or predicate symbol [9], extensions of rewriting on terms with binders [28, 30, 10], and programming languages and proof systems allowing datatypes with binders [36, 31, 39, 27, 35] and more generally, definitions of a notion of term where variables may be bound.
In particular, this motivates nominal terms [40]. They are designed to directly represent informal schematic specifications. For example:
Informal equality: If fv then is -equivalent to []. Nominal terms: #[][]() Permissive: [] []() , where
Informal unification: Which and make () equal to ()? Nominal unification: [][]() [][]() Permissive: [][]() [][]() (here, , ) The first example is part of the usual specification of -equivalence. The second example is from [40]. Definitions of nominal and permissive nominal terms will follow.
Nominal terms have been explored in logic-programming [7], rewriting [10], logic [19, 21], and elsewhere.
An intuition of the translation from informal specification to (permissive) nominal terms is as follows:
Object-level variable symbols and correspond to atoms and (Definition 2.1).
Meta-level variables and correspond to unknowns . Substitution of unknowns is capturing, which models the effect of writing “set to be in ; we get ”. Similarly, ([])[] []. Atoms and unknowns are two distinct levels of variable, just as object- and meta-level are two levels.
Conditions like fv correspond to freshness conditions # in nominal terms. # is a restriction, which is enforced on the notion of substitution, on what may be instantiated to. # is a promise to instantiate only to terms for which is fresh (see the conditions ‘()’ in Lemma 2.14, and ‘#’ in Definition 3.1 of [40]).
Object-level renaming [] is modelled by swapping () (which maps to , to , and all other atoms to themselves; Definition 2.5). Swappings are bijective on atoms and invertible, unlike renamings, and for this reason they are naturally capture-avoiding.1 This gives them attractive mathematical properties which can be exploited in the mathematical theory. Using them to manage renaming in -equivalence is a conspicuous feature of nominal techniques and follows [25, 40]. The reader can safely think of [] as corresponding to () so long as () is sufficiently fresh. It is notable that freshness side-conditions in informal practice seem to appear exactly in those places in which they would be necessary for this to work.
and application are term-formers (function-symbols). In the examples above we write application infix, as is standard.
Permissive nominal terms differ in two ways from nominal terms:
Difference 1. Freshness information is fixed once and for all, and associated to unknowns in the manner of a sorting or typing annotation. For example: # is a nominal term-in-freshness context whose freshness context insists that not occur free in . A corresponding permissive nominal term is where is a set of atoms we call the permission set of , and .
Difference 2. Permission sets are sets of atoms that are both infinite and co-infinite (see Remark 2.23; is co-infinite when is infinite).
These combine with consequences which we now discuss.
1.2. Difference 1: about fixing freshness contexts
Difference 1 on its own is mostly a matter of presentation. It is mentioned already in [40, Remark 2.6] (there, we would obtain ‘permission sets’ such that is infinite and is finite). It is still worth reflecting briefly on what that difference in presentation means, for some example results. Part 2 of Lemma 2.14 from [40] reads as follows:
If () and #, then #
The corresponding result in this paper (Lemma 3.3) reads as follows:
Parts 1 to 3 of Lemma 2.7 from [40] read as follows:
1. If # then #.
2. If # then #.
3. If # then #.
These three statements correspond to one result in this paper (Lemma 2.17) which reads as follows:
To us, the ‘permissive’ versions seem shorter and clearer.
In fact there is a little more to Difference 1 than presentation. If freshness contexts are fixed then some ‘consistency’ properties of the same term across different freshness contexts become irrelevant. For instance consider the weakening and strengthening results for freshness contexts like those in Subsection 3.2 of [24] or Subsection 3.3.2 of [21]; if we had used permissive nominal terms, then these results would have been irrelevant and could have been omitted.
1.3. Difference 2: about choosing fresh atoms
The reader used to nominal terms can think of Difference 2 as allowing and requiring infinite freshness contexts.2 Together with Difference 1, this gives us two key properties which are absent in [40]:
An infinite supply of fresh atoms is guaranteed for every term. There is no need to change a freshness context to obtain fresh atoms, because they are already there.
Terms may be directly quotiented by -equivalence. They also become susceptible to the nominal inductive reasoning principles of [25].
This matters. The nominal terms as presented in [40] cannot be quotiented by -equivalence, and cannot be subjected to the nominal inductive principles of nominal abstract syntax [25]. In this respect, they are less tractable than first-order or higher-order terms, which can be.
True enough, it is always possible to ‘add a fresh atom to the freshness context’ in nominal terms and rename, but this causes similar difficulties to those encountered in -renaming on name-carrying syntax.
This is potentially a problem for the viability of any reasoning on, programming on, or extensions of nominal terms. We have experienced this ourselves in [24, 23].
It becomes possible to argue against nominal terms because they appear to be harder to manipulate than the language they describe, and in particular, because they reintroduce the problem of -equivalence which nominal abstract syntax was originally designed to solve.
The existence of permissive nominal terms demonstrates that in fact, the apparent problem is just an artefact of the way matters were set up in [40]. We can quotient permissive nominal terms by -equivalence. In fact we can also use nominal inductive reasoning principles to reason on permissive nominal terms [22, 15].
Turning to the issue of fresh atoms; in the world of finite freshness contexts based on [40], we may always extend freshness contexts if we want more fresh atoms. This is made formal for example by (fr) in [21, Figure 2] and (Tfr) in [24, Figure 1].
We can observe the effects of this solution to the problem of generating fresh atoms, by considering the mathematics in [24]. (Tfr) is not a syntax-directed rule and this complicates case-analysis on derivations. Subsection 5.1 of [24] is devoted to controlling this issue. Further, since freshness contexts may change during a proof, it is necessary to account for these changes in statements and proofs of results; the results in Subsection 5.3 of [24] therefore contain an existential quantification over ‘sufficiently freshened’ freshness contexts.
In fact we should recognise what happens in [24] because it is typical of something we have seen before. A ‘state’ of ‘generated atoms’ is being carried by the freshness context and threaded through all the proofs. This is a situation familiar from implementing languages with binding; we may need to keep track of the ‘generated fresh atoms’ so that when we generate a new one we can easily pick an ‘even fresher atom’. We thread through the program a ‘state’ of ‘generated atoms’ (see for instance the ‘fresh monad’ in Cheney’s FreshLib [5]). This is undesirable if it can be avoided, because it interferes with the state-free style of functional programming, forces us to program more sequentially, and it complicates code.3 This is what motivated FreshML [38, 39].
The paper [24] is not an isolated case. Similar issues have arisen in proofs on the two-level lambda-calculus [23] and in other work [19, 18, 20]. Furthermore, the ‘fresh atom’ issue is not restricted to proofs:
A prototype implementation of permissive nominal terms and their unification by the third author [33] has a direct mechanism for generating a fresh name for any permissive term. Even in a pure functional language like Haskell, no monadic programming is needed just to generate fresh names.
Calvès recently wrote the Haskell Nominal Toolkit (HNT) [2], which provides efficient implementations of several algorithms on nominal terms. The HNT provides an elegant programming interface for manipulating nominal terms, and any efficient implementation of permissive nominal terms would also likely expose a similar API to the programmer.
However, Calvès’ underlying model is the nominal term and this is reflected in the types of programs written with the HNT. Whereas core functions in the implementation of permissive nominal terms (e.g. unification and alpha-equivalence checks) are pure, the types of their HNT counterparts are heavily monadic, and explicit freshness contexts must also be passed around.
As an example, we compare the types (1) of the alpha-equivalence check function from the HNT and (2) of the implementation of permissive nominal terms:4
(1) check :: (Show Eq Ord Ord) FrsCtxt
CS (ExtB (ErrorT [Char])) ()
(2) aeq :: (Eq Permissive ) Term Term Bool
To us, the ‘permissive’ type seems shorter and clearer. An implementation of the HNT, based on permissive nominal terms, would likely present less daunting types to the programmer, and removing the burden of handling freshness contexts would likely make code shorter and neater.
1.4. Permissive nominal terms in this paper
Permissive nominal terms are designed to deal with these issues. Their theory of -equivalence and ‘fresh atom of’ restore the good features of nominal abstract syntax without losing any expressivity or computational properties.
In fact, permissive nominal terms are ‘best possible’ in a certain sense: in [22, 15] we demonstrate how the atoms-abstraction construction from [25] can be applied directly to permissive nominal terms syntax. That is, in [22, 15] we show that it is possible to take [] to be literally the Gabbay-Pitts atoms-abstraction of in the set that is the abstract syntax tree , so that -equivalence is literal identity, and the definition of permissive nominal terms syntax (Definition 2.6) becomes a nominal abstract syntax style inductive datatype of syntax-with-binding.
In this paper we introduce permissive nominal terms. We study their theory of unification. Given any new syntax, it is important to connect it to existing denotations. Therefore, we relate permissive nominal terms and their unification to nominal unification, and to unification of higher-order patterns. Denotations in nominal sets will be the topic of a separate manuscript [15] (some elements are also in [22]).
The contributions are as follows:
We introduce permissive nominal terms Definitions 2.6, along with theories of -equivalence and freshness with the ‘always fresh’ and ‘always rename’ properties discussed above (Corollaries 2.14 and 2.15).
It may look like permissive nominal terms are infinite, because the in in Definition 2.6 is an infinite set. In Remark 2.7 we mention that they are just as ‘finite’, and computable-upon, as nominal terms.
We develop a notion of unification (Definition 6.6). We use a simplified notion of unifier (Definition 3.9) which is more like the notion of unifier from first- and higher-order unification in that it is based just on a substitution, as compared to the notion of unifier used in [40], which is not.
We make precise the connection between nominal terms and permissive nominal terms by translating nominal terms, nominal unification problems, and their solutions, to the permissive context (Definition 4.6). We verify that no expressivity is lost (Theorem 4.16).
We connect permissive nominal terms and higher order patterns [32, 31] (Definition 8.3) by translating permissive nominal terms, unification problems, and their solutions, to a very general notion of untyped pattern unification problems and their solutions (Definition 9.1). We also prove that this translation is ‘best possible’ and ‘complete’ in senses which we make formal (Theorems 8.14 and Theorems 9.16 and 9.30).
1.5. Map of the paper
The paper is organised as follows: We introduce permissive nominal terms in Section 2. Notable results are the ‘always fresh’ and ‘always rename’ properties for terms (Corollaries 2.14 and 2.15 respectively).
In Section 3 we introduce technical definitions and results which will prove useful in the development of the unification algorithm, including permissive nominal terms substitution (Definition 3.1), unification problems and their solutions (Definition 3.9).
We clarify the relationship between nominal and permissive nominal terms in Section 4, by injecting nominal terms into permissive nominal terms (Definition 4.6 onwards). We also elucidate the relationship between solutions of nominal unification problems, based on subsititution+freshness, and solutions of permissive nominal unification problems, based on substitution alone (Definition 4.12).
In Sections 5 and 6 we present an algorithm to compute most general solutions to permissive nominal unification problems (Definition 6.6). We prove it correct in Theorem 6.25.
We define -terms syntax (Definition 7.1) in Section 7, and higher-order patterns (Definition 7.19). Section 8 translates from permissive nominal term syntax to -term syntax (Definition 8.3 onwards). We prove that this translation is ‘best possible’, in a suitable sense which we make formal (Theorem 8.14).
Section 9 relates the solutions of higher-order pattern unification with solutions of permissive nominal unification (Definition 9.1). We show that the instantiation ordering, hence the property of solutions being ‘more general’, is preserved by the translation (Corollary 9.5). We prove a soundness and weak completeness result (Theorem 9.16). Finally, we refine this to a more complex but more powerful completeness result (Theorem 9.30).
In Section 10, we conclude and suggest ideas for future work.
2. Permissive nominal terms
We set up the syntax of permissive nominal terms (Definition 2.6) and their notion of -equivalence , which does not require a freshness context (Definition 2.13). We prove that permissive nominal terms have the ‘always fresh’ and ‘always rename’ properties (Corollaries 2.14 and 2.15). Finally, we verify that is an equivalence relation; this mirrors the result for nominal terms [40, Theorem 2.11], though the proof-method is based on [10, Subsection 3.2]. Where we omit proofs they are routine (or see a technical report [8], or [10]).
Note the two notions of ‘free variables of’; fa is the free atoms in , and fV is the free unknowns in (Definitions 2.11 and 2.12). This reflects the two-level structure of nominal terms familiar from previous work [40].
Fix two disjoint countably infinite sets and of atoms and write
(Here denotes disjoint set union) will range over distinct elements of (we call this the permutative convention).
Define by
Call elements of permission sets. will range over permission sets.
Call co-infinite when is infinite. is a set of infinite, co-infinite sets of atoms.5
For each permission set fix a disjoint countably infinite set of unknowns of sort . , , , will range over distinct unknowns of sort . If then there is no particular connection between and . will range over finite sets of unknowns (we use this from Section 5 onwards).
Suppose is a function from atoms to atoms. Define nontriv by:
This has also been called the support of [25].
A (finite) permutation is a bijection on atoms such that nontriv is finite. and will range over finite permutations.
Write for the composition of and (so ()((())). Write id for the identity permutation (so id( always). Write () for the swapping permutation that swaps and .
We write for syntactic identity; when and denote identical terms. Note that (the unknown) is not a term, however is a term and in particular id is a term, which we may write as .
Permissive-nominal terms are finite. They are finitely branching finitely deep trees.
Equality of permissive-nominal terms may be calculated in finite time. Permission sets trivially admit a finite representation as the pair of finite sets and in Definition 2.2.
In an implementation of the algorithms in this paper by Mulligan [33], atoms are implemented concretely as numbers. is identified with the even numbers. Permission sets are represented finitely as their finite deviation from .
Another, quite elegant, presentation is possible using exclusive or; see Remark 2.23.
See Section 4 for a comparison between permissive nominal terms of Definition 2.6 and ‘ordinary’ nominal terms [40]. Atoms represent variable symbols; term-formers functions; unknowns meta-variables; abstraction [] binding; and a meta-variable with a suspended substitution, like ‘[]’. For example, suppose term-formers app and : app() can represent ‘’ ( applied to ). app(lam([])) can represent ‘()’ (identity applied to ). ([]) can represent ‘’ if , and ‘, where fv’ if .
Note that fa(. Thus, an intuition for fa is ‘the free atoms we can have after instantiation’.
Corollaries 2.14 and 2.15 are properties that ‘ordinary syntax’ has, that nominal terms do not have, and that permissive nominal terms recover; we can always choose a fresh variable, and we can always -rename with it.
For any , ..., there exist infinitely many such that fa
Define atoms inductively by:
It is not hard to prove by induction on term syntax that fa
Later on, we will often need to say ‘choose an atom fresh’ (see for example Definition 4.14). When we do this, we are using Corollary 2.14.
Corollary 2.15 expresses that we can always -rename:
For any and there exists infinitely many fresh (so fa) such that for some , []
Immediate, by Corollary 2.14 and [b]).
Our changes do not affect basic results about nominal terms [40]; the proofs of the following lemmas are by routine inductions (see [8] for details):
1. id
2. () ()
fa( fa().
If then .
If then fa( fa
If then .
is transitive, reflexive, and symmetric.
2.1. Foundations of permission sets
The Fraenkel-Mostowski sets model used in the work which introduced nominal techniques [25] famously does not admit sets like and , because they do not have finite support. It is not an issue in this paper because we are not concerned with representing permissive nominal syntax-up-to-binding. Permissive nominal syntax-up-to-binding can be constructed though; see [22, 15]. See also generalisations of nominal sets by the second author [11, 13] or by Cheney ([3, Section 3], or [6]).
Define (the exclusive or) by
It is a fact that for every , the set is a finite set of atoms, and it is the unique finite set such that . This gives a nice finite representation of permission sets, alternative to the two mentioned in Remark 2.7.
3. Substitutions, problems, and solutions
3.1. Substitutions
The purpose of an unknown is to represent an ‘unknown term/unknown element’. We therefore define a substitution action for unknowns. Consistent with nominal terms, substitution for unknowns is capturing for abstraction by atoms.
A substitution is a function from unknowns to terms such that fa(()) always (so in describes the ‘permission’ we have to instantiate , namely to terms with free atoms in ). , , , , will range over substitutions.
Write id for the identity substitution mapping to id always. It will always be clear whether id means the identity substitution or permutation. Suppose fa
‘fa(()) ’ looks absent in nominal terms theory ([40, Definition 2.13], [10, Definition 4]), yet it is there: see the conditions ‘()’ in Lemma 2.14, and ‘ #’ in Definition 3.1 of [40]. More on this in Section 4.
Note that means ‘ acting on id ’; () means ‘the value of function at ’.
fa() fa
See Appendix Appendix A. We use Lemma 2.17.
() ().
By induction on .
If (() for all fV , then .
If then .
Define composition by ()() (()).
()().
By induction on . We consider one case:
The case
3.2. Unification problems, and solutions
This is a brief subsection, but it is useful: A solution to ‘makes the equalities valid’, as for first- and higher-order unification. This simplifies the nominal unification notion of solution (Definition 4.11 or [40, Definition 3.1]) based on ‘a substitution + a freshness context’. We prove results about these definitions in Sections 4 (connection with nominal unification) and 6 (unification algorithm).
An equality is a pair . A problem is a finite multiset of equalities. Define by:
Say that solves when implies . Write Sol() for the set of solutions to . Call solvable when Sol() is non-empty.
4. Relation to nominal terms
In Subsection 3.2 we stated what a permissive nominal unification problem is, and what a solution to it is. We now make precise a mathematical sense in which nominal terms and their unification can be considered a subsystem of permissive nominal terms and their unification.
We recall the notions of nominal term and nominal unification problem (Definitions 4.2 and 4.11). We translate from the ‘nominal world’ to the ‘permissive nominal world’ (Definition 4.6). Theorem 4.9 expresses how this translation is sound and complete for respective notions of -equivalence. Theorem 4.16 then shows that furthermore, solutions to unification problems are preserved 1-1 across the translation.
Recall from the Introduction that in nominal terms we often to enrich the freshness context. An interesting feature of Definition 4.6 is how it maps nominal terms to permissive nominal terms with free atoms in , which is an infinite, co-infinite set of atoms. One way to view the interpretation of Definition 4.6 is therefore this: is ‘the atoms we had available so far’ (any other permission set would do as well) and is ‘the atoms with which we will extend the freshness context, in the future’. Both these sets are infinite, and syntax is finite, so it is not absolutely necessary to explicitly separate them: permissive nominal terms do this, for each fixed permission set ; nominal terms do not.
4.1. Alpha-equivalence between nominal and permissive nominal terms
Fix a countably infinite set of nominal atoms, . will range over distinct nominal atoms.
Fix a bijection between and any permission set. For concreteness we will suppose it is from Definition 2.2 but any permission set will do as well.
Fix a countably infinite set of nominal unknowns. will range over distinct nominal unknowns. A nominal permutation is a bijection on such that nontriv) is finite. will range over permutations.
Write for the inverse of , for the identity permutation, and for function composition, as is standard. For example, ))
Define a permutation action on nominal terms by:
Write for syntactic identity. f ranges over term-formers (Definition 2.1).
A freshness is a pair . A freshness context is a finite set of freshnesses of the form # . Define derivable freshness on nominal terms by the rules in Figure 2.
Definition 4.5 repeats [40, Figure 2], up to differences in presentation:
An equality is a pair . Define derivable equality on nominal terms by the rules in Figure 3.
commutes with permutation and it preserves and reflects freshness:
By induction on .
) fa() if and only if .
See Appendix Appendix A.
Theorem 4.9 states that -equivalent nominal-terms-in-context map precisely to -equivalent permissive nominal terms:
if and only if .
See Appendix Appendix A. We use Lemmas 4.7 and 4.8.
4.2. Substitutions and solutions between nominal and permissive nominal unification problems
A unification problem is a finite multiset of freshnesses and equalities. A solution to is a pair ) such that for every , and for every . This follows [40, Definition 3.1].
We extend the interpretation of Definition 4.6 to solutions of nominal unification problems by:
) .
See Appendix Appendix A.
Define by mapping to and mapping to ()) , for some choice of fresh (so fa(); in fact, it suffices to choose some ).
Suppose fa. Then fa if and only if () .
See Appendix Appendix A. We use Lemmas 2.16 and 2.17, and Proposition 2.21.
No solutions go missing, moving from the nominal to the permissive nominal world:
) solves if and only if ) solves .
If ) solves then ) solves . Suppose . Using Lemma 4.13 and Theorem 4.9, ) ).
Suppose . Using Lemma 4.8, ) fa( ). By Lemma 4.13, ) fa( )). By Lemma 4.15, ()) ) ), where is fresh (see Definition 4.14). By Lemma 3.4, (()) ) ) ). The result follows.
If ) solves then ) solves . Suppose that ) ). By Theorem 4.9, .
Suppose (())) ) ). By Lemma 3.4, ()) ) ). By Lemma 4.15, ) fa( )). Using Lemma 4.13, ) fa( ). By Lemma 4.8, , and the result follows.
5. Support inclusion problems
The freshness symbol # used in [25] and [40] is ambiguous. Do we mean ‘ is not free in the syntax of ’ or ‘ is not in the support of the denotation of ’? The first option can be called intensional or syntactic freshness; the second option can be called extensional or semantic freshness.
In nominal terms this question is slightly obscured because a ‘free atoms of’ function on terms is hard to define. In permissive nominal terms we can easily define a ‘free atoms of’ function; see Definition 2.11, fa
We have seen in Section 4 how nominal terms’ notion of freshness ‘#’ translates to a syntactic freshness ‘ fa’.
Nominal terms unification solves equality and freshness problems within a single rewrite system. When we designed the permissive nominal terms unification algorithm, we solve these separately — one algorithm is described in this section, the other (for equalities) is described in Section 6. This is simply a design choice, but it is informed by the translation of # to a syntactic judgement, described above. For, in future it may be useful to consider unification modulo equational theories (and note that semantic freshness can be easily captured using equations; see [17, Theorem 5.5] or [21, Theorem 4.52]). In the presence of equational theories, because we have factored out fragment of the computation that checks ‘ fa’, that fragment will remain modular and unaffected by the imposition of equality axioms.
Recall from Definition 3.1 that fa(()) fa(, and from Lemma 3.3 that instantiation must reduce the set of free atoms. We will exhibit an algorithm which, intuitively, solves the problem “please make fa() true” (Definition 5.9 and Lemma 5.7). In fact the algorithm calculates solutions that are most general, in a sense made formal in Theorem 5.20.
Next, in Section 6, we construct an algorithm to solve equality problems.
5.1. Simplification reduction and normal forms
A support inclusion is a pair of a term and a permissions set. A support inclusion problem is a finite multiset of support inclusions; Inc will range over support inclusion problems. Call a solution to Inc when fa() for every
Inc. Write Sol(Inc) for the solutions of Inc. Call Inc solvable when Sol(Inc) , and non-trivial when nf (Inc) .
Define a simplification rewrite relation by the rules in Figure 4.
Definition 5.2 can easily be expressed as a type I conditional term rewrite system, according to the classification scheme of [1, Definition 7.1.1]. This becomes evident if we bear in mind that we can represent atoms as numbers, as the even numbers, as the finite set (Remark 2.23), and as the finite set .
If Inc then Sol(Inc Sol().
First, we make the following claims:
Claim 1: If then fa() always. Since fa( fa(
Claim 2: fa(f()) if and only if fa() for 1 . Since fa(f(
Claim 3: fa(([])) if and only if fa() . Suppose fa(([])) , therefore
fa([]) . Then fa() , therefore fa() and the result follows. The reverse direction is similar.
Claim 4: fa(()) if and only if fa() . We consider only one case.
fa() by assumption. By Lemma 2.17, fa
Claim 5: By Definition 3.2 we have fa(() fa( ()). If then
. Using Definition 3.2 and Lemma 2.17, fa( ( fa(()) . Therefore, fa(()) , and the result follows. We now proceed by case analysis on Inc (Definition 5.2):
The case (a). Suppose . If Sol( ) then Sol() and the result follows immediately. Conversely, suppose Sol(). Using Claim 1, fa() , and the result follows.
The case (f). From Claim 2.
The case ([]). If Sol( ) then fa() . By Claim 3, fa([]()) . As fa([]( fa(([])) and Sol(), the result follows. The reverse implication is similar.
The case (X). Suppose , id and Sol( Inc), so fa(()) . By Claim 4, fa() , and as Sol(), the result follows. The reverse implication is similar.
The case (). Suppose . If Sol( ) then Sol() and the result follows. Conversely, suppose Sol(). By Claim 5, fa(()) . The result follows.
Support inclusion problem simplification is strongly normalising.
See Appendix Appendix A.
We conclude with a few useful observations:
Call Inc consistent when nf (Inc) for all atoms and permission sets .
If Inc is consistent then all inc nf (Inc) have the form where .
5.2. Building solutions for support inclusion problems
Our main results are Theorems 5.13 and 5.20.
Define fV (Inc) by fV (IncfV
In words, fV (Inc) is “the unknowns appearing in terms appearing in Inc”.
Recall from Definition 2.3 that ranges over finite sets of unknowns.
For example, take , , , , and .
It is easy to see that the support reduction problem is in normal form. Let where be the fixed but arbitrary choice of fresh variable made in Definition 5.9. Then:
is a substitution that “makes Inc true on ”. Nominal unification does not have this notion because nominal terms unknowns are not permanently labelled with freshness information — instead, nominal terms unification emits ‘fresh’ freshness conditions.
It is easy to verify that
In fact, is the most general solution with property; intuitively, all other solutions must factor through on . This is made formal in Theorem 5.20.
If Inc is consistent then Sol(Inc). (‘ solves Inc.’)
Suppose Inc is a -normal form. If Inc then ( id for an which satisfies . The result follows.
More generally, if Inc is not a -normal form, by Theorem 5.3 Sol(Inc Sol(nf (Inc)), and we use the previous paragraph.
By Theorem 5.3 Sol(Inc Sol(nf (Inc)), so it suffices to show the result for the case when Inc is a -normal form.
Suppose Inc is inconsistent, so nf () contains a support inclusions of the form where . Then always, so there is no substitution such that . Conversely, if Inc is consistent, the result follows by Lemma 5.12.
We check that Definition 5.14 is well-defined:
If exists then it is well-defined.
Suppose exists. Then:
Suppose and . By Definition 5.14, ()() () and ()( (. The result follows, as substitutions are well-defined.
Suppose , () id , ( id and . Then ()() () and ()() (. Since the result follows as substitutions are well-defined.
Suppose () id, and . Then ()( ( and ()() (). By Definition 5.9, () id as . The result follows as substitutions are well-defined.
The case , ( id , and is similar to the case for () id , and .
If Sol(Inc) then exists.
If exists, then it is well-defined.
Suppose exists and Then:
and . Then ( id and ( id . By Definition 5.9, and are chosen so . The result follows.
and . Then ( id and ( id The result follows.
and . Then ( id and ( id with . The result follows.
The case and is similar to the case for and .
If Inc then fV () fV (Inc).
By case analysis on the rules defining (Definition 5.2).
If Sol(Inc) and fV (Inc) then is a substitution.
By Lemma 5.16, exists. We show fa(()()) by cases:
The case id () for . Using Lemma 5.18, fV (nf (Inc)) fV (Inc). Then fV (nf (Inc)) , as fV (Inc) by assumption. There are two sub-cases:
The case fV (nf (Inc)). Then and ()(() by Definition 5.14. By assumption fa(()) . The result follows.
The case fV (nf (Inc)). By assumption, Sol(Inc) so Sol(nf (Inc)) using Theorem 5.3. Then fa(()) for every such that nf (Inc), using Definition 5.1. By Definition 5.14, nf (Inc). The result follows.
Otherwise, ()() () and fa(()) by assumption.
Suppose Sol(Inc) and fV (Inc) .
Then () (())() for every .
For some fresh , () id , and ()() (). The result follows by Lemma 2.16.
5.3. Support reduction example
Suppose and . Take , and . We first run the support reduction algorithm on Inc f([] id () () :
We take nf (Inc () () . By Definition 5.6 we have nf (Inc) is consistent, therefore by Theorem 5.13 a solution for Inc exists.
We now construct . Take and as our injective choices of fresh unknowns. Take (() () ) and (() () ). An easy calculation shows that . We define piecewise by:
( id and ( id and ( id for all other
It is easy to verify that this is in fact a substitution (i.e. fa(()) always).
6. Permissive nominal unification problems
We can now give an algorithm to compute solutions to permissive nominal unification problems (Definition 3.9) and we prove that our algorithm computes most general solutions. Note, as we have observed before, that the notion of problem and solution is based just on equalities and substitutions.
6.1. The unification algorithm
Sol() if and only if Sol().
If is a problem, define a support inclusion problem by:
Call a support inclusion problem Inc non-trivial when nf (Inc) .
Define a simplification rewrite relation ; ; on unification problems by the rules in Figure 5.
Call (a), (f), (a]), (b]), and (X) non-instantiating rules. Call (I1), (I2), and (I3) instantiating rules. Write for the transitive and reflexive closure of .
In (I3) we insist that is non-trivial to avoid indefinite rewrites. We insist is consistent so that exists. and ( are defined in Definition 5.9.)
Define fV (fV
(We overload , for technical convenience: is partial and is total.)
If is a problem, define a unification algorithm by:
1. Rewrite fV (); using the rules of Definition 6.3 as much as possible, with top-down precedence (so we apply (a) before (f), and so on down to (I3)).
2. If we reduce to ; , we succeed and return where is the functional composition of all the substitutions labelling rewrites (we take id if there are none). Otherwise, we fail.
The algorithm of Definition 6.6 always terminates.
See Appendix Appendix A.
6.2. Examples of the algorithm
Example one.
Suppose and . Take . Take . Suppose a term-former g. We apply the algorithm to g([](id ) []) g([]
; (Success!) The algorithm succeeds and returns the substitution [].
Example two.
Suppose and . Take and and . Take . Suppose a term-former f.
We apply the algorithm to f([] id id ) f([] [] id :
Here and are the choice of unknown made in Definition 5.9, and .
The algorithm succeeds and returns the substitution
Example three.
An example that fails to unify. Take . Take . We run the algorithm on []([](id )) ](id ):
The algorithm fails as the precondition of rule (I2), fV ([]()), the ‘occurs check’, fails to hold. By Theorem 6.25 there is no solution to the unification problem.
6.3. Preservation of solutions
If ; ; by a non-instantiating rule (Definition 6.3) then Sol( Sol().
See Appendix Appendix A. We use Lemmas 3.3 and 3.4, and Proposition 2.21.
Suppose (() for all fV (). Then Sol() if and only if Sol().
In the right circumstances, a substitution can be factored as ‘a part of that does not touch ’ and ‘a single substitution for ’:
Suppose and fV . Then
We reason as follows:
6.4. Simplification rewrites calculate principal solutions
Write when there exists some such that () always. Call the instantiation ordering.
A principal (or most general) solution to a problem is a solution Sol() such that for all other Sol().
Our main results are Theorems 6.18 — the unification algorithm from Definition 6.6 calculates a solution — and 6.23 — the solution it calculates, is principal.
If fV () and ; ; using a non-instantiating rule, then fV () .
See Appendix Appendix A.
fV ([]) fV
By induction on .
If fV () and ; ; using an instantiating rule, then fV () .
If then ([])]()
We consider cases:
The case with . We reason as follows:
The case with . We reason as follows:
The case with . Since ([])( id and id
Recall that is defined in Definition 6.5:
If fV () then ; ; implies Sol().
By induction on the length of the path in .
Length 0. Then and id. The result follows.
Length . There are three cases:
The non-instantiating case. Suppose ; ; ; . Using Lemma 6.14, fV () and Sol() by inductive hypothesis. Using Lemma 6.8, Sol(), and the result follows.
The case of (I1) or (I2). Suppose ; ; ; . Using Lemma 6.16, fV () . By inductive hypothesis Sol(). By Lemma 6.17, ()(). By Lemma 6.1, () Sol().
The case of (I3). Suppose ; ; ; . Using Lemma 6.16, fV () . By inductive hypothesis Sol(). By Lemma 6.1, () Sol(). By Lemma 6.17, (). By Lemma 6.9,
If then .
By Definition 6.12, exists such that () always. Then:
Suppose always. Then implies .
If then ().
We consider cases:
The case . Then ()( id and ()( id . The result follows.
The case with . Then ()( id and ()( id The result follows.
The case with . Then ()(( and ()( (. As (( when , the result follows.
Suppose fV () .
If ; ; then is a principal solution to (Definition 6.13).
By Theorem 6.18, Sol(). We prove is principal by induction on the path length of ; ; .
Length 0. So and id. By Definition 6.12, id.
Length . We consider the rules in Definition 6.3.
The non-instantiating case. Suppose
where ; ; is a non-instantiating simplification rewrite. By inductive hypothesis is a principal solution of . By Lemma 6.8 is a principal solution of . The result follows.
The case (I1). Suppose fa
Further, suppose that Sol(). By assumption () , so by Lemma 3.4 (. By Lemmas 2.18 and 2.16 ( (), and by Lemma 3.4 ( (). It follows by Theorem 6.11 and Lemma 6.9 that () Sol(). Using Lemma 6.22, (). By Lemma 6.1, () Sol(). By Theorem 6.18, Sol(). By Lemma 6.16, fV () . By inductive hypothesis (). By Lemma 6.19, () (). Now by assumption fV
The case (I2) is similar to the case of (I1).
The case (I3). Suppose is consistent and non-trivial. Write , so that
and suppose that Sol(). By Theorem 6.18, Sol(). It is a fact that , so fV () . By Lemma 6.21, Sol(). By Theorem 5.20 and Lemma 6.9, () Sol(). By Lemma 6.1, Sol(). By inductive hypothesis . By Lemma 6.19, (). It is a fact that (). By Theorem 5.20 and Lemma 6.20, () as required.
1. Suppose fa and fV . Write ].
2. If ; ; with (I3) then Sol() implies Sol().
1. We consider the case of (I1); the case of (I2) is similar. Suppose so that ; ; . Now suppose Sol(). By Lemma 6.9 and Theorem 6.11, ()) Sol(). By Lemma 6.1, Sol(). It follows that Sol() as required.
2. Suppose is consistent and non-trivial. Write , so that ; ; . Now suppose Sol(). By Lemma 6.9 and Theorem 5.20, () Sol(). By Lemma 6.1, Sol() as required.
Given a problem , if the algorithm of Definition 6.6 succeeds then it returns a principal solution; if it fails then there is no solution.
If the algorithm succeeds we use Theorem 6.23. Otherwise, the algorithm generates an element of the form f() f() where , f() g(), f() ], f() , [], [], , a such that is inconsistent, or or where fV . By arguments on syntax and size of syntax, no solution to the reduced problem exists. It follows by Lemma 6.24 that no solution to exists.
7. Lambda-term syntax
We want to relate permissive nominal unification with higher-order pattern unification as promised in the Introduction. In this section we recall the syntax and operational semantics of the -calculus. It is convenient to match the variables of permissive nominal terms with those of the -calculus. Therefore, when we define -terms’ syntax in Definition 7.1, we use the same atoms and unknowns as we used in Definition 2.6; both behave like ordinary variables (with capture-avoiding substitution). As in permissive nominal terms we unify on the unknowns, but we do not care about the permission sets so we will let range over distinct unknowns (without superscripts).
Define -equivalence inductively by the rules in Figure 6.
It is not hard to prove that Definition 7.4 does indeed specify the usual -equivalence relation on -terms. Our definition is designed to match the definition of -equivalence on nominal terms (Definition 2.13). This makes later results easier to prove (for example Theorem 8.12).
Lemma 7.5 to Proposition 7.12 mirror similar results for permissive nominal terms. The proofs of Lemmas 7.5 to 7.7 are by induction on .
If then .
() ()
fa( fa
implies .
If then fa( fa
By induction on the derivation of . We consider one case;
The case (ab). Suppose using (ab), where fa. We aim to show fa( fa(), or, fa
size( size()
By induction on .
is transitive, reflexive, and symmetric.
Call a function from unknowns to -terms a (-calculus) substitution. will range over substitutions (and later so will ; Definition 9.17).
We will write [] for the substitution which maps to and maps all other to .
Define composition by: ()() (()). This mirrors the definition for substitutions on permissive terms, given in Definition 3.7.
()
By induction on size
We also need a substitution action on atoms so that we can talk about -convertibility — the distinction between unknowns and atoms is rather artificial here, but in the context of relating to permissive nominal terms it is useful to maintain it:
Let -equivalence be the least transitive, reflexive, symmetric relation such that ()[] and closed under the rules of Definition 7.4.
We define unification problems as usual and write ‘’ for an equality considered as part of a unification problem. solves a problem when for every in the problem, as usual.
We conclude with definions of pattern and pattern substitution [32, 31]. Recall that we work in an untyped -term syntax.
Let map each unknown to a natural number which we call its arity. Define -patterns, a subset of -terms, by:
Call a pattern when it is a -pattern for some . will range over patterns.
Call a -pattern substitution when every is a -pattern. Call a pattern substitution when is a -pattern substitution for some .
So is a pattern when there exists some such that every in occurs as . This is not quite a typing constraint, but it achieves part of what a typing system would achieve; that within , for each , is consistently applied to a list of atoms of the same length. Note that the translation of Definition 8.3 below, produces terms of this form.
8. Translating nominal terms to lambda-term syntax
8.1. The translation, and its soundness
We define the translation from permissive nominal terms to -terms, and show that it is sound in the sense that -convertible permissive nominal terms map to -convertible -terms (Theorem 8.6). The translation involves a vector of atoms ; we discuss where this comes from in Subsection 8.2.
Call a finite list of distinct atoms a vector. range over vectors. Write [] for the vector containing , ..., in that order.
Suppose . Write for the vector of atoms in that occur in , in order; thus [] ]. Write when every atom in is in . Write when every atom in is in .
By induction on .
Lemma 8.5 is useful for the proof of Theorem 8.6:
fa() fa
By induction on . We consider only one case:
The case . We reason as follows:
The result follows.
If then
By induction on the size of (Definition Appendix A.1). We reason by cases on the last rule in the derivation of :
The cases a), f) and []aa) are straightforward.
The case X). There are two cases:
The case . Then . We use (X). The result follows.
The case ] and 1. By assumption .
We use (p), (X), and (a). The result follows.
The case []ab). By assumption () and fa. We choose fresh so fa
8.2. Capturable atoms; injectivity and minimality
We investigate the converse to Theorem 8.6; if the translations of two terms are -convertible, then so are the two terms. This is injectivity (Theorem 8.12). The translation (Definition 8.3) is parameterised by a vector . Levy and Villaret introduced a translation [29, Definition 2] (for nominal, not permissive nominal terms); they used all the atoms in . This is a safe choice, but we will also show that the smaller set of capturable atoms in (Definition 8.7) is consistent with injectivity — and that the capturable atoms are the minimal such set (Theorem 8.14).
For instance, if ), then capt([][]
If fa then (
If nontriv
See Appendix Appendix A. We use Lemma 2.16.
If fa then ([] ([]() ).
See Appendix Appendix A. We use Lemmas 8.8, 8.9, and 2.17.
Capturable atoms is a canonical notion, in the sense that it is preserved by -equivalence:
If then ( ().
By induction on the derivation of . We consider one case:
The case of [b]). Suppose fa () and []() . The result follows by Corollary 8.10.
Provided that is ‘large enough’, -equivalence of translated terms implies -equivalence of the original terms:
Let be a vector. Let and be nominal terms and let be finite. Suppose () () . Then
As a corollary, if capt
For the first part, we work by induction on the size of (Definition Appendix A.1), reasoning by cases on the last rule in the derivation of
The cases (a) and (aa). Easy.
The case (ab). Suppose ()
By Corollary 8.10 and Definition 8.7:
By inductive hypothesis () (), and using []ab), and Proposition 7.12, []
The case (app). From Definition 8.3, there are two possibilities:
The case f() and f() and f
The case and and
The case (X). From the form of the translation it must be that and and nontriv
The corollary follows from the first part, and by Lemma 8.11.
() implies fV exists such that .
See Appendix Appendix A.
In Theorem 8.12 we used a notion of a ‘large enough’ vector , based on capturable atoms. Theorem 8.14 shows how this bound is precise:
If capt() then there exists some such that and
Suppose capt and . By Lemma 8.13 fV exists such that . We choose and take [)]. It is a fact that () whilst () . An easy calculation shows [) ] and [) ].
9. Translating substitutions; relating solutions of nominal and pattern unification problems
9.1. Translating substitutions
We extend the translation to substitutions. Our main result is Theorem 9.3: we can read this as a compositionality result for permissive nominal substitutions acting on terms with respect to the translation. Given the compositionality result it is easy to prove that the translation also preserves the natural instantiation ordering of solutions to unification problems (Corollary 9.5).
Translating substitutions introduces a problem: may solve but in substituting it may introduce new capturable atoms (consider ]] solving , where ). This motivates introducing a second vector, to account for the capturable atoms ‘after’ the substitution. Accordingly, we will introduce another vector that contains at least the capturable atoms of .
Define by:
Lemma 9.2 is useful in the proof of Theorem 9.3:
If nontriv
By induction on . We consider one case:
The case . Choose fresh (so does not appear in , nontriv or ).
Theorem 9.3 is a compositionality result for permissive nominal substitutions acting on terms with respect to the translation:
If capt
By induction on .
The cases and f() are routine.
The case . Let be and (() by Definition 9.1. Then:
The use of Lemma 9.2 above is valid, because: By assumption capt() . By Definition 8.7 capt( nontriv, so nontriv. By assumption in Definition 3.1, fa(()) . It follows from Definition 8.3 that fa(()) , and so that nontriv
The case []. Choose fresh, so fa(()) for every fV and fa. Then:
The result follows.
Recall the instantiation ordering from Definition 6.12. Similarly:
Write when there exists some such that (), for any . Call the instantiation ordering.
We can leverage Theorem 9.3 to prove a corollary, describing a sense in which the instantiation ordering of Definition 6.12 translates to the instantiation ordering of Definition 9.4:
Suppose capt(()) .
Suppose . By definition (Definition 6.12) there exists some such that () always. We reason as follows, for any unknown :
The result follows.
In Corollary 9.5, the precondition capt(()) is necessary to prevent from introducing infinitely many capturable atoms. The ‘complexity’ of is unconstrained. In practice it is likely that we will care about a particular finite set of unknowns (for example, fV () for some ), and the precondition can be correspondingly refined to consider just .
9.2. Translating permissive nominal unification to pattern unification; soundness, weak completeness
The main result of this subsection is Theorem 9.16.
It says that if and are ‘large enough’, then solves if and only if solves . We call this ‘soundness and weak completeness’, to distinguish from a stronger completeness result we prove in Subsection 9.3.
An equation is a pair . A unification problem is a finite set of equations. A solution to is a such that for all .
For example, if f() where , then () (f () ()).
Definition 9.8 is a technical definition, and the results following it are technical lemmas required for Lemma 9.11, which is a key result for Lemma 9.13, which is itself needed for Theorem 9.16.
uncapt is quite interesting; technically, it came about as the ‘right definition’ to make Lemmas 9.10, 9.11, and 9.12 work.7 Intuitively, it may be useful to think of uncapt as collecting those atoms that are not necessarily in capt, but which could feature in capt([]) for some .
For example, if then uncapt() but
If then () ().
As a corollary, () ([]).
By induction on . As ([] , the corollary follows.
Suppose . Then if uncapt then ().
As a corollary, uncapt implies capt([]).
() ((nontriv
See Appendix Appendix A. We use Lemmas 9.9 and 9.10.
uncapt
() () capt(()).
By induction on :
The cases and f(). Straightforward.
The case []. We reason as follows:
The result follows.
The case . As ()(), we reason as follows:
The result follows.
capt() capt(()) is not true in general. For example if and then capt([]
Suppose capt() and capt() . Then solves if and only if solves .
We reason as follows, where ]:
If and are ‘large enough’, then solves if and only if the translation solves the translation :
Suppose
Then solves if and only if solves .
For example, f() where translates to ((f () ()).
The solution [f()] with translates to [(f () )()].
9.3. Strong Completeness
The main result of this subsection is Theorem 9.30. This strengthens the completeness result of Theorem 9.16, in a certain sense, by expressing that a class of solving all originate from solving , in a suitable formal sense.
fa( fa()
By induction on .
if and only if .
The left to right implication is by induction on the derivation of ; right to left is by induction on the derivation of . We consider one case:
The case (ab). For the left to right implication, suppose () and fa. By inductive hypothesis (() ). By Lemma 9.18, fa(). It is a fact that (() ) () (). It follows that () (. Using (ab), ((). The result follows. For the right to left implication, suppose () ( and fa(). It is a fact that () () (() ). It follows by inductive hypothesis that () . By Lemma 9.18, fa. Using (ab), as required.
Define the substitution by: ()()
Note that is a substitution. () is not a shorthand for (). (() does not hold in general; for example: (() id) () ( id). However:
If nontriv
By a routine induction on .
solves if and only if does.
Suppose nontriv
For the first part, we have two cases:
The case solves implies solves . Suppose and solves . Then . By Lemma 9.19, . By Lemma 7.16, ((), as required.
The case solves implies solves . Suppose and solves . Then ((). By Lemma 7.16, . By Lemma 9.19, , as required.
For the second part, suppose nontriv
Lemma 9.22 expresses an intuition that ‘names of atoms and unknowns on the right in a solution, do not matter’, which also underlies the and in Theorem 9.30. is the price we pay for using the same unknowns in Definitions 7.1 and 2.6: This design decision makes Definition 8.3 compact, but it causes technical problems in Lemma 9.29, because can introduce new unknowns over whose permission sets (back in the nominal world) we have no control. lets us rename those new unknowns as convenient. As for , we discuss it below.
Another design decision is to work with an untyped -terms. This simplifies our presentation and makes our results slightly more powerful (because they apply to more substitutions), but we cannot be too liberal: Suppose solves . Examining Definition 8.3, if occurs in then it is applied to a number of atoms equal to the length of . So, we will only be interested in that respect this fragment of typability ( will be fV ()):
Let be a finite set of unknowns. Call -consistent on when for every , ( where is the length of . (So starts with ‘at least’ length--many -abstractions.)
Call strictly -consistent when also, for every , fa(()) .
Strictness is motivated by the following examples: Take ].
Take f([]) with . Then the problem
Now ()(
Take f([] with and . Then the problem
Now ()( ( is impossible, since fa whereas
fa(() by Lemma 8.5. The in ( for the two considered above, has nothing to do with the in . We can regard this as an unfortunate ‘name-clash’ which Lemma 9.22 allows us to eliminate with a permutation .
More on this in Theorem 9.30. We continue with the proofs:
does not imply args( args. This is by design.
Suppose is a -pattern and args
Define a nominal term by:
Here, for each and , is a fixed but arbitrary choice of permutation of the atoms in , mapping the element of (Definition 8.2) to for 1
args
By induction on .
Suppose is a finite set of unknowns and is a -pattern substitution, strictly -consistent on .
Then there exist , , and , such that , capt(()) , and ()( for every .
Take any ] which includes all atoms in and in
By assumption ( for a -pattern , where [. Take
We can verify that capt(()) . We then reason as follows:
Suppose capt() .
For strictly -consistent on fV () solving there are , , and , such that
For -consistent on fV () solving there are , , , and , such that
By Lemma 9.29, there are , , and , such that ()(
For the second part, write ], choose ] fresh (so is not in , , or for any fV ()), and take ) (). is strictly -consistent and the result follows from the first part and Lemma 9.22.
10. Conclusions
In this paper, we have presented a syntax which slightly generalises nominal terms and obtains significantly enhanced properties. We gain ‘always fresh’ and ‘always rename’ properties (Corollaries 2.14 and 2.15) which are present in first- and higher-order syntax, absent in nominal terms, and regained in permissive nominal terms.
We do not claim a telling difference in expressivity in practice between nominal and permissive nominal terms. It may indeed be that permissive nominal terms can express some things that nominal terms cannot8 but expressivity is not our main motivation in this paper. The issues which motivate us are with the properties of these syntaxes. As we have seen in this paper, a significant new body of mathematics follows from these changes, which at first seem so innocuous. It does not stop there; the interested reader can find more in [15].
Permissive nominal terms do not obsolete nominal terms. To discuss ‘an arbitrary term’, a nominal terms unknown may be more directly useful than a permissive nominal terms unknown (which means ‘an arbitrary term, mentioning atoms in ’).
We have leveraged the difference between nominal terms and permissive nominal terms to obtain a new unification algorithm which is more efficient in the sense that it is based just on substitutions, and in that sense is also more like the notion of solution familiar from first- and higher-order syntax. Freshness problems are solved ‘all in one go’ by a distinct algorithm. We have interpreted nominal unification as a subsystem of permissive nominal unification (Section 4).
One nice way to view this interpretation is that plays the role of ‘the atoms we had so far’ and that of ‘the atoms we will generate fresh in the future’. Finally, we have exhibited permissive nominal unification as equivalent to higher-order pattern unification.
10.1. Related work
Infinite sets of atoms
Permissive nominal terms are based on the idea of infinite and co-infinite sets of atoms . This is new, but it emerges from a literature rich in precedents. As we noted in Remark 2.22, infinite and co-infinite sets break with the standard nominal sets semantics from [25], which does not admit them because they do not have finite support. This is however not a serious mathematical problem: the idea of relaxing the ‘finite support’ property of nominal sets to infinite generalisations is natural.
As far as we know this was first discussed in [11], where the second author proposed to identify ‘small’ sets of atoms not with cardinality but with well-orderability of the atoms in the set — so a set of atoms is small when it can be assigned a cardinal size, and large when it cannot be assigned a cardinal size (internally, within the model) — but we do not commit ourselves to how large those cardinals can get, and in particular they could be infinite. See [13] for a more extended treatment of the same ideas.
Pitts referred to the possibility of using nominal sets with infinite support in [37], in order to obtain a complete semantics for nominal logic. This idea was taken up by Cheney in [6]. Thus, in [6] ‘small’ sets of atoms are identified as elements of a support ideal (Definition 4.1 of [6]), which are similar in spirit to the set of permission sets from Definition 2.2. In Definition 2.2 we give a concrete set of permission sets, but in a footnote to that definition we also identify some reasonable abstract conditions for the set of permission sets to satisfy such that the proofs in this paper still work. These conditions are extremely mild; the structure actually required of permission sets is much weaker than that provided by Definition 2.2.
Namespaces
Since this paper was written, the second author has prepared a manuscript treating permissive nominal algebra [15] (a precursor is [22]). There, the set of all atoms is taken to be uncountable and permission sets are taken to be all countably infinite sets of atoms. This setting is sufficiently general to accommodate many different notions of permission sets as subsystems. In particular the permission sets of this paper feature as a ‘namespace’ identified by ; thus, the ideas in this paper slot quite nicely into a more abstract setting.
‘Free atoms of’ as distinct from ‘support of the denotation of’
It may be useful to note some work to which this paper is not related. One nice aspect of permissive nominal terms is that they give us a notion of ‘free atoms of a term’ fa. The judgement # of nominal terms corresponds to the judgement fa of permissive nominal terms (see Lemma 4.8) and both correspond to the informal judgement ‘ is not free in ’.
Nominal sets have a native notion of semantic freshness; # means ‘ is not in the support of the denotation of ’. Semantic freshness is a distinct concept. The reader should not confuse semantic freshness with the intensional judgement ‘free atoms of’ used in this paper.
Semantic freshness may be expressed using ‘free atoms of’ and equality [17, 21, 15].
Patterns
Patterns emerged by studying Skolemisation of unification problems [32]; they proved useful in the unification of higher-order abstract syntax terms [31].
Cheney proposed a two-stage translation of higher-order pattern unification to nominal unification [4], first by exhibiting a translation of higher-order pattern unification to nominal pattern unification (where nominal patterns are a variant of nominal terms, with a concretion operator, where unknowns have empty support), followed by a translation between nominal pattern unification and nominal unification.
Levy and Villaret related nominal unifiability with higher-order pattern unifiability in [29]. Our treatment translates solutions as well, handles a more general class of higher-order patterns than considered in [29], and we prove our translation complete (Theorem 9.30) and optimal (Subsection 8.2).
Note that translating solutions really matters: it might have been, for example, that higher-order pattern unification and permissive nominal unification have the same notion of unifiability — but very different notions of solution and sets of solutions. For comparison, the -calculus and combinators express similar notions of computability, but have very different notions of reduction and computation.
The version of higher-order pattern unification which we examine is more general than usual, since we do not type our -terms. We show how to retain enough of the properties of typing to avoid ‘silly’ problems. For example, we do not consider untyped higher-order pattern unification problems like (), because this cannot be expressed as a unification of two -patterns for any (Definition 7.19) — we impose a structural condition on our patterns that should be applied to a consistent, fixed number of arguments.
We hypothesise that the results in this paper would work in a typed setting; the conditions which our proofs depend on to work are just structural ones, which would also be guaranteed by types. We have not investigated the effects of -conversion; this is future work.
The broader literature
Hamana’s unification of -terms with holes adds a capturing substitution [26]. 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 permission sets also describe which level 1 variable symbols (we call them atoms in this paper) may appear in them, though with our permission sets 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 [34] adds level 2 variables, but does not manage -conversion in nominal style, and, 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).
10.2. Future work
We propose permissive nominal terms as a syntax for designing logics and -calculi in the spirit of nominal terms.
A first implementation of permissive nominal unification has been made [33] by the third author.
We have begun to apply permissive nominal terms to construct novel logics and -calculi, taking advantage of their properties to simplify the theory. It is simply very useful to reason on terms (without a freshness context), to have an inexhaustible supply of fresh names, and to be able to quotient by -equivalence. We note in particular the papers [24, 23, 19, 18, 20], in which we have struggled with the theory of -equivalence given to us by nominal terms; these might benefit from the use of permissive nominal terms.
Permissive nominal terms syntax has two levels of variable, atoms and unknowns . There is no reason to stop there; we have already considered syntaxes with more than two levels of variable, for example [14, 16]. Again, we had difficulty with -conversion and fresh atoms. It would be very interesting to revisit this material armed with the permissive ideas of this paper.
Finally, it may be possible to extend the techniques of this paper to biject full higher-order unification with an enrichment of (permissive) nominal unification.
References
[1] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.
[2] Christophe Calvès. A Haskell Nominal Toolkit. In 2nd International Workshop on Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009), 2009. source code available online at: http://www.dcs.kcl.ac.uk/pg/calves/hnt/.
[3] James Cheney. Nominal Logic Programming. PhD thesis, Cornell University, August 2004.
[4] James Cheney. Relating nominal and higher-order pattern unification. In Proceedings of the 19th International Workshop on Unification (UNIF 2005), pages 104–119, 2005.
[5] James Cheney. Scrap your nameplate: (functional pearl). SIGPLAN Notices, 40(9):180– 191, 2005.
[6] James Cheney. Completeness and Herbrand theorems for nominal logic. Journal of Symbolic Logic, 71:299–320, 2006.
[7] James Cheney and Christian Urban. Alpha-prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proceedings of the 20th International Conference on Logic Programming (ICLP 2004), number 3132 in Lecture Notes in Computer Science, pages 269–283. Springer, 2004.
[8] Gilles Dowek, Murdoch J. Gabbay, and Dominic P. Mulligan. Permissive Nominal Terms and their Unification. Technical Report HW-MACS-TR-0062, Heriot-Watt University, 2009. Available online at gabbay.org.uk/papers/perntu-tr.pdf.
[9] Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: Proofs and models. In LPAR ’02: Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, pages 130–144, London, UK, 2002. Springer.
[10] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, 2007.
[11] Murdoch J. Gabbay. FM-HOL, a higher-order theory of names. In F. Kamareddine, editor, 35 Years of Automath, 2002.
[12] Murdoch J. Gabbay. A NEW calculus of contexts. In PPDP ’05: Proc. of the 7th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, pages 94–105. ACM, 2005.
[13] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.
[14] Murdoch J. Gabbay. Hierarchical Nominal Terms and Their Theory of Rewriting. Electronic Notes in Theoretical Computer Science, 174(5):37–52, 2007.
[15] Murdoch J. Gabbay. Permissive nominal algebra and semantic nominal unknowns: a new universal algebra for nominal techniques. Manuscript, 2010.
[16] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus (extended version). Information and computation, 207(12):1369–1400, 2009.
[17] 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. Springer, 2007.
[18] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008.
[19] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.
[20] Murdoch J. Gabbay and Aad Mathijssen. A nominal axiomatisation of the lambda-calculus. Journal of Logic and Computation, September 2009. Online access.
[21] Murdoch J. Gabbay and Aad Mathijssen. Nominal (universal) algebra: equational logic with names and binding. Journal of Logic and Computation, 19(6):1455–1508, 2009.
[22] Murdoch J. Gabbay and Dominic P. Mulligan. Semantic nominal terms. In 2nd International Workshop on Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009), 2009.
[23] Murdoch J. Gabbay and Dominic P. Mulligan. Two level lambda-calculus. Electronic Notes in Theoretical Computer Science, 246:107–129, 2009.
[24] Murdoch J. Gabbay and Dominic P. Mulligan. Curry-Howard for incomplete first-order logic derivations using one-and-a-half level terms. Information and Computation, 208:230– 258, 2010.
[25] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.
[26] 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.
[27] Robert Harper, Furio Honsell, and Gordon Plotkin. A framework for defining logics. In Proc. 2nd Annual IEEE Symposium on Logic in Computer Science, LICS’87, pages 194–204. IEEE Computer Society Press, 1987.
[28] Jan-Willem Klop, Vincent van Oostrom, and Femke van Raamsdonk. Combinatory reduction systems. Theoretical Computer Science, 121:279–308, 1993.
[29] 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.
[30] Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
[31] Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1(4):497 – 536, 1991.
[32] Dale Miller. Unification under a mixed prefix. Journal of Symbolic Computation, 14(4):321–358, 1992.
[33] Dominic P. Mulligan. Implementation of permissive nominal terms. source code available online at: http://www.macs.hw.ac.uk/˜dpm8/permissive/, 2009.
[34] Peter Nickolas and Peter J. Robinson. The Qu-Prolog unification algorithm: formalisation and correctness. Theoretical Computer Science, 169(1):81–112, 1996.
[35] Lawrence C. Paulson. Isabelle: the next 700 theorem provers. In P. Odifreddi, editor, Logic and Computer Science, pages 361–386. Academic Press, 1990.
[36] Frank Pfenning and Conal Elliot. Higher-order abstract syntax. In PLDI (Programming Language design and Implementation), pages 199–208. ACM Press, 1988.
[37] Andrew M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186(2):165–193, 2003.
[38] Andrew M. Pitts and Murdoch J. Gabbay. A Metalanguage for Programming with Bound Names Modulo Renaming. In MPC2000, volume 1837 of Lecture Notes in Computer Science, pages 230–255. Springer, 2000.
[39] Mark R. Shinwell, Andrew M. Pitts, and Murdoch J. Gabbay. FreshML: Programming with Binders Made Simple. In ICFP’03, volume 38, pages 263–274. ACM Press, 2003.
[40] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.
Appendix A. Supplementary proofs
Definition Appendix A.1 is useful for Proposition 2.21.
Proof of Proposition 2.21:
Reflexivity is shown by induction on terms. Symmetry is shown by induction on derivations. Transitivity is shown by induction on the size of a term. We consider one case from the proof of symmetry and one from the proof of transitivity:
Proof of Lemma 3.3:
Proof of Lemma 4.8:
We handle the two implications separately.
The case ) fa() implies . We proceed by induction on .
The cases and f) are straightforward.
The case . Since always, using (#[ȧ]).
The case [. Suppose ) fa([() and ) fa() (). Then ) fa(), therefore by inductive hypothesis. Using (#[ ḃ]), we have #[, and the result follows.
The case . Suppose ) fa( ). Then ) , where ) # . But ) # is the same as ) # . Then ) # ) # . Using Definition 4.6, and the fact permutations are bijective, we have ) #) #. We use (# Ẋ) to obtain # , and we have the result.
The case implies ) fa(). We proceed by induction on the derivation of .
The cases (# ḃ) and (#f) are routine.
The case (#[ȧ]). Suppose using (#[ȧ]). Then [)]. Further, ) fa() ), and the result follows.
The case (#[ ḃ]). Suppose and ) fa) by assumption. Then #[ by (#[ ḃ]). Further, fa([ fa() (), and the result follows.
The case (# Ẋ). Suppose )# , and by (# Ẋ). Then where ) # . Further, fa( . The result follows from Definition 4.6.
Proof of Theorem 4.9:
We prove that implies by induction on the derivation of :
The cases and f) are routine.
The case [a]). Suppose and . Then using [a]), [)] [)] and also, using ȧ]). The result follows, as [)].
The case [b]). Suppose (() )) and () fa(). By Lemmas 4.7 and 4.8 () and . By inductive hypothesis () . We use ḃ ]).
The case X). Suppose where ) # . is injective, so # for all such that ) ). The result follows by Ẋ ).
We prove that implies by induction on the derivation of :
The cases ȧ), f) and ȧ]) are straightforward.
The case ḃ ]). Suppose () and . By inductive hypothesis and Lemma 4.7, () . By Lemma 4.8, () fa(). The result follows by [b]).
The case Ẋ ). Recall that and where ) # . Suppose ) ) implies # . Using Lemma 4.8, ()) ()) implies ) . The result follows by X).
Proof of Lemma 4.13:
By induction on . We show two cases:
The case . We reason as follows:
The result follows.
The case . We reason as follows:
The result follows.
Proof of Lemma 4.15:
We prove by induction on that fa implies () :
The cases and f(). Straightforward.
The cases . We show ()
The case is similar.
The case . Suppose fa([]), fa([]) and fa. We show ()
The case . Suppose fa(), fa() and . By Definition 2.9, ()() (()). Using X), (()) whenever (()). As , (()). The result follows.
We prove by induction on that () implies fa:
The case , , and f() are routine.
The case . Suppose ()
The case is similar.
The case . By inductive hypothesis () implies fa. The result follows from []() ()
The case . Suppose () . By Definition 2.9, () (()) . Using X), (()) whenever (). It is a fact that () only when . The result follows.
The following definition is used in the proof of Proposition 5.4:
Define the size of a support inclusion problem size(Inc) to be a tuple (), where: is the number of term-formers appearing within terms in Inc, is the number of abstractions appearing within terms in Inc, is the number of permutations, distinct from the identity permutation, appearing within terms in Inc, and is the number of support inclusions within Inc. We order tuples lexicographically.
Proof of Proposition 5.4:
By case analysis, checking all simplification rules reduce the measure defined in Definition Appendix A.2.
The case . Suppose , size( ), and by (a). Then size( 1). Otherwise, suppose so (a) is not applicable. No other rule is applicable by assumption, and the result follows.
The case f() . Suppose size(f() ) and f() by (f). Then size( 1 1). The result follows from the ordering.
The case . Suppose size([] ) and by ([]). Then size( 1) and the result follows.
The case . Suppose size( ). Then, if , we have by (), with measure (1). Otherwise, if we have and id, we have
with measure ( 1). By assumption, no other rules are applicable.
The following definition is used in the proof of Proposition 6.7:
Define the size of a unification problem size() to be a tuple (), where: is the number of equalities appearing in the unification problem, is the number of term-formers appearing within terms in the equalities of the unification problem, is the number of abstractions appearing within terms in the equalities of the unification problem. We order tuples lexicographically.
Proof of Proposition 6.7:
By case analysis, checking all simplification rules reduce the measure defined in Definition Appendix A.3. We consider three cases:
The case (b]). Suppose fa and ; []]; () by (b]). Suppose further that size([]]). Then size(() 1), and the result follows.
The case (I1). Suppose fV and fa
Proof of Lemma 6.8:
The empty set cannot be simplified, so suppose where the simplification rule acts on . We reason by cases:
The cases (a), (f) and (X) are straightforward.
The case (a]). Suppose ]] and ] by (a]). Then:
Suppose ([]) ([]). By Definition 3.2, []( [](). By the rules in Definition 2.13, . The result follows.
Suppose . By the rules in Definition 3.2, []( [](). By Definition 3.2, ([]) ([]), as required.
The case (b]). Suppose ]], fa and ()
Suppose ([]) ([]). By Definition 3.2, []( [](). By the rules in Definition 2.13, () (. By Lemma 3.4 and Proposition 2.21, (() ). The result follows.
Suppose (()). By Lemma 3.4 and Proposition 2.21, ()(. By Lemma 3.3, fa(). Using [b]), []( [](). By Definition 3.2 []( [](), as required.
Proof of Lemma 6.14:
As the empty set cannot be simplified, it must be that . It therefore suffices to perform case analysis on the simplification of . At each stage, without loss of generality, assume has been simplified by non-instantiating rules as much as possible.
The cases (a), (f) and X) are routine.
The case (a]). Suppose ; []] and fV ([]]) , then ; []]; by (a]). By Definitions 2.12 and 6.4, fV ( ) , and the result follows.
The case (b]). Suppose ; []], fa with fV ([]]) , then ; []]; () by (a]). By Definitions 2.12 and 6.4 it follows that fV (() ) , and the result follows.
Proof of Proposition 7.12:
We prove reflexivity by induction on terms; symmetry by induction on derivations; transitivity by induction on the size of a term. We include one case from the proof of symmetry, and one from the proof of transitivity:
implies . Suppose () and fa. By Lemma 7.7, fa(() ). By Lemmas 7.8 and 7.6, () . By Lemma 7.9, fa. By inductive hypothesis () . Extending with ([b]) we obtain , as required.
and implies . Suppose () , () , fa and fa. By Lemma 7.6, () (() () . By Lemmas 7.11, 7.6 and 7.5 we have () . By Lemma 7.9, fa(() ). By Lemma 7.8, fa. We use (ab) to obtain , and the result follows.
Proof of Lemma 8.9:
By induction on .
The cases and f() are routine.
The case . We reason as follows:
There are now two cases:
The case (. Then:
The result follows.
The case () . Then:
The result follows.
The case . We reason as follows:
The result follows.
Proof of Corollary 8.10:
We reason as follows:
The result follows.
Proof of Lemma 8.13:
By induction on .
The cases and f() are straightforward.
The case . Suppose ([]). Then , and by inductive hypothesis fV exists such that . As fV ([] fV , the result follows.
The case . Suppose ([]). Then , and by inductive hypothesis fV exists such that . As fV ([] fV , the result follows.
The . The result follows immediately by Definition 8.7.
Proof of Lemma 9.11:
By induction on .
The cases and f(). Routine.
The case . By Definitions 2.9 and 8.7
By inductive hypothesis
By Definition 9.8 uncapt([] uncapt
By Lemma 9.9 capt
Suppose () . Then
Suppose ( and uncapt. Then uncapt(.
Suppose ( and uncapt. Then by Lemma 9.10 capt([]).
We consider cases for the ‘missing ’:
Suppose uncapt. Then uncapt
Suppose uncapt. Then by Lemma 9.10 capt([]).
In all cases, the result follows.
The case . Then:
The result follows.
Notes
1For example, () []()
2An similar idea is behind the notion of freshness contexts with sufficient freshnesses in [12, Subsection 3.1]. ↩
3Another layer of complexity arises. Some natural definitions rely on a sufficiently large supply of fresh atoms being available. Even if we can always extend the freshness context, for a fixed freshness context there may be inputs for which the function cannot be defined, and so is partial. This happens for example to the canonical form function in Subsection 5.3 of [24]. ↩
4See the documentation for module Nominal.Matching at http://www.dcs.kcl.ac.uk/pg/calves/hnt/doc/Nominal-Matching.html and module Terms.Terms in the permissive nominal terms implementation source code, available at http://www.macs.hw.ac.uk/˜dpm8/permissive/ ↩
5Other versions of are possible. We believe that a sufficient property for is that it be: co-infinitely down-closed (so if and is co-infinite, then ); and such that for any finite , the union is co-infinite (it does not have to be in ). The first property is sufficient to build the permission set in (1). The second property is sufficient to guarantee Corollary 2.14. This is similar in spirit to the notion of support ideal from [6, Definition 4.1]. ↩
6In fact, support inclusion simplification is confluent so nf (Inc) is also unique. A proof of confluence is in a technical report [8]. For our purposes in this paper, it suffices to know that a normal form exists. ↩
7Thanks to an anonymous referee for spotting the error in a previous proof. ↩
8Permission sets may be larger than as well as smaller, whereas intuitively in nominal terms freshness contexts can only make permission sets smaller. ↩