We argue against
call/cc as a core language feature, as the
distinguished control operation to implement natively relegating all others
to libraries. The primitive
call/cc is a bad abstraction
-- in various meanings of `bad' shown below, -- and its capture of the
continuation of the whole program is not practically useful. The
only reward for the hard work to capture the whole continuation
efficiently is more hard work to get around the capture of the
whole continuation. Both the users and the implementors are better
served with a set of well-chosen control primitives of various degrees
of generality with well thought-out interactions.
shift? A good question
call/cc, as the ultimate abstraction of control is alluring. This single operator seemingly lets us express the whole gamut of control features: exceptions, threads, coroutines, generators,
amb, non-determinism. Why spend any time implementing exceptions or generators when
call/ccgives them all for free. With such an impressive payoff, providing
call/ccas a primitive becomes a categorical imperative then, the right thing to do.
This generality or perhaps the hypnotism of `entering a room once, and yet
leaving it twice', or the ease with which
call/cc lets us write
incomprehensible code resisting local reasoning have made
a cult symbol, something that every cool implementer
must aspire to. This article is meant as a caution, admonishing
of the poor abstraction of control and exposing the traps of its
implementation and use. Here is the summary of the counter-arguments expounded
in the rest of the page.
call/cc, by itself is provably not capable of implementing exceptions, let alone other control features: Vast difference between delimited and undelimited continuations
gotoregardless of any lexical scope, even after the current procedure is finished. Programming with
call/ccis even less structured than
gotoin Fortran and Algol targeted in the famous Dijkstra's letter.
call/cc-- directly or incorporated into library functions -- easily leaks a great amount of memory. It is not clear how to portably plug these leaks.
call/cc, imposes significant and unavoidable performance penalty:
call/cccaptures so-called multi-shot, escaping continuations, which are overkill for most other control features. Using
call/ccfor threads or generators is like implementing the IO library in terms of shell-escapes.
shift? A good question
call/ccplus a mutable cell implements all other control operators holds only under stringent conditions. All other control operations must be implemented in terms of
call/ccin exactly prescribed ways, which are inefficient and wasteful of resources. Common implementations of dynamic binding with reference cells are ruled out. Even
call/ccitself is not allowed to be used independently. If these tight conditions are violated,
call/cccannot implement generators, threads,
shiftetc. according to their semantics, making it impossible to reason about programs maintaining abstractions and hiding implementation details.
call/ccmust be supplemented with another primitive:
dynamic-wind. The addition of
dynamic-windexacerbates the reasoning and especially performance problems of
call/ccis invariably delimited at a REPL or session boundary. Hence
call/ccin practice is expressible in terms of delimited control and does not have to be supported as a core feature.
Neither theory nor practice justify the implementation of
as a core language feature. This control operator does not give us
anything for free, does not save us any implementation effort,
but leads to problems, bugs and more problems.
call/cchave been questioned before, most notably by Matthias Felleisen back in 2000. His message is worth quoting in its entirety:
How many of you use call/cc and continuation objects (rather than mimicing continuations with lambda's) in large programs? Do "we" really use it to implement coroutines and backtracking and threads and whatever?
Is call/cc necessary for Scheme?
[Don't shoot. I wrote many papers on all aspects of call/cc but now that we're building large systems we should revisit these questions. I'd love to be wrong here.]
The experience with
call/cc in other languages has led to similar
doubts, if not opposition. Koichi Sasada, a developer of the Ruby
interpreter and the developer of the Ruby Virtual machine, summarized
his Continuation Fest 2008 talk about
call/cc in Ruby thusly:
call/ccworks really bad in practice.
More recently the deprecation of call/cc has been debated during the discussion of a draft Revised^7 Report on Scheme. This present web page summarizes and extends the main arguments.
Koichi Sasada: Ruby Continuation (or: Ruby continuation considered harmful)
Talk presented at the Continuation Fest 2008, April 13, 2008. Tokyo, Japan
< http://www.atdot.net/~ko1/pub/ContinuationFest-ruby.pdf >
R7RSWG1 Proposal: Clarifying and potentially removing call/cc
Discussion on the R7RS mailing list. February-March 2012.
< http://scheme-reports.org/mail/scheme-reports/msg02780.html >
call/ccis memory leaks. Capturing the whole continuation where only a prefix is really needed prevents objects referenced from the unneeded suffix of the continuation from being garbage collected.
The problem already occurs in the most straightforward cases, such
as the standard implementation of generators in terms of
Converting a generator to a stream (a lazy list) and enumerating it
tail-recursively accumulating no data runs out of memory
within seconds. In contrast, if the generator is written with the
shift, the same stream conversion and enumeration code
runs in constant memory. With
call/cc, the head of the enumerated stream is
referenced from the unneeded part of the captured full continuation.
Newly generated stream elements cannot therefore be garbage collected and
fill the whole memory.
There does not seem to be a good answer how to plug this memory leak in portable RnRS Scheme. Trampolines, although fixing the leak, change the behavior of the program and cause constant dynamic unwinding and rewinding, affecting dynamic environment, current ports, etc. The next section mentions several examples.
Here is another, very simple example, relying on the standard Filinski
(POPL1994) implementation of
shift in terms of
(define (leak-test1 identity-thunk) (let loop ((id (lambda (x) x))) (loop (id (identity-thunk)))))
By the semantics of delimited control,
(reset (shift k k)) is
the identity function. Evaluating
(leak-test1 (lambda () (lambda (x) x))) loops in constant memory.
If we evaluate
(leak-test1 (lambda () (reset (shift k k)))) however, the
program crashes within a a few seconds, having
allocated half a GB of memory and asking for more. It is left
as an exercise to the reader to explain the problem.
Scheme48 therefore includes a corrected POPL1994 code -- with a
so-called JAR hack -- using internal procedures
null-continuation. The appearance of
these internal primitives gives the first doubt if delimited
control is really practically implementable as a library feature in terms of
POPL1994 implementation of
shift in terms of
shift? A good question
shiftcan be implemented with
call/ccand a single mutable cell. This is indeed how
shiftis typically implemented in Scheme, SML or other systems. The fact that first-class undelimited continuations along with the mutable cell express first-class delimited control has entered common knowledge -- often justifying the existence of
call/ccas the core control operator.
Unfortunately the context of the POPL94 remarkable result, its goals
and the scope, and hence its side-conditions are often forgotten. The
POPL94 conclusions are frequently taken beyond their intended
application area, causing problems and confusion. This article reminds
of the POPL94 motivations and restrictions. Practical language
systems invariably violate the side-conditions, making the
POPL94 result inapplicable. Using the POPL94 implementation of
in terms of
call/cc then leads to confusion because the implementation no
longer confirms to the semantics of
shift. We demonstrate two simple
counter-examples of the difference between the predicted, on the basis of
the semantics of
shift, results and the observed ones.
The problem arises precisely because
call/cc captures the whole continuation rather than its prefix.
Such a behavior of
call/cc is not a problem
within the POPL94 framework since it
shiftis the only effect (with all others
implemented in terms of it). Even
call/cc cannot be used except for
its appearance in the implementation of
shift. In practice,
effectful operations such as exceptions or dynamic binding are
implemented independently, breaking the main assumption of POPL94 and
exposing the problem of capturing the whole continuation. In these
call/cc does not implement
shift or other
control features. They have to be provided as primitives.
Recall the standard small-step reduction semantics of
E[ (reset v) ] ---> E[v] E[ (reset C[ shift k e ]) ] ---> E[(reset (let ((k (lambda (x) (reset (C[x]))))) e))]where
eis an arbitrary expression,
vis a value,
Eis an arbitrary evaluation context and
Cis an evaluation context that does not contain
(reset ). As POPL94 wrote ``
shiftcaptures (and erases) the evaluation context up to the nearest dynamically enclosing
reset(every program is run with an implicit all-enclosing
reset), and passes this context to its argument as an ordinary function.'' See, for example, Asai and Kameyama, APLAS 2007, for the discussion of this small-step semantics. POPL94 used the CPS semantics of
reset, which is consistent with the small-step semantics.
For the demonstration, we will use an R5RS Scheme system (such as
Petite Chez and Scheme48) and the original POPL94
shift in terms of
call/cc -- as well as the one corrected
for memory leak, included in the Scheme48 distribution.
The similar examples have been written for SML. We use the R5RS procedure
with-output-to-file to re-direct the output of
display to a file.
That procedure along with
current-output-port is an instance of
dynamic binding. Instead of
with-output-to-file, we could have used
the general portable implementation of dynamic binding, SRFI-39, or
built-in facilities such as fluids in Scheme48. The same problems occur in
all these implementations of dynamic binding.
The first counter-example shows that in POPL94 code
evaluates its body without removing the captured continuation,
contrary to its small-step semantics. Let us apply the reduction semantics
to the following code
(reset (with-output-to-file "/tmp/t" (lambda () (shift k (display "shift")))))The context
Eis empty and the context
(with-output-to-file "/tmp/t" (lambda () )). The code should reduce in one step to (dropping the dead binding to
(reset (display "shift"))which prints on the stdout. However, if we evaluate the original code, we see no stdout print-out. Applying a small-step reduction to the code gave the result differing from the result of the original code.
The second counter-example shows that the delimited continuation
shift does not behave like a function. When that `function'
is invoked, it changes the context of its invocation. The following code
(reset (begin (shift f f) (display "shift")))captures and returns the delimited context reified as a function. According to the small-step semantics of
shift, the context
(begin  (display "shift")). Thus we expect
(let ((captured-k (reset (begin (shift f f) (display "shift"))))) (with-output-to-file "/tmp/t" (lambda () (captured-k #f))))to have the same behavior as
(let ((expected-captured-k (lambda (x) (reset (begin x (display "shift")))))) (with-output-to-file "/tmp/t" (lambda () (expected-captured-k #f))))However, evaluating the two expressions gives different results. The latter code prints nothing on stdout. The output from
displayis redirected to the file, as intended. When evaluating the original code, the output from
displayappears on the stdout and the file is empty. Not only the difference between the predicted and the observed results is disconcerted. We cannot achieve a practical goal, redirecting the output when invoking a captured continuation.
The same two problems occur if we use the portable SRFI-39 implementation of
dynamic binding, or built-in parameters (Chez Scheme) or fluids (Scheme48).
Mixing POPL94 SML code with SML native exceptions leads to the same
failures to predict the program behavior based on the semantics of
These are all practical problems. Chung-chieh Shan's ICFP06 talk
(see PDF page 31, slide 13) showed a sample OCaml program for enumerating
over a file using a generator, written in terms of
shift. The program also
relies on exception handling to make sure the file is always closed
when the enumeration finishes, normally or abnormally. If we
use the POPL94 implementation of
shift and native OCaml exceptions,
the file may remain unclosed. Thus the POPL94 implementation may lead
to very difficult-to-find bugs.
We can see the problems if we examine the POPL94 code.
(define *shift (lambda (f) (call-with-current-continuation (lambda (k) (*abort (lambda () (f (lambda (v) (reset (k v))))))))))Evaluating
E[ reset(C[ *shift (lambda (g) e) ]) ]captures
Cand reifies it as a function
(lambda (v) (reset (k v))), where
E[reset(C)], the whole context of the
shiftexpression. When the captured continuation is invoked in some context
E'[(lambda (v) (reset (k v))) v']-- the result is
E[ reset(C[v']) ]. The context of the caller
E'is removed, which is not the behavior expected of a function. If
C[v]raises an exception for which there is a handler in
Ebut not in
E', the small-step semantics predicts the exception will not be handled. In contrast, the exception will be handled in the POPL94 code. The divergent behavior occurs precisely because
call/cccaptures the whole continuation.
It must be stressed that the problems occur because the POPL94 code is used
beyond its intended scope. Filinski's ambitious goal -- which he successfully
realized in POPL94 and POPL99 papers -- was to prove that the entire
stack of monadic effects can be implemented entirely at the user level,
as a library, provided the host system offers
call/cc and a
single mutable cell. This remarkable expressivity result deals only
with the observational equivalence of programs, abstracting over any efficiency
or memory requirements.
Thus Filinski's work offers the first solution to our predicament: all
monadic effects should be implemented as prescribed in the
POPL94-POPL99 framework. We can then reason about programs using the
semantics of effects, with no divergence between observations and
predictions. Incidentally, the ICFP06 paper on
delimited dynamic binding
demonstrated that approach. There is a heavy price to pay however
(even disregarding the fact that some combinations of effects occurring
in practice are not expressible in the POPL99 framework).
All effects must be implemented exactly as described in the POPL99 framework,
in terms of
shift and eventually
call/cc. We really must
implement exceptions, and dynamic binding, and state
in terms of
call/cc even if
they need no continuation capture. Capturing a continuation
on each dereference of a mutable or dynamic cell leads to abysmal
performance. I am not aware of any system that implements dynamic
binding, for example, through continuations. However, if we implement
at least one effect facility outside of the POPL99 framework, we break
the assumptions of the framework and can no longer rely on it.
An alternative is to implement control operations natively and
to find ways to reason about their interactions. If we need
we have to code it without relying on POPL94. The ICFP06 paper
has mentioned in passing an implementation
shift that is made to work together with Scheme48 dynamic environment.
The code necessarily uses internal Scheme48 primitives and is not portable.
delimcc library in OCaml offers a number of control operators that
work together with OCaml native exceptions. Again the code
relies on internal primitives of the OCaml run-time system.
Therefore, in practice if some form of delimited control is needed,
it has to be provided as a primitive. We cannot in practice rely
mutation. It seems
call/cc has no reason
Andrzej Filinski: Representing Layered Monads. POPL1999
POPL1994 implementation of
shift in terms of
The complete R5RS code for the examples in the text.
The complete code for two more examples, using dynamic binding, either native (fluids) or implemented as a portable library (SRFI-39). The former file should run on any R5RS Scheme system. The latter file uses fluid variables of Scheme48 and the version of the POPL94 code corrected for memory leaks (which is part of Scheme48 distribution). The same problems occur in either case.
Delimited Dynamic Binding
Section 4.1 of the paper shows that trampolining is not semantically transparent. The paper comes with the large collection of code written for a number of language systems, demonstrating problems mixing dynamic binding with delimited control implemented in terms of
call/cchas inherently poor performance. The operator
call/cccaptures so-called multi-shot, escaping continuations, letting us return several times from a single procedure call. Such generality costs performance but is rarely needed. For example, exceptions do not require any continuation capture, let alone multi-shot one. It is much easier and quite more efficient to implement them as primitive, rather than to emulate in terms of control operators. Even R7RS Scheme now specifies a dedicated exception-handling facility; previously, portable Scheme programs were supposed to rely on
call/cc. By the same token, simple generators such as those in CLU and Python are realizable on linear stack with standard function calls and need no continuation capture either. They too make sense to implement natively rather than emulate through more powerful and expensive control operators. Using
call/ccfor threads and coroutines has an unacceptable cost due to
dynamic-wind, as described further below.
It has been frequently observed that in most all cases a captured continuation is invoked at most once. Dybvig et al. and Feeley showed that one-shot continuations are much more efficient to implement. The sole, it seems, use case for multi-shot continuations is non-determinism. A better abstractions for non-determinism, such as generators, have long been known in Icon and Scheme predecessors.
Experience shows that
call/cc makes a poor trade-off between
generality and performance. Implementing exceptions and all other
control facilities as library functions in terms of
call/cc turns out
a bad idea.
Generators: the API for traversal and non-determinism
dynamic-windproved to be one of the most controversial features of Scheme, stirring long debates on comp.lang.scheme in 1998, 2001 and thereafter. It is a strange primitive that we cannot live without and cannot live with. As we shall see, it is
call/ccthat is the real culprit. Dynamic-wind is a problem meant to alleviate the resource-leak problems of
The argument for
dynamic-wind is to permit writing finalizers, so to
dispose of resources on normal or abnormal exit from a function. If a
function deals with files, database connections, etc., its
continuation will contain references to these resources. When the
continuation is captured, the resources remain referenced and cannot
be disposed of -- not until the continuation itself is garbage
collected, which may occur very late. For scarce resources such as
database connections, the leak could be unacceptable. The operator
dynamic-wind was introduced to let us write finalizers,
invoked upon local or non-local exit from a function, to dispose of
resources. Since a continuation captured within a function can be
dynamic-wind lets us write co-finalizers to re-acquire the
resources upon the re-entry. Another application of
implementing efficient, shallow dynamic binding as a library
function, see SRFI-39.
The argument against
dynamic-wind is, surprisingly, the same. The
operator lets us write finalizers that are invoked on each non-local
exit. Therefore, if we implement `lightweight threads' in terms of
call/cc, every thread switch -- a non-local exit from one function
and non-local entry into the other -- causes the firing of finalizers
and co-finalizers, disposing and reacquiring resources. Even a
supposedly heavy-weight OS process context switch does not close and
reopen all the files within processes. The operator
makes it impossible to implement lightweight threads with
By its very existence
call/cc. First, it shows
call/cc is not the only core control primitive: the language
developer also has to write
makes the performance of generators, threads and other control operations
written in terms of
call/cc so ludicrously expensive that the developer
has no choice but to implement those control operations as primitives
as well. If all interesting control operations are implemented as primitives,
why do we need
A commonly employed discipline for resource management is regions. By their nature regions should not permit capturing continuations across them: they delimit continuations.
Thread on comp.lang.scheme Oct 31 - Nov 13, 2001. 143 messages.
Delimited continuations do dynamic-wind
call/cc, which I have been asking for a long time. To my knowledge, in all practical programs
call/ccemulates, to the extent possible, some sort of a delimited control operation, often as simple as exceptions or generators.
It is telling that
call/cc as implemented in real Scheme
systems never captures the whole continuation anyway: Many Scheme systems
put implicit control delimiter around REPL or threads.
These implicit delimiters are easily noticeable: for example, in
Petite Chez or Scheme48, the code
(let ((k0 #f)) (call/cc (lambda (k) (set! k0 k))) (display 0) (k0 #f))prints the unending stream of zeros. If we put each operation on its own line (evaluated by its own REPL):
(define k0 #f) (call/cc (lambda (k) (set! k0 k))) (display 0) (k0 #f)the output is mere
There is a good reason to place a control delimiter at least at a session boundary (that is, a debugging prompt, or `Cafe' in Chez Scheme) if not around every REPL. Alan Bawden have argued that call/cc-captured continuations should not `shift levels' (go between sessions), in Sec 3 of his paper.
call/cc that captures continuations up to REPL or other
such boundary can easily be written with
shift or other delimited
control operator. Modulo cosmetic interface differences,
reset around the whole program behaves just like
call/cc. In fact, the file
scheme/misc/shift-reset.scm in the
Scheme 48 distribution shows such an implementation of
cwcc in the file) in terms of
shift. The code has been in
Scheme 48 since about 1994.
call/ccas a core control feature in terms of which all other control facilities should be implemented turns out a bad idea. Performance, memory and resource leaks, ease of implementation, ease of use, ease of reasoning all argue against
call/cc. If there is really one distinguished control feature to implement as a primitive, with others relegated into libraries, it is not
Chances are there is no such feature, at least from the practical point of view. A language implementation may need to support several control primitives. We have to think what they are and how to reason about their interactions. I feel the design space is not yet well-explored. We need more experience implementing, using and reasoning with various control operators and frameworks.
Your comments, problem reports, questions are very welcome!
Converted from HSXML by HSXML->HTML