An argument against call/cc (original) (raw)

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 shiftin 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 shiftand 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 shiftevaluates 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 shiftexpression. 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.