Nominal Rewriting with Name Generation: Abstraction vs. Locality
Maribel Fernández and Murdoch J. Gabbay
Dept. of Computer Science
King’s College London Strand, London WC2R 2LS,UK
maribel,jamie@dcs.kcl.ac.uk
ABSTRACT
Nominal rewriting extends first-order rewriting with Gabbay-Pitts abstractors: bound entities are explicitly named (rather than being nameless, as for de Bruijn indices) yet rewriting respects -conversion and can be directly implemented, thanks to the use of freshness contexts. In this paper we study two extensions to nominal rewriting. First we introduce a quantifier for modelling name generation. This allows us to model higher-order functions involving local state, and has also applications in concurrency theory. The second extension introduces new constraints in freshness contexts. This allows us to express strategies of reduction and has applications in programming language design and implementation. Finally, we study confluence properties of nominal rewriting and its extensions.
Categories and Subject Descriptors
F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic—lambda calculus and related systems
General Terms
Theory
Keywords
Binders, -conversion, first and higher-order rewriting, name generation, locality, confluence.
1. INTRODUCTION
Term rewriting systems (TRS) specify and reason about computation by working with trees labelled by variable and function symbols. Standard TRSs are first-order, but effort has been devoted to systems manipulating higher-order functions, where variables can be free or bound. Examples of higher-order rewriting formalisms combining first-order rewriting with a notion of bound variable are: Combinatory
Reduction Systems (CRS) [24], Higher-order Rewrite Systems (HRS) [27], Expression Reduction Systems (ERS) [22], and the rewriting calculus [10, 11]. The -calculus can be seen as a higher-order rewrite system with one binder called -abstraction.
Binders lead to -conversion. First-order substitutions (i.e. replacements) may capture variables, so substitution in a higher-order system has to be carefully defined using renamings (-conversion). In the higher-order formalisms mentioned above substitution is a meta-operation which relies on an implicit notion of -conversion: terms are defined modulo renamings of bound variables. Several notions of explicit substitutions and explicit -conversion have been defined for the -calculus (e.g. [1, 26, 12]) and more generally for higher-order rewrite systems (e.g. [30, 6]) 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.
Nominal rewriting is a new formalism for rewriting with bound variables, introduced in [14]. In nominal rewriting systems (NRSs) variables are named (whence ‘nominal’), substitution is first-order, and we deal with -conversion by using an auxiliary freshness relation # between variables and terms (we say “ is fresh for the term ”). This freshness relation was introduced in [31, 18], and used to define a metalanguage for functional programming in [33], and to study unification problems in [36].
Nominal terms are first-order terms with built-in -conversion. Our metalanguage does not include metasubstitutions and -reductions (in contrast to notions of higher-order rewriting): in this sense, nominal rewriting systems are a middle ground between first-order and higher-order rewriting. The usual notion of higher-order substitution can be easily specified since -conversion is in the meta-language.
Following [31, 18], we call the names that can be bound atoms and reserve the word variable for the identifiers that cannot be bound (known as variables and metavariables respectively in CRSs). In nominal terms the dependencies between variables and names are implicit, as in informal presentations of higher-order reductions. For example, -calculus - and -rules are written
Rewriting on nominal terms uses nominal matching [14, 36, 37], which does not need metasubstitutions and -reduction but it does take into account freshness contexts. Selecting a nominal rewrite rule that matches a given term is an NP-complete problem in general [9]; however, by restricting to closed rules we can avoid the exponential cost: nominal matching is polynomial in this case [14]. Closed nominal rewriting turns out to be sufficiently close to first-order rewriting to share many of its properties, including a critical pair lemma [14], and a confluence theorem for orthogonal (i.e. left-linear and non-overlapping) systems which we prove in this paper. It is also expressive (see [14] for a translation of Klop’s Combinatory Reduction Systems) but has some limitations: rewrite rules have no mechanism for locally generating a fresh atom. This occurs in nature. For example in a rewrite system for the -calculus [28] we might wish a reaction rule which we might write as [], where indicates that must be fresh for all variables in the context in which the rewrite is introduced. Similar phenomena arise in programming languages, such as gensym in LISP, unit ref in ML, and many other forms of dynamic allocation both in the foundational and applied literatures.
In this paper we study two extensions to nominal rewriting:
(1) We consider the name generation construct and make corresponding extensions to the freshness contexts to describe the scope of the names thus generated. Although can be seen as a quantifier modelling locality of names, it is not a binder: we will show that abstracted names and local names have different behaviour.
(2) We extend just the contexts with new predicates specifying constraints for atoms in terms, for instance closedness.
In this way strategies of reduction such as closed reduction in the -calculus [16] may be concisely specified. This extension has applications in programming language design and implementation (see for instance [16]).
We study confluence properties of extended nominal rewriting: we give a critical pair lemma for extended NRSs and we prove that orthogonal systems are confluent.
In summary the main contributions of this paper are:
1. We formalise a notion of name generation and locality on nominal terms, with an associated notion of rewriting, with applications to distributed and higher-order programming.
2. We define two new predicates: a scope relation and a closedness relation, which can be used as constraints together with the freshness relation in contexts to specify strategies of reduction in rewrite rules.
3. A Critical Pair Lemma which ensures that extended nominal rewriting rules which do not introduce critical pairs are locally confluent.
4. A Confluence Theorem for orthogonal systems.
Related Work.
NRSs are related to algebraic -calculi [7, 8, 21, 3] where the -reduction rule of the -calculus is combined with a set of term rewriting rules using standard first-order matching. Nominal rules are more general than these, since abstractions can be used in patterns, in the same way as in higher-order rewriting systems (e.g. CRSs [24], HRSs [27], ERSs [22], HORSs [34], and the -calculus [10, 11]).
In contrast with higher-order rewriting systems, nominal rewriting does not need higher-order matching and higher-order substitutions. Instead, it relies on an extension of first-order matching that takes care of -conversion without introducing -reductions.
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. [30, 6]), which implement in a first-order setting the substitution operation together with -conversions using de Bruijn indices. Nominal rewriting is also related to Hamana’s Binding Term Rewriting Systems (BTRS) [19]. The main difference 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).
The name generation operator of extended nominal rewriting systems is related to the operator of Pitts and Stark’s -calculus [32] and the -calculus restriction operator [28]. Apart from obvious differences between a simply typed -calculus, a process calculus, and a rewriting formalism, and differ in their treatment of generated names: is a binder, whereas is a scope construct.
Overview of the paper.
Section 2 presents nominal signatures and extended nominal terms. Section 3 defines -equivalence as a logical notion first, then gives an algorithm to test -equality. Nominal matching and unification algorithms are given in Section 4. Section 5 defines rewriting on extended nominal terms, and Section 6 studies confluence. Section 7 introduces closedness constraints and reduction strategies. We conclude the paper in Section 8.
2. EXTENDED NOMINAL TERMS
2.1 Signatures and terms
A Nominal Signature Σ is a set of function symbols typically written . We do not assume that functions have sorts or arities in this paper (the original presentation [14] does but we shall not need them here).
So for example, a nominal signature for a fragment of ML has function symbols:
var app lam let letrec
Fix some signature Σ. Fix a countably infinite set of term variables . These will represent meta-level unknowns. Fix a distinct countably infinite set of atoms . These will represent object-level variable symbols. Consistent with later notation for terms, we write to denote identity of atoms. We assume that Σ, and are pairwise disjoint.
A swapping is a pair of atoms, which we write (). Permutations are generated by the grammar
We call Id the identity permutation. We call a pair of a permutation and a variable a moderated variable and write it . Formally, swappings and moderated variables are just pairs, and permutations are just lists of swappings.
Extended Nominal Terms, also called tagged terms or just terms for short, are generated by the grammar
() []()
where we write for a finite set of atoms which may be empty. We may write blah more succintly as blah, and similarly we may write Id as .
Terms are called respectively atoms, moderated variables (or just variables for short), tuples, abstractions and function applications.
In the clause for tuples, is called the length of the tuple and may equal 0 in which case we have the empty tuple (). We omit the brackets when is 1 if there is no ambiguity. In the clause for function applications, may be applied to the empty tuple in which case we may write () as just .
Note that an extended nominal term is a tree with nodes annotated by function symbols or (moderated) variables, so, syntax in the accepted sense — later we call it the term’s skeleton — but also annotated at every node with a finite sets of atoms. We shall call these sets tags. A term such that every tag is empty is in essence ordinary syntax and is isomorphic to a(n unextended) nominal term [14].
We denote () the set of variables that occur in the term . Ground terms are terms without variables, that is (. A ground term may still contain atoms, for example or () are ground terms and is not.
An abstraction [] is intended to represent with bound, and 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, [] []. In nominal techniques, -equivalence is a logical notion constructed on top of using a notion of context which we shall define soon.
A tagged term is intended to represent with a local name it is calling . We call occurrences of scoped or local, and unscoped occurrences unscoped or global. As with abstraction, we do not work up to -conversion of tags.
Abstraction is inherited from previous work [36, 14], tags are new to this paper. We give some examples:
is a scoped copy of . In future, we drop the set curly brackets and write .
is a local name called . Note that .
is with a local name (which is not used, the reader might like to consider it ‘garbage’). is not syntactically identical to , , or .
generates and and discards . Because the tags are sets, . However, .
() generates and makes the pair ().
() generates two local names which are both (by coincidence) ‘’.
() is a tuple which generates locally and places it in the first component. The second component is also , but this is a different copy in its own local scope. () ().
Using the ML signature mentioned above, we can write (lam[](app(var() app(var())))) which we will
abbreviate [](). This term can be used to represent a function which has an argument and generates a local name (i.e. ref in ML).
2.2 Substitution and swapping
Substitution of an unknown for a term in a term is a function that satisfies:
()[] (())[] (([]))
A substitution is generated by the grammar
has an action on terms given elementwise from the definition above and satisfying Id . We write substitutions postfix as just shown, and write for composition of substitutions: () ().
The intuition of a moderated variable is that we would like to rename the atoms in , but we do not yet know what is. If a substitution [] instantiates , as in the last clause of the definition above, we apply to . A permutation has an action on terms, denoted defined in the natural way from the component swappings. The action of swappings on terms is defined inductively by:
Here we have applied swappings to atoms and sets of atoms ()() and ()(). The action on sets is pointwise, and the action on atoms satisfies:
()() ()() and ()() ()
For example, ()[][]().
2.3 Positions
A skeletal position is generated by the grammar
where is a number. A position is a pair of a skeletal position and a finite (possibly empty) set of atoms . We write for the subterm of at position ().
Skeletal positions are usually called positions, we assume the reader is familiar with [13, 23]; see also [2]. ‘Skeletal’ refers to the tag-less ‘skeleton’ of a term: so is the root position; 1 indicates going under a function symbol or an abstraction []; refers to th position in (); permutations are ignored. Having arrived at a certain place in the skeleton, ‘’ means remove the atoms from the tag at that (skeletal) position.
We omit a formal definition but give examples: If ( ) then , ( ), ( ), and is undefined. , , , and is not defined. If [] then and .
We write [] for the result of replacing the subterm of at () by , merging the tags. We may omit when it is empty, writing [ instead of []. For example if is as above, then [, [], [] , [].
3. ALPHA-EQUIVALENCE
Syntactic equality is a structural (rather than logical) fact. -equivalence is a logical notion, which we define below.
3.1 A logical presentation
Constraints are generated by the grammar
We call # a freshness predicate, @ a scoping (or locality) predicate, and an equality predicate. They will be defined formally below. The intended interpretation of
# is “if occurs in then each occurrence is either in a tag, or abstracted”. For example, #, #, not #, however #[]. We sometimes write # instead of ##.
@ is “if an occurrence of is unabstracted in then it is in a tag”. For example, @ and @, @[], but not @. We abbreviate @@ as @.
is “ and are -equivalent” (see below).
In the following rules, and consistent with notation used above, we write #Id as #, @Id as @, Id as , and Id as .
# is specified by deduction rules as follows:
This definition is like the one in [14] except that terms have tags added; to calculate # we simply throw them out.
@ is specified by deduction rules as follows:
All rules except for (#), (#) and () are echoed in algorithmic form in the next subsection.
Finally we define inductively as follows, where in all the rules except the last and are terms with an empty tag at the root (i.e. , ).
We have used the difference set of two permutations:
For example, (() Id, so (using the rules above) we can deduce () from assumptions # and # and we also have as expected [] []. Other examples of -equivalence are: , and , but note that .
Say constraints of the form #, #, @, and @ with , are reduced. We write ∆ Γ for sets of reduced constraints, we may call them contexts. If there are no constraints of the form #, and @ with in ∆we say it is consistent.
Call a set of constraints a problem. We write ∆ when proofs of exist for all , using elements of ∆as assumptions, and we say that ∆ entails . Since the rules above decompose syntax, an algorithm to check entailment can be easily built using this logical presentation. We give an operational definition of the predicates #, @ and in the next subsection.
We now state some properties of #, @ and which are needed later. In particular, we show that is a congruence.
If # then @.
We examine the derivation rules for @ and # and see that a proof of # can be transformed rule-for-rule to a proof of @. We may use (#) to deduce @ from some #.
Suppose is a reduced context.
1. # if and only if ()#.
2. @ if and only if ()@.
3. # if and only if #.
4. If # and then #.
5. If @ and then @.
The first, second, and third parts are by routine inductions on derivations.
The fourth part is by mostly routine induction on derivations. We use the first part for the case of [][], and the third part for the case of .
The fifth part follows from the second part in a similar way. We consider two example cases:
Suppose @ and are derivable where at least one of and is nonempty. Then @ for every , and @ for every , and . There are now three cases:
If then @ and we are done.
If and then @ and so @ and we are done.
If and then @ and and we use the inductive hypothesis.
Suppose @[] and [][]. Then () and #.
If we are done.
If we use the previous lemma to derive @ using the derivation of #, then extend to a derivation of @[].
If we use the inductive hypothesis to deduce @(), the second part of this lemma to deduce @, and finally extend to a derivation of @[] as required.
For fixed , is an equivalence relation and implies .
Reflexivity is easy. For transitivity, we use induction on derivations and the previous lemma for the case of [][][]. The final part is also by induction; only the case of [] [] is in any way non-trivial, we use the previous lemma.
if and only if .
if and only if .
()# then .
@ and @ then .
For fixed , is a congruence. Thus, if then [[].
The first four parts are by routine inductions using the previous results. The last part is by induction on the syntax of and uses the previous cases.
3.2 An algorithmic presentation
We specify simplification rules on problems by:
Here, on the left commas indicate disjoint set union, on the right they indicate possibly non-disjoint set union.
These rules define a reduction relation on problems: We write if is obtained from by applying a simplification rule. We denote by its transitive and reflexive closure.
For example, the last rule reduces the problem to @. Other examples are:
These reduction rules are derived from the deduction rules in the last subsection, but there are differences; we omit a rule @#, which would correspond to (#), and also rules corresponding to (#) and (@). If we didn’t, the important lemmas below would not hold.
The simplification rules above are confluent and strongly normalising (reduction order does not matter).
By Newman’s Lemma [29] we need only show termination, because there are no critical pairs. The rules form a hierarchical system in the sense of [15], from which it follows that if the first two groups of rules are terminating and non-duplicating (they are) and do not use in the right-hand side any symbol defined in the third group (i.e. equality ; they do not), then if the rules defining 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.
Write for the unique normal form of , and for , i.e. the result of simplifying it as much as possible. We will say that an equality is clashing when the terms and have different term constructors at the root (e.g. [] (), , , etc.) or they are two different atoms (e.g. ) or two different variables (e.g. ), or applications with different function symbols (e.g. ).
(Normal Forms). # consists of reduced freshness constraints and @ consists of reduced scoping constraints. may contain any mixture of reduced freshness constraints, reduced scoping constraints, and clashing equalities.
Any non-reduced freshness or scoping constraint can be simplified using the rules in the first two groups. Similarly, a non-clashing equation can be simplified with a rule in the third group.
Therefore can always be partitioned into ∆ where ∆is a (possibly empty) context and a (possibly empty) set of clashing equalities .
Assume . Then
Γ if and only if Γ
By inspection of the rules.
Let where is a context and is a set of clashing equalities.
1. If is consistent then:
2. for all if and only if is inconsistent.
The first part is proved by induction on the length of the derivation : using Lemma 3.7 if and only if ∆ . The result follows from the fact that if is clashing then there is no consistent ∆such that .
For the second part, we use the rules (#) and (@).
Let Γ be a consistent context.
Γ if and only if and Γ
Consequence of Theorem 3.8 and Lemma 3.7.
4. UNIFICATION
A unification problem is a problem as previously defined but replacing the equality constraint by the unification constraint . A solution to a unification problem is a pair (Γ) of a consistent context and a substitution such that Γ where is obtained from by changing unification predicates into equality predicates, and is the problem obtained by applying the substitution to the terms in . If there is no consistent context satisfying this property, we say that is unsolvable. We write () for the set of unification solutions to .
Write ∆ when ∆ for all . Write Rt() for the tag associated to the root of (so Rt(().
Write (Γ) () when there exists a substitution such that Γ, and Rt() Rt() for every . We see that this defines a partial order on solutions (sometimes called instantiation ordering). Say a solution to a problem is principal when it is smaller than or equal to all other solutions to that problem. A solution (Γ) is idempotent when Γ .
We will show below that every solvable unification problem has a principal idempotent solution, and give an algorithm to find it.
The simplification rules given in the previous section can be adapted to solve unification problems: we need to add instantiating rules, labelled with substitutions.
[] ()
[] ()
The conditions in the rules are usually called occurs check.
Note that we do not intend to solve apartness or scope constraints. Indeed, to solve apartness and scope constraints we need instantiating rules for these predicates too. Instead, we will solve the equalities in a problem, and require that the solution satisfy the apartness and scope constraints in the problem. This is what we need in rewriting.
We will use the set of simplification rules given in the previous section (where we replace by ), together with the instantiation rules, as a unification algorithm.
The unification rules are confluent and strongly normalising.
Standard: at each step either the number of unsolved variables in the problem decreases, or a non-reduced constraint simplifies towards reduced constraints.
To solve a problem , we will apply the rules until we obtain an irreducible problem. We write ) if is the (unique) normal form of using the unification rules, and is obtained by concatenating the labels in some reduction sequence from to . We can characterise the normal form of under the unification rules:
(Unification Normal Forms). # consists of reduced freshness constraints and @ consists of reduced scoping constraints. may contain any mixture of reduced freshness constraints, reduced scoping constraints, and clashing equalities such that if one side is a variable the other side contains this variable.
Similar to Lemma 3.6: Any non-reduced freshness or scoping constraint or non-clashing equality can be simplified as previously. Clashing equalities of the form or where () can be reduced using an instantiation rule.
Therefore we can decompose as a triple (∆) where ∆is a context, a set of equations, and a substitution.
We will show that the unification algorithm correctly checks whether a problem is solvable or not, and moreover it computes a principal, idempotent solution, if one exists. In the proof we will use the following lemmas:
1. Let be a non-empty set of unification constraints in normal form. Then has no solution.
2. Let be an inconsistent context. Then has no solution.
By Lemma 4.2, the equalities in are clashing or fail the occur check. Since no consistent context can entail an instance of such an equality, is not solvable.
The second part is directly by definition of solution, and the fact that from a consistent context we cannot derive an inconsistent one.
()().
acts top-down and accumulates on moderated variables. acts bottom up on the variable symbols in the moderated variables. The two operations commute. A formal proof is easy by induction on syntax.
If () then [] .
Suppose ∆ () and write for [] . We simplify up to in the context
(We make heavy use of the previous lemma to rearrange the brackets.) The second part is similar.
(Preservation of solutions). Assume
1. If (Γ) () then (Γ) () and Γ .
2. If (Γ) () then (Γ) ().
The first part follows from the previous lemma. For the second part, suppose Γ and suppose [] so that ([]. It is easy to verify that Γ , so Γ ().
Let be a unification problem, and ).
() if and only if is a consistent context and .
If then and for some .
The first part is a consequence of the confluence .
The second part can be proved by induction on the derivation . A step [] is replaced by [] [].
(Principality). Let be a unification problem, and ) such that is a consistent context.
1. ) (), and
2. if (Γ) () then ) (Γ).
For the first part, note that (∆) is a consistent context. Hence by Lemma 4.6 (and induction) ) ().
Γ , by Lemma 4.6 part 1 (and induction). Note in particular that Γ , that is, is idempotent.
Γ by definition of solution, and Γ by Corollary 3.9. Also, Γ () (), and by Lemma 4.8 part 2, Therefore, by Lemma 4.8 part 1, (), and we get Γ . Hence Γ by Corollary 3.9.
Finally, Rt() Rt() for every since is created by the instantiation rules with empty tags.
Therefore (∆) is a principal and idempotent solution.
5. REWRITING
5.1 Matching problems
Given terms-in-context and ∆ such that () , a matching problem between them is the pair (). We write it () ). The solution to this matching problem, if it exists, is a pair ) which is a principal solution in the sense of the last section to the unification problem , such that
for ) and
is derivable.
is derivable.
The first condition ensures that our solution is a matching. The second condition controls when matches with . The third condition controls when the conditions are satisfied. When this third condition is satisfied we say the matching is triggered. (Soon, will be the left-hand of a rewrite rule , and then we say the rule is triggered.)
For example: () () has no solution; ( ) () has a solution Id; and () () has solution ]. All of the following problems have solution (@ []):
See [14] for more examples.
5.2 Rewrite rules
A(n extended) rewrite rule is a tuple of a consistent context , and extended terms and such that () ().
Suppose is a rewrite rule, and are terms, and ∆is a context. We say rewrites with to in the context ∆, and we write ∆ when:
1. () (we can assume this with no loss of generality).
2. There exists a position () in and a matching solution (∆) to () ).
[].
This is essentially the same definition as for (unextended) nominal rewriting [14], modulo slight changes to account for the tags.
Write for that rule obtained by swapping and in throughout. For example, if @ [] () then @ [](). Say a set of rewrite rules is equivariant when it is closed under for all atoms and .
A rewrite system is an equivariant set of rewrite rules. A set of rewrites gives rise naturally to a rewrite system by closing under equivariance. We shall elide this step, saying ‘ has the rewrite blah’ to mean ‘the rewrite system obtained by closing under equivariance has the rewrite blah’. This usage is established [14].
We now consider some simple examples, and give applications of extended nominal rewriting in the following subsection.
The rewrite system has the rewrites for any . This is because of equivariance: if then so is for any . It also has the rewrite , using position ().
The rewrite system has the rewrites and also .
The rewrite system [] has the rewrite []. It also has the rewrite # [] (). This is because # [] [](). The following is an important correctness result:
If then [] [].
By unpacking the definition of rewriting.
5.3 Applications
Modelling name generation in the -calculus.
A reaction system for an asynchronous -calculus is given by the signature
in out par rep
and the following rewrite rules, where we abbreviate par() as (), in( []) as [], out() as and rep() as ! to get the standard -calculus notation. We assume par is associative and commutative, and work modulo a structural congruence as usual; the details are omitted since they are not relevant to this paper.
Here is an explicit substitution with reactions including () and ([]) []().
Call the last rule the scope extrusion rule, the first rule the reaction rule, and the second rule the name-generation rule. Let us consider the name-generation and scope extrusion rules and demonstrate in the context of extended nominal rewriting why they have these names.
Note that is abstracted in []. Nominal rewriting, including the extension in this paper, works on terms up to provable -equivalence; thus if ∆ [] is a valid rewrite and ∆ # is deducible, then ∆ []() () is a valid rewrite. Thus, the name-generation rule ‘generates a fresh ’. defines the scope of and the scope extrusion rule allows us to extend it.
The fly in our ointment is that the scope extrusion rules do not allow renaming a scoped name (, for example) to a ‘fresher’ such that, say, # is provable where # was not. This is known as name-clash and it is ‘unfair’ since we could always have chosen originally.
We can add a freshening rewrite rule
to allow post-factum renaming. A weaker alternative is to strengthen the scope extrusion rules:
(‘Weaker’, because we get rewrites of the transitive closure of with the original scope extrusion rules, but not quite all of them.)
Name generation in Pitts and Starks’s -calculus.
A reaction system for Pitts and Starks’s -calculus [32] is
Again, is an explicit substitution. Reaction rules include # ([])[]() and # ([])[]().
As in the implementation of the -calculus above we have faithfully modelled abstraction in the syntax by abstraction in the rewrite system; for example is abstracted in [] and []. We consider alternatives in the Conclusions.
Rewriting is a little too weak in its treatment of scoped atoms, because they cannot be renamed to avoid name-clash. Accordingly, we shall base our theory of confluence on rewriting in the presence of rule from (1). We shall see this rule has a non-trivial and delicate interaction with the definitions we have set up so far, giving us precisely what we want.
6. CONFLUENCE
6.1 Uniform rewrite rules
We shall give a well-behavedness condition on rewrite rules which we call uniformity, but first we prove properties of which give uniformity its power.
If and then
If ## then #[]#[]. Similarly for @.
If # then #. Similarly for @.
By Corollary 3.9 then ∆ . We modify the deduction of ∆ to replace any use of assumptions in with a (part of) the deduction of ∆ .
We work by induction on , write for the ‘hole’ in . We consider three interesting representative cases. If then #[] is # and ∆## trivially. If () then ##[] so #[]#[] by (#). If [] then #[] is easily derivable.
By induction on using the highly syntax-directed nature of the deduction rules, and using the first part.
Part 1 of the lemma above is a very thinly disguised Cut. Part 2 is, we think, rather striking. Part 3 is perhaps less surprising.
Say a rule is uniform when @ @ for all . Examples of uniform rules are:
For example consider . @@ for all , and @@ by (@). Consider . @@ is provable for by (@), for , and for . Examples of rules that are not uniform are:
If (1) is an equivariant set of uniform rewrite rules and
(2) then call uniform. Henceforth, fix some uniform set of rewrite rules.
If then @@ and #@ for all .
then for some there is some position () in and substitution such that ∆ and ∆ .
By the definition of uniformity, @@. By the first and third parts of Lemma 6.1@@. By the second part of that same result, ∆@@. We use similar reasoning to deduce ∆#@, only we use the first part of that lemma again, and Lemma 3.1.
In fact, we can prove something rather stronger, if we assume the context can allow us to deduce enough freshness information. Say ∆ has enough fresh atoms with respect to some finite set of atoms and finite set of unknowns when there exists a set of atoms with at least as many elements as such that and ∆ # for every and .
If then there is a such that
, @# and ## for all , provided that has enough fresh atoms with respect to the atoms and variables in .
As for the last lemma but using rule to freshen atoms as illustrated in the example below.
For example, using the notation of this lemma: consider a uniform rewrite system with the trivial rewrite rule (which is uniform). If and ∆ # (which has enough fresh atoms for and , namely ) then and ().
Henceforth we suppose ∆provides us with all the fresh atoms we need. In the case of finite terms and finite sequences of rewrites, if we run out we can always try again with a larger ∆.
6.2 Critical Pairs
Fix a rewrite system . Write ∆ for the appropriate pair of rewrite judgements. Call a valid pair a peak. Suppose
1. for 2 are copies of two rules in such that () ( ( and could be copies of the same rule).
2. () is a position in .
3. has solution (Γ) so Γ .
4. is consistent for 2; write respectively.
Then call the pair of terms-in-context
a critical pair. If () and , are copies of the same rule, or if () is the position of a variable in then we say the critical pair is trivial.
The condition be consistent is important. # () and () do not generate a peak; () () does have a solution ( []), but #()# is not consistent.
Say a uniform nominal rewrite system is locally confluent when if ∆ and ∆ , then exists such that ∆ and ∆ . We say such a peak is joinable.
Say a uniform nominal rewrite system is confluent when and ∆ , then exists such that and ∆ .
Trivial critical pairs are not necessarily joinable in NRSs. For instance with rules
the trivial critical pair ( ()) obtained by unifying () with # is not joinable. We obtain exactly the same phenomenon with the condition @ replacing # in this example.
The following result is the reason we consider uniform rules and use rule from (1):
In a uniform rewrite system trivial critical pairs are joinable.
Suppose there is a trivial critical pair
between rules for 2, where () is the position of a variable in .
The only reason we might not be able to apply in [] is if some freshness or scope condition in is unsatisfiable after , which was satisfiable before . For uniform rules, Lemma 6.3 guarantees that this cannot happen (up to rule ): we can always rewrite using and then apply . Therefore the critical pair is joinable.
This is the reason we are interested in critical pairs:
(Critical Pair Lemma). If all nontrivial critical pairs of a uniform nominal rewrite system are joinable, then it is locally confluent.
Suppose ∆ and ∆ is a peak (and as usual assume the context has enough fresh atoms). Then:
1. There exist and positions in , for 2.
2. There exist solutions to ( ([][])) ()) for 2.
Now there are two possibilities:
1. and are in separate subtrees. Local confluence holds by a standard diagrammatic argument taken from the first-order case [2]. We need Corollary 3.4 to account for the weaker notion of equality.
2. is a prefix of or vice versa, we consider only the first possibility. Suppose that , the general case follows using Corollary 3.4. There are two possibilities: Either this is a non-trivial critical pair, joinable by assumption, or it is a trivial critical pair, we use Lemma 6.4
In fact, we need to study rule a little more closely, to deal with two problems, before tying up the results with the Corollary below.
We call a critical pair -trivial if it is either trivial in the sense defined above, or if at least one of the rewrites is .
Problem 1. Rule has ( -trivial) critical pairs with any rule in which mentions tags, simply because can freshen them. Solution. The following lemma implies that -trivial critical pairs are always joinable:
If then (rule is reversible).
By calculations involving the following easily-verified technical fact # ()() ().
So we can strengthen the critical pair lemma to only check joinability of critical pairs that are not -trivial. We may be lax and just say ‘trivial’ and ‘nontrivial’ for ‘ -trivial’ and ‘not -trivial’, e.g. in the corollary below.
Problem 2. is necessarily nonterminating because can be applied to any term with a tag, forever (given enough fresh atoms). Solution. gives rise to an -abstract rewrite system obtained from but counting one or more instances of in sequence as one -abstract rewrite (we count as a single ‘abstract’ rewrite step). Say is terminating up to when its -abstract rewrite relation is terminating. By Newman’s Lemma [29] we can deduce confluence of a locally confluent and -terminating uniform rewrite system. We may be lax and write ‘terminating’ for -terminating.
Fix a uniform nominal rewrite system.
1. If nontrivial critical pairs are joinable then it is locally confluent.
2. If it is in addition terminating then it is confluent, and every term has a unique normal form modulo and rewrites with .
This result holds of rewrite systems in the previous sense
[14], which are the special case of the system here without .
6.3 Orthogonal Systems
We now treat a standard confluence criterion in rewriting theory [13, 23] (see also [24, 27]).
Say a rule is left-linear when each variable occuring in occurs only once. For example, ## () is left-linear but () is not.
We say a uniform, nominal rewrite system with only left-linear rules and no non-trivial critical pairs is orthogonal.
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 at position ’. In the case of rule , means rewrites to using at position , for some .
In Lemma 6.11 we say an instance of (tup’), (abs’), (new’), or (fun’) is for when it uses that rule.
.
By induction on the derivation of . The interesting cases are (new) and (new’); we use the technical fact from the proof of Lemma 6.6.
In a proof we are about to give, we shall have obtained and such that , and we shall say that we assume the atoms in are ‘sufficiently fresh for blah’. We mean that we choose a rewrite such that atoms in are chosen fresh enough not to clash with certain background assumptions in that proof.
If then , and if then . As a corollary, if and only if .
By induction on the position of the rewrite, and by induction on the derivation of .
If the system is uniform and orthogonal then is strongly confluent: 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’) for , that is ∆ () and ∆ () , then exits such that
We now proceed as illustrated and explained below:
We apply the inductive hypothesis to close ∆ , using Lemma 6.9 () to ensure the tags in are sufficiently fresh that Lemma 6.10 () and Lemma 6.3 can be used to deduce of all freshness and locality assumptions deducible of .
Since rules are left-linear still applies: ∆ () and ∆ () by (tup) for (for some substitution ). Finally, we use orthogonality, Lemma 6.9, and Lemma 6.6 ( is reversible) to close with a rewrite .
(3) is derived using (refl) then trivially and ∆ using the same rules as were used to derive ∆ , and ∆ is derivable using (refl).
The other cases are similar; the case of (new) and (new’) uses the lemma below.
We now come back to our theorem:
If the uniform rewrite system has only left-linear rules and no non-trivial critical pairs, then is confluent by Lemma 6.11. Since and by Lemma 6.10, is confluent.
7. EXTENSIONS: CLOSED, AND IS-IN
We will now show that, thanks to the use of contexts, the framework of nominal rewriting can be easily adapted to express strategies of rewriting. As an example, we will show how to define in this framework the system of closed reduction for the -calculus [16]. -terms are -terms with explicit constructs for substitutions, copying and erasing. Reduction on is defined in [16] using a set of conditional rule schemes, shown in Table 1, where denote variables, and denote terms.
Table 1: -reduction
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 #.
We extend the deduction and simplification rules from section 3 respectively with:
Here is any set of atoms strictly containing the atoms in 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 ):
8. CONCLUSIONS AND FUTURE WORK
The technical foundations of this work are derived from work on nominal logic [31] and nominal unification [36]. Nominal rewriting was presented in [14]. Here we extended nominal terms and the nominal unification algorithm with a new construct to model scope of names. We also showed that the nominal rewriting framework can be easily adapted to model reduction strategies: the context used to trigger rules allows us to express in a natural way constraints in the application of the rules.
There is interest in extending Structural Operational Semantics with abstraction and name-generation and Nominal Rewriting could provide (yet another!) forum for it. The authors have considered efficient implementation of ; there is no space here (we treated orthogonality instead) but the issue needs to be addressed for implementability. We have shown how rewriting can be extended with contexts (in the case of this paper, #, , and ; other constraints can be added to model other domains) and annotations on terms (), and we have shown how to retain classic properties of first-order rewriting (in this case, critical pairs and orthogonal rewriting results). We can encode useful structure in rules (name abstraction and generation, and rewrite strategies). It should be possible to consider different extensions, using the same idea of rewriting-in-context.
Abstraction vs. .
In conclusion we would like to ask: What are the properties of name-abstraction versus those of name-generation? The theory of for name-abstraction is generated by #[] and ## (). The theory of for name-generation is generated by @ and # . (This statement could easily be made formal.)
It is certainly not the case that # []. It is also not the case that @@ (). (Though rule gives us something similar, by allowing us to rename tagged atoms.) So abstraction and name-generation are different. How do they interact in our system?
and abstraction are independent in that neither depends on the other for its construction. They coexist in our system with quite subtle interactions. The relevant results are: # implies @ by Lemma 3.1, which comes down to a deduction rule (#@). @ implies # indirectly through Lemma 6.3, which comes down to a rewrite rule .
Indeed equality itself is rather subtle; it is constructed in layers starting with , syntactic identity an intrinsic property of terms, then defined using a context and handling abstraction [], and finally rule which is built into the rewriting and deals with (as we see from Lemma 6.3 and the final parts of 6.2 and 6.3). Finding these different layers, and understanding their interactions, were the authors’ principal technical difficulties designing the system.
Can model abstraction, or vice versa? Abstraction cannot directly model , because does not abstract and of course abstraction does. The converse does not hold, since with -renaming rules could model the abstraction part of abstraction, but we still have @, which abstraction should not satisfy.
Recall our reaction systems for the -calculus and the -calculus from 5.2. We used abstraction to model the -calculus term as [] because the is normally considered -convertible in the -calculus literature. But in fact we could have used directly and saved ourselves the rewrite []:
We cannot model the -calculus ‘abstract in ’ as , since is provable. We can model in the -calculus with as , the reaction is ([]) .
9. REFERENCES
[1] M. Abadi, L. Cardelli, P-L. Curien, and J-J. Lévy, Explicit substitutions, Journal of Functional Programming 1 (1991), no. 4, 375–416.
[2] F. Baader and T. Nipkow, Term rewriting and all that, Cambridge University Press, 1998.
[3] F. Barbanera, M. Fernández, and H. Geuvers, Modularity of strong normalization in the algebraic--cube, Journal of Functional Programming 6 (1997), 613–660.
[4] H. P. Barendregt, Pairing without conventional constraints, Zeitschrift für mathematischen Logik und Grundlagen der Mathematik 20 (1974), 289–306.
[5] C. Bertolissi, H. Cirstea, and C. Kirchner, Translating combinatory reduction systems into the rewriting calculus, RULE 2003, Valencia, Spain, 2003.
[6] E. Bonelli, D. Kesner, and A. Ríos, From higher-order to first-order rewriting, LNCS vol. 2051, 2001.
[7] V. Breazu-Tannen and J. Gallier, Polymorphic rewriting conserves algebraic strong normalization, Theoretical Computer Science 83:1 (1991).
[8] V. Breazu-Tannen and J. Gallier, Polymorphic rewriting conserves algebraic confluence, Information and Computation 82 (1992), 3–28.
[9] J. Cheney, The complexity of equivariant unification. Proceedings of ICALP 2004, LNCS, 2004.
[10] H. Cirstea and C. Kirchner, The Rewriting Calculus - Part I, Logic Journal of the Interest Group in Pure and Applied Logics 9 (2001), 363–399.
[11] H. Cirstea and C. Kirchner, The Rewriting Calculus - Part II, Logic Journal of the Interest Group in Pure and Applied Logics 9 (2001), 401–434.
[12] R. David and B. Guillaume, A -calculus with explicit weakening and explicit substitution, Mathematical Structure in Computer Science 11(1) (2001), 169–206.
[13] N. Dershowitz and J.-P. Jouannaud, Rewrite Systems, Handbook of Theoretical Computer Science: Formal Methods and Semantics, vol. B, 1989.
[14] M. Fernández, M. J. Gabbay and I. Mackie,Nominal Rewriting Systems, ACM Symposium on Principles and Practice of Declarative Programming (PPDP’04), ACM Press, 2004.
[15] M. Fernández and J-P. Jouannaud. Modular Termination of Term Rewriting Systems Revisited. ADT’94, LNCS 906, 1994.
[16] M. Fernández, I. Mackie and F-R. Sinot, Closed Reduction: Explicit Substitutions without alpha-conversion, MSCS 2005 (to appear).
[17] M. J. Gabbay, The -calculus in FM, Thirty-five years of Automath (Fairouz Kamareddine, ed.), Kluwer, 2003.
[18] M. J. Gabbay and A. M. Pitts, A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, vol. 13, pp. 341–363, 2002.
[19] M. Hamana, Term rewriting with variable binding: An initial algebra approach, PPDP 2003.
[20] J.-P. Jouannaud and C. Kirchner, Solving equations in abstract algebras: a rule based survey of unification, Computational Logic: Essays in Honor of Alan Robinson, 1991.
[21] J.-P. Jouannaud and M. Okada, Executable higher-order algebraic specification languages, 6th IEEE Symposium on Logic in Comp. Sci., 1991, pp. 350–361.
[22] Z. Khasidashvili, Expression reduction systems, Proceedings of I.Vekua Institute of Applied Mathematics (Tbisili), vol. 36, 1990, pp. 200–220.
[23] J.-W. Klop, Term Rewriting Systems, Handbook of Logic in Computer Science, Oxford University Press, 1992.
[24] J.-W. Klop, V. van Oostrom, and F. van Raamsdonk, Combinatory reduction systems, introduction and survey, Theoretical Computer Science 121 (1993), 279–308.
[25] J-W. Klop, Combinatory reduction systems, Mathematical Centre Tracts, vol. 127, Amsterdam, 1980.
[26] P. Lescanne, From to a journey through calculi of explicit substitutions, POPL’94, 1994.
[27] R. Mayr and T. Nipkow, Higher-order rewrite systems and their confluence, TCS 192 (1998), 3–29.
[28] Milner, Parrow, and Walker, A Calculus of Mobile Processes, II, Inf. and Comp. 100:1 1992, 41–77.
[29] M.H.A. Newman, On theories with a combinatorial definition of equivalence, Annals of Mathematics 43 (1942), no. 2, 223–243.
[30] B. Pagano, Des calculs de substitution explicite et de leur application à la compilation des langages fonctionnels, Ph.D. thesis, Université de Paris 6, 1998.
[31] A. M. Pitts, Nominal logic, a first order theory of names and binding, Information and Computation 186 (2003), 165–193.
[32] A. M. Pitts and I. D. B. Stark, Observable Properties of Higher Order Functions That Dynamically Create Local Names, or: What’s new?. LNCS, vol. 711, 1993, pp 122–141.
[33] A. M. Pitts and M. J. Gabbay, A metalanguage for programming with bound names modulo renaming, MPC2000, LNCS 1837, 2000, pp. 230–255.
[34] F. van Raamsdonk, Confluence and normalisation for higher-order rewriting, Ph.D. thesis, Free University of Amsterdam, 1996.
[35] M. R. Shinwell, A. M. Pitts, and Murdoch Gabbay, FreshML: Programming with binders made simple, ICFP 2003, pp. 263–274.
[36] C. Urban, A. M. Pitts, and M. J. Gabbay, Nominal unification, CSL’03 & KGC. LNCS 2803, 2003, pp. 513–527.
[37] C. Urban, Nominal matching, in preparation, 2004.
Notes
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 2002 ACM X-XXXXX-XX-X/XX/XX ...$5.00.