Under consideration for publication in Formal Aspects of Computing
Capture-Avoiding Substitution as a Nominal Algebra
Murdoch J. Gabbay and Aad Mathijssen 1
Abstract. Substitution is fundamental to the theory of logic and computation. Is substitution something that we define on syntax on a case-by-case basis, or can we turn the idea of substitution into a mathematical object?
We give axioms for substitution and prove them sound and complete with respect to a canonical model. As corollaries we obtain a useful conservativity result, and prove that equality-up-to-substitution is a decidable relation on terms. These results involve subtle use of techniques both from rewriting and algebra.
A special feature of our method is the use of nominal techniques. These give us access to a stronger assertion language, which includes so-called ‘freshness’ or ‘capture-avoidance’ conditions. This means that the sense in which we axiomatise substitution (and prove soundness and completeness) is particularly strong, while remaining quite general.
Keywords: Substitution, nominal techniques, nominal algebra, binding, capture-avoidance, nominal rewriting, omega-completeness.
1. Introduction
Substitution is intuitively the operation [] meaning:
Replace the variable by in .
Is there an algebra which describes exactly the properties of [] independently of what and are (-terms, formulae of a logic, terms of some process calculus, or any mixture or variation thereof)?
Consider by way of analogy the notion of ‘a field’. This has an algebraic characterisation which tells us what properties ‘a field’ must have, independently of which field it is, or how it may be implemented (if we are programming). This is useful; for example the definition of ‘vector space’ is parametric over fields, and this step requires a characterisation of what fields are [BS81].
When we begin to axiomatise substitution, unusual difficulties present themselves. Consider the following informally expressed candidate property of substitution:
This is not algebraic, because of the side-condition fv(). Here fv() is ‘the free variables of ’, which is a property of the syntax of .
So is it the case that substitution cannot be axiomatised, and only exists as an incidental property of syntax used to talk about ‘real’ mathematical objects? But in that case, what is the status of the intuition which makes us agree that the property above should be satisfied by any self-respecting substitution action?
We shall argue that the properties of Figure 1 axiomatise substitution, all of substitution, and nothing but substitution. We express them in Nominal Algebra as a theory called SUB (given formal meaning in the rest of this paper). Informally, the axioms express the following:
(var): A variable with replaced by , is .
(#): If is fresh for then with replaced by is .
(f): Substitution distributes through term-formers; f ranges over them.
(abs): Substitution of distributes under an abstraction [], provided a capture-avoidance condition is satisfied ( is fresh for ).
(ren): If is fresh for then with replaced by is identical to with replaced by and simultaneously replaced by .
(): [] is sugar for sub([]). In (), is a term not of the form [] so we cannot use that sugar. The reader can think of () as related to -equality from the world of the -calculus, though is not a function. The reader can also think of () as related to a known property of the atoms-concretion operation of Gabbay-Pitts abstraction [GP02], though sub is not atoms-concretion. More on this in Subsection 1.2.
Formally, Figure 1 uses nominal terms [UPG04] as a syntax, and nominal algebra [GM07, GM06b] as an algebraic framework. We describe these below.
A number of questions now arise:
1. Is this substitution and if so, in what sense; for what model are the axioms sound?
2. Are the axioms complete for that model?
3. Do other (perhaps unexpected) models exist of the same axioms?
4. Can theories be built on top of this one by adding axioms for predicate logic, functional programming, unification and logic programming, simultaneous equations, and so on?
1.1. Answers to questions and map of the paper
Section 2 defines nominal terms and nominal algebra, which fix the syntax and judgement forms we use for our axiomatisation. Section 3 creates a concrete model out of syntax and defines a completely standard capture-avoiding substitution action on the model — this is what we want to capture in axioms. Section 4 defines a relatively weak subset of SUB which we call SIMP (for ‘simple’) which is sound for a concrete model, but not complete. This answers question 1 above. Section 5 proves useful properties of this simple axiomatisation; here we make heavy use of techniques from (nominal) rewriting.
Section 6 explores the stronger axioms of Figure 1 formally as a nominal algebra theory. Decidability of these axioms is proved in Subsection 6.2, and completeness with respect to the concrete model from section 3 is proved in Subsection 6.3. This answers question 2 above and completes the proof that Figure 1 does represent substitution.
In other as-yet unpublished work the first author shows how Fraenkel-Mostowski set theory (the underlying model of nominal techniques) [GP02] supports a substitution action. In the case of a set representing a term in the concrete model of this paper, the substitution action coincides with capture-avoiding substitution. However it extends smoothly, in our opinion quite remarkably, to the entire set theoretic universe. This is an answer for question 3 above and, in our opinion, provides independent evidence that substitution has independent mathematical stature.
In other work [GM07, GM06c] we have investigated how the axiomatisation of substitution can be used to develop algebraic theories, for example of first-order logic. This is the start of an answer to question 4.
The Conclusions discuss related and future work.
1.2. Relation with the conference version
A conference version of this paper has appeared [GM06a]. In this paper the technical machinery has been revised and considerably simplified by making more use of models.
As part of these changes we identify an intermediate axiomatisation SIMP. This captures SUB on closed terms but is weaker than SUB on open terms, in a sense made precise in Theorem 5.24. SIMP can be identified with the usual definition of capture-avoiding substitution.
We give a procedure for converting equalities in SUB into equivalent (in a suitable sense) equalities in SIMP over an extended signature (see Subsection 6.2). This is part of the proof of decidability of SUB, and it yields a clearer and more efficient algorithm than the one in the conference version.
This paper includes a new axiom (), correcting a technical error of the conference paper: () is necessary for -completeness (Subsection 6.3). In fact () is only necessary if we admit unknowns of abstraction sort [] (using terminology from the rest of this paper, or from [GM06a]). Although it is not strictly necessary to admit unknowns of abstraction sort, it allows us to talk about substitution at a more general level, resulting in a more smooth presentation (see Subsection 6.4).
2. Nominal algebra
2.1. The syntax of nominal terms
First, we define a syntax of nominal terms. The syntax we use here is tailored to our application of axiomatising substitution; see elsewhere for general treatments [UPG04, FG07].
Fix a base sort and call it the sort of terms. Define sorts by the following grammar:
This simple sort system is sufficient to make sure that terms are well-formed; the reader should not necessarily view it as a ‘typing system’.
Extensions with pair sorts , or base sorts other than (e.g. to model terms and formulae in first-order logic [GM06c]) cause no essential difficulties, aside from inflating the mathematics with extra cases.
Fix some countably infinite set of atoms . These model object-level variable symbols (the ones we substitute for).
Fix a countably infinite collection of unknowns . These represent unknown terms of sort or []. We assume unknowns are inherently sorted and infinitely many populate each sort. is shorthand for ,
A permutation of atoms is a bijection on atoms with finite support meaning that for some finite set of atoms () , and for all other atoms (; in other words, for ‘most’ atoms is the identity.
A term-former f is a formal symbol to which is associated an arity (). We may write f : () for f which has arity (). We call a collection of term-formers a signature.
Atoms, unknowns, signatures and other distinct syntactic classes, are assumed disjoint.
Convention 2.3. We shall use a permutative convention that range permutatively over atoms, so that for example and are always distinct.
In the rare circumstances where we do not want this behaviour, we use primes and subscripts, such as , and (where is an unknown and is an index).
Let terms be inductively defined by:
Here ranges over atoms, over unknowns, over permutations, and f over term-formers.
We call a moderated unknown, representing an unknown term on which a permutation of atoms is performed when it is instantiated. An abstraction represents a term in which an atom is abstracted.
Call a term closed when it does not mention any unknowns.
Write syntactic identity of terms and as to distinguish it from provable equality. Note that if then , since permutations are represented by themselves. Important: we do not quotient terms in any way.
Let (valid) sorting assertions : , read ‘ has sort ’ be inductively defined by:
Note that atom represents a variable symbol of sort . Also note that in the rules for and [], is restricted to and [].
We consider only terms that adhere to the sorting assertions from now on.
A signature for the lambda calculus consists of the following term-formers:
The sorting system is such that a well-sorted term of the form lam() must be of the form lam() (so ) or lam([]) (so
It may help to show how nominal terms in this signature relate to ‘ordinary’ syntax. For convenience identify atoms with variable symbols, then the syntax of the untyped -calculus is inductively defined by:
We define a map (-) to nominal terms by:
() app(()
We shall see that lam([]) behaves much like the -context - where - is a ‘hole’.
Substitution is just a term-former, and this is reflected by the notion of a substitution signature.
We call a signature a substitution signature when:
contains two term-formers sub, one with arity ([]), and one with arity ([][])[];
for any other term-former f in , sorting arities are of the form (), where
A term sub() represents an explicit substitution. We write [] as shorthand for sub([]). We already used this shorthand in Figure 1.
Note that a well-sorted term of the form sub() must be of the form sub(), or sub(sub()), or [] (without sugar: sub([])). If sub() is closed then it has the form [][], or [][], or [].
We will only consider substitution signatures in the rest of this paper.
Term-formers f other than sub are intuitively ‘the language over which substitution for atoms occurs’. Note that sorting assertions allow arguments of abstraction sort []; this is useful for modelling languages with abstractors, such as , , fix, , and so on. Examples follow:
A substitution signature for the lambda calculus is:
So intuitively, the two term-formers sub take care of substitution, and app and lam take care of there being a term-language to substitute over (in the presence of some axioms, which are our object of study in this paper).
We can express natural numbers with fixpoints using the following substitution signature:
Unknowns of sort [], and the second sub above of arity ([][])[], are convenient but not necessary; see in Subsection 6.4.
The signature is arbitrary and may be empty (aside from sub), except that Theorem 6.29 (a strong completeness result with respect to a single term model) requires a term-former taking at least two arguments (for example app or plus) to avoid a degenerate case. All other results, including Theorem 6.20 (a notion of completeness with respect to term models in extended signatures which are never degenerate) are valid even in a signature with just sub.
2.2. Permutation, substitution and freshness
Before we can introduce an equational logic on nominal terms, we need to be able to
permute atoms in terms,
substitute unknowns with terms, and
decide whether an atom is fresh for a term.
In this subsection we elaborate on these elements.
In Definition 2.2 we defined permutations as finitely supported bijection on atoms. As usual write id for the identity permutation, for the inverse of , and for the composition of and , i.e. ()((()). id is also the identity of composition, i.e. id and id . Importantly, we shall write () for the permutation that swaps and , i.e. the permutation that maps to and vice versa, and maps all other to themselves. Also, we usually abbreviate a moderated unknown id to .
Write when () . Write (or ) for ‘ (or ) occurs in (the syntax of) ’. Occurrence is literal, e.g.
A permutation action is defined inductively on by:
Intuitively, propagates through the structure of until it reaches an atom or a moderated unknown.
() () and id .
By an easy induction on the structure of .
Call a substitution a finitely supported function from unknowns to terms of the same sort. Here, finite support means that
Write [] for the substitution , defined by
The substitution action is inductively defined by:
We may call an instance of .
Intuitively, propagates through the structure of until it reaches an atom or a moderated unknown. ‘evaporates’ on an atom, and acts on the unknown of a moderated unknown. The moderating permutation then passes into the term substituted in that position. We suggest a reading of as ‘permute in whatever eventually becomes’.
Note that meta-level substitution does not avoid capture; ([])[]
The following commutation is easy to prove [UPG04, FG07]:
().
By straightforward induction on the structure of .
A freshness (assertion) is a pair # of an atom and a term. Call a freshness of the form # (so ) primitive. Write ∆and for (possibly infinite) sets of primitive freshnesses and call them freshness contexts.
We may drop set brackets in freshness contexts, e.g. writing ## for ##. Also, we may write # for ##. Furthermore, write ∆when occurs anywhere in ∆, and ∆when occurs anywhere in ∆.
Define derivability on freshnesses in natural deduction style [Hod01] by the rules in Figure 2. Here:
and permutatively range over atoms, i.e. and represent any two distinct atoms;
ranges over permutations
ranges over unknowns;
and range over nominal terms;
f ranges over term-formers; there is one copy of the rule for each term-former.
We use similar conventions in the rest of this paper.
The side-condition id of the (#X) rule restricts to non-empty permutations. There is no mathematical reason for this, but there is a nice computational one: the algorithm obtained by reading rules bottom-up, must terminate.
Write ∆ # when a derivation of # exists using the elements of ∆as assumptions. Say that ∆ entails # or # is derivable from ∆; call this a freshness judgement.
We usually write # as #. We will also write ∆ for a set of freshnesses when ∆ # for each #.
For example, in the substitution signature for the lambda calculus (Example 2.8), we have #lam([]) and ##app( lam([])):
The derivation rules are completely syntax-directed, so they also hold in the opposite direction:
# then #
# then ∆ ()#.
#[] then ∆ #.
#f() then ∆ #, for 1 .
By an easy induction on the structure of the derivation rules in Figure 2.
(perm)
Sometimes the freshness context ∆may be strengthened:
If ## and then ∆ #.
We transform a derivation of ## into a derivation of ∆ #:
If ## by assumption then ## ∆. Since we assumed #, we know . Then # ∆, and we conclude ∆ # by assumption.
(#X): If ## is derived using (#X) then #()#. By assumption , so (. Since also , we know () . By the inductive hypothesis and the simple fact that we obtain ∆ ()#. We conclude ∆ # using (#X).
(#ab) and (#[]a) carry over directly.
(#[]b) and (#f) are straightforward using the inductive hypothesis and the following facts: if [] then , and if f() then for 1 .
# then ∆ ()#.
By an easy induction on freshness derivations (Figure 2).
Write ∆ for #
Note that ∆ is not usually a freshness context unless () is an unknown for each #
For any ∆# and ∆ then ∆#.
The structure of natural deduction derivations is such that the conclusion of one derivation may be ‘plugged in’ to an assumption in another derivation, if assumption and conclusion are syntactically identical. The structure of all the rules except for (#X) is such that if unknowns are instantiated by nothing need change. For the case of (#X) we use Lemma 2.23.
The above condition ∆ ensures that ∆ is consistent, in the sense that #() is derivable from for each #
2.3. Equality
An equality (assertion) is a pair where and are terms of the same sort. Define derivability on equalities in natural deduction style by the rules in Figure 3.
We may call this the core theory and refer to it as CORE. We may write ∆ for ‘ is derivable from assumptions ∆in the core theory’; call this an equality judgement. We also write as .
In (fr) square brackets denote discharge in the sense of natural deduction (as in implication introduction); ∆denotes the other assumptions of the derivation of . This is useful because unknowns in a derivation intuitively represent unknown terms, but any finite collection of such terms can mention only finitely many atoms; (fr) expresses that we can always find a fresh one. In sequent style (fr) would be
In (perm) read () as ‘swap and in ’. This single rule expresses -equivalence. To provide some intuition, here are some examples on closed terms.
Note that we use [] ()
(Note here that [] ()
In the substitution signature of the lambda calculus (Example 2.8), [][]app(][]app() is derivable. Since [][]app() () [][]app() it suffices to show () [][]app(][]app(). By (perm) this follows from ∆ #[][]app(), which follow using (#[]a) and (#[]b).
The following is an example of -equivalence on open terms, which shows that we can rename the atom which is substituted for.
#[) )[]
2.4. Inequality of nominal terms up to CORE
It is important to be able to decide when two nominal terms are not equal in CORE because:
We need this to show that CORE is consistent (does not equate all terms; Corollary 2.33).
We need to prove that CORE captures -equivalence (and no more than -equivalence; see Theorem 3.9).
We promised to show that equality up to axioms for substitution is decidable. If we are unable to determine equality and inequality of terms without any axioms then our project would be doomed from the start.
The rules in Figure 3 are unsuited to determining inequality. The problem is that (tran) is not syntax-directed, in the sense that appears in the premises and not in the conclusion. This makes derivation-search, and any proof that derivation-search must fail, hard. In this subsection we give a syntax-directed version of CORE which is more convenient for proving that derivations cannot exist. It bears an astounding resemblance to the equality on nominal terms introduced in nominal unification [UPG04] (we still need nominal algebra so we can extend CORE with axioms).
The following definition was introduced in [UPG04, Figure 2]; the proofs are modelled on a method presented in [FG07, p.13]:
Let be an ordered tuple of a term , a freshness context ∆, and a term . Let the derivable equalities of be inductively defined by the rules in Figure 4. Here we write ds() for the set () , the difference set of and . We write ∆ ds()# for a set of proof-obligations #, one for each ds().
if and only if is derivable in the sequent system for CORE.
The left-to-right direction is by induction on the structure of derivations of ∆ . By the inductive hypothesis it suffices to show:
Syntax-directed equality is an equivalence relation and a congruence. This is [FG07, Theorem 24].
# and ∆ # then () . This follows by an induction on the structure of .
If where then . By a straightforward induction on the structure of derivations of . The case of (Absab) uses Lemma 2.22 to strengthen the assumption ∆## to #.
For the right-to-left direction we work by induction on derivations of . By the inductive hypothesis it suffices to show:
. This is an instance of (refl).
ds()# then ∆ . By induction on the number of elements in ds(). If this set is empty then and the result follows easily by (refl). Now suppose ds(). We construct a partial derivation of the proof obligation:
The remaining equality
for 1 , then ∆ f( f(). Using a number of instances of (tran) and (congf).
then ∆
() and ∆ # then ∆
() and ∆ # respectively. Then the following is a derivation of ∆
As corollaries of Theorem 2.31 we obtain syntactic criteria for determining equality in CORE, and consistency of CORE.
precisely when one of the following hold:
1. and .
2. and and ∆ ds()#.
3.
4.
5. f() and f() and ∆ for 1 .
By Theorem 2.31 it suffices to inspect the rules for , which are just a rendering of the above criteria in terms of derivation rules.
For all ∆there are and such that ∆ .
By Corollary 2.32 is never derivable.
2.5. Axioms and theories
We now come to the raison d’être of nominal algebra: axioms.
Call a triple where is a finite freshness context, an axiom. We may write when is empty (the empty set). Call an instance of an axiom a step in a derivation where the conclusion is obtained from an axiom by instantiating unknowns by terms and permutatively renaming atoms such that the hypotheses are corresponding instances of freshness conditions of the axiom.
This is formally expressed by the rule (ax) in Figure 5. Here ranges over permutations and ranges over substitutions. Recall that we write for #
The reader might have expected that the premise of the axiom rule should be instead of . It turns out that both versions are correct, because of Lemma 2.23 for any ∆.
Call a set of axioms T a theory. Write ∆ when can be derived from ∆ using only axioms from T.
A number of properties on freshnesses also hold for equations of any theory T.
then ∆ .
For any T and ∆ then ∆.
Analogous to the proof of Theorem 2.25.
3. Substitution on ground terms
Call terms , and ground terms when they do not mention unknowns or explicit substitutions. Ground terms are inductively characterised by
where f ranges over all term-formers except for sub.
We now consider the meaning of explicit substitution on ground terms, in a suitable formal sense. This will make a connection between [] and actual capture-avoiding substitution on syntax, and we will find that connection useful later.
Define a ‘free atoms of’ function fa() on ground terms inductively as follows:
# if and only if fa
By induction on the structure of .
Let the size of a ground term be inductively defined by:
For each finite set of atoms fix some choice of ‘fresh’ atom not in that finite set. Then define a ground substitution action [] on ground terms of sort and [] inductively on the size of by:
where f ranges over all term-formers excluding sub. By ‘ fresh’ we mean that is chosen such that fa
Note that the ground substitution action is well-defined, since []
Lemma 3.6 states familiar properties of ground terms. It makes the vital connection between ‘substitution as we know it’ and the nominal technology we bring to bear on it.
For ground terms , , :
1. Identity. [.
2. Swapping. If # then [) .
3. Garbage collection. If # then [.
4. Non-capturing distributivity. If # then [][[][[]].
Part 1 follows from the stronger property that [] , which we can show by an easy induction on the structure of . The other parts all follow by an induction on the size of .
We will now show how equality on ground terms in theory CORE coincides with a straightforward definition of -equivalence on ground terms: syntactic equality extended with a rule to rename bound variables.
Define an -equivalence relation inductively by the rules in Figure 6. Here ‘ fresh’ means any such that fa
If fa() then () .
All instances of and in must occur in the scope of abstractors [] and []. Traverse the structure of bottom-up using the rules of Figure 6 to rename abstractions by [] and [] to fresh atoms. Call the new term . Now () because . Equality is symmetric, so we reverse the process to return to .
Lemma 3.8 enables us to prove the main result of this section: in the presence of the equalities of CORE, ground terms and are provably equal if and only they are -equivalent.
if and only if .
We prove the left-to-right implication by induction on the structure of , using the syntactic criteria of Corollary 2.32. The cases of and f() are easy. Now suppose
1.
2.
Conversely suppose that . It suffices to show that equality in CORE can simulate every derivation rule of =. We treat the only non-trivial case: []
4. The theory SIMP; simply substitution
We introduce nominal algebra theory SIMP which is sound but not complete with respect to the ground term model from Section 3. This is an important technical step towards SUB because we shall prove properties of SUB by reducing them to properties of SIMP.
Let SIMP be the nominal algebra theory with axioms as in Figure 7.
Here, f ranges over all term-formers except for sub. Recall that and are unknowns of , and that the are unknowns of sort or [] (which one applies depends on the instance of f).
For ground terms and , if # then [.
By induction on the size of .
If and are ground terms then [[] is always derivable.
By induction on the size of . We only consider the interesting cases:
By axiom (abs ) also
since #. By the inductive hypothesis and (cong[])
Since [) by part 2 of Lemma 3.6, we deduce
using the rules of equality. Using (tran) we conclude ([])[]([][]).
Define the translation of closed terms to ground terms inductively on closed terms by:
Note that ([])[] follows from the sub case, since []() ([])by the abstraction case.
For any closed term , if # then #.
By induction on the structure of .
Note that the converse of Lemma 4.5 does not hold. Take for example []. Then #([]) since ([]). But #[], since #.
For any closed term , .
By induction on the structure of . We consider the only non-trivial case sub(). By definition sub()[] where [], and by the inductive hypothesis, and . By (congf) and (tran), we obtain
By Theorem 4.3 we know [[]. Since []and [] sub(), this is syntactically equivalent to
By an application of (tran) we conclude sub( sub()as required.
As a corollary of Theorem 4.6 all standard properties of capture-avoiding substitution on ground terms carry over to closed terms.
For closed terms , , :
1.
2. If # then [) .
3. If # then [.
4. If # then [][[][[]].
Using Theorem 4.6 and Lemma 3.6.
In this section we have established that in the presence of the equalities of SIMP, and are provably equal, for closed terms . Yet many questions related to open terms remain:
1. Is SIMP conservative over CORE? That is, if two terms that do not mention sub are equated in SIMP, are they necessarily equated in CORE? (Answer: Yes.)
2. Is equality in SIMP decidable? (Answer: Yes.)
3. Is SIMP sound for the ground term model? That is, if two terms are equated in SIMP, are all their closed instances -equivalent, if we interpret every occurrence of sub by capture-avoiding substitution? (Answer: Yes.)
4. Is SIMP complete? That is, if all closed instances of two terms are -equivalent where we interpret sub by capture-avoiding substitution, are the terms themselves provably equal in SIMP? (Answer: No, but a more powerful theory SUB exists which is complete, and which retains properties 1 to 3 of this list.)
The next two sections provide answers to these questions together with detailed proofs.
5. Substitution on open terms using SIMP
In this section we recall a notion of rewriting called nominal rewriting [FG07], which is tailored to nominal terms. We will use nominal rewriting to prove properties on open terms of theory SIMP.
5.1. Nominal rewriting
A nominal rewrite rule is a tuple of a freshness context and terms and of the same sort such that and mention only unknowns appearing in .
A nominal rewrite system R is a set of nominal rewrite rules. It determines a set of nominal rewrites inductively by the rules in Figure 8.
Write ∆ when the rewrite ∆ is not derivable.
In the (f) rule of Figure 8, f ranges over all term-formers of the signature of R (whatever that signature is). The (rew) rule is closely related to the (ax) rule from Figure 5. We discuss the aspects of this rule in more detail:
The permutation allows us to permutatively rename atoms. Consider for instance the substitution signature of the lambda calculus (Example 2.8) extended with a term-former const : (), and write const() as const. Then the rewrite rule app() const generates, for example, rewrites app() const and app() const but not app() const because no can identify with .
The substitution gives unknowns in rules the character of ‘unknown terms’, and is subject to the freshness conditions formulated by ∆ . Note that we could also have used ∆ , which is equivalent to ∆ by Lemma 2.23.
The use of equality in CORE gives abstractions []- the character of real abstractions. For example the rule lam([]lam([])) const generates rewrites
The following result is easy to prove from the definition of rewriting:
and ∆, then ∆.
By induction on the derivation of ∆ we construct a derivation of ∆.
Write ∆ for the transitive reflexive closure of R defined inductively by the rules in Figure 9.
Write ∆ when ∆ is not derivable.
If a term does not have any rewrites, the transitive reflexive closure of R is precisely CORE-equality:
If there is no such that ∆ then
iff
Suppose there is no such that ∆ then by (refl) also ∆ . Conversely if ∆ then this rewrite must be derived using (refl) by an inductive argument.
Call a nominal rewrite system R confluent when if ∆ and ∆ then there is some such that ∆ and ∆ .
Call a nominal rewrite system R strongly normalising when there is no infinite sequence such that ∆ for all 1 .
If a derivation exists of ∆ then that derivation mentions (rew) exactly once.
By the structure of the derivation rules from Figure 8.
If a rewrite ∆ occurs, it must occur at some subterm of (the subterm where we actually use (rew) and prove ∆ and ∆ ). We say that the rewrite occurs at inside . If the derivation tree has just an instance of (rew), then we may say the rewrite occurs at top level.
Call a pair of nominal rewrites ∆ and ∆ a critical pair when at least one of the rewrites occurs at top level. If any of the two rewrites occurs at a moderated unknown inside , call the critical pair trivial. Otherwise call it nontrivial.
Call a rewrite rule uniform when ∆ # and ∆ imply ∆ # for all ∆ and . A rewrite rule is left-linear when does not mention the same unknown more than once. 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.
See [FG07, Theorem 65].
Nominal rewriting is the default notion of rewriting for nominal terms, like higher-order rewriting (such as CRS’s [KvOvR93] and HRS’s [MN98]) is for higher-order terms. The major differences between the two frameworks can be summarised as follows:
The default notion of instantiation of meta-variables is capturing for nominal rewriting whereas it is capture-avoiding for higher-order rewriting.
Nominal rewriting uses unification up to whereas higher-order rewriting uses unification up
Detailed comparisons are elsewhere [FG07].
5.2. SIMPr: explicit substitution rewritten
Let SIMPr be the nominal rewrite system defined in Figure 10.
A basic correctness result is this:
then ∆ is derivable.
The (Rb) rule cannot be represented by a rule in a higher-order rewrite system, since in such a system object-variables only exist when they are bound by a meta-level abstraction. That is, the rule sub() does not represent (Rb) since represents a meta-variable instead of an object-variable. It represents the more general rule #[] .
All rewrite rules of SIMPr are uniform.
For each rule, use appropriate instances of Lemma 2.21. For example, for the (Rabs) rule, we need to show that ∆ #([])[] and ∆ # imply ∆ #[]([]) for any and ∆. From the first assumption we know, by Lemma 2.21:
if or then #
if and then # ∆and #
Using these assumptions it is easy to show ∆ #[]([]) by case distinction on .
SIMPr is confluent.
By Lemma 5.15 all rewrite rules of SIMPr are uniform. Also, SIMPr has no non-trivial critical pairs and every rule is left-linear (each unknown is mentioned on the left at most once). Then SIMPr is orthogonal and uniform by Definition 5.9. We conclude that it is confluent by Theorem 5.10.
Confluence of SIMPr has a number of nice corollaries, which comprise the remainder of this subsection.
Call a term a SIMPr-normal form with respect to ∆when there is no such that .
Suppose that and are SIMPr-normal forms with respect to ∆. Then
if and only if
The (empty) set of axioms of CORE is a subset of the axioms of SIMP so a derivation in CORE is also a derivation in SIMP and it follows that if ∆ then ∆ .
Conversely suppose ∆ . By Theorem 5.16 there is some term such that ∆ and . By assumption there can be no and such that ∆ and ∆ . Then and ∆ by Lemma 5.4, and we conclude ∆ by (symm) and (tran).
Suppose that and do not mention the term-former sub. Then
if and only if
This is an instance of Theorem 5.18, since if and do not mention sub, then and are SIMPr-normal forms with respect to any ∆.
Recall the notation for closed terms from Definition 4.4.
For closed terms and ,
is equivalent to by Theorem 4.6, (symm) and (tran). By Corollary 5.19 this is equivalent to .
For all ∆there are and such that ∆ .
A corollary of Corollaries 5.19 and 2.33.
For the final theorem of this subsection we need a few definitions.
Call a substitution closing for an unknown when () is a closed term. Call closing for a term or closing for a freshness context ∆when () is closed for every or
Say a closing substitution for ∆is ∆-consistent when , i.e. when #() for all #
SIMP is sound for the ground term model. That is: then for all ∆-consistent closing substitutions (for ∆, and ).
by Theorem 2.37 and our assumption that . We obtain by Corollary 5.20, since and are closed. We conclude by Theorem 3.9, since and are ground.
5.3. Failure of completeness for SIMP
SIMP is not a complete theory of substitution on ground terms. Unknowns in nominal algebra represent unknown terms, and here are some examples of statements that are true for every closing (for the unknowns in the statements) but which are not derivable in SIMP:
1.
2.
3.
4.
For part 1, we can easily check using the syntactic criteria of Corollary 2.32 that [ is not derivable. Now since [] and have no SIMPr rewrites, we conclude [ by Theorem 5.18. The proofs of the other parts are similar.
The fact that above assertions are derivable for closing substitutions follows by Corollary 4.7.
Nominal algebra has a model theory and satisfies soundness and completeness [GM06b, GM07]. So SIMP has ‘nonstandard’ models which contain ‘pathological elements’ for which the above equalities do not hold. SIMP defines substitution, but it does not express all of the properties which emerge from that definition. To do that we must strengthen the theory. Before that however, it is useful to consider the computational content of SIMP.
5.4. Strong normalisation and decidability
We expect the part of a -calculus that handles substitution to be terminating [BR95, Les94] — so is SIMP terminating? After all our syntax contains sub as an explicit term-former, and it contains unknowns so that sub cannot always be completely eliminated. Also, we consider single substitutions and not simultaneous substitutions, so that the order of substitutions matters. Perhaps that all makes enough of a difference that reductions could cycle or diverge in some way?
In fact reductions in SIMPr are extremely well-behaved. We show strong normalisation by a standard method: define a well-founded measure on terms and show that rewrites reduce it.
For a term let be inductively defined by:
For terms [] we have
For all terms and permutations :
1. 0.
2. . As a corollary, if ∆ then
Both parts can be proven by a simple induction on the structure of . The corollary follows by Corollary 2.32 which states that and are renamed versions of each other by means of permutations.
For terms and term-formers f sub:
1. []
2. []
3. f()[]f([][]) (f sub).
4. ([])[][]([]).
By straightforward calculations using the measure on terms. The last part uses the fact 0 (Lemma 5.26 above).
For terms and term-formers f:
1. If
2. If
Again by straightforward calculations. The last part uses the fact that 0 when f sub.
SIMPr is strongly normalising.
It suffices to show that if ∆ then
Suppose ∆ is derived using ( []) or ( f); then the result follows by Lemma 5.28 and the inductive hypothesis.
Suppose ∆ is derived using ( rew); then for each SIMPr rewrite rule of the form from Figure 10 we have, for some and ,
and and
By part 2 of Lemma 5.26, and . So in order to show that
We have already given an algorithm to compute normal forms on closed terms in Definition 4.4:
If is closed then is a SIMPr-normal form of with respect to any ∆.
By an induction on the structure of .
SIMPr-normal forms are unique up to equality in CORE.
Let ∆be a freshness context and be a term. By Theorem 5.29 has a normal form, say , with respect to ∆. Now suppose is also a normal form of with respect to ∆. Then ∆ and ∆ . By confluence (Theorem 5.16) there exists a term such that ∆ and ∆ . Since and do not have any rewrites ∆ and ∆ by Lemma 5.4. Using (symm) and (tran) we conclude ∆ .
As a corollary we obtain decidability of theory SIMP:
It is decidable whether or not ∆ .
Given ∆, and the following procedure decides whether ∆ is derivable:
1. Rewrite and to SIMPr-normal forms and with respect to ∆; by Theorem 5.29 these exist and by Theorem 5.31 they are unique up to equality in CORE.
2. Check whether ∆ using the syntactic criteria of Corollary 2.32.
then return ‘true’, otherwise return ‘false’.
6. Substitution on open terms using SUB
In this section we focus on theory SUB from Figure 1. We show that it is decidable and complete with respect to the ground term model by relating it to theory SIMP.
The theory of substitution SUB is the equality relation obtained by the rules of nominal algebra with the axioms in Figure 1. Here f ranges over all term-formers, including sub.
As an example, we show that our standard properties of capture-avoiding substitution are all derivable in SUB.
The following judgements are derivable in SUB:
1.
2.
3.
4.
Parts 2 and 3 are direct from (ren) and (#). For the other two parts we give nominal algebra derivations in the theory SUB.
Derivation for part 1:
In the above derivation of [, the superscript number one 1 is an annotation associating the instance of the rule (fr) with the assumption it discharges in the derivation. This is standard natural deduction notation.
For the derivation of part 4, we write for [] and we use the unsugared syntax for the other substitutions.
We conjecture that it is not possible to derive [ without (fr).
6.1. Soundness and the relation to SIMP
SUB can do everything that SIMP can:
then ∆ .
All the axioms of SIMP are also axioms of SUB, except for (b). However an instance of (b) is also an instance of (#). Therefore any SIMP derivation is also a SUB derivation. The result follows.
We now show that SIMP can do everything that SUB can — provided that the terms are closed. We need a technical lemma:
If , and are closed, then:
1. sub()[ sub([][]).
2. If # then
We consider the parts in turn:
1. Since by Theorem 4.6, the proof obligation is equivalent to
Now is of the form [] or [], where is a ground term. We only consider the case of , the case of is completely analogous. Take fresh such that # and #. Then
Since #, ([]() )[]((() )[]) by axiom (abs), so the proof obligation is equivalent to sub([]() )[ sub([]((() )[])[]). Or, using sugar:
And this is just an instance of part 4 of Corollary 4.7, since #.
2. We must show
by (tran). By (cong[]), []([]() follows from [) . By Corollary 4.7, this is when #. By (perm) and the rules for freshness also []() ] when #. By Lemma 2.21, this is when #[]. Since [], this follows from the assumption # by Lemma 4.5.
On closed terms, SUB is equivalent to SIMP:
For closed terms :
The right-to-left part follows by Lemma 6.3.
For the left-to-right part, we must show that SIMP can simulate the axioms of SUB on closed terms. Axioms (var), (abs) and (f), for f sub, are also present in SIMP. Each instance of axiom (f), where f sub, is an instance of part 1 of Lemma 6.4. Instances of axioms (ren) and (#) are instances of parts 2 and 3 of Corollary 4.7. Finally, each instance of () is an instance of part 2 of Lemma 6.4.
To recap, SIMP is sound for a ground term model by Theorem 4.3, equality in SIMP is decidable by Theorem 5.32, but not complete by the Theorem 5.24.
We now build the tools to prove that SUB is sound, decidable — and also complete for the ground term model. For soundness we have already done all the hard work:
SUB is sound for the ground term model. That is: then for all ∆-consistent closing substitutions (for ∆, and ).
Since ∆ and is ∆-consistent, we obtain by Theorem 2.37. and are closed so by Lemma 6.5 . By Corollary 5.20 we obtain . We conclude by Theorem 3.9, since and are ground.
6.2. Decidability
In this subsection we will establish that equality in SUB is decidable. We do this by transforming the problem of deciding whether a derivation of ∆ exists, into the problem of deciding whether a derivation of exists, for some carefully-chosen closed terms and in an extended signature (to be precise: in a correspondingly extended theory with extra (f) axioms for the extra term-formers). We can then exploit decidability of SIMP (Theorem 5.32), and conclude that SUB is decidable. The rest of this subsection makes this formal.
Fix some substitution signature , and fix ∆, , and where and are terms in . Let be the atoms mentioned anywhere in ∆, , or . Let be the unknowns mentioned anywhere in ∆, , or . For each pick the following data:
Choose an order on the atoms in such that #
Choose some fresh term-former : () (so does not occur in ) with arguments.
Choose some entirely fresh atom when : [].
Write : [], write , and let be the signature .
Define a substitution by:
A few words on Definition 6.8 may be useful. Substitution maps possibly open terms in mentioning unknowns in , to closed terms in . We design () to be a closed term which mentions unabstracted those atoms that ∆cannot prove are fresh for . The term-formers from help us to create a syntax in which to write these terms. The atoms from help us, where necessary, to place them in the right sort — since according to our sorting system, and consistent with [UPG04], only abstraction can create terms of abstraction sort. We think of d and as tags.
Call a closed term in -tagged when for each : [] all occurrences of and are restricted to subterms []() where the are also -tagged.
is ∆-consistent:
is derivable.
For each # ∆, we need to show #
Suppose # ∆and : . We must prove #(). By construction # ∆for 1 , so , and the result follows.
The case of : [] is similar.
Now it is not hard to show that preserves derivability:
then .
Suppose ∆ in the syntax of . Then also ∆ in the syntax of , since . We obtain by Theorem 2.37, using Lemma 6.10. We conclude by Lemma 6.5.
Recall that we fixed ∆, , and . Since and mention only unknowns from , and are closed terms. Then by Lemma 5.30, and are the SIMPr-normal forms of and .
Let be the set of all atoms mentioned anywhere in the chain of SIMPr-reductions
extended with a set of fresh atoms such that in bijection with . Let ∆ enriched with freshness assumptions # for every and every .
Without loss of generality we may assume that all terms occurring in the above chains of rewrites are -tagged, since the atoms from that occur in and are chosen completely fresh (by Definition 6.7), so when rewriting and to normal form it is not necessary to perform -renamings on these atoms.
We let and range over closed -tagged terms in mentioning only atoms in . The importance of these terms is that they include all of the and in the two chains of SIMPr-reductions mentioned above.
Define an inverse translation from closed -tagged terms in to terms in , inductively as follows, where we omit between compositions of swappings for brevity:
As a first result, we show that -1 really is the inverse of :
()-1 , and ∆ ()-1 .
We prove by induction that if is a subterm of or then ∆ ()-1 .
The only interesting case is when . When : , we must show
Take ()) (())() (). Then the proof obligation follows from
by (ren), since
for all . We can see this as follows: it suffices to show
since the () are pairwise disjoint and by using the rules for freshnesses. Then there are two possibilities:
() for all : then ()# since ()#
( for some : then # by definition.
The remaining proof obligation is
It is convenient to show the stronger property ∆. By the syntactic criteria of Corollary 2.32 it suffices to show that ∆ ds()#. That is, we must show that ∆ ds()# for every such that () (). We consider every possible (every and ):
: then # by definition, and the result follows.
: then (() and there is nothing to prove.
(): then we distinguish two cases:
– if ( for some , the result follows by the case of ;
– if () for all , then ()# by definition.
, but for all , then # by definition.
The case of : [] is similar except that we additionally need to prove that
This follows by axiom (), since ∆#.
The reader might wonder why the inverse mapping of the renames the atoms to the fresh . Consider for example () in the empty freshness context , so we do not know # or #. Then
By calculations we can verify Lemma 6.14:
where ## #. Had we left out the renaming to fresh atoms then ((() ))-1 would be [][], which is not equal to () , since for example
We now build up towards Theorem 6.20, which is our main result. Recall from Definition 6.13 that and are closed -tagged terms in the signature of mentioning only atoms in .
For any , if # then ∆#.
By induction on the structure of . We treat the hardest case, namely that of [](). We must show
where ) (). We distinguish three cases:
: then the result trivially follows by (#ab).
for some : then #[](()[] []) by (#[]a), and the result follows by the rules of freshness using the inductive hypothesis.
for all and : then () for all , so ()# by definition. The result follows using the rules for freshness and the inductive hypothesis.
()-1 when mentions only atoms from ().
By induction on the structure of . In the case of []() we use the fact that ( for all and ( for all .
If then ∆ .
By induction on the structure of , using the syntactic criteria of Corollary 2.32. The only non-trivial case is when
By Lemma 6.16 we obtain ∆#, and by the inductive hypothesis ∆ (() )-1 .
We now prove that:
and : Suppose for some . Now is -tagged so [](). We have assumed that so by the syntactic criteria of Corollary 2.32 it must be that []() (and for 1 ). This is impossible because . We deduce that in a similar manner.
and : By our assumption in Definition 6.13.
By Lemma 6.17 we obtain ∆ (() )-1 ) .
By standard reasoning using the rules for freshness and equality we conclude ∆
If then ∆ .
We work by induction on the derivation of to show that ∆ is derivable.
If the derivation concludes in ([]) or (f) we may use the inductive hypothesis and extend the derivation with (cong[]) or (congf) respectively.
Suppose the derivation concludes in (rew). Then there are various cases depending on which rewrite rule is used:
(Rvar). [ is derivable using axiom (var).
(Rb). [ is derivable using axiom (#), since ∆#.
(Rf), f . f()[ f([][]) is derivable using axiom (f).
(Rf), f . In case : , we must show
where ) (). Since for all , we know #. Then also ∆# by Lemma 6.16. Now we apply part 4 of Lemma 6.2, such that the left-hand-side of the proof obligation is SUB-equal to
By the rules for equality, this is equal to the right-hand-side of the proof obligation when
By axiom (#) this is when ∆#, i.e. when ()#. There are two possibilities:
– for some : then (, and # by definition.
– for all : then (, and # by definition.
The result follows.
The case of : [] is similar.
(Rabs). Suppose #. Then ∆# by Lemma 6.16. By (), we obtain
as required.
The result follows.
if and only if .
The left-to-right part is Theorem 6.11.
For the right-to-left part, suppose that . We have observed that there are SIMPr rewrites
and
Then by Lemma 6.19, we know
() ()-1 and () ()
()-1 )-1 and ∆ ()-1 )-1 by transitivity.
We supposed that so by Corollary 5.20 it must be that . By Lemma 6.18 also ()-1 )-1.
Then ∆ ()-1 )-1 using symmetry and transitivity. By Lemma 6.14 then also ∆. Since ∆ extends ∆with atoms not in , we conclude ∆ using (fr).
As a simple corollary of Theorem 6.20, we obtain decidability of SUB.
It is decidable whether ∆ .
By Theorem 6.20 is equivalent to . By Theorem 5.32, this is decidable.
Combining Theorem 6.20 and Corollary 5.20, we extract the following algorithm that decides whether :
1. Map possibly open terms and to closed terms and .
2. Evaluate and .
3. Check whether using the syntactic criteria of Corollary 2.32.
We can extract a witnessing derivation in SUB from the algorithm above: the meat of work is done in the proofs of Lemma 6.19 and Lemma 6.14.
By a similar method to the one we used to prove Theorem 6.20 we can prove conservativity of SUB over CORE. We use the notation and machinery of this subsection in the following proof:
Suppose that and do not mention term-former sub. Then
if and only if
A derivation in CORE is also a derivation in SUB so the right-to-left implication is immediate.
Now suppose that ∆ . We take a suitably chosen enriched signature and suitably chosen , as in the proofs above. By Theorem 6.11, . By construction and do not mention sub, therefore by Corollary 5.19 also .
Given the derivability of we can prove the derivability of ∆ by exploiting the syntactic criteria of Corollary 2.32. The proof is by induction on using detailed but entirely routine calculations. We consider just one case, the hardest one:
Suppose and : []. Then
By the syntactic criteria of Corollary 2.32 if it must be that
Here is not equal to () for 1 . By the construction of and the way we chose to be the atoms mentioned in ∆, , or which are not provably fresh for in ∆, it follows that must have been equal to for some such that ∆ ds()#. It follows that ∆ as required.
6.3. -completeness
We consider completeness with respect to the ground term model (see Definition 6.23 below for a formal definition). This is also called -completeness. Before we go into the proof of -completeness, it is useful to mention why this is an appropriate notion to consider.
Nominal algebra enjoys a general completeness result [GM07] with respect to a standard class of semantics in nominal sets [GP02]. SUB is a nominal algebra theory, so it is automatically sound and complete with respect to the standard class of nominal sets semantics.
A completeness result is weaker, the larger the class of semantics that it uses. Can we strengthen this general result to some more specific class than the nominal sets models?
Theorem 6.20 can be read as a completeness result with respect to a class of models built out of syntax enriched with finitely but unboundedly many extra term-formers . We could stop there, however, we would have an even more powerful completeness result if we could strengthen this to completeness with respect to terms of substitution signature itself.
In fact, so long as contains a term-former which takes more than one argument (like app or plus), then we can nail SUB down to the theory of capture-avoiding substitution on ground terms of . We now have all the machinery we need to do this quite easily:
Call a ground substitution for ∆, and when for every unknown , and , () is a ground term (it mentions no unknowns and does not mention sub).
Call SUB -complete when for all ∆, and , if for all ∆-consistent ground substitutions (for ∆, and ), then ∆ .
We shall prove the contrapositive. Supposing ∆ , we will exhibit some ∆-consistent ground substitution such that .
We cannot use from Definition 6.8 because maps to an extended signature with extra term-formers . But we can use to construct another substitution with the right properties, as we now see.
Recall from the previous subsection the chain of rewrites
Note that and are ground.
Let be the set of all atoms mentioned in the above chains, let and range over closed terms in mentioning only atoms from , and choose atoms completely fresh from .
Assuming that contains a binary term-former, say pair : ()), define a translation - from closed terms in to closed terms in by:
It is not hard to verify the following properties:
1. () ().
2. if and only if .
3. if and only if .
Part 1 is by induction on the syntax of . For the case of sub(), we use the property that [][] (where , , and [] mention only atoms from ), which is easy to verify.
Part 2 is by induction on the syntax of , using the syntactic criteria from Corollary 2.32.
For part 3, by Corollary 5.20 it suffices to prove the equivalent
which follows by parts 1 and 2.
Define the substitution by:
It is a fact of the construction that maps every appearing in ∆, , or , to a ground term in . This is morally ‘the same’ as (), but we map each extra term-former to a collection of instances of pair.
If is a subterm of or is a subterm of , () ().
By an easy induction on the structure of .
if and only if (().
By Lemma 6.27 and part 3 of Lemma 6.25.
SUB is -complete.
We show that if ∆ then there exists a ∆-consistent ground substitution (for ∆, and ) such that .
Suppose ∆ . Then also by Theorem 6.20. Now (() by Corollary 6.28. Then we obtain () () by Theorem 3.9 and Corollary 5.20.
Now take . Since maps to ground terms in , the result follows.
6.4. Restricting the sort system
We now turn to our discussion in Subsection 2.1 on unknowns of abstraction sort [] and term-formers sub : ([][])[] (Remark 2.10). We mentioned that they are convenient, but not strictly necessary.
To see what precisely we mean by this, we consider a typical signature for languages with binding, namely that of the lambda calculus (see Examples 2.6 and 2.8).
Consider the following signature:
Let theory over this signature have axioms
Suppose SUB is the theory of substitution over the signature of the lambda calculus from Example 2.8. Then for any ∆, and (in this signature) not mentioning unknowns of sort [] or terms of sort [][]:
if and only if
For the right-to-left part it suffices to show that each axiom of can be derived in SUB. Both axiom (lam) and (sub) follow by an instance of (f) and (#), the other axioms of follow direclty from their corresponding axioms in SUB.
For the left-to-right part, suppose ∆ . Then also by Theorem 6.11. We observe that there are SIMPr rewrites
such that whenever a term of sort [][] is introduced by a rewrite, it is removed in the next step. More precisely, only an application of rewrite rule (Rf), where f lam, can introduce such a term, but we can always apply the (Rabs) rule to get rid of it.
We can use properties similar to Lemma 6.19 on these chains of rewrites to obtain derivations of
()-1 )-1 and ()-1 )
That is, we need one such property for direct rewrites and another one for two-step rewrites. The inverse translation never introduces unknowns of sort [] or terms of sort [][].
We also have ∆ ()-1 )-1 by Corollary 5.20, Lemma 6.18 and our assumption . Then ∆ ()-1 )-1 using (symm) and (tran). Using a property similar to Lemma 6.14 we obtain . We conclude ∆ using (fr).
The presentation of theory is somewhat more specific and longer than SUB, since we cannot use a meta-variable f to range over term-formers. For this reason we preferred SUB in this paper.
7. Related work and conclusions
Substitution underlies the quantifiers in predicate logics and the -binder of the -calculus . . . and lots more besides. Quantification and binding are central features of these systems. This paper discusses their common denominator, substitution.
Future work using nominal techniques seems likely to require an axiomatisation of substitution within the nominal style. This paper provides that, and proves a precise sense in which that axiomatisation can be considered the right one, namely soundness and completeness with respect to a canonical term model (Theorem 6.29). It also provides a precise sense in which that axiomatisation can be considered tractable, namely decidability of equality up to the axioms for substitution.
Crabbé [Cra04b, Cra04a] axiomatises substitution much like us and shares (in our terminology) atoms and freshness conditions. However, his axiomatisation is not capture-avoiding from the simple fact that he does not treat binding: ‘. . . we are not concerned with the notion of bound variable’ [Cra04a, page 2].
Feldman [Fel82] gives an algebraic axiomatisation inspired by a concrete model of functions/evaluations. His axioms are closer in spirit to Cylindric Algebras [BS81] and Lambda Abstraction Algebras [LS04, Sal00]. The three approaches share an infinity of term-formers which are ‘morally’ precisely [], -[ -], and We see the advantage of our treatment as systematising and formalising precisely what rôle the atoms really have. In any case the approaches above cannot directly express (ren), (#), and (abs), even though instantiations are derivable for closed terms by calculations parametric over their specific structure.
Combinatory Algebra (CA) [Bar84] and related systems implement substitution by ‘pipes’ (e.g. the translation of -terms into CA [Bar84]). There is no native notion of binder, nor of capture-avoidance. General truths such as (#) are not provable as equalities between combinators, though they remain true and can be proved informally by calculations parametric over specific structure.
Lescanne’s classic survey [Les94] and the thesis of Bloo [Blo97] chart a vast literature on -calculi with explicit substitutions. These decompose -reduction as a rule to introduce explicit substitution ( () [] ), and explicit rules for that substitution’s subsequent behaviour (which is to substitute, of course). These calculi are designed to measure the cost of a -reduction (in an implementation, which may be based on de Bruijn indexes [dB72] or on named variable symbols). They do not axiomatise substitution, they implement it. For example, ‘confluence’ is a typical correctness criterion for a calculus, and ‘-completeness’ is not.
Sun has investigated Binding Algebras [Sun99]. As far as we understand, binding algebras implement binding in the style of higher-order or first-order logic — using variables and binders — but without committing to a functional semantics or to higher orders. Put another way, binding algebra enriches the language of algebra with binding, substitution, and -conversion — but leaves out -abstraction and -conversion. (This has much in common with Binding Logic [DHK02], which does something very similar to first-order logic; neither thread of research cites the other so they appear to have developed independently.)
Nominal algebra is in this spirit. In fact it does not commit to substitution, but by design SUB does and SUB is the topic of this paper. We note that in Sun’s work that every variable must be explicitly accounted for in some binder or some evaluation, some where. That is, variables have no independent denotational existence analogous to that of the atoms in nominal sets. Our best guess is that binding algebras correspond, in our world, to elements with empty support of models of SUB. We do not intend to investigate a connection with binding algebra but we do plan to consider binding logic.
There is a close connection between nominal sets [GP02] and categories of presheaves used in another thread of work [FT01, FPT99, TP05]. This uses ideas from categorical algebra [LS86] and applies presheaves to give just enough extra structure to model names and name-binding. Nominal sets, the canonical semantics for nominal terms, are the Schanuel topos; they can be viewed as a category of pullback-preserving presheaves. Being pullback-preserving (to be more precise, preserving pullbacks of pairs of monos) does not correspond to having finite support — it corresponds, in the terminology of nominal techniques, to assuming a unique least supporting set. This is not a vital assumption, but without a unique least supporting set, the freshness judgement # of nominal terms is meaningless in its current form. It is not clear how [FT01, FPT99, TP05] would give a direct semantics to nominal terms. Thus an easy and direct connection cannot be made at the moment.
A direct connection could be made by relating the general class of models of substitution determined by SUB (which we do not consider in this paper) with the classes of models in presheaves — or alternatively, if the work based on presheaves could include a completeness result for some canonical model (which to our knowledge has not yet been done); this could then be conveniently compared to the ground term model of SUB. Since our models would be in nominal sets and would have unique least supporting sets, and the presheaf models do not, our best guess is that a canonical model for the presheaf work, if it exists, would be a ‘ground term model enriched with non-unique least supporting sets’. It remains to make that formal, and non-syntactic models of SUB remain to be investigated.
There is much possible and interesting future work:
Decidability of unification up to SUB, the axioms for substitution, remains an open problem. Nominal unification [UPG04] (in our terminology, unification of nominal terms up to CORE) is decidable. Nominal unification is to be compared with higher-order patterns [Mil91]. We suggest that unification up to SUB is to be compared with higher-order unification [Hue02], and the technique of Huet’s algorithm could perhaps be imported.
There is no obstacle to taking SUB over itself — that is, to taking what we write in this paper as, say, ([])[] and expressing it in a stronger axiom system as ([])[] where is a ‘stronger’ meta-variable. This relates directly to the Lambda-Context Calculus [GL07] and Hierarchical Nominal Rewriting [Gab07] both of which feature hierarchies of ‘increasingly meta-’variables plus operational notions of semantics for substituting those variables.
Finally, SUB is just an axiom system and it has interesting non-syntactic models. Exploring them is current research, and we hope it will be possible to exploit those models to design interesting new classes of logics and lambda-calculi.
References
[Bar84]H.P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, Amsterdam, 1984.
[Blo97]Roel Bloo. Preservation of Termination for Explicit Substitution. PhD thesis, Eindhoven University of Technology, Eindhoven, 1997.
[BR95]Roel Bloo and Kristoffer Høgsbro Rose. Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection. In CSN-95: Computing Science in the Netherlands, pages 62–72, Amsterdam, 1995. Stichting Mathematisch Centrum.
[BS81]S. Burris and H. Sankappanavar. A Course in Universal Algebra. Springer, Berlin, 1981.
[Cra04a]Marcel Crabbé. On the notion of substitution. Logic Journal of the IGPL, 12(2):111–124, 2004.
[Cra04b]Marcel Crabbé. Une axiomatisation de la substitution. Comptes rendus de l’Académie des Sciences de Paris, Série I, 338:433–436, 2004.
[dB72]N.G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagationes Mathematicae, 5(34):381–392, 1972.
[DHK02]Gilles Dowek, Thérèse Hardin, and Claude Kirchner. Binding logic: proofs and models. In LPAR’02: 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, volume 2514 of LNCS, pages 130–144, Berlin, 2002. Springer.
[Fel82]Norman Feldman. Axiomatization of polynomial substitution algebras. Journal of Symbolic Logic, 47(3):481–492, 1982.
[FG07]Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205:917–965, 2007.
[FPT99]Marcelo Fiore, Gordon Plotkin, and Daniele Turi. Abstract syntax and variable binding. In 14th Annual Symposium on Logic in Computer Science, pages 193–202, Brussels, 1999. IEEE Computer Society Press.
[FT01]Marcelo Fiore and Daniele Turi. Semantics of name and value passing. In 16th Annual Symposium on Logic in Computer Science, pages 93–104, Los Alamitos, 2001. IEEE Computer Society Press.
[Gab07]Murdoch J. Gabbay. Hierarchical nominal terms and their theory of rewriting. ENTCS, 174(5):37–52, 2007.
[GL07]Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. In LFMTP’07: International Workshop on Logical Frameworks and Meta-Languages, to be published in ENTCS, 2007.
[GM06a]Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding substitution as a nominal algebra. In Theoretical Aspects of Computing: ICTAC 2006, volume 4281 of LNCS, pages 198–212, Berlin, 2006. Springer.
[GM06b]Murdoch J. Gabbay and Aad Mathijssen. Nominal algebra. Technical Report HW-MACS-TR-0045, Heriot-Watt, 2006.
[GM06c]Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order logic. In PPDP’06: Proc. of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, pages 189–200, New York, 2006. ACM Press.
[GM07]Murdoch J. Gabbay and Aad Mathijssen. A formal calculus for informal equality with binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of LNCS, pages 162–176, Berlin, 2007. Springer.
[GP02]Murdoch J. Gabbay and Andrew M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2002.
[Hod01]Wilfrid Hodges. Elementary predicate logic. In D.M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer Academic, Dordrecht, 2001.
[Hue02]Gérard Huet. Higher order unification 30 years later. In TPHOLs 2002: Theorem Proving in Higher Order Logics, number 2410 in LNCS, pages 241–258, Berlin, 2002. Springer.
[KvOvR93] Jan Willem Klop, Vincent van Oostrom, and Femke van Raamsdonk. Combinatory reduction systems, introduction and survey. Theoretical Computer Science, 121:279–308, 1993.
[Les94]Pierre Lescanne. From to a journey through calculi of explicit substitutions. In POPL’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 60–69, New York, 1994. ACM Press.
[LS86]J. Lambek and P.J. Scott. Introduction to Higher Order Categorical Logic. Cambridge University Press, Cambridge, 1986.
[LS04]Stefania Lusin and Antonino Salibra. The lattice of lambda theories. Journal of Logic and Computation, 14(3):373–394, 2004.
[Mil91]Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Extensions of Logic Programming, 475:253–281, 1991.
[MN98]Richard Mayr and Tobias Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
[Sal00]Antonino Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.
[Sun99]Yong Sun. An algebraic generalization of Frege structures - binding algebras. Theoretical Computer Science, 211:189–232, 1999.
[TP05]Miki Tanaka and John Power. A unified category-theoretic formulation of typed binding signatures. In MERLIN’05: Proc. of the ACM SIGPLAN workshop on mechanized reasoning about languages with variable binding, pages 13–24, New York, 2005. ACM Press.
[UPG04]Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
Notes
1 Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands ↩
Correspondence and offprint requests to: Murdoch J. Gabbay, www.gabbay.org.uk