schemecallcc

How does the yin-yang puzzle work?


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?


Solution

  • 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, ...