HTML reading edition · 16 source pages · Open the source PDF

Replace this file with prentcsmacro.sty for your meeting, or with entcsmacro.sty for your meeting. Both can be found at the ENTCS Macro Home Page.

The λ-context calculus

Murdoch J. Gabbay Stéphane Lengrand

Abstract

We present a simple but expressive lambda-calculus whose syntax is populated by variables which behave like meta-variables. It can express both capture-avoiding and capturing substitution (instantiation). To do this requires several innovations, including a key insight in the confluence proof and a set of reduction rules which manages the complexity of a calculus of contexts over the ‘vanilla’ lambda-calculus in a very simple and modular way. This calculus remains extremely close in look and feel to a standard lambda-calculus with explicit substitutions, and good properties of the lambda-calculus are preserved.

Keywords: Lambda-calculus, contexts, meta-variables, capture-avoiding substitution, capturing substitution, instantiation, confluence, nominal techniques, calculus of explicit substitutions.

1 Introduction

This is a paper about a λ-calculus for contexts. A context is a term with a ‘hole’. The canonical example is probably C[-] = λx.- in the λ-calculus. This is not λ-calculus syntax because it has a hole -, but if we fill that hole with a term t then we obtain something, we usually write it C[t], which is a λ-calculus term.

For example if C[-] = λx.- then C[x] = λx.x and C[y] = λx.y. This cannot be modelled by a combination of λ-abstraction and application, because β-reduction avoids capture. Formally: there is no λ-term f such that ft = C[t]. The term λz.λx.z is the obvious candidate, but (λz.λx.z)x =α λx′.x. (Here =α is α-equality.)

Contexts arise often in proofs of meta-properties in functional programming. They have been substantially investigated in papers by Pitts on contextual equivalence between terms in λ-calculi (with global state) [18,20]. This work was about proving programs equivalent in all contexts — contextual equivalence. The idea is that two programs, represented by possibly-open λ-terms, are equivalent when one can be exchanged for another in code (without changing whichever notion of observation we prefer to use).

This suggests that we should call holes context variables X (say they have ‘level 2’) distinct from ‘normal’ variables x (say they have ‘level 1’) and allow λ-abstraction over them to obtain a λ-calculus of contexts, so that we can study program contexts with the full panoply of vocabulary, and hopefully with many of the theorems, of the λ-calculus. For example λx.- may be represented by λX.λx.X. Substitution for X does not avoid capture with respect to ‘ordinary’ λ-abstraction, so (λX.λx.X)x reduces to λx.x.

⃝c 2007 Published by Elsevier Science B. V.

The Lambda Context Calculus internalises context variables (as variables of ‘level 2’, which we write X, Y, Z). X, Y , and Z are now variables which can occur any number of times anywhere in a term — and they can be λ-abstracted. The Lambda Context Calculus therefore goes further and internalises another level of contexts (variables of ‘level 3’, which we write W, W′) — and so on. There are several possibilities where such a calculus might be applied.

Consider formalising mathematics in a logical framework based on Higher-Order Logic (HOL) [28]. Typically we have a goal and some assumptions and we want a derivation of one from the other. This derivation may be represented by a λ-term (the Curry-Howard correspondence). But the derivation is arrived at by stages in which it is incomplete.

To the right are two derivations of A⇒B⇒C, A⇒B ⊢ A⇒C. The bottom one is complete, the top one is incomplete. 1 An issue arises because the right-most [A]i in the bottom derivation is discharged, which means that we have to be able to instantiate ? in a sub-derivation for an assumption which will be discharged. Discharge corresponds in the Curry-Howard correspondence precisely to λ-abstraction, and this instantiation corresponds to capturing substitution. Similar issues arise with existential variables [10, Section 2, Example 3].

A⇒B⇒C [A]iB⇒C? BCiA⇒C
A⇒B⇒C [A]iB⇒CA⇒B [A]iBCiA⇒C

The central issue for any calculus of contexts is the interaction of context variables with α-equivalence. Let x, y, z be ‘ordinary’ variables and let X be a context variable. If λx.X =α λy.X then (λX.λx.X)x =α (λX.λy.X)x ⇝λy.x, giving non-confluent reductions. Dropping α-equivalence entirely is too drastic; we need λy.λx.y to be α-convertible with λz.λx.z to reduce a term like (λy.λx.y)x.

Solutions include clever control of substitution and evaluation order [23], types to prevent ‘bad’ α-conversions [21,11,22], explicit labels on meta-variables [10,13], and more [4, Section 2]. More on this in the Conclusions.

We took our technical ideas for handling α-equivalence, not from the literature on context calculi cited above, but from nominal unification [27]. This was designed to manage α-equivalence in the presence of holes, in unification — ‘unification of contexts of syntax’, in other words. Crudely put, we obtained the λ-context calculus (LCC) by allowing λ-abstraction over the holes and adding β-reduction.

This work has similar goals to previous work by the first author [6] which presented a calculus called NEWcc. The LCC possesses a significatnly more elementary set of reduction rules; notably, we dispense entirely with the freshness contexts and freshness logic of the NEWcc. Indeed, the LCC has only one single non-obvious side-condition, it is on (σp) in Figure 5.

The result is a system with a powerful hierarchy of context variables and which still manages to be clean and, we hope, easy to use and to study.

In Section 2 we present the syntax and reductions of the LCC. The look-and-feel is of a λ-calculus with explicit substitutions, except that each variable has a ‘level’ which determines how ‘strongly’ binders by that variable resist capture. We give example reductions and discuss the technical issues which motivated our design. In Section 3 we discuss the λ-free part of the language, prove strong normalisation, and give an algorithm for calculating normal forms. In the usual λ-calculus this normal form is calculated in big-step style and written s[a↦→t]; as is standard for a calculus of explicit substitutions, here this part of evaluation is dissected in detail. In Section 4 we treat confluence, first of the λ-free part of the language, then of the full reduction system. The proof may look elementary but it is not, and we give enough technical detail to show how all the side-conditions interact to ensure confluence. It is not sufficient to give a λ-calculus without binding, but the hierarchy of levels means that λ itself is no longer necessarily a binder. We address that issue with a new N in Section 5. We conclude with brief discussions of programming in Section 6, and then discuss related and future work.

2 Syntax and reductions

2.1 Syntax

We suppose a countably infinite set of disjoint infinite sets of variables A1, A2, . . . . i, j, k range over levels; we usually maintain a convention that k ≤i < j, where we break it we clearly say so. We always use a permutative convention that ai, bj, ck, . . . range permutatively over variables of level i; so ai, bj, and ck are always distinct variables. There is no particular connection between a1 and a2; we have just given them similar names.

Definition 2.1

LCC syntax is given by s, t ::= ai | tt | λai.t | t[ai↦→t].

Application associates to the left, e.g. tt′t′′ is (tt′)t′′. We say that ai has level i. We call bj stronger than ai, and ai weaker than bj, when j > i. If i = j we say that bj and ai have the same strength. We call s[ai↦→t] an explicit substitution (of level i). We call λai.t an abstraction (of level i).

By convention x, y, z, X, Y, Z, W are distinct variables; x, y, z have level 1, X, Y, Z have level 2, and W has level 3. Note that levels are 1, 2, 3, . . . but our proofs would work as well for levels being integers, reals, or any totally ordered set.

The stronger a variable, the more ‘meta’ its behaviour. The intuition of λx.X is of the context λx.- where - is a hole; this is because, as we shall see, substitution for the relatively strong X does not avoid capture by the relatively weak λx. Strong variables can be abstracted as usual; the intuition of λX.X is of the ‘normal’ identity function; the intuition of λX.λx.X is of the mapping ‘t maps to λx.t’.

Our syntax has no constant symbols though we shall be lax and use them where convenient, for example 1, 2, 3, . . .. This can be accommodated by extending syntax, or by declaring them to be variables of a new level 0 < 1 which we do not abstract over or substitute for.

Definition 2.2

Define the level level(s) and the free variables fv(s) by the rules in Figure 1.

Here max(i, j) is the greater of i and j, and max(i, j, k) is the greatest of i, j, and k. Later we shall write ‘level(s1, . . . , sn) ≤i’ as shorthand for ‘level(s1) ≤i and . . . and level(sn) ≤i’, similarly for ‘level(s1, . . . , sn) < i’.

level(ai) = i level(ss′) = max(level(s), level(s′)) level(λai.s) = max(i, level(s)) level(s[ai↦→t]) = max(i, level(s), level(t))fv(ai) = {ai} fv(λai.s) = fv(s)\{ai} fv(s[ai↦→t]) = (fv(s)\{ai}) ∪fv(t) fv(st) = fv(s) ∪fv(t)
Fig. 1. Levels level(s) and free variables fv(s)
aiRaisRs′ tRt′st R s′t′sRs′tRt′s[ai↦→s′] R t[ai↦→t′]sRs′λai.s R λai.s′sRs′s′RssRs′ s′Rs′′sRs′′
Fig. 2. Rules for a congruence
(ai bi)ai = bi(ai bi)bi = ai(ai bi)c = c (c any atom other than ai or bi)(ai bi)(ss′) = ((ai bi)s)((ai bi)s′) (ai bi)(λc.s) = λ(ai bi)c.(ai bi)s (c any atom)(ai bi)(s[c↦→t]) = ((ai bi)s)[(ai bi)c↦→(ai bi)t] (c any atom)
Fig. 3. Rules for swapping
λai.s =α λbi.(bi ai)s if bi#fv(s)s[ai↦→t] =α ((bi ai)s)[bi↦→t] if bi#fv(s)
Fig. 4. Rules for α-equivalence
Lemma 2.3

If level(s) = 1 then fv(s) coincides with the usual notion of ‘free variables of’ for the λ-calculus, if we read s[a1↦→t] as (λa1.s)t.

We shall see that the operational behaviour of such terms is the same as well.

A congruence is a binary relation s R s′ satisfying the conditions of Figure 2. Define an (atoms) swapping (ai bi)s by the rules in Figure 3. Swapping is characteristic of the underlying ‘nominal’ method we use in this paper [9,27]. We let swapping (ai bi) act pointwise on sets of variables S: (ai bi)S = {(ai bi)c | c ∈S}. Here c ranges over all elements of S, including ai and bi (if they are in S).

Lemma 2.4

fv((ai bi)s) = (ai bi)fv(s) and level((ai bi)s) = level(s).

If S is a set of variables write ai#S when ai ∉S and also there exists no variable bj ∈S such that j > i.

Definition 2.5

Call the two rules in Figure 4 α-conversion of ai. Let α-equivalence =α be the least congruence relation containing α-conversion.

Note that: ai may be α-converted in λai.s if level(s) ≤i, so λx.x =α λy.y. ai may be α-converted in s[ai↦→t] if level(s) ≤i, so x[x↦→X] =α y[y↦→X]. We cannot α-convert ai in s if bj ∈ fv(s) for j > i. For example λx.X ≠α λy.X. This is consistent with a reading of strong variables as unknown terms with respect to weaker variables. We cannot α-convert variables to variables of other levels.

Lemma 2.6

If s mentions only variables of level 1, then α-equivalence collapses to the usual α-equivalence on untyped λ-terms (plus an explicit substitution).

Theorem 2.7

If s =α s′ then fv(s) = fv(s′) and level(s) = level(s′).

Proofs of all results above are by easy inductions.

In the rest of this paper we find it convenient to work on terms up to α-equivalence (=α-equivalence classes of terms). When later we write ‘s = t’, the intended reading is that the α-equivalence classes of s and t are equal.

2.2 Reductions

Definition 2.8

Define the reduction relation by the rules in Figure 5.

Recall our permutative convention; for example in (σλ′) ai and ci are distinct. Subsection 2.3 shows examples of these rules at work, and Subsection 2.4 discusses their design. We shall use the following notation:

• We write ⇝∗ for the transitive reflexive closure of ⇝.

• We write s ̸⇝ when there exists no t such that s ⇝t. If s ̸⇝ we call s a normal form, as is standard.

• We write s(ruleset)⇝ t when we can deduce s ⇝t using only rules in (ruleset) and the rules (Rapp) to (Rσ′), where (ruleset)⊆{(β), (σa), (σfv), (σp), (σσ), (σλ), (σλ′)}. (Later in Section 5 we extend reduction with rules for a binder N.)

• Call ⇝ terminating when there is no infinite sequence t1 ⇝· · · ⇝ti ⇝· · · Similarly for (ruleset)⇝. Call ⇝ confluent when if s ⇝∗t and s ⇝∗t′ then there exists some u such that t ⇝∗u and t′ ⇝∗u. Similarly for (ruleset)⇝ .

This is all standard [25,1].

We note two easy but important technical properties: reductions does not increase the level of a term or its set of free variables.

Lemma 2.9

If s ⇝s′ then level(s′) ≤ level(s).

Lemma 2.10

If s ⇝s′ then fv(s′) ⊆ fv(s), and if s ⇝∗s′ then fv(s′) ⊆ fv(s).

2.3 Example reductions

The LCC is a λ-calculus with explicit substitutions [15]. The general form of the σ-rules is familiar from the literature though the conditions, especially those involving levels, are not; we discuss them in Subsection 2.4 below. First, we consider some example reductions. Recall our convention that we write x, y, z for variables of level 1, and X, Y, Z for variables of level 2.

• (β) is standard for a calculus with explicit substitutions.

(β) (λai.s)t ⇝s[ai↦→t] (σa) ai[ai↦→t] ⇝t (σfv) s[ai↦→t] ⇝s ai#fv(s)(σp) (ss′)[ai↦→t] ⇝(s[ai↦→t])(s′[ai↦→t]) level(s, s′, t) ≤i (σσ) s[ai↦→t][bj↦→u] ⇝s[bj↦→u][ai↦→t[bj↦→u]] i < j (σλ) (λai.s)[bj↦→u] ⇝λai.(s[bj↦→u]) i < j(σλ′) (λai.s)[ci↦→u] ⇝λai.(s[ci↦→u]) ai#fv(u)s ⇝s′(Rapp)st ⇝s′tt ⇝t′(Rapp′)st ⇝st′s ⇝s′(Rλ)λai.s ⇝λai.s′s ⇝s′(Rσ)s[ai↦→t] ⇝s′[ai↦→t]t ⇝t′(Rσ′)s[ai↦→t] ⇝s[ai↦→t′]
Fig. 5. Reduction rules of the LCC

• The behaviour of a substitution on a variable depends on strengths:

x[X↦→t](σfv)⇝x x[x′↦→t](σfv)⇝x x[x↦→t](σa)⇝t X[x↦→t] ̸⇝

The term X[x↦→t] will not reduce until a suitable strong substitution [X↦→t] arrives from the surrounding context, if any.

• Substitutions for relatively strong variables may distribute using (σσ) or (σλ) under substitutions or λ-abstractions for relatively weaker variables:

X[x↦→t][X↦→x](σσ)⇝X[X↦→x][x↦→t[X↦→x]](σa)⇝x[x↦→t[X↦→x]](σa)⇝t[X↦→x](λx.X)[X↦→x] ⇝λx.(X[X↦→x]) ⇝λx.x

This makes strong variables behave like ‘holes’. Instantiation of holes is compatible with β-reduction; here is a typical example:

((λx.X)t)[X↦→x](σp)⇝(λx.X)[X↦→x](t[X↦→x])(σλ)⇝(λx.(X[X↦→x]))(t[X↦→x])(σa)⇝(λx.x)(t[X↦→x])(β)⇝x[x↦→t[X↦→x]](σa)⇝t[X↦→x]((λx.X)t)[X↦→x](β)⇝X[x↦→t][X↦→x](σσ)⇝X[X↦→x][x↦→t[X↦→x]](σa)⇝x[x↦→t[X↦→x]](σa)⇝t[X↦→x]

• There is no restriction in s[ai↦→t] that level(t) < i; for example the terms X[x↦→Y] and X[x↦→W] are legal.

• [ai↦→t] is not a term, but the term λbj.bj[ai↦→t] where j > i and j > level(t) will achieve the effect of ‘the substitution [ai↦→t] as a term’:

(λbj.bj[ai↦→t])s(β)⇝bj[ai↦→t][bj↦→s](σσ)⇝bj[bj↦→s][ai↦→t[bj↦→s]](σfv)⇝bj[bj↦→s][ai↦→t](σa)⇝s[ai↦→t].

2.4 Comments on the side-conditions

• (σfv) is a form of garbage-collection. We do not want to garbage-collect [x↦→2] in X[x↦→2] because (σσ) could turn X into something with x free — for example x

itself; this is why the side-condition is not ai ∉ fv(s) but ai#fv(s).

It is unusual for a garbage collection rule to appear in a calculus of explicit substitutions; we might hope to ‘push substitutions into a term until they reach variables’ and so make do with a rule of the form ck[ai↦→t] ⇝ck (for k ≤i). In the LCC this will not do because side-conditions (such as that of (σp)) can stop a substitution going deep into a term. Without (σfv) we lose confluence (see the second case of Theorem 4.10). A version of (σfv) appears in the literature as ‘garbage collection’ [3].

• Recall that the level of a term is the level of the strongest variable it contains, free or bound. The side-condition level(s, s′, t) ≤i in (σp) seems to be fundamental for confluence to work; we have not been able to sensibly weaken it, even if we also change other rules to fix what goes wrong when we do. Here is what happens if we drop the side-condition entirely:

X[x↦→y][y↦→x](β)⇝((λx.X)y)[y↦→x](σpFALSE)⇝ ((λx.X)[y↦→x])(y[y↦→x])(σa)⇝ ((λx.X)[y↦→x])x

• The side-conditions on (σσ), (σλ), and (σλ′) implement that a strong substitution can capture. There is no (σσ′) since that would destroy termination of the part of the LCC without λ — and we have managed to get confluence without it.

• There is no rule permitting a weak substitution to propagate under a stronger abstraction, even if we avoid capture:

(σλ′FALSE) (λai.s)[ck↦→u] ⇝λai.(s[ck↦→u]) ai#fv(u), k ≤i

Such a rule causes the following problem for confluence:

(λY.(xZ))[x↦→3][Z↦→W](σλ′FALSE)⇝ (λY.(xZ)[x↦→3])[Z↦→W]
(λY.(xZ))[x↦→3][Z↦→W](σσ)⇝ (λY.(xZ))[Z↦→W][x↦→3[Z↦→W]](σfv)⇝ (λY.(xZ))[Z↦→W][x↦→3]

As is the case for the side-condition of (σp), any stronger form of (σλ′) than what we admit in the LCC seems to provoke a cascade of changes which make the calculus more complex.

Investigation of these side-conditions is linked to strengthening the theory of freshness and α-equivalence, and possibly to developing a good semantic theory to guide us. This is future work and some details are mentioned in the Conclusions.

3 The substitution action

Define (sigma) = {(σa), (σfv), (σp), (σσ), (σλ), (σλ′)} (so (sigma) is ‘everything except for (β)’). It would be good if this is is terminating [3,15]. Do we sacrifice this property because of the hierarchy of variables? No. To prove it we translate LCC syntax to first-order terms (terms without binding [1,25]) in the signature

s[ai:=t] = s ai#fv(s), and otherwiseai[ai:=t] = t (ss′)[ai:=t] = (s[ai:=t])(s′[ai:=t]) level(s, s′, t) ≤is[ck↦→u][ai:=t] = s[ai:=t][ck:=u[ai:=t]] k < i(λck.s)[ai:=t] = λck.(s[ai:=t]) k < i(λci.s)[ai:=t] = λci.(s[ai:=t]) ci#fv(t)s[ai:=t] = s[ai↦→t]a∗ i = ai(λai.s)∗= λai.(s∗) (s[ai↦→t])∗= s∗[ai:=t∗] (st)∗= (s∗)(t∗)
Fig. 6. Substitution s[ai:=t] and (sigma)-normal form s∗
Σ = {⋆, Abs, App} ∪{Subi | i}

as follows:

x = ⋆ λai.s = Abs(s) s t = App(s, t) s[ai↦→t] = Subi(s, t)

Here ⋆ has arity 0, Abs has arity 1, App has arity 2, and Subi has arity 2 for all i (i ranges over levels). Give symbols precedence (lowest precedence on the right)

. . . , Subj, . . . , Subi, . . . , App, Abs, ⋆ (j > i).

Define the lexicographic path ordering [14,1] by:

ti ≪f(t1, . . . , tn)s ≪tis ≪f(t1, . . . , tn)(t′ 1, . . . , t′ n) ≪(t1, . . . , tn)f(t′ 1, . . . , t′ n) ≪f(t1, . . . , tn)ui ≪f(t1, . . . , tn) for 1 ≤i ≤m g(u1, . . . , um) ≪f(t1, . . . , tn)

Here g and f are first-order symbols, g has strictly lower precedence than f, and t1, . . . , tn, t′ 1, . . . , t′ n, u1, . . . , um, s are first-order terms. It is a fact [14,1] that ≪ is a well-founded order on first-order terms satisfying the subterm property, i.e. if s is a subterm of t then s ≪t.

Theorem 3.1

If t(sigma)⇝u then t ≫u. Thus (sigma)-reduction terminates.

The proof is by checking that a (sigma)-reduction strictly reduces the lexicographic path order of the associated first-order term; this is not hard.

Let x have level 1. (λx.xx)(λx.xx) has an infinite series of reductions in the LCC. It follows that — even with a hierarchy of variables — (β) strictly adds power to the LCC.

Call s (sigma)-normal when s(sigma)̸⇝. What does a (sigma)-normal form look like? Define a substitution action s[ai:=t] and using it define s∗, by the rules in Figure 6. Rules are listed in order of precedence so that a later rule is only used if no earlier rule is applicable. We apply the rule (λci.s)[ai:=t] renaming where possible to ensure ci#fv(t).

Lemma 3.2

s[ai↦→t] (sigma)⇝∗s[ai:=t].

Proof

Each clause in the definition of s[ai:=t] is simulated by a (sigma)-rule. □

Theorem 3.3

s(sigma)⇝∗s∗ and s∗ is a (sigma)-normal form.

Proof

The first part is by an easy induction on the definition of s∗; the case of (s[ai↦→t])∗ uses Lemma 3.2. The second part is by a routine induction on s. 2

4 Confluence

Let (beta) be the set {(β), (σλ), (σλ′), (σfv)}. (sigma) ∩ (beta) is non-empty; we discuss why at the end of Subsection 4.3.

Theorem 4.1

⇝ is confluent.

The proof of Theorem 4.1 occupies this section. Two standard proof-methods are: (1) Use a parallel reduction relation ⇒, and (2) for all s define a s↓ such that s ⇝∗s↓ and if s ⇝s′ then s′ ⇝∗s↓. Both methods are standard [25]. Which to use for the LCC? It seems that λ ‘wants’ method 1 — but σ ‘wants’ method 2. Confluence is (relatively) easy to prove if we split the reduction relation into (sigma) and (beta) and apply different methods to each — and then join them together.

4.1 Confluence of (sigma)

Note there is no capture-avoidance condition in Lemma 4.2, because i < j. The full proofs also contain another version where i = j and ai#fv(u).

Lemma 4.2

If i < j then s[ai:=t][bj:=u] = s[bj:=u][ai:=t[bj:=u]].

Proof

By induction on i, then on s. We illustrate the induction with two cases.

• Suppose i < j < k. Note that usually we take k ≤i; this is an exception. Then:

ck[ai:=t][bj:=u] = ck[ai↦→t][bj:=u] = ck[bj:=u][ai↦→t[bj:=u]] = ck[bj↦→u][ai↦→t[bj:=u]]ck[bj:=u][ai:=t[bj:=u]] = ck[bj↦→u][ai:=t[bj:=u]] = ck[bj↦→u][ai↦→t[bj:=u]]

• Suppose that level(s, s′, t) < j. By Lemma 3.2 we have (ss′)[ai↦→t] ⇝∗ (ss′)[ai:=t]. By Lemma 2.9 we have level((ss′)[ai:=t]) ≤ level((ss′)[ai↦→t]) = level(s, s′, t) < j. Then by our assumptions on levels,

(ss′)[ai:=t][bj:=u] = (ss′)[ai:=t] = (ss′)[bj:=u][ai:=t[bj:=u]].□
Lemma 4.3

(i) (ai[ai↦→t])∗= t∗.

(ii) (ck[ai↦→t])∗= ck where k ≤i.

(iii) ((ss′)[ai↦→t])∗= ((s[ai↦→t])(s′[ai↦→t]))∗ where level(s, s′, t) ≤i.

(iv) (s[ai↦→t][bj↦→u])∗= (s[bj↦→u][ai↦→t[bj↦→u]])∗ if i < j.

(v) ((λai.s)[bj↦→u])∗= (λai.(s[bj↦→u]))∗ if i < j.

(vi) ((λai.s)[ci↦→u])∗= (λai.(s[ci↦→u]))∗ if (renaming where possible) ai#fv(u).

(Pa)ai =⇒ais =⇒s′t =⇒t′(Pσ)s[ai↦→t] =⇒s′[ai↦→t′]s =⇒s′t =⇒t′(Papp)st =⇒s′t′s =⇒s′(Pλ)λai.s =⇒λai.s′s =⇒s′t =⇒t′s′[ai↦→t′]Rϵ⇝u(Pσϵ)s[ai↦→t] =⇒us =⇒s′t =⇒t′s′t′Rϵ⇝u(Pappϵ)st =⇒u(R ∈(beta))
Fig. 7. Parallel reduction relation for the LCC
Proof

Most cases are easy; we consider only the fourth one. Recall that we assume i < j. Using Lemma 4.2

(s[ai↦→t][bj↦→u])∗= s∗[ai:=t∗][bj:=u∗] = s∗[bj:=u∗][ai:=t∗[bj:=u∗]] = (s[bj↦→u][ai↦→t[bj↦→u]])∗.

2

Lemma 4.4

If s(sigma)⇝s′ then s′ (sigma)⇝∗s∗.

Proof

By induction on the derivation of s(sigma)⇝s′, using Lemma 4.3. 2

Theorem 4.5

(sigma)⇝ is confluent.

Proof

By an easy inductive argument using Lemma 4.4. 2

4.2 (beta)-reduction

Define the parallel reduction relation =⇒ by the rules in Figure 7.

In rules (Pσϵ) and (Pappϵ), s′t′Rϵ⇝u and s′[ai↦→t′] Rϵ⇝u indicate a rewrite with R ∈ (beta) derivable without using (Rapp), (Rapp′), (Rλ), (Rσ), or (Rσ′).

Lemma 4.6

s =⇒∗s′ if and only if s(beta)⇝∗s′.

Corollary 4.7

If s =⇒s′ then fv(s′) ⊆ fv(s) and level(s′) ≤ level(s).

Proof

From Lemma 4.6 and Lemma 2.10. 2

Lemma 4.8

=⇒ satisfies the diamond property. That is, if s′ ⇐= s =⇒s′′ then there is some s′′′ such that s′ =⇒s′′′ ⇐= s′′.

Proof

We work by induction on the depth of the derivation of s =⇒s′ proving ∀s′′. s =⇒s′′ ⇒∃s′′′. (s′ =⇒s′′′ ∧s′′ =⇒s′′′). We consider possible pairs of rules which could derive s =⇒s1 and s =⇒s2. All cases are very easy, we only sketch that of (Pσ) and (Pσϵ) for (σλ′), which is the least trivial.

Suppose s =⇒s′ and u =⇒u′ and also s =⇒s′′ and u =⇒u′′. Suppose also that (renaming where necessary) ai#u′′ so that by (Pσ) and (Pσϵ) for (σλ′)

(λai.s′)[ci↦→u′] ⇐= (λai.s)[ci↦→u] =⇒λai.(s′′[ci↦→u′′]).

By inductive hypothesis there are s′′′ and u′′′ such that s′ =⇒s′′′ ⇐= s′′ and u′ =⇒u′′′ ⇐= u′′. By Corollary 4.7 ai#u′′′. Using (Pσϵ) for (σλ′) and (Pσ)

(λai.s′)[ci↦→u′] =⇒λai.(s′′′[ci↦→u′′′]) ⇐= λai.(s′′[ci↦→u′′]).

2

Theorem 4.9

(beta)⇝ is confluent.

Proof

By Lemmas 4.6 and 4.8 and a standard argument [2]. 2

4.3 Combining (sigma) and (beta)

Theorem 4.10

If s =⇒s′ and s(sigma)⇝s′′ then there is some s′′′ such that s′ (sigma)⇝∗s′′′ and s′′ =⇒s′′′.

Proof

We work by induction on the derivation of s =⇒s′. For brevity we merely indicate the non-trivial parts. We always assume that s =⇒s′, t =⇒t′, and u =⇒u′, where appropriate.

• (β) has a divergence with (σp) in the case that i < j and level(s, t, u) ≤j. This can be closed using a =⇒-rewrite which uses (σλ):

(λai.s)[bj↦→u](t[bj↦→u])(σp)⇝((λai.s)t)[bj↦→u] =⇒s′[ai↦→t′][bj↦→u′] (λai.s)[bj↦→u](t[bj↦→u]) =⇒s′[bj↦→u′][ai↦→t′[bj↦→u′]](σσ)⇝s′[ai↦→t′][bj↦→u′]

• (σσ) has a divergence with (σλ′). Suppose i<j and (renaming if necessary) ci#fv(t):

(λci.s)[bj↦→u][ai↦→t[bj↦→u]](σσ)⇝(λci.s)[ai↦→t][bj↦→u] =⇒(λci.(s′[ai↦→t′]))[bj↦→u′]

We know bj#fv(t) because ci#fv(t) and i < j. We deduce bj#fv(t′) using Corollary 4.7. This justifies the =⇒-rewrite below, which uses (σfv):

λci.(s′[ai↦→t′])[bj↦→u′](σλ′)⇝λci.(s′[ai↦→t′][bj↦→u′])(σσ)⇝λci.(s′[bj↦→u′][ai↦→t′[bj↦→u′]])(σfv)⇝λci.(s′[bj↦→u′][ai↦→t′]) ⇐= (λci.s)[bj↦→u][ai↦→t[bj↦→u]] □

(σλ) is in (sigma) ∩ (beta) to make the case of (σp) with (β) work. (σλ′) is in (sigma) ∩ (beta) to make a similar divergence of (σp) with (β) work. (σfv) is in (sigma) ∩ (beta) to make the case of (σσ) with (σλ′) work.

Theorem 4.1 now follows by an easy diagrammatic argument using Theorem 4.10, Theorem 4.5, and Lemma 4.8.

5 A NEW part for the LCC

x is not α-convertible in λx.X. Suppose we really do want to bind x; we can do so with N. We extend syntax: s, t ::= . . . |Nai.t. We extend the notions of level, fv, congruence, and swapping with cases for N which are identical to those for λ (except that we write N instead). For example fv(Nai.s) = fv(s) \ {ai}.

The difference is in the α-equivalence: Nai.s =αNbi.(bi ai)s if bi ∉ fv(s). Note the bi ∉ fv(s) instead of bi#fv(s) as in the clause for λ. This lets variables bound by Nα-convert regardless of whether stronger variables are present. For example λx.X ≠α λy.X but Nx.λx.X =αNy.λy.X. We add reduction rules:

(Np) (Nai.s)t ⇝Nai.(st) ai ∉fv(t)(Nσ) (Nck.s)[ai↦→t] ⇝Nck.(s[ai↦→t]) k ≤i, ck ∉fv(t)(N∉)Nai.s ⇝s ai ∉fv(s)s ⇝s′(RN)Nai.s ⇝Nai.s′

x is not bound in λy.s if s mentions a strong variable, for example in λy.(Xy) substitution for X can capture y. We may want y to be really local and avoid capture by substitutions for X. We can increase the level of y; λY.(XY) will do in this case. This has a hidden cost because side-conditions (especially on (σp)) look at strengths of variables, so having strong variables can block reductions in the context. N avoids this, for example Ny.λy.(Xy) has the behaviour we need:

(Ny.λy.(Xy))[X↦→y](Nσ)⇝Ny′.((λy′.(Xy′))[X↦→y])(Nλ)⇝Ny′.λy′.(Xy′)[X↦→y]) ⇝∗Ny′.λy′.yy′

N is reminiscent of π-calculus restriction [16]. (Np) and (Nσ) are reminiscent of scope-extrusion. (N∉) is reminiscent of ‘garbage-collection’.

We do not admit a rule ‘s(Na.t) ⇝Na.(st) if a ∉ fv(s)’:

Ny.Ny′.(yy′)⇝∗(Ny.y)Ny′.y′⇝∗(λx.xx)Ny.y ⇝Ny.(λx.xx)y ⇝∗Ny.yy

For similar reasons we do not admit a rule ‘s[b↦→Na.t] ⇝Na.(s[b↦→t]) if a ∉ fv(s)’.

Why the side-conditions on (Nσ)? ck ∉ fv(t) comes from the intuition of N as defining a scope. We need k ≤i for confluence:

NX.(X[x↦→2])⇝(NX.X)[x↦→2](σfv)⇝NX.X

The proof of termination of (sigma) extends smoothly if we add the rules for N to (sigma) (to make a set (sigmanew)). The proof of confluence for the system as a whole also extends smoothly. We see some examples of the use of N in a moment.

6 Programming in the calculus

Call t single-leveled of level i when all variables in it (free or bound) have level i. Then it is easy to prove that notions of free variable and substitution coincide with the ‘traditional’ definitions and we have:

Theorem 6.1

For any i the single-leveled terms of level i, with their reductions, form an isomorphic calculus to λx with garbage collection [3].

As a corollary, the trivial mapping from the untyped λ-calculus to single-leveled terms of level 1 (say), preserves normal forms and strong normalisation.

We can exploit the hierarchy to do some nice things. Here is one example: R = X[x↦→2][y↦→3] can be viewed as a record with ‘handle’ X and with 2 stored at x and 3 at y. Then λW.(W[X↦→x]) applied to R looks up the data stored at x, and λW.(W[X↦→X[x↦→3]]) updates it. In fact these terms do a little more than this, because their effect is the same when applied to a term in which a record with ‘handle’ X is buried deep in the term, perhaps as part of a β-redex or substitution. λW.(W[X↦ → (W[X↦→x])+1]) increments the value stored at x.

Here is an example reduction:

(λW.W[X↦→X[x↦→3]]) R(β)⇝ W[X↦→X[x↦→3]][W↦→R](σσ), (σa), (σfv)⇝∗R[X↦→X[x↦→3]] = X[x↦→2][y↦→3][X↦→X[x↦→3]](σσ)⇝∗X[X↦→X[x↦→3]][x↦→2[X↦→X[x↦→3]]][y↦→3[X↦→X[x↦→3]]](σa), (σb)⇝∗X[x↦→3][x↦→2][y↦→3].

There is some garbage here, but a later look-up on x returns 3, not 2:

(λW.W[X↦→x])(X[x↦→3][x↦→2][y↦→3]) ⇝∗x[x↦→3][x↦→2][y↦→3] ⇝∗3

We can use N to assign fresh storage. The following program, if applied to a value and R, extends R with a fresh location and returns the new record together with a lookup function for the new location:

λZ.Nx.λY.(Y [x↦→Z], λW.W[X↦→x]).

Here we use a pairing constructor (-, -) just for convenience.

Note that we access data in R by applying a substitution for X; in this sense the ‘handle’ X in R is externally visible. We can hide it by λ-abstracting X to obtain λX.(X[x↦→2][y↦→3]). Then lookup at x becomes λW.(Wx) and update becomes λW.λX.(W[X↦→X[x↦→1]]).

We can parameterise over the data stored in the record: λX′.(X′[x↦→X][y↦→Y]). Furthermore a term of the form λX.(X[x↦→X][y↦→X]) can capture a form of self-reference within the record. Finally, λX.(X[x↦→W][y↦→W′]) makes no committment about the data stored.

7 Related work, conclusions, and future work

The LCC of this paper is simpler than the NEWcc [6]. Compare the side-condition of (σa) (there is none) with that of (σa) from [6]. The notion of freshness is simpler and intuitive; we no longer require a logic of freshness, or the ‘freshness context with sufficient freshnesses’, see most of page 4 in [6]. A key innovation in attaining this simplicity is our use of conditions involving level(s) the level of s, which includes information about the levels of free and bound variables.

But there is a price: this calculus has fewer reductions. Notably (σλ′) will not reduce (λai.s)[ck↦→u] where k < i; a rule (σλ′) in [6] does. That stronger version seems to be a major source of complexity.

Still, the LCC is part of something larger yet to be constructed. Other papers on nominal techniques contain elements of the developments we have in mind when we imagine such a system. So for example:

In this paper we cannot α-convert x in λx.X. Nominal terms can: swappings are in the syntax (here swappings are in the meta-level) and also freshness contexts [27]. A problem is that we do not yet understand the theory of swappings for strong variables; the underlying Fraenkel-Mostowski sets model [9] only has (in the terminology of this paper) one level of variable. A semantic model of the hierarchy of variables would be useful and this is current work.

In this paper we cannot deduce x#fv(λx.X) even though for every instance this does hold (for example x#λx.x and x#λx.y). Hierarchical nominal rewriting [7] has a more powerful notion of freshness which can prove the equivalent of x#fv(λx.X). Note that hierarchical nominal rewriting does not have the conditions on levels which we use to good effect in this paper.

We cannot reduce (λx.y)[y↦→Y] because there is no z such that z#Y . We can allow programs to dynamically generate fresh variables in the style of FreshML [19] or the style of a sequent calculus for Nominal Logic by Cheney [5].

We cannot reduce X[x↦→2][y↦→3] to X[y↦→3][x↦→2]. Other work [8] gives an equational system which can do this, and more.

There is no denotational semantics for the LCC. This is current work.

More related work (not using nominal techniques). The calculi of contexts λm and λM [23] also have a hierarchy of variables. They use carefully-crafted scoping conventions to manage problems with α-conversion. Other work [21,11,22] uses a type system; connections with this work are unclear. λc of Bognar’s thesis contains [4, Section 2] an extensive literature survey on the topic of context calculi.

A separation of abstraction λ and binding N appears in one other work we know of [24], where they are called q and ν. In this vein there is [12], which manages scope explicitly in a completely different way, just for the fun. Finally, the reduction rules of N look remarkably similar to π-calculus restriction [16], and it is probably quite accurate to think of N as a ‘restriction in the λ-calculus’.

Ours is a calculus with explicit substitutions. See [15] for a survey. Our treatment of substitution is simple-minded but still quite subtle because of interactions with the rest of the language. We note that the translation of possibly open terms of the untyped λ-calculus into the LCC preserves strong normalisation. One reduction rule, (σfv), is a little unusual amongst such calculi, though it appears as ‘garbage collection’ of λx [3].

The look and feel of the LCC is squarely that of a λ-calculus with explicit substitutions. All the real cleverness has been isolated in the side-condition of (σp); other side-conditions are obvious given an intuition that strong variables can cause capturing substitution (in the NEWcc [6] complexity spilled over into other rules and into a logic for freshness). N is only necessary when variables of different strengths occur, and the hierarchy of variables only plays a rôle to trigger side-conditions.

Further work. Desirable and nontrivial meta-properties of the λ-calculus survive in the LCC including confluence, and preservation of strong normalisation for a natural encoding of the untyped λ-calculus into the LCC. It is possible, in principle at least, to envisage an extension of ML or Haskell [17,26] with meta-variables based on the LCC’s notion of strong and weak variables.

We can go in the direction of logic, treating equality instead of reduction and imitating higher-order logic, which is based on the simply-typed λ-terms enriched with constants such as ∀ : (o →o) →o and ⇒: o →o →o where o is a type of truth-values [29], along with suitable equalities and/or derivation rules. There should be no problem with imposing a simple type system on LCC and writing down a ‘context higher-order logic’. This takes the LCC in the direction of calculi of contexts for incomplete proofs [13,10]. The non-trivial work (in no particular order) is to investigate cut-elimination, develop a suitable theory of models/denotations, and possibly to apply it to model incomplete proofs.

An implementation is current work.

The LCC is simple, clear, and it has good properties. It seems to hit a technical sweet spot: every extension of it which we have considered, provokes significant non-local changes. Often in computer science the trick is to find a useful balance between simplicity and expressivity. Perhaps the LCC does that.

References

[1] Franz Baader and Tobias Nipkow, Term rewriting and all that, Cambridge University Press, 1998.

[2] H. P. Barendregt, The lambda calculus: its syntax and semantics (revised ed.), North-Holland, 1984.

[3] Roel Bloo and Kristoffer Høgsbro Rose, Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection, CSN-95: Computer Science in the Netherlands, 1995.

[4] Mirna Bognar, Contexts in lambda calculus, Ph.D. thesis, Vrije Universiteit Amsterdam, 2002.

[5] James Cheney, A simpler proof theory for nominal logic, FOSSACS, Springer, 2005, pp. 379–394.

[6] Murdoch J. Gabbay, A new calculus of contexts, PPDP ’05: Proc. of the 7th ACM SIGPLAN int’l conf. on Principles and Practice of Declarative Programming, ACM Press, 2005, pp. 94–105.

[7]—, Hierarchical nominal rewriting, LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice, 2006, pp. 32–47.

[8] Murdoch J. Gabbay and Aad Mathijssen, Capture-avoiding substitution as a nominal algebra, ICTAC’2006: 3rd Int’l Colloquium on Theoretical Aspects of Computing, 2006, pp. 198–212.

[9] Murdoch J. Gabbay and A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.

[10] Herman Geuvers and Gueorgui I. Jojgov, Open proofs and open terms: A basis for interactive logic, CSL, Springer, 2002, pp. 537–552.

[11] Masatomo Hashimoto and Atsushi Ohori, A typed context calculus, Theor. Comput. Sci. 266 (2001), no. 1-2, 249–272.

[12] Dimitri Hendriks and Vincent van Oostrom, Adbmal, CADE, 2003, pp. 136–150.

[13] Gueorgui I. Jojgov, Holes with binding power., TYPES, LNCS, vol. 2646, Springer, 2002, pp. 162–181.

[14] Samuel Kamin and Jean-Jacques Lévy, Attempts for generalizing the recursive path orderings, Handwritten paper, University of Illinois, 1980.

[15] Pierre Lescanne, From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions, POPL ’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, 1994, pp. 60–69.

[16] Robin Milner, Joachim Parrow, and David Walker, A calculus of mobile processes, II, Information and Computation 100 (1992), no. 1, 41–77.

[17] Lawrence C. Paulson, ML for the working programmer (2nd ed.), Cambridge University Press, 1996.

[18] A. M. Pitts, Operationally-based theories of program equivalence, Semantics and Logics of Computation (P. Dybjer and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1997, pp. 241–298.

[19] A. M. Pitts and Murdoch J. Gabbay, A metalanguage for programming with bound names modulo renaming, Mathematics of Program Construction. 5th Int’l Conf. , MPC2000, Ponte de Lima, Portugal, July 2000. Proceedings (R. Backhouse and J. N. Oliveira, eds.), LNCS, vol. 1837, Springer-Verlag, 2000, pp. 230–255.

[20] A. M. Pitts and I. D. B. Stark, Operational reasoning for functions with local state, Higher Order Operational Techniques in Semantics (A. D. Gordon and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1998, pp. 227–273.

[21] Masahiko Sato, Takafumi Sakurai, and Rod Burstall, Explicit environments, Fundamenta Informaticae 45:1-2 (2001), 79–115.

[22] Masahiko Sato, Takafumi Sakurai, and Yukiyoshi Kameyama, A simply typed context calculus with first-class environments, Journal of Functional and Logic Programming 2002 (2002), no. 4, 359 – 374.

[23] Masahiko Sato, Takafumi Sakurai, Yukiyoshi Kameyama, and Atsushi Igarashi, Calculi of meta-variables, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings (M. Baaz, ed.), LNCS, vol. 2803, 2003, pp. 484–497.

[24] Francois Maurel Sylvain Baro, The qnu and qnuk calculi : name capture and control, Tech. report, Université Paris VII, 2003, Extended Abstract, Prépublication PPS//03/11//n16.

[25] Terese, Term rewriting systems, Cambridge Tracts in Theoretical Computer Science, no. 55, Cambridge University Press, 2003.

[26] Simon Thompson, Haskell: The Craft of Functional Programming, Addison Wesley, 1996.

[27] C. Urban, A. M. Pitts, and Murdoch J. Gabbay, Nominal unification, Theoretical Computer Science 323 (2004), no. 1–3, 473–497.

[28] Johan van Benthem, Modal foundations for predicate logic, Logic Journal of the IGPL 5 (1997), no. 2, 259–286.

[29]—, Higher-order logic, Handbook of Philosophical Logic, 2nd Edition (D.M. Gabbay and F. Guenthner, eds.), vol. 1, Kluwer, 2001, pp. 189–244.

Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.

Notes

1 This example ‘borrowed’ from [10]. ↩