Nominal Rewriting
Maribel Fernández and Murdoch J. Gabbay
King’s College London, Dept. of Computer Science,
Strand, London WC2R 2LS, UK
Abstract
Nominal rewriting is based on the observation that if we add support for alpha-equivalence to first-order syntax using the nominal-set approach, then systems with binding, including higher-order reduction schemes such as lambda-calculus beta-reduction, can be smoothly represented.
Nominal rewriting maintains a strict distinction between variables of the object-language (atoms) and of the meta-language (variables or unknowns). Atoms may be bound by a special abstraction operation, but variables cannot be bound, giving the framework a pronounced first-order character, since substitution of terms for variables is not capture-avoiding.
We show how good properties of first-order rewriting survive the extension, by giving an efficient rewriting algorithm, a critical pair lemma, and a confluence theorem for orthogonal systems.
Key words: Binders, -conversion, first and higher-order rewriting, confluence.
Email address: Maribel.Fernandez@kcl.ac.uk, Murdoch.Gabbay@gmail.com (Maribel Fernández and Murdoch J. Gabbay).
Preprint submitted to Information and Computation 20 July 2006
Contents
2.2 Substitution and swapping 10
3.1 An algorithm to check constraints 15
4 Unification 25
5 Rewriting 33
5.2 Matching problems, and rewriting steps 36
5.3 Critical pairs and confluence 40
6 Uniform rewriting (or: ‘well-behaved’ nominal rewriting) 41
8 Closed rewriting (or: ‘efficiently computable’ nominal rewriting) 49
9 Sorts and Extended Contexts 54
9.1 Sorts 54
9.2 Extending freshness contexts 55
References 58
1 Introduction
This is a paper about rewriting in the presence of -conversion. ‘Rewriting’, or in full ‘the framework of Term Rewriting Systems’ (TRS), is a framework for specifying and reasoning about logic and computation. Usually, if the reader’s favourite formal system can be described by syntax trees (also called terms), then any notion of dynamics (deduction and evaluation for example) can probably be captured by a suitable collection of rewrite rules. For example (we are more formal later):
(1) Assume 0-ary term-formers (constants) S and K, and a binary term-former which we write infix. Then the rewrite rules
define a rewrite system for combinatory algebra (or combinatory logic) [6]. , , and are unknowns, which can be instantiated to any term. So from this rewrite system we may deduce (K S) K S and indeed (K ) .
(2) Assume constants , , and , and rewrite rules
This implements a rewrite system due to Mark Twain. 1
However, in the presence of binding, a notion of rewriting on pure abstract syntax trees is not as useful as we might like. For example, here are informal descriptions of the - and -reduction rules of the untyped -calculus [6]:
Note the freshness side-conditions on the right: () denotes the set of free variables of .
The -reduction rule ()[] raises some issues too: we need to define the capture-avoiding substitution [], and this involves more freshness side-conditions.
These rules introduce nondeterminism and make rewriting conditional. Experience also shows that they are difficult to reason about and pose specific implementation problems.
One answer is to take rules creating these issues, for example , as equalities on terms. We say that ‘names and binding are relegated to the meta-level’. A lot of effort has gone into developing systems along these lines. Several notions of rewriting modulo an equational theory have been developed, but none that can deal specifically with -equivalence (where equivalence classes of terms are infinite). Combinatory Reduction Systems (CRS) [31], Higher-order Rewrite Systems (HRS) [33], Expression Reduction Systems (ERS) [30,29], and the rewriting calculus [13,14], combine first-order rewriting with a notion of bound variable, and rewriting rules work on -equivalence classes of terms. In these systems the -calculus can be defined as a particular rewrite system with one binder: -abstraction.
A benefit of such systems is that non-capture-avoiding substitution can be implemented using capture-avoiding substitution. For example, the effect of ()[] (where here substitution for does not avoid capture) can be obtained in a higher-order system as ()[]. Thus, we do not lose any power by taking terms up to -equivalence (which forces all substitution to be capture-avoiding) so long as we also take them up to -equivalence.
Another approach is to bite the bullet and specify everything to do with , , , and so on, completely explicitly. To make this more manageable, substitution is introduced as a term-former, which does at least make reasoning on these equivalences susceptible to term-level inductions on syntax and so on. Explicit substitution systems have been defined for the -calculus (e.g. [1,32,15]) and more generally for higher-order rewrite systems (e.g. [35,9]) with the aim of specifying the higher-order notion of substitution as a set of first-order rewrite rules. In most of these systems variable names are replaced by de Bruijn indices to make easier the explicitation of -conversion, at the expense of readability. Explicit substitution systems that use names for variables (see for example [23,8]) either restrict the rewriting mechanism to avoid cases in which -conversion would arise (for instance using weak reduction, or closed reduction) or use Barendregt’s convention (all bound variables in a term have fresh names, different from the free variables; and this property is assumed to be maintained by reduction) to avoid addressing the problem of -conversion.
In this paper we present a framework for rewriting based on a different way of slicing these issues. We maintain a strict distinction between object-level variables (we write them and call them atoms), which can be abstracted but behave similarly to constants (whence the ‘nominal’, for ‘name’ in “nominal rewriting systems”, henceforth abbreviated to NRS) — and meta-level variables (we write them and may call them unknowns), which are first-order in that there are no binders for them and substitution does not avoid capture of free atoms (we may refer to our system as ‘first-order’, as opposed to higher-order systems which quotient terms up to -equivalence, and for which substitution is capture-avoiding and may involve -reductions). Our approach is based on the work reported in [36,24,41]. We deal with -conversion using a small logic for deriving a relation ‘are -equivalent’, in a syntax-directed manner (this gives us the great benefit that we can reason by induction on syntax and/or on the derivation that two terms are -equivalent); we deal with the freshness side-conditions mentioned above by introducing an explicit freshness relation between atoms and unknowns, written as # (read “ is fresh for ”; in fact, we write # where is any term, but this is derived by simple induction on syntactic structure). Then, as we shall see, -, - and other similar reduction rules can be easily defined, as rewrite rules.
We can see nominal terms as first-order terms, with a definition of -equality which explicitly supports our intuitive notions of ‘meta-variable’ and ‘freshness condition’. It combines many of the conveniences of higher-order techniques (smooth handling of - and similar reduction rules) with the syntax-directed simplicity of first-order techniques (a simple notion of substitution, decidable unification).
Consistent with previous work on nominal logic and unification [36,24,41], we call atoms the names that can be bound and reserve the words variable and unknown for the identifiers that cannot be bound (known as variables and metavariables respectively in CRSs and ERSs, or bound and free variables in HRSs). We leave implicit the dependencies between variables and names as it is common practice in informal presentations of higher-order reductions. More precisely, variables in NRSs have arity zero, as in ERSs (but unlike ERSs, substitution of atoms for terms is not a primitive notion in NRSs). For example, the -reduction rule and the -expansion rule of the -calculus are written as:
where the substitution in the -rule is a term-former, which has to be given meaning by rewrite rules.
To summarise, the main contributions of this paper are:
(1) We formulate a notion of rewriting on nominal terms which behaves as first-order rewriting but uses matching modulo -conversion. In particular, substitution remains a first-order notion: we deal with -conversion without introducing meta-substitutions and -reductions in our meta-language (in contrast with standard notions of higher-order rewriting, which rely on meta-substitutions and/or -reductions in the substitution calculus). Consequently in some cases we need freshness assumptions in terms and rewrite rules; these will be taken into account in the matching algorithm. We use nominal matching [41] to rewrite terms. Selecting a nominal rewrite rule that matches a given term is an NP-
complete problem in general [12]. However, by restricting to closed rules we can avoid the exponential cost: nominal matching is polynomial in this case. Closed rules are, roughly speaking, rules which preserve abstracted atoms during reductions; in particular, closed rules do not contain free atoms, hence their name. CRSs, ERSs, and HRSs impose similar conditions on rules, by definition (ERSs impose a condition on the substitution used to match a left-hand side, which corresponds to our notion of closed rules). Closed rules are very expressive: 2 see [21] for an encoding of CRSs using closed nominal rules. Translations between CRSs, HRSs and ERSs have already been defined (see [37]).
(2) We prove a Critical Pair Lemma which ensures that closed nominal rewriting rules which do not introduce critical pairs are locally confluent, and a confluence result for orthogonal systems (i.e. NRSs where rules have linear left-hand sides without superpositions). Similar results have been proved for CRSs and HRSs (see [31,33]).
Related work First-order rewriting systems and the -calculus provide two useful notions of terms and reduction, and both formalisms have been used as a basis to develop specification and programming languages. However, in both cases the expressive power is limited (although for different reasons): first-order rewrite systems do not provide support to define binding operators, and there are useful operations which cannot be encoded in the -calculus (see for instance [5], where it is shown that the rules for surjective pairing cannot be encoded in the -calculus). These observations motivated the search for more general formalisms combining the power of first-order term rewriting with the binding capabilities of the -calculus. Our work can be seen as part of this effort. In the rest of the introduction we will compare nominal rewrite systems with the rewrite systems with binders that have been defined previously.
(1) Algebraic -calculi, which can be typed [10,11,28,3,4] or untyped [17], combine the -reduction rule of the -calculus with a set of term rewriting rules. They use capture-avoiding substitution in -reductions, and first-order matching and substitution for term rewriting rules. They are more expressive than either the -calculus or first-order rewriting, but it was observed that properties of the latter formalisms are not automatically inherited by the combination. The papers cited above use types, or syntactical conditions in the rewrite rules, or both, to characterise subsystems that preserve confluence or termination for instance.
Algebraic -calculi can be defined as nominal rewrite systems, but as for the -calculus, the notion of capture-avoiding substitution has to be
explicitely defined using nominal rewrite rules.
(2) Higher-order rewriting systems (e.g. CRSs [31], HRSs [33], ERSs [30,29], HORSs [37]) extend first-order rewriting to include binders using higher-order substitutions and higher-order matching. In contrast with algebraic -calculi (which use first-order matching), binders are allowed in left-hand sides of higher-order rewrite rules. NRSs are related to these since nominal rules may also have binders in left-hand sides, however, nominal rewriting does not use higher-order matching; instead, it relies on nominal matching (which takes care of -equality). Although there is no ‘official’ definition of higher-order rewrite rule, it is generally acknowledged that CRSs, ERSs and HRSs (although using different presentations) define a canonical higher-order rewrite format (see [31]). The subclass of closed NRSs is also canonical in this sense. However, NRSs are more expressive than standard higher-order rewrite systems, we will give examples.
(3) Although NRSs were not designed as explicit substitution systems, they are at an intermediate level between standard higher-order rewriting systems and their explicit substitution versions (e.g. [35,9]), which implement in a first-order setting the substitution operation together with -conversions using de Bruijn indices. Compared with the latter, NRSs are more modular: a higher-order substitution is decomposed into a first-order substitution and a separate notion of -equality (a design idea borrowed from Fresh-ML [38]). Also, from a (human) user point of view, it is easier to use systems with variable names than systems with indices. The disadvantage is that nominal rewriting is not just first-order rewriting, therefore we cannot directly use all the results and techniques available for first-order rewriting. However, nominal rewriting turns out to be sufficiently close to first-order rewriting that it shares many of its desirable and convenient properties: efficient matching, a critical pair lemma, and a confluence result for orthogonal systems.
(4) Hamana’s Binding Term Rewriting Systems (BTRS) [27] also extend first-order rewriting to include binders and -equality, but use a de Bruijn notation. The main difference with Nominal Rewriting is that BTRSs use a containment relation that indicates which free atoms occur in a term (as opposed to a freshness relation which indicates that an atom does not occur free in a term). Not surprisingly, the notions of renaming and variants play an important rôle in BTRSs, as do swappings and equivariance in NRSs. In other words, when free atoms occur in rules, we have to consider all the (infinite) variants that can be obtained by renaming the free atoms. Selecting a rewrite rule that matches a given term is then NP, but we have characterised a class of NRSs for which matching is efficient and we conjecture the BTRS-matching algorithm is efficient in this case too.
(5) NRSs, with their use of freshness contexts in rules, could be seen as a form of conditional rewriting systems (see [7]), albeit with matching modulo . Takahashi’s -calculus with conditional rules [39] is a closely
related formalism: it is a higher-order rewriting framework in the sense that rules can include binders (there is a distinction between object-level and meta-level variables). As in NRSs, substitution of metavariables for terms is not capture-avoiding, but terms are defined as -equivalence classes of trees, and capture-avoiding substitution is a primitive notion as in ERSs. The requirement that rule schemes are closed under capture-avoiding substitution means that only closed NRSs can be expressed. On the other hand, the conditions on the rewrite rules in conditional -calculus systems are arbitrary (not just freshness predicates as in NRSs). We discuss in Section 9 extensions of NRS which can deal with more general contexts in rules.
This paper is an updated and extended version of [21]. Other work exists extending nominal rewriting in various ways [19] and considering types [20].
Overview of the paper Section 2 presents nominal signatures, terms and substitutions. In Section 3 we define -equivalence of nominal terms and give an algorithm to check it, which is used as a basis to design a unification algorithm in Section 4. Rewriting is defined in Section 5. In Section 6 we define uniform systems (a class of nominal rewriting systems which are well-behaved with respect to -equivalence), and prove the Critical Pair Lemma for uniform rules. In Section 7 we prove that orthogonality is a sufficient condition for confluence of uniform rewriting. A further restriction on rewrite rules is used in Section 8 to obtain an efficient implementation of nominal rewriting. In Section 9 we briefly discuss some extensions of nominal rewriting (with sorts, and with more expressive contexts for rewrite rules). We conclude the paper in Section 10.
2 Nominal terms
2.1 Signatures and terms
A nominal signature Σ is a set of term-formers typically written (though we do try to give them suggestive names in examples). For instance, a nominal signature for a fragment of ML has term-formers:
app lam let letrec
and a nominal signature for the -calculus is given by
in out par rep
In order to define operations over the syntax of ML for instance, we will need:
The notion of a term containing unknown terms represented by variables which can be instantiated, so that we can represent a schema of rewrites by a single rewrite rule. We call these (meta-level) unknowns.
The notion of an object-level variable symbol of the ML language, so that we can directly represent the variable structure of the object language, and define variable lookup, open terms, patterns, and -abstractions. We call these (object-level) variable symbols or atoms.
Of course, we would need the same if we wanted to model First-Order Logic, the -calculus, or any other syntactic system which mentions variable symbols.
Fix a countably infinite set of term variables ; these represent meta-level unknowns. Also, fix a distinct countably infinite set of atoms ; these represent object-level variable symbols. Consistent with later notation for terms, we write and to denote syntactic identity of unknowns and atoms. We assume that Σ, and are pairwise disjoint.
A swapping is a pair of atoms, which we write (). Permutations are lists of swappings, generated by the grammar:
We usually omit the last Id when we write the list of swappings that define a permutation. We call Id the identity permutation. We call a pair of a permutation and a variable a moderated variable and write it . We say that is suspended on . We may write for the permutation obtained by reversing the list of swappings in . For example if )() then )() and (. We denote by the permutation containing all the swappings in followed by those in .
Remark: represents an unknown term in which some atoms must be renamed (e.g. by some -equivalence taking place elsewhere in the term) — but because we do not yet know what is, the renaming sits suspended outside. When we come to define substitution of terms for unknowns [], we shall see that permutations ‘unsuspend’ and go into . For example, using the notation we introduce in a moment, ()[()] ().
Nominal terms, or just terms for short, are generated by the grammar:
Terms are called respectively atoms, moderated variables (or just variables for short), tuples, abstractions and function applications.
Note that is not a term, but Id is. We abbreviate Id as when there is no ambiguity. In the clause for tuples we call the length of the tuple. If = 0 we have the empty tuple (). We omit the brackets when is 1, if there is no ambiguity. If is applied to the empty tuple we may write () as just .
We write () for the set of variables occuring in . Ground terms are terms without variables, that is (. A ground term may still contain atoms, for example is a ground term and is not.
An abstraction [] is intended to represent with bound, as in the syntax (from the -calculus) and (from the -calculus). Accordingly we call occurrences of abstracted (or bound) and unabstracted occurrences unabstracted (or free). We do not work modulo -conversion of abstracted atoms, so syntactic identity is not modulo -equivalence; for example, [] . -equivalence is a logical notion constructed on top of using a notion of context which we shall define soon.
Recalling the signature for ML mentioned previously, the following are nominal terms (and the last one is ground):
app(lam([])) (lam([]lam([]))) let([])
We define the following sugar:
Sugar app() to .
Sugar lam([]) to .
Sugar let([]) to let in .
Sugar letrec([]([])) to let in .
There is nothing to stop us writing app([]) if we like, because we have, for simplicity, introduced no notion of arity or sort system. We discuss this later in Section 9, see also [20].
2.2 Substitution and swapping
Substitutions (of variables for terms) are used to instantiate unknowns and to represent matching or unification solutions. In systems with binders, substitution is not so easy to define because it should avoid capture of bound variables, so -conversions may be needed. -conversion is in turn traditionally defined by using a ‘simpler’ kind of substitution — renaming, that is, substitution of atoms by atoms — where an atom is replaced by a fresh one. Instead of using renamings, nominal techniques define -equivalence and freshness using swappings. Intuitively, a swapping () is a special kind of first-order substitution which replaces simultaneously by and by in the syntax of the term, suspending on variables. Swappings have better commutation properties (with substitutions and with -equivalence) than renamings — no side conditions are required. We will return to this point later.
As discussed represents an unknown term with some swappings waiting to happen. This is reflected in the definition of the action of permutations and substitutions on terms below, denoted and [] respectively.
(Permutation) The action of a permutation on a term is defined by induction on the number of swappings in :
where
Here, are any pairwise different atoms.
For example, ()().
Note that although () and () are different swappings, they have the same action on terms. We will show (see Lemma 19) that two permutations with the same action are logically undistinguishable,.
(Substitution) A substitution is generated by the grammar
We write substitutions postfix and write for composition: () ().
acts on terms elementwise in the natural way:
Remark: There is no primitive notion of substitution of a term for an atom in Nominal Rewriting, since some languages have variables which do not represent terms (e.g. the -calculus, which only has variable-for-variable renaming, or a language with global state which may have location variables and a notion of generating new location variables, but no notion of replacing one location by another). Various different kinds of substitution on atoms can be efficiently implemented by rewrite rules — but substitution of terms for unknowns is primitive since we need it to express matching and thus rewriting.
Note that [] really does replace every in by in a completely unimaginative way — in particular ([])[] []([]) does not avoid capture of in by the abstraction — except for the clause ()[] , where a suspended permutation becomes ‘active’ and acts on . Permutations act top-down and accumulate on moderated variables whereas substitutions act on the variable symbols in the moderated variables. These observations are the core of the next lemma.
Substitution and permutation commute: () ().
By induction on : The property is trivial for atoms since they are not affected by substitutions. For moderated variables the property follows directly from the definition of substitution. The cases of tuples and function applications are easily dealt with by the induction hypotheses. The only interesting case is abstraction: () ([]()) by Definition 3, and ([]) [](()) by Definition 4. Now by induction we obtain []() which is []() by Definition 3.
Remark: In contrast with the Substitution Lemma [6], in the lemma above we do not need to compose substitutions and there are no free variable side-conditions.
3 Alpha-equivalence
The notion of ‘fresh variable’ plays an important rôle in the definition of -equivalence. We will introduce a freshness predicate # and an alpha-equality predicate :
# intuitively means that if occurs in then it must do so under an abstractor []-. For example, #, and #[] but not #. We sometimes write # instead of ##.
intuitively means that and are -equivalent.
Syntactic equality is a structural (rather than logical) fact. Intuitively, in the absence of unknowns # and are also structural facts — to check # for example we just check that every in occurs under an abstractor. However, in the presence of unknowns both predicates may depend on assumptions # about what will get substituted for the unknowns (the simplest example: we may derive # if we assume . . . #). Formally, we define # and by a logical system. We use # in the definition of , which expresses the ‘freshness side-conditions’ mentioned in the introduction.
Constraints are generated by the grammar
and specified by a system of natural-deduction rules as follows ( are any pair of distinct atoms):
To define we use the difference set of the two permutations:
In the rules defining below, ()# denotes the set of constraints:
Remark: Rule (absb) is equivalent to a rule with premisses ()#
We can derive #(() ()) from assumptions ##, using the fact that ().
We can also derive #(
Also, we can deduce () from assumptions # and #, and we also have as expected []
Here we use the fact that (() Id. We recall that () is actually lam([]lam([]app( app( Id)))), where lam is applied to a tuple with one element. We write several rules used together as (rule1rule2).
We call constraints of the form # and # reduced, and write Γ for sets of reduced constraints, we may call them contexts. If there are no constraints of the form # in we say it is consistent.
Intuitively, an assumption # can never be true; we could add a rule in the system to reflect this fact:
See [19] for a presentation with this rule. On the other hand, # might be true if we instantiate sensibly (to , say, but not to ).
(Problems and entailment) A set of constraints will be called a problem. We write when proofs of exist for all , using the derivation rules above and elements of the context as assumptions. We say that entails . If because we say trivially entails , or that the derivation is trivial.
Remark: In contrast with higher-order systems, here -equivalence is axiomatised instead of being built into the syntactic equality. This might seem inefficient, because to decide -equivalence in the front end (the syntax we use to reason about terms) we must do an explicit proof. However, this is an illusion, since we are free in nominal rewriting, as with any other framework, to choose the back end (the underlying representation) wisely so it is efficient for the manipulations we intend to carry out. When we define nominal matching later, we will build the -equivalence into the matching algorithm; but by making the calculation of -equivalence explicit in the front end, we lost nothing and gain useful proof principles.
We give below the specification of an algorithm to check the validity of freshness and -equality constraints.
3.1 An algorithm to check constraints
The rules above decompose syntax and the part above the line in a rule is always strictly simpler than the part below the line. This is not completely
obvious for the second rule for abstractions until we recall that () is not itself a term but sugar for a term with swapped with and (if there are unknowns in ), () suspended on . The depth of this term is strictly less than that of []. Based on this observation, we give below an algorithm to check constraints. We refer to [18] for a description of an efficient implementation.
The algorithm is specified as a set of simplification rules acting on problems. We will later extend these rules to solve matching problems between left-hand sides of rewrite rules and terms; in anticipation we use for terms in the simplification rules for .
(Simplification rules for problems) Here denote any pair of distinct atoms, denotes a moderated variable, and a term-former.
These rules define a reduction relation on problems: We write when is obtained from by applying a simplification rule, and we write for the transitive and reflexive closure of .
These rules ‘run the derivation rules in reverse’, in no particular order. In view of the example derivations above, we leave the reader to check that the following hold:
and that the following hold:
Intuitively, if a constraint can be reduced to the emptyset (as in the second example for above) then the predicate holds. If after simplifying a problem as much as possible, still some constraints remain, then we will need those as assumptions to derive the constraints in the problem. We will formalise these observations below.
The relation is confluent (i.e. and implies that there exists such that and ) and strongly normalising (i.e. the simplification process terminates).
By Newman’s Lemma [34] we need only show termination, because the simplification rules do not overlap (there are no critical pairs). The rules form a hierarchical system in the sense of [22], from which it follows that if the first group of rules is terminating (it is, since the rules decrease the size of the problem, defined as the multiset of sizes of individual constraints) and non-duplicating (it is, since no terms are duplicated) and does not use in the right-hand side any symbol defined in the second group (i.e. equality ; it doesn’t), then if the rules for the equality symbol satisfy the general recursive scheme, then the whole system is terminating. The general recursive scheme requires that recursive calls in right-hand sides use strict subterms of the left-hand side arguments, and this is the case (permutations are ignored).
As a consequence, the simplification rules define a function from problems to their unique normal forms. We write for the normal form of , and nf for i.e. the result of simplifying it as much as possible.
The following technical properties are direct corollaries of confluence of =:
and as a corollary if then
The algorithm for determining works elementwise on the elements of , and is confluent by Lemma 11.
We will say that an equality constraint is reduced when one of the following holds:
and are distinct atoms. For example is a reduced equality.
and are applications with different term-formers (e.g. ).
and are two different variables. So is reduced, but is not, for any and .
and have different term constructors at the root. For example [] (), , and , are all reduced equalities.
Recall from 3 that we call a freshness constraint # reduced when it is of the form # or # (i.e. when or ). We call the first inconsistent and the second consistent.
Say a problem is reduced when it consists of reduced constraints, and inconsistent when contains an inconsistent element — so is inconsistent if and only if is, if and only if # for some .
is reduced if and only if
We check the simplification rules above, and the definition of a reduced constraint, and see that a simplification rule applies to a constraint, if and only if that constraint is not reduced.
(Characterisation of normal forms) (1) # is a context , as defined in Section 3.
need not be consistent. For example ## is an inconsistent context.
(2) is of the form where is a set of consistent
reduced freshness constraints (that is, a consistent context), is a set of reduced equality constraints, and is a set of inconsistent reduced freshness constraints.
Any of , , and , may be empty.
(3) is of the form which is as above.
Direct consequence of the previous lemma.
So now we know simplifies to a unique normal form and we have a good idea of the structure of
The rest of this subsection addresses the question: How do logical entailment Γ and interact?
(1) Assume . Then Γ if and only if Γ
(2) Γ if and only if Γ
(1) There are 12 simplification rules which could have been applied in a step so there are precisely 12 cases to consider. Each corresponds precisely to one of the 12 syntax-directed derivation rules defining the entailment relation. The result follows by induction on the number of steps in the simplification .
(2) An immediate consequence of the first part.
If Γ is consistent and Γ then is consistent and moreover if it is in normal form then it does not contain equality constraints.
By a simple induction on derivations.
Write as described by Corollary 14. if and only if and are empty.
By Lemma 15, Γ if and only if Γ . The result now follows easily by Lemma 16 because ∆is consistent (see Corollary 14).
Let Γ and be consistent contexts, and and be any problems.
(1) Correctness of the Algorithm: Γ if and only if (that
is, and are empty) and Γ .
(2) Cut: If Γ and Γ Ψ, then Γ Ψ. (This is, of course, a form of Cut rule.)
In particular, if Γ and are both consistent and Γ and Ψ,
then Γ Ψ.
(3) If Γ and Γ, then Γ .
(1) Suppose Γ . By Theorem 17, = ∆and by Lemma 15, Γ Conversely if = ∆and Γ ∆, by the same results Γ .
(2) Suppose Γ ∆. By the first part of this result, Γ for each Now we can paste into the derivation of ∆ Ψ to obtain a derivation of Γ Ψ as required.
(3) By the previous two parts.
3.2 Properties of # and
The following lemma indicates that use of permutations is extensional, in the sense that lists of swappings denoting the same permutation, are logically indistinguishable.
Suppose is a context. If ( then:
(1)
(2)
(3)
(4)
We consider the four logical equivalences in turn:
(1) We observe simply that ( precisely when always, so and there is nothing more to prove.
(2) We work by induction on the derivation of # from . Note that because of the syntax-directed nature of the derivation rules, this is equivalent to working by induction on the syntax of . We consider just a few cases.
Suppose the derivation concludes in (#X), so # and # . By the same observation as before (i.e., (), and we are done.
Suppose the derivation concludes in (#absa) so #([]) and . Since we use (#absa) to build a derivation of #.
Suppose the derivation concludes in (#absb) so #([]), , and # is derivable. By inductive hypothesis # is derivable, and we continue as in the previous case.
(3) We work by induction on the derivation of . Again, we consider only a few cases.
Suppose the derivation concludes in (X), so we conclude from # for every (). We now observe that (() so we can write a derivation concluding in , from the same hypotheses.
Suppose the derivation concludes in (a). It suffices to observe that always.
Suppose the derivation concludes in (absa), so we conclude [] [] and is also derivable. By inductive hypothesis and since we can extend this derivation with (absa) to derive [] [].
Suppose the derivation concludes in (absb), so we conclude [] where , and () and # are also derivable.
We now observe that (() () (trivially, since ( and ), and the result follows by the inductive hypothesis and by part 2 of this result.
(4) Much as for the previous case.
For example, the lemma above allows us to replace with Id since ( Id.
Given a derivable judgement , we can:
(1) instantiate unknowns ( maps to in a suitable formal sense), and
(2) permute atoms ( maps to ).
We show that derivability is preserved by both. Note that for the case of permutation we only permute atoms in the conclusion , not in the assumptions . 3
In the rest of this section we assume that we are working with a consistent context unless stated otherwise, in other words, we consider derivations
where is a consistent context.
(1) If # then #. Similarly if then .
This can be restated as follows: if and only if , where here the action of is pointwise on all terms mentioned in .
(2) # if and only if #, and similarly if and only if . (This turns out to be particularly useful.)
The first part is by routine induction on derivations. We consider a few cases:
Suppose the derivation concludes in (#X), so # is derivable. It follows that #. It is now easy to construct a derivation of #, using (#X).
Suppose the derivation concludes in (#absb), so #[] is derivable. By the inductive hypothesis # is derivable, and we can also extend its derivation with (#absb).
Suppose the derivation concludes in (absa), so
Suppose the derivation concludes in (absb), so
are derivable.
Now it is a fact that (() (). Therefore, by Lemma 19
are derivable, and so using (absb) we obtain
as required.
For the second part, we simply observe that (Id and use Lemma 19 and the first part.
We use this technical lemma in Lemma 22 below (a converse to this lemma is also true, see Lemma 34).
If # for each (), then .
We work by induction on the syntax of for all and .
(1) Suppose for some atom . Now either () or not; if () then # contradicting our assumption that is consistent. Otherwise, and there is nothing to prove.
(2) If we observe by group theory that ((), and we can use (#X).
(3) Suppose
(a) In the first case we construct a derivation as follows:
To explain the right-hand branch of the proof, we must do some basic group theory. Since , also (), so (), and finally
Thus, () and # is derivable. Using the previous lemma # is derivable as required.
Concerning the left-hand branch, we observe that the top line is not a real derivation rule but represents a use of the induction hypothesis, having verified (by some more basic group theory) that
(b) In the second case (()) we write and construct a derivation as follows:
(Here the topmost horizontal line actually represents a derivation which by Lemma 21 exists.)
(4) Other cases are similar and simpler.
Suppose and are consistent.
If # then #(). Similarly if then () (). More generally, if then .
We work by induction on the derivation of # or . We consider a few cases:
Suppose the derivation concludes with (#X) so #. It follows that #. By Lemma 15 (#) (#). Also, by Corollary 12 #
Therefore #. By Lemma 20 #() and by Lemma 5 () (), and the result follows.
Suppose the derivation concludes with (#absb) so #[] and # are derivable. By inductive hypothesis # is derivable. We also observe that []() ([]) and the result follows.
Suppose the derivation concludes with (X) so # for each () and is derivable.
By inductive hypothesis # for each (). We now use the preceding technical lemma.
Suppose the derivation concludes with (absb) so
(1) If # and then #.
(2) If and then .
For the first part (#) we work by induction on the syntax of :
If then by the syntax-directed nature of the rules for deriving , we see that the derivation must conclude in (X) so and # for every (). Now suppose #. By Lemma 20, #. If () then # and by Lemma 20, #. If () then also () so by the argument above, # and by Lemma 20, #.
If
(1)
(2)
(3) If () then again by the syntax-directed nature of the rules, the derivation must conclude in (tup) so () and we use the
inductive hypothesis.
(4) Other cases are similar.
For the second part (), we sketch the proof semi-formally, but it can very easily be made completely formal in the style of the first part. We work by induction on the size of (permutations are not counted in the size):
If , the result follows by easy calculations to verify that () () ().
If
If
If
If
It follows by induction that () (). Now (() () (
Now by inductive hypothesis we may complete the proof.
Other cases are simple.
Fix a consistent context and say is an equivalence relation when it is reflexive, transitive and symmetric (as usual). Say is a congruence when it is an equivalence relation such that if then , []
is an equivalence relation and a congruence in a consistent context.
Transitivity is by the previous lemma. Reflexivity is by an easy induction on syntax. Symmetry is slightly non-trivial.
We work by induction on the maximum of the sizes of and proving that if then . Mostly this is easy, but (absb) causes difficulty because of its asymmetry. Suppose
Congruence is by induction: suppose . Then:
() () using (tup).
[] [] using (absa).
by Lemma 21.
If is a freshness constraint # or equality constraint , write [] for #[] or [] [] respectively.
Suppose Γ is consistent and Γ . Then:
(1) Γ [] is derivable if and only if Γ [] is derivable.
(2) Γ[] is derivable if and only if Γ[] is derivable.
(1) The case of follows by the previous theorem. The case of # follows again by the previous theorem, and by part 1 of Lemma 23.
(2) Observe that Γ[][] by Lemma 15. Using the first part of this result, Γ[][].
Now suppose Γ[]. Then using Corollary 18 and the observation in the previous paragraph, we conclude that Γ[] .
So equality is ‘an equality’ with respect to the simple logic given by #, , and .
4 Unification
4.1 Definitions
As usual unification is about finding some substitution making two terms and equal; however, now the notion of equality is our ‘logical’ notion of .
(Unification problems) A unification problem is a problem as previously defined but replacing equality constraints by unification constraints .
We recall from Corollary 14 that is of the form ∆ where ∆is a consistent freshness context, is a set of inconsistent freshness constraints, and is a set of reduced equalities. For example, # (). Intuitively, a solution to []
(Solution) A solution to a unification problem is a pair (Γ) of a consistent context and a substitution such that:
(1) Γ where is obtained from by changing unification predicates into equality predicates and is the problem obtained by applying the substitution to the terms in .
(2) for all (we say the substitution is idempotent).
If there is no such (Γ) we say that is unsolvable.
Write () for the set of unification solutions to .
The condition of idempotence is not absolutely necessary, but it is technically convenient and since our algorithms (see the next subsection) generate only idempotent solutions, we lose nothing.
Solutions in () can be compared using the following relation (we will show it is actually an ordering).
Let be consistent contexts, and substitutions. Then () () when there exists some such that
If we want to be more specific, we may write () ().
defines a partial order on (), call it the instantiation ordering.
Reflexivity is trivial. For transitivity, suppose () () (). Then we know (writing slightly informally):
Since is consistent, is consistent by Lemma 16. Since is consistent, is consistent by the same result. We also know
by Lemma 22. Finally, we use Corollary 18 and Theorem 24 to deduce
as required.
A least element of a partially ordered set is one which is related to (we generally say less than or equal to) every other element of the set.
A principal (or most general) solution to a problem is a least element of ().
4.2 Principal solutions
We will now show that every solvable unification problem has a principal idempotent solution. The algorithm is derived from the simplification rules from the previous section, enriched with instantiating rules, labelled with substitutions. The conditions in the instantiating rules are usually called occurs check.
Note that the instantiating rules above apply also in the case . Also note that we do not solve freshness constraints by instantiation — for a problem like it is obvious we should instantiate to , but there is no obvious most general instantiation making, say, # true (any more than there is an obvious instantiation making, say ‘ is a natural number’ true); any term such that is fresh for would do. This is why we always work in a freshness context.
The simplification and instantiation rules specify a unification algorithm: to solve a problem , we will apply the rules until we obtain an irreducible problem. This algorithm is in essence the same as [41] although our presentation is slightly different.
Many different possible reduction paths exist for a given , since it may have many formulae each of which is susceptible to some simplification. Neither are reductions necessarily confluent; for example,
However reductions do always terminate with some normal form, since at each step either a formula becomes smaller, or the number of variables in the problem is reduced by one. Also we shall see later that these normal forms are all equivalent in a natural and useful sense (see Lemma 33).
It will be useful to syntactically characterise normal forms; for this, we define reduced unification constraints:
A unification problem is reduced when one of the following holds:
and are distinct atoms. For example is reduced.
Precisely one of and is a moderated variable and the other term mentions that variable (so the occurrence check in the instantiating rules fails). For example () or () , but not or .
and are applications with different term-formers (e.g. ).
and have different term constructors at the root and neither is a moderated variable. For example ().
We may call all reduced unification constraints inconsistent.
If reduces to a normal form via some sequence of substitutions , write for the tuple ().
(Unification normal forms) # is (# Id).
is a problem of the form and a substitution, where is a consistent freshness context, is an inconsistent freshness context and is a set of inconsistent unification constraints.
As a corollary, is a problem of the form as above and a substitution.
Just as in Corollary 14. We check that the simplification and instantiating rules are applicable to any non-reduced unification or freshness constraint.
If we write ) we presume that ∆with substitution and and are empty. In this case, we may call (∆) the solution of (soon we shall show it actually is a solution to , in the sense that ) ()).
For example ## Id) and (
We now show that the unification algorithm checks whether a problem is solvable or not, and moreover it computes a principal, idempotent solution, if one exists. Thus the particular reduction path does not matter; we make some canonical but arbitrary choice and use it silently henceforth, for example we may talk about ‘the normal form’ of a problem.
(Preservation of solutions)
If using a simplification rule then (().
For simplicity suppose
(1) Suppose # #. Suppose Γ #(). Then we use part 2 of Lemma 20.
(2) Suppose ## where (. Suppose Γ . The result follows by Lemma 34 below.
This result is the converse of Lemma 21.
If then # for each ().
By induction on the structure of .
(1) If then the derivation concludes in (X). The result is immediate.
(2) If then so () and thus any () is not the same as and the result follows using (#ab).
(3) If () then the derivation must conclude in (tup) and for 1 . By the inductive hypothesis # for 1 and each (). Finally we deduce #() for each () using (#tup).
(4) The case () is similar.
(5) If
(a) If then the reasoning is much as for tuples above.
(b) If (i.e. ()) then the derivation must conclude in (absb), so # and () where we set and .
By the inductive hypothesis # for each (()). Now it is a fact that (() ) is those atoms in () not equal to or . Therefore by inductive hypothesis, # for each () not equal to or and using (#absa) and/or (#absb), we have #[] for the same .
We also have # by the above and using part 2 of Lemma 20, so #[] for . 5 Then, #[] by (#absa).
Let be a unification problem, and suppose ). Then:
(1) ) ().
(2) Also ) ) for all other ) (). That is, the solution is also a least or principal solution.
We work by induction on the length of the reduction .
Suppose is in normal form. Then:
(1) Trivially = ∆and Id, and equally trivially ∆ Id and Id is idempotent.
(2) For any other (∆) () trivially is such that ∆ and Id for all .
Suppose by some non-instantiating simplification. Then using Lemma 33, we know that ((). Both parts of the result follow by induction.
Suppose by an instantiating rule. So where ] and (). Suppose ), so that by construction ).
(1) It is easy to see that is idempotent and by the first part of the inductive hypothesis ∆ , that is, (∆) ().
(2) Suppose (∆) (). Then ∆ by part 2 of Lemma 20.
By part 1 of the technical lemma which follows (Lemma 36) and using its notation, (∆) () where acts just like only it maps to , ], and . By part 2 Lemma 36) () and by inductive hypothesis (∆) ). By part 4 it follows that ) ).
(1) Suppose is idempotent and . Then if and , then () where ] and acts just like , only . Furthermore, .
(2) Continuing the assumptions and notation above, if ) () and , then ) ().
(3) For all , , and , if for all , then for all . (‘Two -equivalent substitutions on a single term give two -equivalent terms.’)
(4) For all , , , and , if ) ) then ) ).
(1) We observe that and for any other , .
(2) By part 1 of Corollary 25, and using idempotence.
(3) By part 1 of Corollary 25.
(4) By definition if (∆) ) then for some and ∆ for all . The result follows by the previous part of this lemma.
We conclude with two routine but important results:
(1) If is a non-empty set of inconsistent unification constraints then it has no solution.
(2) If Γ is an inconsistent context then it has no solution.
By definition, a solution to , if it exists, must be of the form (∆) for some freshness context ∆such that ∆ , where here we are a bit lax and convert the unification problems in into equality problems. Lemma 32 tells us what form can take and we check that each kind of problem corresponds to a reduced equality problem. The second part of Theorem 17 then tells us that ∆ simply cannot happen.
Now suppose Γ is an inconsistent context. By Lemma 32 Id). Suppose this is a solution to Γ, so that Γ and nf is consistent. This is not possible since no derivation rule allows us to derive an inconsistent constraint from a consistent context.
Let be a unification problem such that ). Then () is nonempty if and only if .
The right-to-left implication follows by Theorem 35. For the left-to-right implication we work by induction on the length of the reduction .
Suppose is in normal form. Then by Lemma 32 . If is nonempty then by Lemma 37 () is empty. Conversely if is empty, we observe trivially that ∆ Id and () contains (∆ Id).
Suppose by some non-instantiating simplification. Then using Lemma 34 we know that ((). We use the inductive hypothesis.
Suppose by an instantiating simplification, so and ].
Suppose ∆. Then ∆ where acts just like only , and (∆) (). The result follows by the inductive hypothesis for .
Rewriting needs a notion of matching; we develop a suitable one in 5.2.
5 Rewriting
5.1 Rewrite rules
We will define a notion of rewriting which operates on ‘terms-in-consistent-contexts’: a pair (∆) of a consistent context and a term, which we write . Then ∆ rewrites to ∆ — a freshness context is fixed. Since in a particular rewriting path the context is fixed, a given context defines a particular rewrite relation ∆ - - which we define below.
A nominal rewrite rule is a tuple of
a consistent context ; and
terms and such that ()
We now develop a theory of nominal rewriting; we will see in Section 6 that a uniformity condition on becomes useful for rewriting to be truly well-behaved. However, the ‘engine’ driving rewriting remains what we now construct.
In this example we will use the signature of ML and the syntactic sugar defined in Example 2.
(1) # () is a form of trivial -reduction.
(2) #[]() is -expansion.
(3) Of course a rewrite rule may define any arbitrary transformation of terms, and may have an empty context, for example .
(4) # is not a rewrite rule, because (). is also not a rewrite rule.
(5) is a rewrite rule. We mention this again below.
We can now write
We shall never write the substitution in such detail, but this is how we instantiate rules.
As usual we shall consider rules up to permutative renaming of their variable symbols . Thus # () and # () are ‘morally’ the same rule.
Similarly it is convenient to consider atoms up to permutative renamings, so that if we have a rule #[]() then also # []() is available.
It will be useful to have a notation for permuting atoms in the syntax of rules and terms, as we just did above: Write for that rule obtained by swapping and in throughout. For example, if #
A simple technical lemma will be useful in Theorem 50, we mention it now:
for any , where for each mentioned in .
The proof is by an easy induction on and can be illustrated by an example: if we take () and ) then ()() and ()(). The suspended permutations are not identical, but their difference set is empty and the result follows.
A set of rewrite rules is equivariant when it is closed under () for all atoms and .
A nominal rewrite system (Σ) consists of:
(1) A nominal signature Σ.
(2) An equivariant set of nominal rewrite rules over Σ.
We may drop Σ and write for the rewrite system. When we write out the system we (obviously) do not bother to give every possible permutation of variables and atoms. Indeed, given any set of rewrite rules we can always obtain an equivariant one by closing under the permutation action () outlined above (call this the equivariant closure of the set of rules). We shall generally elide this step and equate a (finite, non-equivariant) set of rewrite rules with its equivariant closure.
Note that rewrite systems are “metalevel equivariant”, as opposed to the “internal equivariance” of predicates # and shown in Lemma 20 part 1. In other words, we define a rewrite system as an equivariant set of rules, whereas we can prove that # and are preserved by permutations.
To give a small-step evaluation relation for our fragment of ML (see Examples 2 and 40) we extend it with a term-former for (explicit) substitutions sub which we sugar to . The rewrite rules:
define a system of explicit substitutions for the -calculus with names. We add the following rules:
We can define a signature for first-order logic with term-formers , , , , , and rewrite rules to compute prenex normal forms (here we use variables , ) :
We could also add rules:
We recapitulate aspects of nominal terms and rules which are unusual with respect to a first-order system:
(1) Moderated variables (), which let us ‘suspend’ renamings.
(2) The unusual term constructor abstraction [].
(3) The freshness side-conditions, such as #. We use them to avoid accidental variable capture.
(4) The -equivalence relation , which uses all three of the above.
We now define the process of rewriting.
5.2 Matching problems, and rewriting steps
We do want a rewrite system to induce some actual rewrites on the set of terms in its signature. Here’s how:
A matching problem (in context) is a pair
where are consistent contexts and are nominal terms. The solution to this matching problem, if it exists, is a substitution such that:
.
for ).
We say that solves the matching problem.
Note that a matching problem can be seen as a particular kind of unification problem. The conditions in the definition above ensure that: ∆ and ∆ , and so (∆) (). We can think of the solution to () ) as being a most general such that (∆) solves . For notation and terminology see 4.
Remark: This is more than just matching modulo -conversion because we can use to specify constraints which must be satisfied by the matching solution. When the conditions in are satisfied we say the matching is triggered. (Soon, will be the left-hand side of a rewrite rule , and then we say the rule is triggered.)
(1) () () has no solution.
(2) (
(3) ([][]) ([][]) has solution ()].
(4) (#) () has no solution (because the only candidate, [], causes the condition # to become inconsistent).
Say a term has a position when it mentions a distinguished unknown, we usually write it -, precisely once, and with trivial moderation. We let capital letters vary over terms with a position. We write [] for [-], and [-] when the term is precisely its unique variable. Since the term is only of interest inasmuch as - may be substituted for a term, we shall tend to silently assume that - is fresh.
For example, []( -) has a position, but not (- -) or ()-. 6
Suppose is a rewrite rule, and are terms, and is a consistent context. We say rewrites with to in the context , and we write when:
(1)
(2) for some position [-], and term , such that solves ( ) ).
(3) [] .
If [-] we say the the rewrite occurs at the root position. Otherwise we may (semi-formally) say that the rewrite occurs at .
Given a nominal rewrite system say that rewrites to in a context ∆, and write ∆ or just ∆ , when there is a rule such that .
The rewrite relation is the reflexive and transitive closure of this relation. A normal form is a term-in-context that does not rewrite.
We now give some examples of rewrite steps:
(1) It is easy to show that
in four steps using the rules (Beta) and () of Example 43 together with a rule for the propagation of substitutions under :
In a CRS a similar reduction is done in one step, using a higher-order substitution mechanism which involves some -reductions. NRSs use first-order substitutions and therefore we have to define explicitly the substitution mechanism, but in contrast with first-order TRSs we don’t need to make explicit the -conversions. For instance, rule () (see Example 43) pushes a substitution under a avoiding capture, as the following rewrite step shows:
(2) A pathological but illuminating example of rewriting rule is . Then , but we can also verify that . In general, in the presence of this rule, if ∆ then ∆ , for example # ().
This will not cause problems in confluence results because they are also defined up to .
(3) If is in an equivariant set of rewrite rules, we have a rewrite step for any pair of different atoms and . Our notion of matching does not instantiate, or even permutatively rename, atoms; however, equivariance of the rule system as a whole guarantees that if a rule exists then a rule with permutatively renamed atoms is available.
Nominal rewriting systems are more expressive than first-order systems, as Examples 43 and 44 show. They are also more expressive than standard higher-order formats, as Example 49 shows.
We add to the signature of the -calculus with names (see Example 43) a second operator for substitution, csub, representing context substitution, which does not avoid capture. We introduce a unary term-former to represent ‘a hole’ in a -term, and we abbreviate () to . We write csub(), which we sugar as []; we are supposed to think of this as ‘replace the hole in by ’. We specify this intuition formally using nominal rewrite rules:
Note that the second rule will capture any occurring in an instance of . It is hard to see how these rules would work in a formalism in which terms are taken to be -equivalence classes.
Note that we take to be a unary term-former and not a constant (a 0-ary term-former); for suppose we just took as a constant. Then . This is not the -equivalence behaviour we expect of a binder with a hole in its scope and it would lead to incorrect rewrites such as ()[] .
Another solution would be to pick some distinguished variable, call it , and use that for our hole. We would also have to restrict the instantiation behaviour of the nominal rewriting machinery, to prevent ()[] rewriting to with the rule ()[] . 7
Usually, the one-step rewrite relation generated by a set of rules is defined as the “compatible closure” of a set of rules, that is, the closure of the rewrite rules by context and substitution (see for instance [16]). The definition of nominal rewriting given above satisfies these properties (taking the freshness context of the rule into account), and is also closed under permutation, as the following theorem shows:
Assume using the rule , then:
(1)
(2) If Γ is consistent and Γ , then Γ .
(3) .
(1) Intuitively this is obvious, since part 2 of Definition 47 allows for any context, and part 3 allows for any -equivalent term on the right.
(2) So [] and there exists some such that ∆ and ∆ and ∆ [] .
Suppose that ∆ is consistent. Then by Lemma 22 we know
Now suppose Γ is consistent and Γ . Then ∆ is consistent by Lemma 16 and the result now follows using part 3 of Corollary 18.
(3) So [] and there exists some such that ∆ and ∆ and ∆ [] .
Write () for the substitution such that if then () , and if then () (). Note that:
Because of conditions on disjointness of variables in the matching problem which solves, for every mentioned in .
By Lemma 41 it is the case that ∆ () ().
Similarly ∆ () ().
Similarly ∆ ().
([]) [] where is with - replaced by -.
Then by Lemma 20, Lemma 5, and Theorem 24 we can deduce that: [] and () is such that ∆ () and ∆ () and [()] . This suffices to prove that ∆ .
Another interesting property, closure under , requires a more restrictive notion of rewrite rule. We come back to this point in Section 6.
5.3 Critical pairs and confluence
Say a nominal rewrite system is confluent when if and , then exists such that and .
Confluence is an important property because it ensures unicity of normal forms, a form of determinism. Local confluence is a weaker property, it is defined as ‘joinability of peaks’. More precisely:
Fix an equivariant rewrite system , and write for the appropriate pair of rewrite judgements. A pair is called a peak. A nominal rewrite system is locally confluent when, if , then exists such that and . We say such a peak is joinable.
Suppose
(1) for 2 are copies of two rules in such that
(2) [] such that has a principal solution (Γ), so that Γ and Γ for 2.
Then call the pair of terms-in-context
a critical pair. If -] and , are copies of the same rule, or if is a variable, then we say the critical pair is trivial.
There are several non-trivial critical pairs in Example 43 involving substitution rules. For instance, there is a critical pair between () and (), and also between () and ().
We will say that a peak is an instance of a critical pair Γ ([]) when there is some such that:
Γ is consistent.
Γ.
([]) ().
Another way of phrasing this is that
in the instantiation ordering from Definition 28, for two (suitably fresh) variables and .
A critical pair is a pair of terms which can appear in a peak of a rewrite of a term-in-context. In standard (first-order) rewrite systems any instance of a critical pair gives rise directly to a peak for any substitution, but here, an instance of a critical pair only gives rise to a peak for substitutions (continuing the notation above) such that Γ is consistent.
Non-trivial critical pairs are important in first order term rewriting systems because it is sufficient to check their joinability to deduce local confluence. This result extends to nominal rewriting under certain conditions, which we will discuss in the next section.
6 Uniform rewriting (or: ‘well-behaved’ nominal rewriting)
Nominal rewriting is elementary (and easy to explain) but sometimes we need more. For example:
It is not necessarily the case that trivial critical pairs are joinable.
It suffices to give counterexamples. Consider the rules (for some term-former )
These have a trivial critical pair (
The fact that the left-hand side of is a variable is not a problem, the problem is that ‘creates’ an atom , which invalidates the freshness context in . Rules that create free atoms do not work uniformly in equivalence classes. For instance, take
and the term [][]. Then [][] and
However, rewrite rules ‘in nature’ (see Example 43) seem to belong to a restricted class of uniform rules, which display good behaviour. We now characterise this better-behaved class of uniform rules and show it has good properties (see Lemma 61).
Say is uniform when if then ## for any such that # is consistent.
In the judgements of the form ∆## below we will always assume that we consider only atoms such that # is consistent, or alternatively, we can think that if the freshness context is inconsistent any predicate is derivable, which corresponds to adding a bottom rule to the logical system.
Remark: All the example rewrite rules ‘from nature’ cited so far are uniform.
The definition of uniformity looks hard to check — do we really have to consider all and before we can declare to be uniform? Fortunately, there is a better way:
(1) is uniform if and only if ## for all .
(2) is uniform if and only if ## for all mentioned in , , and , and for one fresh .
Suppose is uniform. It is easy to verify that (that is, rewrites with to in context ). Therefore by assumption, # #.
Conversely suppose ##. Suppose also that ∆ , so that:
There is a substitution such that ∆ .
There is a position such that [] and ∆ .
[].
We know ## by Lemma 22. Also, since ∆ , using the second part of Corollary 18 also ∆##. Then ∆#[] #[] by the technical lemma which follows.
We then conclude that ∆#[]# for any ∆ [] by Lemma 23.
For the last part, we use equivariance of the definition of uniform rewriting itself [26,25] to see that if ## for some not mentioned in , , or , then ## for all other not mentioned in , , or . 9
The following result is useful in the proof above.
For any and , if Γ##, then Γ# #
We work by induction on the syntax of .
If ] the result is immediate since #[]([]) by (#absa).
If ] then we observe that ## so we may use the inductive hypothesis and (#absb).
The other cases are easy.
Remark: Intuitively uniformity means ‘if is not free in and rewrites to , then is not free in ’, or more concisely: ‘uniform rules do not generate atoms’. Note that the following definition is wrong: is ‘uniform’ when # implies # for all . The reason is that and may contain unknowns, so we must insert assumptions about them, e.g. #
For instance, is trivially ‘uniform’ according to the ‘wrong’ definition, since # is derivable for no .
As observed in the proof of Lemma 56 the validity of a freshness judgement # can be influenced by changes deep inside (e.g. as occur in rewriting). With uniform rewriting, this ceases to be a concern:
If is uniform and and #, then #.
Suppose ∆ #. By Lemma 16, # is consistent. Also by definition of uniformity ∆##. We now use Corollary 18.
Uniform rewriting is well-behaved:
Assume is uniform.
(1) If and then does hold (not necessarily with the same rule).
(2) In a uniform rewrite system, peaks which are instances of trivial critical pairs are joinable.
(1) By induction on the structure of . If the reduction takes place at the root position then the rule applies to too because matching takes into account. If the reduction is in a strict subterm of (then cannot be an atom or a moderated variable), we proceed by induction. The cases of a tuple and function application are trivial, as well as the case in which
(2) Suppose two rules for 2 have a critical pair
Then by Definition 53, [], and (Γ) is such that Γ , and Γ . Recall also that we call the critical pair trivial when = [-] and , are copies of the same rule, or is a variable.
If and are identical, then their rewrites are identical and any peak created by these rules is trivially joinable.
If and differ and is a variable, then the only way we might not be able to apply in [] or its instances, is if some freshness condition on in is unsatisfiable after , which was satisfiable before (see the example above). For uniform rules, Lemma 60 guarantees that this cannot happen.
Therefore instances of a trivial critical pair are joinable.
(Critical pair lemma) If all non-trivial critical pairs of a uniform nominal rewrite system are joinable, then it is locally confluent.
Suppose ∆ is a peak. Then:
(1) There exist , for 2.
(2) may be written as [], and as [], for 2.
(3) There exist solutions to ()) ()) for 2.
Now there are two possibilities:
(1) The distinguished context variable [-] occurs at distinct subtrees of in and . Local confluence holds by a standard diagrammatic argument taken from the first-order case (see for instance [2]). We need Theorems 24 and 61 to account for the use of .
(2) [[-]] or [[-]]. We consider only the first possibility. Suppose that [-], so that (the general case follows using Theorems 24 and 50).
There are now three possibilities:
(1) [-] replaces a variable in . This is an instance of a trivial critical pair. If the rules are uniform, joinability of instances of trivial critical pairs follows from the previous lemma.
(2) [-] and and are copies of the same rule. Then and the peak can be trivially joined.
(3) Otherwise, this is an instance of a non-trivial critical pair (see Definition 55). Non-trivial critical pairs are joinable by assumption, and using Theorem 50 we can join their instances.
Remark: As a first application of this result, we can deduce that the substitution rules in Example 43 are locally confluent: they are uniform (we will show this in next section), and the non-trivial critical pairs can be easily joined.
Note that if we consider also (Beta) then the system is not locally confluent. This does not contradict the previous theorem, because there is a critical pair between (Beta) and () which is not joinable. Of course, the system is locally confluent on ground terms (i.e. terms without variables): the critical pair between (Beta) and () is joinable if we replace the variables by ground terms.
We will say that an NRS is terminating if all the rewrite sequences are finite. Using Newman’s Lemma [34], we obtain the following confluence result.
(1) If an NRS is terminating, uniform, and non-trivial critical pairs are joinable, then it is confluent.
(2) Under the same assumptions, normal forms are unique modulo .
7 Orthogonal systems
We now treat a standard confluence criterion in rewriting theory [16,31,33].
A rule is left-linear when each variable occurring in occurs only once.
A uniform nominal rewrite system with only left-linear rules and no non-trivial critical pairs is orthogonal.
For example, ## () is left-linear but () is not.
The subsystem defining substitution in Example 43 (i.e., the rules) is not orthogonal, because rule generates non-trivial critical pairs. However, if we replace in Example 43 by the rule
we obtain an orthogonal system (less efficient than the original one, since substitutions will be pushed all the way to the leaves of the terms even if the concerned variable does not occur in the term).
An orthogonal uniform nominal rewrite system is confluent.
The proof occupies the rest of this section. Henceforth, we only consider uniform rewriting.
We define a parallel reduction relation as follows:
We have used some new notation: ∆ means ‘ rewrites to using where we have matched the whole of to the left-hand side of ’. For example if then but not () ().
(1) If then .
(2) If then
(3) If then .
(4) If then .
(5) If then .
(6) As a corollary, if and only if .
(1) By induction on the derivation of ∆ . We exploit the syntax-directed nature of the rules; we consider only four cases.
then (observing how this can have been derived), it must be that ∆ . Then ∆ by Theorem 50, and by (atom).
then it must be that ∆ . Then by Theorem 50 and ∆ by (var).
then ∆ [] [] by (abs). We observe that [].
and ∆ [], then ∆ by (abs).
(2) Directly by induction on .
(3) Directly using (refl) and (tup), (abs), (fun), (atom), and (var).
(4) Using the previous two parts.
(5) We work by induction on the derivation of ∆ . If the derivation concludes with:
(a) (refl) then the result is trivial, since is reflexive.
(b) (tuple) then we rewrite sequentially in each element of the tuple.
(c) (tuple) then we rewrite as in the last part, and then once at top level.
(d) (abs), (abs), (fun), or (fun), then we reason much as we did for (tuple) and (tuple).
(e) (atom) then we know ∆ . Similarly for (var).
If the system is uniform and orthogonal then: if and , then there exists some such that and . Hence is confluent.
By induction on the derivation of ∆ .
We consider one case. Suppose the derivation ends in (tup). By the syntax-driven nature of deduction there are three possibilities for the last rule in the derivation of ∆ : (tup), (tup), and (refl):
(1) has a derivation ending in (tup) then the inductive hypothesis for ∆ and ∆ give us such that ∆ and We use (tup) and are done.
(2) has a derivation ending in (tup) using , that () and ∆ () , then exists such that
We now proceed as illustrated and explained below:
We apply the inductive hypothesis to close ∆ using Lemma 66 () and Lemma 72 to deduce of all freshness assumptions deducible of .
Since rules are non-overlapping, the rewrite () () takes place in the substitution , that is, .
Since rules are left-linear still applies: ∆ () and therefore () by (tup) for (for some substitution ). Finally, we use Lemma 61 and orthogonality to close with a rewrite .
(3) then and the diamond can be trivially closed.
The other cases are similar.
We now come back to our theorem:
8 Closed rewriting (or: ‘efficiently computable’ nominal rewriting)
Suppose contains atoms and is in a nominal rewrite system. By equivariance that system contains all infinitely many for all renamings of those atoms. Checking whether matches is polynomial [18], but checking whether matches any , for all possible , is NP-complete [12]. For efficiency we are interested in conditions to make this problem polynomial, we consider this now.
Given a rule we shall write where the primed versions of , , and , have atoms and variables renamed to be fresh — for , and possibly also for other atoms occurring in a term-in-context ∆ . We shall always explicitly say what is freshened for when this is not obvious.
For example, a freshened version of (#) with respect to itself and to the term-in-context # is (#), where and .
We will write ()#() to mean that all atoms occurring in are fresh for each of the variables occurring in .
(1) is closed when
has a solution .
Here () is freshened with respect to .
(2) Given and a term-in-context write
and call this closed rewriting.
Here is freshened with respect to , , and (in part 1 of Lemma 69 below we show it does not matter which particular freshened we choose).
In the next few paragraphs we give some examples and make some comments on this definition.
So for example if # [][]
There exists a such that for all () and:
()#
()#
()#
Note that ) because of conditions we put on rewrite rules that unknowns cannot just ‘appear’ on the right-hand side. We shall use these to simplify expressions denoting freshness contexts without comment.
There are two parts to this definition: closed rules, and closed rewriting. It is possible to do (normal) rewriting with a closed rule, closed rewriting with a (normal) rule, or closed rewriting with a closed rule! The intuition is that a closed rule generates the same rewrites with closed rewriting, as all (infinitely many) renamings of that rule generate with (normal) rewriting. The rest of this section formally develops these intuitions.
Note also that is freshened also with respect to ;
“In closed rewriting, atoms explicitly mentioned in are not allowed to interact with the atoms of the term being rewritten.”
So for example if then but not , because is freshened to first.
Most of this subsection is about making this observation formal, in particular Part 2 of Lemma 69 and Theorem 71. Theorem 74 proves this restriction is computationally useful. Lemma 72 adds “and closed are uniform”, where uniformity is defined and discussed above.
For example, the rules in Example 43 are closed. A canonical example of a closed rule is #. Note that does not rewrite to with (though #). The canonical example of a closed rewrite is . On the other hand, is not a closed rule, neither are , or [], but #
If we think of closed rewriting as being such that the atoms in are bound to that rule, the assumption ()#) adds “and for any subsequent instantiations of their unknowns”. This is why the rewrite occurs even though demands to know that some atom is fresh for .
It is interesting to note that CRSs rules are closed by definition, in the sense that left and right-hand sides of rules cannot contain free variables (the equivalent of unabstracted atoms). But in the case of CRSs this is a structural fact, whereas here closure is defined as a logical condition. ERSs have a similar requirement, but it is expressed in terms of admissible substitutions. Note also that the notion of closed rewriting was generalised to Horn Clauses by Cheney and Urban [42].
The following three technical results about renaming atoms will shortly be useful:
(1) For and , if
for one freshening with respect to , , and , then ()#) for all possible freshenings with respect to , , and .
(2) For any , if and only if .
(3) is closed if and only if is closed.
(1) Nominal Rewriting is equivariant in atoms; if Γ then Γ
for any . Nominal Rewriting is also equivariant in variable names (unknowns), so a similar result holds for them though we have not developed the notation to express it.
If the atoms and variables in are disjoint from ∆, , and (if the variables are disjoint from those in ∆and they must be for those in , by correctness conditions on rewriting)—then we can create a permutation for atoms and another for unknowns, renaming them any fresh way we like.
(2) The particular identity of the atoms in is destroyed moving to . We might as well take fresh for and also for . The result is now easy to see using the previous result.
(3) The predicate ‘ is closed’ has only one argument: . Nominal Rewriting is equivariant on atoms, so we can permute them in ‘ is closed’ to obtain ‘ is closed’, without changing the truth value. The reverse implication also holds since is invertible.
Note that closed rewriting considers some freshened and that the associated notation ∆ suggests the choice does not matter since we do not annotate the arrow with , only with . Part 1 proves this suggestion is correct.
Now we look at some simple examples:
(1) If #, # and # , then if ## then ##.
(2) If # and ) observe that # is a freshening of both and with respect to . With a different term-in-context or we might need a different choice of atoms and unknowns but there are infinitely many to choose from.
In what follows we may say “we assume is fresh for such-and-such extra terms-in-context” or “this is valid for any suitably fresh ”; we may also use closure of to justify closure of , or closed rewriting with to justify closed rewriting with . We are using the lemma above.
is closed if and only if for all , if then . ( is closed if and only if rewriting implies closed rewriting.)
Assume that is closed and that ∆ . For simplicity suppose that the rewrite step is at the root position (the result then follows by induction). So let solve ( ()) ()). Recall exists solving ( ()) (()#
Conversely, assume rewriting with implies closed rewriting with . Note the trivial rewrite , at root position. Therefore by assumption this rewrite is also generated by a freshened in the context augmented with ()#(). From the syntactic similarity of to it must be this rewrite is also generated using the root position, and by definition that means we obtain precisely the conditions for closure.
# is a counterexample to the assertion that closed rewriting implies rewriting for closed . But the result holds for ground terms:
Suppose is ground and is closed. Then if and only if there exists some such that .
Since has no variables (it is ground), a freshness context is irrelevant. Then, the definition of closed rewriting boils down to: if and only if . The left-to-right implication is thus trivial, we take to be a freshening permutation generating in the definitions above, as discussed variable names do not matter.
Conversely suppose for some . is closed by Lemma 69 and by the previous theorem we obtain and so again by Lemma 69.
We can re-state this result as follows:
If is closed then captures the rewrites of its equivariance renaming class on ground terms.
Let be a closed rule. Then is uniform.
We must show that ## and we know by assumption that, for any freshening, ( ()) (()#
#()#
We can always take a freshening such that (), and use the technical lemma which follows to deduce that ## for each (). By assumption
(1) If ## and () then #.
(2) If () then # if and only if for every
Both parts are proved by appealing to the syntax-directed nature of the rules for #.
If a nominal rewrite system is provided as the equivariant closure of a finite set of closed rules, then
(1) Rewriting equals closed rewriting on ground terms and rewriting is polynomial on ground terms.
(2) Closed rewriting is polynomial on all (possibly non-ground) terms.
The very first part is a consequence of the previous theorem.
The algorithm to polynomially derive the closed rewrites of ∆ under for all is to derive just the closed rewrites of . The choice of does not matter because of Lemma 69 part 1.
The restriction to closed rules gives a powerful notion of rewriting: we showed in [21] that we can simulate CRSs using closed nominal rules. However, there are interesting systems (e.g. the -calculus, see also Example 49) with non-closed (but uniform) rules. We come back to this point in the conclusions.
9 Sorts and Extended Contexts
9.1 Sorts
Sorts and types are a way of organising terms into useful classes (‘represents a natural number’ is the classic example). Sorts serve to organise terms into ‘the right’ families for term-formers to act on them. They are particularly useful for talking about the abstract syntax of programming languages. Types serve to organise the semantics of terms. As usual, it is important in computer science to distinguish between the syntax 1 + 2, which is the pair 1 and 2, and its meaning, which is 3.
We now demonstrate how to impose a sorting system on terms. A type system is a fascinating subject (can atoms have type ‘the natural numbers’, and if so what does that mean?); we explore this subject in [20].
A Sorted Nominal Signature Σ is:
(1) A set of sorts of atoms typically written .
(2) A set of base data sorts typically written . These are names for the domains under consideration, for example integer, boolean.
(3) Term sorts typically written , defined by the following grammar:
where is called a product and an abstraction sort.
(4) A set of term-formers as before, to each of which is now associated an arity .
If is an empty product, we say that is 0-ary or a constant and we omit the arrow.
A sorted nominal signature for a fragment of ML has one sort of atoms: , one sort of data: , and term-formers with arities as follows:
This example, derived from [40], illustrates clearly how sorts indicate binding scope.
Partition unknowns into countably infinite sets of variables of sort for each . Similarly partition atoms into countably infinite sets of atoms of sort . Even in the sorted context we may drop the sorting subscripts where they are obvious or we do not care, as a notational convenience; and are still different term variables, for which we have overloaded the symbol , and similarly for .
A swapping is a pair () of atoms of the same sort. Permutations are lists of swappings as before.
Then sorts for terms may be deduced by the following syntax-directed deduction rules:
It is not hard to prove the following well-behavedness properties:
(1) If : and is a permutation then : .
(2) If : and : then [] : .
The first part is by induction on the structure of . The base case is the observation that if : then : , which is straight from the sorting rules.
The second part is by induction on the structure of . The base case is . Then [] . Since : by the first part, : , and we are done.
9.2 Extending freshness contexts
We will now show that, thanks to the use of contexts, the framework of nominal rewriting can be easily adapted to express strategies of reduction. As an example, we will show how to define the system of closed reduction for the -calculus [23]. -terms are linear -terms with explicit constructs for substitutions, copying and erasing. Reduction on is defined in [23] using a set of conditional rule schemes, shown in Table 1, where denote variables, and denote terms.
We can formally define using a nominal rewriting system, where we add two new kinds of constraints: (read is closed), with the intended meaning “# for every atom ”, and (read is unabstracted in ), the negation of #.
Table 1 -reduction
We extend the deduction and simplification rules from section 3 respectively with:
Here is any set of atoms strictly containing the atoms in and ∆, and (). In effect we need ( and one fresh atom; if ∆ # for ( ∆) a renaming argument gives ∆ # for all other ( ∆). This is reflected in the simplification rule, which is more algorithmic and chooses one fresh atom.
is intuitively #. The rule for closure is slightly different from the usual predicate logic rule for because atoms behave here as constants and not variables. With that in mind the definitions are quite natural.
We can extend the deductions with rules including
and similarly extend the simplification rules. We can extend contexts with these new constraints and use them in s of rewrite rules to control triggering.
A closed reduction strategy can be specified, this time as a finite nominal rewrite system (we only show rules , and ):
A theory of nominal rewriting with (general) constraints will be the subject of future work.
10 Conclusions
The technical foundations of this work are derived from work on nominal logic [36] and nominal unification [40]. We use a nominal matching algorithm, which is easy to derive from the unification algorithm and which inherits its good properties (such as most general unifiers), in our definition of rewriting.
Our theory stays close to the first-order case, while still allowing binding. We achieve this by working with concrete syntax, but up to a notion of equality which is not just structural identity. It is not -equivalence either: is actually logical, in the sense that ∆ is something that we deduce using assumptions in ∆. We pay the price that terms, rewrites, and equalities, happen in a freshness context ∆. In practice ∆is fixed and does not seem to behave perniciously.
Nominal rewriting is more expressive than first-order rewriting and standard higher-order formats. Capture-avoiding substitution is not a primitive notion, but it is easy to define with nominal rules (we can spare the effort of ‘implementing’ -conversion using de Bruijn indices and all the machinery associated to typical explicit substitution systems). It is also possible to define a nominal rewriting formalism with a primitive notion of substitution of terms for atoms (capture-avoiding).
Many directions for future work are still open. For instance:
We have given a sufficient condition for confluence (orthogonality, for uniform systems); weaker conditions (for example, weak orthogonality) should also be considered.
We have given a critical pair lemma, but we have not studied Knuth-Bendix style completion procedures.
There are sort systems for nominal terms, but no type system yet. We are working on a type system and semantics which provide an interpretation
for terms with variables (usual semantics for -calculus and higher-order rewriting only consider ground terms). If we use term rewriting as a model of computation, termination (or strong normalisation) is an important property. It would be possible to devise sufficient conditions for termination of nominal rewriting using type systems.
Acknowledgements: We thank James Cheney, Ian Mackie, Andy Pitts, Christian Urban, and Nobuko Yoshida for useful comments.
References
[1] Martín Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques Lévy. Explicit substitutions. Journal of Functional Programming, 1(4):375–416, October 1991.
[2] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.
[3] F. Barbanera, M. Fernández, and H. Geuvers. Modularity of strong normalization in the algebraic--cube. Journal of Functional Programming, 6:613–660, 1997.
[4] Franco Barbanera and Maribel Fernández. Intersection type assignment systems with higher-order algebraic rewriting. Theoretical Computer Science, 170:173– 207, 1996.
[5] H. P. Barendregt. Pairing without conventional constraints. Zeitschrift für mathematischen Logik und Grundlagen der Mathematik, 20:289–306, 1974.
[6] H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.), volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam, 1984.
[7] J. Bergstra and J. W. Klop. Conditional rewrite rules: Confluence and terminatio n. Journal of Computer and System Sciences, 32(3):323–362, 1986.
[8] R. Bloo and K. Rose. Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection, 1995.
[9] Eduardo Bonelli, Delia Kesner, and Alejandro Ríos. From higher-order to first-order rewriting. In Proceedings of the 12th Int. Conf. Rewriting Techniques and Applications, volume 2051 of Lecture Notes in Computer Science. Springer, 2001.
[10] Val Breazu-Tannen and Jean Gallier. Polymorphic rewriting conserves algebraic strong normalization. Theoretical Computer Science, 83(1), 1991.
[11] Val Breazu-Tannen and Jean Gallier. Polymorphic rewriting conserves algebraic confluence. Information and Computation, 82:3–28, 1992.
[12] James Cheney. The complexity of equivariant unification, 2004. Submitted.
[13] H. Cirstea and C. Kirchner. The Rewriting Calculus - Part I. Logic Journal of the Interest Group in Pure and Applied Logics, 9:363–399, May 2001. Also available as Technical Report A01-R-203, LORIA, Nancy (France).
[14] H. Cirstea and C. Kirchner. The Rewriting Calculus - Part II. Logic Journal of the Interest Group in Pure and Applied Logics, 9:401–434, May 2001. Also available as Technical Report A01-R-204, LORIA, Nancy (France).
[15] R. David and B. Guillaume. A -calculus with explicit weakening and explicit substitution. Mathematical Structure in Computer Science, 11(1):169–206, 2001.
[16] N. Dershowitz and J.-P. Jouannaud. Rewrite Systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science: Formal Methods and Semantics, volume B. North-Holland, 1989.
[17] Daniel J. Dougherty. Adding algebraic rewriting to the untyped lambda calculus. In Proc. 4th Rewriting Techniques and Applications, LNCS 488, Como, Italy, 1991.
[18] M. Fernández and C. Calves. Implementing nominal unification. In Proceedings of TERMGRAPH’06, 3rd International Workshop on Term Graph Rewriting, ETAPS 2006, Vienna, Electronic Notes in Computer Science. Elsevier, 2006.
[19] M. Fernández and M.J. Gabbay. Nominal rewriting with name generation: Abstraction vs. locality. In Proceedings of the 7th ACM-SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP’05), Lisbon, Portugal. ACM Press, 2005.
[20] M. Fernández and M.J. Gabbay. Types for nominal rewriting, 2006. Submitted.
[21] M. Fernández, M.J. Gabbay, and I. Mackie. Nominal rewriting systems. In Proceedings of the 6th ACM-SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP’04), Verona, Italy, 2004.
[22] M. Fernández and J.-P. Jouannaud. Modular termination of term rewriting systems revisited. In Recent Trends in Data Type Specification. Proc. 10th. Workshop on Specification of Abstract Data Types (ADT’94), number 906 in LNCS, Santa Margherita, Italy, 1995.
[23] M. Fernández, I. Mackie, and F-R. Sinot. Closed reduction: Explicit substitutions without alpha-conversion. Mathematical Structures in Computer Science, 15(2), 2005.
[24] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214– 224. IEEE Computer Society Press, Washington, 1999.
[25] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13:341–363, 2001.
[26] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
[27] Makoto Hamana. Term rewriting with variable binding: An initial algebra approach. In Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP2003). ACM Press, 2003.
[28] J.-P. Jouannaud and M. Okada. Executable higher-order algebraic specification languages. In Proceedings, Sixth Annual IEEE Symposium on Logic in Computer Science, pages 350–361. IEEE Computer Society Press, 1991.
[29] Z. Khasidashvili and V. van Oostrom. Context sensitive conditional reduction systems. Proc. SEGRAGRA’95, Electronic Notes in Theoretical Computer Science, 2, 1995.
[30] Zurab Khasidashvili. Expression reduction systems. In Proceedings of I.Vekua Institute of Applied Mathematics, volume 36, pages 200–220, Tbisili, 1990.
[31] J.-W. Klop, V. van Oostrom, and F. van Raamsdonk. Combinatory reduction systems, introduction and survey. Theoretical Computer Science, 121:279–308, 1993.
[32] Pierre Lescanne. From to a journey through calculi of explicit substitutions. In Proceedings of the 21st ACM Symposium on Principles of Programming Languages (POPL’94). ACM Press, 1994.
[33] Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
[34] M.H.A. Newman. On theories with a combinatorial definition of equivalence. Annals of Mathematics, 43(2):223–243, 1942.
[35] Bruno Pagano. Des calculs de substitution explicite et de leur application à la compilation des langages fonctionnels. PhD thesis, Université de Paris 6, 1998.
[36] A. M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186:1g5–193, 2003. A preliminary version appeared in the Proceedings of the 4th International Symposium on Theoretical Aspects of Computer Software (TACS 2001), LNCS 2215, Springer-Verlag, 2001, pp 219–242.).
[37] Femke van Raamsdonk. Confluence and Normalisation for Higher-Order Rewriting. PhD thesis, Free University of Amsterdam, 1996.
[38] M. R. Shinwell, A. M. Pitts, and M. J. Gabbay. FreshML: Programming with binders made simple. In Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden, pages 263–274. ACM Press, August 2003.
[39] Masako Takahashi. -calculi with conditional rules. In J.F. Groote M. Bezem, editor, Typed Lambda Calculi and Applications, International Conference TLCA’93, volume 664 of Lecture Notes in Computer Science. Springer-Verlag, 1993.
[40] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. In M. Baaz, editor, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings, volume 2803 of Lecture Notes in Computer Science, pages 513–527. Springer-Verlag, Berlin, 2003.
[41] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. Theoretical Computer Science, 323:473 – 497, 2004.
[42] Christian Urban and James Cheney. Avoiding equivariance in alpha-prolog. In Proceedings of Typed Lambda Calculus and Applications, TLCA 2005, pages 401–416, 2005.
Notes
This work has been partially funded by EPSRC grant EP/C517148/1 “Rewriting Frameworks”.↩
1 Substitute “damn” every time you’re inclined to write “very”; your editor will delete it and the writing will be just as it should be. – Mark Twain ↩
2 An argument could be made that they are the correct notion of nominal rewrite rule, though we have a weaker well-behavedness condition we call uniformity, which is also relevant.↩
3 The intuition is that in Definition 6 (#X) makes it clear that # if and only if #, and Definition 3 makes it clear that permutations commute through all term-formers. Also note that renamings (possibly non-injective functions from atoms to themselves, e.g. ‘replace by ’) do not satisfy these useful properties; it is essential to use swappings.↩
4 In [41] the result which ‘did’ this case (Theorem 2.11) was proved by simultaneous induction with transitivity of . We do not need this, because we use Lemma 19. Lemmas 2.7 and 2.8 in [41] have more-or-less the same content, but the mention of equality in 2.8 makes it a little harder to use and forces the simultaneous induction. ↩
5 This is in (), since if then so , and this is not the case.↩
6 A ‘position’ is, literally, the standard notion of a point in the abstract syntax tree of a term, as defined for example in [21]. It is more convenient for us to identify this with the corresponding ‘initial segment’ of a term.↩
7 So we have yet another kind of hole, similar to the of nominal rewriting in that it represents an unknown term, but this is one which we expressly do not want to match with any particular term. Another day, another paper. This idea can be emulated quite effectively in nominal rewriting as we have done, with a unary term-former. ↩
8 . . . assuming - -, which should be the case since we assume - ‘is always fresh enough’ and rename it otherwise.↩
9 Or, if the reader does not care for this degree of rigour, we can just say “since was fresh but otherwise arbitrary, clearly ## holds for any other ”. ↩