Capture-Avoiding Substitution as a Nominal Algebra
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 turn out to be hard and 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.
Table of Contents
Capture-Avoiding Substitution as a Nominal Algebra 1
Murdoch J. Gabbay and Aad Mathijssen
1 Introduction. 3
1.1 Answers to questions and map of the paper 4
1.2 Relation with the conference version 5
2 Nominal algebra 5
2.1 The syntax of nominal terms. 5
2.2 Permutation, substitution and freshness 8
2.3 Equality 12
2.4 Axioms and theories 13
3 Equality and inequality of raw nominal terms. 15
4 Substitution on ground terms. 18
5 The theory SIMP; simply substitution 24
6 Substitution on open terms using SIMP 28
6.1 Nominal rewriting 28
6.2 SIMPr: explicit substitution rewritten 31
6.3 Confluence, conservativity and consistency 32
6.4 Failure of completeness for SIMP with respect to unknowns. 34
6.5 Strong normalisation and decidability 34
7 Substitution on open terms using SUB 36
7.1 Soundness and the relation with SIMP 37
7.2 Decidability 39
7.3 -completeness . 45
7.4 Restricting the sort system 47
8 Related work and conclusions. 48
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 [1].
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 (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 holds ( 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 [2], though sub is not atoms-concretion. More on this in Subsection 1.2.
Formally, Figure 1 uses nominal terms [3] as a syntax, and nominal algebra [4, 5] 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 considers -equality and -inequality of nominal terms. Section 4 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 5 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 6 proves useful properties of the simple axiomatisation; here we make heavy use of techniques from (nominal) rewriting.
Section 7 explores the stronger axioms (Figure 1) formally as a nominal algebra theory. Decidability of the stronger axioms is proved in Subsection 7.2, and completeness is proved in Subsection 7.3 relative to the concrete model from section 4. This answers question (2) above and completes the proof that Figure 1 does represent substitution. Finally, Subsection 7.4 shows how the general axiomatisation of SUB relates to a more concrete axiomatisation.
In other work in preparation, the first author shows how Fraenkel-Mostowski set theory (the underlying model of nominal techniques) [2] 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 [4, 6] 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 [7]. 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 6.25. SIMP can be identified with the usual definition of capture-avoiding substitution.
We give a procedure for converting equalities SUB into equivalent (in a suitable sense) equalities in SIMP over an extended signature (see Subsection 7.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 7.3). In fact () is only necessary if we admit unknowns of abstraction sort [] (using terminology from the rest of this paper, or from [7]). 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 Remark 2.9 and Subsection 7.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 [3, 8].
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 [6]) 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 .3 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 an arity () is associated. We may write f : () for f which has arity (). We call a collection of term-formers a signature.
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. 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:
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:
– it contains two term-formers sub, one with arity ([]), and one with arity ([][])[];
– for any other term-former f , 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 term-former sub : ([][])[], are convenient but not necessary; see in Subsection 7.4.
The signature is arbitrary and may be empty (aside from sub), except that Theorem 7.27 (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 7.18 (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.
A permutation is a 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 [3, 8]:
().
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 for a (possibly infinite) set of primitive freshnesses and call it a freshness context.
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 [9] by the rules in Figure 2. Here:
– and permutatively range over atoms, i.e. and represent any two distinct atoms;
– ranges over non-empty permutations, i.e. Id.4
– 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.
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 #.
For example, in the substitution signature for the lambda calculus (Example 2.7), we have #lam([]) and ##app( lam([])):
The derivation rules are completely syntax-directed. This implies that the rules also hold in the opposite direction:
1. If # then #.
2. If # then ()#.
3. If #[] then #.
4. If #f() then #, for all , 1 .
By an easy induction on the structure of the derivation rules in Figure 2.
In freshness judgements, the freshnesses context may be weakened:
If # and then #.
By an easy induction on the structure of the derivation rules.
Sometimes the freshness contexts may also be strengthened. We need some terminology in order to state this.
Let and be freshness contexts, and be a set of terms. Say that freshly extends with atoms not in when and for each #. If is empty we just say that freshly extends .
For example:
– ## freshly extends #.
– ## freshly extends # with atoms not in .
– ## does not freshly extend # with atoms not in .
– ## does not freshly extend #.
If # and freshly extends with atoms not in , then #.
We inductively transform a derivation of # to a derivation of #:
– If # by assumption, then #. We proceed by case distinction:
If #, then # by assumption.
If #, then , so # does not freshly extend with respect to and there is nothing to prove.
– (#X): Suppose #, Id, is derived using (#X) and freshly extends with atoms not in . Then ()# by assumption and freshly extends with atoms not in . By the inductive hypothesis ()#, and by (#X) we conclude #.
– (#ab) and (#[]a) carry over directly.
– (#[]b) and (#f) are straightforward using the inductive hypothesis and the facts that [] implies and that f() implies for all .
We can generalise the permutation of terms to freshnesses as follows:
If # then ()#.
By an easy induction on freshness derivations (Figure 2). The only non-trivial case is (#X). Suppose # is derived from ()# using (#X), where Id. Then we need to show ()# (). By Lemma 2.13, this is equivalent to ()#() .
We continue by case distinction. Suppose Id. Then the proof obligation is equivalent to the assumption ()#, since by basic properties of permutations.5 The result follows.
If Id by (#X) the proof obligation follows from ()-1(())#. Since ()-1(((), this is equivalent to the assumption ()#, and again the result follows.
Write for #
Note that is not usually a freshness context unless is an unknown for each #.
We can generalise substitution of terms to freshnesses as follows:
For any , , if # 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.24.
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 .6 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 (perm) read () as ‘swap and in ’. This single rule expresses -equivalence. To provide some intuition, here are some examples on closed terms.
–
(Note here that [] ()
– In the substitution signature of the lambda calculus (Example 2.7),
is derivable: since [][]app() () [][]app() it suffices to show
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.
#[) )[]
In Section 3 we will prove that derivability in CORE is -equivalence in a formal sense, also on open terms.
2.4 Axioms and theories
Nominal Algebra is the theory of freshness and equality outlined above, along with the ability to impose axioms on terms:
Call a triple where is a finite freshness context, an axiom. We may write when 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 4. 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.24: iff 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. For instance we can weaken the freshnesses context in equational judgments:
If and then .
By an easy induction on the structure of the derivation rules.
We may strengthen the freshness context , since the rule (fr) precisely introduces a ‘ freshly extending with atoms not in ’ in equational derivations:
If and freshly extends with atoms not in , then .
We extend the derivation with (fr).
Also we may permute atoms and instantiate unknowns in equational derivations:
For any , if then .
For any , , if and then .
Analogous to the proof of Theorem 2.26.
3 Equality and inequality of raw nominal terms
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 3.5).
– We need to prove that CORE captures -equivalence (and no more than -equivalence; see Theorem 4.13).
– 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 [3] (we still need nominal algebra so we can extend CORE and study theories with more axioms, like SUB).
The following definition was introduced in [3, Figure 2]; the proofs are modelled on a method presented in [8, 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 5. 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().
Syntax-directed equality is transitive:
If and then .
By induction on the size of (we do not count permutations in the size). For each we exploit the syntax-directed nature of the rules of Figure 5 to determine the possibilities for and .
For the abstraction case
– If then . This follows by induction on the structure of derivations of .
– If ds()# then . By induction on the structure of .
– If then # if and only if #. By induction on the structure of .
Full details can be found in the proof of [8, Lemma 23(2)].
We use Lemma 3.2 to show that CORE is equivalent to the syntax-directed equality of Figure 5.
if and only if is derivable in the sequent system for CORE.
The left-to-right direction is by routine induction on the structure of Nominal algebra derivations of . By the inductive hypothesis it suffices to show:
– (is derivable). This follows by an easy induction on the structure of .
– If then . By induction on derivations of . Except for (Absab), all cases are trivial using the inductive hypothesis, since they are symmetric. For the remaining case, we need to show [] []. By Lemma 3.2, this follows from
By (Absaa) [] []() follows from () ; by the inductive hypothesis this follows from the assumption () . By (Absab) []()
– If and then . This is Lemma 3.2.
– If then []
– If then f() f(). This is an instance of (F), using the fact that for all .
– if # then () . By an easy induction on the structure of .
– if where then . By an easy induction the structure of derivations of . The case of (Absab) uses Lemma 2.23 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).
– If 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 following proof obligations remain:
1.
This condition is satisfied since ds( (
2. ()# follows from (())# by Lemma 2.24. This follows from assumptions ds()#, if (()) ds(). That is, when (((())) (). This is the case, since we assumed () and because ≠ is invariant under permutation.
3. ()# follows from #, by Lemma 2.24. This follows directly from assumption ds()#, since ds().
– If for , 1 , then f( f(). Using a number of instances of (tran) and (congf).
– If then
– If () and # then
As direct corollaries of Theorem 3.3, 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()# (that is, # for every such that () ).
3.
4.
5. f() and f() and for , 1 .
By Theorem 3.3 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 3.4, is never derivable.
A technical corollary will also be useful later and has a simple proof using Corollary 3.4:
If then # if and only if #.
By an easy induction on using concrete calculations and the syntactic criteria of Corollary 3.4.
4 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 .
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 by:
where f ranges over all term-formers excluding sub. By ‘ fresh’ we mean that is chosen such that fa
Note that we will not mention anymore, since this is enforced by our permutative convention (see Definition 2.18.)
Let the size of a ground term be inductively defined by:
We will often use the fact that on ground terms capture-avoiding substitution of atoms for atoms preserves size, i.e. []
We will use the following simple properties relating freshness and capture-avoiding substitution on ground terms:
For ground terms , fa([]) (fa) fa
By induction on the size of . In the calculations we indicate uses of the inductive hypothesis with a superscript IH . We consider the three more interesting cases in turn:
–
which is trivial.
–
–
which we calculate as follows:
In the first application of the inductive hypothesis above, we use the fact that [].
For ground terms :
1. If # then #[].
2. If # and # then #[].
Lemma 4.8 states familiar properties of ground terms — but are they true? Lemma 4.8 makes the vital connection between ‘substitution as we know it’ and the nominal technology we bring to bear on it. We give proofs in some detail. They run smoothly, and this fact is encouraging evidence that our definitions are appropriate:
For ground terms , , :
1. Identity. [.
2. Swapping. If # then [) .
3. Garbage collection. If # then [.
4. Distributivity. If # then [][[][[]].
Part 1 follows from the stronger property that [] . We prove that by an easy induction on which we omit.
We show part 2 by induction on the size of . Most cases are easy; the interesting ones are:
–
–
By (symm) and the syntactic criteria of Corollary 3.4, this happens when
We consider each part in turn. Since fa(), we know #() by Lemmas 2.24 and 4.3. To prove [][) () it suffices to show that
by (tran). Now [] so we use the inductive hypothesis to deduce
from #[], which follows by Lemma 4.7. We deduce () [) () from [) using Lemma 2.34. We assumed fa() so by Lemma 4.3 also #. We use the inductive hypothesis.
–
This follows directly from the inductive hypothesis using (cong[]).
We show part 3 by induction on the size of using the syntactic criteria of Corollary 3.4. The only interesting case is when
By (perm), []() ] follows from #[] and #[], which follow from assumption fa() by the rules for freshness and Lemma 4.3. By (cong[]) and (tran), []([][]() follows from
By the inductive hypothesis, [][[] follows from #[], which follows from assumption #[] by Lemmas 4.7 and 2.20. Finally, [) is an instance of part 2 of this lemma, since #.
We can prove part 4 by induction on the size of , using parts 2 and 3 and congruence of capture-avoiding substitution on ground terms. We will only provide the congruence properties here.
For ground terms , , :
1. If then [[].
2. If then [[].
The proof of the first part is by induction on the size of , using the syntactic criteria of Corollary 3.4. We consider the two most interesting cases:
–
–
The proof of the second part is similar, but simpler.
We will now show how equality on ground terms in theory CORE coincides with a ‘standard’ definition of -equivalence.
Define an -equivalence relation inductively by the rules in Figure 6. Here ‘ fresh’ means any such that fa
Before we can relate CORE equality and =, we need to establish a few technical properties of =. Define a ‘bound atoms of’ function ba() on ground terms inductively as follows:
If ba and , then []([
Let . By a congruence rule from Figure 6, []([
Lemma 4.11 enables us to prove the =-equivalent of the (perm) rule.
If fa then () .
It is not hard to see that all instances of and in occur in the scope of abstractors [] and []. Traverse the structure of bottom-up, and use Lemma 4.11 to rename those abstractors so they are not or any more, but some completely fresh set of atoms — a different one for each instance of [] and []. Call the new term , then it is easy to show () , since . Now equality is symmetric, so we reverse the process to get back again.
Lemma 4.12 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 and are -equivalent.
For ground terms , , if and only if .
We prove the left-to-right implication by induction on the structure of , using the syntactic criteria of Corollary 3.4. The cases 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.
Suppose we have deduced []
by part 2 of Lemma 4.8. Using (symm), (tran) and (cong[]) we obtain
By (perm) []() ] and []() ], since # and #. Using (symm) and (tran) we conclude that
5 The theory SIMP; simply substitution
We introduce nominal algebra theory SIMP which is sound but not complete with respect to the ground terms model in Section 4. 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 , , if # then [.
We work by induction on the size of . We consider the cases in turn:
– . Then # and there is nothing to prove.
– . Then #. [ by axiom (b).
–
By (abs) also
since #. Since #() , we know (() )[) by the inductive hypothesis (() has the same size as , and so is smaller than []). Using (cong[]) and []() ] we obtain
We use (tran) to obtain ([])[], as required.
–
– f()[], f sub. By assumption #f(). Then # by Theorem 2.20 and [ by the inductive hypothesis, for all , 1 . Using (congf) and (tran) we obtain
By axiom (f)
We obtain f()[ f() by (tran), as required.
For ground terms , , [[].
By induction on the size of :
– . Then [ by axiom (var), and [] .
– . Then [ by axiom (b), and [] .
–
–
–
By axiom (abs ) also
since #. By the inductive hypothesis and (cong[])
Since [) by part 2 of Lemma 4.8, we deduce
using the rules of equality and Lemma 4.9. Using (tran) we put the pieces together to conclude
– f(), f sub. Then
by (f). By the inductive hypothesis [[] for all , 1 . Then by applications of (congf) and (tran) we obtain
Since f()[] f([][]), we are done.
On closed terms we can interpret all occurrences of term-former sub by capture-avoiding substitution.
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 . The interesting case is sub(). By assumption we know #sub(). By Lemma 2.20 also # and #. By the inductive hypothesis, #and #.
There are now two cases:
–
–
Note that the converse of Lemma 5.5 does not hold. Take[] for instance. Then #([]) since ([]). But #[], since #.
For any closed term , .
By induction on the structure of :
– . Then , and we conclude by (refl).
–
– f(), f sub. Then f() f(), and
(tran).
– sub(). Then sub()[] where []. By the inductive hypothesis,
By (congf) and (tran), we obtain
By Theorem 5.3 we know [[]. Now since []and [] sub(), this is syntactically equivalent to
By an application of (tran) we conclude sub( sub() as required.
As a corollary of Theorem 5.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 5.6 and Lemma 4.8.
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, is it not the case that there are two terms all of whose closed instances are equated by SIMP, but which are not themselves probably 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.
6 Substitution on open terms using SIMP
In this section we recall a notion of rewriting called nominal rewriting, which is tailored to nominal terms [8]. We will use nominal rewriting to prove properties on open terms of theory SIMP.
6.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 is a set of nominal rewrite rules. We tend to let R range over nominal rewrite systems.
A nominal rewrite system R determines a set of nominal rewrites inductively by the rules in Figure 8.
Write when is not derivable.
In Figure 8, f ranges over all term-formers of the signature of R (whatever that signature is). We dicuss each of the aspects of the (rew) in more detail:
– The permutation gives atoms in rules the character of ‘unknown atoms up to permutation’. Thus in the substitution signature of the lambda calculus (Example 2.7) extended with a term-former const : () the rewrite rule app() const generates, for example, rewrites
but not
because no can identify with .
– The substitution gives unknowns in rules the character of ‘unknown terms’. This is standard.
– The premise ensures that the instantiation is consistent. Note that we could also have used , which is equivalent to by Lemma 2.24.
– Finally, the use of equality in CORE gives abstractions []- the character of real abstractions. For example the rule lam([]lam([])) const generates rewrites
If a derivation exists of then that derivation mentions (rew) exactly once.
By an easy induction on derivations.
So 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 that position or occurs at inside . If the derivation tree has just one derivation rule in it then it must be an instance of (rew) for some rewrite rule R and we may say the rewrite occurs at root position and that matches at top level.
The following result is very easy to prove from the definition of rewriting:
If 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.
If a term does not have any rewrites, the transitive reflexive closure of R is precisely alpha-equivalence:
If there is no such that then
Suppose there is no such that . For the right-to-left direction, assume . By (refl) we obtain .
For the left-to-right direction, the proof obligation is equivalent to (swapping antecedents): If then if there is no such that then . We proceed by induction on derivations of . Suppose the derivation concludes in:
– (): then and there is nothing to prove, since there is a such that .
– (refl): then and we are done.
– (tran): then is derived from and for some . By the inductive hypothesis
if there is no such that then , and
if there is no such that then .
By assumption there is no such that , so . Using , it is easy to verify that there is no such that . So we also have . We conclude by (tran).
The result follows.
The transitive reflexive closure of R is a congruence:
The following rules are admissible:
We only give a proof for the case of ([]), the case of (f) is analogous. We work by induction on the derivation of :
– If the derivation concludes in () then it must be that is derived from . We extend the derivation of with ( []) and () to obtain one of
– If the derivation concludes in (refl) then we extend the derivation of with (cong[]) and (refl) to obtain
– If the derivation concludes in (tran) then it must be that is derived from and . So
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 .
Call a pair of nominal rewrites and a critical pair when at least one of the rewrites occurs at root position. If any of the two rewrites occurs at a moderated unknown inside , call the critical pair trivial.
Call a nominal rewrite rule uniform when # and imply # for all and . A rewrite rule is left-linear when each variable occurring in occurs only once. A uniform nominal rewrite system with only left-linear rules and no non-trivial critical pairs is orthogonal.
An orthogonal uniform nominal rewrite system is confluent.
See [8, Theorem 65].
6.2 SIMPr: explicit substitution rewritten
Let SIMPr be the nominal rewrite system defined in Figure 10.
A basic correctness result is this:
For possibly open , , 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). [ using axiom (b).
– (Rf). f()[ f([][]) using axiom (f).
– (Rabs). ([])[]([]) using (abs); the freshness side-condition is guaranteed by the identical side-condition on (abs).
The result follows.
For possibly open , , if then .
By induction on the structure of derivations of . The case of () uses Theorem 6.14, (refl) uses (refl), and (tran) uses (tran).
6.3 Confluence, conservativity and consistency
All rewrite rules of SIMPr are uniform.
For each rule, use appropriate instances of Lemma 2.20. 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.20:
– if or then #;
– if and then # and #.
Using these assumptions it is easy to show #[]([]) by case distinction on .
Note that SIMPr satisfies the even stronger property of being a closed nominal rewrite system [10, Section 4.2, Theorem 5.2]. However, Lemma 6.16 is enough to obtain Theorem 6.17 below.
SIMPr is confluent.
By Lemma 6.16 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 by Definition 6.11, SIMPr is orthogonal and uniform. Then by Theorem 6.12, SIMPr is confluent.
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
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 6.17 there is some term such that and . By assumption there can be no and such that and . Then and by Lemma 6.7, and we conclude by (tran).
Suppose that and do not mention the term-former sub. Then
This is an instance of Theorem 6.19, 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 5.4.
For closed terms and ,
is equivalent to by Theorem 5.6 and (tran). By Corollary 6.20 this is equivalent to .
For all there are and such that .
A corollary of Corollaries 6.20 and 3.5.
For the next result need some terminology.
Call a substitution closing for an unknown when is a closed term. Call closing for a term or a freshness context when it is closing for the unknowns in or , i.e. is closed for every or .
Say a closing is -consistent when , i.e. when # for all #.
Theorey SIMP is sound for the ground term model. That is: If then for all -consistent closing substitutions (for , and ).
by Theorem 2.35 and our assumption that . We obtain by Corollary 6.21, since and are closed. We conclude by Theorem 4.13, since and are ground.
6.4 Failure of completeness for SIMP with respect to unknowns.
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 4, we can easily check using the syntactic criteria of Corollary 3.4 that
Since [][] and [][[]] have no SIMPr rewrites with respect to #, we conclude
by Theorem 6.19.
The proofs of the other parts are similar.
The fact that above assertions are derivable for closing substitutions follows by Corollary 5.7.
Nominal algebra has a model theory and satisfies soundness and completeness [5, 4]. 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.
6.5 Strong normalisation and decidability
We expect the part of a -calculus that handles substitution to be terminating [11, 12] — 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.8
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 3.4 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 6.27 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 6.29 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 ,
By part 2 of Lemma 6.27, and . Then showing
We have already given an algorithm to compute normal forms:
If is closed then is a SIMPr normal form of .
By an easy induction on .
SIMPr-normal forms are unique up to equality in CORE.
Let be a freshness context and be a term. By Theorem 6.30 has a normal form, say , with respect to . Now suppose is also a normal form of with respect to . Then
By confluence (Theorem 6.17) there exists a term such that
Since and do not have any rewrites
by Lemma 6.7. Using (symm) and (tran) we conclude .
As a corollary we obtain decidability of theory SIMP:
It is decidable whether .
Given , and the following procedure decides whether is derivable from in SIMP:
1. Rewrite and to SIMPr-normal forms and with respect to ; by Theorem 6.30 these exist and by Theorem 6.32 they are unique up to equality in CORE.
2. Check whether using the syntactic criteria of Corollary 3.4.
3. If then return ‘true’, otherwise return ‘false’.
7 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.
For the derivation of part 4, we write for [] and we use the unsugared syntax for the other substitutions:
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.
We conjecture that it is not possible to derive [ without (fr).
7.1 Soundness and the relation with SIMP
SUB can do everything that SIMP can:
If 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 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 5.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
Also ([]() )[]((() )[]) by axiom (abs) and #, so the proof obligation is equivalent to
Or, using sugar:
But since #, this is just an instance of part 4 of Corollary 5.7, and we are done.
2. We must show
–
–
by (tran). By (cong[]), []([]() follows from [). By Corollary 5.7, this is when #. By (perm) and the rules for freshness also []() ] when #. By Lemma 2.20, this is when #[]. Since [], this follows from the assumption # by Lemma 5.5.
SIMP can do everything that SUB can — provided that the terms are closed:
If and are closed and then .
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 7.4. Instances of axioms (ren) and (#) are instances of parts 2 and 3 of Corollary 5.7. Finally, each instance of () is an instance of part 2 of Lemma 7.4.
To recap, SIMP is sound for a ground term model by Theorem 5.3, equality in SIMP is decidable by Theorem 6.33, but not complete by the Theorem 6.25.
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:
Theory SUB is sound for the ground term model. That is: If then for all -consistent closing substitutions (for , and ).
Since and is -consistent, we obtain by Theorem 2.35. and are closed so by Lemma 7.5 . By Corollary 6.21 we obtain . We conclude by Theorem 4.13, since and are ground.
7.2 Decidability
In this subsection we will establish that equality in SUB is decidable; we will show an algorithm exists which given , and a freshness context , decides whether is derivable.
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 6.33), and conclude that SUB is decidable. The rest of this section 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 entirely fresh atom .
– Choose some fresh term-former (so does not occur in ) with arguments.
Write , and let be the signature .
Define a substitution by:
Note that maps possibly open terms in mentioning unknowns in , to closed terms in . Then is -consistent:
is derivable.
For each #, we need to show #
Suppose # and : . We must prove #(). By construction #, so , and the result follows.
The case of : [] is similar.
Now it is not hard to show that preserves derivability:
If then .
Suppose in the syntax of . Then also in the syntax of , since . We obtain by Theorem 2.35, using Lemma 7.9. We conclude by Lemma 7.5.
Recall that we fixed , , and . Since and mention only unknowns from , and are closed terms. Then by Lemma 6.31, 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 new atom for each , and
– a set of new atoms in bijection with , write it such that . (Note that we choose atoms in distinct from all the chosen above.)
Let be enriched with freshness assumptions # for every and every .
We let and range over closed terms in mentioning only atoms in . Define an inverse translation from these closed terms in to terms in , inductively by:
(- sub((() () )[] []) (:[])
The importance of these terms is that they include all of the and in the two chains of SIMPr-reductions mentioned above.
As a first result, we show that -1 really is the inverse of :
()-1 , and ()-1 .
We prove that if is a subterm of or then ()-1 , by induction on .
The only interesting case is when . When : , we must show
SUB 1 1) ( ) )[1 (1)] [( )]
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 3.4 we need only 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 needs to rename the atoms to the fresh . We illustrate the reasons with an informal argument which can easily be made formal. Consider () , where we don’t know # or #. Then
By calculations we can verify Lemma 7.13:
is derivable in an appropriate freshness context. Had we left out the renaming to fresh atoms the result of ((() ))-1 would be [][], which is not equal to () , since for example
We now build up towards Theorem 7.18, which is our main result. Recall from Definition 7.12 that and are closed terms in the signature of mentioning only atoms in .
For any , if # then #.
By induction on the structure of . The only non-trivial case is when (). We treat the case of : , the case of : [] is similar. Suppose #(). Then # for all , by Lemma 2.20. By the inductive hypothesis, # . We must show
where ) (). We distinguish two cases:
– for some : then
by (#[]a). Now sub is just a term-former so
by (#f) and the inductive hypothesis for , and the result easily follows by the rules of freshness using the inductive hypothesis.
– for all : then () for all , and ()# by definition. The result follows using the rules for freshness and the inductive hypothesis.
If then .
By induction on the structure of , using the syntactic criteria of Corollary 3.4. The only non-trivial case is when
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 .
is derivable using axiom (f).
– (Rf), f . In case : , we must show
where ) (). Since for all , we know #. Then also # by Lemma 7.15. Now we apply part 4 of Lemma 7.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 follows from #, 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 7.15. By (), we obtain
as required.
The result follows.
if and only if .
The left-to-right part is Theorem 7.10.
For the right-to-left part, suppose that . We have observed that there are SIMPr rewrites
and
Then by Lemma 7.17, we know
and
so ()-1 )-1 and ()-1 )-1 by transitivity.
We supposed that so by Corollary 6.21 it must be the case that . By Lemma 7.16 also ()-1 )-1.
Then ()-1 )-1 by symmetry and transitivity. By Lemma 7.13 then also . Since freshly extends with atoms not in , we conclude by strengthening (Lemma 2.33).
As a simple corollary of Theorem 7.18, we obtain decidability of SUB.
It is decidable whether .
By Theorem 7.18, is equivalent to . By Theorem 6.33, this is decidable.
Combining Theorem 7.18 and Corollary 6.21, 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 3.4.
We can extract a witnessing derivation in SUB of from the algorithm above: the meat of work is done in the proofs of Lemma 7.17 and Lemma 7.13.
By a similar method to the one we used to prove Theorem 7.18 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
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 7.10, . By construction and do not mention sub, therefore by Corollary 6.20 also .
Given the derivability of we can prove the derivability of by exploiting the syntactic criteria of Corollary 3.4. 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 3.4 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.
7.3 -completeness
We consider completeness with respect to the ground term model (see Definition 7.21 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 [4] with respect to a standard class of semantics in nominal sets [2]. 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 7.18 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 in , , 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 the previous subsection 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 3.4.
For part 3, by Corollary 6.21 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 7.25 and part 3 of Lemma 7.23.
SUB is -complete.
We show that if then there exists a -consistent ground substitution (for , and ) such that .
Suppose . Then also by Theorem 7.18. Now by Corollary 7.26 we obtain ((). Then () () by Theorem 4.13 and Corollary 6.21.
Now take . Since maps to ground terms in , the result follows.
7.4 Restricting the sort system
In Remark 2.9 we claimed that unknowns of sort [] and the term-former sub : ([][])[] are ‘convenient but not necessary’.
To see what precisely we mean by this, consider by way of example the lambda calculus signature from Example 2.7. Remove from it sub : ([][])[] and disallow unknowns of abstraction sort. The signature now has term-formers
Let theory over this signature have axioms
Let SUB be the theory of substitution over the signature of the lambda calculus from Example 2.7.
Suppose that , and are terms in the signature of and do mention unknowns of sort . Then
For the right-to-left part it suffices to show that each axiom of can be derived in SUB. Instances of (lam) and (sub) may be replaced by instances of (f) and (#). Instances of the other axioms of are directly instances of axioms with similar names in SUB.
For the left-to-right part, suppose . Then also by Theorem 7.10. 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.
Using a result similar to Lemma 7.17 we obtain derivations of
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 6.21, Lemma 7.16 and our assumption . Then ()-1 )-1 using (symm) and (tran). Using a result similar to Lemma 7.13 we obtain . We conclude using (fr).
We used every axiom of in the proof above and it is not hard to show that if we remove any then the weaker theory is not complete. is somewhat longer than SUB, and proofs involving tend to be somewhat longer than proofs involving SUB. For this reason we preferred SUB in this paper.
8 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 7.27). 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é [13, 14] 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’ [14, page 2].
Feldman [15] gives an algebraic axiomatisation inspired by a concrete model of functions/evaluations. His axioms are closer in spirit to Cylindric Algebras [1] and Lambda Abstraction Algebras [16, 17]. 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) [18] and related systems implement substitution by ‘pipes’ (e.g. the translation of -terms into CA [18]). 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 [12] and the thesis of Bloo [19] 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 [20] 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’ definitely is not.
Sun has investigated Binding Algebras [21]. 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 [22], 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 [2] and categories of presheaves used in another thread of work [23, 24, 25]. This uses ideas from categorical algebra [26] 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 [23, 24, 25] 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 [3] (in our terminology, unification of nominal terms up to CORE) is decidable. Nominal unification is to be compared with higher-order patterns [27]. We suggest that unification up to SUB is to be compared with higher-order unification [28], 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 [29] and Hierarchical Nominal Rewriting [30] 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
[1] Burris, S., Sankappanavar, H.: A Course in Universal Algebra. Springer (1981)
[2] Gabbay, M.J., Pitts, A.M.: A new approach to abstract syntax with variable binding. Formal Aspects of Computing 13(3–5) (2001) 341–363
[3] Urban, C., Pitts, A.M., Gabbay, M.J.: Nominal unification. Theoretical Computer Science 323(1–3) (2004) 473–497
[4] Gabbay, M.J., Mathijssen, A.: A formal calculus for informal equality with binding. In: WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation. Volume 4576 of LNCS. (2007) 162–176
[5] Gabbay, M.J., Mathijssen, A.: Nominal algebra. Technical Report HW-MACS-TR-0045, Heriot-Watt (2006)
[6] Gabbay, M.J., Mathijssen, A.: One-and-a-halfth-order logic. In: PPDP ’06: Proc. of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, ACM Press (2006) 189–200
[7] Gabbay, M.J., Mathijssen, A.: Capture-avoiding substitution as a nominal algebra. In: ICTAC’2006: 3rd Int’l Colloquium on Theoretical Aspects of Computing. Volume 4281 of LNCS. (2006) 198–212
[8] Fernández, M., Gabbay, M.J.: Nominal rewriting. Information and Computation 205 (2007) 917–965
[9] Hodges, W.: Elementary predicate logic. In Gabbay, D., Guenthner, F., eds.: Handbook of Philosophical Logic, 2nd Edition. Volume 1. Kluwer (2001) 1–131
[10] Fernández, M., Gabbay, M.J., Mackie, I.: Nominal rewriting systems. In: Proc. 6th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2004), ACM (2004) 108–119
[11] Bloo, R., Rose, K.H.: Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection. In: CSN-95: Computer Science in the Netherlands. (1995)
[12] Lescanne, P.: From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions. In: POPL ’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press (1994) 60–69
[13] Crabbé, M.: Une axiomatisation de la substitution. Comptes rendus de l’Académie des Sciences de Paris, Série I 338 (2004) 433–436
[14] Crabbé, M.: On the notion of substitution. Logic Journal of the IGPL 12 n.2 (2004) 111–124
[15] Feldman, N.: Axiomatization of polynomial substitution algebras. Journal of Symbolic Logic 47(3) (1982) 481–492
[16] Lusin, S., Salibra, A.: The lattice of lambda theories. Journal of Logic and Computation 14 n.3 (2004) 373–394
[17] Salibra, A.: On the algebraic models of lambda calculus. Theoretical Computer Science 249(1) (2000) 197–240
[18] Barendregt, H.P.: The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland (1984)
[19] Bloo, R.: Preservation of Termination for Explicit Substitution. PhD thesis, Eindhoven University of Technology, Eindhoven (1997)
[20] de Bruijn, N.G.: Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the church-rosser theorem. Indagationes Mathematicae 5(34) (1972) 381–392
[21] Sun, Y.: An algebraic generalization of frege structures - binding algebras. Theoretical Computer Science 211 (1999) 189–232
[22] Dowek, G., Hardin, T., Kirchner, C.: Binding logic: Proofs and models. In: LPAR ’02: Proceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, London, UK, Springer-Verlag (2002) 130– 144
[23] Fiore, M., Turi, D.: Semantics of name and value passing. In: Proc. 16th LICS Conf., IEEE, Computer Society Press (2001) 93–104
[24] Fiore, M.P., Plotkin, G.D., Turi, D.: Abstract syntax and variable binding. In: 14th Annual Symposium on Logic in Computer Science, IEEE Computer Society Press (1999) 193–202
[25] Tanaka, M., Power, J.: A unified category-theoretic formulation of typed binding signatures. In: MERLIN, ACM (2005) 13–24
[26] Lambek, J., Scott, P.: Introduction to Higher Order Categorical Logic. CUP (1986)
[27] Miller, D.: A logic programming language with lambda-abstraction, function variables, and simple unification. Extensions of Logic Programming 475 (1991) 253–281
[28] Huet, G.: Higher order unification 30 years later. In: TPHOL 2002. Number 2410 in LNCS (2002) 3–12
[29] Gabbay, M.J., Lengrand, S.: The lambda-context calculus. In: LFMTP’07: International Workshop on Logical Frameworks and Meta-Languages. To appear in ENTCS (2007)
[30] Gabbay, M.J.: Hierarchical nominal rewriting. In: LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice. (2006) 32–47
Notes
3 Unknowns, atoms, and other distinct syntactic classes, are assumed disjoint. ↩
4 There is no mathematical reason for this, but there is a nice computational one: the algorithm obtained by reading rules bottom-up, must terminate. ↩
5 Composing both sides of Id with , we obtain . Inverting both sides, we obtain . ↩
7 Both ([])[] and ([])[] introduce the same fresh atom because fa( fa(). We can see this as follows: fa( fa() is equivalent to fa iff fa() for all atoms . By Lemma 4.3 this is equivalent to # iff #, and by Corollary 3.6, this follows from the assumption . ↩
8 As is also standard, it took the authors months of laborious fiddling to get this definition just right. ↩