How does the yin-yang puzzle work?

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

Understanding Scheme

I think at least half of the problem with understanding this puzzle is the Scheme syntax, which most are not familiar with.

First of all, I personally find the call/cc x to be harder to comprehend than the equivalent alternative, x get/cc. It still calls x, passing it the current continuation, but somehow is more amenable to being represented in my brain circuitry.

With that in mind, the construct (call-with-current-continuation (lambda (c) c)) becomes simply get-cc. We’re now down to this:

(let* ((yin          ((lambda (cc) (display #\@) cc) get-cc))        (yang          ((lambda (cc) (display #\*) cc) get-cc)) )     (yin yang)) 

The next step is the body of the inner lambda. (display #\@) cc, in the more familiar syntax (to me, anyway) means print @; return cc;. While we’re at it, let’s also rewrite lambda (cc) body as function (arg) { body }, remove a bunch of parentheses, and change function calls to the C-like syntax, to get this:

(let*  yin =          (function(arg) { print @; return arg; })(get-cc)        yang =          (function(arg) { print *; return arg; })(get-cc)     yin(yang)) 

It’s starting to make more sense now. It’s now a small step to rewrite this completely into C-like syntax (or JavaScript-like, if you prefer), to get this:

var yin, yang; yin = (function(arg) { print @; return arg; })(get-cc); yang = (function(arg) { print *; return arg; })(get-cc); yin(yang); 

The hardest part is now over, we’ve decoded this from Scheme! Just kidding; it was only hard because I had no previous experience with Scheme. So, let’s get to figuring out how this actually works.

A primer on continuations

Observe the strangely formulated core of yin and yang: it defines a function and then immediately calls it. It looks just like (function(a,b) { return a+b; })(2, 3), which can be simplified to 5. But simplifying the calls inside yin/yang would be a mistake, because we’re not passing it an ordinary value. We’re passing the function a continuation.

A continuation is a strange beast at first sight. Consider the much simpler program:

var x = get-cc; print x; x(5); 

Initially x is set to the current continuation object (bear with me), and print x gets executed, printing something like <ContinuationObject>. So far so good.

But a continuation is like a function; it can be called with one argument. What it does is: take the argument, and then jump to wherever that continuation was created, restoring all context, and making it so that get-cc returns this argument.

In our example, the argument is 5, so we essentially jump right back into the middle of that var x = get-cc statement, only this time get-cc returns 5. So x becomes 5, and the next statement goes on to print 5. After that we try to call 5(5), which is a type error, and the program crashes.

Observe that calling the continuation is a jump, not a call. It never returns back to where the continuation was called. That’s important.

How the program works

If you followed that, then don’t get your hopes up: this part is really the hardest. Here’s our program again, dropping the variable declarations because this is pseudo-code anyway:

yin = (function(arg) { print @; return arg; })(get-cc); yang = (function(arg) { print *; return arg; })(get-cc); yin(yang); 

The first time line 1 and 2 are hit, they are simple now: get the continuation, call the function(arg), print @, return, store that continuation in yin. Same with yang. We’ve now printed @*.

Next, we call the continuation in yin, passing it yang. This makes us jump to line 1, right inside that get-cc, and make it return yang instead. The value of yang is now passed into the function, which prints @, and then returns the value of yang. Now yin is assigned that continuation that yang has. Next we just proceed to line 2: get c/c, print *, store the c/c in yang. We now have @*@*. And lastly, we go to line 3.

Remember that yin now has the continuation from when line 2 was first executed. So we jump to line 2, printing a second * and updating yang. We now have @*@**. Lastly, call the yin continuation again, which will jump to line 1, printing a @. And so on. Frankly, at this point my brain throws an OutOfMemory exception and I lose track of everything. But at least we got to @*@**!

This is hard to follow and even harder to explain, obviously. The perfect way to do this would be to step through it in a debugger which can represent continuations, but alas, I don’t know of any. I hope you have enjoyed this; I certainly have.

Answer 2

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