How the yin-yang puzzle works?

Question

I'm trying to grasp the semantics of call/cc in Scheme, and the Wikipedia page on continuations shows the yin-yang puzzle as an example:

(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))

It should output @\*@\**@\**\*@\**\**@..., but I don't understand why; I'd expect it to output @\*@\**\**\**\**\*...

Can somebody explain in detail why the yin-yang puzzle works the way it works?

Answer 1

I don't think I understand this one fully, but I can only think of one (extremely hand-wavy) explanation for this:

• The first @ and * are printed when yin and yang are first bound in the let*. (yin yang) is applied, and it goes back to the top, right after the first call/cc is finished.
• The next @ and * are printed, then another * is printed because this time through, yin is re-bound to the value of the second call/cc.
• (yin yang) is applied again, but this time it's executing in the original yang's environment, where yin is bound to the first call/cc, so control goes back to printing another @. The yang argument contains the continuation that was re-captured on the second pass through, which as we've already seen, will result in printing **. So on this third pass, @* will be printed, then this double-star-printing continuation gets invoked, so it ends up with 3 stars, and then this triple-star continuation is re-captured, ...

Answer 2

Musings first, possible answer at the end.

I think the code can be re-written like this:

; call (yin yang)
(define (yy yin yang) (yin yang))

; run (call-yy) to set it off
(define (call-yy)
    (yy
        ( (lambda (cc) (display #\@) cc) (call/cc (lambda (c) c)) )
        ( (lambda (cc) (display #\*) cc) (call/cc (lambda (c) c)) )
     )
)

Or with some extra display statements to help see what is happening:

; create current continuation and tell us when you do
(define (ccc)
    (display "call/cc=")
    (call-with-current-continuation (lambda (c) (display c) (newline) c))
)

; call (yin yang)
(define (yy yin yang) (yin yang))

; run (call-yy) to set it off
(define (call-yy)
    (yy
        ( (lambda (cc) (display "yin : ") (display #\@) (display cc) (newline) cc) 
            (ccc) )
        ( (lambda (cc) (display "yang : ") (display #\*) (display cc) (newline) cc) 
            (ccc) )
     )
)

Or like this:

(define (ccc2) (call/cc (lambda (c) c)) )
(define (call-yy2)
    (
        ( (lambda (cc) (display #\@) cc) (ccc2) )
        ( (lambda (cc) (display #\*) cc) (ccc2) )
    )
)

Possible Answer

This may not be right, but I'll have a go.

I think the key point is that a 'called' continuation returns the stack to some previous state - as if nothing else had happened. Of course it doesn't know that we monitoring it by displaying @ and * characters.

We initially define yin to be a continuation A that will do this:

1. restore the stack to some previous point
2. display @
3. assign a continuation to yin
4. compute a continuation X, display * and assign X to yang
5. evaluate yin with the continuation value of yang - (yin yang)

But if we call a yang continuation, this happens:

1. restore the stack to some point where yin was defined
2. display *
3. assign a continuation to yang
4. evaluate yin with the continuation value of yang - (yin yang)

We start here.

First time through you get yin=A and yang=B as yin and yang are being initialised.

The output is @*

(Both A and B continuations are computed.)

Now (yin yang) is evaluated as (A B) for the first time.

We know what A does. It does this:

1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B, we don't compute it.
4. compute another continuation B', display * and assign B' to yang

The output is now @*@*

5. evaluate yin (B) with the continuation value of yang (B')

Now (yin yang) is evaluated as (B B').

We know what B does. It does this:

1. restore the stack - back to the point where yin was already initialised.
2. display *
3. assign a continuation to yang - this time, it is B'

The output is now @*@**

4. evaluate yin with the continuation value of yang (B')

Since the stack was restored to the point where yin=A, (yin yang) is evaluated as (A B').

We know what A does. It does this:

1. restores the stack - back to the point where yin and yang were being initialised.
2. display @
3. assign a continuation to yin - this time, it is B', we don't compute it.
4. compute another continuation B", display * and assign B" to yang

The output is now @*@**@*

5. evaluate yin (B') with the continuation value of yang (B")

We know what B' does. It does this:

1. restore the stack - back to the point where yin=B.
2. display *
3. assign a continuation to yang - this time, it is B"

The output is now @*@**@**

4. evaluate yin (B) with the continuation value of yang (B")

Now (yin yang) is evaluated as (B B").

We know what B does. It does this:

1. restore the stack - back to the point where yin=A and yang were being initialised.
2. display *
3. assign a continuation to yang - this time, it is B'"

The output is now @*@**@***

4. evaluate yin with the continuation value of yang (B'")

Since the stack was restored to the point where yin=A, (yin yang) is evaluated as (A B'").

.......

I think we have a pattern now.

Each time we call (yin yang) we loop through a stack of B continuations until we get back to when yin=A and we display @. The we loop through the stack of B continuations writing a * each time.

(I'd be really happy if this is roughly right!)

Thanks for the question.