call/cccall/cc? What is this
page?call/cc?call/cc stand
for?call/cc function?setjmp() and
longjmp()call/cc does: a first
descriptioncall/cccall/cc? What is this
page?
call/cc stands for
“call with current continuation”; it is a function that
exists in certain programming languages. What it does is not very
easy to describe; in fact, I think it is one of the strangest
inventions of computer science. This page tries to explain what
call/cc does, what it means, why it is useful and how it
works.
[1999/11/14] This page has only started. It is something I really wanted to write. However, I have so much to say on the subject, and so little time, that I must beg the reader's pardon for its obscurity and many failings. Still, I hope I am able to share some of my enthusiasm for this wonderful function.
The background required to read this page varies widely. To
understand it fully, you need a thorough knowledge of theoretical
computer science and mathematical logic — and then you probably
don't need to be told what call/cc is, anyway. But most
parts require little or no knowledge of such topics. I have tried to
keep this free of Scheme prerequisites, but I have not always
succeeded. Anyway, consider this page more as a collection of
scattered thoughts with little order in them than as a systematic
treatment of the subject. If something is obscure, just continue, it
might become clearer later on since I try to repeat the same things as
often as possible in various different ways.
At its heart, call/cc is something like the
goto instruction (or rather, like a label for a
goto instruction); but a Grand High Exalted
goto instruction. I can see your hair turning green at
this point: ever since Dijkstra's famous Turing award speech, we
know that goto is Evil and can never be Grand, High and
Exalted. Well, wait until you know more about call/cc.
The point about call/cc is that it is not a
static (lexical) goto instruction but a
dynamic one. Just exactly what is meant by this should
become clear later on. The call/cc function introduces
some rather mysterious objects in the programming language,
first-class reified continuations; these fundamentally alter
the way the program is understood (some would say, making it much
harder to understand — and admittedly there is truth in this).
call/cc?
Some genius I would say. No, seriously, I'm not sure. I am told that
P. J. Landin, in “A Correspondence between algol 60 and Church's
Lambda-notation” (Communications of the ACM,
vol. 8, Feb. 1965, 89–101 and 158–165), introduces the
J
operator that is quite like call/cc. I have not
checked this. [XXX — do so.]
call/cc stand
for?
It means “call-with-current-continuation”.
At least, that is its official name in Scheme (and though the
call/cc abbreviation is common, it has not achieved
universal recognition and some Scheme implementations, such as guile,
accept only the longer name). This refers to the fact that
call/cc captures the current continuation, and
applies its argument to this continuation (however, before you try to
make sense of this please wait for me to explain what continuations
are).
Since I am trying to speak of the function in general, and not of its
particular implementation in Scheme, I will refer to it as
“call/cc” and not
“call-with-current-continuation”.
call/cc function?
Scheme is
the canonical language having a call/cc function: it is
officially called call-with-current-continuation,
although the call/cc notation is semi-standard.
The Standard ML of
New Jersey also has a call/cc function, that is
called SMLofNJ.Cont.callcc
(it differs a bit from the Scheme version in that continuations are
not directly reified as functions but need to be “thrown”
with the function SMLofNJ.Cont.throw; however, that does
not change the fundamental nature of the call/cc
function).
The Unlambda programming language
also has a call/cc function (introduced simply because it
is something that is difficult to understand and Unlambda is an
obfuscated programming language): it is called “c”.
To the best of my knowledge, these are the only languages with a
full-fledged call/cc function. Many other languages
(notably Java, CAML or C++) incorporate a weaker form of
call/cc (“outgoing-only continuations”)
called exceptions: we will explain what exceptions are and
why they are weaker than true continuations.
At a lower level, some OS's have support for a kind of
call/cc function: the only that I know of is the Solaris form of Unix which
supports the getcontext() function that is strongly
related to call/cc. And processor Task State Segments
(used in multitasking) could be thought of as a manner of
continuations.
Finally, a call/cc function can be added to the Coq project by simply entering
Axiom callcc : (P:Type) ((P->EmptyT)->P)->P.; however,
since Coq is not Turing-complete, this can be considered cheating.
Exceptions are present in many programming languages, and most people seem to have no problem understanding them. We review them briefly.
An exception signals that a special condition (generally an error) was encountered in the course of the execution of a program. Signaling the condition (highly inappropriate term) is called raising the exception (most people use the term “throwing” here, but I prefer the former term). When this happens, normal execution ceases: the function in which the exception was raised terminates immediately, raising the exception again in its caller (parent), which terminates in turn, and so on until either the entire program is terminated or until it is caught. Catching the exception involves putting the code which might raise it in a special block; if the exception is raised, control is transferred to the exception handler which decides what to do; after the exception handler has returned, normal execution is resumed (at the end of the block, not where the exception was raised), as if the code had terminated normally.
With the exception is associated certain data, which are specified when the exception is raised, and which will be passed to the exception handler when (and if) the exception is caught. Several different exceptions might be raised by the same block of code: they will be handled independently, in that an exception handler can be put for any subset of the exceptions which might occur, and those exceptions which are not caught will continue to cause termination.
The weakest form of exceptions are lexically scoped ones,
also called block/break exceptions: they are
not true exceptions but merely a structured form of labels and
gotos. This means that the exception may be raised only
if a lexically surrounding block is there to catch it
(something that can be checked statically at compile time). In its
very weakest form, this is the return, break
and continue statements of C; however, C does not have
labeled breaks (like Perl or Java do) [XXX — any
projects on adding this feature?], so these “exceptions”
are limited to one-at-a-time local exits (or, if you prefer, lexical
scoping with a single-name namespace). Beyond that, the labeled
breaks of Java (next in Perl) are examples
of lexically scoped exceptions; still, these are a far cry from true
exceptions, and even further from first-class continuations. Note how
we say that these lexically scoped exceptions propagate
outward through the program (“outward” in the
sense of lexical block scoping, of course).
True exceptions (the raise/catch sort and
not the break/block one) are of a different
nature: any block can raise an exception, it does need to have to be
lexically embedded within a catch block. And the
exception will be caught (if at all) by the innermost
catch that is dynamically surrounding the
raise. We say that (dynamically scoped) exceptions
propagate upward through the program (“upward”
through the program stack, that is), from callee to caller.
One important thing to note is that whereas with lexically scoped
exceptions the block (catching the exception) associated
to a break (raising the exception) is well-defined and
can be determined at compile time, on the other hand with true
(dynamically scoped) exceptions the catch that will
actually catch an exception thrown with a given raise
cannot be determined in advance, and can vary from time to time
according to the way the function containing the raise is
called.
(If what follows seems obscure to you, do not worry, that is normal; please feel free to skip over the rest of this section.)
There are, of course, subtleties involved when the language allows first-class citizenship of functions and inner functions, because an inner function might then escape from its lexically containing function and might be called from elsewhere, meaning that its dynamical container might be quite different from its lexical container. Consider the following fragment of an imaginary C-like language:
void (foo) (void) (void)
// A function taking void and returning a function that takes
// void and returns void.
{
try {
// Return the following function:
void inner (void)
{
raise SomeExn;
}
}
catch (SomeExn) {
print ("Here I am!\n");
exit (whatever);
}
}
void main (void)
{
try {
foo () ();
}
catch (SomeExn) {
print ("There I am!\n");
exit (whatever);
}
}
What does this do? Essentially, from main we call the
inner function of foo, which raises an
exception. Which handler should handle it? If exceptions are
lexically scoped, it is that of foo, and if they are
dynamically scoped, then it is that of main. So in the
one case, “Here I am!” will be printed, and “There I
am!” in the other.
Note that this dilemma is not likely to happen in any real situation.
Why is that? Because no language acts like that — I'm not
talking about exceptions but simply about this escaping of inner
functions — except Lisp variants. Pascal allows inner
functions, but Pascal does not give them first-class citizenship so
that inner functions cannot escape (their dynamic container is always
within lexical scope of their lexical container); C allows first-class
citizenship of functions (or, to be precise, of pointers to functions)
but no nested functions; gcc allows both but its manual explicitly specifies that
“all hell will break loose” if you try to invoke an inner
function after its lexical container has exited.
There is a deep reason behind this (“this” being the remark made in the previous paragraph). Indeed, when inner functions can escape, the question of the visibility of variables from the outer functions becomes rather complex: the duration of closures is greater than simply the execution time of the function, and the simple stack-based model of computation fails (garbage-collection must be used, the closures must be stored on the heap rather than on the stack). I mention this here because there is an analogy with escaping continuations: escaping continuations do to return addresses what escaping inner functions do to data (i.e. making lifetimes become unpredictable and forcing a replacement of the simple stack model by a more complex, garbage-collected graph). We will return to this. There is something very deep here, which I am not able to understand clearly, let alone explain in detail.
Anyway, we now end this digression.
setjmp() and
longjmp()
The C programming language (or, rather, the POSIX standard) defines
two functions, setjmp() and longjmp() which
are the nearest thing C has to exceptions or continuations. We shall
look at them in some detail because they have some interesting common
points with call/cc and throw respectively.
The setjmp() function stores the so-called “stack
context” (not a very appropriate name for outgoing-only
continuations like these, but let us stick to it) in a variable passed
to it, the “jump buffer”; it then returns 0.
The longjmp() function takes a jump buffer and a (non
zero) return value: it makes the execution point jump (non-locally) to
the return of the setjmp() function which had set that
jump buffer, and the function returns the proposed return value. In
other words, the longjmp() never returns, it makes the
setjmp() function return instead. As for the
setjmp() function, it can return in two different ways:
with a return code of 0 the first time, and possibly one
or more times later, with the return code that was passed to the
longjmp() function. This key point of one function
making another return a specific value will be crucial in
understanding call/cc, so keep it in mind.
These functions are used to implement exceptions in C: an exception
handler is installed with the setjmp() function, and the
exception is raised with longjmp(). What the functions
actually do is that setjmp() stores the size of
the stack in the jump buffer, and longjmp() restores it.
(Of course, there is a heavy amount of black magic involved, notably
on the compiler's part, so that this not mess up with the various
optimizations, and there are some complicated restrictions on the use
of these functions; in the case where the longjmp()
function is called from a signal handler, things get pretty messy
indeed. But we are floating far above such worries.)
One important restriction of the setjmp() and
longjmp() functions is that the function that called
setjmp() must not have returned between the call to
setjmp() and that to longjmp(). The
following code, for example, is invalid:
#include <stdio.h>
#include <setjmp.h>
jmp_buf buf;
int
foo (volatile int n)
{
if ( setjmp (buf) )
{
printf ("%d\n", n);
return 0;
}
else
return 1;
}
int
main (void)
{
if ( foo (42) )
longjmp (buf, 1);
/* Yow! DEMONS are flying through my NOSE! */
exit (0);
}
(In practice, though, it works reasonably. But more complex examples
would fail miserably.) The reason for this restriction is the way
setjmp() functions: it works by remembering just the size
of the stack (marking the current stack pointer), and
longjmp() essentially just reduces the size to that size,
so that program execution appears to have jumped to the point where
setjmp() was about to return. This works well so far as
everything that was below the marked point on the stack remained
unaltered, i.e. so long as the function that called
setjmp() did not return. This is why we say that we have
“outgoing-only” (or, more precisely,
“upgoing-only” since we are talking of dynamic scoping)
continuations.
Think of a setjmp() function that would not have this
limitation and you have a good approximation of call/cc.
If you adhere to a stack-based paradigm of computation, or things to
work in all cases we would need a full copy of the stack as per
getcontext().
call/cc does: a first
description
The call/cc function takes one argument. That argument
should itself be a function f (hence, our programming
language should allow first-class citizenship of functions).
call/cc will apply f to the current
continuation. The current continuation is something
which looks a lot like a function (at least in the Scheme version of
call/cc it does; in the SML/NJ version it is a bit
different but that is unimportant). If a continuation is applied to a
value (or, as some prefer to say, thrown a value), it has the
effect of making the call/cc (which produced that
continuation) return that value.
We give a few examples. These are written in Scheme, but little or no
knowledge of Scheme should be required to understand them. Keep in
mind that (lambda (variables) body)
is the notation for an anonymous function with given parameters
(variables) that performs the given function
(body), and that the function f applied to the
variables x1,...,xn is written (f x1
... xn).
Consider the first example: (call/cc (lambda (k) (k
42))). This applies call/cc to the function
(lambda (k) (k 42)); hence, the latter function is called
with argument (k) equal to the current continuation. But
the body of the function is (k 42), in other words, the
continuation is thrown the value 42. This makes the
call/cc return the value 42. Hence, the entire
expression evaluates to 42.
Now consider (call/cc (lambda (k) (+ (k 42) 1729))).
Here, the function throws the value 42 to the continuation, and
attempts to do something afterward. Only this has no effect, because
as soon as a continuation is invoked (by throwing a value to it), the
program jumps (to be precise, the current continuation becomes the
continuation invoked) and the program bit (the continuation)
which was going to take an x and perform (+
x 1729) has been lost in space (it has become
GC-fodder). So the result is still 42.
On the other hand, consider (call/cc (lambda (k) 42)).
Here, the function applied to the current continuation (namely
(lambda (k) 42)) does not make use of the said
continuation. It returns in the “normal” way. In the
case of Scheme (and also SML/NJ and Unlambda, so, as far as I know,
every implementation of call/cc), when this happens, the
call/cc function also returns the same value. Hence the
result is 42 again. But other
approaches are possible, so this should not be taken as part of
the “fundamental” nature of call/cc but only
as a contingent property of its main implementations.
For the next example, we need to add two more elements of Scheme:
(let ((variable value) ...)
body) is used to bind initially variable
to value in body. And (set!
variable value) is used to change the
value of variable to value. In what follows,
#f (the “false” boolean) is used as a dummy
value representing something unspecified. So, here is the example:
(let ((cont #f)) (call/cc (lambda (k) (set! cont k))) (cont
#f)). Here we have a variable cont: its initial
value is unimportant. We call call/cc upon a function
(lambda (k) (set! cont k)) that takes the continuation
(k) and binds the variable cont to it; it
then returns in the normal way. We ignore the return value of the
call/cc and we call the saved continuation
cont with an unimportant value. But when that
continuation is called, it has the effect of going, so to speak,
“back in time”, to the point where the
call/cc returned, and make it return again, after which
the continuation is again called, so call/cc returns
again, and so on: we are caught in a “time warp” and our
example loops endlessly.
The interesting thing about the last variable is that the continuation
escaped, i.e. it became visible outside of the function that
is the argument to call/cc (namely (lambda (k)
(set! cont k))); this is precisely what was impossible with
exceptions. It (meaning the continuation) was captured and bound to
the variable cont, and used outside the scope
permitted for outgoing-only continuations (exceptions; in fact, with exceptions it is not
possible to produce an endless loop like this).
[XXX — add more examples here]
It is time by now to explain the meaning of the central keyword in all this discussion: that of a continuation.
A continuation is “something which waits for a value” in order to perform some calculations with it. This is a very vague definition, but I think it nevertheless makes things clear. With every intermediate value in a computation, there is a continuation associated, which represents the future of the computation once that value is known. A continuation is not something, like a function, which takes a value and returns another: it just takes a value and does everything that follows to it, and never returns.
Consider a computation such as (* (+ 2 4) (+ 1 6)). We
have several continuations involved here. The continuation for
(+ 2 4) says: take this value, keep it aside; now add one
and six, take the result and multiply it with the value we had kept
aside; then finish. The continuation for (+ 1 6) says:
take this value, multiply it with the value (6) we had kept aside;
then finish. Notice in particular how the result of (+ 2
4)is part of the continuation of (+ 1 6), because
it has been calculated and kept aside. Continuations are not
something static that can be determined at compile time: they are
dynamic entities that are created and invoked as program execution
proceeds.
At each step in the program, when a value is being evaluated, there is a current continuation, waiting for the value to be thrown to it [why is it that I suddenly have the clear image in my mind of a lion waiting for fresh meat to be thrown to it?]; the current continuation will perform the remainder of the computation, including calculating other values and calling other continuations.
It can be argued, if we believe in the stack-based paradigm for computation, that a continuation represents the execution stack, i.e. the sequence of nested functions that are the callers of a given value, at a given point in the program execution history.
The basic evaluation element in a programming language is this: evaluate an expression exp (possibly in a given environment env if the language has named variables which is frequent) with a continuation cont (the current continuation) waiting for the result. Keep this in mind as we will say that we are evaluating an expression (in an environment) with a continuation, the “with” referring to the continuation that is waiting for the value.
One important particular case is that when the result of one computation immediately determines (gives, yields, provides — or, more simply, “is”) the result of another, that is, when the one is in tail position in another, such as the last instruction in a compound instruction or function body, then the continuation of the one is the same as the continuation of the other.
If we allow the program to explicitly manipulate continuations, which
is the whole point of call/cc, we are reifying
these continuations. If they can be manipulated in exactly the same
way as, say, integers (they can be passed as arguments to functions,
returned as return values, passed to other continuations, and so on),
then we have given them first-class citizenship.
So, when we apply call/cc to a function f with
a continuation k (the current continuation
hungrily waiting for the result of the said call/cc),
call/cc applies f to k,
with continuation k. Notice how k
plays a double role: it is passed as the argument to
f, and it is also the continuation to that same
call. (The latter fact, as we have already pointed out that this fact is not
so important, being more a convention in existing implementations of
call/cc than a fundamental property of it. This says, in
a way, that the function call is in tail position in the
call/cc call.)
We reconsider the previous examples. First, (call/cc (lambda
(k) (k 42))). Here, k is bound to the continuation
waiting for call/cc to terminate. So we are evaluating
(k 42), k being bound to the said
continuation, with k again as (current) continuation; the
latter fact is not used, since k is immediately thrown the
value 42, making call/cc return. Second
example: (call/cc (lambda (k) (+ (k 42) 1729))). Here,
we have two continuations, k, the continuation waiting for
call/cc to finish, and also for (+ (k 42)
1729), and another continuation, say l, waiting for
(k 42) to finish so as to add 1729 to it and
throw it to k; but that l will be left waiting
(and eventually garbage-collected) because (k 42)
never finishes, since k is a continuation.
Third, (call/cc (lambda (k) 42)): this time we really
need to use the fact that the function f (here
(lambda (k) 42)) gets applied with the same continuation
k as the call/cc (the double role mentioned
above).
dynamic-wind
and related subjects.
call/cc and concurrency: cooperative (and non
cooperative) scheduling by continuation switching.
call/cc with fork(), with
getcontext() (what is preserved in each case).
call/cc. CPS interpreters. Thoughts on
continuations and tasks.
call/cc and the Curry-Howard isomorphism: Pierce's
law, “going back in time”, double negation and the meaning
of disjunction.
call/cc in linear programming / logic (?).
call/cccall/cc of the FOLDOC
call/cc in an Introduction
to Scheme and its Implementation
call/cc
entry of the R5RS
Cont
module in SML/NJ