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

Two-level lambda-calculus

Murdoch J. Gabbay http://www.gabbay.org.uk

Dominic P. Mulligan http://www.macs.hw.ac.uk/˜dpm8

Abstract

Two-level lambda-calculus is designed to provide a mathematical model of capturing substitution, also called instantiation. Instantiation is a feature of the ‘informal meta-level’; it appears pervasively in specifications of the syntax and semantics of formal languages. The two-level lambda-calculus has two levels of variable. Lambda-abstraction and beta-reduction exist for both levels. A level 2 beta-reduct, triggering a substitution of a term for a level 2 variable, does not avoid capture for level 1 abstractions. This models meta-variables and instantiation as appears at the informal meta-level. In this paper we lay down the syntax of the two-level lambda-calculus; we develop theories of freshness, alpha-equivalence, and beta-reduction; and we prove confluence. In doing this we give nominal terms unknowns — which are level 2 variables and appear in several previous papers — a functional meaning. In doing this we take a step towards longer-term goals of developing a foundation for theorem-provers which directly support reasoning in the style of nominal rewriting and nominal algebra, and towards a mathematics of functions which can bind names in their arguments.

Keywords: Lambda Calculus, Meta-variables, Functional programming, Confluence, Nominal terms

1 Introduction

The λ-calculus is a syntax to express function abstraction and application which is simple, amenable to mathematical analysis, and easy to extend. Yet not everything that looks like a function fits obviously into the λ-calculus; examples include meta-variables, capturing substitution, and functions depending on intensional properties like free variables and freshness conditions associated with free variables.

This paper defines a λ-calculus which contains a model of λ-abstraction and β-reduction for meta-variables, including capturing substitution and freshness conditions.

The idea of internalising meta-variables and capturing substitution into formal languages is a recurrent theme in the literature, though our application of nominal techniques to the problem is new and specific to our work. Models of meta-variables and capturing substitution appear in Jojgov’s thesis and subsequent work [20,22], in Munõz’s thesis [25], in work by Hashimoto and Ohori [21], by Lee and Friedman [5], and by Kahrs [23]. This is also a theme in the first author’s research [7,9,11].

Authors cite various motivations for internalising meta-variables and studying capturing substitution; each author comes to the problem with their own individual background, though the ‘convergent evolution’ — the product is always some form of capturing substitution! — suggests that an underlying mathematical entity is being uncovered. These motivations include representing intermediate proof-states (i.e. states of a theorem-prover as it builds a derivation as in the case of Muñoz [25]), and representing ‘λ-terms with holes’ as a foundation for describing distributed programs, modules, linking, and other manipulations of ‘program fragments’ ([21,5] belong to this camp and both cogently describe their vision). A comparison with related work is in the Conclusions.

We also think some straightforward mathematical curiosity is called for: capture-avoiding substitution is well-studied and finds expression in many formal logics and calculi, yet capturing substitution is fundamental — see the discussion of the informal meta-level in the next paragraph, or the discussions in the papers by the authors cited above — and it has received relatively less formal attention.

We come to this material from the first author’s investigation of nominal rewriting with Fernández [8] and of nominal algebra with Mathijssen [14,24] as mathematical foundations. These use nominal terms [29,8,14] (see also later in this paper) advantageously, as a syntax for rewrite rules and algebraic axioms, which very closely model rules and axioms in what we shall call the informal meta-level — the prose discourse of, for example, this paper. In the informal meta-level, capturing substitution and freshness conditions are widespread. Here are some examples:

• λ-calculus: (λx.r)[y↦ →t] = λx.(r[y↦ →t]) if x is fresh for t

• π-calculus: νx.(P | Q) = P | νx.Q if x is fresh for P

• First-order logic: ∀x.(φ ⊃ψ) = φ ⊃∀x.ψ if x is fresh for φ

These quoted (reified) informal statements mention two levels of variable; object-variables x, y and meta-variables r, t, P, Q, φ, ψ. Capture-avoidance conditions are (freshness) constraints on the values that meta-variables may assume.

It seems that meta-variables are naturally substituted with capturing substitution; consider the following quote:

“Set r to x and t to x in (λx.r)[y↦ →t]; obtain (λx.x)[y↦ →x].”

Capturing substitution on syntax trees is not hard to define, yet syntax usually has semantics, which motivates the study of (amongst other things) α-equivalence, unification, and β-equivalence.

Nominal terms feature a two-level hierarchy of variables directly reflecting the hierarchy noted above:

• level 1 variables a, b, c, d, . . . (atoms) model object-variables;

• level 2 variables X, Y, Z, . . . (unknowns) model meta-variables.

Variables in nominal terms have no in-built functional meaning. There is no λ-abstraction λX or λa, and no application. In a suitable (generalised) sense, nominal terms are first-order. Indeed, until now the semantics for level 2 variables (unknowns) in nominal terms has been ‘they range over terms’. This purely syntactic meaning is acceptable for unification, matching, and rewriting [29,8], and possibly for logic-programming [3], but taking a broader view this is clearly only a partial answer. In this paper we extend nominal terms to investigate full αβ-equivalence in the presence of level 1 and level 2 variables (thus: αβ-equivalence in the presence of object- and meta-variables). By giving level 2 variables a notion of λ-abstraction and β-reduction, we give them a functional operational semantics.

We present two-level λ-calculus. We give a syntax, reduction system, and prove confluence and consistency. The calculus contains the untyped λ-calculus (two copies, in fact; at level 1 and level 2), so it is not strongly normalising.

Just as the step from first-order terms to higher-order terms implies an increase in expressivity traded against the loss of some computational and mathematical properties [31], so we expect similar benefits and drawbacks moving from nominal terms to two-level λ-calculus — but the λ-calculus now expresses both capturing and capture-avoiding substitution.

We sketch with examples the kind of thing we can do, or believe should be possible in future work, using two-level λ-calculus. Syntax and full definitions follow.

“Set t to be x in λx.t” and “set t to be y in λx.t” are modelled by reductions

(λX.(λa.X))a → (λa.X)[X := a] ≡ λa.a and (λX.(λa.X))b → (λa.X)[X := b] ≡ λa.b.

(≡ is syntactic equivalence, i.e. ‘the same term’.) Capture-avoidance for λa (level 1) in the presence of level 2 variables is managed using permutations and freshness in nominal terms style:

c#X ⊢(λb.(λa.X))a →λc.(((c a) · X)[b↦ →a]).

“Set r to x and t to x in (λx.r)[y↦→t]; obtain (λx.x)[y↦→x]” is expressed by:

“λZ.λY.((λa.Z)[b↦ →Y]) applied to a twice reduces to (λa.a)[b↦ →a].”

It is not hard to impose a simple type system on our syntax (this should be a special case of [6]; here, λX should cause no essential new difficulties). An interesting application for our calculus is as the basis of a logic. Example axioms are (we indicate types with subscripts):

• ∀Po.(ao#Po ⊃Po ⊃∀ao.Po) Here o is a type of truth-values. ∀ is short for ∀λ where ∀ is a constant symbol. # is short for #λ where # is a constant symbol intended to internalise the nominal freshness judgement. This models ‘for all φ, if a ∉ fv(φ) then φ ⊃∀a.φ’.

• ∀Xα.(aβ#Xα ⊃λaβ.(Xαaβ) = Xα)

Here = is a constant symbol, written infix. α and β are intended to be arbitrary types. This models η-equivalence (extensionality) at level 1.

• ∀Po.(NИaA.¬Po) ⇔¬NИaA.Po.

Here NИ is short for NИλ where NИ is a constant symbol intended to internalise the Gabbay-Pitts ‘new’ quantifier [19]. ¬ and ⇔ are constant symbols. A is a ‘type of atoms’ with no term-formers. This models the self-duality of NИ.

The reductions are real reductions in our calculus. The axioms are expressed in a logic which does not yet exist, but they still have some mathematical force because the structure they express has been studied in previous work with level 2 variables but (since nominal terms have no λX) without a level 2 quantification explicitly represented in the syntax. The literature contains theories (sets of axioms) for several specific object languages, including first-order logic, the π-calculus, and subsets of ML [24,19,8,11]. It also contains a study describing how to use a fragment of the calculus in this paper, as the term-language for a Curry-Howard correspondence for ‘incomplete derivations’ [13] (level 2 variables represent ‘unknown proofs’, as in Muñoz [25]). Authors mentioned above have their own reasons for considering multi-level systems [20,22,25,21,5,23] and we currently see no obvious reason why the ideas in this paper might not also be turned to other applications.

2 The syntax

Definition 1

Fix disjoint countably infinite sets of level 1 and level 2 variables. We let a, b, c, . . . and X, Y, Z, . . . range over level 1 and level 2 variables respectively. We use a permutative convention that these are distinct. For example, ‘a and b’ means any pair of distinct level 1 variables. 1

Remark 2

Level 2 variables are sometimes called meta-variables (as in for example [25]). We prefer not to do this; level 2 variables are designed to model meta-variables, but they inhabit the syntax and are objects in the formal syntax. The ‘real’ meta-level still exists — for example we are writing in it now — and mixing terminology for the real thing and our formal model of it, seems to us too great a possible source of confusion.

Definition 3

A permutation π is a finitely supported bijection of level 1 variables. Here ‘finitely supported’ means that π(a) = a for all but finitely many level 1 variables.

Write id for the identity permutation, so id(a) = a always; write ◦ for functional composition, so

(π ◦π′)(a) = π(π′(a)).

Write π-1 for inverse. Write (a b) for the swapping such that

(a b)(a) = b, (a b)(b) = a, and (a b)(c) = c.
Definition 4

Let the syntax of two-level λ-calculus be:

r, s, t, u, v ::= a | π · X | λa.r | λX.r | rr

Intuitively, this is two copies of the λ-calculus; a level 1 copy with a, rr, and λa.r, and a level 2 copy with π·X, rr, and λX.r. Both copies have capture-avoiding substitution within their own level. The challenge is to understand how these two copies interact; we discuss this in the rest of this section.

a[X := t] ≡ a (π · X)[X := t] ≡ π · t (π · Y )[X := t] ≡ π · Y (λa.r)[X := t] ≡ λa.(r[X := t]) (r′r)[X := t] ≡ (r′[X := t])(r[X := t]) (λY.r)[X := t] ≡ λY.(r[X := t]) (Y ∉ fv(t)) π · a ≡ π(a) π · (π′ · X) ≡ (π ◦ π′) · X π · (r′r) ≡ (π · r′)(π · r) π · (λa.r) ≡ λπ(a).(π · r) π · (λX.r) ≡ (λX.π · r[X := π-1 · X])
Figure 1. Level 2 substitution and level 1 permutation action (Definition 6)

We equate terms up to α-equivalence of λX-bound variables, but not λa-bound variables (this is not necessary, but it is convenient). We write ≡ for syntactic equivalence (up to α-equivalence of λX-bound variables). For example,

λX.X ≡λY.Y but λa.X ≢λb.X and λa.a ≢λb.b.

There is no paradox here. We do not seek to eliminate the meta-level; we want mathematical models with which to study it. That is why we have given our calculus two levels of variable.

We may write

r[a↦ →t] as shorthand for (λa.r)t.
Definition 5

Define a notion fv(r) of free occurrence (for level 2) by:

fv(a) = ∅ fv(π · X) = {X} fv(r′r) = fv(r′) ∪ fv(r) fv(λa.r) = fv(r) fv(λX.r) = fv(r) \ {X}
Definition 6

Define level 2 substitution r[X := t] and level 1 permutation actions by the rules in Figure 1.

Level 2 substitution avoids capture by λ-abstracted level 2 variables, but not by λ-abstracted level 1 variables. Compare the clauses for (λa.r)[X := t] and (λY.r)[X := t]:

• (λa.r)[X := t] ≡λa.(r[X := t]) always (no condition that ‘a should be fresh for t’).

• (λY.r)[X := t] ≡λY.(r[X := t]) provided Y ∉fv(t) (a freshness condition).

From the point of view of level 1 variables, level 2 variables behave like meta-variables and are instantiated. The usual apparatus of level 2 β-conversion gives us the power to program ‘normally’ at level 2.

The level 1 permutation action π · r is the general mechanism by which level 1 α-renaming is managed; it is based on ideas inherited from nominal terms [29]. It is not always the case that π · r is α-equivalent with r, but in specific special cases where all variables that π permutes are bound, this is the case; more on this in Section 3. For example,

(a b) · λa.λb.ab ≡λb.λa.ba.

For a discussion of the advantages of this approach, see Cheney’s comment that permutations are ‘inherently capture-avoiding’ [2] and the surrounding discussion.

π ·X is a moderated level 2 variable; this is the point in the raw syntax where the two levels of variable interact. Moderations rename level 1 variables in uninstantiated level 2 variables; for example:

((b a) · X)[X:=a] ≡b

In Definition 6 we must decide how the permutation action π · r interacts with level 2 λ-abstraction λX (this is a new issue which does not appear in nominal terms, because they do not have level 2 λ-abstraction). The intuition is ‘π moderates free but not bound level 2 variables’. For example:

π · (XY ) ≡(π · X)(π · Y )
π · λX.(XY ) ≡λX.Xπ · Y
π · λY.λX.(XY ) ≡λY.λX.(XY ).

Y ∉fv(t) in the clause for (λY.r)[X := t] can be guaranteed by renaming Y . The definitions of r[X := t] and π · r are intertwined. This is due to the clause for π · (λX.r). The proof that π · r and r[X := t] are well-defined is routine, and we omit it. It uses a notion of depth of a term, which will be useful later:

depth(a) = 1 depth(π · X) = 1 depth(λa.r) = 1 + depth(r) depth(λX.r) = 1 + depth(r) depth(r′r) = depth(r′) + depth(r)
Lemma 7

r[X := π · X][X := π′ · X] ≡r[X := (π ◦π′) · X]

Lemma 8

π · (π′ · r) ≡ (π ◦π′) · r

Lemma 9

π · (rσ) ≡ (π · r)σ

Proof

We prove the result for σ = [Y := u] by induction on r. We consider just the case of λX.r: α-converting X if necessary, assume X ∉fv(u). Then:

(π · λX.r)[Y := u] ≡ λX.(π · r[X := π-1 · X][Y := u]) π · ((λX.r)[Y := u]) ≡ π · (λX.r[Y := u]) ≡ λX.(π · r[X := π-1 · X][Y := u]).

□

Lemma 10

depth(r) = depth(π · r).

3 Freshness and reductions

3.1 Definition of the rules

Definition 11

We define some notation:

• A freshness is a pair a#r of a level 1 variable and a term.

• Call a#X a primitive freshness.

• Call a finite set of primitive freshnesses ∆ a freshness context.

(a#b) ∆ ⊢ a#b (a#λa) ∆ ⊢ a#λa.r ∆ ⊢ a#r (a#λb) ∆ ⊢ a#λb.r π-1(a)#X ∈ ∆ (a#X) ∆ ⊢ a#π·X ∆ ⊢ a#r′ ∆ ⊢ a#r (a#app) ∆ ⊢ a#r′r ∆, a#X ⊢ π(a)#π·r (X ∉ ∆) (a#λX) ∆ ⊢ π(a)#π·(λX.r)
Figure 2. Freshness entailment (Definition 11)

We may drop set brackets, for example writing {a#X, b#X} as a#X, b#X and writing ∆, a#X for ∆∪{a#X}. We may also write a#X, b#X as a, b#X.

Figure 2 gives freshnesses a notion of derivation.

The notion of nominal freshness is well-discussed [19,29,24]. Intuitively,

a#r corresponds with ‘a ∉fv(r)’,

read ‘a is abstracted/not free in r’. In the presence of level 2 variables, which can be instantiated (substituted in a possibly capturing manner) to any term, the notion of ‘free variables’ is replaced by a notion of freshness which may depend on freshness assumptions on level 2 variables. For example:

(a#X) (a#X) a#X, a#Y ⊢ a#X a#X, a#Y ⊢ a#Y (a#app) a#X, a#Y ⊢ a#XY (a#λX) a#Y ⊢ b#λX.(X(b a) · Y ) (a#λa) a#X ⊢ a#λa.X (a#λX) ⊢ a#λX.λa.X

We may write ‘∆⊢a#t’ as shorthand for ‘∆⊢a#t is derivable’. We use this shorthand for other derivable assertions including →, →∗, ⇒, ⇒∗, defined later.

Remark 12

(a#λX) does not implement the denotational notion of freshness for functions from nominal sets [19], with intuition “(b a) · λX.r equals λX.r for fresh b”. Informally, a is fresh for the function ‘λX.λa.X’ in the sense of (a#λX), but not fresh in the sense of nominal sets. (a#λX) is a strictly weaker condition; a discussion of denotations is for a later paper.

Remark 13

(a#λX) is syntax directed, in the following sense:

depth(π · λX.r) = depth(r) + 1 > depth(r) = depth(π · r)

See Lemma 10.

Definition 14

Write ∆⊢ - ▷ - for a binary relation on terms parameterised on ∆. Call ∆⊢ - ▷ - a congruence when it is closed under the rules named ▷ in Figure 3.

∆ ⊢ r ▷ s (▷λa) ∆ ⊢ λa.r ▷ λa.s ∆ ⊢ r ▷ s ∆ ⊢ t ▷ u (▷app) ∆ ⊢ rt ▷ su ∆ ⊢ r ▷ s (X ∉ ∆) (▷λX) ∆ ⊢ λX.r ▷ λX.s ∆ ⊢ r ▷ s ∆ ⊢ a#s ∆ ⊢ b#s (▷α) ∆ ⊢ r ▷ (a b) · s (βa) ∆ ⊢ a[a ↦→ t] → t ∆ ⊢ a#r (β2app) ∆ ⊢ (r′r)[a ↦→ t] → (r′[a ↦→ t])r ∆ ⊢ a#r (β#) ∆ ⊢ r[a ↦→ t] → r level (r′) = 1 (β1app) ∆ ⊢ (r′r)[a ↦→ t] → (r′[a ↦→ t])(r[a ↦→ t]) (β2) ∆ ⊢ (λX.r)t → r[X := t] ∆ ⊢ b#t (βλ1) ∆ ⊢ (λb.r)[a ↦→ t] → λb.(r[a ↦→ t]) (X ∉ fv(t)) (βλ2) ∆ ⊢ (λX.r)[a ↦→ t] → λX.(r[a ↦→ t])
Figure 3. Congruence (Definition 14) and reductions (Definition 17)
Remark 15

(▷α) builds in the nominal term notion of α-equivalence for level 1 variables (see [14, Lemma 3.2]). A better name for congruence might be ‘congruent α-equivalence’, but we just write ‘congruence’.

Definition 16

Write level(t) = 2 if t mentions a level 2 variable, free or bound. Otherwise, write level(t) = 1. For example

level((a b) · X) = level(λX.X) = 2 and level(a) = level(λa.a) = 1.

Write a ∉∆ when a#X ∉∆ for all level 2 variables X. Write X ∉∆ when a#X ∉∆ for all level 1 variables a.

We can now define our reduction relation:

Definition 17

Let ∆⊢ - → - be the least congruence closed under the rules named β in Figure 3.

Recall that r[a↦ →t] is sugar for (λa.r)t.

Remark 18

Level 2 β-reduction is a single step [X := t], level 1 β-reduction is not. Definition 27 gives the single step level 1 β-reduction. There are no level 3 variables in this particular calculus and therefore no special need arises to break level 2 β-reduction into smaller steps.

Example reductions are in the Introduction. Note that capture-avoiding substitution is as usual within a single level:

(λb.(λa.b))a →∗ λa′.(b[b ↦→ a]) → λa′.a (λY.(λX.Y ))X →λX′.(Y [Y := X]) ≡ λX′.X

3.2 Discussion of rules (β1app) and (β2app)

(β1app) and (β2app) can be viewed as two parts of a single rule (βapp):

∆ ⊢ a#r or level (r′) = 1 (βapp) ∆ ⊢ (r′r)[a ↦→ t] → (r′[a ↦→ t])(r[a ↦→ t])

If level(r′) = 1 and ∆⊢a#r we may join (β1app) and (β2app) with (β#), like so:

(r′r)[a↦ →t](β2app) - (r′[a↦ →t])r6(β1app)∗(r′[a↦ →t])(r[a↦ →t])?(β#)- (r′[a↦ →t])r?(r′r)[a↦t] \overset{(β2app)}{→} (r′[a↦t])r (r′r)[a↦t] \overset{(β1app)}{→} (r′[a↦t])(r[a↦t]) (r′[a↦t])(r[a↦t]) \overset{(β#)}{→} (r′[a↦t])r (r′[a↦t])r ↕* (r′[a↦t])r

The restrictions in (β1app) and (β2app) are necessary. Suppose we drop them, to obtain just one rule

(r′r)[b↦ →u](FALSE)−→\overset{(FALSE)}{⟶}(r′[b↦ →u])(r[b↦ →u]).

Then for example: 2

((λX.X[b ↦→ a])b)[b ↦→ c] (FALSE)−→\overset{(FALSE)}{⟶} (λX.X[b ↦→ a])[b ↦→ c](b[b ↦→ c]) (βλ2), (βa)−→\overset{(βλ2),(βa)}{⟶} (λX.X[b ↦→ a][b ↦→ c])c (β2)−→\overset{(β2)}{⟶} c[b ↦→ a][b ↦→ c] (β#), (β#)−→\overset{(β#),(β#)}{⟶} c
((λX.X[b ↦→ a])b)[b ↦→ c] (β2)−→\overset{(β2)}{⟶} b[b ↦→ a][b ↦→ c] (β1)−→\overset{(β1)}{⟶} a[b ↦→ c] (β#)−→\overset{(β#)}{⟶} a

Thus, confluence fails in the presence of (FALSE).

Intuitively, level 2 and level 1 β-reducts can ‘compete’ to instantiate variables. The side-conditions on (β1app) and (β2app) prevent this competition from destroying confluence. Intuitively level 2 β-reductions ‘happen first’ — though note that, subject to the side-conditions, β-reducts can reduce in any order in the two level λ-calculus.

More formally, to close a divergence in ((λX.r)t)[b↦ →u] between (β2) and (FALSE) we must join

r[X := t][b↦ →u] and r[b↦ →u][X := t[b↦ →u]],

where X ∉ fv(u) and X ∉ fv(t) and where the freshness context ∆ is such that ∆⊢b#u. It is not possible to join this in general, as the example above shows. It is possible to join this if level(r) = 1 or if ∆⊢b#t.

The interested reader might like to compare the side-conditions in (β1app) and (β2app) with the side-condition on the corresponding rule (σp) in the lambda-context calculus [11, Figure 5]. For the reader’s convenience we reproduce it here (ai denotes a variable of level i; the lambda context calculus has an infinite hierarchy of levels):

(ss′)[ai↦ →t] →(s[ai↦ →t])(s′[ai↦ →t]) (level(s), level(s′), level(t) ≤i)

Transposing this to the two-level lambda-calculus we would obtain a rule

level (r′) = level (r) = level (t) = 1 (βLCC) ∆ ⊢ (r′r)[a ↦→ t] → (r′[a ↦→ t])(r[a ↦→ t])

Clearly, (β1app) and (β2app) allow more reductions than (βLCC). The technical reason that we are able to allow these reductions turns out to be the stronger theory of α-equivalence in this paper. Specifically, we should look at the renaming to fresh c in the case of (λb.r)[a := t] if ∆⊬b#t in Definition 27. That renaming is not in general possible in the lambda-context calculus; the lambda-context calculus lacks freshness contexts and permutations, so it is not always possible to generate a fresh c and rename a level 1 binding to our fresh c using a permutation. More comment on the lambda-context caluclus is in the Conclusions.

3.3 Substitution and soundness

In the rest of this section we prove soundness results; that freshness and reduction are preserved under instantiating level 2 variables (Lemma 20 and Theorem 24), and that freshness is preserved under reduction (Theorem 22):

Definition 19

A substitution σ is a finitely supported map from level 2 variables to terms. ‘Finitely supported’ means that σ(X) ≡ id · X for all but finitely many variables. These act on terms tσ in the natural way, extending the action of [X := t] from Definition 6. We extend this action pointwise as convenient; in particular we write ∆σ for {a#σ(X) | a#X ∈∆}.

If F is a set of freshnesses write ∆′ ⊢F for ‘∆′ ⊢a#r for every a#r ∈F’. Lemma 20 is soundness for substitutions compatible with the freshness context:

Lemma 20

If ∆′ ⊢∆σ then ∆⊢a#r implies ∆′ ⊢a#(rσ).

Proof

By induction on r. We consider two cases:

− The case of λa. ∆′ ⊢a#(λa.r)σ always, by (a#λa).

− The case of λX. Suppose ∆, a#X ⊢π(a)#π · r is derivable, where X ∉∆.

Suppose the inductive hypothesis of the derivation. Renaming X if necessary, we may assume that X ∉∆′ and σ(X) ≡X. By inductive hypothesis ∆′, a#X ⊢ π(a)#(π · r)σ is derivable. By Lemma 9, (π · r)σ ≡π · (rσ). We extend the derivation with (a#λX) to obtain a derivation of ∆′ ⊢π(a)#π · (λX.(rσ)). We then have π · (λX.(rσ)) ≡π · ((λX.r)σ) ≡ (π · λX.r)σ (the final ≡ uses Lemma 9), and the result follows.

□

Lemma 21

∆⊢a#r implies ∆⊢π(a)#π · r.

Proof

By induction on derivations, we consider just one case:

− The case (a#λX). Suppose ∆, a#X ⊢π(a)#π · r. By inductive hypothesis ∆, a#X ⊢π′(π(a))#π′ · (π · r), so ∆, a#X ⊢ (π′ ◦π)(a)#(π′ ◦π) · r by Lemma 8.

Using (a#λX) we derive ∆⊢ (π′◦π)(a)#(π′◦π)·λX.r. We use Lemma 8 to deduce ∆⊢π′(π(a))#π′ · (π · λX.r).

□

Theorem 22 is ‘subject-reduction for freshness’:

Theorem 22

If ∆⊢r →s then ∆⊢a#r implies ∆⊢a#s.

Proof

By induction on derivations. We consider a selection of cases:

− The case (β2app), assuming ∆⊢b#r. Suppose ∆⊢b#r and ∆⊢ (r′r)[b↦ → u] → (r′[b↦ →u])r.

If ∆⊢a#(r′r)[b↦ →u] then ∆⊢a#r′, ∆⊢a#r, and ∆⊢a#u. It follows that ∆⊢a#(r′[b↦ →u])r. Similarly if ∆⊢b#(r′r)[b↦ →u]. Similarly for (β1app).

− The case (β2). Suppose that ∆⊢ (λX.r)t →r[X := t].

If ∆⊢a#(λX.r)t then ∆⊢a#t and ∆, a#X ⊢a#r. It follows by Lemma 20 that ∆⊢a#r[X := t] as required.

− The case (▷α). Suppose that ∆⊢r →s and ∆⊢a#s and ∆⊢b#s.

∆⊢a#s and ∆⊢b#s by assumption. If ∆⊢c#r then, by inductive hypothesis, ∆⊢c#s, and so ∆⊢c#(a b) · s by Lemma 21.

□

Lemma 23

If level(r) = 1 then level(rσ) = 1.

Theorem 24 does for → what Lemma 20 did for freshness; it is a form of soundness under substitutions compatible with the freshness contexts:

Theorem 24

If ∆′ ⊢∆σ then ∆⊢r →s implies ∆′ ⊢rσ →sσ.

Proof

By induction on derivations. We present a selection of cases.

− The case (β#). Suppose ∆⊢a#r. By Theorem 22 ∆′ ⊢a#rσ if ∆⊢a#r. It follows by (β#) that ∆′ ⊢rσ[a↦ →tσ] →rσ.

− The case (β1app). We have (r′r)[a↦ →t]σ ≡ (r′σ)(rσ)[a↦ →tσ]. By assumption level(r′) = 1 so by Lemma 23, level(r′σ) = 1 and ∆′ ⊢ (r′σ)(rσ)[a↦ →tσ] → (r′[a↦ →t])(r[a↦ →t])σ by (β1app). The result follows.

− The case (βλ1). By Theorem 22 if ∆⊢b#t then ∆′ ⊢b#tσ. It follows by (βλ1) that ∆′ ⊢ (λb.rσ)[a↦ →tσ] →λb.(rσ[a↦ →tσ]). As λb.(rσ[a↦ →tσ]) ≡ (λb.r[a↦ → t])σ, the result follows.□

4 Confluence

Our calculus can be viewed as two λ-calculi (level 1, level 2) glued together by a nominal treatment of the interaction of level 1 α-equivalence with level 2 variables. The proof of confluence also splits into two proofs, plus some ‘proof-glue’.

4.1 Level 1 reductions

Definition 25

Let (level1) be the set

{(βa), (β#), (β1app), (β2app), (βλ1), (βλ2)}

of rules from Figure 3. Let ∆⊢r(level1)−→\overset{(level1)}{⟶}s be the least congruence closed under the rules in (level1).

Definition 26

Write ∆⊬a#r when ∆⊢a#r is not derivable.

Choose some fixed but arbitrary order on atoms. If S is a finite set of atoms say ‘for the first atom not in S’ to mean ‘for the least atom, in our fixed but arbitrary order, that is not an element of S’. 3

Definition 27

For a given ∆, define a level 1 substitution action r[a := t] as below; earlier rules take priority:

−r[a := t] ≡r if ∆⊢a#r.

− a[a := t] ≡t.

− (π · X)[a := t] ≡(π · X)[a↦ →t].

− (r′r)[a := t] ≡ (r′[a := t])(r[a := t]) provided level(r′) = 1.

− (r′r)[a := t] ≡r′[a := t]r provided ∆⊢a#r.

− (r′r)[a := t] ≡ (r′r)[a↦ →t] if ∆⊬a#r and level(r′) = 2.

− (λb.r)[a := t] ≡λb.(r[a := t]) provided ∆⊢b#t.

− (λb.r)[a := t] ≡ (λc.((b c) · r)[a := t]) if ∆⊬b#t. Here c is the first atom not mentioned in r, a, b, or t, such that ∆⊢c#r and ∆⊢c#t, if such a c exists. Thus we α-convert the level 1 λb to a fresh λc, but in the presence of level 2 variables we use an explicit permutation and explicitly fresh level 1 variable, in nominal terms style.

− (λb.r)[a := t] ≡ (λb.r)[a↦ →t] otherwise.

− (λX.r)[a := t] ≡λX.(r[a := t]), renaming X if needed so that X ∉t.

Then for that ∆, let r∗ be defined as follows; earlier rules have priority, read left-to-right then top-to-bottom (∆ will always be clear from the context):

a∗ ≡ a (π · X)∗ ≡ π · X (λa.r)∗ ≡ λa.r∗ (λX.r)∗ ≡ λX.r∗ (X ∉ ∆) (r′[a ↦→ t])∗ ≡ r′∗[a := t∗] ((λX.r)t)∗ ≡ r∗[X := t∗] (r′r)∗ ≡ r′∗r∗

We can always rename X to ensure X ∉∆.

− If ∆ = {a#X} then X[a := b] ≡ X and (X[a := b])∗ ≡ X. − If ∆ = ∅ then X[a := b] ≡ X[a ↦→ b].

Intuitively, r∗ is a canonical form of r, and r[a := t] is a canonical form of r[a↦ → t]. This is not necessarily a normal form (which may not exist), but garbage is collected and substitutions (level 1 β-reducts) are pushed into r. Level 2 β-reducts are unreduced.

Definition 28

Call ∆⊢ - ▷ -

• reflexive when ∆⊢r ▷r always, and

• transitive when ∆⊢r ▷r′ and ∆⊢r′ ▷r′′ imply ∆⊢r ▷r′′.

Write ∆⊢ - ▷∗ - for the least transitive reflexive relation containing ∆⊢ - ▷ -.

Definition 29

Suppose that ∆ and ∆+ are freshness contexts. Say ∆+ freshly extends ∆ when there exists some ∆′ such that:

• ∆∩∆′ = ∅ (in words: ∆ and ∆′ are disjoint),

• ∆+ = ∆∪∆′,

• for all c#X ∈∆′ it is the case that c ∉∆, and for all c#X ∈∆′ it is the case that X ∈∆.

Intuitively, ∆+ ‘extends ∆ with some fresh atoms’.

Lemma 30

For every ∆, r, a, and t there exists a ∆+ freshly extending ∆ such that ∆+ ⊢r[a↦ →t] (level1)−→∗\overset{(level1)}{⟶}*r[a := t] (r[a := t] calculated for ∆+.)

Proof

Each rule in Definition 27 is emulated by a rule in (level1). We may need some fresh atoms to α-convert. □

Lemma 31

depth(r) = depth(r[X := π · Y])

Lemma 32

We have:

(i) (π · r)∗≡π · r∗

(ii) If (π · t)∗≡π · t∗ for all π, then (r[X := t])∗≡r∗[X := t∗]

Proof

By induction on depth(r), using Lemma 10 and Lemma 31. □

Theorem 33 states that terms reduce to their canonical form; it enters via Lemma 30 that we may need some fresh atoms, to α-convert.

Theorem 33

For every ∆ and r there exists a ∆+ freshly extending ∆ such that ∆+ ⊢ r(level1)−→∗\overset{(level1)}{⟶}*r∗ (r∗ calculated for ∆+.)

Proof

By induction on r. For example, a∗≡a and (λX.r)∗≡λX.r∗. The special case (λX.r)t requires Lemma 32, and the case (λa.r)t requires Lemma 30. □

Lemma 34

Fix ∆. Then ∆⊢a#s implies ∆⊢a#s∗. (s∗ calculated for ∆.)

Proof

By induction on derivations, using Lemma 32. □

Lemma 35

Suppose ∆⊢r(level1)−→\overset{(level1)}{⟶}s and also that ∆′ ⊢∆[X := π · X], then ∆′ ⊢r[X := π · X] (level1)−→\overset{(level1)}{⟶}s[X := π · X].

Proof

By induction on derivations, using Lemma 31, Lemma 20 and Lemma 9. □

Lemma 36

If ∆⊢r(level1)−→\overset{(level1)}{⟶}s then ∆⊢π · r(level1)−→\overset{(level1)}{⟶}π · s.

Proof

By induction on derivations, using Lemma 21 and Lemma 35. □

Theorem 37, along with Theorem 33 above, makes up the diagram in Theorem 38:

Theorem 37

For every ∆, r, and s, there exists a ∆+ freshly extending ∆ such that ∆⊢r(level1)−→\overset{(level1)}{⟶}s implies ∆+ ⊢s∗(level1)−→∗\overset{(level1)}{⟶}*r∗. (r∗ and s∗ calculated for ∆+.)

Proof

By induction on the derivation of ∆⊢r(level1)−→\overset{(level1)}{⟶}s. We sketch some cases:

− The case (β2app) where ∆⊢a#r. We use Lemma 34 to conclude that ∆+ ⊢ a#r∗ in the case where level(r′) = 1.

((r′r)[a↦→t])∗ ≡ (r′∗[a:=t∗])(r∗[a:=t∗]) ≡ (r′∗[a:=t∗])(r∗) if level (r′) = 1 ((r′r)[a↦→t])∗ ≡ (r′∗[a:=t∗])(r∗) if level (r′) = 2

− The case (β1app) where level(r′) = 1.

((r′[a↦ →t])(r[a↦ →t]))∗≡(r′∗[a := t∗])(r∗[a := t∗]) ≡((r′r)[a↦ →t])∗

− The case (βλ2). Suppose X ∉t, which can be guaranteed. Then ∆⊢ (λX.r)[a↦ → t] (level1)−→\overset{(level1)}{⟶}λX.(r[a↦ →t]). We have ((λX.r)[a↦ →t])∗≡λX.r∗[a := t∗] ≡ (λX.(r[a↦ → t]))∗, and we have the result.

− The case (▷α). Suppose s ≡ (a b) · s′. Suppose ∆⊢r →s′ and ∆⊢a#s′ and ∆⊢b#s′. By inductive hypothesis, ∆+ ⊢s′∗(level1)−→∗\overset{(level1)}{⟶}*r∗. By Lemma 34, ∆+ ⊢a#s′∗ and ∆+ ⊢b#s′∗. By Theorem 22 it follows that ∆+ ⊢a#r∗ and ∆+ ⊢b#r∗. By (▷α) it follows that ∆+ ⊢s′∗(level1)−→∗\overset{(level1)}{⟶}* (a b) · (r∗). By Lemmas 8 and 36 it follows that ∆+ ⊢ (a b) · (s′∗) (level1)−→∗\overset{(level1)}{⟶}*r∗. By Lemma 32, ∆+ ⊢s∗(level1)−→∗\overset{(level1)}{⟶}*r∗ as required.

□

Theorem 38

(level1) is confluent.

Proof

From the following diagram, using Theorem 33 and Theorem 37:

rs◀∗t∗-s∗∗ ?∗- r∗∗ ? ◀∗t∗∗ ?r →* s r →* t r →* r* s →* s* t →* t* s* →* r* t* →* r*

□

4.2 Level 2

Definition 39

Let (level2) be the set

{(β2), (βλ2)}

of rules from Figure 3. Let ∆⊢r(level2)−→\overset{(level2)}{⟶}s be the least congruence closed under the rules in (level2).

(Pa) ∆ ⊢ a ⇒ a (PX) ∆ ⊢ (π·X) ⇒ (π·X) ∆ ⊢ r ⇒ s ∆ ⊢ t ⇒ u (Papp) ∆ ⊢ rt ⇒ su ∆ ⊢ r ⇒ s ∆ ⊢ t ⇒ u ∆ ⊢ su R−→\overset{R}{⟶} v (Pappε) ∆ ⊢ rt ⇒ v ∆ ⊢ r ⇒ s (Pλa) ∆ ⊢ λa.r ⇒ λa.s ∆ ⊢ r ⇒ s (PλX) ∆ ⊢ λX.r ⇒ λX.s ∆ ⊢ r ⇒ s ∆ ⊢ a#s ∆ ⊢ b#s (Pα) ∆ ⊢ r ⇒ (a b) · s
Figure 4. The parallel reduction relation (Definition 40)

Note that (level1)−→\overset{(level1)}{⟶} and (level2)−→\overset{(level2)}{⟶} have (βλ2) in common. This is necessary for confluence to work, see Lemma 51.

Definition 40

Define a parallel reduction relation, ⇒, by the rules in Figure 4. Here, R ranges over rules in (level2) (Definition 39).

Lemma 41

∆⊢r ⇒s implies ∆⊢r(level2)−→∗\overset{(level2)}{⟶}*s.

As a corollary, ∆⊢r ⇒∗s implies ∆⊢r(level2)−→∗\overset{(level2)}{⟶}*s.

Lemma 42

∆⊢r(level2)−→\overset{(level2)}{⟶}s implies ∆⊢r ⇒s.

As a corollary, ∆⊢r(level2)−→∗\overset{(level2)}{⟶}*s implies ∆⊢r ⇒∗s

Proof

It suffices to show that every possible (level2)-reduction can be mirrored by a parallel reduction. This is routine. The second part follows from the first part and an easy proof that ∆⊢r ⇒r (⇒ is reflexive). □

Theorem 43

∆⊢r ⇒∗s if and only if ∆⊢r(level2)−→∗\overset{(level2)}{⟶}*s

Proof

From Lemmas 41 and 42. □

Lemma 44

If ∆⊢r(level2)−→\overset{(level2)}{⟶}s then ∆⊢π · r(level2)−→\overset{(level2)}{⟶}π · s.

Proof

By induction on derivations. We mention two cases:

− The case (▷α). By inductive hypothesis, we have ∆⊢π · r →π · s, and from Lemma 21, we have ∆⊢π(a)#π · s and ∆⊢π(b)#π · s. Using (▷α) we obtain ∆⊢ (π · r) → (π(a) π(b)) · (π · s) and the result follows via elementary properties of permutations.

− The case (β2). Using Lemma 7, we have:

π·((λX.r)t) ≡ (λX.π·r[X:=π-1·X])(π·t) → (π·r[X:=π-1·X])[X:=π·t] ≡ π·(r[X:=π-1·X][X:=π·t]) ≡ (π·r)[X:=t] ≡ π·(r[X:=t]) □
Lemma 45

If ∆⊢r⇒s and ∆′ ⊢∆[X:=π·X] then ∆′ ⊢r[X:=π·X]⇒s[X:=π·X].

Proof

By induction on derivations using Lemma 9, Lemma 20 and Theorem 24. □

Lemma 46

If ∆⊢r ⇒s then ∆⊢π · r ⇒π · s.

Proof

The proof is by induction on derivations. We present a selection of cases:

− The case (PλX). By inductive hypothesis, we have ∆⊢π · r ⇒π · s. From this and Lemma 45 we can obtain ∆⊢ (π · r)[X := π-1 · X] ⇒ (π · s)[X := π-1 · X].

Using (PλX), we have ∆⊢π · λX.r ⇒π · λX.s.

− The case (Pappε). By inductive hypothesis, we have ∆⊢π · r ⇒π · s and ∆⊢π · t ⇒π · u, and also ∆⊢ (π · s)(π · u) (level2)−→\overset{(level2)}{⟶}π · v, using Lemma 44. Then ∆⊢ (π · r)(π · t) ⇒π · v is derivable, and the result follows.

− The case (Pα). By inductive hypothesis, ∆⊢π · r ⇒π · s, and by Lemma 21, ∆⊢π(a)#π·s and ∆⊢π(b)#π·s. Then ∆⊢π·r ⇒ (π(a) π(b))·(π·s) is derivable and the result follows by elementary properties of permutations.□

Lemma 47

∆⊢r ⇒s and ∆⊢t ⇒u imply ∆⊢r[X := t] ⇒s[X := u].

Proof

The proof is by induction on the derivation of ∆⊢r ⇒s (Figure 4). We assume that ∆⊢t ⇒u.

− The case (PX). By Lemma 46, and by the fact that (π · Y)[X := t] ≡π · Y .

− The case (Pappε). Suppose ∆⊢r ⇒s, ∆⊢v ⇒w and ∆⊢sw(level2)−→\overset{(level2)}{⟶}v. Then ∆⊢r[X := t] ⇒s[X := u] and ∆⊢v[X := t] ⇒w[X := u] are both derivable, and from Theorem 24, we have ∆⊢s[X := u](w[X := u]) →v[X := u]. The result follows from (Pappε).

− The case (Pα). By inductive hypothesis, ∆⊢r[X := t] ⇒s[X := u], and by Lemma 20, ∆⊢a#s[X := u] and ∆⊢b#s[X := u]. Extending with (Pα), we obtain ∆⊢r[X := t] ⇒ (a b) · (s[X := t]). The result follows from Lemma 9.□

Write

‘∆⊢r ⇐s ⇒t’ for ‘∆⊢s ⇒r and ∆⊢s ⇒t’,

and similarly for other reduction relations later.

Lemma 48

∆⊢ - ⇒ - satisfies the diamond property: If ∆⊢r ⇐s ⇒t then there exists some u such that ∆⊢r ⇒u ⇐t.

Proof

We consider possible pairs of rules that can derive ∆⊢s ⇒r and ∆⊢ s ⇒t, where r ≢t. We present the case of (Papp) and (Pappε) for (β2). Suppose ∆⊢ (λX.r′)t′ ⇐ (λX.r)t ⇒r′′[X := t′′] using (Papp), and (Pappε) for (β2). By inductive hypothesis, there exists an r′′′ such that ∆⊢r′ ⇒r′′′ ⇐r′′ and a t′′′ such that ∆⊢t′ ⇒t′′′ ⇐t′′. Using Lemma 47 we derive ∆⊢ (λX.r′)t′ ⇒r′′′[X := t′′′] ⇐r′′[X := t′′]. □

Theorem 49

(level2)−→\overset{(level2)}{⟶} is confluent.

Proof

An immediate corollary of Theorem 43 and Lemma 48. □

4.3 Level 1 and level 2 reductions

Lemma 50

∆⊢r →s implies level(s) ≤ level(r), and so does ∆⊢r ⇒s.

Lemma 51

∆⊢r ⇐s(level1)−→\overset{(level1)}{⟶}t implies that ∆⊢r(level1)−→∗\overset{(level1)}{⟶}*u ⇐t. As a corollary,

∆⊢r ⇐s(level1)−→∗\overset{(level1)}{⟶}*t implies ∆⊢r(level1)−→∗\overset{(level1)}{⟶}*u ⇐t.

Proof

We assume ∆⊢u ⇒u′, ∆⊢t ⇒t′, and so on. We present some cases:

−∆⊢ (r′′′r′′)[a↦ →t′] ⇐ (r′r)[a↦ →t] → (r′[a↦ →t])(r[a↦ →t]) when level(r′) = 1.

This can be closed to (r′′′[a↦ →t′])(r′′[a↦ →t′]); by Lemma 50 level(r′′′) = 1.

−∆⊢ (r′′′r′′)[a↦ →t′] ⇐ (r′r)[a↦ →t] → (r′[a↦ →t])r when ∆⊢a#r.

This can be closed to (r′′′[a↦ →t′])r′′.

−∆⊢ ((λX.r′)t′)[b↦ →u′] ⇐ ((λX.r)t)[b↦ →u] → ((λX.r)[b↦ →u])t when ∆⊢b#t.

This can be closed to ((λX.r′)[b↦ →u′])t′.

−∆⊢r′[X := t′][b↦ →u′] ⇐ ((λX.r)t)[b↦ →u] → ((λX.r)[b↦ →u])t when ∆⊢b#t.

This can be closed to r′[X := t′][b↦ →u′] where X ∉u which can be guaranteed; we require (βλ2) in (level2).

□

Lemma 52

If ∆⊢r(level1) ←−\overset{(level1)}{⟵} s →∗t, then ∆+ ⊢r →∗u ←−⟵t for some suitably freshened context, ∆+. Similarly, if ∆⊢r(level2) ←−\overset{(level2)}{⟵} s →∗t, then ∆+ ⊢r →∗u ←−⟵t for some suitable freshened context ∆+.

Proof

Both claims follow by induction on the path length of ∆⊢s →∗t using Theorem 38, Theorem 49 and Lemma 51. □

Theorem 53

∆⊢ - → - (reduction with (level2) ∪ (level1)) is confluent, in the following sense: if ∆⊢s →∗r and ∆⊢s →∗t then there exists some ∆+ freshly extending ∆, and some u, such that ∆+ ⊢r →∗u and ∆+ ⊢t →∗u.

Proof

By a diagrammatic argument, using Lemma 52. □

The ‘freshly extending’ part of Theorem 53 ensures we can α-rename λa with a permutation to guarantee the freshness precondition of (βλ1). In the presence of only a single level of variable we can ‘just rename’, and so we do not need to record the freshness of freshly generated variables relative to higher-level variables in a freshness context.

Recall Definition 28. Call ∆⊢ - ▷ - symmetric when ∆⊢r ▷r′ implies ∆⊢r′ ▷r. Write ∆⊢ - = - for the least congruence closed under ∆⊢ - → - that is also transitive, reflexive, and symmetric.

Corollary 54

∆⊢ - = - is consistent. (There exist two terms which are not related by the transitive reflexive symmetric closure of ∆⊢ - → -.)

Proof

λa.λb.a and λa.λb.b are two distinct terms, and they do not rewrite to a common term. By Theorem 53 the result follows. □

5 Related and future work

Previous ‘nominal’ λ-calculi.

The NEW calculus of contexts and the lambda-context calculus [9,11] are λ-calculi with more than one level of variable. These have a weak theory of α-equivalence which is less powerful than that of nominal terms. There are no permutations and it is not possible to α-rename a in λa.X, where a has level 1 and X has level 2. This problem carries through to the theory of reduction since β-reductions can get stuck due to lack of α-equivalence. For example, (λa.X)[b↦ →a]a cannot reduce because we cannot α-convert λa to λc for a fresh c. (A similar observation goes back at least to [5].)

The NEW calculus of contexts and the lambda-context calculus retain some unique features not subsumed by this paper. They have an infinite hierarchy of levels and, arguably, are closer to the λ-calculus (precisely because their syntax does not include permutations). It is future work to combine β-conversion for more than two levels of variable with the notion of reduction with nominal terms style α-equivalence appearing in this paper.

The lambda-context calculus preserves strong normalisation. A variant of two-level λ-calculus which preserves strong normalisation is possible using ideas from [11]. The proof of confluence is not harder. The result in this paper is more relevant for designing logics, where we trade off more reductions against weaker computational properties.

Capture-avoiding substitution as a nominal algebra with Mathijssen [12,18] used nominal terms syntax, with permutations and freshness; substitution corresponds to level 1 β-reductions. There is no level 2 λ-abstraction λX.

λ-calculi for capturing substitution.

The λ-calculus itself can emulate capturing substitution. Let r and t range over λ-terms: then the quote in the Introduction is emulated by

‘apply λx.((λy.r)(yx)) to λx.t’.

However, compositionality fails in the sense that the number of ‘extra’ λ-abstractions needed on t, and ‘extra’ applications needed on y, depend non-locally on the variables for which we authorise capture at the point(s) at which y occurs in r. See [26, Section 2] for further discussion.

λ-calculi exist with more than one level of variable, or with constructions with essentially the same intent. We mentioned several in the Introduction.

Jojgov and Geuvers. Jojgov and Geuvers [20] study incomplete derivations in higher-order logic. They create o-HOL, which conservatively extends HOL with ‘open’ terms and ‘open’ (incomplete) proofs. ‘Meta-variables’ (level 2 variables in our terminology) are represented in o-HOL syntax. Their treatment of α-conversion is not nominal, but neither is it ‘traditional’. The definition of meta-variable instantiation on page 546 (page 10 of the paper, just after Definition 11) in simplified form reads:

n\underline{n}[q]{n\underline{n}[y] := t} = t[q/y]

Here n\underline{n} is a meta-variable symbol (level 2 variable), q and t are terms, and y is a(n ordinary, level 1) variable. Meta-variable symbols are always associated either with a (list of) variable(s) y or a (list of) term(s) q. By this rather ingenious device Jojgov and Geuvers seem to manage α-equivalence in the presence of two levels of variable. n\underline{n}[q] seems to correspond with what we might write ‘X[- ↦→q]’ and the meta-variable instantiation {n\underline{n}[y] := t} seems to correspond with what we might write ‘[y↦ → -][X := t]’.

Establishing the precise technical relationship between our term language and that of Jojgov and Geuvers might be the topic of future work (though the approach of Jojgov and Geuvers has not been under development for some time). However, our syntax seems to be simpler and more atomic. Level 2 variables exist ‘as is’ (not annotated by suspended substitutions). In our system level 1 substitution is managed very simply by level 1 β-reducts, whereas Jojgov and Geuvers have two copies of level 1 substitution; level 1 β-reducts and the variable-and-term annotations on the meta-variables.

Pfenning et al. A thread of research exemplified by [26] manages capturing vs. non-capturing substitution inside a specially-designed logical framework. Our calculus uses levels; there is no (need for a) ‘wrapping’ in formal logic and the meaning of a term is contained in the term itself, rather than in the term and its interaction with the ‘wrapping’ logical framework. Also, our level 2 variables are ‘open’ (instantiation captures unless a freshness condition forbids it) whereas context variables in [26] are ‘closed’ (variables that can be captured must be accounted for, in the type system).

Sato et al. Sato et al have investigated calculi with meta-variables. Their calculi are very similar to the lambda-context calculus but forbid β-reduction if terms contain variables that are ‘too strong’. In particular (λa.(Z′Z))Y will not β-reduce in their system [28, Subsection 3.3]. For better or for worse, this is a clearly weaker notion of reduction (there are fewer reductions) than two-level lambda-calculus (it is also weaker than the notion of reduction of the lambda-context calculus).

We also mention work by Hashimoto and Ohori [21], which annotates level 2 variables with ‘variable renamers’ similar to our permutations, and work by Lee and Friedman [5] which is more like a full meta-programming system but with an emphasis on meta-variables.

Our two-level λ-calculus is specifically tailored to nominal terms and so fits into our broader research programme. The syntax is relatively simple, and we may well be able to to import other nominal research, from semantics [19,10] to implementation [30]. Thus, we have not yet built semantics or a type system for two-level λ-calculus, but tools exist to do this in a principled way [10,6].

Future work.

The complexity of presentation of the two-level lambda-calculus compares reasonably favourably with that of the systems we find by other authors in the existing literature, for example [25,21,20]. We may be able to simplify the presentation futher, this is future work.

We intend to impose types and create a higher-order logic, as outlined in the Introduction. A discussion will follow once the logic is created. Nominal unification, nominal algebra, and one-and-a-halfth order logic [29,24,17] have already done much of the work but the universal quantification of level 2 variables (unknowns) X is implicit (there is no λX or ∀X). Denotations, presumably using nominal sets [19], are future work. We can also consider enriching our functional operational semantics with nominal unification, which is computationally more tractable than higher-order unification [29].

A word on terminology

We have created several multi-level systems: nominal terms [29], hierarchical nominal rewriting [7], the NEW calculus of contexts [9] and the lambda-context calculus [11], one-and-a-halfth-order logic [15] and nominal algebra [14,24]. They all have a capturing substitution but differ in complexity, scale, and detail. We need a taxonomy to describe them.

We have used ‘-and-a-halfth order’, as in ‘one-and-a-halfth order logic’ [17] or ‘two-and-a-halfth order lambda-calculus’ [16]. We have found that this sometimes causes confusion because ‘order’ is usually associated with types. Levels can be viewed as a sort system, but they are not types in the sense of simple type theory [4] (for example, in the two-level lambda-calculus X and a have different levels but can be substituted for exactly the same terms, namely, any terms at all).

In this paper we propose and use the following terminology:

• One level system. Examples include the typed and untyped lambda-calculus, and first- and higher-order logic.

• One-and-a-half level system. Two levels of variable, abstraction only for level 1 (not for level 2; i.e. a, λa, and X, but no λX). Examples include nominal terms, nominal unification, nominal rewriting, nominal algebra, and one-and-a-halfth order logic (which we would now call one-and-a-half level logic).

• Two level system. Two levels of variable, abstraction for both. The calculus in this paper is a two level lambda-calculus with a nominal terms style theory of level 1 alpha-equivalence (until now, we would call it ‘two-and-a-halfth order lambda-calculus’; now we call it the ‘two-level lambda-calculus’).

• Multi-level system. An infinity of levels with abstraction for all levels. Examples include hierarchical nominal rewriting, the NEW calculus of contexts, and the lambda-context calculus. See [11,9] for accounts of how having more than two levels of variable can be useful.

References

[1] Mirna Bognar. Contexts in Lambda Calculus. PhD thesis, Vrije Universiteit Amsterdam, 2002.

[2] James Cheney. Nominal logic and abstract syntax. SIGACT News (logic column 14), 36(4):47– 69, 2005.

[3] James Cheney and Christian Urban. αProlog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proc. of the 20th Int’l Conf. on Logic Programming (ICLP 2004), number 3132 in LNCS, pages 269–283. Springer-Verlag, 2004.

[4] Alonzo Church. A formulation of the Simple Theory of Types. Journal of Symbolic Logic, 5(2):56–68, 1942.

[5] Shinn-Der Lee and Daniel P. Friedman. Enriching the lambda calculus with contexts: toward a theory of incremental program construction. In ICFP ’96: Proceedings of the first ACM SIGPLAN international conference on functional programming, pages 239–250, 1996.

[6] Maribel Fernández and Murdoch J. Gabbay. Curry-style types for nominal terms. In Types for Proofs and Programs, volume 4502/2007 of LNCS, pages 125–139, 2006.

[7] Murdoch J. Gabbay. Hierarchical nominal rewriting. In LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice, pages 32–47, 2006.

[8] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205(6):917–965, 2007.

[9] Murdoch J. Gabbay. A NEW calculus of contexts. In PPDP’05, pages 94–105. ACM, 2005.

[10] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205:982–1011, July 2007.

[11] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. ENTCS, 196:19–35, 2008.

[12] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC, volume 4281 of LNCS, pages 198–212, 2006.

[13] Murdoch J. Gabbay and Dominic P. Mulligan. One-and-a-halfth order terms: Curry-Howard for incomplete derivations. In WoLLIC ’08: International Workshop on Logic, Language, Information and Computation, volume 5110 of LNAI, pages 180–194, 2008.

[14] Murdoch J. Gabbay and Aad Mathijssen. A formal calculus for informal equality with binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of LNCS, pages 162–176, 2007.

[15] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth order Logic. In PPDP ’06: Proceedings of the 8th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pages 189–200, 2006.

[16] Murdoch J. Gabbay and Dominic P. Mulligan. Two-and-a-halfth order lambda-calulus. In WFLP ’08: 17th International Workshop on Functional and (Constraint) Logic Programming, preliminary proceedings, pages 107–121, 2008.

[17] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic (journal version). Journal of Logic and Computation, November 2007. Online.

[18] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra (journal version). Formal Aspects of Computing, 2008. Online.

[19] Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341–363, 2001.

[20] Herman Geuvers and Gueorgui I. Jojgov. Open proofs and open terms. In CSL ’02: Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, pages 537–552, 2002.

[21] Masatomo Hashimoto and Atsushi Ohori. A typed context calculus. Theoretical Computer Science, 266(1-2):249–272, 2001.

[22] Gueorgui I. Jojgov. Holes with binding power. In Types for Proofs and Programs, volume 2646 of LNCS, pages 162–181. Springer, 2002.

[23] Stefan Kahrs. Context rewriting. In CTRS ’92: 3rd International Workshop on Conditional Term Rewriting Systems, volume 656 of LNCS, pages 21–35, 1992.

[24] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.

[25] César Muñoz. A Calculus of Explicit Substitutions for Incomplete Proof Representation in Type Theory. PhD thesis, INRIA Rocqencourt, Projet Coq, 1997.

[26] Aleksandar Nanevski, Frank Pfenning, and Brigitte Pientka. Contextual modal type theory. Transactions on Computational Logic, 2007.

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

[28] Masahiko Sato, Takafumi Sakurai, Yukiyoshi Kameyama, and Atsushi Igarashi. Calculi of meta-variables. In CSL, volume 2803 of LNCS, pages 484–497, 2003.

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

[30] Christian Urban and Christine Tasson. Nominal techniques in Isabelle/HOL. In CADE ’05: Proceedings of the 20th International Conference on Automated Deduction, volume 3632 of Lecture Notes in Artificial Intelligence, pages 38–53, 2005.

[31] Johan van Benthem. Higher-order logic. In Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 189–244. Kluwer, 2001.

Notes

1 a and b are meta-variables ranging permutatively over level 1 variables. X and Y are meta-variables ranging permutatively over level 2 variables. However, we will probably just call a a level 1 variable, and X a level 2 variable, just as we may later call r a term when in fact it is a meta-variable ranging over terms (Definition 4). ↩

2 Thanks to Stéphane Lengrand for helping develop this pithy example. ↩

3 This is not necessary for expressing the proofs to follow but it is convenient. We will never make infinitely many choices of fresh atom, and nowhere will the truth of a result depend on our choice of order. ↩