The Lambda-Calculus is Nominal Algebraic
1 Introduction
The -calculus is fundamental in the study of logic and computation. Partly this is because it is a tool to study functions and functions are an important object of study in this field. Partly this is because the -calculus seems to be, for homo sapiens, an ergonomic formal syntax.
-terms are inductively defined by
In this paper we will write -[ -] as shorthand for (-)-. Thus [] stands for () and not for the term resulting from ‘substituting for in ’ (we write that as [], see Definition 44).
The -calculus represents functions in programming languages [25, 31], logic [7, 20], theorem-provers [3, 24], higher-order rewriting [5], and much more besides. However, the ‘’ in the -calculus has proved resistent to a treatment in universal algebra [8]. For example the property that
“()[([]) when does not occur free in ”
cannot be represented in an algebraic framework, at least not obviously so, because of the freshness condition ‘ does not occur free in ’ which is necessary to avoid ‘accidental capture’ by . Similarly for the property “( when does not occur free in ”.
Nominal algebra is a form of universal algebra enriched with primitive constructs to handle names, binding, and freshness conditions — just like those that appear in informal specifications of the -calculus and other languages with binders. Nominal algebra has the feature that, thanks to the enriched constructs, it allows fully formal algebraic reasoning which is pleasingly close to informal practice, including explicit reasoning on -renaming and freshness side-conditions.
In this paper we introduce ULAM (Figure 1), a nominal algebra theory for the untyped -calculus. The axioms of ULAM make fundamental use of characteristic ‘nominal’ features of nominal algebra:
We use nominal unknowns , , and to represent unknown elements. Instantiation of nominal unknowns does not avoid capture; see Definition 11.
Freshness conditions #, #, and # are a framework to prevent ‘accidental capture’ of names by binders.
We shall prove that ULAM is sound and complete with respect to a model constructed out of -terms quotiented by -equivalence; the rest of the paper makes these observations formal.
Nominal techniques subscribe to a mathematical view according to which names are first-class entities in the denotation. This was used, for example, to develop the Gabbay-Pitts quantifier and the Gabbay-Pitts model of -abstraction [17]. A traditional view is that names arise as a syntax for talking about inputs to functions, and therefore they range over elements of the underlying domain.1 The -calculus expresses this latter idea. With ULAM our nominal algebraic axiomatisation of the -calculus we make a novel connection between the two worlds; the axioms of ULAM express the properties that must be added to convert a nominal-style atom into a -calculus style variable, and a nominal-style abstraction into a -calculus binding.
Map of the paper. Section 2 introduces nominal algebra, giving basic definitions and results about syntax, freshness conditions, equality, and nominal algebra theories. Section 3 introduces the syntax and operational semantics of the untyped -calculus. Section 4 proves that ULAM is sound and complete (Subsections 4.1 and 4.2), and that it is conservative over the native nominal terms theory of -equivalence (Subsection 4.3). The most technical material in this paper is concentrated in the proofs in Subsection 4.2. Finally, Section 5 discusses related and future work.
2 Nominal algebra
2.1 The syntax of nominal terms
We define a syntax of nominal terms. It is tailored to our application to the untyped -calculus; see elsewhere for general treatments [32, 13, 14, 23].
Fix the following:
A countably infinite set of atoms . We let range over atoms. These model -calculus variables.
We use a permutative convention that and range permutatively over atoms unless stated otherwise. For example in (#ab) from Figure 3, and in (perm) from Figure 4, and range over any two distinct atoms.
A countably infinite collection of unknowns. We let range over unknowns. These represent unknown elements in nominal algebra axioms.
We also use a permutative convention that and range permutatively over unknowns. In Figure 1 we make a fixed but arbitrary choice of unknown. That is, ULAM contains five axioms — not infinitely many for every possible , , , , and — but the choice is immaterial for all practical purposes as we shall see in (ax) of Figure 4 and in Definition 25.
A possibly infinite collection of constant symbols c C.
Unknowns, atoms, and other distinct syntactic classes, are assumed disjoint.
For the reader’s convenience we provide Figure 2: a ‘cheat-sheet’ linking in a single list concepts from informal practice to some of the main definitions and lemmas which will soon follow. This list, by its nature, contains forward references.
We can now set about building the machinery of nominal algebra.
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 words: For ‘most’ atoms is the identity.
Let terms be inductively defined by:
We write syntactic identity of terms as to distinguish it from ‘=’ the derivable equality-in-freshness-context we construct in Subsection 2.3. Note that if then , since permutations are represented by themselves. Also note that we do not quotient terms in any way.
We give some intuition of terms:
An atom represents a -calculus variable symbol.
We call a moderated unknown. This represents an unknown term, on which a permutation of atoms will be performed when is instantiated. The use of permutations provides primitive support for -equivalence.
represents the usual -calculus application.
represents the usual -abstraction. Recall from the Introduction that we write [] as shorthand for (), for example in Figure 1.
A typed version of this syntax is possible; the interaction between atoms, unknowns, permutations, and -abstraction raises subtle and unexpected issues which have been investigated independently in the general framework of nominal rewriting [12]. Types would cause no essential difficulties for the results which follow.
2.2 Permutation, substitution and freshness
We need some more notation to talk about permutations (Definition 4).
As usual we 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: 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; note that this is the same permutation as (). We may drop between swappings, writing for example () () as ()(); this is a standard notation in the theory of permutations. We may write as shorthand for id .
We write when () . We extend this inductively to as follows:
If is not derivable write . We read ‘’ as ‘ occurs in’.
We also write when occurs anywhere in , and otherwise. Occurrence is literal, for example and () .
Define a permutation action inductively by:
Intuitively propagates through the structure of until it reaches an atom or a moderated unknown. Note that in the clause for , acts also on the ‘’. Following Cheney (verbal communication) we say that the permutation action is inherently capture-avoiding, meaning that it can act uniformly and will not require special behaviour for binders. For example:
() () and id .
By an easy induction on the structure of using the fact that composition of permutations is just composition of functions and so is associative.
We call a substitution a function from unknowns to terms. We write [] for the substitution mapping to for 1 , and mapping to for all other .
Define a substitution action inductively by:
We may call an instance of .
For example:
The final example is direct from the definition and Lemma 9; () is ‘the function applied to ’, whereas is shorthand for (id ).
Intuitively, propagates through the structure of until it reaches an atom or a moderated unknown. ‘evaporates’ on an atom , and on it instantiates to () — then the permutation acts on
Substitution does not avoid capture; ()[] . There is an deliberate analogy here with context substitution, which is the substitution used when we write ‘let - be in -’, or ‘suppose is in ’; we obtain . Moderated unknowns behave exactly like the ‘hole’ - in syntactic contexts — except that an unknown can occur multiple times in a nominal term; unknowns occur in terms with a moderating permutation because this is needed, along with freshness contexts, to manage -equivalence.
Recall from Definition 11 that ()(). This extends easily to all terms:
() ().
By induction on . The only interesting case if when . Then unpacking definitions
The result follows by Lemma 9.
A freshness (assertion) is a pair # of an atom and a term. We call a freshness of the form # (so ) primitive. We write ∆and for (finite, and possibly empty) sets of primitive freshnesses and call them freshness contexts.
We may drop set brackets in freshness contexts, e.g. writing ## for ##. Also, we may write # for ##. We write ∆when # ∆for some , and ∆when # ∆for some .
A sequent style presentation of Figure 3 is also possible; for example (#X) becomes and we need a new rule where the ‘’ in the bottom line is shorthand for id and square brackets indicate a side-condition.
We write ∆ # when a derivation of # exists using the rules of Figure 3, such that the assumptions are elements of ∆. In words, we say “# is derivable from ∆”. We usually write # as #.
For example #, #, and ##():
The example of # demonstrates that #, whose intuitive reading is ‘is not free in’, differs from , whose intuitive reading is ‘does not occur in’.
The derivation rules are completely syntax-directed. Therefore:
1. # always.
2. If # then #.
3. If # then ()#.
4. # always.
5. If # then #.
6. If # then # and #.
7. #c always.
By an easy induction on the structure of the derivation rules in Figure 3.
We can strengthen the freshness context ∆in freshness derivations:
If ## and then #.
We transform a derivation of ## into a derivation of #:
If ## by assumption then ## ∆. Since , we know # ∆, and we conclude ∆ # by assumption. The case of # is similar.
(#X): Suppose ## is derived using (#X). Then #()#. By assumption , so (. Since also , we know () . By the inductive hypothesis and the simple fact that we obtain ∆ ()#. We conclude ∆ # using (#X). The case of # is similar.
(#ab), (#a) and (#c) carry over directly.
(#b) and (#app) are straightforward using the inductive hypothesis and the following facts: if then , and if then and .
Freshness context weakening also holds and is part of a more general result; see Theorem 21.
Equivariance is a characteristic property of nominal techniques. Equivariance arises from the use nominal techniques make of permutations as opposed to renamings (possibly non-bijective functions on atoms). Intuitively, equivariance states that if something is true, then it should remain true if we permute atoms. Formally we write:
If # then ()#.
By induction on the structure of derivations of # from ∆. The only non-trivial case is (#X). Suppose # is derived from ()# using (#X). We must show that ()#() . This follows from ()-1(())#. It is a fact that ()-1(((). The result follows.
Lemma 19 is part of a collection of equivariance properties and these are responsible for much of the technical convenience of the nominal treatment of names. See for example [32, Lemma 2.7], [13, Lemma 20], [16, Appendix A], and [17, Lemma 4.7].
We can extend the substitution action to freshness contexts:
We write
Intuitively read this as ‘apply to every
We write ∆ when ∆#() for every #
Note that ∆ need not be a freshness context, because it might contain # for not an unknown.
For any , , if # and then #.
As a corollary, 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 19. The corollary follows taking
2.3 Equality, axioms and theories
We call a pair an equality (assertion). We call the pair of a freshness context and an equality an axiom. We may write as .
We call a set of axioms T a theory. The theories needed in this paper are:
CORE: the empty set of axioms.
ULAM: the axioms from Figure 1.
Theory ULAM axiomatises a non-extensional -calculus. An extensional version is obtained if we add the following axiom to Figure 1:
We see no difficulties with extending the results of this paper to the extensional case.
A word on the history of the ideas behind ULAM: ULAM grew out of SUB [15], which was based on a nominal rewrite system for the -calculus [13, Example 43], which was itself based on an example signature used in nominal unification [32, Example 2.2]. The axioms of ULAM directly and deliberately identify nominal abstraction [] (notation in the style of [32, 15]) with -abstraction , and nominal substitution sub() with -calculus application . In [32, 13, 15] term-formers such as -abstraction and application exist separately and a sort-system ensures for example that the in sub() is an abstraction:
is a unary term-former. It takes a nominal abstraction as an argument and returns a term of base sort. In the style of [15, 32] we write that it has arity ([]).
Substitution is a binary term-former sub with arity ([]).
The direct identification of nominal abstraction with -abstraction, and substitution with application, is possible because terms of ULAM are unsorted (i.e. all terms have base sort, including abstractions) and because nominal algebra allows us to assert the relevant equalities in a logical framework.
Define derivability on equalities in natural deduction style by the rules in Figure 4. We 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 briefly discuss the most interesting rules of Figure 4:
(perm). This rule provides us with a concise way to express -equivalence. See Lemma 28 and Theorem 49 for formal expressions of this intuition.
(ax). This rule formally expresses how we obtain instances of axioms: instantiate unknowns by terms (using substitutions) and rename atoms (using permutations) such that the hypotheses are corresponding instances of freshness conditions of the axiom. In this rule ranges over substitutions, ranges over permutations, and stands for the hypotheses #
The reader might expect the premise of the axiom rule to be instead of . It turns out that both versions are correct, because of Lemma 19 if and only if ∆ for any ∆.
(fr). This rule allows us to introduce a fresh atom into the derivation. In (fr) the square brackets denote discharge in the sense of natural deduction, for example as in implication introduction [19]; ∆denotes the other assumptions of the derivation of . In sequent style (fr) would be ().
We will always be able to find a fresh atom, no matter how unknowns are instantiated, since all our syntax is finite and can never mention more than finitely many atoms.
To provide some intuition for these rules, we give a number of examples.
The (perm) rule allows us to show standard -equivalence properties such as and (():
Note that we use () and () () () in the conclusions of the derivations.
We give a full derivation of (()). We use the shorthand from the Introduction to write for example (()) as ()[].
The examples above do not showcase the full power of nominal terms, because we are not reasoning on terms containing unknowns. The raison d’étre of nominal terms is their unknowns and how their interaction with permutations and freshness allow us to manage -conversion. We now consider examples of derivations with -renaming and freshness in the presence of unknowns:
#[) )[]
De-sugaring we must derive ()() ) from #:
The instance of (perm) relies on the fact that () () .
The usual proof of the substitution lemma is by induction on but now is just a formal symbol and part of the syntax — but instead, the axioms of ULAM capture this behaviour.
By (tran) it suffices to derive
and
from # . The first part follows by axiom (app). The second part can be derived as follows:
The following lemma formally connects the usual use of substitution to handle -renaming, with the unusual treatment of -renaming which is primitive to nominal terms, based on permutations.
#[) .
We sketch the derivation:
In this derivation the superscript number one 1 is an annotation associating the instance of the rule (fr) with the assumption it discharges in the derivation. Note how we use (fr) to generate a ‘fresh atom’.
If # for every unknown in , and , then #.
By an easy induction on using the rules in Figure 3.
We write ds() for the set () , the difference set of permutations and . We write ∆ ds()# for a set of proof-obligations ∆ #, one for each ds().
Figure 4 contains some redundancy; (refl) may be emulated using (fr) and (tran) as follows:
Here are chosen fresh (so and ). The vertical dots elide derivations described in Lemma 32.
It is convenient in a logic of equality to be able to derive that without ‘going round the houses’ with (tran) and (fr), so we include both (perm) and (refl).
(perm) and (refl) are both instances of the following rule:
Here ds()# is shorthand for the set of # for all ds(), if any. This rule looks complicated, so we do not use it in Figure 4.
We can derive syntactic criteria for determining equality in CORE. These will be useful later:
precisely when one of the following hold:
1. and .
2. and and ds()#.
3. and and .
4. and and # and () .
5. and and and .
6. c and c.
For all there are and such that .
By Theorem 35 is never derivable.
It is decidable whether is true or not.
By an easy induction on , using the syntactic criteria of Theorem 35.
A number of properties on freshnesses also hold for equalities of any theory T. For instance we can strengthen the freshnesses context ∆in equational derivations:
If # and and , then .
We extend the derivation with (fr).
Also we may permute atoms and instantiate unknowns in equational derivations:
If then .
By induction on the structure of the rules of Figure 4.
For any T, , , if and then .
Analogous to the proof of Theorem 21.
In the case that mentions a ‘fresh’ atom used in an instance of (fr), we rename that atom to be ‘fresher’. The inductive hypothesis is valid also for the ‘freshened’ derivation because of the mathematical principle of ZFA equivariance ([16, Appendix A] or [17]); induction on a measure of the depth of derivations is also possible, subject to uninteresting lemmas that renaming atoms does not change depth.
3 Untyped -terms
We call a term ground when it mentions no unknowns. Ground terms are inductively characterised by the grammar in Definition 1.
It is no coincidence that ground terms are characterised by Definition 1; as discussed in Subsection 2.1 the syntax of nominal terms used in this paper is specialised to the intended application.
The rest of this section sketches a formal development of the syntax and operational semantics of -terms and -reduction, and links it to the ‘nominal’ exposition. For more detailed treatments of -terms and -reduction see elsewhere [2, 6].
Define the free atoms fa() inductively by:
This is standard.
fa if and only if #.
Also, if (Definition 7) then #.
By routine inductions on the structure of .
Define the size of a ground term inductively by:
We define a capture-avoiding substitution action [] inductively on the size of by:
In the clause for ()[] we make some fixed and arbitrary choice of fresh (the ‘ fresh’), for each .
A basic property is useful in the proofs of the results which follow:
Capture-avoiding substitution of atoms for atoms preserves size. More formally, []
By an easy induction on
fa([]) (fa) fa
Also, if # then #[].
The first part is by a routine induction on size. For the second part we prove the contrapositive. By Lemma 43 it suffices to show that fa([]) implies fa(). This also follows by a routine induction on the size of .
We introduce the usual notion of -equivalence.
We write = for the -equivalence relation, which is obtained by extending syntactic equivalence with the following rule to rename bound variables:
when [[] for some fresh atom
The following lemma shows how permutations interact with =:
1. If fa then () .
2. If fa then [ () .
For the first part, we observe that all and 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 . Equality is symmetric, so we reverse the process to return to .
The second part follows by an induction on
Derivable equality in CORE coincides with on ground terms.
We do not quotient terms by -conversion and we do not use a syntax based on a nominal-style datatype of syntax-with-binding [17]. This is because the proof of Theorem 57 involves keeping careful track of what atoms do and do not appear in terms, and if we quotient by -equivalence now we lose information — names of abstracted atoms — which is useful for expressing that proof.
Let -reduction be inductively defined by:
We call a -normal form when there is no such that .
We write when there exist and such that
We write = for the transitive reflexive symmetric closure of .
is confluent.
See elsewhere [6].
4 Soundness, completeness, conservativity
4.1 Soundness
We call a substitution ground for a set of unknowns when () is ground for every . We call ground for ∆ when is ground for the set of unknowns appearing anywhere in ∆, , or .
fa(
It is now easy to state and prove a notion of soundness for ULAM:
Suppose that is a ground substitution for , , and . Suppose further that fa(()) for every #. Then:
# implies fa().
implies .
We proceed by induction on ULAM derivations.
We consider the rules in Figure 3 in turn:
By assumption. We must show that if # ∆then fa(()), which follows by our assumptions on .
The case (#ab). It is a fact of Definition 42 that fa
The case (#a). It is a fact that fa(()).
The cases of (#b), (#app), and (#c) are no harder.
The case (#X). By Lemma 54, fa() if and only if
We consider the rules in Figure 4 in turn:
The cases (refl), (symm), (tran), (cong) and (congapp) follow by induction using the fact that = is an equivalence relation and a congruence.
The case (perm). Suppose that fa(). Then () follows by Lemma 48, since = implies =.
The case (ax). It remains to check the validity of the axioms of ULAM. It suffices to verify that:
– (var). We must show
for any permutation and substitution . This follows from the property that
always (i.e. for any atom and ground term ), which is a fact about -equivalence.
– (#). Suppose that (())[() (() is derived from ()#() using the assumptions from ∆. By inductive hypothesis, we know () fa((())). We must show ((()))[() (()) (()). This follows from the basic fact about -equivalence that
always. Other cases are similar:
– (app). ()[ ([])([]).
– (abs). If fa() then ()[([]).
– (id). [.
The case (fr). If necessary, we rename the fresh atom in (fr) to a ‘fresher’ atom. By ZFA equivariance ([16, Appendix A]), the inductive hypothesis also holds for the ‘freshened’ derivation, and the result easily follows.
4.2 Completeness
We start with a weak form of completeness:
For ground terms and , if then .
It is not hard to prove this by concrete calculations, but it also follows as a corollary of the following more powerful result:
Suppose that for every substitution such that
is ground for and
fa(()) for every #.
Then is derivable.
The proof occupies the rest of this section. Fix some freshness context ∆and two terms and .
Let be the atoms mentioned anywhere in ∆, , or . Let be the unknowns mentioned anywhere in ∆, , or . For each fix the following data:
An order on the atoms in such that #
Some entirely fresh atom .
We write for the set .
Specify a ground substitution for by:
If # then fa(()).
By construction of
By assumption . The untyped -calculus is confluent (Theorem 52) so and rewrite to a common term, call it :
Fix two chains
Without loss of generality we assume these -conversions and -reductions do not introduce abstractions by atoms from .
Let be the set of all atoms mentioned anywhere in the chains of Definition 61, extended with a set of fresh atoms
in bijection with . (So is disjoint from and from all atoms mentioned , , , .) Let ∆ be ∆enriched with freshness assumptions # for every and every .
We call a ground term accurate when:
mentions only atoms in .
never occurs abstracted. That is, no term contains ‘’.
appears, if it appears at all, in head position applied to a list of terms in a subterm of the form ‘ ’.
Note that and are accurate by construction of and and by the nature of -conversions and -reductions.
Define an inverse translation from accurate terms to (possibly non-ground) terms inductively by:
The inverse translation -1 is an inverse of in the following sense:
()-1 , and ()-1 .
We prove by induction that if is a subterm of or then ()-1 .
The only interesting case is when . We must show
where ) ().
Take ()) (()). By transitivity it suffices to show:
The first part follows using Lemma 30 when, for 1 ,
By the rules for freshness, this follows from ∆()# since the ()() are all disjoint. We conclude using a case distinction on
() for all : then ()# since ()#
( for some : then # by definition.
We still have to show that ∆ () . It is convenient to show the stronger property ∆ () . By Theorem 35 we need only show that ∆ ds()#. That is, we must show that ∆# 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 reader might wonder why the inverse mapping of the renames to the fresh . Consider for example () in the empty freshness context , so we do not know # or #. Then
By calculations we can verify Lemma 65:
where ###. Had we left out the renaming to fresh atoms then (() ) would be [][], which is not equal to () , since for example
A technical lemma about freshness will be useful.
Suppose that is accurate. For any , if fa then #.
By induction on . The only non-trivial case is when . Suppose fa(). Then and we must show
where ) (). We distinguish two cases:
for some : then #() by (#a), and the result follows by the rules of freshness using the inductive hypothesis.
for all : then () for all , so ()# by definition. The result follows using the rules for freshness and the inductive hypothesis.
We need a technical lemma:
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 if then .
By Theorem 49 coincides with . We therefore work by induction on the structure of using the syntactic criteria of Theorem 35.
The only non-trivial case is when
By assumption (). By Lemma 67 we have ∆#. By inductive hypothesis ∆ (() )-1 . By Lemma 68 we have ∆ (() )-1 ) (). From the rules for freshness and equality ∆(() follows.
Suppose that . Suppose that , , and [] are accurate. Then [[])-1.
We work by induction on the size of :
[]. [ by (var).
[]. [ by (#) since ∆#. The cases of ()[] and c[] are similar.
()[] where fa We must show
By the inductive hypothesis and the rules for equality, it suffices to show
By Lemma 67 we know ∆#. The result follows from (abs).
()[] where fa By assumption is accurate, therefore .
Recall from Definition 44 that ()[] ([][]) for some choice of fresh (so fa() and fa()). Now by assumption ([][]) is accurate, so and [][] is accurate.
We must show
Note that by Lemma 67# and ∆#, and therefore #() by (#b). Also ∆#() is immediate by (#a). We present the rest of the proof in a calculational style:
The result follows by transitivity.
()[]. By the inductive hypothesis and the rules for equality, (()())[)[])-1 follows from
We conclude using axiom (app).
[] where . By assumption , so we must show
By assumption for all 1 , therefore also fa By Lemma 67 also ∆#. Then we can show by a number of applications of axiom (abs) that (())[] is equal to ()[]. By the rules for equality, it suffices to show
By axiom (#) this follows if ()#. There are two possibilities:
– for some : then (, and # by definition.
– for all : then (, and # by definition.
The result follows.
Suppose that and are accurate. If then .
We are now ready to prove Theorem 57:
4.3 Conservativity over CORE
We can exploit the from Subsection 4.2 to prove conservativity of ULAM over CORE.
Fix . Suppose that and contain no subterm of the form []. Then for the ground substitution constructed in Subsection 4.2, and are -normal forms.
() for every appearing in ∆, , or . Applying this substitution to and cannot introduce subterms of the form [].
Suppose that and contain no subterm of the form []. Then
A derivation in CORE is also a derivation in ULAM so the right-to-left implication is immediate.
Now suppose that ∆ . We construct as in Subsection 4.2. By Theorem 55, . By Lemma 72 we know that and are -normal forms. By confluence of the -calculus (Theorem 52), .
We now prove ∆ by induction on . The calculations are detailed but entirely routine. We consider just one case, the hardest one:
Suppose . Then () (). By Theorem 35, if 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 it follows that must have been equal to , for some , such that ds()#. It follows that ∆ as required.
5 Conclusions
5.1 Related work not using nominal techniques
-equivalence on -calculus syntax is a good idea; we find it realised in different ways in different systems. If the -calculus syntax in question serves as the language of a logic, then -equivalence may have the status of axioms. For example Andrews’s logic [1, 51] contains five axioms (41), (42), (43), (44), and (45) ([1, page 164]). In fact they are axiom schemes, containing meta-variables A and B in the informal meta-level ranging over terms (and also meta-variables , ranging permutatively over variable-symbols). The relationship which Figure 1 bears to them is clear but here, axioms feature in the formal framework of Nominal Algebra — a formal logic, not an informal meta-level. We claim that Nominal Algebra captures part of the ‘informal meta-level’ in which researchers routinely work — and that within that, ULAM captures the (untyped) -calculus.
Salibra’s Lambda Abstraction Algebras [28] axiomatise the -calculus using universal algebra. The method is cylindric in the sense of cylindric algebras [18]; abstraction is represented by infinitely many term-formers (there is a term-former ‘’ for every ) and freshness is encoded in the structure of the terms in the following sense: consider Salibra’s rule () from [28, page 6]:
We can rewrite this in our notation as ()[ and this is a version of (#), where the freshness condition # has been built into the structure of the term by replacing with . Similarly Salibra’s rule
can be rewritten in our notation as ([([][]) and this plays an analogous rôle to our Lemma 28. The notion of dimension set [28, Definition 4] corresponds to freshness. The proof of a main result, Theorem 13 of [28] (first carried out by Salibra, improved by Selinger), uses definitions reminiscent of, though not identical to, Definitions 58 and 59. The ‘nominal’ techniques give a clear separation of the parts having to do with names and abstraction, and the parts having to do with and application, which is not possible with Lambda Abstraction Algebras. However, Salibra’s results [28, 22] show what can be achieved using algebraic methods.
Curry discovered combinatory algebra [10]. The signature contains a binary term-former application and two constants and . Axioms are and )(). This syntax is parsimonious and the axioms are compact, but it is not natural or ergonomic to program in; that most ergonomic feature of the -calculus which makes it so very useful in practice, the , is missing. There is also a mathematical issue: the natural encoding of closed -terms into combinatory algebra syntax ([6, Section 7] or [29, Subsection 1.4]) does not map -equivalent -terms (() and ) to provably equal terms in combinatory algebra. This is resolved if we strengthen combinatory algebra to lambda algebra by adding five axioms, due to Curry [29, Proposition 5]. However the translation is still not sound, in the sense that 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 . To ensure soundness, we must add the Meyer-Scott axiom [29, Proposition 20] (Selinger calls it ‘the notorious rule’).
In short, combinators do not capture the model of functions expressed by the -calculus. Selinger [29] identifies the problem with the interpretation of variables and argues for denotations with fresh ‘indeterminates’; this reminds us of nominal techniques with its set of atoms in the denotation and well-developed theories of freshness.
-calculi of explicit substitution decompose the substitution used in -reduction into many explicit reduction steps [21]. This is similar to the way ULAM breaks down the calculation of an equality into many explicit algebraic equalities. A calculus of explicit substitutions is a calculus, not a logic; all reasoning using calculi occurs informally in natural language. ULAM on the other hand is intended to support algebraic reasoning on the -calculus within a formal framework, while remaining very close to informal practice.
5.2 Related work using nominal techniques
The first application of nominal techniques was to datatypes of syntax with binding [17]. The syntax of the untyped -calculus is often used as a paradigmatic example of such a datatype. This paper is not another such study. ‘The -calculus’ studied in some other publications — using nominal sets [17], nominal logic [27], and also using higher-order abstract syntax [26], de Bruijn terms [11], and so on — is a collection of (syntax) trees. This paper studies functions.
This paper is part of a broader research programme developing nominal techniques in general and nominal algebra in particular. A rewrite system for the -calculus appeared already in [13] but without any statement or proof of completeness (indeed, the system considered there was not complete). The authors have axiomatised first-order logic as a theory FOL [16] and also substitution as a theory SUB [15]. Since -reduction is based on substitution, this paper shares technical results with the study of SUB [15]. The completeness result we give for ULAM is for a model based on untyped -terms quotiented by -equality. The completeness result for SUB is for a model based on trees with an explicit substitution. Derivable equality in ULAM includes the full power of the -calculus and is undecidable; equality in SUB is equality of syntax with a substitution action and is decidable. For example
is derivable in ULAM, but (in notation from [15]) only
is derivable in SUB. The proofs in this paper have been improved and simplified. Technical issues have been avoided and we do not rely on a strong normalisation property which the proofs of [15] required (probably unnecessarily). Note that the treatment of SUB is parametric over a range of signatures and would be the appropriate theory where substitution is precisely what we require — for example as part of an axiomatisation of quantifiers in first-order logic.
A version of ULAM for a typed -calculus should be possible. It would sit ‘in between’ ULAM and SUB, as one might expect, but to make this formal a typing system for nominal terms is required (such that atoms are assigned types by a typing context). This has been investigated to some extent [12]. Investigations in nominal algebra are for future work.
Nominal algebra has a cousin, nominal equational logic (NEL) [9], which was derived from nominal algebra but making different design decisions. NEL satisfies a completeness result for a generic class of models in nominal sets [9], as does nominal algebra [14, 23]. The completeness result of this paper is much stronger than the generic results, because it is completeness for a single elementary model; similarly for the authors’ treatments of substitution [15] and first-order logic [16]. 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.
5.3 Future work
The nominal algebraic framework proved itself capable of translating, with remarkable accuracy and uniformity, informal mathematical specification into formal nominal algebra axioms, almost symbol for symbol. This paper is both a study of the algebraisation of functions using nominal algebra, and a case study in nominal techniques applied to the -calculus. We hope that future study of nominal techniques may benefit from the ‘off-the-shelf’ axiomatisation provided in this paper. We have proved a soundness result (Theorem 55) and a strong completeness result (Theorem 57). We hope that as the theory of nominal algebra itself is improved, this will be of direct benefit to -calculus theory.
It would be interesting to consider direct ‘nominal’ versions of models of the -calculus, such as graph models or domain models of the -calculus [6, 30]. It would also be interesting to consider work using the language of categories (for example [29, 4]) using categories based on nominal sets.
It remains to develop the theory of nominal algebra itself, such as to prove the HSP theorem [8]; we would then be able to apply it to ULAM to study the -calculus, and likewise for other nominal algebraic theories.
It is also possible to investigate how well nominal algebra, or a system like it, can serve as the basis of a theorem-prover. Theorem-provers based on the -calculus [3] are the state of the art, and the Isabelle theorem-prover demonstrates how a weak meta-logic (such as Isabelle/Pure) can encode powerful object-logics (such as Isabelle/HOL) [24]. Is it possible that an elaboration of Nominal Algebra could serve as the foundation of a generic theorem-prover in the spirit of Isabelle, offering a new set of reasoning-principles ‘ away from informal practice’? The construction of ULAM in nominal algebra is a useful preliminary step.
5.4 Conclusions
The -calculus is a fundamental model of functions in logic and computation. We have given axioms ULAM for the untyped -calculus in nominal algebra, a recently-developed logical framework based on nominal techniques. This gives a logical theory pleasingly close to informal practice, while remaining mathematically completely rigorous. ULAM completes a trio of papers on nominal algebra and first-order logic [16], substitution [15], and with this paper, the -calculus. Researchers using nominal techniques might find ULAM and its completeness result a useful off-the-shelf component in later and larger works.
ULAM formally connects ‘nominal atoms’ and ‘-calculus variables’. Discussions about this connection — usually based on not-entirely-explicit criteria of practical usefulness — have continued since nominal techniques were introduced [17] and they may continue into the forseeable future. ULAM makes a nice mathematical contribution to this discussion; the axioms of ULAM are an algebraic measure of the distance we must travel from nominal-style atoms and atoms-abstraction, to -calculus style variables and -binding. This is gives new sense of how nominal techniques fit into a long tradition of functions in logic and computation.
BIBLIOGRAPHY
[1] Peter B. Andrews. An introduction to mathematical logic and type theory: to truth through proof. Academic Press, 1986.
[2] Peter B. Andrews. Classical type theory. In Handbook of Automated Reasoning, volume 2, chapter 15, pages 965–1007. Elsevier Science, 2001.
[3] 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.
[4] Giulio Manzonetto Antonio Bucciarelli, Thomas Ehrhard. Not Enough Points Is Enough. In Computer Science Logic, pages 298–312, 2007.
[5] Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Great Britain, 1998.
[6] H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.). North-Holland, 1984.
[7] J. Barwise. An Introduction to First-Order Logic. In J. Barwise, editor, Handbook of Mathematical Logic, pages 5–46. North Holland, 1977.
[8] S. Burris and H. Sankappanavar. A Course in Universal Algebra. Graduate texts in mathematics. Springer, 1981.
[9] Ranald A. Clouston and Andrew M. Pitts. Nominal Equational Logic. Electronic Notes in Theoretical Computer Science, 172:223–257, 2007.
[10] Haskell B. Curry and R. Feys. Combinatory Logic, volume 1. North Holland, 1958.
[11] 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.
[12] 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.
[13] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting (journal version). Information and Computation, 205(6):917–965, 2007.
[14] 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, 2007.
[15] Murdoch J. Gabbay and Aad Mathijssen. Capture-Avoiding Substitution as a Nominal Algebra. Formal Aspects of Computing, 20(4-5):451–479, August 2008.
[16] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic. Journal of Logic and Computation, 18(4):521–562, August 2008.
[17] Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341–363, 2001.
[18] L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras. North Holland, 1971 and 1985. Parts I and II.
[19] Wilfrid Hodges. Elementary predicate logic. In D.M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer, 2001.
[20] 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.
[21] Pierre Lescanne. From Lambda-sigma to Lambda-upsilon: a Journey Through Calculi of Explicit Substitutions. In POPL, pages 60–69. ACM, 1994.
[22] G. Manzonetto and A. Salibra. Boolean Algebras for Lambda Calculus. In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), pages 317–326. IEEE Computer Society, 2006.
[23] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.
[24] Lawrence C. Paulson. The Foundation of a Generic Theorem Prover. Journal of Automated Reasoning, 5(3):363–397, 1989.
[25] Lawrence C. Paulson. ML for the working programmer (2nd ed.). Cambridge University Press, 1996.
[26] F. Pfenning and C. Elliot. Higher-Order Abstract Syntax. In PLDI (Programming Language design and Implementation), pages 199–208. ACM Press, 1988.
[27] A. M. Pitts. Nominal Logic, A First Order Theory of Names and Binding. Information and Computation, 186(2):165–193, 2003.
[28] Antonino Salibra. On the algebraic models of lambda calculus. Theoretical Computer Science, 249(1):197–240, 2000.
[29] Peter Selinger. The lambda calculus is algebraic. Journal of Functional Programming, 12(6):549–566, 2002.
[30] Joseph E. Stoy. Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press, Cambridge, MA, USA, 1977.
[31] Simon Thompson. Haskell: The Craft of Functional Programming. Addison Wesley, 1996.
[32] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
Notes
1Homepage: http://www.gabbay.org.uk ↩
2Email: a.h.j.mathijssen@tue.nl ↩
3We are grateful to a dilligent anonymous referee of a previous paper for making a suggestion which put us on the path to write this paper, and to Pablo Nogueira and Chad Brown for useful advice on improving the exposition. Supported by grant RYC- 2006-002131 at the Polytechnic University of Madrid. ↩
1In [17], names had no functional content at all; they were used just to build datatypes of abstract syntax trees with binding. Higher-order abstract syntax [26] is a way to do the same thing using the ‘names as arguments to functions’ philosophy. ↩