Replace this file with prentcsmacro.sty for your meeting, or with entcsmacro.sty for your meeting. Both can be found at the ENTCS Macro Home Page.
The -context calculus
Murdoch J. Gabbay Stéphane Lengrand
Abstract
We present a simple but expressive lambda-calculus whose syntax is populated by variables which behave like meta-variables. It can express both capture-avoiding and capturing substitution (instantiation). To do this requires several innovations, including a key insight in the confluence proof and a set of reduction rules which manages the complexity of a calculus of contexts over the ‘vanilla’ lambda-calculus in a very simple and modular way. This calculus remains extremely close in look and feel to a standard lambda-calculus with explicit substitutions, and good properties of the lambda-calculus are preserved.
Keywords: Lambda-calculus, contexts, meta-variables, capture-avoiding substitution, capturing substitution, instantiation, confluence, nominal techniques, calculus of explicit substitutions.
1 Introduction
This is a paper about a -calculus for contexts. A context is a term with a ‘hole’. The canonical example is probably - 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 (). (Here = is -equality.)
Contexts arise often in proofs of meta-properties in functional programming. They have been substantially investigated in papers by Pitts on contextual equivalence between terms in -calculi (with global state) [18,20]. This work was about proving programs equivalent in all contexts — contextual equivalence. The idea is that two programs, represented by possibly-open -terms, are equivalent when one can be exchanged for another in code (without changing whichever notion of observation we prefer to use).
This suggests that we should call holes context variables (say they have ‘level 2’) distinct from ‘normal’ variables (say they have ‘level 1’) and allow -abstraction over them to obtain a -calculus of contexts, so that we can study program contexts with the full panoply of vocabulary, and hopefully with many of the theorems, of the -calculus. For example - may be represented by . Substitution for does not avoid capture with respect to ‘ordinary’ -abstraction, so () reduces to .
c 2007 Published by Elsevier Science B. V.
The Lambda Context Calculus internalises context variables (as variables of ‘level 2’, which we write ). , , and are now variables which can occur any number of times anywhere in a term — and they can be -abstracted. The Lambda Context Calculus therefore goes further and internalises another level of contexts (variables of ‘level 3’, which we write ) — and so on. There are several possibilities where such a calculus might be applied.
Consider formalising mathematics in a logical framework based on Higher-Order Logic (HOL) [28]. Typically we have a goal and some assumptions and we want a derivation of one from the other. This derivation may be represented by a -term (the Curry-Howard correspondence). But the derivation is arrived at by stages in which it is incomplete.
To the right are two derivations of . The bottom one is complete, the top one is incomplete. 1 An issue arises because the right-most [] in the bottom derivation is discharged, which means that we have to be able to instantiate ? in a sub-derivation for an assumption which will be discharged. Discharge corresponds in the Curry-Howard correspondence precisely to -abstraction, and this instantiation corresponds to capturing substitution. Similar issues arise with existential variables [10, Section 2, Example 3].
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 to reduce a term like ().
Solutions include clever control of substitution and evaluation order [23], types to prevent ‘bad’ -conversions [21,11,22], explicit labels on meta-variables [10,13], and more [4, Section 2]. More on this in the Conclusions.
We took our technical ideas for handling -equivalence, not from the literature on context calculi cited above, but from nominal unification [27]. This was designed to manage -equivalence in the presence of holes, in unification — ‘unification of contexts of syntax’, in other words. Crudely put, we obtained the -context calculus (LCC) by allowing -abstraction over the holes and adding -reduction.
This work has similar goals to previous work by the first author [6] which presented a calculus called NEWcc. The LCC possesses a significatnly more elementary set of reduction rules; notably, we dispense entirely with the freshness contexts and freshness logic of the NEWcc. Indeed, the LCC has only one single non-obvious side-condition, it is on (p) in Figure 5.
The result is a system with a powerful hierarchy of context variables and which still manages to be clean and, we hope, easy to use and to study.
In Section 2 we present the syntax and reductions of the LCC. The look-and-feel is of a -calculus with explicit substitutions, except that each variable has a ‘level’ which determines how ‘strongly’ binders by that variable resist capture. We give example reductions and discuss the technical issues which motivated our design. In Section 3 we discuss the -free part of the language, prove strong normalisation, and give an algorithm for calculating normal forms. In the usual -calculus this normal form is calculated in big-step style and written []; as is standard for a calculus of explicit substitutions, here this part of evaluation is dissected in detail. In Section 4 we treat confluence, first of the -free part of the language, then of the full reduction system. The proof may look elementary but it is not, and we give enough technical detail to show how all the side-conditions interact to ensure confluence. It is not sufficient to give a -calculus without binding, but the hierarchy of levels means that itself is no longer necessarily a binder. We address that issue with a new in Section 5. We conclude with brief discussions of programming in Section 6, and then discuss related and future work.
2 Syntax and reductions
2.1 Syntax
We suppose a countably infinite set of disjoint infinite sets of variables , , . . . . range over levels; we usually maintain a convention that , where we break it we clearly say so. We always use a permutative convention that range permutatively over variables of level ; so , , and are always distinct variables. There is no particular connection between and ; we have just given them similar names.
LCC syntax is given by [].
Application associates to the left, e.g. is (). We say that has level . We call stronger than , and weaker than , when . If we say that and have the same strength. We call [] an explicit substitution (of level ). We call an abstraction (of level ).
By convention are distinct variables; have level 1, have level 2, and has level 3. Note that levels are 1 2 3 but our proofs would work as well for levels being integers, reals, or any totally ordered set.
The stronger a variable, the more ‘meta’ its behaviour. The intuition of is of the context - where - is a hole; this is because, as we shall see, substitution for the relatively strong does not avoid capture by the relatively weak . Strong variables can be abstracted as usual; the intuition of is of the ‘normal’ identity function; the intuition of is of the mapping ‘ maps to ’.
Our syntax has no constant symbols though we shall be lax and use them where convenient, for example 1 2 3. This can be accommodated by extending syntax, or by declaring them to be variables of a new level 0 1 which we do not abstract over or substitute for.
Define the level level and the free variables fv by the rules in Figure 1.
Here max() is the greater of and , and max() is the greatest of , , and . Later we shall write ‘level() ’ as shorthand for ‘level
If level( then fv coincides with the usual notion of ‘free variables of’ for the -calculus, if we read [] as ().
We shall see that the operational behaviour of such terms is the same as well.
A congruence is a binary relation satisfying the conditions of Figure 2. Define an (atoms) swapping () by the rules in Figure 3. Swapping is characteristic of the underlying ‘nominal’ method we use in this paper [9,27]. We let swapping () act pointwise on sets of variables : ()(). Here ranges over all elements of , including and (if they are in ).
fv(())fv and level(() level
If is a set of variables write # when and also there exists no variable such that .
Call the two rules in Figure 4 -conversion of . Let -equivalence be the least congruence relation containing -conversion.
Note that: may be -converted in if level
If mentions only variables of level 1, then -equivalence collapses to the usual -equivalence on untyped -terms (plus an explicit substitution).
In the rest of this paper we find it convenient to work on terms up to -equivalence (=-equivalence classes of terms). When later we write ‘’, the intended reading is that the -equivalence classes of and are equal.
2.2 Reductions
Define the reduction relation by the rules in Figure 5.
Recall our permutative convention; for example in () and are distinct. Subsection 2.3 shows examples of these rules at work, and Subsection 2.4 discusses their design. We shall use the following notation:
We write for the transitive reflexive closure of .
We write when there exists no such that . If we call a normal form, as is standard.
We write when we can deduce using only rules in (ruleset) and the rules (Rapp) to (R), where (ruleset) (a) (fv) (p) () () (). (Later in Section 5 we extend reduction with rules for a binder .)
Call terminating when there is no infinite sequence Similarly for (. Call confluent when if and then there exists some such that and . Similarly for ( .
We note two easy but important technical properties: reductions does not increase the level of a term or its set of free variables.
If then level
If then fv
2.3 Example reductions
The LCC is a -calculus with explicit substitutions [15]. The general form of the -rules is familiar from the literature though the conditions, especially those involving levels, are not; we discuss them in Subsection 2.4 below. First, we consider some example reductions. Recall our convention that we write for variables of level 1, and for variables of level 2.
The behaviour of a substitution on a variable depends on strengths:
The term [] will not reduce until a suitable strong substitution [] arrives from the surrounding context, if any.
Substitutions for relatively strong variables may distribute using () or () under substitutions or -abstractions for relatively weaker variables:
This makes strong variables behave like ‘holes’. Instantiation of holes is compatible with -reduction; here is a typical example:
There is no restriction in [] that level
[] is not a term, but the term [] where and level() will achieve the effect of ‘the substitution [] as a term’:
2.4 Comments on the side-conditions
(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() but #fv
It is unusual for a garbage collection rule to appear in a calculus of explicit substitutions; we might hope to ‘push substitutions into a term until they reach variables’ and so make do with a rule of the form [] (for ). In the LCC this will not do because side-conditions (such as that of (p)) can stop a substitution going deep into a term. Without (fv) we lose confluence (see the second case of Theorem 4.10). A version of (fv) appears in the literature as ‘garbage collection’ [3].
Recall that the level of a term is the level of the strongest variable it contains, free or bound. The side-condition level() in (p) seems to be fundamental for confluence to work; we have not been able to sensibly weaken it, even if we also change other rules to fix what goes wrong when we do. Here is what happens if we drop the side-condition entirely:
The side-conditions on (), (), and () implement that a strong substitution can capture. There is no () since that would destroy termination of the part of the LCC without — and we have managed to get confluence without it.
There is no rule permitting a weak substitution to propagate under a stronger abstraction, even if we avoid capture:
Such a rule causes the following problem for confluence:
As is the case for the side-condition of (p), any stronger form of () than what we admit in the LCC seems to provoke a cascade of changes which make the calculus more complex.
Investigation of these side-conditions is linked to strengthening the theory of freshness and -equivalence, and possibly to developing a good semantic theory to guide us. This is future work and some details are mentioned in the Conclusions.
3 The substitution action
Define (sigma) (a) (fv) (p) () () () (so (sigma) is ‘everything except for ’). It would be good if this is is terminating [3,15]. Do we sacrifice this property because of the hierarchy of variables? No. To prove it we translate LCC syntax to first-order terms (terms without binding [1,25]) in the signature
as follows:
Here has arity 0, Abs has arity 1, App has arity 2, and Sub has arity 2 for all ( ranges over levels). Give symbols precedence (lowest precedence on the right)
Define the lexicographic path ordering [14,1] by:
Here and are first-order symbols, has strictly lower precedence than , and are first-order terms. It is a fact [14,1] that is a well-founded order on first-order terms satisfying the subterm property, i.e. if is a subterm of then .
If then . Thus (sigma)-reduction terminates.
The proof is by checking that a (sigma)-reduction strictly reduces the lexicographic path order of the associated first-order term; this is not hard.
Let have level 1. ()() has an infinite series of reductions in the LCC. It follows that — even with a hierarchy of variables — strictly adds power to the LCC.
Call (sigma)-normal when . What does a (sigma)-normal form look like? Define a substitution action [] and using it define , by the rules in Figure 6. Rules are listed in order of precedence so that a later rule is only used if no earlier rule is applicable. We apply the rule ()[] renaming where possible to ensure #fv
[] ([].
Each clause in the definition of [] is simulated by a (sigma)-rule. □
and is a (sigma)-normal form.
The first part is by an easy induction on the definition of ; the case of ([]) uses Lemma 3.2. The second part is by a routine induction on . 2
4 Confluence
Let (beta) be the set () () (fv). (sigma) (beta) is non-empty; we discuss why at the end of Subsection 4.3.
is confluent.
The proof of Theorem 4.1 occupies this section. Two standard proof-methods are: (1) Use a parallel reduction relation , and (2) for all define a such that and if then . Both methods are standard [25]. Which to use for the LCC? It seems that ‘wants’ method 1 — but ‘wants’ method 2. Confluence is (relatively) easy to prove if we split the reduction relation into (sigma) and (beta) and apply different methods to each — and then join them together.
4.1 Confluence of (sigma)
Note there is no capture-avoidance condition in Lemma 4.2, because . The full proofs also contain another version where and #fv
If then [][[][[]]
(i) ([]).
(ii) ([]) where .
(iii) (()[])[])([])) where level() .
(iv) ([][])[][[]]) if .
(v) (()[])([])) if .
(vi) (()[])([])) if (renaming where possible) #fv
If then .
By induction on the derivation of , using Lemma 4.3. 2
( is confluent.
By an easy inductive argument using Lemma 4.4. 2
4.2 (beta)-reduction
Define the parallel reduction relation by the rules in Figure 7.
In rules (P) and (Papp), and [] indicate a rewrite with (beta) derivable without using (Rapp), (), (R), (R), or (R).
if and only if .
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 ( ). We consider possible pairs of rules which could derive and . All cases are very easy, we only sketch that of (P) and (P) for (), which is the least trivial.
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 and . By Corollary 4.7 #. Using (P) for () and (P)
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.
() has a divergence with (). Suppose and (renaming if necessary) #fv
We know #fv() because #fv() and . We deduce #fv() using Corollary 4.7. This justifies the -rewrite below, which uses (fv):
() is in (sigma) (beta) to make the case of (p) with work. () is in (sigma) (beta) to make a similar divergence of (p) with work. (fv) is in (sigma) (beta) to make the case of () with () work.
Theorem 4.1 now follows by an easy diagrammatic argument using Theorem 4.10, Theorem 4.5, and Lemma 4.8.
5 A NEW part for the LCC
is not -convertible in . Suppose we really do want to bind ; we can do so with . We extend syntax: . We extend the notions of level, fv, congruence, and swapping with cases for which are identical to those for (except that we write instead). For example fv( fv
The difference is in the -equivalence: () if fv Note the fv() instead of #fv() as in the clause for . This lets variables bound by -convert regardless of whether stronger variables are present. For example but . We add reduction rules:
is not bound in if mentions a strong variable, for example in () substitution for can capture . We may want to be really local and avoid capture by substitutions for . We can increase the level of ; () will do in this case. This has a hidden cost because side-conditions (especially on (p)) look at strengths of variables, so having strong variables can block reductions in the context. avoids this, for example () has the behaviour we need:
is reminiscent of -calculus restriction [16]. (p) and () are reminiscent of scope-extrusion. () is reminiscent of ‘garbage-collection’.
We do not admit a rule ‘() () if fv()’:
For similar reasons we do not admit a rule ‘[] ([]) if fv()’.
Why the side-conditions on ()? fv() comes from the intuition of as defining a scope. We need for confluence:
The proof of termination of (sigma) extends smoothly if we add the rules for to (sigma) (to make a set (sigmanew)). The proof of confluence for the system as a whole also extends smoothly. We see some examples of the use of in a moment.
6 Programming in the calculus
Call single-leveled of level when all variables in it (free or bound) have level . Then it is easy to prove that notions of free variable and substitution coincide with the ‘traditional’ definitions and we have:
For any the single-leveled terms of level , with their reductions, form an isomorphic calculus to with garbage collection [3].
As a corollary, the trivial mapping from the untyped -calculus to single-leveled terms of level 1 (say), preserves normal forms and strong normalisation.
We can exploit the hierarchy to do some nice things. Here is one example: [2][3] can be viewed as a record with ‘handle’ and with 2 stored at and 3 at . Then ([]) applied to looks up the data stored at , and ([[3]]) updates it. In fact these terms do a little more than this, because their effect is the same when applied to a term in which a record with ‘handle’ is buried deep in the term, perhaps as part of a -redex or substitution. ([ ([])+1]) increments the value stored at .
Here is an example reduction:
There is some garbage here, but a later look-up on returns 3, not 2:
We can use to assign fresh storage. The following program, if applied to a value and , extends with a fresh location and returns the new record together with a lookup function for the new location:
Here we use a pairing constructor (- -) just for convenience.
Note that we access data in by applying a substitution for ; in this sense the ‘handle’ in is externally visible. We can hide it by -abstracting to obtain ([2][3]). Then lookup at becomes () and update becomes ([[1]]).
We can parameterise over the data stored in the record: ([][]). Furthermore a term of the form ([][]) can capture a form of self-reference within the record. Finally, ([][]) makes no committment about the data stored.
7 Related work, conclusions, and future work
The LCC of this paper is simpler than the NEWcc [6]. Compare the side-condition of (a) (there is none) with that of (a) from [6]. The notion of freshness is simpler and intuitive; we no longer require a logic of freshness, or the ‘freshness context with sufficient freshnesses’, see most of page 4 in [6]. A key innovation in attaining this simplicity is our use of conditions involving level() the level of , which includes information about the levels of free and bound variables.
But there is a price: this calculus has fewer reductions. Notably () will not reduce ()[] where ; a rule () in [6] does. That stronger version seems to be a major source of complexity.
Still, the LCC is part of something larger yet to be constructed. Other papers on nominal techniques contain elements of the developments we have in mind when we imagine such a system. So for example:
In this paper we cannot -convert in . Nominal terms can: swappings are in the syntax (here swappings are in the meta-level) and also freshness contexts [27]. A problem is that we do not yet understand the theory of swappings for strong variables; the underlying Fraenkel-Mostowski sets model [9] only has (in the terminology of this paper) one level of variable. A semantic model of the hierarchy of variables would be useful and this is current work.
In this paper we cannot deduce #fv() even though for every instance this does hold (for example # and #). Hierarchical nominal rewriting [7] has a more powerful notion of freshness which can prove the equivalent of #fv(). Note that hierarchical nominal rewriting does not 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 [19] or the style of a sequent calculus for Nominal Logic by Cheney [5].
We cannot reduce [2][3] to [3][2]. Other work [8] gives an equational system which can do this, and more.
There is no denotational semantics for the LCC. This is current work.
More related work (not using nominal techniques). The calculi of contexts and [23] also have a hierarchy of variables. They use carefully-crafted scoping conventions to manage problems with -conversion. Other work [21,11,22] uses a type system; connections with this work are unclear. 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 work we know of [24], where they are called and . In this vein there is [12], which manages scope explicitly in a completely different way, just for the fun. Finally, the reduction rules of look remarkably similar to -calculus restriction [16], and it is probably quite accurate to think of as a ‘restriction in the -calculus’.
Ours is a calculus with explicit substitutions. See [15] for a survey. Our treatment of substitution is simple-minded but still quite subtle because of interactions with the rest of the language. We note that the translation of possibly open terms of the untyped -calculus into the LCC preserves strong normalisation. One reduction rule, (fv), is a little unusual amongst such calculi, though it appears as ‘garbage collection’ of [3].
The look and feel of the LCC is squarely that of a -calculus with explicit substitutions. All the real cleverness has been isolated in the side-condition of (p); other side-conditions are obvious given an intuition that strong variables can cause capturing substitution (in the NEWcc [6] complexity spilled over into other rules and into a logic for freshness). is only necessary when variables of different strengths occur, and the hierarchy of variables only plays a rôle to trigger side-conditions.
Further work. Desirable and nontrivial meta-properties of the -calculus survive in the LCC including confluence, and preservation of strong normalisation for a natural encoding of the untyped -calculus into the LCC. It is possible, in principle at least, to envisage an extension of ML or Haskell [17,26] with meta-variables based on the LCC’s notion of strong and weak variables.
We can go in the direction of logic, treating equality instead of reduction and imitating higher-order logic, which is based on the simply-typed -terms enriched with constants such as : () and : where is a type of truth-values [29], along with suitable equalities and/or derivation rules. There should be no problem with imposing a simple type system on LCC and writing down a ‘context higher-order logic’. This takes the LCC in the direction of calculi of contexts for incomplete proofs [13,10]. The non-trivial work (in no particular order) is to investigate cut-elimination, develop a suitable theory of models/denotations, and possibly to apply it to model incomplete proofs.
An implementation is current work.
The LCC is simple, clear, and it has good properties. It seems to hit a technical sweet spot: every extension of it which we have considered, provokes significant non-local changes. Often in computer science the trick is to find a useful balance between simplicity and expressivity. Perhaps the LCC does that.
References
[1] Franz Baader and Tobias Nipkow, Term rewriting and all that, Cambridge University Press, 1998.
[2] H. P. Barendregt, The lambda calculus: its syntax and semantics (revised ed.), North-Holland, 1984.
[3] Roel Bloo and Kristoffer Høgsbro Rose, Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection, CSN-95: Computer Science in the Netherlands, 1995.
[4] Mirna Bognar, Contexts in lambda calculus, Ph.D. thesis, Vrije Universiteit Amsterdam, 2002.
[5] James Cheney, A simpler proof theory for nominal logic, FOSSACS, Springer, 2005, pp. 379–394.
[6] Murdoch J. Gabbay, A new calculus of contexts, PPDP ’05: Proc. of the 7th ACM SIGPLAN int’l conf. on Principles and Practice of Declarative Programming, ACM Press, 2005, pp. 94–105.
[7], Hierarchical nominal rewriting, LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice, 2006, pp. 32–47.
[8] Murdoch J. Gabbay and Aad Mathijssen, Capture-avoiding substitution as a nominal algebra, ICTAC’2006: 3rd Int’l Colloquium on Theoretical Aspects of Computing, 2006, pp. 198–212.
[9] Murdoch J. Gabbay and A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001), no. 3–5, 341–363.
[10] Herman Geuvers and Gueorgui I. Jojgov, Open proofs and open terms: A basis for interactive logic, CSL, Springer, 2002, pp. 537–552.
[11] Masatomo Hashimoto and Atsushi Ohori, A typed context calculus, Theor. Comput. Sci. 266 (2001), no. 1-2, 249–272.
[12] Dimitri Hendriks and Vincent van Oostrom, Adbmal, CADE, 2003, pp. 136–150.
[13] Gueorgui I. Jojgov, Holes with binding power., TYPES, LNCS, vol. 2646, Springer, 2002, pp. 162–181.
[14] Samuel Kamin and Jean-Jacques Lévy, Attempts for generalizing the recursive path orderings, Handwritten paper, University of Illinois, 1980.
[15] Pierre Lescanne, From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions, POPL ’94: Proc. 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, 1994, pp. 60–69.
[16] Robin Milner, Joachim Parrow, and David Walker, A calculus of mobile processes, II, Information and Computation 100 (1992), no. 1, 41–77.
[17] Lawrence C. Paulson, ML for the working programmer (2nd ed.), Cambridge University Press, 1996.
[18] A. M. Pitts, Operationally-based theories of program equivalence, Semantics and Logics of Computation (P. Dybjer and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1997, pp. 241–298.
[19] A. M. Pitts and Murdoch J. Gabbay, A metalanguage for programming with bound names modulo renaming, Mathematics of Program Construction. 5th Int’l Conf. , MPC2000, Ponte de Lima, Portugal, July 2000. Proceedings (R. Backhouse and J. N. Oliveira, eds.), LNCS, vol. 1837, Springer-Verlag, 2000, pp. 230–255.
[20] A. M. Pitts and I. D. B. Stark, Operational reasoning for functions with local state, Higher Order Operational Techniques in Semantics (A. D. Gordon and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1998, pp. 227–273.
[21] Masahiko Sato, Takafumi Sakurai, and Rod Burstall, Explicit environments, Fundamenta Informaticae 45:1-2 (2001), 79–115.
[22] Masahiko Sato, Takafumi Sakurai, and Yukiyoshi Kameyama, A simply typed context calculus with first-class environments, Journal of Functional and Logic Programming 2002 (2002), no. 4, 359 – 374.
[23] Masahiko Sato, Takafumi Sakurai, Yukiyoshi Kameyama, and Atsushi Igarashi, Calculi of meta-variables, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings (M. Baaz, ed.), LNCS, vol. 2803, 2003, pp. 484–497.
[24] Francois Maurel Sylvain Baro, The qnu and qnuk calculi : name capture and control, Tech. report, Université Paris VII, 2003, Extended Abstract, Prépublication PPS//03/11//n16.
[25] Terese, Term rewriting systems, Cambridge Tracts in Theoretical Computer Science, no. 55, Cambridge University Press, 2003.
[26] Simon Thompson, Haskell: The Craft of Functional Programming, Addison Wesley, 1996.
[27] C. Urban, A. M. Pitts, and Murdoch J. Gabbay, Nominal unification, Theoretical Computer Science 323 (2004), no. 1–3, 473–497.
[28] Johan van Benthem, Modal foundations for predicate logic, Logic Journal of the IGPL 5 (1997), no. 2, 259–286.
[29], Higher-order logic, Handbook of Philosophical Logic, 2nd Edition (D.M. Gabbay and F. Guenthner, eds.), vol. 1, Kluwer, 2001, pp. 189–244.
Acknowledgements. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.