Can the CPS-styled `call/cc` be written in terms of a hypothetical non-CPS-styled `cc'`?

Question

In a language which supports continuation, e.g. Scheme, Ruby, and Haskell, suppose there is a function cc' which takes no argument and return the current continuation, so that the caller that obtains a continuation by calling cc' can then invoke the continuation anywhere and as often as it likes.

cc' can be written in terms of the CPS-styled call/cc, by passing an identity function as an argument to call/cc.

Conversely, can the CPS-styled call/cc be written in terms of the non-CPS-styled cc'?

@rampion That is intuitive, but wrong (AFAICS). It would cause g(call/cc(f)) = g(f(cc)) = call/cc(g . f), where the last . denotes function composition, and this is clearly not what we want. The point is that, intuitively, f should receive the continuation "without f itself", when f(cc) includes f in the continuation. — chi
Haskell doesn't natively support continuations. Delimited continuations can be implemented in the language (e.g., the ContT r monad transformer and various CPSish things like Codensity), but there is no support whatsoever for undelimited continuations like Scheme has. — dfeuer

chi chi · Accepted Answer · 2019-08-05T16:05:35

Here's my attempt (warning: I am an inexperienced schemer). Let get-cc be the function returning the current continuation.

(define (get-cc)
  (call-with-current-continuation (lambda (k) k)))

Then, we can define:

(define (callCC f)
  (let ((w (get-cc)))
    (if (pair? w)
      (car w)
      (f (lambda (x) (w (cons x '())))))))

The first time this function is called, w is bound to the current continuation. So, (pair? w) is false, and we call f with continuation (lambda (x) (w (cons x '())).

When w is called though f (with argument (cons x '())), then the body of the let is entered again, where w is now bound to (cons x '()). Now, (pair? w) is true, and we can return (car w) which is x.

The pair wrapper is used so as to distinguish what is "the continuation for f" from "the result from f", so to speak.

A quick test shows this to be working, but I'm not completely confident of its correctness.

You probably noticed that w is bound to values of different types. That is why I resorted to an untyped language like Scheme instead of Haskell.

Can the CPS-styled `call/cc` be written in terms of a hypothetical non-CPS-styled `cc'`?

1 Answers