How does the yin-yang puzzle work?

by

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.

Leave a Comment