Capture-Avoiding Substitution as a Nominal Algebra
Abstract. Substitution is fundamental to computer science, underlying for example quantifiers in predicate logic and beta-reduction in the lambda-calculus. So is substitution something we define on syntax on a case-by-case basis, or can we turn the idea of ‘substitution’ into a mathematical object?
We exploit the new framework of Nominal Algebra to axiomatise substitution. We prove our axioms sound and complete with respect to a canonical model; this turns out to be quite hard, involving subtle use of results of rewriting and algebra.
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, 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 algebraically axiomatise substitution some 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 following properties axiomatise substitution, all of substitution, and nothing but substitution. We express them in Nominal Algebra (given formal meaning in the rest of this paper):
For convenience we now give an informal reading:
(var ): If is a variable then with replaced by , is .
(# ): If is fresh for then with replaced by is .
(f ): Substitution distributes through term-formers (we can have as many as we like); f ranges over them.
(abs ): Substitution distributes under abstraction, provided an ‘accidental 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 .
Formally, Fig. 1 uses nominal terms [2] as a syntax, and nominal algebra [3] as an algebraic framework.
A number of questions now arise: a) Is this substitution? In what sense; are the axioms sound, and for what model? b) Are the axioms complete for that model? c) Do other (perhaps unexpected) models exist of the same axioms? d) Can the axioms be used to found theories of predicate logic, -calculus, unification, and so on?
Sections 2 and 3 define nominal terms and nominal algebra. Section 4 defines substitution as a nominal algebraic theory. Section 5 develops some highly non-trivial technical results. Section 6 answers a) by showing that on a canonical model, our axioms for substitution give rise to something which is recognisably substitution as we might expect it to behave. Section 7 further shows the harder property mentioned in b) that our axioms for substitution precisely characterise what is true of that concrete model. The Conclusions then describes related and future work. Questions c) and d) are answered positively in other papers [4, 5].
2 Nominal terms
We define a syntax of nominal terms. For simplicity fix a sort of atoms and a (base) sort of terms . Then sorts are inductively defined by:3
We could admit more sorts of atoms, and base sorts other than , if we wished.
Our syntax has term-formers: Fix term-formers to each of which is associated some unique arity ). We may write f : for ‘f, which has arity ’. We assume term-formers:
The two subs will be used to represent the substitutions from Fig. 1; the condition on is for simplicity only.
var, pair, and binder define a sufficiently rich language for our axioms of substitution to have an interesting action, but as mentioned in the Introduction almost anything else would do (e.g. see example signatures in [6]).
Finally, we can define the sorted syntax itself:
Fix some countably infinite set of atoms . These model object-level variable symbols (the ones we axiomatise substitution for).
Fix a countably infinite collection of unknowns .4 Intuitively these represent unknown terms. We assume unknowns are inherently sorted and infinitely many populate each sort: so is shorthand for , and and are two different unknowns with confusingly similar names.
Terms are inductively defined by the following grammar:
Here we call () a moderated unknown; is described below. We have indicated sorts with a subscript but we shall usually omit them; we repeat the definition above without subscripts, for clarity:
A permutation of atoms is a bijection on 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. 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 . We may abbreviate Id to . Importantly, we shall write () for the permutation which maps to and vice versa, and maps all other to themselves.
In Fig. 1 we have sugared sub([]) to []. We suggestively name a term of this form an explicit substitution.
A few more simple notations are useful for later: We call the size of its inductive rank.5 Write (or ) for ‘ (or ) occurs in (the syntax of) ’. Occurrence is literal, e.g. [] and when () . Similarly write and for ‘does not occur in the syntax of ’. Write syntactic identity of terms as to distinguish it from provable equality. Important: we do not quotient terms in any way.
It may help to show how nominal terms 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: var(), () pair(), ( binder([]()). Even for this simple signature of var, pair, and binder, there are interesting things to say. For example we shall see that binder([]) behaves much like the -context - where - is a ‘hole’, and of course sub will allow us to state (and prove!) nontrivial properties of substitution in the presence of those holes. Example 4.1 gives three such properties; there are many more and our main result Theorem 7.5 asserts that we can prove all of them from our axioms.
3 Nominal algebra
We can now do algebra. For us, algebra is the logic of equality (no implication, no quantification). We consider a canonical syntax-based model later in Section 6 and find much of interest to say about it in Section 7 — other models of our axioms are the topic of other work [4].
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 ##. Define derivability on freshnesses in natural deduction style by:
Here f ranges over term-formers, and range over terms, ranges over unknowns, and and permutatively range over atoms, i.e. and represent any two distinct atoms. We use similar conventions henceforth.
Write # when a derivation of # exists using the elements of as assumptions. Say that entails # or # is derivable from ; call this a freshness judgement.
An equality (assertion) is a pair where and are terms of the same sort. Define derivability on equalities in natural deduction style by:
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.
In (fr) square brackets denote discharge in the sense of natural deduction, as in implication introduction [7]; denotes the other assumptions of the derivation of .7 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 ’. It is defined on syntax by:
So propagates through the structure of until it reaches an atom or a moderated unknown. We can easily verify that () () and Id .
Here is an example derivation, using the fact that [] () []:
Provable equality in CORE coincides with provable equality on nominal terms in the sense of nominal unification [2], for details see elsewhere [3]. This corresponds in a suitable sense to -equivalence, though in a non-trivial way since []] does not hold — but # []]() does [2].
Nominal Algebra (NA) is the theory outlined above, along with the ability to impose axioms. Call a triple where is finite 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,8 and permutatively renaming atoms, such that the hypotheses are corresponding instances of freshness conditions of the axiom.
4 SUB: the theory of explicit substitution
NA substitution allows the axioms in Fig. 1. Here (f) represents a schema of axioms, one for each term-former other than var; one particular example is (sub). We make concrete choices of atoms and , of an unknown of sort , and of unknowns of appropriate sorts. We call the axioms and the resulting equality a theory of substitution and write it SUB.
The following judgements are derivable in SUB:
1.
2.
3. [ var(
We give only the first derivation in full. We write for [] and we use the unsugared syntax for the other substitutions.
For part 2: We must prove # sub([] sub([]() ). By (congf), (refl), and (symm), it suffices to derive []() ]. Using (perm) it suffices to derive #[], which is easy.
For part 3: By (fr) we may assume # for some [ var()], i.e. . By (tran) it suffices to derive [ var() )[ var()] and (() )[ var(. The former is an instance of part 2 of this example. For the latter it suffices to derive #() , by axiom (ren ) and () () . By (#X), this follows from the assumption #.
5 SUBfr: explicit substitution rewritten
Equality has no algorithmic content so we have specified what is equal, but not how to verify it. Rewriting is algorithmic in that sense, given confluence. It is useful to give a rewrite system for SUB.
Nominal rewriting is like nominal algebra, but with a directed notion of equality; terms are taken up to equality in CORE. A rewrite rule may trigger a rewrite in a term when (an instance of) is provably equal in CORE to some subterm of , and the corresponding instance of is derivable using the ambient context of freshness assumptions (so is freshness conditions on the rewrite rule) [8, 9, 10]. Rewrite rules are given in Fig. 2. Write for the rewrite relation induced by rewrites in CORE, given .
Say a freshness context freshly extends when where may be empty, but if # then . Note that the rule (fr) precisely ‘introduces a ’. So ## freshly extends # but ## does not.
is derivable if and only if is related to by the symmetric transitive reflexive closure of for some freshly extending .
Say a property holds of a triple () ‘provided has sufficient freshnesses’ when that property holds of some () for freshly extending . So for , , and , equality between and SUB coincides with rewritability between them in SUBfr, provided that has sufficient freshnesses.
5.1 SUBe and strong normalisation up to SUBe
Substitution has the character of a computation and our re-casting SUB as a rewrite system recognises this. However substitutions also have an awkward ‘simultaneous’ character. For example
is derivable but there is no obvious direction to the equality and SUBfr does not strongly normalise on the terms.
Call a binary relation (by incredible coincidence write it ) strongly normalising when if for we have then exists such that if then . Clearly this is not the case of any from SUBfr.
Let SUBe be the NA theory with axioms in Fig. 3.
The rules obtained from directing the equalities from SUBe, are admissible in SUBfr, i.e. every instance of the following can be obtained in SUBfr:
As a corollary, provable equality in SUBe implies provable equality in SUB.
We will show that of SUBfr is strongly normalising up to provable equality in SUBe. Some auxiliary functions and notations are needed.
Fix and write # for # and # for #. Let f range over all term-formers excluding sub (but including var), and let denote the arithmetic product. Define by # and only otherwise by:
Then the following inductive definition makes Theorem 5.3 a matter of easy arithmetic:
If then either or . As a result SUBfr is strongly normalising up to provable equality in SUBe.
Write for the transitive reflexive (but not symmetric) closure of . We note that does not imply or . For a counterexample consider var()[ var()] and var()[ var()].
5.2 Garbage and garbage-collection
Call the pair a (nominal) term-in-context. Equalities, and rewrites, are on terms in context. Only if is closed is context irrelevant.
Say that a term-in-context has garbage when:
– for some subterm [] it is the case that #, or
– for some subterm of the form and some , it is the case that both # and ()# hold.
Otherwise say has no garbage.
Terms in the top line have no garbage, the others do:
Alas the rewrite rule (Rsub) in SUBfr may introduce garbage (the innermost [] acting on ). Alas also, -equivalence (provable equality in CORE) may introduce garbage, for example # () .9
Say that is a SUBfr-normal form when for all with . So a SUBfr-normal form may still rewrite with a rule from SUBfr ((R#) and (Rsub) to be precise) but that rewrite just has no effect up to provable equality in SUBe.
For any there is some a SUBfr-normal form with no garbage such that . Furthermore, if is derivable then there is some SUBfr-normal form with no garbage such that and .
5.3 Confluence
A standard way to prove confluence is to prove local confluence and strong normalisation. But SUBfr is not strongly normalising, see the example of Sect. 5.1. The interest of this proof is that we use SUBe to ‘cancel that out’.
Rewrites of in the nominal rewrite system SUBfr are locally confluent in a context with sufficient freshnesses, up to provable equivalence in CORE.
(Recall that the restriction on contexts is not a ‘real’ one, because we have (fr).)
SUBfr is confluent in a context with sufficient freshnesses.
From this follow:
SUB is conservative over CORE. That is, if and only if , assuming that neither nor mention explicit substitution.
For all there are such that .
6 Ground terms
Call terms and ground terms when they do not mention unknowns or explicit substitutions. These are inductively characterised by
where f ranges over all term-formers except for sub.
We consider the meaning of explicit substitution on ground terms (making a connection between [] and actual capture-avoiding substitution on syntax).
Define a ‘free atoms of’ function fa() on ground terms inductively as follows:
Define the support of by supp(#.
fa() = supp().
For each finite set of atoms arbitrarily choose some canonical ‘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 var (and sub of course), and ‘ fresh’ means is fresh for fa() fa() according to our arbitrary choice.
[[] is always derivable.
By straightforward induction on the structure of , using Lemma 6.1.
Define an -equivalence relation inductively by:
Here ‘ fresh’ means fresh for fa() fa().
if and only if is derivable.
By Theorem 5.8 is equivalent to . By results about nominal terms [2, 3] this happens precisely when .
So intuitively: On ground terms is -equivalence and explicit substitution is capture-avoiding substitution.
7 -completeness
How do we know that SUB really is an axiomatisation of substitution? We now give a soundness and completeness result. -completeness (notation from [12]) is ‘soundness and completeness with respect to the closed term model’.
We need a number of technical definitions and lemmas.
7.1 Meta-level substitution
Call a substitution a finitely supported function from unknowns to terms of the same sort. Here, finite support means that () Id for all but finitely many unknowns , i.e. for ‘most’ .
Write [] for defined by () and () Id , for all .
Let (‘ applied to ’) be inductively defined by:
We may call an instance of . The substitution action extends to freshness assertions, equalities, and so on. We extend notations and terminologies silently. Note that this does not avoid capture; ([])[] [] and in this formal sense is ‘meta’ and really does represent an unknown term.
Call nontrivial on when () Id . By assumption is nontrivial for only finitely many unknowns. Say that extends when () () whenever is nontrivial on . Call closing for some collection of freshness and equality assertions when () is a closed term for every . We will not mention when it is clear from the context.
Say a closing is -consistent when #() for all #.
Fix , , and closed term . If # for every # then there is a -consistent closing which extends [].
7.2 Suspended explicit substitutions
Suppose a term-in-context ()[] [] is such that # for all 1 . Here may equal 0, in which case ().
Then call the partial syntax ( -)[] [] a suspended substitution; we generally let and vary over suspended substitutions. will typically be ( -)[] []. Suspended substitutions have a natural action on terms given by replacing - by .
Assuming sufficient freshnesses, if is a SUBfr-normal form with no garbage then every explicit substitution mentions is in a subterm such that and has no garbage.
Otherwise there is a rewrite such that where .
Suppose and are SUBfr-normal forms with no garbage. Then precisely when one of the following hold:
1. and .
2. and .
3. [] and [] and .
4. [] and [] and () and #.
5. f() and f() and for 1 (f sub).
6. and and 0 and , and for every there is a unique such that (() and — and similarly for every .
Equality in SUB is decidable.
Given , and , we can calculate whether is derivable:
1. Rewrite and to SUBfr-normal forms and , using Theorem 5.3.
2. Remove garbage from and , using Lemma 5.5.
3. Check if the top-level term-formers of and satisfy the criteria stated in Lemma 7.3; for each of the new proof obligations go to step 2.10
4. If all criteria checks were successful, return true; otherwise false.
7.3 -completeness
-completeness is soundness and completeness with respect to a model made out of closed terms (terms which do not mention unknowns ); since syntax is the canonical example on which substitution is defined, soundness and completeness with respect to this model is a powerful argument that in theory SUB, we got it right. An NA judgement has the flavour of a universal quantification over the unknowns it mentions. Soundness for the closed terms model means: if is derivable then all instances of this equality (subject to ) on closed terms are derivable. Much harder to prove is that furthermore if all instances are derivable (subject to ), then so is .
Call SUB -complete when if is derivable for all -consistent closing substitutions (for , and ), then is derivable.
SUB is -complete.
By contraposition. Suppose not . We construct -consistent such that not . It suffices to do this for some which freshly extends ; for convenience assume . By the first part of Lemma 5.5 and by Lemma 5.1 we may suppose and are SUBfr-normal forms with no garbage. By Lemma 7.2 further assume they have the particular form mentioned in that result. By Lemma 5.2 also is not derivable. So now we must prove
where and have the structure as described above.
We work by induction on the size of and . We proceed by case distinction (we omit routine cases, and calculations concerning size):
– and . By Theorem 6.3.
– f() and g() (f g sub). Apply any closing -consistent (easy to manufacture), use Theorem 6.2 to remove all explicit substitutions, and then use Theorem 6.3 to conclude .
– f() and f() (f sub). By part 5 of Lemma 7.3 for some . We use the inductive hypothesis and Theorems 6.2 and 6.3.
– [] and []. Using Lemma 7.3 () or #. If #, then choose appropriate and use Theorems 6.2 and 6.3. If () then we can remove possible garbage from () without increasing size, apply the inductive hypothesis, and finally use Theorems 6.2 and 6.3.
– and and 0. Using Lemma 7.3 and notation from that result, precisely when for every such that ((). So suppose and are such that . Now using pair, var, and binder, generate such that supp() and supp() is otherwise fresh (thus, disjoint from atoms mentioned in and ). Choose -consistent closing extending [] using Lemma 7.1. Then by Theorems 6.2 and 6.3 we see that .
8 Conclusions
Substitution underlies quantifiers in predicate logics, the -binder of the -calculus, unification, and lots more besides. It is a central, not incidental, feature of these systems. This paper throws a new and unexpected light on this profoundly important common denominator.
Future work on nominal techniques needs a nominal axiomatisation of substitution. This paper provides that and the work has already found application in concurrent work; we use it to ‘power’ a nominal axiomatisation of first-order logic [5], and we develop abstract (non-term-based) models of SUB in [4]. Such enterprises would not be mathematically secure without Theorem 7.5 to tell us that we got our foundations right.
We have considered one substitution and Theorem 7.5 tells us it is capture-avoiding substitution. We can think of other kinds of substitution, for example context substitution which does not avoid capture; the basic principles are clear in this paper and there are a great many possibilities for applying them elsewhere.
Note how we decompose an equational system into a rewrite system over a simpler equational system, and we fully exploit results of nominal rewriting and nominal algebra as well as detailed calculations on terms (such as the notion of measure we use to prove confluence). Similar techniques may be useful for other systems; they seemed to arise in our treatment of first-order logic [5].
We find the nominal terms treatment of binding pleasingly clean; a nominal term such as [] or [] corresponds exactly and syntax-for-syntax to what we intend when we write and , right down to the way in which and are instantiated. Other approaches to binding involve some degree of emulation (index lifting in de Bruijn [13], type-raising in type-based techniques [14]). Thus a nominal treatment of substitution is worthwhile to investigate in itself.
8.1 Related work
Crabbé [15, 16] axiomatises substitution much like us and shares (in our terminology) atoms and freshness conditions. Crabbé does not treat binding.11 So our substitution is capture-avoiding. Also, for us atoms and freshness side-conditions are parts of a broader nominal framework whereas Crabbé expresses them in first-order logic; we feel that nominal techniques have given us a cleaner separation of the layers of complexity hidden in these deceptively simple ideas.
Feldman [17] 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 [18, 19]. 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) [20] and related systems implement substitution by ‘pipes’ (e.g. the translation of -terms into CA [20]). General truths such as (#) are only provable for fixed closed terms by calculations parametric over its specific structure.
Lescanne’s classic survey [13] and the thesis of Bloo [21] 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 [22] 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.
8.2 Future work
Nominal unification [2] is ‘merely’ unification of nominal terms up to CORE. Our confluence results are a step towards unification up to SUB. Nominal Unification is to be compared (in a sense we do not discuss here) with higher-order patterns [23]; we now suggest that unification up to SUB is to be compared with higher-order unification [24] — with the difference that SUB is weaker, because there is no and application, only their combination as ‘substitution’.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 to the NEW calculus of contexts [25] and hierarchical nominal rewriting [26] investigated by the first author, but much more is possible and there are many substitutions out there which we could axiomatise.Armed with SUB and the knowledge that it is correct in the sense of Theorem 7.5 we hope to develop logics and -calculi with a fundamentally new, beautiful, and mathematically advantageous, way of treating substitution and more generally internalising the meta-level.
References
[1] Burris, S., Sankappanavar, H.: A Course in Universal Algebra. Springer (1981) Available online.
[2] Urban, C., Pitts, A.M., Gabbay, M.J.: Nominal unification. Theoretical Computer Science 323(1–3) (2004) 473–497
[3] Gabbay, M.J., Mathijssen, A.: Nominal algebra. Submitted STACS’07 (2006)
[4] Gabbay, M.J., Marin, A., Rota Bulò, S.: A nominal semantics for simple types. Submitted STACS’07 (2006)
[5] Gabbay, M.J., Mathijssen, A.: One-and-a-halfth-order logic. In: PPDP ’06: Proceedings of the 8th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming, New York, NY, USA, ACM Press (2006) 189–200
[6] 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
[7] Hodges, W.: Elementary predicate logic. In Gabbay, D., Guenthner, F., eds.: Handbook of Philosophical Logic, 2nd Edition. Volume 1. Kluwer (2001) 1–131
[8] 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
[9] Fernández, M., Gabbay, M.J.: Nominal rewriting. Information and Computation (2005) Accepted for publication.
[10] Fernández, M., Gabbay, M.J.: Nominal rewriting with name generation: abstraction vs. locality. In: Proc. 7th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2005), ACM (2005) 47–58
[11] Newman, M.: On theories with a combinatorial definition of equivalence. Annals of Mathematics 43(2) (1942) 223–243
[12] Groote, J.F.: A new strategy for proving omega-completeness applied to process algebra. In Baeten, J., Klop, J., eds.: CONCUR ’90: Proceedings of the Theories of Concurrency: Unification and Extension. Volume 458 of LNCS., London, UK, Springer-Verlag (1990) 314–331
[13] 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
[14] Paulson, L.C.: The foundation of a generic theorem prover. Journal of Automated Reasoning 5(3) (1989) 363–397
[15] Crabbé, M.: Une axiomatisation de la substitution. Comptes rendus de l’Académie des Sciences de Paris, Série I 338 (2004) 433–436
[16] Crabbé, M.: On the notion of substitution. Logic Journal of the IGPL 12 n.2 (2004) 111–124
[17] Feldman, N.: Axiomatization of polynomial substitution algebras. Journal of Symbolic Logic 47(3) (1982) 481–492
[18] Lusin, S., Salibra, A.: The lattice of lambda theories. Journal of Logic and Computation 14 n.3 (2004) 373–394
[19] Salibra, A.: On the algebraic models of lambda calculus. Theoretical Computer Science 249(1) (2000) 197–240
[20] Barendregt, H.P.: The Lambda Calculus: its Syntax and Semantics (revised ed.). Volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland (1984)
[21] Bloo, R.: Preservation of Termination for Explicit Substitution. PhD thesis, Eindhoven University of Technology, Eindhoven (1997)
[22] 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
[23] Miller, D.: A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation 1(4) (1991) 497536
[24] Huet, G.: Higher order unification 30 years later. In: TPHOL 2002. Number 2410 in LNCS (2002) 3–12
[25] Gabbay, M.J.: A new calculus of contexts. In: Proc. 7th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2005), ACM (2005)
[26] Gabbay, M.J.: Hierarchical nominal rewriting. In: LFMTP’2006. (2006) 32–47
Notes
3 So sorts are just , [], [][], and so on, and similarly , [], and so on. ↩
4 Unknowns, atoms, and term-formers, are assumed disjoint. ↩
5 In plain english: the depth of a proof that is in the set of terms, using the inductive definition above. ↩
6 More precisely, f is a meta-variable ranging over term-formers. ↩
9 This is one reason SUB is a difficult beast to handle, and it took us quite a while to decide to split it up as a rewrite system over a provable equality, and then which provable equality to use. ↩
10 Garbage could be introduced by case 4 of Lemma 7.3, so we must remove it. ↩
11 He declares as much: ‘. . . we are not concerned with the notion of bound variable’ [16, page 2]. See also the axioms (there is no (abs)) and the soundness and completeness result — Crabbé’s model is based on (in our notation) var and pair, whereas we consider a model based on var, pair, binder, and sub. ↩