Transform coroutine in continuation passing style

Question

I have this coroutine example

(define p1
  (lambda (continuation)
    (display "1")
    (newline)
    (p1 (call/cc continuation))))

(define p2
  (lambda (continuation)
  (display "2")
  (newline)
  (p2 (call/cc continuation))))

(p1 p2)

And I would like to change it in CPS so that I can use the CPS call/cc :

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

I know that to transform a function in CPS I need to add a continuation to the fonction but I'm quite confused and I don't really know how to do it.

I think that it would look like that :

 (define p1
   (lambda (continuation)
   (display "2")
   (newline)
   (call/cc-cps
     (lambda (continuation actual-continuation)
       continuation) ;; or actual-continuation ?
     (lambda (value)
       (p1 value)))))

(p1 p2)

But It's probably wrong. Can someone help me understand how to do it correctly ?

Thank you

Sylwester Sylwester · Accepted Answer · 2017-08-20T13:20:40

If you do something in CPS only one calculation is done in tail position in every function. It's kind of the way an interpreter evaluates the code:

(define (hyp a b)
  (sqrt (+ (square a) (square b))))

The whole point is that CPS does the calculation in the needed order and never do more than one thing at a time. This in CPS becomes:

(define (hyp& a b cont)
  (define (cont-square-a sqa)
    (define (cont-square-b sqb)
      (define (cont-sum sum)
        (sqrt& sum cont))          
      (+& sqa sqb cont-sum))        
    (square& b cont-square-b))      
  (square& a cont-square-a))

Or if you prefer anonymous continuations:

(define (hyp& a b cont)      
  (square& a
           (lambda (sqa)
             (square& b
                      (lambda (sqb)          
                        (+& sqa
                            sqb
                            (lambda (sum)
                              (sqrt& sum cont))))))))

All the &-functions are just CPS-versions of the actual function, thus they have a continuation argument in addition to the original function. p1 would look like this:

(define (p1& continuation& cont)
  (define (cont-display-2 undefined-value-1)
    (define (cont-newline undefined-value-2)
      (define (cont-call-cc-continuation& continuation-value)
        (p1& continuation-value cont))
      (call/cc& continuation& cont-call-cc-continuation&))
    (newline& cont-newline))
   (display& "2" cont-display-2))

You might be interested in the articles of Matt Might. Take a loot at everything around continuations and compilations as they are related. I also recommend watching the SICP videos and perhaps try solving the exercises in the SICP book. By the time you are making interpreters and compilers it should be a walk in the park making generators.

Transform coroutine in continuation passing style

1 Answers