A typed context calculus.
This paper develops a typed calculus for contexts i.e., lambda terms with "holes". In addition to ordinary lambda terms, the calculus contains labeled holes, hole abstraction and context application for manipulating first-class contexts. The primary operation for contexts is hole-filling, which captures free variables. This operation conflicts with substitution of the lambda calculus, and a straightforward mixture of the two results in an inconsistent system. We solve this problem by defining a type system that precisely specifies the variable-capturing nature of contexts and that keeps track of bound variable renaming. These mechanisms enable us to define a reduction system that properly integrates&brg;-reduction and hole-filling. The resulting calculus is Church-Rosser and the type system has the subject reduction property. We believe that the context calculus will serve as a basis for developing a programming language with advanced features that call for manipulation of open terms. Copyright 2001 Elsevier Science B.V.
Introduction
A context in the lambda calculus is a term with a \hole" in it. The operation
for contexts is to ll the hole of a context with a term. For the purpose of
1 This is the authors' version of the article to appear in Theoretical Computer
Science.
current a-liation: Department of Information Science,
University of Tokyo, Bunkyo-ku, Tokyo 113-0033, Japan.
3 Atsushi Ohori's work was partly supported by the Japanese Ministry of Education
Grant-in-Aid for Scientic Research on Priority Area no. 275: \Advanced
databases," and by the Parallel and Distributed Processing Research Consortium,
Japan.
Preprint submitted to Elsevier Preprint 23 January 2001
explanation in this section, we write C[] for a context containing the hole
indicated by [], and write C[M ] for the term obtained from C[] by lling its
hole with M . For example, if C[]  (x:[]+y) 3 then C[x+z]  (x:x+z+y) 3.
As seen from this simple example, the feature that distinguishes this operation
from substitution of the lambda calculus is that it captures free variables. In
the above example, x in x z becomes bound when it is lled in the context
One motivation behind using contexts in the theory of lambda calculus is to
study properties of open terms. Since the behavior of an open term depends
on bindings of their free variables, in order to analyze its behavior, it is essential
to consider possible contexts in which the open term occurs. Study of
program analyses based on contexts such as observational equivalence [13,11]
yields important results in analysis of programming languages. In these and
most of other usages, context is a meta-level notion and its applicability to
programming languages has largely been limited to meta-level manipulation
of programs. We believe that if a programming language is extended with
rst-class contexts, then the extended language will provide various advanced
features that call for manipulation of open terms. Let us brie
y mention a few
of them.
Programming environment. In conventional programming environments, programs
must rst be compiled into \object modules", and they must then be
linked together to form an executable program. Moreover, an executable program
must be a closed term. If a programming environment can be extended
with the ability to link various software components dynamically, then its
exibility will signicantly increase. Since the mechanism of contexts we are
advocating oers a way of performing linking at runtime, it would provide a
basis for developing such an environment in a theoretically sound way.
Distributed programming. In distributed programming, one often wants to send
a piece of code to a remote site and execute it there. As witnessed by recently
emerging Internet programming languages such as Java [4], this feature will
greatly enhance the expressive power of distributed programming. One naive
approach to send a program is to pack all the necessary resources as a closure
and send the entire closure to the remote site. An obvious drawback to this
approach is ine-ciency. Since in most cases, communicating sites share common
resources such as standard runtime libraries, a better approach would be
to send an open term and to make the necessary binding at the remote site.
A typed calculus with rst-class contexts would provide a clean and type safe
mechanism for manipulating open terms.
First-class modules. A program using a module can naturally be regarded as
an open term containing free variables whose values will be supplied by the
module. One way of modeling a module exporting a set of functions F
through identiers f would therefore be regarding it as a context that
captures variables f bind them to F respectively. Using
(or \opening") a module then corresponds to lling the hole of the context
with the variables. This approach can provide a new foundation for
exible
module systems. In conventional languages with modules such as Modula-2
[18] and Standard ML [12], there is rigid separation between the type system
for modules and that of terms, and allowable operations on modules are rather
limited. Signicant potential advantage of the \modules-as-contexts" approach
is that modules can be freely combined with any other constructions available
in the language i.e. that modules are treated as rst-class citizens. Needless to
say, an actual module system must account for various features such as type
abstraction, type sharing and separate compilation, and the above simple view
alone does not immediately provide a proper basis for module systems. We
nonetheless believe that, when properly rened with various mechanisms for
module systems studied in literature, the above approach will open up a new
possibility for
exible module systems. Indeed, a recent work by Wells and
Vestergaad [17] shows a connection between their module language and our
context calculus.
The general motivation for this study is to develop a programming language
with rst-class contexts that can represent those features in a clean way.
Despite those and other potentially promising features of contexts, a language
with rst-class contexts has not been well investigated. Lee and Friedman
[10] proposed a calculus where contexts and lambda terms are two disjoint
classes of objects: contexts are regarded as \source code" and lambda terms
as \compiled code". This separation is done by assuming two disjoint variable
name spaces: one for lambda terms and one for contexts. As a consequence, in
their system, -reduction and ll-reduction are two disjoint relations without
non-trivial interaction. Dami [2] also announced a system for dynamic binding
similar to that of Lee and Friedman. While these approaches would be useful
for representing source code as a data structure, they do not allow contexts
of the language itself to be treated as rst-class values inside the language.
Kahrs [9] have developed a combinatory term rewriting system that is compatible
with contexts. However, contexts and hole-lling themselves are not
represented as terms within the system of terms. Talcott [16] developed an algebraic
system for manipulating binding structures. Her system includes suitable
mechanisms for manipulating contexts. In particular, it contains holes and
hole-lling which commutes with substitution. However, this is a meta-level
system, and the issue of representing contexts and the associated hole-lling
operation inside of the reduction system of lambda calculus is not addressed.
One of the features of contexts is to bind variables through holes. In this
sense, contexts are closely related to environments. Abadi et al. [1] developed
the -calculus for explicit substitutions. Their motivation is similar in spirit
to ours in that it internalizes a meta-level mechanism in the lambda calculus.
However, they did not address the problem of rst-class treatment of substitu-
tions. In revising the present article, the authors noticed that Sato et al. [14]
recently developed an environment calculus where environments are rst-class
values. In obtaining a con
uent calculus, they also address the problem of
variable binding in the presence of rst-class environments. Their solution to
this problem has some similarity to ours, although more general mechanisms
are needed for a calculus with rst-class contexts. We shall comment on this
in some detail when we describe our approach in the next section.
The goal of this paper is to establish a type theoretical basis for a programming
language with rst-class contexts by developing a typed context calculus
where lambda terms are simply a special case of contexts. In particular, contexts
and lambda terms belong to the same syntactic category sharing the
same set of variables, and substitution and hole-lling are dened on the same
syntactic objects. This property is essential for achieving various features explained
above. As observed in the literature [9,10], however, -reduction and
ll-reduction for contexts do not mix well, and a (naive) integration of them
yields an inconsistent system. The development of a meaningful calculus containing
-reduction and ll-reduction both acting on the same set of terms
constitutes a non-trivial technical challenge. Our main technical contribution
is to establish that such a calculus is possible. We prove that the calculus is
Church-Rosser and its type system has the subject reduction property.
To obtain a con
uent calculus, we have to overcome various delicate problems
in dealing with variables, and to introduce several new mechanisms in the
lambda calculus. Before giving the technical development, in the next section,
we explain the problems and outline our solution.
2 The Problem and Our Solution
It is not hard to extend the syntax of the (untyped) lambda calculus with
constructors for contexts. In conventional study, holes in contexts are name-
less. However, since our goal is to develop a calculus with rst-class contexts,
we should be able to consider a context containing other contexts. This requires
us to generalize contexts to contain multiple dierent holes, only one
of which is lled by each hole-lling operation. One way to dene a uniform
syntax for those contexts is to introduce labeled holes [9]. We use upper case
letters labeled holes. To incorporate operations for contexts as
terms in a lambda calculus, we introduce hole abstraction -X:M which abstracts
hole X in term M and creates a term that acts as a context whose
hole is X, and we introduce context application which denotes the
operation to ll the abstracted hole in M 1 with term M 2 . For example, the
context C[]  (x:[] represented by the term
and the context application term
denotes the term obtained by lling the hole in the context with x
call a subterm of the form (-X:M which contracts to the
term obtained from M 1 by lling the X-hole in M 1 with M 2 . Dierent from
the meta notation C[x application is a term constructor, which
allows us to exploit the features of rst-class contexts by combining it with
lambda abstraction and lambda application. For example, we can write a term
like
which is contracted to the above term.
The goal of this paper is to develop a type system and a reduction system
for the lambda calculus extended with the above three term constructors, i.e.,
labeled holes, hole abstraction and context application. The crucial step is the
development of a proper mechanism for integrating variable-capturing hole-
lling and capture-avoiding substitution in the lambda calculus. To see the
problem, consider the term
where we use dierent type faces (x, x and x) to distinguish dierent occurrences
of variable x to which we should pay attention. The above term has
two -redexes and one ll-redex. Our intention is that the inner x should be
captured by the x when it is lled in hole X, while the outer x is free. The
following reduction sequence produces the intended result.
However, reducing any of the -redexes before the ll-redex will result in a
dierent term. If we reduce the inner -redex before the ll-redex then the
binding of inner x will be lost, yielding x y. If we reduce the outer
-redex before the ll-redex, then the outer x is unintentionally captured by
y depending on the order of the ll-redex and
the other -redex.
To avoid these inconsistencies, we should redene the scope of lambda binding
to re
ect the behavior of terms of the form (-X:M 1 )M 2 . Suppose there is a
x in M 1 whose scope contains X. Since M 2 is lled in X, the scope of the
x also extends to M 2 . This property implies the following two requirements.
First, a -redex containing a hole X cannot be contracted. Secondly, when
substituting a term containing x for a free variable in M 2 , the x in M 1
and the corresponding variables in M 1 and M 2 need to be renamed to avoid
unwanted capture. In the above example, we should not contract the inner -
redex before hole-lling, and when we contract the outer -redex before hole-
lling, we should rename x and x before doing -substitution. The situation
becomes more subtle when we consider a term like
(w:    ((z:w(x
Since w is a variable, simple inspection of term w(x+z) no longer tells which
variables in x+z should be regarded as bound. However, variable-capture will
still occur when the hole abstraction is substituted for w.
Our strategy to solve this problem is to dene a type system that tells exactly
which variables should be considered bound, and to introduce a rened notion
of -equivalence that reconciles hole-lling and -substitution.
To tell which variables should be considered bound, we type a hole abstracted
term -X:M with a context type of the form:
where  1 is the type of the abstracted hole,  2 is the type of the term that will
be produced by lling the hole in the context with a term, and
describes the set of variables being captured when they are lled in the hole
X. We call those variables interface variables. For example,
would be typed as [fx : intg . int] ) int. However, if we simply list the set
of actual bound variables surrounding X in -X:M as interface variables in
its type, then we cannot rename those bound variables. Since -substitution
can only be dened up to renaming of bound variables, this causes a problem
in extending substitution to hole abstracted terms. For example, we cannot
rename bound variable x in the term -X:(x:X It should be noted
that the usual \bound variable convention" does not solve the problem. In the
lambda calculus, we can simply assume that \all bound variables are dierent
from the free variables" for each -redex. This is only possible when we can
freely rename bound variables. As well known in the theory of lambda calculus,
the above condition is not preserved by substitution. Even if we start with a
term satisfying the bound variable condition, anomalous terms like the above
may appear during -reduction.
To avoid this problem, we separate actual bound variables in -X:M and the
corresponding interface variables, and rene hole-lling to an operation that
also performs variable renaming. For manipulation of binding structures, Talcott
[16] developed a technique to pair a hole with a substitution. We use this
approach and annotate a hole X with a variable renamer , which renames
interface variables to the corresponding bound variables. We write X  for the
hole X annotated with . The above context can now be represented as the
typed term
where x is an interface variable and is renamed to a when it is lled in X. By
this separation, bound variable a can be renamed without changing the type
of this term. This allows us to achieve a proper integration of hole-lling and
-substitution with terms of the form -X:M . The semantics of hole-lling is
preserved by applying the renamer fa=xg to the term to be lled in X. For
example, we have the following reduction for the example before.
Yet another delicate problem arises when we consider the interaction between
substitution and a term of the form MN . This construct may bind some
variables in N . In order to determine those bound variables, we need to annotate
this construct with the set of variables in N that will be bound by forming
this term. Since this set must correspond to the set of interface variables of
the context term M , a naive attempt would be to annotate the constructor
MN with this set. A subterm of the example term might then be represented
as the term (-X:(a:X fa=xg
z). As we noted earlier,
the variable x must be treated as bound variable. This implies that, when
combining -substitution, this variable needs to be renamed. Unfortunately,
this is impossible for terms of the form w fxg
we cannot rename the corresponding interface variables of the hole abstracted
term that will be substituted later for w. So, again we need to separate the
set of interface variables in the type of hole abstracted term and the set of
variables that will be captured when they are lled in the hole of the context.
To achieve this, we annotate the constructor for context application with a
renamer  and write M  N . The renamer  renames variables in N that are
to be bound by hole-lling to the corresponding interface variables in the hole
abstracted term. Its eect is obtained by composing it with the renamer of
the hole. Now the bound variables in N are independent of the corresponding
interface variables, we can perform bound variable renaming. The above
example can be correctly represented by the following term:
(b
In this term, both a and b are bound variables, which can be renamed without
changing the typing of the term. Again, the semantics of hole-lling is
preserved by applying the composition fa=xg ? fx=bg( fa=bg) of renamers
fa=xg and fx=bg to the term to be lled in X. The following is an example of
reduction involving renamer applications.
(b
3:
Another slightly more general alternative to M  N is to make a renamer as a
term constructor [:N ] and introduce a new type constructor
n g .  ] for this constructor. We believe that this is also possible. In our
system, however, we shall not take this approach, since the only elimination
operation would be (the modied version of) the hole-lling and therefore
the additional
exibility is not essential in achieving our goal of rst-class
treatment of contexts.
Based on the strategies outlined above, we have worked out the denition of
the type system of the calculus, and its reduction system, and proved that the
type system has the subject reduction property and that the reduction system
is Church-Rosser.
In the work by Sato et al. [14], a type-theoretical approach similar to ours was
taken in order to identify the set of free and bound variables. However, their
system does not fully address the problem of mixing such a construct with -
substitution. Their calculus contains a term constructor e 1 intuitive
meaning is to evaluate e 2 under the bindings provided by the environment e 1 .
However, the reduction for nested application of this construction is restricted
to variables, and does not act on general terms. Because of this restricted
treatment, the subtle problem of -equivalence explained above does not arise
in their system.
The careful reader may have noticed that some aspects of contexts can already
be represented in the lambda calculus. If one can predetermine the exact order
of variables exported by a context and imported by a term to be lled in the
context, then one can represent hole abstractions and context applications
simply by functionals as seen in the following encoding scheme. A hole-lling
of the form:
can be represented as a lambda term of the form:
However, such encoding eliminates the ability to bind variables through names,
and it therefore signicantly reduces the benets of rst-class contexts we have
advocated in the introduction.
The rest of the paper is organized as follows. In Section 3 we dene the context
calculus. Section 4 denes the reduction system and proves the subject reduction
property and Church-Rosser property of the calculus. Section 5 concludes
the paper with the discussion of further investigations. Appendix contains
proofs of some of the lemmas.
3 The Calculus
We use the following notation for functions. The domain and the codomain
of a function f are written as dom(f) and cod(f) respectively. We sometimes
regard a function as a set of pairs and write ; for the empty function. Let f; g
be functions. We write f ; g for f [ g provided that dom(f) \ dom(g) = ;. We
omit \;" if g is explicitly represented as a set, writing ff: : :g for f :g. The
restriction of a function f to the domain D is written as f j D .
The set of types (ranged over by ) of the calculus is given by the syntax:
where b ranges over a given set of base types, and ranges over variable type
assignments each of which is a function from a nite set of variables to types.
We let x range over a countably innite set of variables; we let X range over
a countably innite set of labeled holes; and we let  range over variable
renamers each of which is a function from a nite set of variables to variables
denoted by fy 1 =x g. Let be a renamer. To
avoid unnecessary complication, we assume that fy i ng \ fx i
n). That is, a renamer changes each name in
the domain of the renamer to a fresh name, if it is not an identity. A renamer
is extended to the set of all variables by letting In
what follows, we identify a renamer with its extension. However, we maintain
that the domain dom() of a renamer  always means the domain of the
original nite function . The composition  1 ?  2 of two variable renamers  1
and  2 is the function  such that
The set of (unchecked) terms (ranged over by M) of the calculus is given by
the syntax:
A term -X:M binds the hole X in M . The denitions of bound holes and free
holes are given similarly to the usual denition of bound variables and free
variables in the ordinary lambda calculus. We write FH(M) for the set of
Fig. 1. The sets of free and bound variables
free holes in M . Since -X is the only binder for holes, this does not create
any of the subtle problems we have explained for variables in our calculus,
and therefore we can safely assume -renaming of bound holes just as in -
congruence in the ordinary lambda calculus. In what follows, we regard terms
as their -equivalence classes induced by bound holes renaming.
The set of free variables, denoted by FV (M ), and that of bound variables
of M , denoted by BV (M) are given in Figure 1. These denitions correctly
model the eect of context application terms of the form M 1   M 2 which binds
the variables in dom() in M 2 .
In addition to the sets of free and bound variables, we need to distinguish
three other classes of variables. Let M be a term containing a hole X  . The
variables in cod(), which we call free variable candidates, behave similarly
to free variables if they are not abstracted in M ; The variables in the set
dom(), which we call interface variable candidates, are the source of interface
variables. To see the last one, consider a term which contains M 1   M 2 . The
variables in cod(), which we call exported variables, are used to match the
variables exported by the context M 1 with bound variables in M 2 . The formal
denitions of the set FV C(M) of free variable candidates of M , and the set
IV C(M) of interface variables candidates of M are given in Figure 2, and the
denition of the set EV (M) of exported variables of M is given in Figure 3.
Fig. 2. The sets of free variable candidates and interface variable candidates.
Fig. 3. The set of exported variables
We dene the set PFV (M) of potentially free variables of M as
We are now in the position to dene the type system of the calculus. Since
a term may contain free holes as well as free variables, its type depends not
only on types of variables but also on types of free holes. A hole type is
determined by a triple ([ .  ]; ) consisting of type  of a term to be lled,
type assignment describing the set of interface variables and their types,
and variable renamer  which is used to keep track of the correspondence
between bound variables and interface variables. While describes the set
of all abstracted variables,  describes the set of free variable candidates to
be abstracted. We for the triple obtained from
([ .  ]; ) by abstracting x, whose denition is given below.
.  ]; )
This operation is extended to type assignments as follows:
A hole type assignment , ranged over by , is a nite function which assigns
a hole to a triple ([ .  ]; ) describing the type of the hole, and we call the
variables in dom() interface variables. We write Clos(; ) for the hole type
assignment dom()g. We write  for the hole type
assignment g.
The type system of the calculus is dened as a proof system to derive a typing
of the form:
which indicates that term M has type  under variable type assignment and
hole type assignment . The set of typing rules is given in Figure 4.
Some explanations are in order.
Rule (hole). Since X is not surrounded by any  at this moment, the associated
type assignment in the hole type assignment is empty, and the set of
variable candidates of X is specied by . They will be abstracted by
the rule (abs) and (ll).
Rule (abs). Lambda abstracting x not only discharges x from the type hypothesis
for the term M , but also extends the set of interface variables
for each hole in M with corresponding x 0 . The later eect is represented by
the operation Clos(fx : g; ), which extends each appearing in .
Rule (ll). By forming the term M 1  fx 0=x 1 ;:::;x 0
=xng M 2 , each x i in M 2 becomes
bound, and the set of interface variables of each hole in M 2 is extended
with it. This property is modeled by discharging each x i from the typing
judgment for M 2 and abstracting it from  2 . This rule is similar to the
one for a \closure" i.e., a term associated with an explicit substitution, in
-calculus [1].

Figure

5 shows an example of typing derivation.
(abs)
(app)
(ll)
if dom() \ fx 0
Fig. 4. The Type System
Fig. 5. Example of Typing Derivation
In our calculus, each free hole occurs linearly in a well-typed term. If multiple
occurrences of a hole are allowed, then they could have dierent interface
variables. This would considerably complicate the conceptual understanding
of contexts as well as the type system. The linearity condition is ensured by the
rule (hole), the condition implied by the notation  1 ;  2 in rules (app), (ll),
and the property that there is no rule for adding redundant hypothesis to .
The following lemma is easily shown by induction on the typing derivations.
dom(). Moreover, each free
hole appears exactly once in M .
The following standard properties also hold for this type system, and can be
easily shown by induction on the typing derivations.
Lemma
Lemma
Lemma 7 If X fx 0
=yng occurs in M , fz
ng \ fx 0
. ]; fy 0
. ]; fy 0
M 0 is obtained from M by substituting X fx 0
=yng
for
=wng .
4 The Reduction System
To dene the reduction relation, we need to dene substitution and hole-lling
operations. In the ordinary lambda calculus, substitution can be dened modulo
-congruence, which allows us to simply assume that unwanted variable
capture will not happen. In our calculus, since we have not yet obtained -
congruence, we need at rst to dene substitution as an operation on syntactic
terms (not on equivalence class).
We write fM 0 =xgM for the term obtained by substituting M 0 for any free
occurrence of x in M . The following lemma shows that substitution preserves
typing under a strong variable hygiene conditions.
Lemma
The proof is deferred to the Appendix. As in the standard denition of sub-
stitution, we have the following composition lemma:
y.
As we have explained earlier, hole-lling involves application of the variable
renamer associated with the hole to the term being lled. To dene hole-lling,
we extend a variable renamer  to a function  on terms as follows:
We have the following renaming lemma, whose proof is deferred to the appendix

Hole-lling is dened as a combination of variable renamer and substitution.
We write M [M 0 =X] for the term obtained from M by syntactically substituting
the term (M 0 ) for X in M where  is the variable renamer associated with X.
Its denition is obtained by simply extending the following clauses according
to the structure of M .
From this denition and the property of typing, it is easily seen that if ;  '
. The following lemma shows
that hole-lling preserves the typing.
Lemma
The proof is deferred to the appendix.
The following is the composition lemma for the hole-lling, where IV CX (M)
denotes the domain of the variable renamer on the shoulder of hole X in M .
Lemma 12
PROOF. If dom( 1 )\(PFV (M)ndom( 2 M)).The notion of -congruence in our calculus is now dened as the congruence
relation on the set of well typed terms generated by the following two axioms:
=yng fy 1 =x
if each y i 62 BV
The following lemma shows that -renaming preserves typing, which is proved
by induction on the derivation of M using lemma 10.
-congruence allows us to rename bound variables whenever it is necessary.
In what follows, we assume the following variable convention for our calculus:
bound variables are all distinct and the set of bound variables has no intersection
with the set of interface variable candidates, the set of potentially
and the set of exported variables.
Under this variable convention, the reduction axioms of our calculus are given
as follows:
ll
In the axiom (), the restriction FH(M 2 is needed to ensure that each
linearly. The restriction FH(M 1 is needed to maintain
the binding generated by x for the holes in M 1 . Since in our calculus contexts
are represented not by terms with free holes but by hole abstracted terms, this
does not restrict rst-class treatment of contexts.
The one-step reduction relation M ! N is dened on the set of well typed
terms as: is well typed and M 0 is obtained by applying one
of the two reduction axioms to some subterm of M . We write M
the re
exive, transitive closure of !.
For this reduction, we have the following desired results.
Theorem 14 (Subject Reduction) If ;
(app)
(ll)
Fig. 6. Denition of the Parallel Reduction
PROOF. This is a direct consequence of lemmas 7,8, 11 and 13. 2
Theorem 15 (Con
uence) For any well typed term M , if M
then there is some M 3 such that M 1
The proof is by using the technique of parallel reduction due to Tait and
Martin-Lof. The parallel reduction relation of our calculus, written ! !, is
given in Figure 6.
From this denition, it is easily seen that the transitive closure of the parallel
reduction coincides with the reduction relation of the calculus (
!). To prove
the theorem, it is therefore su-cient to prove the diamond property of ! !. To
show this, we follow Takahashi [15] and prove the following stronger property.
Lemma 16 For any well typed term M , there exists a term M  such that if
In the lemma above, M  denotes the term obtained from M by parallel reducing
all the possible redexes of M , whose denition is given Figure 7.
The proof of lemma 16 is by induction on the derivation of ;
using the following lemmas:
1 is not a lambda abstraction
1 is not a hole abstraction
Fig. 7. Denition of M
Lemma
terms M;M 0 such that fx :
PROOF. We proceed by induction on the derivation of M ! !M 0 . Here we
only show the cases (betred) and(lred).
Case (betred)
By the induction hypothesis,
.
Therefore by the rule(betred),
1 . The rest of
this case is by lemma 9.
Case (lred)
By the induction hypothesis,
.
Therefore by the rule(lred),
can assume x 62 dom() by the hygiene condition. Then,
Lemma
PROOF. We proceed by induction on the derivation of M ! !M 0 . We only
show the crucial case (lred).
Case (lred)
By the induction hypothesis,
.
2 =X] by
the rule (lred). Since fx; x 0 g\BV
Therefore ((fx 0 =xgM 0
for any terms M;M 0 such that
n .
PROOF. We proceed by induction on the derivation of M ! !M 0 . Here we
only show the cases (hole) and (lred).
. By repeated application of lemma 18.
Case (lred)
(Y 6 X).
Suppose
. By the
induction hypothesis, M 1 [M
Therefore by the rule(lred),
The rest of this sub-case
is by (M 0
. By the induction hypothesis,
Therefore by the rule(lred),
Therefore by lemma 12,
This completes the proof of theorem 15.
Conclusions
We have developed a typed calculus for contexts. In this calculus, contexts and
lambda terms share the same set of variables and can be freely mixed (as far
as they type-check). This allows us to treat contexts truly as rst-class values.
However, a straightforward mixture of -reduction and ll-reduction results
in an inconsistent system. We have solved the problem by developing a type
system that precisely species the variable-capturing nature of contexts. The
resulting typed calculus enjoys the subject reduction property and Church-Rosser
property. We believe that the typed context calculus presented here
will serve as a type theoretical basis for developing a programming language
with advanced features for manipulation of open terms. There are a number
of interesting topics that merit further investigation. We brie
y discuss some
of them below.
Integration with Explicit Substitution. In our calculus, -contraction is restricted
to those redexes that do not contain free holes. While this does not
restrict rst-class treatment of contexts, removing this restriction will make
the reduction system slightly more general. As we have noted earlier, one reason
for this restriction is that if we contract a -redex containing a free hole,
then the binding through the hole will be lost. One way of solving this problem
would be to integrate our calculus with -calculus of Abadi et al. [1], and
to generalize variable renamers to explicit substitutions. Dowek et al. [3] considered
a calculus containing holes and grafting, which roughly corresponds to
hole-lling, and developed a technique to mingle capture-avoiding substitution
with grafting by encoding them in a calculus of explicit substitution using de
Bruijn notation. Although their calculus does not contain a term constructor
for context application and therefore their technique is not directly applicable
to our calculus, we believe that it is possible to extend their technique for our
calculus by translating all the machinery we have developed for our calculus
into de Bruijn notation. However, such translation would signicantly decrease
the
exibility of access to exported variables by names. It should also be noted
that the notion of de Bruijn indexes presupposes -equivalence on terms, and
therefore dening the context calculus using de Bruijn notation requires the
mechanisms (or something similar to those) for obtaining -equivalence we
have developed in this paper.
Programming Languages with Contexts. Our motivation is to provide a basis
for developing a programming language with the feature of rst-class contexts.
The context calculus we have worked out in this article guarantees that we
can have such a typed language with rst-class contexts. In order to develop
an actual programming language, however, we need to develop a realistic evaluation
strategy for the calculus. Our preliminary investigation shows that the
usual call-by-value evaluation strategy using closures can be extended to our
calculus. A more challenging topic is to develop a polymorphic type system
and a type inference algorithm for our calculus, which will enable us to develop
an ML-style programming language with the feature of contexts we have
advocated. One crucial issue is the
exible treatment of context types. In the
current denition, the constructor  fx1=x 0;:::;x n=x 0
n g is annotated with a variable
renamer. This reduces the
exibility of the calculus. A better approach
would be to rene the type system so that if  0 then a context of type
can be used whenever a context of type [ .
One of the authors has recently developed an ML-style language with rst-
class contexts [5] where an ML-style polymorphic type system, a call-by-value
operational semantics and a type inference algorithm are given.
Relationship with formula-as-type notion. It is intuitively clear that a context
represented as a term in our calculus has constructive meaning. An important
question is to characterize this intuition formally in the sense of Curry-Howard
isomorphism [7]. This would lead us to a new form of proof normalization process
corresponding to our ll-reduction. Since the context calculus is Church-
Rosser, it should be possible to develop a proof system that is conservative
over the conventional intuitionistic logic and supports a proof normalization
process corresponding to ll-reduction. The authors recently noticed that there
is an intriguing similarity between the proof system of typings in the context
calculus and Joshi and Kulick's partial proof manipulation system [8] which is
used to represent linguistic information. Another relevant system is Herbelin's
lambda calculus isomorphic to a variant of sequent calculus, where proofs of
certain sequents are interpreted by applicative contexts [6]. These results suggest
some interesting connections between context calculus and proof systems.

Acknowledgements

The authors thank Pierre-Louis Curien, Laurent Dami, Yasuhiko Minamide,
Didier Remy, Masahiko Sato and anonymous referees for their careful reading
of a draft of this paper and numerous useful comments. The second author
also thanks Shinn-Der Lee, and Dan Friedman for insightful discussions on
contexts.



--R

Explicit substitutions.
A lambda-calculus for dynamic binding

The feel of Java.

A lambda-calculus structure isomorphic to sequent calculus structure
The formulae-as-types notion of construction
Partial proof trees as building blocks for a categorized grammars.
Context rewriting.
Enriching the Lambda Calculus with Contexts: Towards A Theory of Incremental Program Construction.
Fully abstract models of typed

LCF considered as a programming language.
Explicit Environments.
Parallel reductions in
A theory of binding structures and applications to rewriting.
Con uent Equational Reasoning for Linking with First-Class Primitive Modules
Programming in Modula-2
--TR
Programming in MODULA-2 (3rd corrected ed.)
A theory of binding structures and applications to rewriting
Parallel reductions in MYAMPERSANDlgr;-calculus
Enriching the lambda calculus with contexts
A lambda-calculus for dynamic binding
The Definition of Standard ML
The Feel of Java
Explicit Environments
First-Class Contexts in ML
A Lambda-Calculus Structure Isomorphic to Gentzen-Style Sequent Calculus Structure
Context Rewriting
Higher-order Unification via Explicit Substitutions

--CTR
Brigitte Pientka, Functional Programming With Higher-order Abstract Syntax and Explicit Substitutions, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.7, p.41-60, June, 2007
Roger Keays , Andry Rakotonirainy, Context-oriented programming, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA
Yosihiro Yuse , Atsushi Igarashi, A modal type system for multi-level generating extensions with persistent code, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy
Christian Urban , Andrew M. Pitts , Murdoch J. Gabbay, Nominal unification, Theoretical Computer Science, v.323 n.1-3, p.473-497, 14 September 2004
Murdoch J. Gabbay, A new calculus of contexts, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.94-105, July 11-13, 2005, Lisbon, Portugal
Makoto Hamana, Term rewriting with variable binding: an initial algebra approach, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.148-159, August 27-29, 2003, Uppsala, Sweden
Steven E. Ganz , Amr Sabry , Walid Taha, Macros as multi-stage computations: type-safe, generative, binding macros in MacroML, ACM SIGPLAN Notices, v.36 n.10, October 2001
Gavin Bierman , Michael Hicks , Peter Sewell , Gareth Stoyle , Keith Wansbrough, Dynamic rebinding for marshalling and update, with destruct-time ?, ACM SIGPLAN Notices, v.38 n.9, p.99-110, September
Makoto Hamana, An initial algebra approach to term rewriting systems with variable binders, Higher-Order and Symbolic Computation, v.19 n.2-3, p.231-262, September 2006
alpha-renaming;lambda-calculus;type system;context