Ying Yang call/cc or the call-with-current-continuation puzzle • Ramblings of Boy Maas

One of the more interesting paradigms arising from Scheme is the call-with-current-continuation. Let me try to explain this in abstract terms, a call/cc is passed a procedure p. This procedure takes one argument k which represents the continuation. The continuation k can be applied with a value. This value will become the value of the application of call/cc. Easy heh?

Ok? Let's play a little with them

To give an example, this first example does call/cc which does not apply the continuation k:

(call/cc
 (lambda (k)
  (* 5 4))) =>  20

The lambda is called with our current-continuation which is ignored as it just returns the result of the calculation.

In this next example the continuation is applied with an integer argument of 4, the return value of the call/cc lambda becomes the value passed to the continuation k and thus prints 4.

(call/cc
 (lambda (k)
  (* 5 (k 4)))) => 4

We could argue that the continuation acts as a return statement. This facilitates returning from a recursion as described below.

(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ((ls ls))
          (cond
            ((null? ls) 1)
            ((= (car ls) 0) (break 0))
            (else (* (car ls) (f (cdr ls))))))))))

This is simple, let's try to find something more interesting

Try this piece of code which I found in The Scheme Programming Language.

(let ((x (call/cc (lambda (k) k))))
  (x (lambda (ignore) "hi"))) => "hi"

What happens here?

x gets bound to the continuation k
- since call/cc calls lambda k: which returns itself
x, which is the continuation k, is applied with the (lambda (ignore) "h1")
- this has the effect of rebinding x to (lambda (ignore) "hi")
control continues and comes again to the statement (x (lambda (ignore) .. )
- and thus applies the lambda to the rebond x returning "hi"

Now for something really interesting, the call/cc ying yang puzzle.

Reading the wikipedia article I stumbled upon this interesting puzzle. I was immediatly fascinated as it seemed difficult to explain why the below described call/cc combinations deliver the output as described.

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

Outputs an infinitive sequence, I have extracted the first output of this function below.

@*@**@***@****@*****@******@*******@********@*********@**********@*******
****@************@*************@**************@***************@**********
******@*****************@******************@*******************@*********
***********@*********************@**********************@****************
*******@************************@*************************@**************
************@

Keep in mind that (let* (b1 b2) e1 e2 ..) translates to (let (b1) (let (b2) e1 e2 .. ). Try to explain this one .. good luck, heheh