Change a function into CPS, to not use call/cc

Question

I would like to understand how to implement coroutines without call/cc.

I began with this little example to understand how to modify a code so that I can use it without call/cc:

(define x 0)

( + 2 (call-with-current-continuation
  (lambda (cont)
    (set! x cont)
  3)))

(x 4)

When I execute the function with the call/cc it gives me 5, then 6 when I execute (x 4).

I use this function to replace the call/cc :

(define (call/cc-cps f continuation)
   (f continuation continuation))

I tried to change this function into CPS (continuation-passing style):

(call/cc-cps
  (lambda (exit cont)
   (set! x cont)
   3)
(lambda (value)
  (+ value 2)))

But when I execute it, instead of having 5 I get 3. But I do get 6 with (x 4).

Can you tell me what is wrong ? thank you

Answer 1

With CPS you don't have top level continuations prompts so for a comparison you need to put you code in an empty let like this:

(let ()
  (define x 0)
  (+ 2 (call-with-current-continuation
         (lambda (cont)
           (set! x cont)
           3))) ; ==> 5
  (x 4))
  ; ==> 6
  ; ==> 6
  ; ==> 6
  ; ... forever 

This becomes an infinite loop since you call (x 4) after the summing every time.

;; CPS-version of +
(define (+& a b continuation)
  (continuation (+ a b)))

Notice the &. It's used to indicate that the function takes one extra argument, the continuation. In CPS you define call/cc like this:

(define (call/cc& f& continuation)
  (define (exit& value actual-continuation)
    (continuation value))
  (f& exit& continuation))

Notice it's quite different from your version. It passes the exit function to f& and instead of using the passed actual-continuation that would do all the remaining computation it passes it to the continuation of call/cc& instead.

Now we can rewrite your program into this:

((lambda (x& halt-continuation) 
  (call/cc& (lambda (cont continuation)
              ((lambda (ingnored-undefined-value) (continuation 3))
               (set! x& cont)))
            (lambda (three)
              (+& 2 three (lambda (ignored-result)
                      (x& 4 halt-continuation))))))
 0 values)

ignored-result is 5 the first time and the infinite other times it calculates it with 4 ignored-result is 6, just like in the non CPS version with let.

I use DrRacket which has a pretty darn good debugger and you can step and see exactly what is happening. I added a break point at the +& call and pressed |> and saw the variable three fist be 3 then 4 infinite times.

CPS isn't easy. call/cc gives us the benefits of CPS without making the code much harder to read. Implementing coroutines without call/cc would be challenging for me to write as I though it was quite complex to do it with call/cc to begin with, especially since you have a infinite loop if you are not very careful.