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.