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

A NEW Calculus of Contexts

Murdoch J. Gabbay Dept. of Computer Science King’s College London Strand, London WC2R 2LS, UK jamie@dcs.kcl.ac.uk

ABSTRACT

We study contexts (terms with holes) by proposing a ‘λ-calculus with holes’. It is very expressive and can encode programming constructs apparently unrelated to contexts, including objects and algorithms in partial evaluation. We give proofs of confluence, preservation of strong normalisation, principal typing for an ML-style Hindley-Milner type system, and an applicative characterisation of contextual equivalence. We explore the limitations of the calculus including further applications, and discuss how they might be tackled.1

Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: lambda calculus and related systems

General Terms: Theory.

Keywords: Calculi of contexts, Functional programming, Binders, Lambda-Calculi, Nominal Techniques.

1. INTRODUCTION

This is a paper about contexts. We shall study them by proposing a “λ-calculus for contexts” which we call the N calculus of contexts (N is pronounced ‘new’). In this calculus, contexts are terms (first-class values) and can be passed as arguments to functions, applied to other terms, and so on.

We prove • confluence (using results from [36]), • preservation of strong normalisation with respect to the untyped λ-calculus, • give a Hindley-Milner style type system [9] with subject reduction, and • an applicative characterisation of contextual equivalence (drawing on techniques in [10] and [29]). This small library of results is chosen to make the NEW context calculus a respectable implementation environment because respectively • the calculus has ‘semantic content’ (normal forms are unique if they exist), • is ‘conservative’ over a familar programming language, • can be implemented as an extension of a (toy core of) ML without destroying the type-system, and • programs can be optimised up to preserving extensional behaviour.

What are the technical design issues?

A context is a term with a ‘hole’. The canonical example in the untyped λ-calculus is C [-] = λx.-. (We use ‘=’ to denote syntactic α-equality.)

A term t may be placed in the hole -, e.g. C [t] = λx.t and if t = x then C [x] = λx.x. This cannot be modelled inside the calculus by λy.λx.y because β-reduction avoids capture. Our idea is to treat the hole as a variable X which is stronger than x and y and for which substitution does not avoid capture of weaker variables. For example, (λX.λx.X)x ⇝λx.x.

But now α-equivalence is a problem; if λx.X = λy.X

then (λX.λx.X)x ⇝λy.x, giving non-confluent reductions. Dropping α-equivalence entirely is too drastic because some capture-avoidance, as in (λy.λx.y)x, should be legitimate.

Existing calculi of contexts include λm and λℳ [31] by Sato et al.2 which seems closest to ours because they have a hierarchy of variables (see below). Some other work [22, 15, 30] use a type system which may prove related to our freshness contexts (see below) though the connections are unclear. Finally we mention λc of Bognar’s thesis, which also contains [7, Section 2] an essay on the issues involved in designing context calculi, as well as an extensive literature survey.

How does our calculus relate to the existing literature?

The central point of all calculi of contexts we know of, including our own, is the interaction of α-equivalence with holes, and the resulting problems with scope and abstraction. Solutions include clever control of substitution and evaluation order, and types to prevent ‘bad’ α-conversions.

Technically, this paper contains yet another solution and we are not primarily interested in how that solution works though of course we do describe it in detail. Broadly speaking, its novelty is to imports ideas from previous work by the author and others, known under the umbrella term of ‘Nominal techniques’ (notably with Urban and Pitts on Nominal Unification [35], and with Fern´andez on Nominal Rewriting [21, 11]). These ideas were designed to manage α-equivalence; crudely put, we simply applied them to a new problem.

Why do this and why make another context calculus?

First, it has been our personal belief for some time that contexts are significantly underrated.

Our inspiration came from specific technical issues which arise with existential variables in the theorem-proving environment Isabelle [27], and from technical work by Pitts [29] on (what we can slightly inaccurately call) applicative characterisations of contextual equivalence. The problem with existential variables is that the ∃ right sequent introduction rule Γ ⊢P (t) Γ ⊢∃y. P (y) requires us to pick a specific fresh t to make the rest of the proof above Γ ⊢P (t) work. This is silly (we want to build t interactively as we construct the rest of the proof). Therefore the designers of Isabelle introduced existential variables ?t. These resemble ‘holes’ in λ-calculus contexts, but this is somehow disguised because they are Skolemised over the free variables they may contain.

With Pitts’s work, we would claim that contexts — and not terms — are the true object of study. They occur in the definition of contextual equivalence which Pitts uses (originally due to Lockwood Morris), and again with Pitts’s notion of ‘continuation’, which is actually a structured form of a Felleisen-style evaluation context [29, Page 15]. It always seemed to us naughty to have so many contexts around without saying what they are in some more abstract sense.

So our answer is ‘here is a calculus of contexts’. Contexts and ‘ordinary terms’ are on an equal footing as terms in this calculus; indeed so are substitutions and many other things. Results about contexts and substitutions become results about suitable relations (such as β-equivalence or contextual equivalence) between the contexts represented as terms in the calculus.

This is not a denotational answer in quite the same sense as some other work (compare with Hamana [14] and possibly [28]) but for many applications a calculus is just what we want: for example Isabelle theories are encoded in Isabelle/Pure, which is a typed λ-calculus with a simple theory of equality.

But there is more. The NEW context calculus, with its elements of Nominal techniques and hierarchy of variables, gives us fine-grained control of substitution. It turns out that we can apply this to implement constructs which a priori have nothing to do with contexts. We shall explore notions of global state (for general references [2]), objects with forms of in-place update [1], and interesting interactions with partial evaluation [8]; in the conclusions we look at other potential applications such as staged programming (MetaML [26]) and logic and unification.

We are not aware of claims for such implementations made of other context calculi. Perhaps they could implement some or all of our examples (or not; our hierarchy of variables is shared only with [31] and makes a great contribution to expressivity). A different paper might try to make a fair comparison between the different calculi (probably by translating them into ours of course!) and in so doing gain some measure of their relative expressivities. However, we feel it is our small library of meta-properties listed above which distinguishes our work from other context calculi. We do not know, for example, of any other applicative characterisation of contextual equivalence.

Therefore, our motivation writing this paper is not really to produce a calculus of contexts even though that was our original motivation and this may be sufficient motivation for some readers. We aim further for an implementation environment with good meta-properties and fine-grained control of substitution (thanks to the use of Nominal techniques applied to other ideas already in the literature). We hope that this calculus or something resembling it will provide a convenient environment in which to implement and prove things about other systems which benefit from fine control of substitution including the non-capture-avoiding kind.

In summary: all computation can be coded in the untyped λ-calculus. Some questions then are: (1) can we optimise programs, (2) can we statically analyse them, and (3) can we prove properties of an implementation? If not, what extended calculus allows us to do so. This paper presents an extension of the untyped λ-calculus with constructs to manage capture in substitution, and our examples and meta-properties are chosen precisely to at least suggest that we should be able to answer (1) to (3) of some useful systems of independent interest.

Besides Nominal Techniques mentioned above, our calculus comes out of a very long tradition of calculi for studying programming. Our calculus has explicit substitutions, see [19] for a survey; our particular treatment of substitution is deliberately simple-minded but still subtle because of interactions with the rest of the language. We give a translation of possibly open terms of the untyped λ-calculus which preserves strong normalisation.

We do not directly import ideas from other calculi of contexts because our management of α-equivalence is based on Nominal techniques with are novel to this field; we do share the hierarchy of variables with one other work [31] and the separation of scope and binding in a λ-calculus appears in one other (unpublished) work we know of [33]. For our meta-properties, we have modelled our proofs on work which we cited above.

2. BASIC SYNTAX AND BASIC EXAMPLE REDUCTIONS

The syntax of the context calculus is easy to construct. We formally define reductions in the next section.

We suppose a countably infinite set of disjoint infinite sets of variables 𝔸1, 𝔸2, . . . , where we write ai, bi, ci, ni, . . . ∈ 𝔸i for i ⩾1. We say that ai has level i. The syntax is then given by:

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

We call s[ai↦→t] an explicit substitution. We call λai.t an abstraction. We equate terms up to α-equivalence on ai in Nai.t (but not in λai.t or t[ai↦→t′]). We say ‘N is a binder’ (and λ and explicit substitution are not).

For the moment we ignore N (and so α-equivalence) and concentrate on examples of the interaction of the hierarchy of variables with explicit substitutions.

We call a variable bj stronger than another ai when j >i, that is, when it has a strictly higher level. We say they have the same strength when they have the same level. For example, b3 is stronger than a1. There is no particular connection between variables of different levels with the same name, for example a1 and a2.

We now consider some example reductions. We write x, y, z for variables of level 1, and X, Y, Z for variables of level 2.

• (Ordinary) β-reduction.

(λx.x)y ⇝x[x↦→y] ⇝y.

The explicit substitution implements β-reduction in a standard way. Here and later we colour subterms under an explicit substitution, to help visualise the brackets.

• Context substitution. In an explicit substitution s[ai↦→t] consider the case s = λx.X (a λ-abstraction of a level 2 variable by a level 1 variable), a = X, and t = x. The intended operational behaviour is

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

The explicit substitution moves under the λx and acts on the X, without capture-avoidance. This kind of substitution (implemented here as a rewrite) is called context substitution or grafting. This example demonstrates that we cannot just equate terms up to α-equivalence, at least not blindly; if λx.X and λy.X were equal terms, context substitution would make no sense.

• Explicit substitutions on variables. Canonical reductions (and non-reductions) of terms of the form a[b↦→t] where a and b are variables and t is any term are:

x[X↦→t]⇝x x[x′↦→t]⇝x x[x↦→t]⇝t X [x↦→t] |⇝

A substitution of a strong variable on a weak variable, or two different variables of the same strength, ‘evaporates’. A substitution of a variable by itself is a substitution. A substitution of a weak variable on a stronger variable does not in general reduce; we say [x↦→t] is suspended on X. (The precise rules (σa) and (σ#) are introduced below, but first we must introduce binding, and we give some more examples before that.) A canonical reduction illustrating the use of suspensions, is as follows:

X [x↦→t][X↦→x] ⇝X [X↦→x][x↦→t[X↦→x]]⇝x[x↦→t[X↦→x]] ⇝t[X↦→x].

So we can think of bj [ai↦→t] for i < j as a strong hole bj with a substitution on a weaker ai waiting for it to be filled.

• Substitutions and λ-abstraction. A λ-abstracted atom can never get substituted for, not even by a stronger substitution. For example (λx.x)[x↦→X] ⇝λx.x.

• Substitutions as terms. Substitution [ai↦→t] is not a term and so cannot be made an argument of a function. Using suspensions we can express this: for example λX.X [x↦→y] encodes [x↦→y] as a term. Reduction is not possible since X is stronger than x. Contrast this with λX.(X [X↦→y]), which reduces in one step to λX.y. Define true ≡λx, y.x, false ≡λx, y.y, and Id ≡λx.x. Here is a program which takes a substitution, a truth value, and an argument, and applies the substitution or not according to the truth value: f ≡λx, y, z.(yxId)z. Here is an example of reduction using f:

f (λX.X [x↦→y]) true x ⇝∗yf (λX.X [x↦→y]) false x ⇝∗x.

To encode substitutions for stronger variables [ai↦→s] (we call these stronger substitutions), the general scheme is λai+1.(ai+1 [ai↦→s]). This is the first real use of level three variables, which are useful to encode the ‘context substitution’ [X↦→s] as a term.

We hope this clarifies everything except for binding. We shall now give a formal definition of the syntax and operational semantics of the context calculus, all in a block, and then we return to the examples.

3. FORMAL DEFINITION OF THE NEW CONTEXT CALCULUS

We inherit the definitions, notation, and terminology of the beginning of the last section. Briefly, assume an infinity of disjoint sets of variables ai, bi, ci, ni, . . . ∈𝔸i for i ⩾1 and say that ai has level i. The syntax is:

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

N is the only binder and we work up to α-equivalence between variables of the same level bound by N. So for instance Na1.a1 =Nb1.b1 but Na1.a1 ≠Na2.a2. It may also be convenient to allow constants, e.g. for arithmetic or truth-values. They behave much like variables which we do not abstract or substitute for and we tend to ignore them. Note that [ai↦→t] is not a term.

Reduction rules are given on terms as follows:

(β)(λai.s)u ⇝s[ai↦→u](σa) ai[ai↦→u] ⇝u ∀j, cj. j<i ∧cj#ai⇒cj#u(σ#) s[ai↦→u] ⇝s ai#s(σp)(ait1 . . . tn)[bj↦→u] ⇝(ai [bj↦→u]). . . (tn[bj↦→u])(σσ) s[ai↦→u][bj↦→v] ⇝s[bj↦→v][ai↦→u[bj↦→v]] j>i(σλ)(λai.s)[ck↦→u] ⇝λai.(s[ck↦→u]) ai#u, ck k⩽i(σλ′)(λai.s)[bj↦→u] ⇝λai.(s[bj↦→u]) j >i(σtr) s[ai↦→ai] ⇝s(Np)(Nnj.s)t ⇝Nnj.(st) nj∉t(Nλ) λai.Nnj.s ⇝Nnj.λai.s nj ≠ai(Nσ)(Nnj.s)[ai↦→u] ⇝Nnj.(s[ai↦→u]) nj∉u nj ≠ai(N∉)Nnj.s ⇝s nj∉s

nj ≠ai means ‘nj and ai are distinct symbols’. nj ∉t means ‘nj does not occur in t’. We use these conventions silently henceforth. The intuition of a#t is ‘a cannot occur free in t’; defining and explaining its formal meaning is for the rest of this subsection. j in ∀j varies over all levels and cj in ∀cj varies over all variables of that level, so the side-condition on (σa) is ‘for all variables cj weaker than i, if cj#ai then cj#u (see the end of §4.1 for further discussion). In (σp) and henceforth we write ((((mu)p)p)e)t as muppet, associating application to the left (as is standard).

Many of these rules are familiar from λ-calculi of explicit substitutions (see [19] for examples). (σ#) is reminiscent of Bloo’s ‘garbage collection’ [6] and we refer the reader there for a further discussion. The rules involving N are scope extrusion rules, e.g. as in the π-calculus [24].

Call a pair of a variable and a term ai#t a freshness assertion, we let ϕ vary over them. If t = bj is a variable and i <j it a primitive freshness assertion. Call a possibly infinite set Γ of primitive freshness assertions a freshness context.

Define a notion of entailment between freshness contexts and freshness assertions by:

j >i bj#aiai ≠biai#biai#λai.ubj#u bj#λai.uai#s ai#t ai#stai#u ai#s[ai↦→u]ai#s bj#s bj#s[ai↦→u]bj#s bj#u bj#s[ai↦→u]ai#s ai#Nbj.s

We say a#s is entailed by Γ and write Γ ⊢a#s, when a#s can be derived from Γ using these rules.

Read bottom-up these are rewrite rules on (sets of) freshness assertions. They reduce assertions to a normal form Sol which is a set of freshness contexts. For example a1#a1a1 reduces to a1#a1, and a1#b1 reduces to the empty set. Γ ⊢a#s holds when Sol ⊆ Γ.

Here are some examples/comments.

• Γ ⊢bj#ai always if j > i, or if j = i but bj ≠ai. This expresses the intuition that a stronger hole can never ‘occur in’ a weaker one, and that two different holes of the same strength are different.

• Γ ⊢ai#λai.s. We say that λ abstracts and this expresses a natural intuition.

• Γ ⊢ai#s[ai↦→t] if Γ ⊢ai#t. This expresses an intuition that substitution abstracts away all ai in s.

• Γ ⊢a1#b2c2 is derivable from Γ if {a1#b2, a1#c2} ⊆ Γ. This expresses the intuition that ‘if a1 is not free in b2 and a1 is not free in c2, then a1 is not free in b2 applied to c2’. Here b2 and c2 are stronger variables which may for example ‘become’ a1, in the sense that b2c2 may occur in a subterm of a larger term containing substitutions [b2↦→a1].

A freshness context Γ induces a reduction relation Γ ⊢s ⇝ t, we may just write s ⇝t, on the syntax of the calculus. It is given by reading the conditions ai#bj and nj#t as Γ ⊢ai#bj and Γ ⊢nj#t.

Lemma 3.1

(Subject reduction for #). If Γ ⊢ ai#s and Γ ⊢s ⇝t then Γ ⊢ai#t.

Proof

By case-analysis on the rewrites defining s ⇝t and on the position in which the rewrite occurs in s.End of proof

# controls abstraction; what a variable can be replaced by, and what can be done under a λ and an explicit substitution. This is distinct from from scope (and literal binding in the syntax), which remains relatively simple and is controlled by N (N is the only binder, in the traditional sense of renaming variables). We discuss this further in the rest of the paper.

We note that (σ#) resembles Bloo and Rose’s ‘garbage collection rule’ [6]. The deduction rules for # and explicit substitutions implement a notion of unabstracted variable which they reject [6, Remark 2.3] for reasons we seem to avoid because of the separation of binding and abstraction.

3.1 Freshness #, α-equivalence, and N

Why is all the apparatus of # necessary; why not use ∉? The following two rewrites would be valid:

(λx.y)[y↦→X][X↦→x] (σλ)⇝(λx.y[y↦→X])[X↦→x](σλ′)⇝ λx.(y[y↦→X][X↦→x])(σa) ⇝∗ λx.x(λx.y)[y↦→X][X↦→x] (σσ)⇝(λx.y)[X↦→x][y↦→X [X↦→x]](σa)⇝(λx.y)[X↦→x][y↦→x](σλ′)⇝ λx.(y[X↦→x])[y↦→x] |⇝

These rewrites are not confluent (and we want confluence). The problem rewrite is the first one, where the strong variable X (which contains only X in its raw syntax, and in particular does not contain x) comes under an abstraction by a weak variable x and is then substituted for by non-capture-avoiding context substitution.

We use freshness assumptions to manage abstraction. Fix some freshness context Γ and read the side-conditions ϕ ∈ {nj#u, nj#t, ai#bj, . . .}, in the definition of reduction from the previous subsection, as meaning Γ ⊢ϕ. Each freshness context induces a different reduction relation.

By way of example, we re-consider the example reductions above in the universal freshness context Θ = {ai#bj | i < j}, and the empty freshness context Φ = ∅.

In the universal freshness context Θ the term above rewrites as follows:

Θ ⊢(λx.y)[y↦→X][X↦→x] (σλ) x#X⇝(λx.y[y↦→X])[X↦→x](σλ′)⇝λx.(y[y↦→X][X↦→x])(σa)⇝λx.(X [X↦→x]) |⇝Θ ⊢(λx.y)[y↦→X][X↦→x] (σσ)⇝(λx.y)[X↦→x][y↦→X [X↦→x]](σλ′)⇝(λx.(y[X↦→x]))[y↦→X [X↦→x]](σ#) X#y⇝(λx.y)[y↦→X[X↦→x]](σλ) x#X[X↦→x]⇝λx.(y[y↦→X [X↦→x]])(σa)⇝λx.X [X↦→x]] |⇝

Here X [X↦→x] cannot reduce (by (σa)) because Θ ⊢x#X and Θ ⊬x#x.

In the empty freshness context Φ,

Φ ⊬(λx.y)[y↦→X][X↦→x] (σλ)⇝(λx.y[y↦→X])[X↦→x]Φ ⊢(λx.y)[y↦→X][X↦→x] (σσ)⇝(λx.y)[X↦→x][y↦→X [X↦→x]](σλ′)⇝(λx.(y[X↦→x]))[y↦→X [X↦→x]](σ#) X#y⇝(λx.y)[y↦→X[X↦→x]](σa)⇝(λx.y)[y↦→x] |⇝

The first reduction cannot take place because Φ ⊬y#X.

(We note in passing that we can emulate a constant with a variable a such that b#a always.)

Is there a canonical freshness context between the extremes of Θ and Φ? We need some notation: given a set of variables S write max(S) for the level of a strongest variable, if such a variable exists, and min(S) for the level of the weakest. For example, maxΦ = 0 and max{a2, b3} = 3. maxΘ is not well-defined. Given any set of variables I write bj#I for the set {bj#ai | ai ∈I}. Write Γ ⊢bj#I for the assertion ∀ai ∈S. Γ ⊢bj#ai.

A freshness context Γ has sufficient freshnesses when for all finite sets of variables S and all i, there exists bi ∉S with Γ ⊢bi#S, and for all i ⩽ min(S), there exists ai ∉S with Γ ⊬ai#S.

So Γ has two kinds of freshness: internally, for any finite set we can find a variable which Γ promises is fresh for them, but also externally we can find a variable fresh in the sense that Γ knows nothing about its relation to S (provided the variable is no stronger than any element of S, in which case its freshness may be deducible from the derivation rules, e.g. a2#a1).

It is not hard to inductively construct a Γ with sufficient freshnesses inductively:

• Let Γ0 = {} and U0 = {}.

• Given Γl and Ul, enumerate all subsets S1, . . . , Sn of Ul. For each Sj and i ⩽ max(Ul) + 1 choose distinct fresh bj i. For each Sj and i ⩽ min(S) choose distinct fresh aj i. Let Γi+1 = Γi ∪{bj i#Sj | i, j}and let Ul+1 = Ul ∪{aj i, bj i | i, j}.

Iterate and let Γ = ⋃i Γi (actually, we must take the normal form with respect to the deduction rules for #).

Lemma 3.2

If Γ has sufficient freshnesses then for any term t and any i there exists ai such that Γ ⊢ai#t. Similarly for a finite set of terms. We may say ai is sufficiently fresh, in the case that the other parameters are fixed or understood.

Proof

Let S be all variables mentioned in t and choose ai such that Γ ⊢ai#S. It is not hard to prove by induction on t that Γ ⊢ai#t is derivable.End of proof

For the rest of this paper, we silently fix a context Γ with sufficient freshnesses. Thus when we write ‘a#s’ we mean ‘Γ ⊢a#s’. This is just the usual assumption that ‘we can always find a fresh variable’. The hierarchy of strengths of variables created problems which we solved with an explicit freshness context, so we make explicit assumptions about it; but the associated technical details work as we would expect so we tend to retain informal practice and terminology.

3.2 Intuitive ‘facts’ and silly reductions

We might expect that if x∉s then x#s. This is not true; x#X is not true in general, only for those x and X such that x#X is in the context.

Conversely, it is not true that if x#s then x∉s, a counterexample is X [x↦→y]. We leave it to the reader to check the derivation of x#(X [x↦→y]) using the rules defining #.

Why do rules (N⋆) for ⋆∈{p, λ, σ, ∉} all use inequality ∉ and ≠, whereas rules (σ⋆) for ⋆∈{a, #, λ} use #? Intuitively, N regulates α-equivalence, which has to do with occurrences and scope, and # regulates abstraction, which has to do with what can be substituted or moved where! For illustration we propose silly (=non-confluent) reductions based on (false) rules consistently using only # and only ∉ respectively:

(Nx.X [x↦→y])[X↦→x] (Nσ) x#X[x↦→y]⇝Nx.(X [x↦→y][X↦→x]) ⇝∗Nx.x

This is silly, because we can α-rename the N-bound x to some x′ and (as we can easily verify) reduce to Nx′.x.

X [x↦→0][X↦→x] (σ#) x∉X⇝ X [X↦→x] ⇝X.

This is silly, because we can also reduce with (σσ) to obtain 0.

A rule s(Na.t) ⇝Na.(st) (if a ∉s) would be silly:

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

For this reason, N remains trapped in any position where it might be copied.

4. PROGRAMMING IN THE CALCULUS

Having defined and motivated the formal design of the calculus, we explore its expressivity, at first with respect to existing calculi in the literature but also with respect to some interesting applications.

4.1 Some simple reductions

We start by seeing how some familiar reductions work: Consider variables x1, y1, X2 (with levels 1, 1, and 2 respectively; we may state levels as subscripts for the first use of a variable, then drop them). We might expect (λx.s)x to reduce to s. This is so:

(λx.s)x (β)⇝s[x↦→x] (σtr)⇝s.

Note however that λ does not bind; does (Nλx.s)x reduce to s? Here and henceforth we write Nλx.s for Nx.λx.s. The answer is ‘yes’, but for more complex reasons. We consider the first part of its reduction:

(Nλx.s)x (Np) y#x⇝Ny.((λy.s[y/x])x) (β)⇝Ny.(s[y/x][y↦→x])

Write [t/x] for term substitution avoiding capture by N-bound variables. We choose y such that y#x so we can extend the scope of N; here we assume the context has sufficient freshnesses.

Note that s[y/x][y↦→x] does not in general reduce to s[x/y]. A counterexample is s = X2 [y↦→x] (X [y/x] = X). y is weaker than X, so reductions stop. However:

Lemma 4.1

If the level of a is no less than that of the other variables mentioned in s then s[a↦→t] ⇝∗s[t/a] and as a corollary, (Nλx.s)x ⇝∗s.

Proof

By induction on the reduction rules.End of proof

We would expect (λx.s)t and (Nλx.s)t to reduce to s if x does not occur in s. In fact, the first statement is not true!

A counterexample is (λx.X)y (β)⇝X [x↦→y]. This does not reduce further unless x#X. Of course, this is the point of the context calculus; X is stronger than x and a substitution may arrive from elsewhere in the term to instantiate it to another term, such as x, unless the context prohibits this. The second statement is true. The reductions are:

(Nλx.s)t (Np) x#t⇝Nx.((λx.s)t) ⇝∗Nx.s[x↦→t](σ#) x#s⇝Nx.s (N∉) x∉s⇝ s.

The conditions on x annotating the reductions can be met by successive α-renamings, because the context has sufficient freshness.

We never use the following result in this paper because we always work with reductions of a fixed term, but it is important because it expresses something about the sense in which variables represent terms:

Lemma 4.2

Suppose s is a term mentioning ai whose level (i) is no less than that of the other variables in s. Suppose u is a term such that for all variables c, if Γ ⊢c#ai then Γ ⊢c#u. Then if s ⇝t then s[u/ai] ⇝t[u/ai].

Proof

By exhaustively checking the reduction rules.End of proof

With regards to (σa), the two canonical cases are: (a) x[x↦→y]σa⇝y always; the side-condition is vacuous because x and y have the same strength. (b) X [x↦→y] reduces if x#X and y#X or ¬(x#X) and ¬(x#X), but not if x#X and ¬(y#X). This rule is the crunch case, where name-capture (encoded by freshness conditions) can block a substitution actually occurring. Intuitively, a term t can only be substituted for a variable, X say, if it satisfies the intentional conditions on use of variables which the freshness context associates to X.

4.2 The untyped lambda-calculus

Terms of the untyped λ-calculus are given by

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

λ binds x in λx.e. This is standard [3]. A translation into the context calculus is given by:

⟦x ⟧= x⟦ee′ ⟧= ⟦e ⟧⟦e′ ⟧⟦λx.e⟧=Nλx.⟦e ⟧.

(Recall Nλx.blah is shorthand for Nx.λx.blah.) We also assume some injection from the variables in the untyped λ-calculus to variables of level 1 in the context calculus. We may silently assume these injections henceforth.

Since λ does not bind in the context calculus we need an explicit N. Otherwise, the translation is as one would expect. We omit the operational semantics e →e′ of the untyped λ-calculus; a simulation result is easy to prove:

Lemma 4.3

If e →e′ then ⟦e ⟧⇝∗⟦e′ ⟧.

Multiple reductions ⇝∗, because the context calculus is an explicit substitution calculus. The proof is routine but subtle for reasons similar to the issues discussed in the last subsection. We use the fact that all variables in ⟦e ⟧ have level 1, and the corollary of the previous subsection.

Another correctness result is:

Lemma 4.4

(Preservation of strong normalisation). If e is any (possibly open) untyped λ-term then e has a normal form if and only if ⟦e ⟧ does.

Proof

Confluence of the untyped λ-calculus means that we can choose a strict left-to-right →-reduction strategy and be confident of arriving at the normal form if it exists. This particular rewrite strategy is easily simulated by the context calculus, one β-reduction corresponding to one instance of (β) followed by other rules (other reduction strategies can be less obvious because of the particular form of (σp)). It is easy to verify that if e is a normal form (has no valid β-reducts) then ⟦e ⟧ has no valid instances of (β). Finally, the reductions of the context calculus without (β) are strongly normalising.End of proof

4.3 The qν-calculus

Baro and Maurel’s qν-calculus [33] shares the context calculus’s unusual feature of spliting λ into a binder ν and an abstractor q. (We are not aware of this idea anywhere else in the literature except for our work with Fern´andez on extensions of Nominal Rewriting [11].) This translates perfectly into the context calculus, with ν mapping to N and q to λ.

4.4 Records

Say a record is a term of the form bj [a1 i1 ↦→t1] ···[an in↦→tn] where j > ik for 1 ⩽k ⩽n. In words, a record is a set of substitutions suspended on a ‘big hole’ bj.

Consider variables X2, l1, and p1, and terms tl, tp (think of them as ‘data’). For convenience drop the subscripts on variables, a convention we shall use silently henceforth.

So R = X [l↦→tl][p↦→tp] is a simple record, we say it has two data elements tl and tp which are stored at l and p on X. Call the term Nλa3.a3 [X↦→l] record lookup at l and Nλa3.a3[X↦→X [l↦→t′l]] record update at l.

We observe the following reductions:

(Nλa3.a3[X↦→l])R (β)⇝Na3.a3 [X↦→l][a3↦→R](σσ),(σa)⇝∗Na3.R[X↦→l] (σσ)⇝∗Na3.l[l↦→tl[X↦→l]][p↦→tp[X↦→l]](σa),(N#)⇝∗tl[X↦→l].

We leave it to the reader to verify similar reductions for record update.

So record lookup at l is a term which, when applied to a record, almost retrieves the data element — except for that troublesome [X↦→l]. We call this name capture.

If we suppose for the sake of argument that X#tl, then we can use (σ#) to drop the troublesome substitution. There are two ways of looking at this: either X#tl is a desirable feature, or an undesirable restriction.

To avoid name capture it is not enough to insist that X not occur in tl and tp. For example suppose tl = O4. Then the substitution [O↦→X] may arrive from the outside context, transforming tl into X! Of course we can simply insist that X#tl be provable, but there is also a more elegant way: We can call a R′ =NλX.X [l↦→tl][p↦→tp] (say X is protected). Then protected record lookup at l is encoded by Nλa3.a3l and record update by Nλa3.NλX.a3(X [l↦→t′l]). Then the variable X is bound by a N and will avoid capture (assuming, of course, that X does not actually occur in the syntax of tl when R′ is created).

More sophisticated programming with records is possible, for example in-place update. Suppose the calculus contains basic arithmetic and consider X [l↦→ 1], a simple record 1 stored at l on X. We can apply the substitution [X↦→X [l↦→l + 1]. The reader can verify the reduction

(X [l↦→1]) [X↦→X [l↦→l + 1]] ⇝∗X [l↦→l + 1][l↦→1]

— the l in l + 1 is carried by the strong substitution for X under the weak substitution [l↦→ 1]. This does not reduce further as-is, but a later lookup for l will return 2. Thus Nλa3.a3 [X↦→X [l↦→l+1]] implements a command ‘increment the value stored at l’. This term clearly relies on not using protected records, since X is free in it (later, we show how to obtain the same effect for protected records). We call this ‘in-place update’ because to increment l we do not build a new record which is a copy of the old one only with an incremented value; we actually directly modify the original item of data. This is significant from an implementational standpoint. In full generality we can replace X by any term we wish. These constructions and our notation should remind us of objects in the sense of ‘object-oriented programming’. First we consider global state, then we return to records to generalise them to objects.

4.5 Global state (with calculus)

Consider an untyped λ-calculus with general references. Terms are generated by the grammar

e ::= x |!l | l := e |Nl.e | skip | ee | λx.e.

Here l is drawn from a set of location variables and x from a set of program variables. The intended semantics of !l is ‘the value which the global state associates to l’, of l := e is ‘set l to e in the global state’, and of Nl.e is ‘allocate a fresh local location (with some unspecified or default value associated) and evaluate e in the extended state’. The rest is standard as for the untyped λ-calculus.

This calculus is roughly similar to others in the literature, for example ℒ [2, Fig. 1 and Fig. 2] and to ReFS [29, Fig. 1 and Fig. 4]. The focus of study for ℒ is a fully abstract game semantics; that of ReFS is how to prove contextual equivalences between programs. Both ℒ and ReFS are typed. For brevity we have considered an untyped calculus.

[2] contains a construction of the Y combinator using general references in a typed system, thus obtaining the power of recursion. Therefore the absence of types does not make the calculus above obviously more powerful than ℒ, though it is more powerful than ReFS, which has recursion but integer-only references.

An encoding in the context calculus is given as follows: Fix a level 3 variable W, a level 2 variable S, and a level 1 variable r. Continuing the discussion of records above, write t.l for t[S↦→l]. Write t.l := s for t[S↦→ S[l↦→s]]. (In particular, we write W.r for W[S↦→ r].)

⟦x ⟧=NλW.W.r := x⟦!l ⟧=NλW.W.l⟦l := e ⟧=NλW.(W.l := e).r := ⊤ ⟦skip ⟧=NλW.W.r := ⊤⟦λx.e ⟧=NλW, x.⟦e ⟧W⟦ee′ ⟧=NλW.⟦e ⟧((⟦e′ ⟧W).r := ⊤)((⟦e′ ⟧W).r)

The definitions above faithfully simulate the reductions we would expect of a language with references, and in particular those from [2], though we have no space to give them.

The reader may have noticed that our interpretation of global state is a ‘state transformer’; ⟦e ⟧ is a function which transforms states into other states:

4.6 Global state (with state-transformer)

As observed by Moggi [25], monads can model state in a purely functional setting. Following [18], and continuing notation from the last subsection, we define macros:

newVar =Nλx, W.Nl.W.l := xreadVar =Nλl, W.W.r := (W.l)writeVar =Nλl, x, W.(W.l := x).r := ⊤runST = λP.NW.(PW).r

For detailed explanations see [18, §2.2, 2.4] and [17, 16]. Intuitively, newVarx takes a state W (represented by a big hole!), allocates a new reference l in it, assigns l to x, and returns the new state. readVarl takes a state W and extracts the value assigned to l to the distinguished result record r. writeVar takes a reference l and a value x, and given a state W returns W with l allocated to x. If x evaluates to some term t containing readVar(l, W) then l will be linked to the old value of l, before writeVar (this is not worthy of comment in [18] because the types make it quite clear how states are passed around). Finally, runST takes a program P, applies it to a fresh empty state, and returns the result.

4.7 Objects

We propose terms for method invocation and method update which behave like constructs of the same name in the imp-ς calculus of Abadi and Cardelli [1]. For brevity we must assume the reader has some familiarity with it.

• Call NλO3, l1.O3O3l1 method invocation. Write O.l for it applied to terms O and l.

• Call NλO3, P3.NλS3, Y2.(O3S3(Y2[l1↦→(P3S3)])) method update (at l) and write O.l⇐P for it applied to terms O and P.

To see how these definitions relate to daily life and in particular to imp-ς say a term t is an (Abadi-Cardelli style) object when it has the form

NλS3, X2.(X2 [l1 1↦→s1] ···[l1 n↦→sn]).

We have typeset the levels of the variables li as superscripts and not subscripts. S may occur in the syntax of the si and plays the rôle of the self parameter in [1]. We call the terms si the data.

Consider t =NλS, X.X [p↦→S][q↦→ 0]. Then t.p =

(NλO, l.(OO)l)tp ⇝∗ttp ⇝∗NS, X.((X [p↦→S][q↦→0])[S↦→t][X↦→p])⇝∗NS, X.(X [p↦→t][q↦→0][X↦→p]) ⇝∗t

Similarly, t.q ⇝∗ 0. For the same t, consider

(t.p)⇐(NλS.⟨p, p⟩) ⇝∗NλS, Y.tS(Y [p↦→⟨p, p⟩])⇝∗NλS, Y.(Y [p↦→⟨p, p⟩][p↦→S][q↦→0])

We can verify that ((t.p)⇐(NλS.⟨p, p⟩)).p ⇝∗⟨t, t⟩.

Similarly, ((t.q)⇐(NλS.q + 1)).q ⇝∗ 1.

Recalling the discussion of records above, we have a notion of protected record with a ‘self’ parameter with implementations of method invocation and update. Note a technical feature of our presentation is that S the self parameter is abstracted at top level, and not in every data item, for example NλX.X [p↦→NλS.sp], which would be more similar to imp-ς. Both ways are possible in our calculus and our choice seemed the simpler.

Note that imp-ε is a purpose-built abstract machine with a strong notion of global state whereas the context calculus is a purely functional rewrite system (so: no state and no control of evaluation order). So we have not ‘implemented imp-ε’. We have shown that some of the behaviour it was designed to study exists in the context calculus. And this in a strong sense that for example a term ‘method invocation’ exists which when applied to a record s and a location l obtains in a suitable sense the data stored at l in s. There is no need to use a family of macros encoding ‘method invocation for s at l’ for each s and l.

We could continue with dynamic rebinding and mustering [5, 10] or modules and linking [20]. But now for something completely different:

4.8 Partial evaluation

Partial evaluation seeks strategies to optimally specialise code when some of the parameters are known. If s and t are programs (closed terms) then partial evaluation can be viewed as the search for algorithms to efficiently (in a suitable sense) compute an optimal (in a suitable sense) term u which is equivalent (in a suitable sense) to st (s applied to t).

See [8] for a short but efficient survey of this huge field. The context calculus may have something to contribute; we use an example adapted from [8, §6.1]. Write

if = λa, b, c.abc true = λab.a false = λab.b not = λa.if a false true.

in the untyped λ-calculus. It is easy to verify β-equivalences showing these terms model truth values in a suitable sense. Now suppose we want to calculate

s = λf, a.if a (f a) a specialised to s not.

A naïve method β-reduces snot and obtains a term β-equivalent to λa.if a (not a) a — a more intelligent method with access to a type system and which performs static analysis of dynamic values, may recognise that the program will always return false.

Now choose level 1 variables a, b and level 2 variables and B, C and define context calculus terms

true = λab.a false = λab.bif = λa, B, C. a(B[a↦→true])(C [a↦→false])not = λa.if a false true.

Here B and C are variables which just happen to be stronger than a. This enables to directly encode in the term knowledge we have about execution flow, e.g. (very informally) that if we get to B, a must equal true.

If we want to partially evaluate

s = λf, a.if a (f a) a specialised to s not.

we can naïvely reduce to obtain

s not⇝∗λa.a ((notB)[a↦→true][B↦→a]) (C[a↦→false][C↦→a])⇝∗λa.a ((nota)[a↦→true]) (a[a↦→false])⇝∗λa.(a false false).

This is more efficient and with types a must be true or false so the term can be specialised to false by standard techniques. So with strong variables and explicit substitution we ‘suspend information’ about a on B and C.

5. CONFLUENCE

We use an attractive result in Van Oostrom’s thesis [36, Thm 2.3.5], but we need some notation to state it.

Take X a set and ⇝⊆X ×X a reduction relation on it. In connection with X we shall always write r = (x⇝y) and s = (x⇝z) for pairs in ⇝. Take ≼ a well-founded partial order on reductions r ≼s. We write r ≺s when r ≼s and s |≼r, and r ≈s when r ≼s and s ≼r.

Call a sequence c1 = (x1⇝x2), c2 = (x2⇝x3), . . . , cn−1 = (xn−1⇝xn), a chain and write it namelessly just as x⇝∗y (n may equal 0). In the case that the chain has at length at most one (so n ⩽1) we write x⇝+y.

When ci ≺s for all elements of the chain, we write (x⇝∗y) ≺s. To assert the existence of such a chain, we write x≺s⇝∗y. Similarly for ≼ and ≈. When there is some pair r and s of reductions such that at least one of ci ≺r or ci ≺s always holds, we write (x⇝∗y) ≺{r, s}, and to assert the existence of such a chain we write (x≺{r,s} ⇝∗y).

Given x and z, to assert the existence of two chains xϕ⇝∗y and yψ⇝∗z (satisfying conditions ϕ and ψ as discussed above) for some y, we write namelessly xϕ⇝∗ψ⇝∗z.

Call a pair r = (x⇝y) and s = (x⇝z) a local divergence, and call a pair of chains y⇝∗u and z⇝∗u a convergence

Theorem 5.1

(Van Oostrom). Suppose for every pair of local divergences r = (x⇝y) and s = (x⇝z) there exists a convergence of the form y≺r⇝∗≈s⇝+≺{r,s} ⇝∗u and z≺s⇝∗≈r⇝+≺{r,s} ⇝∗u. Then ⇝ is confluent.

The partial order we impose on reductions is as follows: Instances of. . .

• (σσ) are ranked according to the size of s:

s[a↦→u][b↦→v](σσ) ⇝∗s[b↦→v][a↦→u[b↦→v]] ≺⟨s, s⟩[a↦→u][b↦→v](σσ) ⇝∗⟨s, s⟩[b↦→v][a↦→u[b↦→v]].

• (σλ) and (σλ′) are ranked according to the size of the context in which they occur:

(λa.(s[c↦→u]))[d↦→v](σλ) ⇝∗λa.(s[c↦→u][d↦→v]) ≺(λa.s)[c↦→u][d↦→v](σλ) ⇝∗(λa.(s[c↦→u]))[d↦→v]

• (σp) are ranked according to the size of ait1. . . tn.

• (β), (σa), (σ#), and (σtr), are ranked together inversely according to the size of the context in which they occur:

(s[b↦→a[a↦→u]])t(σa)⇝∗(s[b↦→u])t ≺(st)[b↦→a[a↦→u]](σa)⇝∗(st)[b↦→u]

• (Np), (Na), (Nσ), and (N∉), are ranked according to the size of the context in which they occur. For example,

(Na.s)t(Np)⇝∗Na.(st) ≺u[b↦→ (Na.s)t](Np)⇝∗u[b↦→Na.(st)]

• ≼ is reflexive; s ≼s. Everything else is incomparable:

a[a↦→ (λb.s)t](σa)⇝∗(λb.s)t |≼a[a↦→ (λb.s)t] (β)⇝∗a[a↦→s[b↦→t]])

The proof is now by the theorem above, verifying that every divergence has a suitable convergence. When closing a divergence involving scope-extrusion for N, (Na.s)t ⇝Na.(st) say, the side-condition a ∉t does not ensures a#t. However we may α-rename to some a′ such that a′#t; we assumed the context has enough freshnesses so this can be done.

Let ↔ be the transitive symmetric reflexive closure of ⇝.

Corollary 5.2

↔ does not relate all terms to all other terms (we say the calculus is consistent).

Proof

If s and t are two terms and s ↔t then by confluence there exists some u with s ⇝u and t ⇝u. To prove consistency, it suffices to exhibit two different normal forms; for example λa1.a1 and λa2.a2 (or, if the reader prefers, λa1, b1.a1 and λa1, b1.b1).End of proof

6. 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 [9] is a simple and successful polymorphic type system which underlies ML. As such it is both a ‘working (functional) programmer’s’ tool and a starting point for more complex schemes. If the context calculus interacts well with it, then it is that bit less difficult to implement, e.g. as an extension of ML.

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 σ = ∀α1. ···∀αn. τ′ (we shall just write σ = ∀α. τ here and τ = Sτ′. Also write tyv τ for the type variables appearing in τ. Write Γ, Δ for (finite) type contexts in the standard sense.

Then typing rules are as follows:

x : σ ∈Γ τ ⪯σ Γ ⊢x : τΓ, ai : τ ⊢s : τ′ Γ ⊢λai.s : τ →τ′Γ ⊢s′ : τ′ Γ, ai : ∀α. τ′ ⊢s : τ α = tyv τ′\tyv ΓΓ ⊢s[ai↦→s′] : τΓ, nj : α ⊢s : τ nj, α ∉ΓΓ ⊢Nnj.s : τΓ ⊢s : τ →τ′ Γ ⊢t : τ Γ ⊢st : τ′
Lemma 6.1

(Weakening for type judgements). If Γ ⊢s : τ then Γ, Δ ⊢s : τ.

Proof

By induction on the derivation.End of proof

Theorem 6.2

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

Proof

We exhaustively check all rules for ⇝ (we consider just two cases).

Suppose Γ ⊢(λnj.t)[ai↦→u] : τ →τ′ is derivable. By following the 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 weakening for type judgements above to weaken Γ ⊢ u : τ″ to Γ, nj : τ ⊢u : τ″.

Suppose (Nnj.s)t ⇝Nnj.(st) and Γ ⊢(Nnj.s)t is derivable. Then for some τ′, Γ, nj : α ⊢s : τ →τ′ and Γ ⊢t : τ, where α ∉ Γ. It is now easy to derive Γ ⊢Nnj.(st) : τ′.End of proof

We use the following technical lemma in the theorem which follows:

Lemma 6.3

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

Proof

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

Theorem 6.4

For all Γ and s there exists a pair (S, τ ) such that S′Γ ⊢s : τ′ if and only if (S′, τ′) ⪯(S, σ).

Proof

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

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

We prove by induction on the syntax of s that for all Γ, if (Γ ⊢? s) = (S, τ ) and α = tyv τ\tyv (SΓ) then (S, ∀α. τ) is a principal solution to (Γ ⊢? t). The case t = ai . . . is simple. Suppose t = ss′ . . . is complex but standard straight out of [9] .

Suppose t =Nai.s Let (S, τ ) and α be as in the inference rule, so that SΓ, ai : α ⊢s : τ. Suppose T Γ ⊢Nai.s : μ. Following the typing rules, T Γ, ai : α ⊢s : μ. By the universal property of (S, τ), T = US and μ = Uτ for some U. The case t = s[ai↦→s′] is also simple.End of proof

In conclusion, the type system is almost completely standard Hindley-Milner polymorphic types. The typing rule for explicit substitutions is identical to that of ML let-statements, so we are justified in viewing the explicit substitution as a let, and viewing the context calculus as an extension of a core of ML with a hierarchy of context variables (and a separation of abstraction and binding).

7. APPLICATIVE CHARACTERISATION OF CONTEXTUAL EQUIVALENCE

It is interesting to ask what an appropriate theory of contextual equivalence between programs is, since our system has programs which are contexts.

7.1 Programs, contexts, evaluations, and equivalences

It is convenient to introduce a constant ⊤. a#⊤ always and ⊤ engages in no reductions (e.g. ⊤s is a normal form for all s).

Call a term s with no free variables a program. λx.x is not a program, and Nλx.x and Nx.x are. (Recall: we write Nλx.s for Nx.λx.x.)

If s is a program write s↘ when s ⇝∗⊤ and say s evaluates.

Say C is a context when (a) C is a program and (b) C =Nλdl.D where dl is stronger than all other variables in D. We may abuse notation and also call D a context.

For example NλX2.X2, Nf1.NλX2.λf1.(f1X2)X2, and NλX2.⊤ are contexts. λX.a1 and λX2.X2 are not a contexts since they are not closed. NλX2.NλY2.Y2X2 is not a context because Y2 has level 2 and so does X2, so X2 is not strictly stronger than Y2.

An equivalence relation is a transitive symmetric reflexive relation. Call an equivalence relation 𝒳 on programs contextual (or a congruence) when

∀s, t. s 𝒳t ⇒∀C. Cs 𝒳Ct ∀s, t. s 𝒳t ∧s↘⇒t↘

Here C varies over contexts. Write =ctx for the greatest contextual equivalence, which (abusing notation) we call contextual equivalence. We discuss this definition below.

Call an equivalence relation 𝒫 on programs applicative when

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

Here u varies over programs. Write =ap for the greatest applicative equivalence and abuse notation calling it applicative equivalence.

The main result of this section is

Theorem 7.1

=ctx and =ap are equal.

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

Lemma 7.2

(Technical lemma). Write s ↔t when s and t are related by the transitive symmetric closure of ⇝. Then ↔⊆=ap and ↔⊆=ctx.

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

Proof

Suppose s ↔t. By confluence, su↘ if and only if tu↘, and similarly for Cs and Ct. The second part follows from the observation that ⊤s1. . . sn↘ is impossible unless n = 0.End of proof

Note that 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 proof below we tend to use traditional notation of D[dl↦→s] rather than (λdl.D)s.

7.2 Proof that =ctx equals =ap

Proof (=ctx equals =ap). It is easy to show that =ctx implies =ap.

Conversely suppose s =ap t. 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

{(Nas.D[dl↦→s],Nas.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 the technical lemma above, along with confluence and the inductive hypothesis, to suppose that D is in ⇝-normal form. We also silently strip leading Ns, writing for example dl for Nas.dl. Suppose D = dl. Then dl[dl↦→s] ↔s =ap t ↔dl[dl↦→t]. We use the first part of the technical lemma above and the fact that =ap is by construction 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])↔(λx1.x1D″)[dl↦→s](D′ [dl↦→t])=ap(λx1.x1D″)[dl↦→t](D′ [dl↦→t])↔(D′D″)[dl↦→t]

Here x1 is chosen fresh. We use the inductive hypothesis for D′ and λx1.(x1D″), both of which have fewer occurrences of dl then D′D″. Then D[dl↦→s] =ap D[dl↦→t] follows using the technical lemma and the fact that =ap is by construction an equivalence and also closed under application on the right. 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″. Then D′ is closed. If D′ is a λ-abstraction and 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 (checking cases) it must be that:

• D′ = λe.E for some e and E, where e#D″ does not hold but e#nj does (so (σλ) does not apply). Then D′ [nj↦→D″][dl↦→u] cannot possibly evaluate to ⊤ for any u.

• D′ =Ne.E, where e#D″ does not hold but e#nj does. Since N binds, e can always be renamed to some atom such that e#D″ does hold. Therefore, this is not a normal form.

• D′ = nj and for some e, e#D″ does not hold but e#nj does.

dl is stronger than nj and because nj is assumed bound by a top-level N which we silently omitted, we can assume that nj#dl does not hold. Then for u ∈{s, t} we can reduce as follows:

nj [nj ↦→D″][dl↦→u] (σσ)⇝ nj [dl↦→u][nj↦→D″[dl↦→u]](σb)⇝ nj [nj↦→D″[dl↦→u]].

Recall that s and t are both closed so ∀a. a#s and ∀a. a#t. By the technical lemma below, e#D″[dl↦→s] if and only if e#D″[dl↦→t]. Write u for s and/or t. If e#D″[dl↦→u] do not hold then nj [nj↦→D″[dl↦→u]] do not reduce for u ∈{s, t} and there is nothing to prove. If e#D″[dl↦→u] do hold then nj [nj↦→D″[dl↦→u]] ⇝D″[dl↦→u]. D″ is in normal form, has the same number of occurrences of dl as nj [nj↦→D″], and is strictly smaller. So we use the inductive hypothesis.End of proof

Note how the most fiddly case is nj [nj↦→D″], which might look ‘simplest’. But of course, this is the crunch case, where calculation actually gets done.

Lemma 7.3

(Technical lemma). Suppose d is a variable and s and t are terms. Suppose a#s if and only if a#t for all variables (a variable is fresh for s if and only if it is fresh for t). Then a#E [e↦→s] if and only if a#E [e↦→t], for all terms E and variables e.

Proof

By routine induction on the syntax of E.End of proof

It may be that this result can be ‘lifted’ to calculi translated into the context calculus. We only need check that at points in the proof above where we convert contexts into applicative contexts, every manipulation keeps us within the image of the translation. We have in mind results similar to those by Pitts [29] characterising contextual equivalence for languages with global state, or perhaps analogous results for MetaML (see the Conclusions). We must defer this for a later paper.

8. CONCLUSIONS AND FUTURE WORK

Our NEW calculus of contexts is a little different, because of its freshness contexts and separation of abstraction (λ) and binding (N) — but it is not so complicated and has standard (and nontrivial) meta-properties motivated in the introduction. We have programmed interesting things in it including of course contexts, but also objects, general references, and we have made some observations about tracing values variables must have as a construction encoded directly in terms, which we applied to partial evaluation. We do not believe that this exhausts the possibilities.

We now explore what we cannot do in the calculus, since it is a prototype and there is plenty of ways to extend it.

The N context calculus can express ‘s with x substituted for t’ as s[x↦→t]; this is a primitive of the calculus. We can abstract over s and t to obtain NλP, X.X [x↦→P] (X stronger than x, and P stronger than X); call this term substitution for x, because (NλP, X.X [x↦→P])tx ⇝∗s[x↦→t]. However, we cannot abstract over x;

(NλP, X, x.X [x↦→P])tsyx,P,X∉t,s,y⇝∗Nx, P, X.X [x↦→P][P ↦→t][X↦→s][x↦→y]⇝Nx, P, X.X [x↦→t][X↦→s][x↦→y]⇝∗Nx.s[x↦→t][x↦→y](σ#)⇝Nx.s[x↦→t] (σ#),(N∉)⇝ s.

This is not the intended operational behaviour. This is no surprise: variables can be substituted for at any time, so it should not possible to pass a variable as a first-class value. However we believe things are not quite so clear-cut now because of the context Γ, into which we already put assertions such as a#X (X is a hole that should not contain a). We may be able to also place assertions such as vara, meaning ‘a is a variable’. If that seems far-fetched, the reader can look at [12] where the author carries out a similar exercise to the one described in the context of first-order logic.

The N context calculus cannot express ‘substitute all varibles of level 1 for blah in s’, which we might write as s[⋆↦→blah]. This idea appears in work by Dami [10] on dynamic binding. We do believe that our context calculus could have something to say about dynamic binding and linking, but we leave that for future work.

Now we recall the problem of implementing proof-search in first-order logic. The sequent right-introduction rules for ∀ and ∃ are [4]:

Γ ⊢P [y↦→x] Γ ⊢∀y. PΓ ⊢P [y↦→t] Γ ⊢∃y. P

Here x ∉ Γ, P and t is any term. This can be a problem, for example for the design of a theorem-prover such as Isabelle [27], since it may become apparent only further up in the proof-tree (if at all) which t is appropriate. Isabelle uses, instead of t, an existential variable which behaves much like a level 2 variable only function-application is used to control scope.

We can certainly model existential variables using variables of level 2; for example ∃?t. P (?t) is modelled by a term of the form ∃λX.PX where ∃ is some constructor. Substitutions on X can be discovered deep in a proof, e.g. when we arrive at a leaf Γ ⊢X = 1, and the substitution can be passed upwards and applied directly to the proof-state as a whole to specialise X. However, there is no way to write a unification algorithm in the N context calculus precisely because variables can be instantiated randomly by explicit substitutions from outside.

It is of significant long-term interest to present proof-search and programming (if the reader prefers; unification and tactics) in a unified framework, so we should definitely consider whether anything can be done here. We can introduce judgements of the form vara into the context, and constructors into the calculus which detect when a variable is ‘known’ to be a variable in that sense. We can impose types and build the terms of the logic in an inductive datatype. A more-or-less strict evaluation order would avoid issues with confluence. We could try to solve only higher-order patterns [23], or restrict substitutions to be fresh renamings (substitutions of atoms for fresh atoms, similar in power to FM swapping [13]). Nominal Unification [35] already implements an algorithm which can be viewed as a special case of unifiers and the author’s a-logic [12] introduces a logical judgement ‘this is a variable’ into first-order logic; so there is hope.

(We should mention that even in purely propositional logic, the Cut rule can be programmed in a similar way using a meta-variable for the formula introduced by the cut. So the issues just discussed arise in many logics and on many levels.)

We mention staged computation, as in for example MetaML [26, 28], Template Haskell [32], and Converge [34]. These languages 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 context calculus cannot model staged computation, simply because it is a pure rewrite system with no control of evaluation order. However, it is possible to design a programming language based on the N context calculus which can model staged computation. We have explored the idea in detail but have no space to do more than indicate the idea: in the term s[a↦→t], restrict evaluations in t to those involving variables that are at least as strong as a. So for example a3 [a1↦→(λa2.1)0] ⇝a3 [a1↦→ 1], but a3 [a2↦→(λa1.1)0] does not reduce. a3[a2↦→(λa2.λa1.a2)11 ⇝∗a3 [a2↦→λa1.1], because a2 is strong enough to reduce under a substitution by a2, but a1 is not. This to give enough control of execution flow to encode the brackets, escape, and run of MetaML (as well as other less exotic constructs, such as call-by-name and call-by-value versions of function application).

This programming language is as expressive as the N context calculus; we just have control of execution flow. We expect it has the same good meta-properties as the smaller and simpler calculus of this paper, but proving that is for future work. We can hope the language might provide a semantics and common intermediate language for comparing additional features related to control of execution flow.

Other obvious extensions of the calculus include enriching the structure and treatment of levels. Finally, it is interesting to ask what kind of abstract machine is suitable for executing the N context calculus (or the staged version discussed above). We have some promising results in this direction but they too must remain for another paper.

9. REFERENCES

[1] Martín Abadi and Luca Cardelli, An imperative object calculus, TAPSOFT ’95: Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, LNCS, vol. 915, 1995, pp. 471–485.

[2] S. Abramsky, K. Honda, and G. McCusker, A fully abstract game semantics for general references, Proc. 13th IEEE Symp. Logic in Comp. Sci., IEEE Computer Society Press, 1998, pp. 334–344.

[3] H. P. Barendregt, The lambda calculus: its syntax and semantics (revised ed.), Studies in Logic and the Foundations of Mathematics, vol. 103, North-Holland, 1984.

[4] John Bell and Mosh´e Machover, A course in mathematical logic, North-Holland, 1977.

[5] Gavin Bierman, Michael Hicks, Peter Sewell, Gareth Stoyle, and Keith Wansbrough, Dynamic rebinding for marshalling and update, with destruct-time lambda, Proceedings of ICFP 2003: the 8th ACM SIGPLAN International Conference on Functional Programming (Uppsala), August 2003, pp. 99–110.

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

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

[8] Charles Consel and Olivier Danvy, Partial evaluation: Principles and perspectives, Journ´ees Francophones des Langages Applicatifs, February 1993, pp. 493–501.

[9] Luis Damas and Robin Milner, Principal type-schemes for functional programs, POPL ’82: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM Press, 1982, pp. 207–212.

[10] Laurent Dami, A lambda-calculus for dynamic binding, Theoretical Comp. Sc. 192(2) (1998), 201–231.

[11] Maribel Fern´andez and Murdoch J. Gabbay, Extensions of nominal rewriting, PPDP, 2005.

[12] Murdoch J. Gabbay, a-logic, Submitted, 2005.

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

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

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

[16] Peyton Jones, Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in haskell, Engineering theories of software construction, Marktoberdorf Summer School, NATO ASI, 105 Press, 2001, pp. 47–96.

[17] Simon L. Peyton Jones and Philip Wadler, Imperative functional programming, Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina, 1993, pp. 71–84.

[18] John Launchbury and Simon L. Peyton Jones, Lazy functional state threads, PLDI ’94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, ACM Press, 1994, pp. 24–35.

[19] Pierre Lescanne, From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions, POPL, 1994, pp. 60–69.

[20] Elena Machkasova and Franklyn A. Turbak, A calculus for link-time compilation, Lecture Notes in Computer Science 1782 (2000), 260–274.

[21] Ian Mackie Maribel Fern´andez, Murdoch J. Gabbay, Nominal rewriting, Submitted, January 2004.

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

[23] Dale Miller, A logic programming language with lambda-abstraction, function variables, and simple unification, Extensions of Logic Programming (1991), no. 475, 253–281.

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

[25] Eugenio Moggi, Notions of computation and monads, Inf. Comput. 93 (1991), no. 1, 55–92.

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

[27] Larry Paulson, The Isabelle reference manual, Cambridge University Computer Laboratory, February 2001.

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

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

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

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

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

[33] Francois Maurel Sylvain Baro, The qnu and qnuk calculi : name capture and control, Tech. report, Universit´e Paris VII, March 2003, Extended Abstract, Pr´epublication PPS//03/11//n16.

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

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

[36] Vincent van Oostrom, Confluence for abstract and higher-order rewriting, Ph.D. thesis, Vrije Universiteit, Amsterdam, March 29 1994.

Notes

1We are very grateful to Pierre Lescanne, Laurence Tratt, Andrew Pitts, David Richter, Gérard Huet, Maribel Fern´andez, Antonino Salibra, and Gilles Dowek, for encouragement, help, conversations, and advice.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. PPDP’05, July 11–13, 2005, Lisbon, Portugal. Copyright 2005 ACM 1-59593-090-6/05/0007 ...$5.00.

2We take this opportunity to thank Sato for his hospitality in Kyoto, and for many interesting conversations.