The lambda-context calculus
Abstract
We present a simple lambda-calculus whose syntax is populated by variables which behave like meta-variables. It can express both capture-avoiding and capturing substitution (instantiation). To do this requires several innovations, including a key insight in the confluence proof and a set of reduction rules which manages the complexity of a calculus of contexts over the ‘vanilla’ lambda-calculus in a very simple and modular way. This calculus remains extremely close in look and feel to a standard lambda-calculus with explicit substitutions, and good properties of the lambda-calculus are preserved. These include a Hindley-Milner type system with principal typings and subject reduction, and an applicative characterisation of contextual equivalence.
Key words: Lambda-calculus, calculi of contexts, functional programming, binders, nominal techniques, explicit substitutions, capturing substitution.
Email address: Murdoch.Gabbay@gmail.com, sl@cs.st-andrews.ac.uk (Murdoch J. Gabbay Stéphane Lengrand).
Preprint submitted to Information and Computation 6 June 2007
Contents
1 Introduction 3
2 Syntax, freshness, reductions 5
2.1 Syntax 5
2.2 Levels and Free variables 6
2.3 -equivalence 6
2.4 Reductions 9
2.5 Example reductions 11
2.6 Comments on the side-conditions 13
3 The substitution action 15
3.1 Termination of (sigma) 15
3.2 Calculating (sigma)-normal forms 17
4 Confluence 18
4.1 Confluence of (sigma) 19
4.2 (beta)-reduction 24
4.3 Combining (sigma) and (beta) 26
5 The untyped lambda-calculus 28
6 A NEW part for the LCC 31
6.1 Some NEW rules 31
6.2 Some false NEW rules 33
7 Hindley-Milner types 34
8 Applicative characterisation of contextual equivalence 40
8.1 Programs, contexts, evaluations, and equivalences 40
8.2 Proof that equals 41
9 Related work, conclusions, and future work 44
References 48
1 Introduction
This is a paper about a -calculus for contexts. A context is a term with a ‘hole’. The canonical example is probably - in the -calculus. This is not -calculus syntax because it has a hole -, but if we fill that hole with a term then we obtain something, we usually write it [], which is a -calculus term.
For example if - then [ and [. This cannot be modelled by a combination of -abstraction and application, because -reduction avoids capture. Formally: there is no -term such that The term is the obvious candidate, but ().
(We shall use ‘=’ to denote -equality of terms.)
Contexts arise often in proofs of meta-properties in functional programming. They have been substantially investigated in papers by Pitts on contextual equivalence between terms in -calculi (with global state) [24,27]. This work was about proving programs equivalent in all contexts — contextual equivalence. The idea is that two programs, represented by possibly-open -terms, are equivalent when one can be exchanged for another in code. That code might have binders which bind variables in the scope of the ‘hole’ within which we are substituting, whence the need for binders.
This suggests that we should call holes context variables (distinct from ‘normal’ variables ) and allow -abstraction over them to obtain a -calculus of contexts, so that we can study program contexts with the full panoply of vocabulary, and hopefully with many of the theorems, of the -calculus. For example - may be represented by . Substitution for does not avoid capture with respect to ‘ordinary’ -abstraction, so () reduces to .
A context calculus can have applications besides aspects of proofs of contextual equivalence.
Consider formalising mathematics in a logical framework based on Higher-Order Logic (HOL) [37]. Typically we have a goal and some assumptions and we want a derivation of one from the other. This derivation may be represented by a -term (the Curry-Howard correspondence). But the derivation is arrived at by stages in which it is incomplete.
To the right are two derivations of . The bottom one is complete, the top one is incomplete. 1 An issue arises because the right-most [] in the bottom (complete) derivation is discharged, which means that we have to be able to instantiate ? in a sub-derivation for an assumption which will be discharged. Discharge corresponds in the Curry-Howard correspondence precisely to -abstraction, and this instantiation corresponds to capturing substitution. Similar issues arise with existential variables [14, Section 2, Example 3].
The central issue for any calculus of contexts is the interaction of context variables with -equivalence. Let be ‘ordinary’ variables and let be a context variable. If then (), giving non-confluent reductions. Dropping -equivalence entirely is too drastic; we need to be -convertible with so that we can reduce a term such as ().
Solutions include clever control of substitution and evaluation order [30], types to prevent ‘bad’ -conversions [28,16,29], explicit labels on meta-variables [14,18], and more [4, Section 2]. More on this in the Conclusions.
In this paper we present a new calculus of contexts, the ‘lambda context calculus’ (LCC). We took our technical ideas for handling -equivalence not from the literature on context calculi cited above, but from nominal unification [36]. This was designed to manage -equivalence in the presence of holes, in unification — ‘unification of contexts of syntax’, in other words. Crudely put, we obtained the LCC by allowing -abstraction over the holes and adding -reduction.
This work has similar goals to the N EWcc previously developed by the first author [9]. The LCC has a simpler and more intuitive set of reduction rules. Indeed there is now only one non-obvious side-condition, it is on (p); Technical aspects of the previous work have been simplified, clarified, or eliminated altogether. Notably we dispense entirely with the freshness contexts and freshness logic of the N EWcc.
The result is a clean and simple system with a powerful hierarchy of context variables, yet which has the look and feel of an ordinary -calculus with explicit substitutions, along with many of the properties which make the -calculus so nice to work with. These include confluence, a Hindley-Milner type system with principal typings and subject reduction, and an applicative characterisation of contextual equivalence.
1 This example ‘borrowed’ from [14].↩
2 Syntax, freshness, reductions
2.1 Syntax
We suppose a countably infinite set of disjoint infinite sets of variables , , . . . , where we write for 1.
We shall use a permutative naming convention; we shall always assume that variables that we give different names, are different. Thus and range permutatively over elements of . In particular, when we write and we do not assume (unless stated otherwise) that , but we do assume that even if , and are different variables, because we have given them different names.
There is no particular connection between variables of different levels with the same name. For example and are different variables to which we happen to have given similar names.
The syntax of the lambda context calculus (LCC) is given by:
We use the following conventions:
As is standard, application associates to the left. For example is ().
We say that the variable has level .
We call stronger than when , that is, when has higher level than . If we call weaker than . If we say that and have the same strength.
We call [] an explicit substitution of level (for the atom , acting on ).
We call an abstraction of level (over the term ).
Later on we shall use the convention that are variables of level 1, are variables of level 2, and has level 3.
This syntax has no constant symbols. We might like to have constants like 1, 2, 3, . . . for arithmetic, or and for truth-values. These behave much like variables ‘of level 0’ which we do not abstract over and for which we do not substitute. We may add them where convenient for illustrative examples. Adding them formally to the syntax causes no particular difficulties aside from adding extra cases to a few proofs.
2.2 Levels and Free variables
Here max() is the greater of and , and max() is the greatest of , , and .
For the reader’s convenience we mention now that we write ‘level() ’ as shorthand for ‘level() and . . . and level() ’, similarly for ‘level() ’; this will be useful later.
If level( then fv() coincides with the usual notion of ‘free variables of’ for the untyped -calculus, if we read [] as ().
We shall see that the operational behaviour of such terms is the same as well.
2.3 -equivalence
A congruence on LCC terms is a binary relation satisfying the conditions of Figure 3.
It is easy to show that a congruence is reflexive, so perhaps a better name would be ‘congruent equivalence relation’ — but ‘congruence’ is shorter so we use that.
Define an (atoms) swapping () action inductively by the rules in Figure 4.
Note that the definition of the swapping action is absolutely uniform, literally
swapping and in without regard to binders et cetera. This is very characteristic of the underlying ‘nominal’ method of this paper [13,36].
We will use swapping () on sets of variables acting pointwise by
Here ranges over all elements of , including and (if they are in ).
fv(())fv and level(() level
By easy inductions on the definition of (). 2
If is a set of variables write # for
, and
there exists no variable such that .
If level
We work by induction on the definition of level
The case of . level(. So suppose that . It follows from the definition of fv that #fv
The case of . level( level
The case of . level( max( level()), so . fv() fv The result follows by the inductive hypothesis.
The case of [] is similar.
2
Let -equivalence be the least congruence relation satisfying the conditions of Figure 5.
Suppose that and have level 1 and has level 2. We can easily verify that:
may be -converted in if level
may be -converted in [] if level() . In particular [ [].
It is not possible to -convert in if fv() for . For example . This is consistent with a reading of strong variables as unknown terms with respect to weaker variables.
We can never -convert variables to variables of other levels.
If mentions only variables of level 1, then -equivalence collapses to the usual -equivalence on untyped -terms (plus an explicit substitution).
Parenthetical note: The definitions above are descended from the notion of -equivalence for nominal terms from [36]. In the terminology used here, that paper considered a syntax with a hierarchy with just levels 1 and 2 and no abstraction over variables of level 2. However LCC is weaker in the sense that nominal terms include swappings in the syntax of terms. We use swappings as an operation on LCC syntax (Definition 5) but we have not included them in the syntax of the LCC itself.
Extending LCC syntax with swappings is future work. To do that it would help to have a better understanding of LCC models (this paper is purely syntactic) and of freshness #. Another paper does explore the notion of freshness in the presence of a hierarchy [10].
If then fv( fv and level( level
The proof is by an easy induction on the derivation rule defining a congruence. We give only the base cases:
If #fv() then fv( fv(()).
Suppose level() . By Lemma 6 level(()) as well. Then using Lemma 6 we have
It follows by easy set calculations that
We also observe that swapping and in has no effect on the levels of the variables occurring in , and it follows easily that
If #fv() then fv([ fv((())[]). Note that
We use the previous part.
2
Theorem 11 guarantees that we can -convert without changing the levels or sets of free variables. We use these facts (especially in the proof of confluence when we write ‘renaming if necessary’) without comment henceforth.
2.4 Reductions
Define the reduction relation on terms (modulo -equivalence) inductively by the rules in Figure 6.
In that figure consistent with our conventions variables with different names are assumed distinct. For example in () we assume that and are distinct.
We shall use the following notation:
We write for the transitive reflexive closure of .
We write when there exists no such that . If we call a normal form, as is standard.
We write when we can deduce but using only rules in (ruleset) where
(Later in Section 6 we extend reduction with rules for a binder .)
We call terminating when there is no infinite sequences
Similarly for .
We call confluent when if and then there exists some such that and . Similarly for (ruleset).
We take a moment to note two easy but important technical properties: reductions decrease the level of a term, and its set of free variables.
If then level
By a series of easy calculations on the rules in Figure 6 and an inductive argument. 2
If then fv
We work by induction on the derivation of . The base cases are:
fv([fv
fv([ fv() and fv() is a subset of itself.
Suppose that #fv(). By definition
From Lemma 8 we deduce that fv
Suppose that level() . Then
The subset inclusion follows by easy calculations on sets.
Other cases are no harder. The inductive argument is straightforward, relying on Lemma 13. The corollary is immediate. 2
2.5 Example reductions
The LCC is a -calculus with explicit substitutions [20]. The general form of the -rules is familiar from the literature though the conditions, especially those involving levels, are not; we discuss them in Subsection 2.6 below.
First, we consider some example reductions. Recall our convention that we write for variables of level 1, and for variables of level 2.
-reduction. This is a standard -reduction rule for a calculus with explicit substitutions:
Substitutions on variables. The behaviour of a substitution on a variable depends on the relative strengths of the variable being substituted on, and the variable being substituted for:
We can summarise the behaviour of substitutions on variables as follows:
A strong substitution acting on a weak variable ‘evaporates’.
A substitution of a variable acting on itself acts ‘normally’.
A substitution of a variable acting on another variable of the same strength ‘evaporates’.
A weak substitution on a strong variable ‘stays put’.
Traversing weak variables.
An explicit substitution for a relatively strong variable may distribute using () under an explicit substitution for a relatively weaker variable, without avoiding capture:
Similarly, an explicit substitutions for a relatively strong variable can traverse a -abstraction by a relatively weaker variable, using (), without avoiding capture:
This makes strong variables behave like ‘holes’. Instantiation of holes is compatible with -reduction; here is a typical example:
Substitutions on no weaker substitutions. These terms do not reduce:
Here (a) and (fv) are not applicable because has level 2 and has level 1, and () is not applicable because both and have level 1. So weak substitutions are ‘suspended’ — until a stronger substitution turns into something with internal structure which they can act on.
We imagine stronger versions of the LCC (i.e. with more reductions) in the Conclusions.
Substitutions for stronger terms There is no restriction in [] that level() or level() ; for example the terms [] and [] are
legal (recall that has level 3).
Terms like [] are useful. Examples ‘in nature’ appear in the -introduction rule in logic
where it is understood that and are meta-variables — and in the -reduction rule
where it is understood that and are meta-variables.
A term such as [] is useful if there is a surrounding binder which we would like to conveniently link to. For example in the term ([]) can be bound to by a substitution arriving from some enclosing context:
Substitutions as terms [] is not a term; it cannot be the argument to a function. However [] is a term, and it acts like a substitution in the following sense:
As a general scheme, [] encodes the substitution [] if level
2.6 Comments on the side-conditions
The side-conditions of the LCC reduction rules are where much of the technical ‘magic’ happens.
(fv) is a form of garbage-collection. We do not want to garbage-collect [2] in [2] because () could turn into something with free
— for example itself. This is why the side-condition is not fv(). For example fv( and so with a false version of the rule with a side-condition using
instead of # we have reductions
This is blocked in LCC, because # does not hold.
It is unusual for a garbage collection rule to appear in a calculus of explicit substitutions; usually we can ‘push substitutions into a term until they reach variables’ so we make do with a rule of the form [] . In the LCC we cannot always push substitutions into a term until they reach variables, because of the conditions on (p) and (). A version of (fv) does appear in the literature as Bloo’s ‘garbage collection’ [3].
Recall that the level of a term is the level of the strongest variable it contains, free or bound. Recall also that the side-condition level() in (p) means that level
This condition seems to be fundamental for confluence to work; we have not been able to sensibly weaken it, even if we also change other rules to fix what goes wrong when we do. Here is what happens if we drop the side-condition entirely:
The term ()[] does not reduce (more on that in the Conclusions).
The side-conditions on (), (), and () implement that a relatively strong substitution can capture but substitution for variables of the same level avoids capture.
There is no rule
since that would destroy termination of the part of the LCC without — and we have managed to get confluence without it.
There is no rule permitting a weak substitution to propagate under a stronger abstraction, even if we avoid capture:
Such a rule would cause the following problem for confluence:
Neither of these terms reduces further.
As is the case for the side-condition of (p), any stronger form of () seems to provoke a cascade of changes which make the calculus more complex.
Investigation of these side-conditions is linked to strengthening the theory of freshness and -equivalence, and possibly to developing a good semantic theory to guide us. This is future work and some details are mentioned in the Conclusions.
3 The substitution action
Let (sigma) be equal to the set of rewrite rules other than , namely,
This is the part of the LCC that handles substitution — the ‘-free’ part of the calculus.
We expect the -free part of other calculi of explicit substitutions to be terminating [3,20] and this is useful behaviour — but now we have a hierarchy of variables. Do we lose this good behaviour? No, and in this section we prove it.
3.1 Termination of (sigma)
We show that (sigma)-reduction decreases terms with respect to a well-founded ordering based on mapping LCC terms to first-order terms (no variables, no binders), and using a lexicographic path ordering [19,1] on them.
We use first-order terms in the following infinite signature:
Here indicates that has arity . Symbols have the following precedence:
We define the lexicographic path ordering by:
Here and are first-order symbols and are first-order terms.
It is a fact [19,1] that is a well-founded order on first-order terms satisfying the subterm property, i.e. if is a subterm of then .
We define a translation from LCC to first-order terms as follows:
If then .
We check for each reduction rule that the corresponding first-order term on the left, is higher in the lexicographic path ordering than the one on the right. This is routine:
2
(sigma)-reduction terminates.
We can now make a useful observation. Let have level 1. It is easy to show that ()() has an infinite series of reductions if we allow rules in (sigma) and . It follows that — even with a hierarchy of variables — strictly adds to the power of the reduction system.
Call (sigma)-normal when .
By Corollary 17, any chain of (sigma)-reductions must terminate, and by definition it terminates at a (sigma)-normal form.
What does that (sigma)-normal form look like?
3.2 Calculating (sigma)-normal forms
Define a substitution action [] by the equalities in Figure 7.
The precedence of which equality in Figure 7 to use is from top to bottom. Also, when we try to apply the equality ()[([]) we rename where possible to satisfy the side condition #fv
[] [].
By induction on and then . We inspect the definition of := and see that each clause can be imitated by a rule for []. 2
If and are (sigma)-normal then [] is (sigma)-normal.
By induction on and then . 2
Define inductively by the rules in Figure 8.
is a (sigma)-normal form of .
4 Confluence
Recall from Definition 15 that (sigma) is the set of rules defined by
It is convenient to define:
Let (beta) be the set () () (fv).
Note that (sigma) (beta) is equal to the set of all reduction rules of the LCC.
Note that (sigma) (beta) is non-empty. We mention the technical reasons for this just after Lemma 39 — it seems to be vital for the proofs to work. Understanding the deeper mathematical reasons for this, if any, is future work.
is confluent. That is, if and then there is some such that and .
The proof of Theorem 25 occupies this section. Before we give the details we comment on the overall design of the proof.
Roughly speaking there are two standard ways to prove confluence:
(1) Define a so-called parallel reduction relation . such that and .
It then suffices to show that if and then there is some such that and .
(An example of the method is in Subsection 4.2.)
(2) Define for each term a normal form such that and then prove that for all possible reductions it is the case that .
Both of these methods are standard [33]. But which to use for the LCC?
It seems that reductions using ‘want’ method 1 above — but (sigma)-reductions ‘want’ method 2. To prove confluence of the LCC, we split the reduction relation into (sigma) and (beta); we prove confluence results by methods 1 and 2 above independently, and then we combine them.
4.1 Confluence of (sigma)
Lemmas 27 and 29 will be useful; Lemma 27 in this subsection and Lemma 29 in Subsection 4.3. Since these results are closely related so we have put them side-by-side here.
We need this technical lemma in a moment:
If level
By Lemma 8 if level() then #fv(). The result follows from the definition of []. 2
If then
(Note the lack of capture-avoidance condition; this is because .)
By induction on and then on the structure of .
Suppose [[]. We then have
This covers the cases with , with level() , [] with , with , or without #fv
Suppose . Note that by our permutative convention, is distinct
from . Then:
The cases of [][] and [][] are easy.
Suppose that level() . By Lemma 20 we have ()[] ()[]. By Lemma 13 we have
Finally by Lemma 26 we have
Suppose . Then
Suppose . Then
Suppose (renaming where possible) that #fv(). Then
2
We need a technical lemma for Lemma 29:
If s is (sigma)-normal and level
By a routine induction on . 2
Suppose that level() and #fv (which in view of the condition on levels, means just fv). Suppose also that , , and are (sigma)-normal. Then
By induction on the structure of .
Suppose . Recall that by our permutative convention is distinct from and . Then:
The cases of [][] and [][] are easy.
We do not need to consider the case [][] for , because then
For the case of [], assumed to be be (sigma)-normal, we know from the assumption level([]) and Lemma 28 that . Hence,
Suppose . Since level() we can rename so that #fv
so level
The case of ()[][] where is similar, but easier.
2
We now come back to the confluence of (sigma).
(1) ([]).
(2) ([]) where .
(3) (()[])[])([])) where level() .
(4) ([][])[][[]]) if .
(5) (()[])([])) if .
(6) (()[])([])) if (renaming where possible) #fv
(2) Recall that we assume .
(3) Recall that we assume that level() .
(4) Recall that we assume that . Using Lemma 27
(5) Recall that we assume that .
(6)
2
[] ([]).
By definition ([])[]. We use Lemma 20. 2
If then .
We work by induction on the derivation of , see Figure 6.
In this proof, and in this proof only, we shall write for and for
(Rapp) Suppose so that .
By inductive hypothesis and by Theorem 23 , so also ). The case of () is similar.
(R) Suppose so that . By inductive hypothesis , and so ().
(R) Suppose so that [] [].
By inductive hypothesis and by Theorem 23 , so also [] []. By Lemma 31 [] ([]). The case of (R) is similar.
Now suppose that is derived using one of the rules (a), (c), (p), (), (), or (). In these cases we use Theorem 23 and the relevant part of Lemma 30.
2
is confluent.
By an easy inductive argument using Lemma 32. 2
4.2 (beta)-reduction
Inductively define the parallel reduction relation (for (beta)) by the rules in Figure 9.
In rules (P) and (Papp), and [] indicate a top-level rewrite with any (beta) — that is, and [] respectively are derivable without using (Rapp), (), (R), (R), or (R).
(1) .
(2) If then .
(3) If then .
As a corollary, if and only if .
All parts are by routine inductions:
(1) By induction on the syntax of .
(2) By induction on the derivation of .
(3) By induction on the derivation of .
2
If then fv
satisfies the diamond property. That is, if then there is some such that .
We work by induction on the depth of the derivation of proving
For simplicity we just consider possible pairs of rules which could derive and .
(Pa) and (Pa). There is nothing to prove.
(P) and (P). and and also and so that by (P) and (P)
By inductive hypothesis there are and such that
It follows that
(P) and (P) for ().
Suppose and and also and . Suppose also that so that by (P) and (P) for ()
By inductive hypothesis there are and such that
Using (P) for () and (P)
The case of (P) for () and (P) is similar.
(P) and (P) for ().
Suppose and and also and . Suppose also that (renaming where necessary) # so that by (P) and (P) for ()
By inductive hypothesis there are and such that
By Corollary 36 #. Using (P) for () and (P)
(P) with (P).
Suppose so that . By inductive hypothesis there is some such that . By (P) also
Other cases are similar and no harder. 2
is confluent.
4.3 Combining (sigma) and (beta)
If and then there is some such that
and .
We work by induction on the derivation of . For brevity we merely indicate the non-trivial parts.
We always assume that , , and , where appropriate.
This can be closed by:
We suppose, renaming if necessary, that #.
By Corollary 36 level() . By Lemma 20 and Theorem 23,
and by Lemma 29 this is equal to ()[][[]].
On the other hand (also using Lemma 20 and Lemma ??):
which closes the divergence above.
() has a divergence with (). Suppose that :
This can be closed by:
() has a divergence with (). Suppose that and (renaming where possible) #fv
We know that #fv() because #fv() and . We then deduce #fv() using Corollary 36. We use this to justify the -rewrite which uses (fv) in a moment.
This can be closed by:
2
We promised to explain why
() (beta) and () (beta) because otherwise the two cases of (p) and above, would not work.
(fv) (beta) because otherwise the case of () with () would not work.
We can easily generalise this lemma to several -steps:
If and then there is some such that
and .
We work by induction on the length of the path . The case of the empty path is trivial. Otherwise we have and the induction hypothesis provides such that and . Lemma 39 then provides such that and . 2
We now generalise this lemma even further:
If (respectively ) and , then there is some such that and (respectively ).
Again, we work by induction on the length of the path . The case of the empty path is trivial. Otherwise we have or . In both cases, the induction hypothesis provides such that and (respectively ). In the former case, Lemma 39 (respectively Theorem 33) provides such that and (respectively ). In the latter case, Lemma 37 (respectively Lemma 40) provides such that and (respectively ). 2
We can now prove Theorem 25:
Suppose that and . We prove that there exists such that and , by induction on the length of the reduction path . In the case of the empty path, . Otherwise, we have either or . In both cases, the induction hypothesis provides such that and , and then Lemma 41 provides such that , and or , and in both cases we have as required. 2
5 The untyped lambda-calculus
We show how to translate the untyped -calculus into the LCC.
For convenience, we use the variables of level 1 in the LCC as variables in our -calculus; when we translate the -calculus into the LCC, we will use this identification.
Terms of the untyped -calculus are given by
binds in . This is standard [2].
We define a free variables of fv() function in the usual way:
Call open when there exists some such that fv
Define a capture-avoiding substitution action inductively by:
Here we may assume does not occur in because we have equated syntax up to binding by .
Define a reduction relation inductively by:
We call a normal form or value when there is no such that . Note that normal forms may be open.
A translation into the LCC is given by:
The following results are very easy to prove:
fv( fv([[ ]] ).
We consider the clauses of the definition of fv above, and of the definition of fv from Figure 2, and we see that they coincide in the special case that only variables of level 1 appear. 2
[[ []] [ ].
We work by induction on the structure of .
Here we assume that fv
2
If then [[ ]] [[ .
We work by induction on the derivation of .
The case Then ()[], where (renaming if necessary) we choose fv
The other cases are easy. 2
Write when there is no such that . If call a normal form.
(Preservation of strong normalisation) If is a normal form then [[ ]] is a normal form.
As a corollary, if is any untyped -term, then if has a normal form then so does [[ ]] .
The corollary follows by Theorem 44.
It is a fact [2] that the normal forms of the untyped -calculus are inductively characterised (as a subset of the set of terms of the untyped -calculus) by:
The proof is by induction on .
[[ and we check the reduction rules of the LCC and observe that is a normal form.
[[ [[ [[ . We check the reduction rules of the LCC and observe that if [[ , . . . , [[ are normal forms, then so is [[ [[ .
[[ [[ ]] . By assumption [[ ]] is a normal form. We check the reduction rules of the LCC and observe that if [[ ]] is a normal form then so is [[ ]] .
2
6 A NEW part for the LCC
6.1 Some NEW rules
LCC -abstraction is weak in the sense that for example is not -convertible in , if has level 1 and has level 2.
Suppose we really do want to bind in . That is, suppose we want to recover the notion of ‘local variable’ which the traditional -calculus (without a hierarchy of levels) identifies with functional abstraction.
We extend the syntax of the LCC as follows:
We extend the definition of level and fv (Definition 2) with clauses
We extend the definition of congruence (Definition 4) with a clause
We extend the definition of swapping (Definition 5 ) with a clause
where is any atom.
We extend the definition of -equivalence (Definition 9) with a clause
Note the difference that in -equivalence for -abstraction we check #fv (Definition 7), and in -equivalence for -binding we check fv
Variables bound by rename regardless of whether stronger variables are present.
For example take and to be variables of level 1, and and to be variables of level 2. Then
We add reduction rules
has behaviour similar to that of -calculus restriction [21].
(p) and () are reminiscent of scope-extrusion.
() is reminiscent of ‘garbage-collection’.
Here is an example reduction which exploits :
Compare with a pair of related rewrites in the syntax without :
So binds and this is separated from the functional abstraction implemented by .
LCC syntax permits also not directly above , for example in . This behaves like a constant symbol and indeed fv( (though note that level information is preserved; level(). The which binds ensures that it can never be substituted for:
(Recall that we take terms up to -equivalence when discussing reductions.)
We shall make no use of terms of the form in the examples to come. In this paper we are only interested in to restore -conversion behaviour to -abstracted variables which have been abstracted over a scope containing stronger variables. However, we expect a better understanding of to be important for future work.
6.2 Some false NEW rules
We do not admit a rule
With (pFALSE) we can reduce as follows:
It is a fact that these terms are normal forms and they are not equal.
We can have an intuition of as ‘generating a fresh variable symbol’. Then (pFALSE) (with the other rules of the LCC) lets us make a non-confluent choice of whether to generate a name, then copy, or copy and then generate.
For similar reasons we do not admit (FALSE):
Why the side-conditions on ()? Clearly the condition fv() comes from the intuition of as defining a scope. We insist on to guarantee confluence:
Proofs extend smoothly to the calculus extended with rules for , including confluence and termination of (sigma) extended with the rules for .
7 Hindley-Milner types
Some basic motivation: a type system is a logic (often a decidable logic) on terms, which allows us to reason on terms without having to evaluate them. For example, in ML if a term types has type integer, by Subject Reduction the term will always have type integer no matter how we evaluate it, and if it reduces to a normal form that normal form will be an integer. So there is no ‘one’ type system; it depends what properties we are interested in.
Hindley-Milner typing [7] is a simple and successful polymorphic type system which underlies functional programming languages such as Erlang [39], ML [23], or Haskell [34]. As such it is both a ‘working (functional) programmer’s’ tool and a starting point for more complex schemes. If the LCC interacts well with it, then a hierarchy of variables can be implemented, at least in principle, as an extension of functional programming as we know it in common practice.
Fix infinitely many type variables TyVar. Types and type schemes are defined by:
Let a type substitution, we generally write or , be a function from type variables to types such that for all but finitely many . Type substitutions act on types in the standard way. Write when there is some substitution such that
(we shall just write for this),
implies that occurs in (we may say ‘ acts only on variables in ’), and
Also write tyv for the type variables appearing in .
A type context is a finite set of pairs : : such that if then for 1 . Type contexts may be empty. Γ ranges over type contexts.
Then typing rules are as follows:
The notation Γ in (Ty) is shorthand for ‘ and do not occur anywhere in the syntax of Γ’. The notation tyv Γ in (Ty) is shorthand for the type variables occurring free in Γ. For example
Abusing notation write Γ for the typing context obtained from Γ by removing from it : if there is some such that : Γ.
Write Γ : for (Γ ) : .
We have to be a little careful proving Lemma 46. In ‘normal’ -calculus we can always rename a -abstracted variable to avoid any clash with names in the type context, if this is convenient. In LCC this is not the case; for example if has level 1 and has level 2, then we cannot rename in . This difficulty is easily surmounted with just a little care, as follows:
If is a finite set of variables write Γ for the typing context Γ restricted to ; for example : : .
(Weakening) Γ : if and only if Γ : .
As a corollary, if fv then if Γ : then Γ : : . Here is any variable.
We prove the first part by induction on the derivation; the corollary is an easy consequence of it:
The case of (Tya). . . . is routine.
The case of (Ty). Suppose Γ : . By inductive hypothesis
By some easy set calculations, and using the corollary if fv
We may then use (Ty) to deduce that
as required.
The case of (Ty). Suppose that Γ and Γ : where tyv tyv Γ. By inductive hypothesis
By elementary calculations on sets and using the corollary if fv() we deduce that
The result follows observing that fv([fv
The case of (Ty). Suppose that Γ : : where and do not occur in Γ. By inductive hypothesis (Γ : ) : . By elementary set calculations and using the corollary if fv() we deduce that Γ : : . The result follows.
The case of (Typ) . . . is easy.
2
(Soundness) If Γ : and then Γ .
We check the rules for .
The case of Suppose that Γ () : is derivable. By following the typing derivation rules we see that for some ,
must be derivable. It is then easy to use (Ty) to deduce that Γ [] : , since for any .
The case of (a) . . . is easy.
The case of (fv). Suppose that Γ [] : and suppose that #fv It follows that fv(). By following the typing derivation rules we see that
where tyv tyv Γ. Now if fv() then by Lemma 46 also Γ : and we are done.
The case of (p). Suppose that Γ ()[] : . Then for some is must be that
Here tyv tyv Γ. Using (p) it is immediate that
The case of (). Suppose Γ [][] : . Then for some and ,
Here
It is not hard to calculate that , so we write for both henceforth. From this we can calculate that
and from this we can conclude that
as required.
The cases of () and (). Suppose Γ ()[] : is derivable. By following the typing derivation rules we see that
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 Γ ([]) : , using Lemma 46 to weaken Γ : to Γ : : .
The case of (p). Suppose that Γ () : is derivable where (renaming if necessary) we suppose does not occur in or Γ. Then
are derivable, where Γ. By Lemma 46 also Γ : : is derivable. It is now easy to derive Γ () : .
The cases of () and () are easy.
2
We use the following technical lemma in Theorem 49:
If Γ : then Γ : .
By induction on the derivation of Γ : . 2
Write () () when there is some such that
(type substitutions are written prefix, so is ‘ followed by ’), and
A type problem is a pair (Γ ). A solution to (Γ ) is a pair () such that Γ : . A principal solution is a solution () which is maximal amongst all solutions to (Γ ) in the ordering given by .
If Γ has a solution, then it has a principal solution.
A principal solution () is calculated by the algorithm below — the rules are read bottom-up, and we write (Γ ) for the pair () which is being calculated:
In the rule for , Id is the identity type substitution, which is such that Id.
In the rule for application () is the most general unifier of and ; that is it is a substitution such that () (a unifier of and ) which is msot general in the sense that all other unifiers are of the form for some . This is standard, see elsewhere [7]. The need not exist, for example () does not exist. It is part of the condition for using the rule for application above, that () does exist. It is a fact that if a unifier of two types exists, then a most general unifier exists.
In the rule for , consistent with previous usage Γ means ‘ does not occur anywhere in the syntax of Γ’.
The typing rules and principal types algorithm above are identical to those of the standard Hindley-Milner; we give our explicit substitution exactly the rules for the ML let construct. 2
The proofs transfer to this setting unchanged from the original presentations [7,6], because the definitions are identical — except for the case of , which is new.
It is routine to show by induction that if (Γ ) exists then it is a solution to Γ .
It remains to show that if a solution to (Γ ) exists, then the algorithm for calculating () calculates a principal solution. We consider only the cases of and :
The case of . Suppose that
By the form of the typing rules it must be that : Γ for some and such that . Here we assume (renaming if necessary) that acts trivially on and that no variable in occurs free in Γ. We take , and we are done.
The case of . Suppose that
By the form of the typing rules it must be that
By inductive hypothesis (Γ ) calculates a principal solution, write it (), so there is some such that and , and we are done.
2
In conclusion, the type system is almost identical to a standard Hindley-Milner type system for polymorphic types. The typing rule for explicit substitutions is identical to that of ML let. The hierarchy of variables does not damage the type system in any way. There also seems no a priori reason that LCC would not accommodate any other type systems developed for functional programming.
2 This is one of those ideas which is instantly obvious — in retrospect.↩
8 Applicative characterisation of contextual equivalence
As our final theoretical investigation we consider contextual equivalence of the LCC.
8.1 Programs, contexts, evaluations, and equivalences
It is convenient to introduce a constant such that .
Call a program when fv(.
As is our convention, take to have level 1 and to have level 2. For example:
and are not programs; fv(
and ([]) are programs.
If is a program write
and say that evaluates.
Call a context when
is a program, and
where level() and is the only variable of level in .
We may abuse notation and call a context.
For example:
, (), and are contexts.
is not a context because it is not a program; fv(
is not a context.
is not a context.
is a context.
An equivalence relation is a transitive symmetric reflexive relation. Call an equivalence relation on programs contextual when
Here ranges over contexts and and range over programs. Write 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
Here , , and range over programs. Write for the greatest applicative equivalence and abuse notation calling it applicative equivalence.
The main result of this section is
and are equal.
. . . but we need technical machinery to prove it.
Write for the least equivalence relation containing . Then
Also, always, for 0.
Suppose . By confluence Theorem 25
if and only if
and similarly for and .
For the second part we examine the reduction rules and observe that is impossible unless 2
When we define we consider applied to . 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 [].
In the proofs below we tend to use traditional notation of [] rather than ().
We can also characterise as the greatest congruence (Definition 4; extended with the rule for from Subsection 6.1) such that
We do not explore this further because the definition of which we use is more convenient for the proof-method to follow.
8.2 Proof that equals
Suppose and are programs and . We want to show that . By the coinductive principle by which was defined, it suffices to show that if then:
If then .
For any program it is the case that .
The first part follows directly from our assumption that .
Also for any program , the term () is a context (where is a variable which we choose stronger than any variable in or ). By assumption ()[] ()[]. To take the next step and reduce these to and we need Lemmas 53 and 54.
If level then #fv
By an easy induction on the definition of level() (Definition 2). 2
Suppose and are any terms (we only care about the case that and are programs). Suppose further that is a variable such that level(). Then
By Lemma 54 ()[] and ()[] . By Lemma 52 we have that , and we are done.
Now suppose that . We want to prove that . By the coinductive principle by which was defined, it suffices to show that if then:
If then .
For any context it is the case that .
We work by induction on the tuple () where
is the number of occurrences of in the normal form of and otherwise (=the first uncountable ordinal; if has no normal form there will be nothing to prove),
is the least number of -reductions to reduce to its normal form and otherwise, and
is the size of ,
proving that
is a contextual relation, where varies over possibly empty lists of variables no stronger than . We work by cases on the form of .
In the the cases below we may implicitly use the first part of Lemma 52 along with confluence and the inductive hypothesis, to suppose that is in -normal form. We also silently strip leading s, writing for example for .
Suppose . Then [] []. We use the first part of Lemma 52 and the fact that is an equivalence.
Suppose ). Then [] and [] cannot evaluate to so there is nothing to prove.
Suppose , and suppose occurs in and . We reason as follows:
Here we choose fresh and stronger than . We justify the steps of this reasoning, which we numbered on the right above:
(1) has fewer instances of than since we assumed that also appears in . So we use the inductive hypothesis for to deduce that [] []. By assumption is closed under application on the right, and so also ([])([]) ([])([]).
(2) (())[]([]) is easy to verify.
(3) By the inductive hypothesis and the fact that is closed under application on the right.
(4) Reversing the reasoning above.
Suppose , and suppose occurs in but not . We reason as follows:
Suppose , and suppose does not occur in and may or may not occur in . We have supposed that is a normal form with no
unabstracted variables. If is a -abstraction then reduces with so we use the inductive hypothesis. Otherwise, cannot ever evaluate and there is nothing to prove.
Suppose []. 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 occurs in and , or in and not in , we can proceed as we did for applications above. Suppose does not occur in and does occur in . We have supposed this is a normal form, so we work by cases: for some and such that is not weaker than (so that () does not apply). Then [][] cannot possibly evaluate to for any , so there is nothing to prove. . We are free to -convert and therefore we can use () to reduce [], contradicting our assumption that [] is a normal form. . [] is not a normal form, because of (a). for not stronger than . [] is not a normal form, because of (fv). for stronger than and (by assumption) not equal to . It is not possible for [][] to evaluate to for any , so there is nothing to prove. The case of [] is similar.
That concludes the proof of Theorem 51.
9 Related work, conclusions, and future work
In a previous conference paper we presented the NEW calculus of contexts
[9]. The LCC of this journal paper updates and improves that that work. The LCC is simpler than the NEWcc. Compare the side-condition of (a) (there is none) with that of (a) from [9]. The notion of freshness is simpler and intuitive; we no longer require a logic of freshness, or the ‘freshness context with sufficient freshnesses’, see most of page 4 in [9]. A key innovation in attaining this simplicity is our use of conditions involving level() the level of , which includes information about the levels of free and bound variables, and the condition on rule (p).
But there is a price: the LCC has fewer reductions. Notably () will not reduce ()[] where ; a rule () in [9] does. However that stronger version seems to be a major source of complexity. Do we miss the extra reductions? An insight that was necessary to make this paper is that certain reductions which we thought were important, could be dropped. Still, it is clear that we are approximating something larger. Other papers on nominal techniques have useful elements which we can import, now that we have a solid basis to work from.
In this paper we cannot -convert in . Nominal terms can: swappings are in the syntax (here swappings are purely a meta-level) and also freshness contexts [36]. A problem is that we do not yet understand the theory of swappings for strong variables; the underlying Fraenkel-Mostowski sets model [13] only has (in the terminology of this paper) one level of variable. A semantic model of the hierarchy of variables would be useful and this is current work.
In this paper we cannot deduce #fv() even though for every instance this does hold (for example # and #). Hierarchical nominal rewriting [10] has a more powerful notion of freshness which can prove the equivalent of #fv(). Note that hierarchical nominal rewriting does have the conditions on levels which we use to good effect in this paper.
We cannot reduce ()[] because there is no such that # . We can allow programs to dynamically generate fresh variables in the style of FreshML
[25] or the style of a sequent calculus for Nominal Logic by Cheney [5].
Finally, we cannot reduce [2][3] to [3][2]. Other work [12] gives an equational system which can do this, and more.
Desirable and nontrivial meta-properties of the -calculus survive in the LCC. The LCC is confluent. It supports a type system in Hindley-Milner style making it possible, in principle at least, to envisage an extension of ML or Haskell with meta-variables based on the LCC’s notion of strong and weak variables. Also, contextual equivalence coincides with applicative equivalence — a full treatment will be in a longer paper. This is a surprising result considering that substitution in the LCC can capture.
More related work (not using nominal techniques). The calculi of contexts and [30] also have a hierarchy of variables. They use carefully-crafted scoping conventions to manage problems with -conversion. Other work [28,16,29] uses a type system; connections with this work are unclear. of Bognar’s thesis contains [4, Section 2] an extensive literature survey on the topic of context calculi.
A separation of abstraction and binding appears in one other (unpublished) work we know of [32], where they are called and . In this vein there is [17], which manages scope explicitly in a completely different way, just for the fun. Finally, the reduction rules of look remarkably similar to -calculus restriction [21], and it is probably quite accurate to think of as a ‘restriction in the -calculus’.
Hamana takes a semantic approach to meta-variables [15]. We have not developed the semantic theory of the LCC. We should do this in future work, and when we do we would expect to arrive at something similar to Hamana’s construction. However we do not expect the semantics to be identical; ours it will be phrased in terms of sets and permutation actions (in keeping with the first author’s previous work [13]). These have slightly stronger, and in our opinion more desirable, properties than the categories of presheaves which Hamana uses.
Ours is a calculus with explicit substitutions. See [20] for a survey. Our treatment of substitution is simple-minded but still quite subtle because of interactions with the rest of the language. We note that the translation of possibly open terms of the untyped -calculus into the LCC preserves strong normalisation. One reduction rule, (fv), is a little unusual amongst such calculi, though it appears as Bloo’s ‘garbage collection’ [3].
The look and feel of the LCC is squarely that of a -calculus with explicit substitutions. All the real cleverness has been isolated in the side-condition of (p); other side-conditions are obvious given an intuition that strong variables can cause capturing substitution (in the NEWcc [9] complexity spilled over into other rules and into a logic for freshness). is only necessary when variables of different strengths occur, and the hierarchy of variables only plays a rôle to trigger side-conditions.
Further work. We discussed above how to add off-the-shelf elements of nominal techniques, if we want to give ourselves more reductions.
Another possibility is in the direction of logic, treating equality instead of reduction and imitating higher-order logic, which is based on the simply-typed -terms enriched with constants such as : () and : where is a type of truth-values [38], along with suitable equalities and/or derivation rules. Because the LCC admits a Hindley-Milner style type system it certainly admits a simple type system. There should be no problem with writing down a ‘context higher-order logic’. This takes the LCC in the direction of calculi of contexts for incomplete proofs [18,14], and also in the direction of giving semantics to existential variables in logic-programming (unpublished work by Lipton and Mariño). The non-trivial work (in no particular order) is to investigate cut-elimination, develop a suitable theory of models, and to check whether and how usefully the LCC can be used as-is to model incomplete proofs of some theorem-proving system.
One important element is the denotation semantics of the hierarchy of variables — we do not yet have one; this is current work.
Certain specific ideas appear elsewhere in the literature which the LCC cannot express, but they might be accommodated with a relatively straightforward extension.
As discussed, the LCC can express [] using the term ([]) where and level() . However we cannot abstract over . For example consider ([]) and the reduction
This is not the intended operational behaviour (if we intended to abstract over the name of and replace it by ). Variables can be substituted for so it should not possible to pass a variable name as a first-class value. An extension of the LCC based on atom from [11] may be possible and useful.
The LCC cannot express ‘substitute all variables of level 1 for in ’, which we might write as []. This idea appears in work by Dami [8] on dynamic binding. We do believe that the LCC could have something to contribute to dynamic binding and linking, since they seem to have to do with capturing substitution, but that is future work.
Languages for staged computation, for example MetaML [22,26], Template Haskell [31], and Converge [35], have a hierarchy (of stages) reminiscent of our hierarchy of levels. They offer a program enough control of its own execution that it can suspend its own execution, compose suspended programs into larger (suspended) programs, pass suspended programs as arguments to functions, and evaluate them. This raises issues similar to those surrounding contexts. The LCC cannot model staged computation because it is a pure rewrite system with no control of evaluation order. Even if we choose some evaluation order on the LCC to make it into a programming language, the deeper problem is that the LCC has no first-class construct to promote variables between levels. Adding this extension is interesting future work.
In conclusion: the LCC of this paper is simple, clear, and it has good properties. It seems to hit a technical sweet spot. Often in computer science the trick is to find a useful balance between simplicity and expressivity. Perhaps the LCC does that.
References
[1] Franz Baader and Tobias Nipkow, Term rewriting and all that, Cambridge University Press, 1998.
[2] H. P. Barendregt, The lambda calculus: its syntax and semantics (revised ed.), North-Holland, 1984.
[3] Roel Bloo and Kristoffer Høgsbro Rose, Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection, CSN-95: Computer Science in the Netherlands, 1995.
[4] Mirna Bognar, Contexts in lambda calculus, Ph.D. thesis, Vrije Universiteit Amsterdam, 2002.
[5] James Cheney, A simpler proof theory for nominal logic, FOSSACS, Springer, 2005, pp. 379–394.
[6] Luis Damas, Type assignment in programming languages, Ph.D. thesis, University of Edinburgh, 1985.
[7] Luis Damas and Robin Milner, Principal type-schemes for functional programs, POPL ’82: Proc. of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, 1982, pp. 207–212.
[8] Laurent Dami, A lambda-calculus for dynamic binding, Theoretical Computer Science 192(2) (1998), 201–231.
[9] Murdoch J. Gabbay, A new calculus of contexts, PPDP ’05: Proc. of the 7th ACM SIGPLAN int’l conf. on Principles and Practice of Declarative Programming, ACM Press, 2005, pp. 94–105.
[10], Hierarchical nominal rewriting, LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice, 2006, pp. 32–47.
[11] Murdoch J. Gabbay and Michael J. Gabbay, a-logic, We Will Show Them: Essays in Honour of Dov Gabbay, vol. 1, College Publications, 2005.
[12] Murdoch J. Gabbay and Aad Mathijssen, Capture-avoiding substitution as a nominal algebra, ICTAC’2006: 3rd Int’l Colloquium on Theoretical Aspects of Computing, 2006, pp. 198–212.
[13] Murdoch J. Gabbay and A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
[14] Herman Geuvers and Gueorgui I. Jojgov, Open proofs and open terms: A basis for interactive logic, CSL, Springer, 2002, pp. 537–552.
[15] M. Hamana, Free sigma-monoids: A higher-order syntax with metavariables, The Second Asian Symposium on Programming Languages and Systems (APLAS 2004), LNCS, vol. 3202, 2004, pp. 348–363.
[16] Masatomo Hashimoto and Atsushi Ohori, A typed context calculus, Theor. Comput. Sci. 266 (2001), no. 1-2, 249–272.
[17] Dimitri Hendriks and Vincent van Oostrom, Adbmal, CADE, 2003, pp. 136–150.
[18] Gueorgui I. Jojgov, Holes with binding power., TYPES, LNCS, vol. 2646, Springer, 2002, pp. 162–181.
[19] Samuel Kamin and Jean-Jacques Lévy, Attempts for generalizing the recursive path orderings, Handwritten paper, University of Illinois, 1980.
[20] Pierre Lescanne, From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions, POPL ’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, 1994, pp. 60–69.
[21] Robin Milner, Joachim Parrow, and David Walker, A calculus of mobile processes, II, Information and Computation 100 (1992), no. 1, 41–77.
[22] Eugenio Moggi, Walid Taha, Zine-El-Abidine Benaissa, and Tim Sheard, An idealized metaml: Simpler, and more expressive, ESOP ’99: Proc. of the 8th European Symposium on Programming Languages and Systems, LNCS, vol. 1576, 1999, pp. 193–207.
[23] Lawrence C. Paulson, Ml for the working programmer (2nd ed.), Cambridge University Press, 1996.
[24] A. M. Pitts, Operationally-based theories of program equivalence, Semantics and Logics of Computation (P. Dybjer and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1997, pp. 241–298.
[25] A. M. Pitts and Murdoch J. Gabbay, A metalanguage for programming with bound names modulo renaming, Mathematics of Program Construction. 5th Int’l Conf. , MPC2000, Ponte de Lima, Portugal, July 2000. Proceedings (R. Backhouse and J. N. Oliveira, eds.), LNCS, vol. 1837, Springer-Verlag, 2000, pp. 230–255.
[26] A. M. Pitts and T. Sheard, On the denotational semantics of staged execution of open code, Submitted, 2004.
[27] A. M. Pitts and I. D. B. Stark, Operational reasoning for functions with local state, Higher Order Operational Techniques in Semantics (A. D. Gordon and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1998, pp. 227–273.
[28] Masahiko Sato, Takafumi Sakurai, and Rod Burstall, Explicit environments, Fundamenta Informaticae 45:1-2 (2001), 79–115.
[29] Masahiko Sato, Takafumi Sakurai, and Yukiyoshi Kameyama, A simply typed context calculus with first-class environments, Journal of Functional and Logic Programming 2002 (2002), no. 4, 359 – 374.
[30] Masahiko Sato, Takafumi Sakurai, Yukiyoshi Kameyama, and Atsushi Igarashi, Calculi of meta-variables, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings (M. Baaz, ed.), LNCS, vol. 2803, 2003, pp. 484–497.
[31] Tim Sheard and Simon Peyton Jones, Template metaprogramming for Haskell, ACM SIGPLAN Haskell Workshop 02 (Manuel M. T. Chakravarty, ed.), ACM Press, 2002, pp. 1–16.
[32] Francois Maurel Sylvain Baro, The qnu and qnuk calculi : name capture and control, Tech. report, Université Paris VII, 2003, Extended Abstract, Prépublication PPS//03/11//n16.
[33] Terese, Term rewriting systems, Cambridge Tracts in Theoretical Computer Science, no. 55, Cambridge University Press, 2003.
[34] Simon Thompson, Haskell: The Craft of Functional Programming, Addison Wesley, 1996.
[35] Laurence Tratt, Compile-time meta-programming in converge, Tech. Report TR-04-11, Department of Computer Science, King’s College London, 2002.
[36] C. Urban, A. M. Pitts, and Murdoch J. Gabbay, Nominal unification, Theoretical Computer Science 323 (2004), no. 1–3, 473–497.
[37] Johan van Benthem, Modal foundations for predicate logic, Logic Journal of the IGPL 5 (1997), no. 2, 259–286.
[38], Higher-order logic, Handbook of Philosophical Logic, 2nd Edition (D.M. Gabbay and F. Guenthner, eds.), vol. 1, Kluwer, 2001, pp. 189–244.
[39] Robert Virding, Claes Wikström, and Mike Williams, Concurrent programming in ERLANG, 2 ed., Prentice Hall, 1996.