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.
call/cc implements shift? A good questioncall-with-current-continuation, or 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/cc gives them all for free. With such an impressive
payoff, providing call/cc as 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 call/cc
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 is inexpressivecall/cc, by itself is provably not capable of
implementing exceptions, let alone other control features: Vast difference between delimited and undelimited continuationsgoto regardless of any lexical scope,
even after the current procedure is finished. Programming with
call/cc is even less structured than goto in 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/cc captures so-called multi-shot, escaping continuations,
which are overkill for most other control features. Using call/cc
for threads or generators is like implementing the IO library in terms
of shell-escapes.call/cc implements shift? A good questioncall/cc plus a mutable cell implements all other
control operators holds only under stringent conditions. All other
control operations must be implemented in terms of call/cc in exactly
prescribed ways, which are inefficient and wasteful of resources.
Common implementations of dynamic binding with reference cells are ruled out.
Even call/cc itself is not allowed to be used independently. If these
tight conditions are violated, call/cc cannot implement generators,
threads, shift etc. according to their semantics, making it impossible
to reason about programs maintaining abstractions and
hiding implementation details.call/cc must be supplemented with another primitive:
dynamic-wind. The addition of dynamic-wind exacerbates the
reasoning and especially performance problems of call/cc.call/cc is invariably delimited at a REPL
or session boundary. Hence call/cc in 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 call/cc
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/cc have 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/cc works 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/cc is
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 call/cc.
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
leak-proof 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 call/cc.
(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 with-continuation and 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 call/cc.
shift-reset.scm [<1K]
POPL1994 implementation of shift in terms of call/cc.
call/cc implements shift? A good questionshift can be implemented with call/cc and a single mutable cell.
This is indeed how shift is 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/cc as 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 shift
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
presupposes that 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
practical circumstances, 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 shift and reset:
E[ (reset v) ] ---> E[v]
E[ (reset C[ shift k e ]) ] --->
E[(reset
(let ((k (lambda (x) (reset (C[x])))))
e))]
where e is an arbitrary expression, v is a value, E[] is
an arbitrary evaluation context and C[] is an evaluation context
that does not contain (reset []). As POPL94 wrote ``shift captures
(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 shift
and 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
code for 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 shift
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 E[] is empty and
the context C[] is (with-output-to-file "/tmp/t" (lambda () [])).
The code should reduce in one step to (dropping the dead binding to k) (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
captured by 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 C[] is (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 display is
redirected to the file, as intended. When evaluating the original
code, the output from display appears 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 shift.
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 C[]
and reifies it as a function (lambda (v) (reset (k v))),
where k represents E[reset(C[])], the whole context of the shift
expression. When the captured continuation is invoked in some context E'[] -- 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 E[] but 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/cc captures 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 shift,
we have to code it without relying on POPL94. The ICFP06 paper
has mentioned in passing an implementation
of shift that is made to work together with Scheme48 dynamic environment.
The code necessarily uses internal Scheme48 primitives and is not portable.
The 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
on call/cc plus mutation. It seems call/cc has no reason
for existence.
Andrzej Filinski: Representing Layered Monads. POPL1999
shift-reset.scm [<1K]
POPL1994 implementation of shift in terms of call/cc.
traps.scm [3K]
The complete R5RS code for the examples in the text.
traps-srfi.scm [5K]
traps-s48.scm [3K]
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/cc.
call/cc has
inherently poor performance. The operator call/cc
captures 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/cc for 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.
dynamic-wind proved 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/cc that is the real culprit. Dynamic-wind is a
problem meant to alleviate the resource-leak problems of call/cc.
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
invoked again, dynamic-wind lets us write co-finalizers to re-acquire the
resources upon the re-entry. Another application of dynamic-wind is
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 dynamic-wind
makes it impossible to implement lightweight threads with call/cc.
By its very existence dynamic-wind condemns call/cc. First, it shows
that call/cc is not the only core control primitive: the language
developer also has to write dynamic-wind. Second, dynamic-wind
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 call/cc?
A commonly employed discipline for resource management is regions. By their nature regions should not permit capturing continuations across them: they delimit continuations.
dynamic-wind
Thread on comp.lang.scheme Oct 31 - Nov 13, 2001. 143 messages.
call/cc, which
I have been asking for a long time. To my knowledge, in all practical programs call/cc emulates, 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 0 #f.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.
Therefore, 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, shift with
only one 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 call/cc
(called cwcc in the file) in terms of shift. The code has been in
Scheme 48 since about 1994.
call/cc as 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 call/cc.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.
oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!
Converted from HSXML by HSXML->HTML