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

The lambda-context calculus

Murdoch J. Gabbay Stéphane Lengrand

Heriot-Watt University, St-Andrew’s University, Scotland

Abstract

We present a simple 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. These include a Hindley-Milner type system with principal typings and subject reduction, and an applicative characterisation of contextual equivalence.

Key words: Lambda-calculus, calculi of contexts, functional programming, binders, nominal techniques, explicit substitutions, capturing substitution.

Email address: Murdoch.Gabbay@gmail.com, sl@cs.st-andrews.ac.uk (Murdoch J. Gabbay Stéphane Lengrand).

Preprint submitted to Information and Computation 6 June 2007

Contents

1 Introduction 3

2 Syntax, freshness, reductions 5

2.1 Syntax 5

2.2 Levels and Free variables 6

2.3 α-equivalence 6

2.4 Reductions 9

2.5 Example reductions 11

2.6 Comments on the side-conditions 13

3 The substitution action 15

3.1 Termination of (sigma) 15

3.2 Calculating (sigma)-normal forms 17

4 Confluence 18

4.1 Confluence of (sigma) 19

4.2 (beta)-reduction 24

4.3 Combining (sigma) and (beta) 26

5 The untyped lambda-calculus 28

6 A NEW part for the LCC 31

6.1 Some NEW rules 31

6.2 Some false NEW rules 33

7 Hindley-Milner types 34

8 Applicative characterisation of contextual equivalence 40

8.1 Programs, contexts, evaluations, and equivalences 40

8.2 Proof that =ctx equals =ap 41

9 Related work, conclusions, and future work 44

References 48

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.

(We shall use ‘=’ to denote α-equality of terms.)

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) [24,27]. 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. That code might have binders which bind variables in the scope of the ‘hole’ within which we are substituting, whence the need for binders.

This suggests that we should call holes context variables X (distinct from ‘normal’ variables x) 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.

A context calculus can have applications besides aspects of proofs of contextual equivalence.

Consider formalising mathematics in a logical framework based on Higher-Order Logic (HOL) [37]. 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.

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

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 (complete) 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 [14, Section 2, Example 3].

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 ⇝λy.x, giving non-confluent reductions. Dropping α-equivalence entirely is too drastic; we need λy.λx.y to be α-convertible with λz.λx.z so that we can reduce a term such as (λy.λx.y)x.

Solutions include clever control of substitution and evaluation order [30], types to prevent ‘bad’ α-conversions [28,16,29], explicit labels on meta-variables [14,18], and more [4, Section 2]. More on this in the Conclusions.

In this paper we present a new calculus of contexts, the ‘lambda context calculus’ (LCC). We took our technical ideas for handling α-equivalence not from the literature on context calculi cited above, but from nominal unification [36]. 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 LCC by allowing λ-abstraction over the holes and adding β-reduction.

This work has similar goals to the N EWcc previously developed by the first author [9]. The LCC has a simpler and more intuitive set of reduction rules. Indeed there is now only one non-obvious side-condition, it is on (σp); Technical aspects of the previous work have been simplified, clarified, or eliminated altogether. Notably we dispense entirely with the freshness contexts and freshness logic of the N EWcc.

The result is a clean and simple system with a powerful hierarchy of context variables, yet which has the look and feel of an ordinary λ-calculus with explicit substitutions, along with many of the properties which make the λ-calculus so nice to work with. These include confluence, a Hindley-Milner type system with principal typings and subject reduction, and an applicative characterisation of contextual equivalence.

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

2 Syntax, freshness, reductions

2.1 Syntax

We suppose a countably infinite set of disjoint infinite sets of variables A1, A2, . . . , where we write ai, bi, ci, ni, . . . ∈Ai for i ≥ 1.

We shall use a permutative naming convention; we shall always assume that variables that we give different names, are different. Thus ai and bi range permutatively over elements of Ai. In particular, when we write ai and ck we do not assume (unless stated otherwise) that i ≠ k, but we do assume that even if i = k, ai and ck are different variables, because we have given them different names.

There is no particular connection between variables of different levels with the same name. For example a1 and a2 are different variables to which we happen to have given similar names.

Definition 1

The syntax of the lambda context calculus (LCC) is given by:

s, t ::= ai | tt | λai.t | t[ai↦→t].

We use the following conventions:

• As is standard, application associates to the left. For example tt′t′′ is (tt′)t′′.

• We say that the variable ai has level i.

• We call bj stronger than ai when j > i, that is, when bj has higher level than ai. If j < i we call bj weaker than ai. If i = j we say that bj and ai have the same strength.

• We call s[ai↦→t] an explicit substitution of level i (for the atom a, acting on s).

• We call λai.t an abstraction of level i (over the term t).

• Later on we shall use the convention that x, y, z are variables of level 1, X, Y, Z are variables of level 2, and W has level 3.

This syntax has no constant symbols. We might like to have constants like 1, 2, 3, . . . for arithmetic, or ⊤ and ⊥ for truth-values. These behave much like variables ‘of level 0’ which we do not abstract over and for which we do not substitute. We may add them where convenient for illustrative examples. Adding them formally to the syntax causes no particular difficulties aside from adding extra cases to a few proofs.

level(ai) = ilevel(ss′) = max(level(s), level(s′))level(λai.s) = max(i, level(s))level(s[ai↦→t]) = max(i, level(s), level(t))
Fig. 1. Level level(s)
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. 2. Free variables fv(s)

2.2 Levels and Free variables

Definition 2

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

Here max(i, j) is the greater of i and j, and max(i, j, k) is the greatest of i, j, and k.

For the reader’s convenience we mention now that we write ‘level(s1, . . . , sn) ≤ i’ as shorthand for ‘level(s1) ≤i and . . . and level(sn) ≤i’, similarly for ‘level(s1, . . . , sn) < i’; this will be useful later.

Lemma 3

If level(s) = 1 then fv(s) coincides with the usual notion of ‘free variables of’ for the untyped λ-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.

2.3 α-equivalence

Definition 4

A congruence on LCC terms is a binary relation s R s′ satisfying the conditions of Figure 3.

It is easy to show that a congruence is reflexive, so perhaps a better name would be ‘congruent equivalence relation’ — but ‘congruence’ is shorter so we use that.

Definition 5

Define an (atoms) swapping (ai bi)s action inductively by the rules in Figure 4.

Note that the definition of the swapping action is absolutely uniform, literally

ai R ais R s′t R t′st R s′t′s R s′t R t′s[ai↦→s′] R t[ai↦→t′]s R s′λai.s R λai.s′s R s′s′ R ss R s′s′ R s′′s R s′′
Fig. 3. 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)(ai bi)(s[c↦→t]) = ((ai bi)s)[(ai bi)c↦→(ai bi)t] (c any atom)
Fig. 4. 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. 5. Rules for α-equivalence

swapping ai and bi in s without regard to binders et cetera. This is very characteristic of the underlying ‘nominal’ method of this paper [13,36].

We will use swapping (ai bi) on sets of variables S acting pointwise by

(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 6

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

Proof

By easy inductions on the definition of (ai bi)s. 2

Definition 7

If S is a set of variables write ai#S for

• ai ∉S, and

• there exists no variable bj ∈S such that j > i.

Lemma 8

If level(t) < j then bj#fv(t).

Proof

We work by induction on the definition of level(t).

• The case of ai. level(ai) = i. So suppose that i < j. It follows from the definition of fv that bj#fv(ai).

• The case of tt′. level(tt′) = level(t) ∪ level(t′). fv(tt′) = fv(t) ∪ fv(t′). The result follows by the inductive hypothesis.

• The case of λai.t. level(λai.t) = max(i, level(t)), so i < j. fv(λai.t) ⊆ fv(t). The result follows by the inductive hypothesis.

• The case of s[ai↦→t] is similar.

2

Definition 9

Let α-equivalence be the least congruence relation s =α s′ satisfying the conditions of Figure 5.

Suppose that x and y have level 1 and X has level 2. We can easily verify that:

• ai may be α-converted in λai.s if level(s) ≤i. In particular λx.x =α λy.y.

• ai may be α-converted in s[ai↦→t] if level(s) ≤i. In particular x[x↦→X] =α y[y↦→X].

• It is not possible to α-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 can never α-convert variables to variables of other levels.

Lemma 10

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

Parenthetical note: The definitions above are descended from the notion of α-equivalence for nominal terms from [36]. In the terminology used here, that paper considered a syntax with a hierarchy with just levels 1 and 2 and no abstraction over variables of level 2. However LCC is weaker in the sense that nominal terms include swappings in the syntax of terms. We use swappings as an operation on LCC syntax (Definition 5) but we have not included them in the syntax of the LCC itself.

Extending LCC syntax with swappings is future work. To do that it would help to have a better understanding of LCC models (this paper is purely syntactic) and of freshness a#t. Another paper does explore the notion of freshness in the presence of a hierarchy [10].

Theorem 11

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

Proof

The proof is by an easy induction on the derivation rule defining a congruence. We give only the base cases:

• If bi#fv(s) then fv(λai.s) =α fv(λbi.(bi ai)s).

Suppose level(s) ≤i. By Lemma 6 level((bi ai)s) ≤i as well. Then using Lemma 6 we have

fv(λai.s) = fv(s) \ {ai} fv(λbi.(bi ai)s) = ((bi ai)fv(s)) \ {bi}.

It follows by easy set calculations that

fv(λai.s) = fv(λbi.(bi ai)s).

We also observe that swapping ai and bi in s has no effect on the levels of the variables occurring in s, and it follows easily that

level(λai.s) = level(λbi.(bi ai)s).

• If bi#fv(s) then fv(s[ai↦→t]) = fv(((bi ai))s[bi↦→t]). Note that

fv(s[ai↦→t]) = fv(λai.s) ∪fv(t) andfv(((bi ai))s[bi↦→t]) = fv(λbi.(bi ai)s) ∪fv(t).

We use the previous part.

2

Theorem 11 guarantees that we can α-convert without changing the levels or sets of free variables. We use these facts (especially in the proof of confluence when we write ‘renaming if necessary’) without comment henceforth.

2.4 Reductions

Definition 12

Define the reduction relation on terms (modulo α-equivalence) inductively by the rules in Figure 6.

In that figure consistent with our conventions variables with different names are assumed distinct. For example in (σλ′) we assume that ai and ci are distinct.

We shall use the following notation:

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

(β) (λ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. 6. Reduction rules of the LCC

• 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 but using only rules in (ruleset) where

(ruleset) ⊆{(β), (σa), (σfv), (σp), (σσ), (σλ), (σλ′)}.

(Later in Section 6 we extend reduction with rules for a binder И.)

• We call ⇝ terminating when there is no infinite sequences

t1 ⇝· · · ⇝ti ⇝· · · .

Similarly for (ruleset)⇝ .

• We 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 [33,1].

We take a moment to note two easy but important technical properties: reductions decrease the level of a term, and its set of free variables.

Lemma 13

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

Proof

By a series of easy calculations on the rules in Figure 6 and an inductive argument. 2

Lemma 14

If s ⇝s′ then fv(s′) ⊆ fv(s). As a corollary, if s ⇝∗s′ then fv(s′) ⊆ fv(s).

Proof

We work by induction on the derivation of s ⇝s′. The base cases are:

• fv(s[ai↦→t]) = (fv(s) \ {ai} ∪ fv(t)) = fv((λai.s)t).

• fv(ai[ai↦→t]) = fv(t) and fv(t) is a subset of itself.

• Suppose that ai#fv(s). By definition

fv(s[ai↦→t]) = (fv(s) \ {ai}) ∪fv(t).

From Lemma 8 we deduce that fv(s) \ {ai} = fv(s) and so fv(s) is a subset of fv(s[ai↦→t]).

• Suppose that level(s, s′, t) ≤i. Then

fv((ss′)[ai↦→t]) = ((fv(s) ∪fv(s′)) \ {ai}) ∪fv(t) fv(s[ai↦→t]s′[ai↦→t]) = ((fv(s) \ {ai}) ∪fv(t))∪ ((fv(s′) \ {ai}) ∪fv(t)).

The subset inclusion follows by easy calculations on sets.

Other cases are no harder. The inductive argument is straightforward, relying on Lemma 13. The corollary is immediate. 2

2.5 Example reductions

The LCC is a λ-calculus with explicit substitutions [20]. 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.6 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.

• β-reduction. This is a standard β-reduction rule for a calculus with explicit substitutions:

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

• Substitutions on variables. The behaviour of a substitution on a variable depends on the relative strengths of the variable being substituted on, and the variable being substituted for:

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

We can summarise the behaviour of substitutions on variables as follows:

• A strong substitution acting on a weak variable ‘evaporates’.

• A substitution of a variable acting on itself acts ‘normally’.

• A substitution of a variable acting on another variable of the same strength ‘evaporates’.

• A weak substitution on a strong variable ‘stays put’.

• Traversing weak variables.

An explicit substitution for a relatively strong variable may distribute using (σσ) under an explicit substitution for a relatively weaker variable, without avoiding capture:

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

Similarly, an explicit substitutions for a relatively strong variable can traverse a λ-abstraction by a relatively weaker variable, using (σλ), without avoiding capture:

(λ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].

• Substitutions on no weaker substitutions. These terms do not reduce:

X[x↦→z][y↦→z] ̸⇝ X[x↦→y][y↦→z] ̸⇝.

Here (σa) and (σfv) are not applicable because X has level 2 and x has level 1, and (σσ) is not applicable because both x and y have level 1. So weak substitutions are ‘suspended’ — until a stronger substitution turns X into something with internal structure which they can act on.

We imagine stronger versions of the LCC (i.e. with more reductions) in the Conclusions.

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

legal (recall that W has level 3).

Terms like X[x↦→Y] are useful. Examples ‘in nature’ appear in the ∃-introduction rule in logic

Γ ⊢φ[a↦→t] Γ ⊢∃a. φ

where it is understood that φ and t are meta-variables — and in the β-reduction rule

(λa.s)t ⇝s[a↦→t]

where it is understood that s and t are meta-variables.

A term such as X[a↦→W] is useful if there is a surrounding binder which we would like to conveniently link to. For example in the term λX.(X[x↦→W]) W can be bound to X by a substitution arriving from some enclosing context:

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

• Substitutions as terms [x↦→y] is not a term; it cannot be the argument to a function. However λX.X[x↦→y] is a term, and it acts like a substitution in the following sense:

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

As a general scheme, λbj.bj[ai↦→s] encodes the substitution [ai↦→s] if level(s) ≤ j and i < j.

2.6 Comments on the side-conditions

The side-conditions of the LCC reduction rules are where much of the technical ‘magic’ happens.

• (σ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). For example x ∉ fv(X) = {X} and so with a false version of the rule with a side-condition using ∉

instead of # we have reductions

X[x↦→2][X↦→x](σfvFALSE)⇝ X[X↦→x]σa⇝ x
X[x↦→2][X↦→x](σσ)⇝ X[X↦→x][x↦→2[X↦→x]](σa),(σfvFALSE)⇝∗2

This is blocked in LCC, because x#X does not hold.

It is unusual for a garbage collection rule to appear in a calculus of explicit substitutions; usually we can ‘push substitutions into a term until they reach variables’ so we make do with a rule of the form b[a↦→t] ⇝b. In the LCC we cannot always push substitutions into a term until they reach variables, because of the conditions on (σp) and (σλ′). A version of (σfv) does appear in the literature as Bloo’s ‘garbage collection’ [3].

• Recall that the level of a term is the level of the strongest variable it contains, free or bound. Recall also that the side-condition level(s, s′, t) ≤i in (σp) means that level(s) ≤i and similarly for s′ and t.

This condition 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](σpFALSE)⇝ ((λx.X)[y↦→x])(y[y↦→x])(σa)⇝ ((λx.X)[y↦→x])x
((λx.X)y)[y↦→x](β)⇝ X[x↦→y][y↦→x]

The term (λx.X)[y↦→x] does not reduce (more on that in the Conclusions).

• The side-conditions on (σσ), (σλ), and (σλ′) implement that a relatively strong substitution can capture but substitution for variables of the same level avoids capture.

There is no rule

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

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 would cause 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]

Neither of these terms reduces further.

As is the case for the side-condition of (σp), any stronger form of (σλ′) 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

Definition 15

Let (sigma) be equal to the set of rewrite rules other than (β), namely,

(sigma) = {(σa), (σfv), (σp), (σσ), (σλ), (σλ′)}.

This is the part of the LCC that handles substitution — the ‘λ-free’ part of the calculus.

We expect the λ-free part of other calculi of explicit substitutions to be terminating [3,20] and this is useful behaviour — but now we have a hierarchy of variables. Do we lose this good behaviour? No, and in this section we prove it.

3.1 Termination of (sigma)

We show that (sigma)-reduction decreases terms with respect to a well-founded ordering based on mapping LCC terms to first-order terms (no variables, no binders), and using a lexicographic path ordering [19,1] on them.

We use first-order terms in the following infinite signature:

Σ = {⋆/0, Abs/1, App/2} ∪{Subi/2 | m is an integer}.

Here f/n indicates that f has arity n. Symbols have the following precedence:

Subj ≻· · · ≻Subi ≻· · · ≻App ≻Abs ≻⋆ if j > i

We define the lexicographic path ordering by:

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

Here g/m and f/n are first-order symbols and t1, . . . , tn, t′ 1, . . . , t′ n, u1, . . . , um, s are first-order terms.

It is a fact [19,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.

We define a translation from LCC to first-order terms as follows:

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

If t(sigma)⇝ u then t ≫u.

Proof

We check for each reduction rule that the corresponding first-order term on the left, is higher in the lexicographic path ordering than the one on the right. This is routine:

(σa) Subi(⋆, t) ≫t(σfv) Subi(s, t) ≫s (σp) Subi(App(s, s′), t) ≫App(Subi(s, t), Subi(s′, t)) (σσ) Subj(Subi(s, t), u) ≫Subi(Subj(s, u), Subj(t, u)) i < j (σλ) Subj(Abs(s), u) ≫Abs(Subj(s, u))(σλ′) Subk(Abs(s), u) ≫Abs(Subk(s, u))

2

Corollary 17

(sigma)-reduction terminates.

s[ai:=t] = s if ai#fv(s), and otherwise. . .ai[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] otherwise
Fig. 7. Substitution on terms of the LCC
a∗ i= ai(λai.s)∗= λai.(s∗) (s[ai↦→t])∗= s∗[ai:=t∗] (st)∗= (s∗)(t∗)
Fig. 8. The catchily-named ‘the star’ function

We can now make a useful observation. Let x have level 1. It is easy to show that (λx.xx)(λx.xx) has an infinite series of reductions if we allow rules in (sigma) and (β). It follows that — even with a hierarchy of variables — (β) strictly adds to the power of the reduction system.

Definition 18

Call s (sigma)-normal when s(sigma)̸⇝.

By Corollary 17, any chain of (sigma)-reductions must terminate, and by definition it terminates at a (sigma)-normal form.

What does that (sigma)-normal form look like?

3.2 Calculating (sigma)-normal forms

Definition 19

Define a substitution action s[ai:=t] by the equalities in Figure 7.

The precedence of which equality in Figure 7 to use is from top to bottom. Also, when we try to apply the equality (λci.s)[ai:=t] = λci.(s[ai:=t]) we rename ci where possible to satisfy the side condition ci#fv(t).

Lemma 20

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

Proof

By induction on i and then s. We inspect the definition of := and see that each clause can be imitated by a rule for [ai↦→t]. 2

Lemma 21

If s and t are (sigma)-normal then s[ai:=t] is (sigma)-normal.

Proof

By induction on i and then s. 2

Definition 22

Define s∗ inductively by the rules in Figure 8.

Theorem 23

s∗ is a (sigma)-normal form of s.

Proof

There are two results to prove. The first is s(sigma)⇝∗s∗, which is proved by an easy induction on the definition of s∗ (the case of (∗σ) uses Lemma 20). The second is that s∗ is a (sigma)-normal form, which is proved by a routine induction on s, using Lemma 21. 2

4 Confluence

Recall from Definition 15 that (sigma) is the set of rules defined by

(sigma) = {(σa), (σfv), (σp), (σσ), (σλ), (σλ′)}.

It is convenient to define:

Definition 24

Let (beta) be the set {(β), (σλ), (σλ′), (σfv)}.

Note that (sigma) ∪ (beta) is equal to the set of all reduction rules of the LCC.

Note that (sigma) ∩ (beta) is non-empty. We mention the technical reasons for this just after Lemma 39 — it seems to be vital for the proofs to work. Understanding the deeper mathematical reasons for this, if any, is future work.

Theorem 25

⇝ is confluent. That is, if s ⇝∗t1 and s ⇝∗t2 then there is some u such that t1 ⇝∗u and t2 ⇝∗u.

The proof of Theorem 25 occupies this section. Before we give the details we comment on the overall design of the proof.

Roughly speaking there are two standard ways to prove confluence:

(1) Define a so-called parallel reduction relation ⇒. such that ⇒⊆⇝∗ and ⇒∗=⇝∗.

It then suffices to show that if s ⇒t1 and s ⇒t2 then there is some u such that t1 ⇒u and t2 ⇒u.

(An example of the method is in Subsection 4.2.)

(2) Define for each term s a normal form s↓ such that s ⇝∗s↓ and then prove that for all possible reductions s ⇝s′ it is the case that s′ ⇝∗s↓.

Both of these methods are standard [33]. But which to use for the LCC?

It seems that reductions using (β) ‘want’ method 1 above — but (sigma)-reductions ‘want’ method 2. To prove confluence of the LCC, we split the reduction relation into (sigma) and (beta); we prove confluence results by methods 1 and 2 above independently, and then we combine them.

4.1 Confluence of (sigma)

Lemmas 27 and 29 will be useful; Lemma 27 in this subsection and Lemma 29 in Subsection 4.3. Since these results are closely related so we have put them side-by-side here.

We need this technical lemma in a moment:

Lemma 26

If level(t) < j then t[bj:=u] = t.

Proof

By Lemma 8 if level(t) < j then bj#fv(t). The result follows from the definition of [bj:=u]. 2

Lemma 27

If i < j then

s[ai:=t][bj:=u] = s[bj:=u][ai:=t[bj:=u]].

(Note the lack of capture-avoidance condition; this is because i < j.)

Proof

By induction on i and then on the structure of s.

• Suppose s[ai:=t] = s[ai↦→t]. We then have

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

This covers the cases s = ck with k > i, s = s1s2 with level(s1, s2, t) > i, s = s1[ck↦→s2] with k ≥i, s = λck.s1 with k > i, or k = i without ck#fv(t).

• Suppose k ≤i < j. Note that by our permutative convention, ck is distinct

from ai. Then:

ck[ai:=t][bj:=u] = ck[bj:=u] = ckck[bj:=u][ai:=t[bj:=u]] = ck[ai:=t[bj:=u]] = ck.

• The cases of ai[ai:=t][bj:=u] and bj[ai:=t][bj:=u] are easy.

• Suppose that level(s, s′, t) ≤i < j. By Lemma 20 we have (ss′)[ai↦→t] ⇝∗ (ss′)[ai:=t]. By Lemma 13 we have

level((ss′)[ai:=t]) ≤level((ss′)[ai↦→t]) = level(s, s′, t, ai) < j.

Finally by Lemma 26 we have

(ss′)[ai:=t][bj:=u] = (ss′)[ai:=t] (ss′)[bj:=u][ai:=t[bj:=u]] = (ss′)[ai:=t]

• Suppose k < i. Then

s[ck↦→s′][ai:=t][bj:=u] = s[ai:=t][ck:=s′[ai:=t]][bj:=u]ind. hyp.= s[ai:=t][bj:=u][ck:=s′[ai:=t][bj:=u]]ind. hyp.= s[bj:=u][ai:=t[bj:=u]][ck:=s′[bj:=u][ai:=t[bj:=u]]] s[ck↦→s′][bj:=u][ai:=t[bj:=u]] = s[bj:=u][ck:=s′[bj:=u]][ai:=t[bj:=u]]ind. hyp.= s[bj:=u][ai:=t[bj:=u]][ck:=s′[bj:=u][ai:=t[bj:=u]]]

• Suppose k < i. Then

(λck.s)[ai:=t][bj:=u] = λck.(s[ai:=t][bj:=u])ind. hyp.= λck.(s[bj:=u][ai:=t[bj:=u]]) (λck.s)[bj:=u][ai:=t[bj:=u]] = λck.(s[bj:=u][ai:=t[bj:=u]])

• Suppose (renaming ci where possible) that ci#fv(t). Then

(λci.s)[ai:=t][bj:=u] = (λci.s[ai:=t][bj:=u])ind. hyp.= (λci.s[bj:=u][ai:=t[bj:=u]]) (λci.s)[bj:=u][ai:=t[bj:=u]] = (λci.s[bj:=u][ai:=t[bj:=u]])

2

We need a technical lemma for Lemma 29:

Lemma 28

If s is (sigma)-normal and level(s) ≤i then there is no substitution of level i in s.

Proof

By a routine induction on s. 2

Lemma 29

Suppose that level(s, t, u) ≤i and ai#fv(u) (which in view of the condition on levels, means just ai ∉ fv(u)). Suppose also that s, t, and u are (sigma)-normal. Then

s[ai:=t][bi:=u] = s[bi:=u][ai:=t[bi:=u]].
Proof

By induction on the structure of s.

• Suppose k ≤i. Recall that by our permutative convention ck is distinct from ai and bi. Then:

ck[ai:=t][bi:=u] = ck[bi:=u] = ckck[bi:=u][ai:=t[bi:=u]] = ck[ai:=t[bi:=u]] = ck.

• The cases of ai[ai:=t][bi:=u] and bi[ai:=t][bi:=u] are easy.

• We do not need to consider the case ck[ai:=t][bi:=u] for k > i, because then level(ck) > i.

•

(ss′)[ai:=t][bi:=u] = ((s[ai:=t])(s′[ai:=t]))[bi:=u] = (s[ai:=t][bi:=u])(s′[ai:=t][bi:=u])ind. hyp.= (s[bi:=u][ai:=t[bi:=u]])(s′[bi:=u][ai:=t[bi:=u]]) (ss′)[bi:=u][ai:=t[bi:=u]] = ((s[bi:=u])(s′[bi:=u]))[ai:=t[bi:=u]] = (s[bi:=u][ai:=t[bi:=u]])(s′[bi:=u][ai:=t[bi:=u]])

• For the case of s[ck↦→s′], assumed to be be (sigma)-normal, we know from the assumption level(s[ck↦→s′]) ≤i and Lemma 28 that k < i. Hence,

s[ck↦→s′][ai:=t][bi:=u] = s[ai:=t][ck:=s′[ai:=t]][bi:=u]Lem.27= s[ai:=t][bi:=u][ck:=s′[ai:=t][bi:=u]]ind. hyp.= s[bi:=u][ai:=t[bi:=u]][ck:=s′[bi:=u][ai:=t[bi:=u]]] s[ck↦→s′][bi:=u][ai:=t[bi:=u]] = s[bi:=u][ck:=s′[bi:=u]][ai:=t[bi:=u]]Lem.27= s[bi:=u][ai:=t[bi:=u]][ck:=s′[bi:=u][ai:=t[bi:=u]]]

• Suppose k ≥i. Since level(λck.s, t, u) ≤i we can rename ck so that ck#fv(t)∪ fv(u). Then

(λck.s)[ai:=t][bi:=u] = (λck.(s[ai:=t]))[bi:=u] = (λck.(s[ai:=t][bi:=u]))ind. hyp.= (λck.(s[bi:=u][ai:=t[bi:=u]])) (λck.s)[bi:=u][ai:=t[bi:=u]] = (λck.(s[bi:=u]))[ai:=t[bi:=u]] = (λck.(s[bi:=u][ai:=t[bi:=u]]))

k ≥i so level(s) ≤ level(λck.s), and this is why we can use the inductive hypothesis.

• The case of (λck.s)[ai:=t][bi:=u] where k < i is similar, but easier.

2

We now come back to the confluence of (sigma).

Lemma 30

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

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

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

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

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

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

Proof

(1) (ai[ai↦→t])∗= ai[ai:=t∗] = t∗.

(2) Recall that we assume k ≤i.

(ck[ai↦→t])∗= ck[ai:=t∗] = ck = c∗ k.

(3) Recall that we assume that level(s, s′, t) ≤i.

((ss′)[ai↦→t])∗= (s∗[ai:=t∗])(s′∗[ai:=t∗]) ((s[ai↦→t])(s′[ai↦→t]))∗= (s∗[ai:=t∗])(s′∗[ai:=t∗]).

(4) Recall that we assume that i < j. Using Lemma 27

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

(5) Recall that we assume that i < j.

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

(6)

((λai.s)[ck↦→u])∗= (λai.s∗)[ck:=u∗] = λai.(s∗[ck:=u∗]) (λai.(s[ck↦→u]))∗= λai.(s∗[ck:=u∗])

2

Lemma 31

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

Proof

By definition (s[ai↦→t])∗= s∗[ai:=t∗]. We use Lemma 20. 2

Lemma 32

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

Proof

We work by induction on the derivation of s(sigma)⇝ s′, see Figure 6.

In this proof, and in this proof only, we shall write ⇝ for (sigma)⇝ and ⇝∗ for (sigma)⇝∗.

• (Rapp) Suppose s ⇝s′ so that st ⇝s′t.

By inductive hypothesis s′ ⇝∗s∗ and by Theorem 23 t ⇝∗t∗, so also s′t ⇝∗s∗t∗= (st)∗. The case of (Rapp′) is similar.

• (Rλ) Suppose s ⇝s′ so that λai.s ⇝λai.s′. By inductive hypothesis s′ ⇝∗s∗, and so λai.s′ ⇝∗λai.(s∗) = (λai.s)∗.

• (Rσ) Suppose s ⇝s′ so that s[ai↦→t] ⇝s′[ai↦→t].

By inductive hypothesis s′ ⇝∗s∗ and by Theorem 23 t ⇝∗t∗, so also s′[ai↦→t] ⇝∗s∗[ai↦→t∗]. By Lemma 31 s∗[ai↦→t∗] ⇝∗ (s[ai↦→t])∗. The case of (Rσ′) is similar.

• Now suppose that s(sigma)⇝ s′ is derived using one of the rules (σa), (σc), (σp), (σσ), (σλ), or (σλ′). In these cases we use Theorem 23 and the relevant part of Lemma 30.

2

Theorem 33

(sigma)⇝ is confluent.

Proof

By an easy inductive argument using Lemma 32. 2

(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] =⇒u(R ∈(beta))s =⇒s′t =⇒t′s′t′ Rϵ⇝u(Pappϵ)st =⇒u(R ∈(beta))
Fig. 9. Parallel reduction relation for the LCC

4.2 (beta)-reduction

Definition 34

Inductively define the parallel reduction relation =⇒ (for (beta)) by the rules in Figure 9.

In rules (Pσϵ) and (Pappϵ), s′t′ Rϵ⇝u and s′[ai↦→t′] Rϵ⇝u indicate a top-level rewrite with any R ∈ (beta) — that is, s′t′R⇝u and s′[ai↦→t′] R⇝u respectively are derivable without using (Rapp), (Rapp′), (Rλ), (Rσ), or (Rσ′).

Lemma 35

(1) s =⇒s.

(2) If s =⇒s′ then s(beta)⇝∗s′.

(3) If s(beta)⇝ s′ then s =⇒s′.

As a corollary, s =⇒∗s′ if and only if s(beta)⇝∗s′.

Proof

All parts are by routine inductions:

(1) By induction on the syntax of s.

(2) By induction on the derivation of s =⇒s′.

(3) By induction on the derivation of s(beta)⇝ s′.

2

Corollary 36

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

Proof

From Lemma 35 and Lemma 14. 2

Lemma 37

=⇒ 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′′′).

For simplicity we just consider possible pairs of rules which could derive s =⇒ s1 and s =⇒s2.

• (Pa) and (Pa). There is nothing to prove.

• (Pσ) and (Pσ). s =⇒s′ and t =⇒t′ and also s =⇒s′′ and t =⇒t′′ so that by (Pσ) and (Pσ)

s′[ai↦→t′] ⇐= s[ai↦→t] =⇒s′′[ai↦→t′′].

By inductive hypothesis there are s′′′ and t′′′ such that

s′ =⇒s′′′ ⇐= s′′and t′ =⇒t′′′ ⇐= t′′.

It follows that

s′[ai↦→t′] =⇒s′′′[ai↦→t′′′] ⇐= s′′[ai↦→t′′].

• (Pσ) and (Pσϵ) for (σλ).

Suppose s =⇒s′ and t =⇒t′ and also s =⇒s′′ and t =⇒t′′. Suppose also that i < j so that by (Pσ) and (Pσϵ) for (σλ)

(λai.s′)[bj↦→t′] ⇐= (λai.s)[bj↦→t] =⇒λai.(s′′[bj↦→t′′]).

By inductive hypothesis there are s′′′ and t′′′ such that

s′ =⇒s′′′ ⇐= s′′and t′ =⇒t′′′ ⇐= t′′.

Using (Pσϵ) for (σλ) and (Pσ)

(λai.s′)[bj↦→t′] =⇒λai.(s′′′[bj↦→t′′′]) ⇐= λai.(s′′[bj↦→t′′]).

• The case of (Pσϵ) for (σλ) and (Pσ) is similar.

• (Pσ) and (Pσϵ) for (σλ′).

Suppose s =⇒s′ and u =⇒u′ and also s =⇒s′′ and u =⇒u′′. Suppose also that (renaming ai 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 36 ai#u′′′. Using (Pσϵ) for (σλ′) and (Pσ)

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

• (Pλ) with (Pλ).

Suppose s′ ⇐= s =⇒s′′ so that λai.s′ ⇐= λai.s =⇒λai.s′′. By inductive hypothesis there is some s′′′ such that s′ =⇒s′′′ ⇐= s′′. By (Pλ) also

λai.s′ =⇒λai.s′′′ ⇐= λai.s′′.

Other cases are similar and no harder. 2

Theorem 38

(beta)⇝ is confluent.

Proof

By Lemma 35 and Lemma 35 and a standard argument [2]. 2

4.3 Combining (sigma) and (beta)

Lemma 39

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:

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

This can be closed by:

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

• (β) has a divergence with (σp) in the case that i = j and level(s, t, u) ≤i:

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

We suppose, renaming ai if necessary, that ai#u.

By Corollary 36 level(s′, t′, u′) ≤i. By Lemma 20 and Theorem 23,

s′[ai↦→t′][bi↦→u′](sigma)⇝∗(s′)∗[ai:=t′][bi:=u′]

and by Lemma 29 this is equal to (s′)∗[bi:=u′][ai:=t′[bi:=u′]].

On the other hand (also using Lemma 20 and Lemma ??):

(λai.s)[bi↦→u](t[bi↦→u]) =⇒s′[bi↦→u′][ai↦→t′[bi↦→u′]](sigma)⇝∗(s′)∗[bi:=u′][ai:=t′[bi:=u′]]

which closes the divergence above.

• (σσ) has a divergence with (σλ). Suppose that k < i < j:

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

This can be closed by:

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

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

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

We know that bj#fv(t) because ci#fv(t) and i < j. We then deduce bj#fv(t′) using Corollary 36. We use this to justify the =⇒-rewrite which uses (σfv) in a moment.

This can be closed by:

λ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]] =⇒λci.(s[bj↦→u][ai↦→t])

2

We promised to explain why (σ) ∩ (β) ≠ ∅. We can now do so by reference to the details of the proof of Lemma 39.

• (σλ) ∈ (beta) and (σλ′) ∈ (beta) because otherwise the two cases of (σp) and (β) above, would not work.

• (σfv) ∈ (beta) because otherwise the case of (σσ) with (σλ′) would not work.

We can easily generalise this lemma to several σ-steps:

Lemma 40

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 length of the path s(sigma)⇝∗s′′. The case of the empty path is trivial. Otherwise we have s(sigma)⇝∗t(sigma)⇝ s′′ and the induction hypothesis provides t′ such that s′ (sigma)⇝∗t′ and t =⇒t′. Lemma 39 then provides s′′′ such that t′ ⇝∗s′′′ and s′′ =⇒s′′′. 2

We now generalise this lemma even further:

Lemma 41

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

Proof

Again, we work by induction on the length of the path s ⇝∗s′′. The case of the empty path is trivial. Otherwise we have s ⇝∗t(sigma)⇝ s′′ or s ⇝∗t(β)⇝s′′. In both cases, the induction hypothesis provides t′ such that s′ ⇝∗t′ and t =⇒t′ (respectively s(sigma)⇝∗s′). In the former case, Lemma 39 (respectively Theorem 33) provides s′′′ such that t′ ⇝∗s′′′ and s′′ =⇒s′′′ (respectively s′′ (sigma)⇝∗s′′′). In the latter case, Lemma 37 (respectively Lemma 40) provides s′′′ such that t′ ⇝∗s′′′ and s′′ =⇒s′′′ (respectively s′′ (sigma)⇝∗s′′′). 2

We can now prove Theorem 25:

Proof

Suppose that s ⇝∗t and s ⇝∗t′. We prove that there exists s′ such that t ⇝∗s′ and t′ ⇝∗s′, by induction on the length of the reduction path s ⇝∗t. In the case of the empty path, t = s ⇝∗t′. Otherwise, we have either s ⇝∗s′′ (sigma)⇝ t or s ⇝∗s′′ (beta)⇝ t. In both cases, the induction hypothesis provides t′′ such that s′′ ⇝∗t′′ and t′ ⇝∗t′′, and then Lemma 41 provides s′′′ such that t ⇝∗s′′′, and t′′ =⇒s′′′ or t′′ (sigma)⇝∗s′′′, and in both cases we have t′′ ⇝∗s′′′ as required. 2

5 The untyped lambda-calculus

We show how to translate the untyped λ-calculus into the LCC.

For convenience, we use the variables of level 1 in the LCC as variables in our λ-calculus; when we translate the λ-calculus into the LCC, we will use this identification.

Terms of the untyped λ-calculus are given by

e ::= x | ee | λx.e.

λ binds x in λx.e. This is standard [2].

We define a free variables of fv(t) function in the usual way:

fv(x) = {x} fv(ee′) = fv(e) ∪fv(e′) fv(λx.e) = fv(e) \ {x}.

Call e open when there exists some x such that x ∈ fv(e).

Define a capture-avoiding substitution action inductively by:

x[x:=e] = x y[x:=e] = y (e1e2)[x:=e] = (e1[x:=e])(e2[x:=e]) (λx′.e′)[x:=e] = λx′.(e′[x:=e]) (x′ ∉fv(e))

Here we may assume x′ does not occur in e because we have equated syntax up to binding by λ.

Define a reduction relation inductively by:

(λx.e)e′ →e[x:=e′]e1 →e′ 1e2 →e′ 2e1e2 →e′ 1e′ 2e →e′λx.e →λx.e′

We call e a normal form or value when there is no e′ such that e →e′. Note that normal forms may be open.

A translation into the LCC is given by:

[[ x ]] = x [[ ee′ ]] = [[ e ]] [[ e′ ]] [[ λx.e ]] = λx.[[ e ]]

The following results are very easy to prove:

Lemma 42

fv(e) = fv([[ e]] ).

Proof

We consider the clauses of the definition of fv above, and of the definition of fv from Figure 2, and we see that they coincide in the special case that only variables of level 1 appear. 2

Lemma 43

[[ e[x:=e′] ]] = [[ e]] [x:=[[ e′]] ].

Proof

We work by induction on the structure of e.

• [[ x[x:=e′] ]] = [[ e′ ]] = x[x:=[[ e′ ]] ].

• [[ (e1e2)[x:=e′] ]] = [[ e1[x:=e′](e2[x:=e′]) ]] = [[ e1[x:=e′] ]] [[ e2[x:=e′ ]] ])ind.hyp.= [[ e1 ]] [x:=[[ e′ ]] ]([[ e2 ]] [x:=[[ e′ ]] ]) = ([[ e1 ]] [[ e2 ]] )[x:=[[ e′ ]] ] = [[ e1e2 ]] [x:=[[ e′ ]] ].
• [[ (λy.e)[x:=e′] ]] = [[ λy.(e[x:=e′]) ]] = λy.[[ e[x:=e′] ]] = λy.([[ e ]] [x:=[[ e′ ]] ]) = (λy.[[ e ]] )[x:=[[ e′ ]] ]Lemma 42= [[ λy.e ]] [x:=[[ e′ ]] ].

Here we assume that y ∉ fv(e′).

2

Theorem 44

If e →e′ then [[ e]] ⇝∗ [[ e′]] .

Proof

We work by induction on the derivation of e →e′.

• The case (β). Then (λx.e)e′ →e[x:=e′], where (renaming x if necessary) we choose x ∉ fv(e′).

[[ (λx.e)e′ ]] = (λx.[[ e ]] )[[ e′ ]] ⇝[[ e ]] [x↦→[[ e′ ]] ]Lemma 20⇝∗[[ e ]] [x:=[[ e′ ]] ].Lemma 43= [[ e[x:=e′] ]] .

The other cases are easy. 2

Write e ↛ when there is no e′ such that e →e′. If e ↛ call e a normal form.

Lemma 45

(Preservation of strong normalisation) If e is a normal form then [[ e]] is a normal form.

As a corollary, if e is any untyped λ-term, then if e has a normal form then so does [[ e]] .

Proof

The corollary follows by Theorem 44.

It is a fact [2] that the normal forms of the untyped λ-calculus are inductively characterised (as a subset of the set of terms of the untyped λ-calculus) by:

V ::= x | xV . . . V | λx.V.

The proof is by induction on V .

• [[ x ]] = x and we check the reduction rules of the LCC and observe that x is a normal form.

• [[ xV1. . . Vn]] = x[[ V1]] . . . [[ Vn]] . We check the reduction rules of the LCC and observe that if [[ V1]] , . . . , [[ Vn]] are normal forms, then so is x[[ V1]] . . . [[ Vn]] .

• [[ λx.V ]] = λx.[[ V]] . By assumption [[ V]] is a normal form. We check the reduction rules of the LCC and observe that if [[ V]] is a normal form then so is λx.[[ V]] .

2

6 A NEW part for the LCC

6.1 Some NEW rules

LCC λ-abstraction is weak in the sense that for example x is not α-convertible in λx.X, if x has level 1 and X has level 2.

Suppose we really do want to bind x in λx.X. That is, suppose we want to recover the notion of ‘local variable’ which the traditional λ-calculus (without a hierarchy of levels) identifies with functional abstraction.

We extend the syntax of the LCC as follows:

s, t ::= . . . |Иai.t.

We extend the definition of level and fv (Definition 2) with clauses

level(Иai.s) = max(i, level(s)) fv(Иai.s) = fv(s) \ {ai}.

We extend the definition of congruence (Definition 4) with a clause

s R s′Иai.s RИai.s′.

We extend the definition of swapping (Definition 5 ) with a clause

(ai bi)Иc.s =И(ai bi)c.(ai bi)s

where c is any atom.

We extend the definition of α-equivalence (Definition 9) with a clause

Иai.s =αИbi.(bi ai)s if bi ∉fv(s).

Note the difference that in α-equivalence for λ-abstraction we check bi#fv(s) (Definition 7), and in α-equivalence for И-binding we check bi ∉ fv(s).

Variables bound by И rename regardless of whether stronger variables are present.

For example take x and y to be variables of level 1, and X and Y to be variables of level 2. Then

λx.X ≠α λy.X butИx.λx.X =αИy.λy.X.

We add reduction rules

(Иp) (Иai.s)t ⇝Иai.(st) ai ∉fv(t)(Иσ) (Иck.s)[ai↦→t] ⇝Иck.(s[ai↦→t]) k ≤i, ck ∉fv(t)(И∉)Иai.s ⇝s ai ∉fv(s)s ⇝s′(RИ)Иai.s ⇝Иai.s′

И has behaviour similar to that of π-calculus restriction [21].

• (Иp) and (Иσ) are reminiscent of scope-extrusion.

• (И∉) is reminiscent of ‘garbage-collection’.

Here is an example reduction which exploits И:

(λX.Иx.λx.X)x(β)⇝(Иx.λx.X)[X↦→x](Иσ)⇝Иx′.((λx′.X)[X↦→x])(Иλ)⇝Иx′.λx′.(X[X↦→x])(Иa)⇝Иx′.λx′.x

Compare with a pair of related rewrites in the syntax without И:

(λX.λx.X)x ⇝∗λx.x (λX.λy.X)x ⇝∗λy.x.

So И binds and this is separated from the functional abstraction implemented by λ.

LCC syntax permits И also not directly above λ, for example in Иx.x. This behaves like a constant symbol and indeed fv(Иx.x) = ∅ (though note that level information is preserved; level(Иai.ai) = i). The И which binds x ensures that it can never be substituted for:

(Иx.x)[x↦→t](Иσ)⇝Иx′.(x′[x↦→t])(σfv)⇝Иx′.x′ =αИx.x.

(Recall that we take terms up to α-equivalence when discussing reductions.)

We shall make no use of terms of the form Иx.x in the examples to come. In this paper we are only interested in И to restore α-conversion behaviour to λ-abstracted variables which have been abstracted over a scope containing stronger variables. However, we expect a better understanding of И to be important for future work.

6.2 Some false NEW rules

We do not admit a rule

(ИpFALSE) s(Иa.t) ⇝Иa.(st) a ∉fv(s).

With (ИpFALSE) we can reduce as follows:

(λx.xx)Иy.y(ИpFALSE)⇝Иy.(λx.xx)y(β),(σp),(σa),(σa)⇝∗Иy.yy(λx.xx)Иy.y(β),(σp),(σa),(σa)⇝∗(Иy.y)Иy′.y′(Иp),(ИpFALSE)⇝∗Иy.Иy′.(yy′).

It is a fact that these terms are normal forms and they are not equal.

We can have an intuition of И as ‘generating a fresh variable symbol’. Then (ИpFALSE) (with the other rules of the LCC) lets us make a non-confluent choice of whether to generate a name, then copy, or copy and then generate.

For similar reasons we do not admit (ИσFALSE):

(ИσFALSE) s[b↦→Иa.t] ⇝Иa.(s[b↦→t]) a ∉fv(s).

Why the side-conditions on (Иσ)? Clearly the condition ck ∉ fv(t) comes from the intuition of И as defining a scope. We insist on k ≤i to guarantee confluence:

(ИX.x)[x↦→2](σfv)⇝ИX.x(И∉)⇝ x(ИX.x)[x↦→2](ИσFALSE)⇝ИX.(x[x↦→2])(σa)⇝ 2.

Proofs extend smoothly to the calculus extended with rules for И, including confluence and termination of (sigma) extended with the rules for И.

7 Hindley-Milner types

Some basic motivation: a type system is a logic (often a decidable logic) on terms, which allows us to reason on terms without having to evaluate them. For example, in ML if a term types has type integer, by Subject Reduction the term will always have type integer no matter how we evaluate it, and if it reduces to a normal form that normal form will be an integer. So there is no ‘one’ type system; it depends what properties we are interested in.

Hindley-Milner typing [7] is a simple and successful polymorphic type system which underlies functional programming languages such as Erlang [39], ML [23], or Haskell [34]. As such it is both a ‘working (functional) programmer’s’ tool and a starting point for more complex schemes. If the LCC interacts well with it, then a hierarchy of variables can be implemented, at least in principle, as an extension of functional programming as we know it in common practice.

Fix infinitely many type variables α, β ∈ TyVar. Types and type schemes are defined by:

τ ::= α | (τ, τ) | τ →τ σ ::= τ | ∀α. σ.

Let a type substitution, we generally write S or T, be a function from type variables α to types τ such that Sα = α for all but finitely many α. Type substitutions act on types in the standard way. Write τ ⪯σ when there is some substitution S such that

• σ = ∀α1. · · · ∀αn. τ ′ (we shall just write σ = ∀α. τ for this),

• Sα ≠ α implies that α occurs in α (we may say ‘S acts only on variables in α’), and

• τ = Sτ ′.

Also write tyv τ for the type variables appearing in τ.

A type context is a finite set of pairs {x1 : σ1, . . . , xn : σn} such that if xi = xj then i = j for 1 ≤i, j ≤n. Type contexts may be empty. Γ ranges over type contexts.

Then typing rules are as follows:

ai : σ ∈Γ τ ⪯σ(Tya)Γ ⊢ai : τΓ, ai : τ ⊢s : τ ′(Tyλ)Γ ⊢λai.s : τ →τ ′Γ ⊢s′ : τ ′Γ, ai : ∀α. τ ′ ⊢s : τ α = tyv τ ′ \ tyv Γ(Tyσ)Γ ⊢s[ai↦→s′] : τΓ, nj : α ⊢s : τ nj, α ∉Γ(TyИ)Γ ⊢Иnj.s : τΓ ⊢s : τ →τ ′Γ ⊢t : τ(Typ)Γ ⊢st : τ ′

The notation nj, α ∉ Γ in (TyИ) is shorthand for ‘nj and α do not occur anywhere in the syntax of Γ’. The notation tyv Γ in (Tyσ) is shorthand for the type variables occurring free in Γ. For example

tyv {c : ∀α. α →β} = {β}.

Abusing notation write Γ \ c for the typing context obtained from Γ by removing from it c : σ′ if there is some σ′ such that c : σ′ ∈ Γ.

Write Γ, c : σ for (Γ \ c) ∪{c : σ}.

We have to be a little careful proving Lemma 46. In ‘normal’ λ-calculus we can always rename a λ-abstracted variable to avoid any clash with names in the type context, if this is convenient. In LCC this is not the case; for example if x has level 1 and X has level 2, then we cannot rename x in λx.X. This difficulty is easily surmounted with just a little care, as follows:

If S is a finite set of variables write Γ|S for the typing context Γ restricted to S; for example {c : τ, c′: τ ′}|{a,c} = {c : τ}.

Lemma 46

(Weakening) Γ ⊢s : τ if and only if Γ|fv(s) ⊢s : τ.

As a corollary, if c ∉ fv(s) then if Γ ⊢s : τ then Γ, c : σ′ ⊢s : τ. Here c is any variable.

Proof

We prove the first part by induction on the derivation; the corollary is an easy consequence of it:

• The case of (Tya). . . . is routine.

• The case of (Tyλ). Suppose Γ, ai: τ ⊢s : τ ′. By inductive hypothesis

(Γ, ai : τ)|fv(s) ⊢s : τ ′.

By some easy set calculations, and using the corollary if ai ∉ fv(s),

Γ|fv(s)\{ai}, ai : τ ⊢s : τ ′.

We may then use (Tyλ) to deduce that

Γ|fv ⊢λai.s : τ →τ ′

as required.

• The case of (Tyσ). Suppose that Γ ⊢s′: τ ′ and Γ, ai: ∀α. τ ′ ⊢s : τ where α = tyv τ ′ \ tyv Γ. By inductive hypothesis

Γ|fv(s′) ⊢s′ : τ ′and (Γ, ai : ∀α. τ ′)|fv(s) ⊢s : τ.

By elementary calculations on sets and using the corollary if ai ∉ fv(s) we deduce that

Γ|(fv(s)\{ai})∪fv(s′) ⊢s′ : τ ′and Γ|(fv(s)\{ai})∪fv(s′), ai : ∀α. τ ′ ⊢s : τ.

The result follows observing that fv(s[ai↦→s′]) = (fv(s) \ {ai}) ∪ fv(s′).

• The case of (TyИ). Suppose that Γ, nj : α ⊢s : τ where nj and α do not occur in Γ. By inductive hypothesis (Γ, nj : α)|fv(s) ⊢s : τ. By elementary set calculations and using the corollary if nj ∉ fv(s) we deduce that Γ|fv(s), nj : α ⊢s : τ. The result follows.

• The case of (Typ) . . . is easy.

2

Theorem 47

(Soundness) If Γ ⊢s : τ and s ⇝s′ then Γ ⊢s′: τ.

Proof

We check the rules for ⇝.

• The case of (β). Suppose that Γ ⊢ (λai.s)t : τ ′ is derivable. By following the typing derivation rules we see that for some τ,

Γ, ai : τ ⊢s : τ ′and Γ ⊢t : τ

must be derivable. It is then easy to use (Tyσ) to deduce that Γ ⊢s[ai↦→t] : τ, since τ ⪯∀α. τ for any α.

• The case of (σa) . . . is easy.

• The case of (σfv). Suppose that Γ ⊢s[ai↦→t] : τ and suppose that ai#fv(s). It follows that ai ∉ fv(s). By following the typing derivation rules we see that

Γ ⊢t : τ ′Γ, ai : ∀α. τ ′ ⊢s : τ

where α = tyv τ ′ \ tyv Γ. Now if ai ∉ fv(s) then by Lemma 46 also Γ ⊢s : τ and we are done.

• The case of (σp). Suppose that Γ ⊢ (s′s)[ai↦→t] : τ ′. Then for some τ ′′ is must be that

Γ, ai : ∀α. τ ′′ ⊢s : τ Γ, ai : ∀α. τ ′′ ⊢s′ : τ →τ ′Γ ⊢t : τ ′′.

Here α = tyv τ ′′ \ tyv Γ. Using (σp) it is immediate that

Γ ⊢(s[ai↦→t])(s′[ai↦→t]) : τ ′.

• The case of (σσ). Suppose Γ ⊢s[ai↦→t][bj↦→u] : τ. Then for some τ ′ and τ ′′,

Γ, bj : ∀α′′. τ ′′, ai : ∀α′. τ ′ ⊢s : τ Γ, bj : ∀α′′. τ ′′ ⊢t : τ ′Γ ⊢u : τ ′′.

Here

α′′ = tyv τ ′′ \ tyv Γ and α′ = tyv τ ′ \ tyv (Γ, ∀α′′. τ ′′).

It is not hard to calculate that α′ = α′′, so we write α for both henceforth. From this we can calculate that

Γ, ai : ∀α. τ ′ ⊢s[bj↦→u] : τ and Γ ⊢t[bj↦→u] : τ ′

and from this we can conclude that

Γ ⊢s[bj↦→u][ai↦→t[bj↦→u]] : τ

as required.

• The cases of (σλ) and (σλ′). Suppose Γ ⊢ (λnj.t)[ai↦→u] : τ →τ ′ is derivable. By following the typing derivation rules we see that

Γ ⊢u : τ ′′and Γ, ai : ∀α. τ ′′, nj : τ ⊢t : τ ′

must be derivable, where α = tyv τ ′′ \ tyv Γ. Without loss of generality we rename elements of α to be disjoint from tyv τ. It is now not hard to derive Γ ⊢λnj.(t[ai↦→u]) : τ →τ ′, using Lemma 46 to weaken Γ ⊢u : τ ′′ to Γ, nj : τ ⊢u : τ ′′.

• The case of (Иp). Suppose that Γ ⊢ (Иnj.s)t : τ ′ is derivable where (renaming nj if necessary) we suppose nj does not occur in t or Γ. Then

Γ, nj : α ⊢s : τ →τ ′and Γ ⊢t : τ

are derivable, where α ∉ Γ. By Lemma 46 also Γ, nj : α ⊢t : τ is derivable. It is now easy to derive Γ ⊢Иnj.(st) : τ ′.

• The cases of (Иσ) and (И∉) are easy.

2

We use the following technical lemma in Theorem 49:

Lemma 48

If Γ ⊢s : τ then SΓ ⊢s : Sτ.

Proof

By induction on the derivation of Γ ⊢s : τ. 2

Write (S′, τ ′) ⪯ (S, τ) when there is some T ′ such that

• S′ = T ′S (type substitutions are written prefix, so T ′S is ‘S followed by T ′’), and

• τ ′ = T ′τ.

A type problem is a pair (Γ ⊢? s). A solution to (Γ ⊢? s) is a pair (S, τ) such that SΓ ⊢s : τ. A principal solution is a solution (S, τ) which is maximal amongst all solutions to (Γ ⊢? s) in the ordering given by ⪯.

Theorem 49

If Γ ⊢? s has a solution, then it has a principal solution.

Proof

A principal solution (S, τ) is calculated by the algorithm below — the rules are read bottom-up, and we write (Γ ⊢sol s) for the pair (S, τ) which is being calculated:

(Γ, ai : α ⊢sol s) = (S, τ) (Γ ⊢sol λai.s) = (S, Sα →τ)(Γ ⊢sol s) = (S, τ) S′′=mgu(S′τ, τ ′ →α) (SΓ ⊢sol s′) = (S′, τ ′) α∉S, S′, Γ, s, s′(Γ ⊢sol ss′) = (S′′S′S, S′′α)(Γ ⊢sol s′) = (S′, τ ′) α=tyv τ ′\tyv (S′, Γ) (S′Γ, ai : ∀α. τ ′ ⊢sol s) = (S, τ) (Γ ⊢sol s[ai↦→s′]) = (SS′, τ) (Γ, ai : α ⊢sol s) = (S, τ) α ∉Γ(Γ ⊢solИai.s) = (S, τ)ai : ∀α. τ ∈Γ (Γ ⊢sol ai) = (Id, τ)

In the rule for ai, Id is the identity type substitution, which is such that Idα = α.

In the rule for application mgu(S′τ, τ ′ →α) is the most general unifier of S′τ and τ ′ →α; that is it is a substitution such that S′′S′τ = S′′(τ ′ →α) (a unifier of S′τ and τ ′ →α) which is msot general in the sense that all other unifiers are of the form S′′′S′′ for some S′′′. This is standard, see elsewhere [7]. The mgu need not exist, for example mgu(α′, α′ →α) does not exist. It is part of the condition for using the rule for application above, that mgu(S′τ, τ ′ →α) does exist. It is a fact that if a unifier of two types exists, then a most general unifier exists.

In the rule for И, consistent with previous usage α ∉ Γ means ‘α does not occur anywhere in the syntax of Γ’.

The typing rules and principal types algorithm above are identical to those of the standard Hindley-Milner; we give our explicit substitution exactly the rules for the ML let construct. 2

The proofs transfer to this setting unchanged from the original presentations [7,6], because the definitions are identical — except for the case of И, which is new.

It is routine to show by induction that if (Γ ⊢sol s) exists then it is a solution to Γ ⊢? s.

It remains to show that if a solution to (Γ ⊢? s) exists, then the algorithm for calculating (Γsols) calculates a principal solution. We consider only the cases of ai and Иai.s:

• The case of ai. Suppose that

S′Γ ⊢ai : τ ′.

By the form of the typing rules it must be that ai : ∀α. τ ∈ Γ for some α and τ such that τ ′ = S′τ. Here we assume (renaming if necessary) that S′ acts trivially on α and that no variable in α occurs free in Γ. We take T = S′, and we are done.

• The case of Иai.s. Suppose that

S′Γ ⊢Иai.s : τ ′.

By the form of the typing rules it must be that

S′Γ, ai : α ⊢s : τ ′.

By inductive hypothesis (Γ ⊢sol s) calculates a principal solution, write it (S, τ), so there is some T such that TS = S′ and TSτ = τ ′, and we are done.

2

In conclusion, the type system is almost identical to a standard Hindley-Milner type system for polymorphic types. The typing rule for explicit substitutions is identical to that of ML let. The hierarchy of variables does not damage the type system in any way. There also seems no a priori reason that LCC would not accommodate any other type systems developed for functional programming.

2 This is one of those ideas which is instantly obvious — in retrospect.↩

8 Applicative characterisation of contextual equivalence

As our final theoretical investigation we consider contextual equivalence of the LCC.

8.1 Programs, contexts, evaluations, and equivalences

It is convenient to introduce a constant ⊤ such that ⊤̸⇝.

Definition 50

Call s a program when fv(s) = ∅.

As is our convention, take x to have level 1 and X to have level 2. For example:

• x and λx.X are not programs; fv(x) = {x} and fv(λx.X) = {X}.

• λx.x and λx.(X[X↦→x]) are programs.

If s is a program write

s↘ when s ⇝∗⊤

and say that s evaluates.

Call C a context when

• C is a program, and

• C = λdl.D where l = level(D) and dl is the only variable of level l in D.

We may abuse notation and call D a context.

For example:

• λX.X, λX.λx.(xX)X, and λX.⊤ are contexts.

• λX.x is not a context because it is not a program; fv(λX.x) = {x}.

• λx.λX.Xx is not a context.

• λX.λY.XY is not a context.

• λX.λy.XXy is a context.

An equivalence relation is a transitive symmetric reflexive relation. Call an equivalence relation X on programs contextual when

∀s, t. s X t ⇒∀C. Cs X Ct ∀s, t. (s X t ∧s↘) ⇒t↘

Here C ranges over contexts and s and t range over programs. Write =ctx for the greatest contextual equivalence, which (abusing notation) we call contextual equivalence. We discuss this definition below.

Call an equivalence relation P on programs applicative when

∀s, t. s P t ⇒∀u. su P tu ∀s, t. s P t ∧s↘⇒t↘.

Here s, t, and u range over programs. Write =ap for the greatest applicative equivalence and abuse notation calling it applicative equivalence.

The main result of this section is

Theorem 51

=ctx and =ap are equal.

. . . but we need technical machinery to prove it.

Lemma 52

Write s ↔t for the least equivalence relation containing ⇝. Then

↔⊆=apand ↔⊆=ctx .

Also, ⊤s1. . . sn =ap ⊤t1. . . tn always, for n > 0.

Proof

Suppose s ↔t. By confluence Theorem 25

su↘ if and only if tu↘,

and similarly for Cs and Ct.

For the second part we examine the reduction rules and observe that ⊤s1. . . sn↘ is impossible unless n = 0. 2

When we define =ctx we consider C applied to s. From the first part of the technical lemma above and from the definition of context, this is clearly equivalent to a definition in more traditional form D[dl↦→s].

In the proofs below we tend to use traditional notation of D[dl↦→s] rather than (λdl.D)s.

We can also characterise =ctx as the greatest congruence (Definition 4; extended with the rule for И from Subsection 6.1) such that

∀s, t. (s X t ∧s↘) ⇒t↘.

We do not explore this further because the definition of =ctx which we use is more convenient for the proof-method to follow.

8.2 Proof that =ctx equals =ap

Suppose s and t are programs and s =ctx t. We want to show that s =ap t. By the coinductive principle by which =ap was defined, it suffices to show that if s =ctx t then:

• If s↘ then t↘.

• For any program u it is the case that su =ctx tu.

The first part follows directly from our assumption that s =ctx t.

Also for any program u, the term (dlu) is a context (where dl is a variable which we choose stronger than any variable in s or u). By assumption (dlu)[dl↦→s] =ctx (dlu)[dl↦→t]. To take the next step and reduce these to su and tu we need Lemmas 53 and 54.

Lemma 53

If l > level(s) then dl#fv(s).

Proof

By an easy induction on the definition of level(s) (Definition 2). 2

Lemma 54

Suppose s and u are any terms (we only care about the case that s and u are programs). Suppose further that dl is a variable such that l > level(s, u). Then

(dlu)[dl↦→s] ⇝∗su.
Proof

The reduction path is as follows:

(dlu)[dl↦→s](σp)⇝(dl[dl↦→s])(u[dl↦→s])(σa)⇝s(u[dl↦→s])(σfv)⇝su.

For the reduction with (σfv) we use Lemma 53. 2

By Lemma 54 (dlu)[dl↦→s] ⇝∗su and (dlu)[dl↦→t] ⇝∗tu. By Lemma 52 we have that su =ctx tu, and we are done.

Now suppose that s =ap t. We want to prove that s =ctx t. By the coinductive principle by which =ctx was defined, it suffices to show that if s =ap t then:

• If s↘ then t↘.

• For any context D it is the case that Ds =ap Dt.

We work by induction on the tuple (ocD, nfD, siD) where

• ocD is the number of occurrences of dl in the normal form of D and ω otherwise (=the first uncountable ordinal; if D has no normal form there will be nothing to prove),

• nfD is the least number of ⇝-reductions to reduce D to its normal form and ω otherwise, and

• siD is the size of D,

proving that

{(Иas.D[dl↦→s],Иas.D[dl↦→t]) | D, dl, as}

is a contextual relation, where as varies over possibly empty lists of variables no stronger than dl. We work by cases on the form of D.

In the the cases below we may implicitly use the first part of Lemma 52 along with confluence and the inductive hypothesis, to suppose that D is in ⇝-normal form. We also silently strip leading Иs, writing for example dl for Иa.dl.

• Suppose D = dl. Then dl[dl↦→s] ↔s =ap t ↔dl[dl↦→t]. We use the first part of Lemma 52 and the fact that =ap is an equivalence.

• Suppose D = (λnj.D′). Then D[dl↦→s] and D[dl↦→t] cannot evaluate to ⊤ so there is nothing to prove.

• Suppose D = D′D′′, and suppose dl occurs in D′ and D′′. We reason as follows:

(D′D′′)[dl↦→s] ↔(D′[dl↦→s])(D′′[dl↦→s]) =ap (D′[dl↦→t])(D′′[dl↦→s]) (1)↔(λxm.xmD′′)[dl↦→s](D′[dl↦→t]) (2)=ap (λxm.xmD′′)[dl↦→t](D′[dl↦→t]) (3)↔(D′D′′)[dl↦→t] (4)

Here we choose xm fresh and stronger than dl. We justify the steps of this reasoning, which we numbered on the right above:

(1) D′ has fewer instances of dl than D = D′D′′ since we assumed that dl also appears in D′′. So we use the inductive hypothesis for D′ to deduce that D′[dl↦→s] =ap D′[dl↦→t]. By assumption =ap is closed under application on the right, and so also (D′[dl↦→s])(D′′[dl↦→s]) =ap (D′[dl↦→t])(D′′[dl↦→s]).

(2) (λxm.(xmD′′))[dl↦→s](D′[dl↦→t]) ⇝D′D′′ is easy to verify.

(3) By the inductive hypothesis and the fact that =ap is closed under application on the right.

(4) Reversing the reasoning above.

• Suppose D = D′D′′, and suppose dl occurs in D′ but not D′′. We reason as follows:

(D′D′′)[dl↦→s] ↔(D′[dl↦→s])D′′=ap (D′[dl↦→t])D′′↔(D′D′′)[dl↦→t]

• Suppose D = D′D′′, and suppose dl does not occur in D′ and may or may not occur in D′′. We have supposed that D′ is a normal form with no

unabstracted variables. If D′ is a λ-abstraction then D′D′′ reduces with (β) so we use the inductive hypothesis. Otherwise, D′D′′ cannot ever evaluate and there is nothing to prove.

• Suppose D = D′[nj↦→D′′]. If this is not a normal form, we reduce and use the inductive hypothesis.

If this is a normal form we reason by cases. If dl occurs in D′ and D′′, or in D′ and not in D′′, we can proceed as we did for applications above. Suppose dl does not occur in D′ and does occur in D′′. We have supposed this is a normal form, so we work by cases: · D′ = λe.E for some e and E such that e is not weaker than nj (so that (σλ) does not apply). Then D′[nj↦→D′′][dl↦→u] cannot possibly evaluate to ⊤ for any u, so there is nothing to prove. · D′ =Иe.E. We are free to α-convert e and therefore we can use (Иσ) to reduce D′[nj↦→D′′], contradicting our assumption that D′[nj↦→D′′] is a normal form. · D′ = nj. nj[nj↦→D′′] is not a normal form, because of (σa). · D′ = ck for ck not stronger than nj. ck[nj↦→D′′] is not a normal form, because of (σfv). · D′ = ck for ck stronger than nj and (by assumption) not equal to dl. It is not possible for ck[nj↦→D′′][dl↦→u] to evaluate to ⊤ for any u, so there is nothing to prove. · The case of D′ = D′ 1[n′ j′↦→D′ 2] is similar.

That concludes the proof of Theorem 51.

9 Related work, conclusions, and future work

In a previous conference paper we presented the NEW calculus of contexts

[9]. The LCC of this journal paper updates and improves that that work. The LCC is simpler than the NEWcc. Compare the side-condition of (σa) (there is none) with that of (σa) from [9]. 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 [9]. 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, and the condition on rule (σp).

But there is a price: the LCC has fewer reductions. Notably (σλ′) will not reduce (λai.s)[ck↦→u] where k < i; a rule (σλ′) in [9] does. However that stronger version seems to be a major source of complexity. Do we miss the extra reductions? An insight that was necessary to make this paper is that certain reductions which we thought were important, could be dropped. Still, it is clear that we are approximating something larger. Other papers on nominal techniques have useful elements which we can import, now that we have a solid basis to work from.

In this paper we cannot α-convert x in λx.X. Nominal terms can: swappings are in the syntax (here swappings are purely a meta-level) and also freshness contexts [36]. A problem is that we do not yet understand the theory of swappings for strong variables; the underlying Fraenkel-Mostowski sets model [13] 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 [10] has a more powerful notion of freshness which can prove the equivalent of x#fv(λx.X). Note that hierarchical nominal rewriting does 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

[25] or the style of a sequent calculus for Nominal Logic by Cheney [5].

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

Desirable and nontrivial meta-properties of the λ-calculus survive in the LCC. The LCC is confluent. It supports a type system in Hindley-Milner style making it possible, in principle at least, to envisage an extension of ML or Haskell with meta-variables based on the LCC’s notion of strong and weak variables. Also, contextual equivalence coincides with applicative equivalence — a full treatment will be in a longer paper. This is a surprising result considering that substitution in the LCC can capture.

More related work (not using nominal techniques). The calculi of contexts λm and λM [30] also have a hierarchy of variables. They use carefully-crafted scoping conventions to manage problems with α-conversion. Other work [28,16,29] 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 И appears in one other (unpublished) work we know of [32], where they are called q and ν. In this vein there is [17], which manages scope explicitly in a completely different way, just for the fun. Finally, the reduction rules of И look remarkably similar to π-calculus restriction [21], and it is probably quite accurate to think of И as a ‘restriction in the λ-calculus’.

Hamana takes a semantic approach to meta-variables [15]. We have not developed the semantic theory of the LCC. We should do this in future work, and when we do we would expect to arrive at something similar to Hamana’s construction. However we do not expect the semantics to be identical; ours it will be phrased in terms of sets and permutation actions (in keeping with the first author’s previous work [13]). These have slightly stronger, and in our opinion more desirable, properties than the categories of presheaves which Hamana uses.

Ours is a calculus with explicit substitutions. See [20] 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 Bloo’s ‘garbage collection’ [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 [9] complexity spilled over into other rules and into a logic for freshness). И 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. We discussed above how to add off-the-shelf elements of nominal techniques, if we want to give ourselves more reductions.

Another possibility is 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 [38], along with suitable equalities and/or derivation rules. Because the LCC admits a Hindley-Milner style type system it certainly admits a simple type system. There should be no problem with writing down a ‘context higher-order logic’. This takes the LCC in the direction of calculi of contexts for incomplete proofs [18,14], and also in the direction of giving semantics to existential variables in logic-programming (unpublished work by Lipton and Mariño). The non-trivial work (in no particular order) is to investigate cut-elimination, develop a suitable theory of models, and to check whether and how usefully the LCC can be used as-is to model incomplete proofs of some theorem-proving system.

One important element is the denotation semantics of the hierarchy of variables — we do not yet have one; this is current work.

Certain specific ideas appear elsewhere in the literature which the LCC cannot express, but they might be accommodated with a relatively straightforward extension.

As discussed, the LCC can express [ai↦→t] using the term λbj.(bj[ai↦→t]) where i < j and level(t) ≤j. However we cannot abstract over ai. For example consider λP.λX.λx.(X[x↦→P]) and the reduction

(λP.λX.λx.X[x↦→P])2xy ⇝∗X[x↦→P][P↦→2][X↦→x][x↦→y] ⇝X[x↦→2][X↦→x][x↦→y] ⇝∗x[x↦→2][x↦→y] ⇝∗2.

This is not the intended operational behaviour (if we intended to abstract over the name of x and replace it by y). Variables can be substituted for so it should not possible to pass a variable name as a first-class value. An extension of the LCC based on atom from [11] may be possible and useful.

The LCC cannot express ‘substitute all variables of level 1 for t in s’, which we might write as s[⋆↦→t]. This idea appears in work by Dami [8] on dynamic binding. We do believe that the LCC could have something to contribute to dynamic binding and linking, since they seem to have to do with capturing substitution, but that is future work.

Languages for staged computation, for example MetaML [22,26], Template Haskell [31], and Converge [35], have a hierarchy (of stages) reminiscent of our hierarchy of levels. They offer a program enough control of its own execution that it can suspend its own execution, compose suspended programs into larger (suspended) programs, pass suspended programs as arguments to functions, and evaluate them. This raises issues similar to those surrounding contexts. The LCC cannot model staged computation because it is a pure rewrite system with no control of evaluation order. Even if we choose some evaluation order on the LCC to make it into a programming language, the deeper problem is that the LCC has no first-class construct to promote variables between levels. Adding this extension is interesting future work.

In conclusion: the LCC of this paper is simple, clear, and it has good properties. It seems to hit a technical sweet spot. 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] Luis Damas, Type assignment in programming languages, Ph.D. thesis, University of Edinburgh, 1985.

[7] Luis Damas and Robin Milner, Principal type-schemes for functional programs, POPL ’82: Proc. of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, 1982, pp. 207–212.

[8] Laurent Dami, A lambda-calculus for dynamic binding, Theoretical Computer Science 192(2) (1998), 201–231.

[9] 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.

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

[11] Murdoch J. Gabbay and Michael J. Gabbay, a-logic, We Will Show Them: Essays in Honour of Dov Gabbay, vol. 1, College Publications, 2005.

[12] 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.

[13] 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.

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

[15] M. Hamana, Free sigma-monoids: A higher-order syntax with metavariables, The Second Asian Symposium on Programming Languages and Systems (APLAS 2004), LNCS, vol. 3202, 2004, pp. 348–363.

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

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

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

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

[20] 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.

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

[22] Eugenio Moggi, Walid Taha, Zine-El-Abidine Benaissa, and Tim Sheard, An idealized metaml: Simpler, and more expressive, ESOP ’99: Proc. of the 8th European Symposium on Programming Languages and Systems, LNCS, vol. 1576, 1999, pp. 193–207.

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

[24] 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.

[25] 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.

[26] A. M. Pitts and T. Sheard, On the denotational semantics of staged execution of open code, Submitted, 2004.

[27] 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.

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

[29] 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.

[30] 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.

[31] Tim Sheard and Simon Peyton Jones, Template metaprogramming for Haskell, ACM SIGPLAN Haskell Workshop 02 (Manuel M. T. Chakravarty, ed.), ACM Press, 2002, pp. 1–16.

[32] 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.

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

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

[35] Laurence Tratt, Compile-time meta-programming in converge, Tech. Report TR-04-11, Department of Computer Science, King’s College London, 2002.

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

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

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

[39] Robert Virding, Claes Wikström, and Mike Williams, Concurrent programming in ERLANG, 2 ed., Prentice Hall, 1996.