A nominal axiomatisation of the lambda-calculus
Abstract
The lambda-calculus is fundamental in computer science. It resists an algebraic treatment because of capture-avoidance side-conditions.
Nominal algebra is a logic of equality designed for specifications involving binding. We axiomatise the lambda-calculus using nominal algebra, demonstrate how proofs with these axioms reflect the informal arguments on syntax, and we prove the axioms sound and complete. We consider both non-extensional and extensional versions (alpha-beta and alpha-beta-eta equivalence).
This connects the nominal approach to names and binding with the view of variables as a syntactic convenience for describing functions. The axiomatisation is finite, close to informal practice, and it fits into a context of other research such as nominal rewriting and nominal sets.
Keywords: lambda calculus, equational logic, nominal techniques
Contents
1 Introduction
Functions are widely used in what we now call computer science; a development which can be traced back to Church [Chu41]. They are the basis of functional programming languages [Pau96,Tho96]; they also find application in logic [Bar77,Lei94], theorem-provers [ABI96,Pau89], rewriting [BN98], and more. Functions are a basic mathematical entity of computer science.
Functions have been studied in different ways. Models include Scott domain models, graph and filter models, game models, and more [CDHL84,KNO02,Ber00,Ber06]. There is much study using rewriting, starting with the proof of confluence of -reduction (a particularly neat proof is in [Tak95]). There are also axiomatisations, including axioms by Andrews [And86], -algebras [Sel02], Salibra’s lambda-abstraction algebras [Sal00], and (if one does not care about representing -abstraction, which we do) -lifting [Joh85].
This paper will axiomatise the -calculus using a recent logic by the authors: nominal algebra [GM06,Mat07,GM07,GM09]. Nominal algebra extends universal algebra [Coh65] with support for names and binding, while preserving much of its flavour and its good mathematical properties. Using nominal algebra to axiomatise the -calculus brings several benefits:
Nominal algebra seems quite good at bringing us close to informal practice. It is easy to write down plausible axioms for the -calculus; they look just like well-known informal -equivalences. In this paper we shall consider two nominal algebra theories:
ULAM (Figure 1). This axiomatises the -calculus up to -equivalence (Theorems 4.3 and 4.7).
ULAME (Figure 5). This axiomatises the -calculus up to -equivalence (Theorems 5.3 and 5.4).
The sets of axioms ULAM and ULAME are finite. Figures 1 and 5 do not describe infinite schemes of axioms (unlike is the case for example in [Sal00] or [And86]; see Remark 2.13). This is because name-binding are handled by nominal algebra itself. 4
Nominal algebra is not a stand-alone logic; it is part of a body of research which includes nominal unification and nominal rewriting [UPG04,FG07b] (both of which have good computational properties) — and nominal sets:
ULAM and ULAME are nominal algebra theories, and so they take models in nominal sets [GM07,GP01]. 5 The theory of these nominal sets models is investigated in [Gab09]. They have properties that sets models of universal algebra theories do not have. The notion of variety is richer, and nominal sets models are inherently finite-dimensional and exclude infinite-dimensional models. 6 Thus, using nominal techniques give us the option of working purely (nominal) algebraically in a finite-dimensional world, which is an option that universal algebra does not offer.
So we can write down axioms which look plausibly like they axiomatise functional abstraction, in an algebraic logic which looks plausibly like universal algebra and which is compatible with a broader body of research. But ... in what sense are the axioms correct? We can ask three questions:
If we quotient -terms by -equivalence (respectively, -equivalence) do we obtain, in some natural way, a model of ULAM (respectively, ULAME)?
Are the equalities which are valid in all models of ULAM, precisely the equalities described by that one set or is there something missing? (Is ULAM complete for ?) Similarly for ULAME.
Does nominal algebra reasoning capture a useful fragment of the kind of reasoning steps we would like to represent?
In this paper we explore to what extent our two theories ULAM and ULAME capture ‘the -calculus and its theory’. We will demonstrate that ULAM and ULAME are theories for the untyped -calculus, in the sense that they are sound and complete for -terms quotiented by -equivalence and -equivalence respectively. We will demonstrate with examples how they can express informal reasoning as formal derivations.
Nota bene:
Nominal techniques were first applied to construct datatypes of syntax-with-binding [GP01] with good inductive reasoning principles. One datatype often used is -term (up to -equivalence). This paper is not another such study, like those in nominal sets [GP01], higher-order abstract syntax [PE88], de Bruijn terms [dB72], and so on — which are about collections of syntax trees.
Overview of the paper
We introduce nominal algebra in Section 2, with a syntax specialised to our application to the -calculus (a general treatment is elsewhere [Mat07]). In Section 3 we provide a brief formal treatment of the -calculus. In Section 4 we show that the nominal algebra theory ULAM is sound and complete with respect to -equality. In Section 5 we show that the nominal algebra theory ULAME is sound and complete with respect to -equality. In the Conclusions (Section 6) we discuss related and future work. In Appendix A we include, for the reader’s convenience, statements and proofs of some underlying properties of nominal algebra; these do not depend on ULAM or ULAME but they are relevant background, in much the same way as the definitions and results in Section 3 are relevant background.
2 Nominal algebra
In this section, we present the proof theory of nominal algebra. It consists of an equational logic on nominal terms, and has built-in support for binding, freshness and meta-variables.
2.1 Nominal terms
We define a syntax of nominal terms tailored to our -calculus application; general treatments are elsewhere [GM08a,Mat07].
Fix the following disjoint sets:
A countably infinite set of atoms . Atoms represent object-level variables. will range over atoms. We use a permutative convention that range over distinct atoms. Thus for example in (#ab) and (#b) from Figure 2, and in (perm) from Figure 3, and represent two distinct atoms. 7
A countably infinite collection of unknowns. Unknowns represent meta-variables (as in ‘take a term ’; is a meta-variable ranging over terms). will range over distinct unknowns.
a possibly infinite collection of constant symbols. c will range over constant symbols (we will never need to consider more than one at a time).
We set about constructing the machinery of nominal algebra.
A permutation of atoms is a bijection on atoms with finite support, which means that the set supp, defined by () , is finite. In words: For ‘most’ atoms is the identity.
The following notation will prove convenient:
Write id for the identity permutation on atoms, for the inverse of , and for the composition of and , i.e. ()((()).
Write () for the permutation that swaps and , i.e. ()(, ()(, and ()(. We may omit between swappings, writing () () as ()().
Terms are inductively defined by:
We will use the following conventions:
Application is left-associative, so for example ‘’ means ‘()’.
Abstraction extends as far to the right as possible, so for example ‘’ means ‘()’.
We may write id just as . However, note that ‘’ is an unknown and not a term — ‘id ’ is a term.
We write for syntactic identity. That is, ‘’ means ‘ and denote the same term’.
A typed syntax is possible; see [FG07a]. Types would cause no essential difficulties for the results to follow.
We now give some basic definitions; of the atoms-permutation action and of the capturing substitution action, which are characteristic of nominal terms [UPG04].
Define the set atoms of atoms that occur anywhere in inductively by:
We also write atoms() as a shorthand for atoms
For example,
Define a permutation action by:
In the clause for , acts also on the ‘’. For example () () . In the clause for , is a term (recall that ‘’, on its own, is not a term; it must always be paired with a permutation, even if it is id).
A substitution is a function from unknowns to terms.
Define a substitution action by:
()
Note that substitution does not avoid capture; note also that when encounters , the permutation is applied to . For example if
2.2 Freshness, equality, axioms, theories
A freshness is a pair # of an atom and a term. Call a freshness of the form # (so ) primitive. Write and for (finite, and possibly empty) sets of primitive freshnesses and call them freshness contexts.
We may drop set brackets in freshness contexts. For example we may write ## for ##.
Define derivability on freshnesses by the rules in Figure 2. In this figure, and permutatively range over atoms, and range over nominal terms, over permutations of atoms, over unknowns, and c over constants.
Write # when a derivation of # exists using these rules such that the assumptions are elements of . We usually write # as #.
For example from the rules in Figure 2, #, #, and ##() are all derivable.
Freshness has an accepted technical denotation as a notion in nominal sets, introduced in [GP01], but it has a broader pedigree and it might be convenient to briefly mention it here. Freshness is a notion of independence. Notions of dependence and independence have been studied abstractly before; two different examples are in [Coh65, Chapter VII, Section 2] or [Fin85]. Freshness is also related with specific constructions studied for example by Salibra (consider for example the function in Definition 3 of [Sal00]).
An equality is a pair . An axiom is a pair of a freshness context and an equality . We may write as .
Call a set of axioms T a theory. The theories considered in this paper are:
CORE: the empty set of axioms.
ULAM: the axioms from Figure 1. In Section 4 we give a formal sense in which this is a nominal algebra theory of the -calculus (with ).
In Figure 1, note that the and are specific atoms and the , and are specific unknowns.
ULAME: the axioms from Figure 1, plus an extra axiom #(.
This is, of course, an -equality. In Section 5 we give a formal sense in which this is a nominal algebra theory of the -calculus with .
Define derivability on equalities by the rules in Figure 3. In this figure, and permutatively range over atoms, , , and range over nominal terms, over unknowns, over freshness contexts, over permutations, and over substitutions.
Write when a derivation of exists using these rules such that:
for each instance of (ax), is an axiom from T;
in the derivations of freshnesses (introduced by instances of (ax) and (perm)) the freshness assumptions used are from only.
We write as .
We discuss the most interesting rules of Figure 3:
(ax). This axiom rule expresses how we obtain instances of axioms: we instantiate unknowns by terms using substitutions (using the substitution action defined in Definition 2.7) and also we rename atoms using permutations (using the permutation action defined in Definition 2.5).
This allows ULAM to have finitely many axioms; Figure 1 does not describe axiom-schemes. For example consider the axiom (var ()). This uses an arbitrary, but fixed atom and an arbitrary, but fixed unknown . We deduce () using (ax) taking ) and mapping to () (and all other to id ) as follows:
The reader can easily check from Definition 2.5 that () (() ) id .
We might expect the premises of the instance of the axiom rule to be
Both versions are correct, because of a known property of nominal terms which we have called object-level equivariance:
# if and only if ()#
for any , , and . This is characteristic of nominal techniques (e.g. [UPG04, Lemma 2.7], [FG07b, Lemma 20], [GM08b, Appendix A], [GP01, Lemma 4.7]).
(fr). This introduces a fresh atom into the derivation. Square brackets denote discharge of the assumption. We can always find a fresh atom no matter how unknowns are instantiated, since our syntax is finite and must mention finitely many atoms. (fr) adds no deductive power to CORE but it does in the presence of axioms; a full discussion with an example is in [Mat07, Lemma 2.3.18].
(perm). This rule expresses -equivalence (see Lemma 2.16 and Theorem 3.10). For instance, (perm) allows us to show the following standard -equivalence property:
(perm) captures several rules from [UPG04, Figure 2] (but not in a syntax-directed manner).
(refl). Choosing atoms we can construct the derivation sketched below:
So we can view (refl) as sugar, but (if only for cleaner example derivations) we retain it. All our proofs treat (refl) as a ‘real’ rule. 8
Nominal algebra is algebraic (even though the judgement-form has ‘’, which looks like an implication) in the following two senses:
Nominal algebra is sound and complete for models in nominal sets [GM07,Mat07].
These models are closed under notions of product, subalgebra, quotient (just like for traditional algebra) — and a nominal sets notion we call atoms-abstraction. A version of the HSP theorem (Birkhoff’s theorem) holds; any class of nominal algebra models closed under product, subalgebra, quotient, and atoms-abstraction, is characterised by a nominal algebra theory [Gab09].
So, perhaps unexpectedly, nominal algebra retains much of the flavour and mathematical properties of universal algebra.
In ULAM we can prove -equivalences as illustrated in Figure 4 — we choose one requiring an -conversion.
We now consider some useful examples of derivations in the presence of unknowns:
# ()(() )) .
We give the derivation in full:
The instance of (perm) relies on the fact that () () . □
Lemma 2.17 is a nominal algebra rendering of the substitution lemma [Bar84, Lemma 2.1.16] in terms of -redexes:
# ((()))(()))(()).
A proof by induction on is impossible — need not range over syntax, only over elements of nominal algebra models of ULAM (for the general theory of nominal algebra denotations see elsewhere [Mat07]). But ULAM proves this, in logic:
The rules of CORE are not syntax-directed (consider (tran)), but we can derive syntactic criteria for equality in CORE, which will also be useful later:
Write ds() for the set () , the difference set of permutations and . We write ds()# for a set of proof-obligations #, one for each ds().
precisely when one of the following holds:
and .
, and ds()#.
, and .
, , # and () .
, , and .
c and c.
For a proof see Appendix A; expanded details are also in [Mat07, Cor. 2.5.4]. Thus, CORE induces the same theory of equality as the rules for equality from [UPG04].
3 The -calculus
We give a short formal treatment of -terms and -equivalence.
Call a nominal term ground when it mentions no unknowns. 9
As discussed in Subsection 2.1 our nominal terms syntax is specialised to the -calculus; ground terms are characterised by:
Thus, ‘ordinary’ -terms are a subset of the nominal terms from Definition 2.3, obtained by exluding unknowns. This should be no surprise, since unknowns are in Definition 2.3 to represent meta-variables.
Define the free atoms fa by:
fa if and only if #.
Also, if atoms then #.
Define the size of a ground term by:
Fix an infinite set of atoms , such that is also infinite.
We define a capture-avoiding substitution action [] inductively on by:
In the clause for ()[] we make some fixed but arbitrary choice of fresh for each (so atoms
We fix and make our choice of fresh be from because this is convenient for our later proof of completeness of ULAM. This choice allows us to prove Lemma 3.15, which is needed to prove Lemma 4.13, and this in turn guarantees Lemma 4.17, which makes it easier for us to express a compact definition of the inverse translation in Definition 4.18, which is a key component of the proof of Completeness (Theorem 4.7). This pattern is repeated in Section 5.
Let -equivalence be the least transitive reflexive symmetric relation such that:
(Name-abstraction.) If [[] for fresh (so atoms()) then .
(Congruence for .) If then .
(Congruence for application.) If and then .
Suppose is a ground term.
(i) If fa then () .
(ii) If fa then [ () .
For the first part, we observe that since fa, any and that occur in must occur in the scope of and . We traverse the structure of bottom-up and rename these to fresh atoms (for example and which do not occur anywhere in ). Call the resulting term . Now () because atoms. Equality is symmetric, so we reverse the process to return to .
The second part then follows by an induction on □
On ground terms, derivable equality in CORE coincides with .
(See also [Mat07, Theorem 4.3.13].)
We must show that for ground terms ,
We prove the left-to-right implication by induction on the structure of , using the syntactic criteria for CORE-equality (Theorem 2.19). The cases of and c follow by reflexivity, and the case of follows by congruence using the inductive hypothesis. Now suppose , then there are two possibilities:
(i) and . Then by the inductive hypothesis, and we conclude by congruence.
(ii) , # and () . By Lemma 3.3 and some easy calculations we know fa(), so () by part 1 of Lemma 3.9 and symmetry. Also () by congruence and the inductive hypothesis. We conclude by transitivity.
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 from [[], where is fresh (so atoms()). By Lemma 3.3 we know # and #, with which we can show
by an induction on and
Now also [[] by the inductive hypothesis. Then we obtain
by (symm), (tran) and (cong[]).
By (perm) () and () , since # and #. Using (symm) and (tran) we conclude that . □
We do not quotient terms by -conversion and we do not use a nominal-style datatype of syntax-with-binding [GP01]. Later on the proof-method for Theorem 4.7 involves delicate accounting of what atoms appear abstracted in terms. In particular, we do not want to have to invent names (and keep track of our invented names) for abstracted atoms in Definition 4.18.
We conclude this section with some basic definitions and lemmas, which will be useful later.
Let (one step) -reduction be defined by:
()[].
If then .
If then .
If then .
Let (one step) -equality be defined by when or . Let (multi step) -equality be the least transitive reflexive relation containing and .
Let (one step) -contraction be defined by:
() if fa
If then .
If then .
If then .
Let (one step) -equality be defined by when or . Let (multi step) -equality be the least transitive reflexive relation containing , , and .
Define the bound atoms ba by:
For ground terms , :
(i) If and ba
(ii) If and ba
The first part is by routine calculations, using the fact that in Definition 3.6 we choose fresh atoms from .
The second part is trivial, since -contraction eliminates a bound variable. □
For ground terms , , :
(i) If and then there exists some such that and .
(ii) If and then there exists some such that and .
4 Soundness, completeness, and conservativity for
In Section 2 we presented nominal algebra and the theory ULAM. We saw formal derivations reminiscent of the ‘informal meta-level’. This informal meta-level is made formal using nominal terms; object-level variables become atoms, and meta-level variables become unknowns. ULAM axiomatises the -calculus up to -equivalence within this framework. Theorems 4.3 and 4.7 make that formal.
4.1 Soundness
Call a ground substitution for a set of unknowns when is ground for every . Call ground for when is ground for the set of unknowns appearing anywhere in , , or .
So: ground substitutions eliminate all metavariables.
Write when (Definition 3.12) for all ground substitutions for such that fa(()) for every #.
(Soundness) For any , , , if then .
We proceed by induction on ULAM derivations. We sketch the proof (some reasoning on freshnesses is elided):
The cases (refl), (symm), (tran), (cng) and (cngapp) follow by induction using the fact that is an equivalence relation and a congruence.
The case (perm). Suppose fa. By part 1 of Lemma 3.9, () and () follows.
The case (fr). Unknowns are irrelevant because ground terms by definition do not contain them. If mentions an atom which (fr) generates fresh for some in , , or , then we ‘freshen’ the atom further to avoid an ‘name clash’. 10
The case (ax). The axioms of ULAM are all standard properties of the -calculus:
4.2 Completeness and conservativity
Recall our choice of from Definition 3.5:
Fix a freshness context and two terms and . Let be the atoms mentioned anywhere in , , or , i.e. # atoms(). Let be the unknowns mentioned anywhere in , , or . For each fix the following data:
an order on the atoms in such that #;
two entirely fresh atoms and (so , and ).
Write for and for .
Specify a ground substitution for by:
Lemma 4.6 is easy and will be useful:
If # then fa(()).
(Completeness) If then .
The proof of this result uses the constructed above, and it is technical. Therefore, we defer it to Subsection 4.3 and mention Corollary 4.8 and Theorem 4.12, which are two forms of conservativity result for ULAM over CORE.
Suppose and are ground. Then if and only if .
Call a ground term a -normal form when no exists with .
Fix . Suppose that and contain no subterm of the form (). Then for the ground substitution from Definition 4.5, and are -normal forms.
() () for every appearing in , , . Applying this substitution to and cannot introduce subterms of the form (). □
implies .
We prove by induction on that if is a subterm of and a subterm of then implies .
The interesting case is when . Suppose (() (). Then it must be that (() ()). 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 take the form , for some such that ds()#. It follows that as required. □
(Conservativity) Suppose that and contain no subterm of the form (). Then
4.3 Proof of Theorem 4.7
Recall the definition of ba from Definition 3.14.
There exists a chain
where each is one of or , which is such that ba
By assumption , so by Lemma 4.6, we know . It follows that there is a chain
where each is one of or .
By construction, ba
Suppose is a link in the chain and such that ba
We iterate the replacement above as much as possible. Now suppose is a pair of links in the chain. Since is transitive, we replace this with .
It is easy to check that the final chain has the form
where ba
We can make the following definition:
Make a fixed but arbitrary choice of chain as specified in Lemma 4.13.
Let be the set of all atoms mentioned anywhere in the chain we fixed in Definition 4.14, and let be enriched with freshness assumptions # for every and every .
Call a ground term accurate when:
atoms
ba
are accurate.
Trivially, from the construction in Lemma 4.13 and from our choice of . □
Define an inverse translation from accurate ground terms to (possibly non-ground) terms inductively by:
We need some technical lemmas:
Suppose that is accurate. For any , if fa then #.
By induction on . The non-trivial case is when . If fa then and we must show
which follows using the rules for freshness and the fact that the atoms that might not be fresh for are precisely the . □
Suppose that is accurate. Suppose that is a permutation such that ( for all (). Then ()-1 ().
By a routine induction on . In the case of we use the fact that ( for all (). □
Suppose that and are accurate. Then implies .
By Theorem 3.10 coincides with . The proof is then by a detailed but routine induction on using the syntactic criteria of Theorem 2.19.
The only non-trivial case is when
We must show -1 -1. By transitivity and congruence, it suffices to show the following:
-1 ()
()
(() )-1 )-1. () and are accurate, so this follows by inductive hypothesis from our assumption that () . □
Suppose that (). Suppose that , , and [] are accurate. Then (())([])-1.
By induction on (Definition 3.4). We consider the cases in turn:
[]. ()( by axiom (var).
[] where (). So #, and ()( by axiom (#). (Recall that by our permutative convention, ranges over atoms other than .)
c[]. So #c, and (c)( c by axiom (#). (Recall from Definition 2.1 that c ranges over constant symbols.)
[] where . By assumption , so we must show
Using axiom (#) (and (tran) and (refl)) it suffices to show
This follows from Lemma 4.19 and the fact that fa(
[] where . By assumption , so we must show
Using axiom (#) (and (tran) and (refl)) it suffices to show
We derive this using the derivation rules for freshness (Figure 2).
()[]. ((-1))(() by axiom (#).
()[] where fa
()[] where fa By assumption is accurate, therefore (). By Definition 3.6, ()[] ([][]) for fresh (so atoms()). By assumption ([][]) is accurate, and so () and [][] is accurate. We must show
Note that by Lemma 4.19, # and #, and #() follows by (#b). Also #() is immediate by (#a). We present the rest of the proof as a calculation:
()[]. By axiom (app) and the inductive hypothesis.
The result follows. □
Suppose that and are accurate. If then .
()-1 , and ()-1 .
We prove by induction that if is a subterm of or then ()-1 is derivable.
The only interesting case is when . We must show that
Take a set of fresh atoms such that in bijection with ; so is disjoint from the and . Let # and . Then by (fr), it suffices to show
Now let ) () and ()) (()). We will need the following properties of derivability in CORE involving these permutations:
We can see this as follows:
Proof obligation (3) follows by uses of Lemma 2.16 (and 1 instances of (cng)), since for 1 ,
Proof obligation (4) follows by uses of Lemma 2.16 (and 1 instances of (cng)), provided that for 1 ,
By the rules for freshness, this follows from ()# since the are all disjoint and the are different from . We reason by cases on : () for all : then ()# by Definition 4.4. ( for some : then #.
Proof obligation (5): By Theorem 2.19 it suffices to show ds()#. That is, we must show that # for every such that ()()
We use the properties above to construct the following ULAM derivation, presented in a calculational style:
The result follows. □
We are now ready to prove Theorem 4.7:
5 Soundness, completeness, and conservativity for
Our proof-method works for the -calculus augmented with -conversion (extensionality) as well, and the proofs change only slightly. We outline how this works, emphasising only the parts of previous sections that need changing.
5.1 Soundness
We modify Definition 4.2 in the natural way:
Write when (Definition 3.13) for all ground substitutions for such that fa(()) for every #.
Soundness is just like Theorem 4.3:
(Soundness) For any , , , if then .
Just as for Theorem 4.3. The induction on ULAME derivations has one extra axiom case:
If fa then (.□
5.2 Completeness and conservativity
Definition 4.4, Definition 4.5 and Lemma 4.6 are unchanged. Completeness theorem 4.7 becomes:
(Completeness) If then .
We defer the proof to Subsection 5.3.
Corollary 4.8 becomes:
For any ground terms , if and only if .
Definition 4.9 and Lemma 4.10 are changed as follows:
Call a -normal form when no exists with or .
Fix . Suppose that and contain no subterm of the form () or () where #. Then for the ground substitution from Definition 4.5, and are -normal forms.
() () for every appearing in , , . Applying this substitution to and cannot introduce subterms of the form () or (). 11 □
Lemma 4.11 is unchanged, as it does not concern ULAM. Conservativity theorem 4.12 becomes:
(Conservativity) Fix some . Suppose that and contain no subterm of the form () or () where #. Then
5.3 Proof of Theorem 5.4
Lemma 4.13 and Definition 4.14 are changed as follows:
There exists a chain
where each is one of , , or , which is such that ba
Make a fixed but arbitrary choice of chain as specified in Lemma 5.9.
Definitions 4.15 () and 4.16 ( accurate) are unchanged. As before (Lemma 4.17), are accurate by construction. Definition 4.18 (the inverse translation ) is unchanged.
Lemmas 4.19 to 4.21 do not concern ULAM, and are unchanged. Lemma 4.22 becomes:
Suppose that (). Suppose that , , and [] are accurate. Then (())([])-1.
By Lemma 4.22, since a derivation in ULAM is also one in ULAME. □
Corollary 4.23 changes as follows:
Suppose that and are accurate.
If then .
If then .
Lemma 4.24 changes as follows:
()-1 , and ()-1 .
From Lemma 4.24, since a derivation in ULAM is also one in ULAME. □
We can now prove Theorem 5.4:
6 Conclusions
6.1 Related work
What are functions, from a(n algebraic) logical point of view? This question has been studied from many angles:
Lambda-lifting
‘Lambda-lifting’ introduces constant symbols to represent functions and adds axioms for them [Joh85]. This expresses functions, but the axiomatisation is of atomic constant symbols representing individual functions (as many as we would like to add) and not of the -calculus.
The issues of variables and binding surrounding the ‘’ in the ‘-calculus’ are avoided — or more precisely, they are relegated to the meta-level into the universal quantifiers used in the formula expressing the properties of each atomic constant symbol. Implementationally this can be extremely convenient but from a logical point of view we should consider this deeply unsatisfactory.
Combinatory algebra
Schönfinkel and Curry discovered combinatory algebra [Sch67,CF58]. The signature contains a binary term-former application and two constants S and K. Axioms are K and S)().
This syntax is parsimonious and the axioms are compact, but it is not natural or ergonomic to program in because it is impossible to go directly from a rule specifying a function, to the function itself — by -abstracting. In common with lambda-lifting, this must be done at the meta-level.
There is another mathematical issue inherent to combinators themselves: the natural encoding of closed -terms into combinatory algebra syntax ([Bar84, Section 7] or [Sel02, Subsection 1.4]) is unsound; it does not map -equivalent -terms to provably equal terms in combinatory algebra. We can strengthen combinatory algebra to lambda algebra by adding five more axioms [Sel02, Proposition 5] but the translation is still not sound; there exist -terms and such that the translation of is derivably equal to the translation of , but the translation of is not derivably equal to the translation of .
For soundness we need the Meyer-Scott axiom [Sel02, Proposition 20] (Selinger calls it ‘the notorious rule’). Thus, combinators do not capture the same functions as expressed by the -calculus.
Calculi of explicit substitutions
Calculi of explicit substitutions capture the -calculus in a first-order rewrite system; the idea originates in [ACCL92] and we note also Lescanne’s compact but readable survey [Les94]. If we orient the axioms of ULAM left-to-right then they become rewrite rules, and
— although ULAM has no explicit substitution term-former — if we consider a -reduct () as a(n implicit) substitution [] then we can view the axioms of ULAM as ‘pushing substitutions’ down into a term, step-by-step. Thus, a derivation of an equality in ULAM looks very much like a sequence of explicit substitution rewrites, just not necessarily all oriented left-to-right because equality is symmetric.
ULAM displays two other notable differences from explicit substitution:
The management of -equivalence (name-binding) comes from nominal techniques and is distinct from that explored in [ACCL92] or the subsequent literature. For an exploration of the computational cost of -equivalence in nominal terms (in the terminology of this paper; of equality up to CORE) see [Che04].
The syntax of ULAM includes unknowns , , which explicitly represent unknown terms. ‘Push a substitution down into a term’ is an analogy but it cannot always be fully realised; there is no way to push [] into (i.e. reduce () using (id), (app), or (abs)) because is an unknown. (#) resembles Bloo and Rose’s ‘garbage collection rule’ [BR95]. There the rule is dispensable — removing it does not affect the transitive symmetric closure of the reduction relation [BR95, Remark 2.15]. In contrast, there may be models of ULAM in which can denote an element which cannot be represented by a term. For this reason (#) is not admissible in the presence of (id), (app), and (abs).
Lambda Abstraction Algebras
Salibra’s Lambda Abstraction Algebras (LAA) [Sal00] are a -calculus version of cylindric algebra [HMT85]. There are many similarities with ULAM. For the convenience of the reader familiar with LAA syntax and semantics, a ‘cheat-sheet’ relating the material in this paper with definition 1, page 6 of [Sal00] is to the right.
ULAM exists in the nominal algebra framework; thus, at the level of syntax, there is one term-former for -abstraction. LAA includes infinitely many term-formers , , ,. . . ; and there are finitely many axioms and term-formers. This is because LAA uses ‘ordinary’ universal algebra, whereas in nominal algebra, -equivalence is handled primitively by the nominal algebra framework, and does not require special consideration in the signature or axioms.
Similarly, freshness side-conditions appear ‘hard-wired’ in LAA axioms. For example Salibra’s axiom from [Sal00, page 6] (()) is a version of (#) where the freshness condition is built into the structure of the term by writing . Nominal algebra handles freshness primitively (the ‘freshness judgements’ # of Definition 2.8). The notion of algebraic dependence from [Sal00, Definition 3] ‘() for some ’ corresponds with the negation of our freshness judgement ‘#’ (in a rather unfortunate notation clash with our notation for atoms, Salibra uses to range over arbitrary elements of a model). Algebraic (in)dependence is handled rigorously but informally (that is, in the prose discourse of the paper) in Salibra’s work; for us, the corresponding notion of freshness is a formal part of the syntax of nominal algebra judgements, and freshness has a denotation in nominal sets going back to the original work on nominal techniques [GP01], which places LAA ‘algebraic (in)dependence’ in a broader and more general mathematical setting.
For a general theory of models of ULAM, see the general theory of models of nominal algebra theories [Mat07]; recall that nominal algebra theories take models in nominal sets. Nominal sets have a finite-support property which, from the ‘cyclindic’ point of view, corresponds with a property which is known and studied under the name locally finite or locally finite dimensional [Sal00, Definition 7]. Models of ULAM are finitely-supported / locally finite by construction. 12
See the Related Work section of [Sal00] for further references to this and similar work.
Syntax quotiented by -equivalence
The definition of -equivalence on syntax is occasionally called ‘axiomatising the -calculus’, although it is just an equivalence relation on abstract syntax trees. However, if the -calculus syntax serves as the language of a logic with an equality judgement then -equivalence may have the status of axioms. For example Andrews’s logic [And86, 51] contains five axioms (41), (42), (43), (44), and (45) ([And86, page 164]). In fact these are axiom schemes, containing meta-variables A and B in the informal meta-level ranging over terms, and meta-variables , ranging permutatively over variable-symbols. A kinship with Figure 1 is apparent, though the axioms of ULAM exist in the formal framework of nominal algebra — a formal logic, not an informal meta-level. The interested reader might like to consider a formalisation of the arguments about in [And86] into a formal logic (not a nominal one) [Tan05].
Nominal techniques
A rewrite system for the -calculus appeared already in [FG07b] but without any statement or proof of completeness (indeed, it was not complete). More recently the authors have used nominal algebra to axiomatise first-order logic as a theory FOL [GM08b] and substitution as a theory SUB [GM08a].
One might suspect that the theory of substitution should be only a hair’s breadth away from that of the untyped -calculus, and could be obtained by imposing a type system (just as the simply-typed -calculus is related to the untyped -calculus). 13 Perhaps this will indeed prove to be the case, but so far all attempts by the authors to derive the properties of SUB from those of ULAM have tantalisingly failed. This may (or may not!) indicate the existence of a subtle mathematical point lurking in these systems; if there is, it seems to relate to the difference between -calculus variables and nominal algebra unknowns.
Nominal algebra has a cousin, nominal equational logic (NEL) [CP07]), which is very similar but makes slightly different design decisions. To the description of the relationship with nominal algebra given in [CP07] should be added that (unsorted) NEL is a subsystem of nominal algebra. The translation described and discussed in [GM09, Subsection 6.1.2]; it relies on the encoding of freshness using equality given in [GP01, equation 32]. NEL and nominal algebra both satisfy completeness results for a class of models in nominal sets [CP07,GM07,Mat07] (in other words — derivable equality coincides with validity in all models). The completeness results in this paper are stronger; they prove that derivable equality coincides with validity in particular models, which we built in this paper (Definitions 4.2 and 5.2). Similarly for the authors’ treatments of substitution [GM08a] and first-order logic [GM08b]. We know of no like treatments of substitution, logic, and the -calculus in NEL. If and when this is done it will be interesting to compare the results; one way to do this is to transfer results using the translation of [GM09, Subsection 6.1.2].
Some concluding remarks on names, variables, and functional abstraction
Nominal techniques are based on modelling names as atoms (urelemente) in set theory [Bru96,Gab00], an idea raised by the Gabbay-Pitts models of -abstraction and quantification [GP01]. These ideas find uses beyond the initial applications to syntax: in game theory and reasoning about pointers [AGM04,Tze07,BL05], spatial logics [LC04], and more.
Thus, there is now a body of work based on atoms, some concerned with reasoning on syntax-with-binding, some concerned with representing other things. Nevertheless, it always treats atoms as denotational entities in their own right rather than as a purely syntactic adjunct to a notion of function.
For us, nominal techniques are a general theory of names, and nominal algebra is a formal logic with which to instantiate this general theory to more specific theories.
-calculus style variables are names that can be functionally abstracted. 14 Nominal-style atoms are names that can be permuted and -abstracted. We have written down ULAM and ULAME and shown that they soundly and completely express those properties which, when added to nominal-style names, convert them into -calculus style variables. Conveniently, permutation then behaves like abstracted-then-applied variables (the device used, for example, in Miller’s higher-order patterns [Mil91] and in Salibra’s lambda-abstraction algebras [Sal00]) — and nominal-style -abstraction becomes -calculus style functional abstraction.
6.2 Future work and conclusions
ULAM completes a trio of papers studying (untyped) nominal algebra considered as a logical framework: first-order logic [GM08b], substitution [GM08a], and with this paper, the -calculus. Between them, these works cover a significant fraction of the typical syntaxes of interest in theory and practice of computer science. It would of course be interesting to seek common generalisations of the proof-techniques therein.
Our most immediate interest is in constructing a theorem-prover based on nominal algebra instead of the -calculus. We expect this to formally represent at least some kinds of reasoning better than the -calculus can, because the treatment of names and variables in nominal algebra, and nominal techniques in general, is very close to some kinds of informal practice (for example the pervasive use of meta-variables and freshness conditions, as appear in specifications of ... the -calculus). From that perspective this paper proves a vital correctness result.
It remains to understand the connections between standard models for the -calculus and the class of models determined by models of ULAM in nominal sets. It might also be interesting to construct versions of graph models or domain models of the -calculus [Bar84,Sto77] that themselves are built in nominal sets; does the presence of nominal-style atoms add any useful structure? Similarly, we can consider existing work using the language of categories (for example [Sel02,AB07]) using categories based on nominal sets.
A representation theorem for ULAM, in nominal sets models, would also be interesting. As a first step, in recent work we have proved an HSP theorem (also known as Birkhoff’s theorem) for nominal algebra [Gab09].
References
[AB07] Giulio Manzonetto Antonio Bucciarelli, Thomas Ehrhard. Not enough points is enough. In Proc. 21st International Workshop on Computer Science Logic (CSL 2007), volume 4646 of Lecture Notes in Computer Science, pages 298–312. Springer, 2007.
[ABI96] Peter B. Andrews, Matthew Bishop, Sunil Issar, Dan Nesmith, Frank Pfenning, and Hongwei Xi. TPS: A theorem proving system for classical type theory. Journal of Automated Reasoning, 16(3):321–353, 1996.
[ACCL92] Martín Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques Lèvy. Explicit substitutions. Journal of Functional Programming, 1(4):375–416, 1992.
[AGM04] Samson Abramsky, Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong, and Ian D. B. Stark. Nominal games and full abstraction for the nu-calculus. In Proc. 19th IEEE Symposium on Logic in Computer Science (LICS 2004), pages 150–159. IEEE Computer Society, 2004.
[And86] Peter B. Andrews. An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof. Academic Press, 1986.
[Bar77] Jon Barwise. An introduction to first-order logic. In Jon Barwise, editor, Handbook of Mathematical Logic, pages 5–46. North Holland, 1977.
[Bar84] Henk P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.
[Ber00] Chantal Berline. From computations to foundations via functions and application: the lambda-calculus and its webbed models. Theoretical Computer Science, 249(1):81–161, 2000.
[Ber06] Chantal Berline. Graph models of lambda-calculus at work, and variations. Mathematical Structures in Computer Science, 16(2):185–221, 2006.
[BL05] Nick Benton and Benjamin Leperchey. Relational reasoning in a nominal semantics for storage. In Proc. 7th Int’l Conf. on Typed Lambda Calculi and Applications (TLCA), volume 3461 of Lecture Notes in Computer Science, pages 86–101. Springer, 2005.
[BN98] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.
[BR95] Roel Bloo and Kristoffer Høgsbro Rose. Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection. In CSN-95: Computer Science in the Netherlands, 1995.
[Bru96] Norbert Brunner. 75 years of independence proofs by Fraenkel-Mostowski permutation models. Mathematica Japonica, 43:177–199, 1996.
[CDHL84] Mario Coppo, Mariangiola Dezani-Ciancaglini, Furio Honsell, and Giuseppe Longo. Extended type structures and filter lambda-models. In G. Lolli, G. Longo, and A. Marcja, editors, Proceedings of the Logic Colloquium ’82, pages 241–262, Amsterdam, the Netherlands, 1984. North-Holland.
[CF58] Haskell B. Curry and R. Feys. Combinatory Logic, volume 1. North Holland, 1958.
[Che04] James Cheney. The complexity of equivariant unification. In Proc. 31st Int’l Colloquium on Automata, Languages and Programming (ICALP 2004), volume 3142 of Lecture Notes in Computer Science, pages 332–344. Springer, 2004.
[Chu41] Alonzo Church. The calculi of lambda-conversion. Number 6 in Annals of Mathematics Studies. Princeton University Press, 1941.
[Coh65] P.M. Cohn. Universal Algebra. Harper and Row, New York, 1965.
[CP07] Ranald A. Clouston and Andrew M. Pitts. Nominal equational logic. Electronic Notes in Theoretical Computer Science, 172:223–257, 2007.
[dB72] N. G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indagationes Mathematicae, 5(34):381–392, 1972.
[FG07a] Maribel Fernández and Murdoch J. Gabbay. Curry-style types for nominal terms. In Types for Proofs and Programs (proceedings of TYPES’06), volume 4502 of Lecture Notes in Computer Science, pages 125–139. Springer, 2007.
[FG07b] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205(6):917–965, 2007.
[Fin85] Kit Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.
[Gab00] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
[Gab07] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205(7):982–1011, July 2007.
[Gab09] Murdoch J. Gabbay. Nominal Algebra and the HSP Theorem. Journal of Logic and Computation, 19(2):341–367, 2009.
[GM06] Murdoch J. Gabbay and Aad Mathijssen. Nominal Algebra. In 18th Nordic Workshop on Programming Theory, 2006.
[GM07] Murdoch J. Gabbay and Aad Mathijssen. A Formal Calculus for Informal Equality with Binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of Lecture Notes in Computer Science, pages 162–176. Springer, 2007.
[GM08a] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, June 2008.
[GM08b] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.
[GM09] Murdoch J. Gabbay and Aad Mathijssen. Nominal (universal) algebra: equational logic with names and binding. Journal of Logic and Computation, 2009. In press.
[GP01] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.
[HMT85] Leon Henkin, J. Donald Monk, and Alfred Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II.
[Joh85] Thomas Johnsson. Lambda lifting: transforming programs to recursive equations. In Conference on Functional programming languages and computer architecture, pages 190–203. Springer, 1985.
[KNO02] Andrew D. Ker, Hanno Nickau, and C-H. Luke Ong. Innocent game models of untyped lambda-calculus. Theoretical Computer Science, 272(1-2):247–292, 2002.
[LC04] Luca Cardelli Luís Caires. A spatial logic for concurrency (part II). Theoretical Computer Science, 322(3):517–565, 2004.
[Lei94] Daniel Leivant. Higher order logic. In D. Gabbay, C.J. Hogger, and J.A. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming, volume 2, pages 229–322. Oxford University Press, 1994.
[Les94] Pierre Lescanne. From lambda-sigma to lambda-upsilon: a journey through calculi of explicit substitutions. In Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’94), pages 60–69. ACM Press, 1994.
[Mat07] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.
[Mil91] Dale Miller. A logic programming language with lambda-abstraction, function variables, and simple unification. Journal of Logic and Computation, 1(4):497 – 536, 1991.
[NPP08] Aleksandar Nanevski, Frank Pfenning, and Brigitte Pientka. Contextual modal type theory. Proc. ACM Transactions on Computational Logic (TOCL), 9(3), 2008.
[Pau89] Lawrence C. Paulson. The foundation of a generic theorem prover. Journal of Automated Reasoning, 5(3):363–397, 1989.
[Pau96] Lawrence C. Paulson. ML for the working programmer (2nd ed.). Cambridge University Press, 1996.
[PE88] F. Pfenning and C. Elliot. Higher-order abstract syntax. In Proc. ACM SIGPLAN 1988 conference on Programming Language Design and Implementation (PLDI), pages 199– 208. ACM Press, 1988.
[Sal00] Antonino Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.
[Sch24] Moses Schönfinkel. Über die bausteine der mathematischen logik. Mathematishe Annalen, 92(3-4):305–316, 1924.
[Sch67] Moses Schönfinkel. On the building blocks of mathematical logic. In Jean van Heijenoort, editor, From Frege to Gödel: a source book in mathematical logic, 1879-1931. Harvard University Press, 1967. Translated from [Sch24] by Stefan Bauer-Mengelberg.
[Sel02] Peter Selinger. The lambda calculus is algebraic. Journal of Functional Programming, 12(6):549–566, 2002.
[Sto77] Joseph E. Stoy. Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press, Cambridge, MA, USA, 1977.
[Tak95] Makato Takahashi. Parallel reductions in lambda-calculus. Information and Computation, 1(118):120–127, 1995.
[Tan05] Li-Yang Tan. Formalizing the meta-theory of in Rogue-Sigma-Pi. In 17th European Summer School in Logic, Language and Information (ESSLLI), student session, 2005.
[Tho96] Simon Thompson. Haskell: The Craft of Functional Programming. Addison Wesley, 1996.
[Tze07] Nikos Tzevelekos. Full abstraction for nominal general references. In Proc. 22th IEEE Symposium on Logic in Computer Science (LICS 2007), pages 399–410. IEEE Computer Society, 2007.
[UPG04] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
A Syntactic criteria for CORE-equality
For completeness we include a proof of Theorems 2.19. Note that this is a basic result of theory CORE and hence of nominal algebra in general; it does not have to do with the -calculus, or with ULAM.
We will show that theory CORE is equivalent to an existing notion of -equivalence on nominal terms, which is syntax-directed by definition [UPG04,FG07b]. Definition A.1 was introduced in [UPG04, Figure 2] (except that here, our syntax is specific to the -calculus):
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 A.1.
() () and id .
By routine inductions on . The only interesting case is for the first part: by Definition 2.5 we can verify that
□
Recall the notion of difference set ds() of two permutations and from Definition 2.18. Lemma A.3 shows how theory CORE can mimic the (Ds) rule of :
If ds()# then .
We work 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 instance of (perm) here is valid because by Lemma A.2 ((() ()) ) ((
The following proof obligations remain:
()# follows from -1(())# by an easy calculation. Now this is one of the assumptions ds()#: by Definition 2.18, we know that -1(()) ds() when (()-1((()))
()# follows from # by an easy calculation. This follows directly from assumption ds()#, since ds().□
(Equivalence of CORE and ) is derivable if and only if is derivable using the rules of Figure A.1.
The left-to-right direction is by induction on the structure of nominal algebra derivations of . By the inductive hypothesis it suffices to show the following:
Syntax-directed equality is an equivalence relation and a congruence. This is [FG07b, Theorem 24].
If # and # then () . By induction on .
If where then . By straightforward induction on the structure of derivations of .
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 . This is Lemma A.3.
If and then . This is (congapp).
c c. This is an instance of (refl).
If then . This is (cong).
If () and # then . Suppose that Π and are derivations of () and # respectively. Then the following is a derivation of :
Notes
1 We thank an anonymous referee of a previous paper for comments which set us on the path to writing this one, the anonymous referees, and Chantal Berline for comments and support. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid. ↩
2 Homepage: http://www.gabbay.org.uk ↩
3 Email: a.h.j.mathijssen@tue.nl ↩
4 See [NPP08, Section 7] for an outline of how a similar idea can be implemented in a completely different kind of language. ↩
5 For the impatient: a nominal set is a set with a name-permutation action. Name-binding is formed by a construction very similar to taking -equivalence classes; we use the permutation action to ‘rename’ the name to be bound and taking an equivalence class of all the renamed variants.
Nominal sets can be considered as sheaves, or as algebraic structures. They were introduced in [GP01]; see that paper for full details. ↩
6 This is terminology from cylindric techniques (see [Sal00, Definition 7] or [HMT85]). Nominal sets terminology calls this finitely-supported and infinitely-supported respectively. ↩
7 Besides being useful in what follows, this models common practice: if we ask the reader to ‘consider two variable symbols and ’ then we have no control over, for example, their handwriting, and thus over the symbols which they actually commit to the page. What matters is that the two variable symbols are different. ↩
8 It is a fact that (symm) and (tran) are admissible rules in CORE (a proof can be constructed using Theorem 2.19 below). This property fails in the presence of axioms, for instance, the axioms of ULAM and ULAME. On the other hand, we can view (refl) as sugar for the derivation given above using (perm), in any theory. ↩
9 Ground terms should not be confused with closed lambda terms, i.e. terms without free atoms; closed terms are not used in this paper. ↩
10We retain the inductive hypothesis of the ‘freshened’ derivation using the mathematical principle of ZFA equivariance [GM08b, Appendix A] — or by performing induction instead on the depth of derivations, and proving that freshening atoms does not affect this measure. ↩
11We chose in Definition 4.4, and ‘wrapped’ in in Definition 4.5, specifically to prevent accidental -contracts here. ↩
12It may be prudent to note that being finitely-supported / locally finite does not mean that in nominal sets we cannot consider models including infinitary syntax. Nominal sets are consistent with infinitary syntax, so long as it mentions only finitely many free variables; it can mention as many bound variables as we like, including infinitely many. For a nominal-style theory of objects with infinite support, and in particular infinitary syntax with potentially infinitely many free variables, see [Gab07]. ↩
13We briefly give some intuition for what SUB is: (())( is derivable in ULAM, but only app()[ lam([] app(lam([])) is derivable in SUB (notation from [GM08a]). ↩
14This marks a difference from combinators, which share a notion of functional application with the -calculus but not the notion of functionally abstracting variable symbols. ↩