A NEW Calculus of Contexts
ABSTRACT
We study contexts (terms with holes) by proposing a ‘-calculus with holes’. It is very expressive and can encode programming constructs apparently unrelated to contexts, including objects and algorithms in partial evaluation. We give proofs of confluence, preservation of strong normalisation, principal typing for an ML-style Hindley-Milner type system, and an applicative characterisation of contextual equivalence. We explore the limitations of the calculus including further applications, and discuss how they might be tackled.1
Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: lambda calculus and related systems
General Terms: Theory.
Keywords: Calculi of contexts, Functional programming, Binders, Lambda-Calculi, Nominal Techniques.
1. INTRODUCTION
This is a paper about contexts. We shall study them by proposing a “-calculus for contexts” which we call the calculus of contexts ( is pronounced ‘new’). In this calculus, contexts are terms (first-class values) and can be passed as arguments to functions, applied to other terms, and so on.
We prove confluence (using results from [36]), preservation of strong normalisation with respect to the untyped -calculus, give a Hindley-Milner style type system [9] with subject reduction, and an applicative characterisation of contextual equivalence (drawing on techniques in [10] and [29]). This small library of results is chosen to make the NEW context calculus a respectable implementation environment because respectively the calculus has ‘semantic content’ (normal forms are unique if they exist), is ‘conservative’ over a familar programming language, can be implemented as an extension of a (toy core of) ML without destroying the type-system, and programs can be optimised up to preserving extensional behaviour.
What are the technical design issues?
A context is a term with a ‘hole’. The canonical example in the untyped -calculus is --. (We use ‘’ to denote syntactic -equality.)
A term may be placed in the hole -, e.g. and if then . This cannot be modelled inside the calculus by because -reduction avoids capture. Our idea is to treat the hole as a variable which is stronger than and and for which substitution does not avoid capture of weaker variables. For example, .
But now -equivalence is a problem; if
then , giving non-confluent reductions. Dropping -equivalence entirely is too drastic because some capture-avoidance, as in , should be legitimate.
Existing calculi of contexts include and [31] by Sato et al.2 which seems closest to ours because they have a hierarchy of variables (see below). Some other work [22, 15, 30] use a type system which may prove related to our freshness contexts (see below) though the connections are unclear. Finally we mention of Bognar’s thesis, which also contains [7, Section 2] an essay on the issues involved in designing context calculi, as well as an extensive literature survey.
How does our calculus relate to the existing literature?
The central point of all calculi of contexts we know of, including our own, is the interaction of -equivalence with holes, and the resulting problems with scope and abstraction. Solutions include clever control of substitution and evaluation order, and types to prevent ‘bad’ -conversions.
Technically, this paper contains yet another solution and we are not primarily interested in how that solution works though of course we do describe it in detail. Broadly speaking, its novelty is to imports ideas from previous work by the author and others, known under the umbrella term of ‘Nominal techniques’ (notably with Urban and Pitts on Nominal Unification [35], and with on Nominal Rewriting [21, 11]). These ideas were designed to manage -equivalence; crudely put, we simply applied them to a new problem.
Why do this and why make another context calculus?
First, it has been our personal belief for some time that contexts are significantly underrated.
Our inspiration came from specific technical issues which arise with existential variables in the theorem-proving environment Isabelle [27], and from technical work by Pitts [29] on (what we can slightly inaccurately call) applicative characterisations of contextual equivalence. The problem with existential variables is that the right sequent introduction rule requires us to pick a specific fresh to make the rest of the proof above Γ work. This is silly (we want to build interactively as we construct the rest of the proof). Therefore the designers of Isabelle introduced existential variables ?. These resemble ‘holes’ in -calculus contexts, but this is somehow disguised because they are Skolemised over the free variables they may contain.
With Pitts’s work, we would claim that contexts — and not terms — are the true object of study. They occur in the definition of contextual equivalence which Pitts uses (originally due to Lockwood Morris), and again with Pitts’s notion of ‘continuation’, which is actually a structured form of a Felleisen-style evaluation context [29, Page 15]. It always seemed to us naughty to have so many contexts around without saying what they are in some more abstract sense.
So our answer is ‘here is a calculus of contexts’. Contexts and ‘ordinary terms’ are on an equal footing as terms in this calculus; indeed so are substitutions and many other things. Results about contexts and substitutions become results about suitable relations (such as -equivalence or contextual equivalence) between the contexts represented as terms in the calculus.
This is not a denotational answer in quite the same sense as some other work (compare with Hamana [14] and possibly [28]) but for many applications a calculus is just what we want: for example Isabelle theories are encoded in Isabelle/Pure, which is a typed -calculus with a simple theory of equality.
But there is more. The NEW context calculus, with its elements of Nominal techniques and hierarchy of variables, gives us fine-grained control of substitution. It turns out that we can apply this to implement constructs which a priori have nothing to do with contexts. We shall explore notions of global state (for general references [2]), objects with forms of in-place update [1], and interesting interactions with partial evaluation [8]; in the conclusions we look at other potential applications such as staged programming (MetaML [26]) and logic and unification.
We are not aware of claims for such implementations made of other context calculi. Perhaps they could implement some or all of our examples (or not; our hierarchy of variables is shared only with [31] and makes a great contribution to expressivity). A different paper might try to make a fair comparison between the different calculi (probably by translating them into ours of course!) and in so doing gain some measure of their relative expressivities. However, we feel it is our small library of meta-properties listed above which distinguishes our work from other context calculi. We do not know, for example, of any other applicative characterisation of contextual equivalence.
Therefore, our motivation writing this paper is not really to produce a calculus of contexts even though that was our original motivation and this may be sufficient motivation for some readers. We aim further for an implementation environment with good meta-properties and fine-grained control of substitution (thanks to the use of Nominal techniques applied to other ideas already in the literature). We hope that this calculus or something resembling it will provide a convenient environment in which to implement and prove things about other systems which benefit from fine control of substitution including the non-capture-avoiding kind.
In summary: all computation can be coded in the untyped -calculus. Some questions then are: (1) can we optimise programs, (2) can we statically analyse them, and (3) can we prove properties of an implementation? If not, what extended calculus allows us to do so. This paper presents an extension of the untyped -calculus with constructs to manage capture in substitution, and our examples and meta-properties are chosen precisely to at least suggest that we should be able to answer (1) to (3) of some useful systems of independent interest.
Besides Nominal Techniques mentioned above, our calculus comes out of a very long tradition of calculi for studying programming. Our calculus has explicit substitutions, see [19] for a survey; our particular treatment of substitution is deliberately simple-minded but still subtle because of interactions with the rest of the language. We give a translation of possibly open terms of the untyped -calculus which preserves strong normalisation.
We do not directly import ideas from other calculi of contexts because our management of -equivalence is based on Nominal techniques with are novel to this field; we do share the hierarchy of variables with one other work [31] and the separation of scope and binding in a -calculus appears in one other (unpublished) work we know of [33]. For our meta-properties, we have modelled our proofs on work which we cited above.
2. BASIC SYNTAX AND BASIC EXAMPLE REDUCTIONS
The syntax of the context calculus is easy to construct. We formally define reductions in the next section.
We suppose a countably infinite set of disjoint infinite sets of variables , , . . . , where we write for 1. We say that has level . The syntax is then given by:
We call an explicit substitution. We call an abstraction. We equate terms up to -equivalence on in (but not in or ). We say ‘ is a binder’ (and and explicit substitution are not).
For the moment we ignore (and so -equivalence) and concentrate on examples of the interaction of the hierarchy of variables with explicit substitutions.
We call a variable stronger than another when , that is, when it has a strictly higher level. We say they have the same strength when they have the same level. For example, is stronger than . There is no particular connection between variables of different levels with the same name, for example and .
We now consider some example reductions. We write for variables of level 1, and for variables of level 2.
(Ordinary) -reduction.
The explicit substitution implements -reduction in a standard way. Here and later we colour subterms under an explicit substitution, to help visualise the brackets.
Context substitution. In an explicit substitution consider the case (a -abstraction of a level 2 variable by a level 1 variable), , and . The intended operational behaviour is
The explicit substitution moves under the and acts on the , without capture-avoidance. This kind of substitution (implemented here as a rewrite) is called context substitution or grafting. This example demonstrates that we cannot just equate terms up to -equivalence, at least not blindly; if and were equal terms, context substitution would make no sense.
Explicit substitutions on variables. Canonical reductions (and non-reductions) of terms of the form where and are variables and is any term are:
A substitution of a strong variable on a weak variable, or two different variables of the same strength, ‘evaporates’. A substitution of a variable by itself is a substitution. A substitution of a weak variable on a stronger variable does not in general reduce; we say is suspended on . (The precise rules a and # are introduced below, but first we must introduce binding, and we give some more examples before that.) A canonical reduction illustrating the use of suspensions, is as follows:
So we can think of for as a strong hole with a substitution on a weaker waiting for it to be filled.
Substitutions and -abstraction. A -abstracted atom can never get substituted for, not even by a stronger substitution. For example
Substitutions as terms. Substitution is not a term and so cannot be made an argument of a function. Using suspensions we can express this: for example encodes as a term. Reduction is not possible since is stronger than . Contrast this with , which reduces in one step to . Define true , false , and Id . Here is a program which takes a substitution, a truth value, and an argument, and applies the substitution or not according to the truth value: Id Here is an example of reduction using :
To encode substitutions for stronger variables (we call these stronger substitutions), the general scheme is . This is the first real use of level three variables, which are useful to encode the ‘context substitution’ as a term.
We hope this clarifies everything except for binding. We shall now give a formal definition of the syntax and operational semantics of the context calculus, all in a block, and then we return to the examples.
3. FORMAL DEFINITION OF THE NEW CONTEXT CALCULUS
We inherit the definitions, notation, and terminology of the beginning of the last section. Briefly, assume an infinity of disjoint sets of variables for 1 and say that has level . The syntax is:
is the only binder and we work up to -equivalence between variables of the same level bound by . So for instance but . It may also be convenient to allow constants, e.g. for arithmetic or truth-values. They behave much like variables which we do not abstract or substitute for and we tend to ignore them. Note that is not a term.
Reduction rules are given on terms as follows:
means ‘ and are distinct symbols’. means ‘ does not occur in ’. We use these conventions silently henceforth. The intuition of # is ‘ cannot occur free in ’; defining and explaining its formal meaning is for the rest of this subsection. in varies over all levels and in varies over all variables of that level, so the side-condition on a is ‘for all variables weaker than , if # then (see the end of 4.1 for further discussion). In p and henceforth we write as , associating application to the left (as is standard).
Many of these rules are familiar from -calculi of explicit substitutions (see [19] for examples). # is reminiscent of Bloo’s ‘garbage collection’ [6] and we refer the reader there for a further discussion. The rules involving are scope extrusion rules, e.g. as in the -calculus [24].
Call a pair of a variable and a term # a freshness assertion, we let vary over them. If is a variable and it a primitive freshness assertion. Call a possibly infinite set Γ of primitive freshness assertions a freshness context.
Define a notion of entailment between freshness contexts and freshness assertions by:
We say # is entailed by Γ and write Γ #, when # can be derived from Γ using these rules.
Read bottom-up these are rewrite rules on (sets of) freshness assertions. They reduce assertions to a normal form which is a set of freshness contexts. For example # reduces to #, and # reduces to the empty set. Γ # holds when Γ.
Here are some examples/comments.
Γ # always if , or if but . This expresses the intuition that a stronger hole can never ‘occur in’ a weaker one, and that two different holes of the same strength are different.
Γ #. We say that abstracts and this expresses a natural intuition.
Γ # if Γ #. This expresses an intuition that substitution abstracts away all in .
Γ # is derivable from Γ if ## Γ. This expresses the intuition that ‘if is not free in and is not free in , then is not free in applied to ’. Here and are stronger variables which may for example ‘become’ , in the sense that may occur in a subterm of a larger term containing substitutions .
A freshness context Γ induces a reduction relation Γ , we may just write , on the syntax of the calculus. It is given by reading the conditions # and as Γ # and Γ #.
(Subject reduction for #). If Γ # and Γ then Γ #.
By case-analysis on the rewrites defining and on the position in which the rewrite occurs in .
# controls abstraction; what a variable can be replaced by, and what can be done under a and an explicit substitution. This is distinct from from scope (and literal binding in the syntax), which remains relatively simple and is controlled by ( is the only binder, in the traditional sense of renaming variables). We discuss this further in the rest of the paper.
We note that # resembles Bloo and Rose’s ‘garbage collection rule’ [6]. The deduction rules for # and explicit substitutions implement a notion of unabstracted variable which they reject [6, Remark 2.3] for reasons we seem to avoid because of the separation of binding and abstraction.
3.1 Freshness #, -equivalence, and
Why is all the apparatus of # necessary; why not use ? The following two rewrites would be valid:
These rewrites are not confluent (and we want confluence). The problem rewrite is the first one, where the strong variable (which contains only in its raw syntax, and in particular does not contain ) comes under an abstraction by a weak variable and is then substituted for by non-capture-avoiding context substitution.
We use freshness assumptions to manage abstraction. Fix some freshness context Γ and read the side-conditions ###, in the definition of reduction from the previous subsection, as meaning Γ . Each freshness context induces a different reduction relation.
By way of example, we re-consider the example reductions above in the universal freshness context Θ # , and the empty freshness context Φ .
In the universal freshness context Θ the term above rewrites as follows:
Here cannot reduce (by a) because Θ # and Θ #.
In the empty freshness context Φ,
The first reduction cannot take place because Φ #.
(We note in passing that we can emulate a constant with a variable such that # always.)
Is there a canonical freshness context between the extremes of Θ and Φ? We need some notation: given a set of variables write max for the level of a strongest variable, if such a variable exists, and min for the level of the weakest. For example, maxΦ 0 and max 3. maxΘ is not well-defined. Given any set of variables write # for the set #. Write Γ # for the assertion Γ #.
A freshness context Γ has sufficient freshnesses when for all finite sets of variables and all , there exists with Γ #, and for all min, there exists with Γ #.
So Γ has two kinds of freshness: internally, for any finite set we can find a variable which Γ promises is fresh for them, but also externally we can find a variable fresh in the sense that Γ knows nothing about its relation to (provided the variable is no stronger than any element of , in which case its freshness may be deducible from the derivation rules, e.g. #).
It is not hard to inductively construct a Γ with sufficient freshnesses inductively:
Let and .
Given and , enumerate all subsets of . For each and max 1 choose distinct fresh . For each and min choose distinct fresh . Let #and let .
Iterate and let Γ (actually, we must take the normal form with respect to the deduction rules for #).
If Γ has sufficient freshnesses then for any term and any there exists such that . Similarly for a finite set of terms. We may say is sufficiently fresh, in the case that the other parameters are fixed or understood.
Let be all variables mentioned in and choose such that . It is not hard to prove by induction on that is derivable.
For the rest of this paper, we silently fix a context Γ with sufficient freshnesses. Thus when we write ‘#’ we mean ‘Γ #’. This is just the usual assumption that ‘we can always find a fresh variable’. The hierarchy of strengths of variables created problems which we solved with an explicit freshness context, so we make explicit assumptions about it; but the associated technical details work as we would expect so we tend to retain informal practice and terminology.
3.2 Intuitive ‘facts’ and silly reductions
We might expect that if then #. This is not true; # is not true in general, only for those and such that # is in the context.
Conversely, it is not true that if # then , a counterexample is . We leave it to the reader to check the derivation of # using the rules defining #.
Why do rules for all use inequality and , whereas rules for # use #? Intuitively, regulates -equivalence, which has to do with occurrences and scope, and # regulates abstraction, which has to do with what can be substituted or moved where! For illustration we propose silly (=non-confluent) reductions based on (false) rules consistently using only # and only respectively:
This is silly, because we can -rename the -bound to some and (as we can easily verify) reduce to .
This is silly, because we can also reduce with to obtain 0.
A rule (if ) would be silly:
For this reason, remains trapped in any position where it might be copied.
4. PROGRAMMING IN THE CALCULUS
Having defined and motivated the formal design of the calculus, we explore its expressivity, at first with respect to existing calculi in the literature but also with respect to some interesting applications.
4.1 Some simple reductions
We start by seeing how some familiar reductions work: Consider variables (with levels 1, 1, and 2 respectively; we may state levels as subscripts for the first use of a variable, then drop them). We might expect to reduce to . This is so:
Note however that does not bind; does reduce to ? Here and henceforth we write for . The answer is ‘yes’, but for more complex reasons. We consider the first part of its reduction:
Write for term substitution avoiding capture by -bound variables. We choose such that # so we can extend the scope of ; here we assume the context has sufficient freshnesses.
Note that does not in general reduce to . A counterexample is ( ). is weaker than , so reductions stop. However:
If the level of is no less than that of the other variables mentioned in then and as a corollary, .
By induction on the reduction rules.
We would expect and to reduce to if does not occur in . In fact, the first statement is not true!
A counterexample is . This does not reduce further unless #. Of course, this is the point of the context calculus; is stronger than and a substitution may arrive from elsewhere in the term to instantiate it to another term, such as , unless the context prohibits this. The second statement is true. The reductions are:
The conditions on annotating the reductions can be met by successive -renamings, because the context has sufficient freshness.
We never use the following result in this paper because we always work with reductions of a fixed term, but it is important because it expresses something about the sense in which variables represent terms:
Suppose is a term mentioning whose level is no less than that of the other variables in . Suppose is a term such that for all variables , if Γ # then . Then if then .
By exhaustively checking the reduction rules.
With regards to a, the two canonical cases are: (a) always; the side-condition is vacuous because and have the same strength. (b) reduces if # and # or # and #, but not if # and #. This rule is the crunch case, where name-capture (encoded by freshness conditions) can block a substitution actually occurring. Intuitively, a term can only be substituted for a variable, say, if it satisfies the intentional conditions on use of variables which the freshness context associates to .
4.2 The untyped lambda-calculus
Terms of the untyped -calculus are given by
binds in . This is standard [3]. A translation into the context calculus is given by:
(Recall is shorthand for .) We also assume some injection from the variables in the untyped -calculus to variables of level 1 in the context calculus. We may silently assume these injections henceforth.
Since does not bind in the context calculus we need an explicit . Otherwise, the translation is as one would expect. We omit the operational semantics of the untyped -calculus; a simulation result is easy to prove:
If then .
Multiple reductions , because the context calculus is an explicit substitution calculus. The proof is routine but subtle for reasons similar to the issues discussed in the last subsection. We use the fact that all variables in have level 1, and the corollary of the previous subsection.
Another correctness result is:
(Preservation of strong normalisation). If is any (possibly open) untyped -term then has a normal form if and only if does.
Confluence of the untyped -calculus means that we can choose a strict left-to-right -reduction strategy and be confident of arriving at the normal form if it exists. This particular rewrite strategy is easily simulated by the context calculus, one -reduction corresponding to one instance of followed by other rules (other reduction strategies can be less obvious because of the particular form of p). It is easy to verify that if is a normal form (has no valid -reducts) then has no valid instances of . Finally, the reductions of the context calculus without are strongly normalising.
4.3 The -calculus
Baro and Maurel’s -calculus [33] shares the context calculus’s unusual feature of spliting into a binder and an abstractor . (We are not aware of this idea anywhere else in the literature except for our work with on extensions of Nominal Rewriting [11].) This translates perfectly into the context calculus, with mapping to and to .
4.4 Records
Say a record is a term of the form where for . In words, a record is a set of substitutions suspended on a ‘big hole’ .
Consider variables , , and , and terms , (think of them as ‘data’). For convenience drop the subscripts on variables, a convention we shall use silently henceforth.
So is a simple record, we say it has two data elements and which are stored at and on . Call the term record lookup at and record update at .
We observe the following reductions:
We leave it to the reader to verify similar reductions for record update.
So record lookup at is a term which, when applied to a record, almost retrieves the data element — except for that troublesome . We call this name capture.
If we suppose for the sake of argument that #, then we can use # to drop the troublesome substitution. There are two ways of looking at this: either # is a desirable feature, or an undesirable restriction.
To avoid name capture it is not enough to insist that not occur in and . For example suppose . Then the substitution may arrive from the outside context, transforming into ! Of course we can simply insist that # be provable, but there is also a more elegant way: We can call a (say is protected). Then protected record lookup at is encoded by and record update by . Then the variable is bound by a and will avoid capture (assuming, of course, that does not actually occur in the syntax of when is created).
More sophisticated programming with records is possible, for example in-place update. Suppose the calculus contains basic arithmetic and consider 1, a simple record 1 stored at on . We can apply the substitution 1. The reader can verify the reduction
— the in 1 is carried by the strong substitution for under the weak substitution 1. This does not reduce further as-is, but a later lookup for will return 2. Thus 1 implements a command ‘increment the value stored at ’. This term clearly relies on not using protected records, since is free in it (later, we show how to obtain the same effect for protected records). We call this ‘in-place update’ because to increment we do not build a new record which is a copy of the old one only with an incremented value; we actually directly modify the original item of data. This is significant from an implementational standpoint. In full generality we can replace by any term we wish. These constructions and our notation should remind us of objects in the sense of ‘object-oriented programming’. First we consider global state, then we return to records to generalise them to objects.
4.5 Global state (with calculus)
Consider an untyped -calculus with general references. Terms are generated by the grammar
Here is drawn from a set of location variables and from a set of program variables. The intended semantics of ! is ‘the value which the global state associates to ’, of : is ‘set to in the global state’, and of is ‘allocate a fresh local location (with some unspecified or default value associated) and evaluate in the extended state’. The rest is standard as for the untyped -calculus.
This calculus is roughly similar to others in the literature, for example [2, Fig. 1 and Fig. 2] and to ReFS [29, Fig. 1 and Fig. 4]. The focus of study for is a fully abstract game semantics; that of ReFS is how to prove contextual equivalences between programs. Both and ReFS are typed. For brevity we have considered an untyped calculus.
[2] contains a construction of the combinator using general references in a typed system, thus obtaining the power of recursion. Therefore the absence of types does not make the calculus above obviously more powerful than , though it is more powerful than ReFS, which has recursion but integer-only references.
An encoding in the context calculus is given as follows: Fix a level 3 variable W, a level 2 variable S, and a level 1 variable r. Continuing the discussion of records above, write for S. Write : for S S. (In particular, we write Wr for WS r.)
The definitions above faithfully simulate the reductions we would expect of a language with references, and in particular those from [2], though we have no space to give them.
The reader may have noticed that our interpretation of global state is a ‘state transformer’; is a function which transforms states into other states:
4.6 Global state (with state-transformer)
As observed by Moggi [25], monads can model state in a purely functional setting. Following [18], and continuing notation from the last subsection, we define macros:
For detailed explanations see [18, 2.2, 2.4] and [17, 16]. Intuitively, newVar takes a state W (represented by a big hole!), allocates a new reference in it, assigns to , and returns the new state. readVar takes a state W and extracts the value assigned to to the distinguished result record r. writeVar takes a reference and a value , and given a state W returns W with allocated to . If evaluates to some term containing readVar W then will be linked to the old value of , before writeVar (this is not worthy of comment in [18] because the types make it quite clear how states are passed around). Finally, runST takes a program , applies it to a fresh empty state, and returns the result.
4.7 Objects
We propose terms for method invocation and method update which behave like constructs of the same name in the imp- calculus of Abadi and Cardelli [1]. For brevity we must assume the reader has some familiarity with it.
Call method invocation. Write for it applied to terms and .
Call method update (at ) and write for it applied to terms and .
To see how these definitions relate to daily life and in particular to imp- say a term is an (Abadi-Cardelli style) object when it has the form
We have typeset the levels of the variables as superscripts and not subscripts. may occur in the syntax of the and plays the rôle of the self parameter in [1]. We call the terms the data.
Consider 0. Then
Similarly, 0. For the same , consider
We can verify that .
Similarly, 1 1.
Recalling the discussion of records above, we have a notion of protected record with a ‘self’ parameter with implementations of method invocation and update. Note a technical feature of our presentation is that the self parameter is abstracted at top level, and not in every data item, for example , which would be more similar to imp-. Both ways are possible in our calculus and our choice seemed the simpler.
Note that imp- is a purpose-built abstract machine with a strong notion of global state whereas the context calculus is a purely functional rewrite system (so: no state and no control of evaluation order). So we have not ‘implemented imp-’. We have shown that some of the behaviour it was designed to study exists in the context calculus. And this in a strong sense that for example a term ‘method invocation’ exists which when applied to a record and a location obtains in a suitable sense the data stored at in . There is no need to use a family of macros encoding ‘method invocation for at ’ for each and .
We could continue with dynamic rebinding and mustering [5, 10] or modules and linking [20]. But now for something completely different:
4.8 Partial evaluation
Partial evaluation seeks strategies to optimally specialise code when some of the parameters are known. If and are programs (closed terms) then partial evaluation can be viewed as the search for algorithms to efficiently (in a suitable sense) compute an optimal (in a suitable sense) term which is equivalent (in a suitable sense) to ( applied to ).
See [8] for a short but efficient survey of this huge field. The context calculus may have something to contribute; we use an example adapted from [8, 6.1]. Write
in the untyped -calculus. It is easy to verify -equivalences showing these terms model truth values in a suitable sense. Now suppose we want to calculate
A naïve method -reduces not and obtains a term -equivalent to if not — a more intelligent method with access to a type system and which performs static analysis of dynamic values, may recognise that the program will always return false.
Now choose level 1 variables , and level 2 variables and and define context calculus terms
Here and are variables which just happen to be stronger than . This enables to directly encode in the term knowledge we have about execution flow, e.g. (very informally) that if we get to , must equal true.
If we want to partially evaluate
we can naïvely reduce to obtain
This is more efficient and with types must be true or false so the term can be specialised to false by standard techniques. So with strong variables and explicit substitution we ‘suspend information’ about on and .
5. CONFLUENCE
We use an attractive result in Van Oostrom’s thesis [36, Thm 2.3.5], but we need some notation to state it.
Take a set and a reduction relation on it. In connection with we shall always write and for pairs in . Take a well-founded partial order on reductions . We write when and , and when and .
Call a sequence , , . . . , , a chain and write it namelessly just as ( may equal 0). In the case that the chain has at length at most one (so 1) we write .
When for all elements of the chain, we write . To assert the existence of such a chain, we write . Similarly for and . When there is some pair and of reductions such that at least one of or always holds, we write , and to assert the existence of such a chain we write .
Given and , to assert the existence of two chains and (satisfying conditions and as discussed above) for some , we write namelessly .
Call a pair and a local divergence, and call a pair of chains and a convergence
(Van Oostrom). Suppose for every pair of local divergences and there exists a convergence of the form and . Then is confluent.
The partial order we impose on reductions is as follows: Instances of. . .
are ranked according to the size of :
and are ranked according to the size of the context in which they occur:
p are ranked according to the size of .
, a, #, and tr, are ranked together inversely according to the size of the context in which they occur:
p, a, , and , are ranked according to the size of the context in which they occur. For example,
is reflexive; . Everything else is incomparable:
The proof is now by the theorem above, verifying that every divergence has a suitable convergence. When closing a divergence involving scope-extrusion for , say, the side-condition does not ensures #. However we may -rename to some such that #; we assumed the context has enough freshnesses so this can be done.
Let be the transitive symmetric reflexive closure of .
does not relate all terms to all other terms (we say the calculus is consistent).
If and are two terms and then by confluence there exists some with and . To prove consistency, it suffices to exhibit two different normal forms; for example and (or, if the reader prefers, and ).
6. HINDLEY-MILNER TYPES
Some basic motivation: a type system is a logic (often a decidable logic) on terms, which allows us to reason on terms without having to evaluate them. For example, in ML if a term types has type integer, by Subject Reduction the term will always have type integer no matter how we evaluate it, and if it reduces to a normal form that normal form will be an integer. So there is no ‘one’ type system; it depends what properties we are interested in.
Hindley-Milner typing [9] is a simple and successful polymorphic type system which underlies ML. As such it is both a ‘working (functional) programmer’s’ tool and a starting point for more complex schemes. If the context calculus interacts well with it, then it is that bit less difficult to implement, e.g. as an extension of ML.
Fix infinitely many type variables TyVar. Types and type schemes are defined by:
Let a type substitution, we generally write 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 (we shall just write here and . Also write tyv for the type variables appearing in . Write Γ Δ for (finite) type contexts in the standard sense.
Then typing rules are as follows:
(Weakening for type judgements). If Γ : then Γ : .
By induction on the derivation.
(Soundness). If Γ : and then Γ : .
We exhaustively check all rules for (we consider just two cases).
Suppose Γ : is derivable. By following the derivation rules we see that
must be derivable, where tyv . Without loss of generality we rename elements of to be disjoint from tyv . It is now not hard to derive , using weakening for type judgements above to weaken : to .
Suppose and is derivable. Then for some , and , where Γ. It is now easy to derive .
We use the following technical lemma in the theorem which follows:
If Γ : then Γ : .
By induction on the derivation of .
For all Γ and there exists a pair such that Γ : if and only if .
is calculated by the following algorithm — the rules are read bottom-up, and we write Γ for the pair which is being calculated:
We prove by induction on the syntax of that for all Γ, if Γ and tyv tyv Γ then is a principal solution to Γ . The case . . . is simple. Suppose . . . is complex but standard straight out of [9] .
Suppose Let and be as in the inference rule, so that Γ : : . Suppose Γ : . Following the typing rules, Γ : : . By the universal property of , and for some . The case is also simple.
In conclusion, the type system is almost completely standard Hindley-Milner polymorphic types. The typing rule for explicit substitutions is identical to that of ML let-statements, so we are justified in viewing the explicit substitution as a let, and viewing the context calculus as an extension of a core of ML with a hierarchy of context variables (and a separation of abstraction and binding).
7. APPLICATIVE CHARACTERISATION OF CONTEXTUAL EQUIVALENCE
It is interesting to ask what an appropriate theory of contextual equivalence between programs is, since our system has programs which are contexts.
7.1 Programs, contexts, evaluations, and equivalences
It is convenient to introduce a constant . # always and engages in no reductions (e.g. is a normal form for all ).
Call a term with no free variables a program. is not a program, and and are. (Recall: we write for .)
If is a program write when and say evaluates.
Say is a context when (a) is a program and (b) where is stronger than all other variables in . We may abuse notation and also call a context.
For example , , and are contexts. and are not a contexts since they are not closed. is not a context because has level 2 and so does , so is not strictly stronger than .
An equivalence relation is a transitive symmetric reflexive relation. Call an equivalence relation on programs contextual (or a congruence) when
Here varies over contexts. 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 varies 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 some technical machinery to prove it:
(Technical lemma). Write when and are related by the transitive symmetric closure of . Then and .
Also, always, for 0.
Suppose . By confluence, if and only if , and similarly for and . The second part follows from the observation that is impossible unless
Note that 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 proof below we tend to use traditional notation of rather than .
7.2 Proof that equals
Proof ( equals ). It is easy to show that implies .
Conversely suppose . 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 the technical lemma above, 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 the technical lemma above and the fact that is by construction 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 is chosen fresh. We use the inductive hypothesis for and , both of which have fewer occurrences of then . Then follows using the technical lemma and the fact that is by construction an equivalence and also closed under application on the right. 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 . Then is closed. If is a -abstraction and 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 (checking cases) it must be that:
for some and , where # does not hold but # does (so does not apply). Then cannot possibly evaluate to for any .
, where # does not hold but # does. Since binds, can always be renamed to some atom such that # does hold. Therefore, this is not a normal form.
and for some , # does not hold but # does.
is stronger than and because is assumed bound by a top-level which we silently omitted, we can assume that # does not hold. Then for we can reduce as follows:
Recall that and are both closed so # and #. By the technical lemma below, # if and only if #. Write for and/or . If # do not hold then do not reduce for and there is nothing to prove. If # do hold then . is in normal form, has the same number of occurrences of as , and is strictly smaller. So we use the inductive hypothesis.
Note how the most fiddly case is , which might look ‘simplest’. But of course, this is the crunch case, where calculation actually gets done.
(Technical lemma). Suppose is a variable and and are terms. Suppose # if and only if # for all variables (a variable is fresh for if and only if it is fresh for ). Then # if and only if # , for all terms and variables .
By routine induction on the syntax of .
It may be that this result can be ‘lifted’ to calculi translated into the context calculus. We only need check that at points in the proof above where we convert contexts into applicative contexts, every manipulation keeps us within the image of the translation. We have in mind results similar to those by Pitts [29] characterising contextual equivalence for languages with global state, or perhaps analogous results for MetaML (see the Conclusions). We must defer this for a later paper.
8. CONCLUSIONS AND FUTURE WORK
Our NEW calculus of contexts is a little different, because of its freshness contexts and separation of abstraction and binding () — but it is not so complicated and has standard (and nontrivial) meta-properties motivated in the introduction. We have programmed interesting things in it including of course contexts, but also objects, general references, and we have made some observations about tracing values variables must have as a construction encoded directly in terms, which we applied to partial evaluation. We do not believe that this exhausts the possibilities.
We now explore what we cannot do in the calculus, since it is a prototype and there is plenty of ways to extend it.
The context calculus can express ‘ with substituted for ’ as ; this is a primitive of the calculus. We can abstract over and to obtain ( stronger than , and stronger than ); call this term substitution for , because . However, we cannot abstract over ;
This is not the intended operational behaviour. This is no surprise: variables can be substituted for at any time, so it should not possible to pass a variable as a first-class value. However we believe things are not quite so clear-cut now because of the context Γ, into which we already put assertions such as # ( is a hole that should not contain ). We may be able to also place assertions such as var, meaning ‘ is a variable’. If that seems far-fetched, the reader can look at [12] where the author carries out a similar exercise to the one described in the context of first-order logic.
The context calculus cannot express ‘substitute all varibles of level 1 for in ’, which we might write as . This idea appears in work by Dami [10] on dynamic binding. We do believe that our context calculus could have something to say about dynamic binding and linking, but we leave that for future work.
Now we recall the problem of implementing proof-search in first-order logic. The sequent right-introduction rules for and are [4]:
Here Γ and is any term. This can be a problem, for example for the design of a theorem-prover such as Isabelle [27], since it may become apparent only further up in the proof-tree (if at all) which is appropriate. Isabelle uses, instead of , an existential variable which behaves much like a level 2 variable only function-application is used to control scope.
We can certainly model existential variables using variables of level 2; for example ? ? is modelled by a term of the form where is some constructor. Substitutions on can be discovered deep in a proof, e.g. when we arrive at a leaf , and the substitution can be passed upwards and applied directly to the proof-state as a whole to specialise . However, there is no way to write a unification algorithm in the context calculus precisely because variables can be instantiated randomly by explicit substitutions from outside.
It is of significant long-term interest to present proof-search and programming (if the reader prefers; unification and tactics) in a unified framework, so we should definitely consider whether anything can be done here. We can introduce judgements of the form var into the context, and constructors into the calculus which detect when a variable is ‘known’ to be a variable in that sense. We can impose types and build the terms of the logic in an inductive datatype. A more-or-less strict evaluation order would avoid issues with confluence. We could try to solve only higher-order patterns [23], or restrict substitutions to be fresh renamings (substitutions of atoms for fresh atoms, similar in power to FM swapping [13]). Nominal Unification [35] already implements an algorithm which can be viewed as a special case of unifiers and the author’s -logic [12] introduces a logical judgement ‘this is a variable’ into first-order logic; so there is hope.
(We should mention that even in purely propositional logic, the Cut rule can be programmed in a similar way using a meta-variable for the formula introduced by the cut. So the issues just discussed arise in many logics and on many levels.)
We mention staged computation, as in for example MetaML [26, 28], Template Haskell [32], and Converge [34]. These languages offer a program enough control of its own execution that it can suspend its own execution, compose suspended programs into larger (suspended) programs, pass suspended programs as arguments to functions, and evaluate them. This raises issues similar to those surrounding contexts.
The context calculus cannot model staged computation, simply because it is a pure rewrite system with no control of evaluation order. However, it is possible to design a programming language based on the context calculus which can model staged computation. We have explored the idea in detail but have no space to do more than indicate the idea: in the term , restrict evaluations in to those involving variables that are at least as strong as . So for example 10 1, but 10 does not reduce. 11 1, because is strong enough to reduce under a substitution by , but is not. This to give enough control of execution flow to encode the brackets, escape, and run of MetaML (as well as other less exotic constructs, such as call-by-name and call-by-value versions of function application).
This programming language is as expressive as the context calculus; we just have control of execution flow. We expect it has the same good meta-properties as the smaller and simpler calculus of this paper, but proving that is for future work. We can hope the language might provide a semantics and common intermediate language for comparing additional features related to control of execution flow.
Other obvious extensions of the calculus include enriching the structure and treatment of levels. Finally, it is interesting to ask what kind of abstract machine is suitable for executing the context calculus (or the staged version discussed above). We have some promising results in this direction but they too must remain for another paper.
9. REFERENCES
[1] Martín Abadi and Luca Cardelli, An imperative object calculus, TAPSOFT ’95: Proceedings of the 6th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, LNCS, vol. 915, 1995, pp. 471–485.
[2] S. Abramsky, K. Honda, and G. McCusker, A fully abstract game semantics for general references, Proc. 13th IEEE Symp. Logic in Comp. Sci., IEEE Computer Society Press, 1998, pp. 334–344.
[3] H. P. Barendregt, The lambda calculus: its syntax and semantics (revised ed.), Studies in Logic and the Foundations of Mathematics, vol. 103, North-Holland, 1984.
[4] John Bell and Machover, A course in mathematical logic, North-Holland, 1977.
[5] Gavin Bierman, Michael Hicks, Peter Sewell, Gareth Stoyle, and Keith Wansbrough, Dynamic rebinding for marshalling and update, with destruct-time lambda, Proceedings of ICFP 2003: the 8th ACM SIGPLAN International Conference on Functional Programming (Uppsala), August 2003, pp. 99–110.
[6] Roel Bloo and Kristoffer Høgsbro Rose, Preservation of strong normalisation in named lambda calculi with explicit substitution and garbage collection, CSN-95: Computer Science in the Netherlands, 1995.
[7] Mirna Bognar, Contexts in lambda calculus, Ph.D. thesis, Vrije Universiteit Amsterdam, 2002.
[8] Charles Consel and Olivier Danvy, Partial evaluation: Principles and perspectives, Francophones des Langages Applicatifs, February 1993, pp. 493–501.
[9] Luis Damas and Robin Milner, Principal type-schemes for functional programs, POPL ’82: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM Press, 1982, pp. 207–212.
[10] Laurent Dami, A lambda-calculus for dynamic binding, Theoretical Comp. Sc. 192(2) (1998), 201–231.
[11] Maribel and Murdoch J. Gabbay, Extensions of nominal rewriting, PPDP, 2005.
[12] Murdoch J. Gabbay, -logic, Submitted, 2005.
[13] Murdoch J. Gabbay and A. M. Pitts, A new approach to abstract syntax with variable binding, Formal Aspects of Computing 13 (2001), 341–363.
[14] M. Hamana, Free sigma-monoids: A higher-order syntax with metavariables, The Second Asian Symposium on Programming Languages and Systems (APLAS 2004), Lecture Notes in Computer Science, vol. 3202, 2004, pp. 348–363.
[15] Masatomo Hashimoto and Atsushi Ohori, A typed context calculus, Theor. Comput. Sci. 266 (2001), no. 1-2, 249–272.
[16] Peyton Jones, Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in haskell, Engineering theories of software construction, Marktoberdorf Summer School, NATO ASI, 105 Press, 2001, pp. 47–96.
[17] Simon L. Peyton Jones and Philip Wadler, Imperative functional programming, Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina, 1993, pp. 71–84.
[18] John Launchbury and Simon L. Peyton Jones, Lazy functional state threads, PLDI ’94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, ACM Press, 1994, pp. 24–35.
[19] Pierre Lescanne, From lambda-sigma to lambda-upsilon a journey through calculi of explicit substitutions, POPL, 1994, pp. 60–69.
[20] Elena Machkasova and Franklyn A. Turbak, A calculus for link-time compilation, Lecture Notes in Computer Science 1782 (2000), 260–274.
[21] Ian Mackie Maribel , Murdoch J. Gabbay, Nominal rewriting, Submitted, January 2004.
[22] Takafumi Sakurai Masahiko Sato and Rod Burstall, Explicit environments, Fundamenta Informaticae 45:1-2 (2001), 79–115.
[23] Dale Miller, A logic programming language with lambda-abstraction, function variables, and simple unification, Extensions of Logic Programming (1991), no. 475, 253–281.
[24] Robin Milner, Joachim Parrow, and David Walker, A calculus of mobile processes, II, Information and Computation 100 (1992), no. 1, 41–77.
[25] Eugenio Moggi, Notions of computation and monads, Inf. Comput. 93 (1991), no. 1, 55–92.
[26] Eugenio Moggi, Walid Taha, Zine-El-Abidine Benaissa, and Tim Sheard, An idealized metaml: Simpler, and more expressive, ESOP ’99: Proceedings of the 8th European Symposium on Programming Languages and Systems, LNCS, vol. 1576, 1999, pp. 193–207.
[27] Larry Paulson, The Isabelle reference manual, Cambridge University Computer Laboratory, February 2001.
[28] A. M. Pitts and T. Sheard, On the denotational semantics of staged execution of open code, Submitted, February 2004.
[29] A. M. Pitts and I. D. B. Stark, Operational reasoning for functions with local state, Higher Order Operational Techniques in Semantics (A. D. Gordon and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1998, pp. 227–273.
[30] Masahiko Sato, Takafumi Sakurai, and Yukiyoshi Kameyama, A simply typed context calculus with first-class environments, Journal of Functional and Logic Programming 2002 (2002), no. 4, 359 – 374.
[31] Masahiko Sato, Takafumi Sakurai, Yukiyoshi Kameyama, and Atsushi Igarashi, Calculi of meta-variables, Computer Science Logic and 8th Kurt Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings (M. Baaz, ed.), Lecture Notes in Computer Science, vol. 2803, 2003, pp. 484–497.
[32] Tim Sheard and Simon Peyton Jones, Template metaprogramming for Haskell, ACM SIGPLAN Haskell Workshop 02 (Manuel M. T. Chakravarty, ed.), ACM Press, October 2002, pp. 1–16.
[33] Francois Maurel Sylvain Baro, The qnu and qnuk calculi : name capture and control, Tech. report, Paris VII, March 2003, Extended Abstract, PPS//03/11//n16.
[34] Laurence Tratt, Compile-time meta-programming in converge, Tech. Report TR-04-11, Department of Computer Science, King’s College London, December 2002.
[35] C. Urban, A. M. Pitts, and Murdoch Gabbay, Nominal unification, Theoretical Computer Science 323 (2004), 473–497.
[36] Vincent van Oostrom, Confluence for abstract and higher-order rewriting, Ph.D. thesis, Vrije Universiteit, Amsterdam, March 29 1994.
Notes
1We are very grateful to Pierre Lescanne, Laurence Tratt, Andrew Pitts, David Richter, Gérard Huet, Maribel , Antonino Salibra, and Gilles Dowek, for encouragement, help, conversations, and advice.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. PPDP’05, July 11–13, 2005, Lisbon, Portugal. Copyright 2005 ACM 1-59593-090-6/05/0007 ...$5.00.
2We take this opportunity to thank Sato for his hospitality in Kyoto, and for many interesting conversations.