previous   next   up   top

An argument against call/cc

 

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.


 

Introduction

The generality of call-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.

Even in theory call/cc is inexpressive
This single control operator, call/cc, by itself is provably not capable of implementing exceptions, let alone other control features: Vast difference between delimited and undelimited continuations
Lack of composability
Undelimited continuations do not compose -- undelimited continuations are not functions. A captured undelimited continuation is in essence a backward label, to goto 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.
Memory leaks
Using 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.
Unavoidable performance hit
Implementing control features as a library, through 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 question
The claim that call/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.
The dynamic-wind problem
To write robust libraries that clean after themselves and leak no resources, 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.
Undelimited continuations do not occur in practice
The continuation captured by 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.

Version
The current version is 1.2, August 2012.

 

It was said before

The benefits of 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:

His talk painfully details the pain inflicted by call/cc on the language developers and demonstrates, among other things, that implementing threads with 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.

References
Matthias Felleisen: Re: continuations and threads
Message posted on the SRFI-18 discussion list, March 18, 2000
< http://srfi.schemers.org/srfi-18/mail-archive/msg00013.html >

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://lists.scheme-reports.org/pipermail/scheme-reports/2012-February/ >

 

Memory leaks

An immediately noticed practical problem with 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.

References
gen-leak.scm [2K]
Portable Scheme code demonstrating the memory leak caused by capturing the full -- longer than needed -- continuation.

shift-reset.scm [<1K]
POPL1994 implementation of shift in terms of call/cc.

 

call/cc implements shift? A good question

In the POPL 1994 paper Filinski showed that ``that the composable-continuations construct can itself be represented using ordinary, non-composable first-class continuations and a single piece of state.'' In short, shift 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.

References
Andrzej Filinski: Representing Monads. POPL1994

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.

 

Unavoidable performance hit

Implementing control features in terms of 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.

References
Carl Bruggeman, Oscar Waddell and R. Kent Dybvig: Representing Control in the Presence of One-Shot Continuations
PLDI, 1996, pp. 99-107
< http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.3782 >

Generators: the API for traversal and non-determinism

 

The dynamic-wind problem

The primitive 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.

References
William D Clinger, Matthias Blume and others
R5RS call/cc & dynamic-wind in terms of r4rs
Thread on comp.lang.scheme. May 15-24, 1998.

dynamic-wind
Thread on comp.lang.scheme Oct 31 - Nov 13, 2001. 143 messages.

Delimited continuations do dynamic-wind

 

Undelimited continuations do not occur in practice

Undelimited continuations by themselves seem to have no practical use: at least noone has shown me a practical application of just 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.

References
Alan Bawden: Reification without Evaluation
AI Memo, AIM-946, 1-Jun-1988
< http://hdl.handle.net/1721.1/6461 >

 

Conclusions

Offering 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.



Last updated August 9, 2012

This site's top page is http://okmij.org/ftp/

oleg-at-pobox.com or oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!

Converted from HSXML by HSXML->HTML