(let* ((yin
((lambda (cc) (display "@") cc) (call/cc (lambda (c) c))))
(yang
((lambda (cc) (display "*") cc) (call/cc (lambda (c) c)))))
(yin yang))
The call/cc yin-yang puzzle is written in Scheme. It is commonly presented when discussing the "call-with-current-continuation" construct—usually shortened to call/cc to prevent repetitive strain injury—in programming, because of its heavy reliance on the function. It was originally written by David Madore, the creator of the Unlambda programming language, in an attempt to write an Unlambda program which printed consecutive integers.
When run, the output of the yin-yang puzzle is "@*@**@***@****@*****@******@*******...", i.e. successively larger numbers of asterisks separated by at-signs. Many a soul has tried and failed to figure out exactly why; such is the nature of continuations.
A bit of background on continuations is necessary to understand just how confusing the yin-yang puzzle really is. If you don't know anything about continuations, this section is essential. If you completely grok continuations and think you're fine, read it anyway.
Continuations are, to glaze over a couple of important points, objectifications of the future of a program's execution; basically, they are—they don't just represent, they actually embody—what the program has left to do at any given moment in time. To relay their incredible power to the programmer, they require a language with first-class functions: functions in that language can be assigned as variables and passed to other functions just like any other datatype. Some examples of these languages are Lua, Scheme (and other LISPs), Haskell (and other functional languages), Ruby (to an extent), Python, JavaScript, and Unlambda. (Note that not all of these languages support (or even can support) call/cc.)
To give an example, assume, without loss of generality, that our program (written in bastard-tacular pseudocode) calculates the length of the hypotenuse of two specified leg lengths via the Pythagorean theorem.
define function pythag(x, y) {
return sqrt(x * x + y * y);
}
Let's make this a little more verbose, for the sake of discussion.
define function pythag(x, y) {
x2 := x * x;
y2 := y * y;
z2 := x2 + y2;
z := sqrt(z2);
return z;
}
Within the function, you can clearly pick out the steps the program takes to get to the result. Square the x, square the y, add them, root the result. The continuation, for example, right at the y2 assignment is to add that value to x2, and then take the square root of the result. The continuation at the x2 computation would be to square y, and then proceed with the y2 continuation. Think about that for a moment.
Now, as mentioned earlier, in call/cc languages, functions are first-class values. call/cc takes one argument, a function, which should itself take only one argument. Then, it takes the continuation of the call/cc invocation—the current continuation—and passes this as the sole argument to the passed function. For example, assuming the continuation object could be represented as <cont>, then callcc(f) becomes f(<cont>). When you later pass the <cont> a value, it "returns" to the callcc(f) statement and continues with that value.
You may now be confused. No worries. The most prudent way to think about how this works is like so.
callcc(f) would have had a return value, right? So, take a snapshot of the continuation of the call/cc, namely the rest of the program after it, and turn that into a (first-class) function. This function will execute the rest of the program, when you give it an argument. (This argument would normally have been supplied by the return value of callcc(f) if it had been any other function.) Now, pass this continuation function to f, and let that execute. If f never uses <cont>, then just use f(<cont>)'s return value at the point where the return value from the callcc(f) would have been needed. If, however, <cont> does get evoked, then take the value passed to it and continue right from where you left off with callcc(f)!
As a visual reference, take the following example. (From here on, we will use LISP notation, because it is much more natural for the purposes of call/cc and the first-class/higher-order functions concepts we are using.)
(- (call/cc (lambda (k) (+ (k 42) 1729))) 16)
=> (- ((lambda (k) (+ (k 42) 1729)) <cont>) 16)
=> (- (+ (<cont> 42) 1729) 16)
** FWOOSH MAGICAL TELEPORTATION **
(- (call/cc (lambda (k) (+ (k 42) 1729))) 16)
=> (- 42 16) ;; call/cc "returns" the received 42
=> 26
You may now have a couple of follow-up questions.
- What happens to the continuation of the (k 42) (being added to 1729)? It's gone. It has been dropped, in favour of continuing the <cont> continuation. This is pretty much because the reification of continuations in Scheme is based on fussing about with the call stack, so when the continuation is finally invoked, the copy of the call stack embedded in it replaces the original one, and that old execution path literally stops existing after garbage collection.
- What if the continuation hadn't been used in the lambda (if (+ (k 42) 1729) read (+ 42 1729))? Then 42 would be added to 1729, yielding 1771, and that would have 16 subtracted from it to yield 1755. To wit, the continuation would just remain unused and the call to (call/cc (some-lambda)) would have stayed rewritten as ((some-lambda) continuation-that-is-never-used), execution continuing from where it left off with no fussing about.
- What if we used another call/cc inside the call/cc'ed function or later in the program? Yes.
There is one final important note. There are aspects that live outside of continuations. The most useful of those are input/output streams, such as the standard printing functions. This means anything printed during any sort of continuation shenanigans you may conjure up stays printed. This is a key aspect of understanding what is going on with the yin-yang puzzle, as well as many other programs involving continuations. Another permanent construct, this one more explicitly permanent, is Scheme's set! function: it's basically like a variable assignment that persists throughout the program, regardless of what sort of continuation maze you set up. (And, in fact, it can influence the control path of that continuation maze, if you bring in conditionals that are based on values in these variables.) In terms of the call stack explanation above, one just thinks of the variables as existing in some internal lookup within the interpreter, as opposed to in the program space.
There are plenty of resources on the internet dedicated to helping the average Joe programmer to understand call/cc. A couple of the most useful, I found, are Madore's own internet shrine, and the Scheme Wiki's tutorial of sorts. My treatment of call/cc here is by no means complete, so feel free to press onward if you find this brand of coding masochism comforting.
We can now almost approach the puzzle, but we have to deal with what each part of the program actually means. Some of these definitions are changed a little from the standard Scheme usage for ease of comprehension, so I will leave out, gloss over, or not-exactly-correctly explain things when it is necessary to do so; don't expect that any knowledge gleaned from here might apply directly in Scheme programming without checking it against the R5RS first.
display is an obvious printing function. call/cc is the thing we just spent the last section discussing.
The lambda construct is a way of writing anonymous functions, i.e. functions that don't need names or full-on definitions to work. It comes in the form (lambda (var1 var2 ...) body). It takes as many arguments as there are variables in the list of variables (var1, etc), binds them (meaning attaches the value passed at invocation-time to the name specified at definition-time), and then executes all the functions in the body (there can be more than one) with the proper variable names bound. For example, ((lambda (x y) (sqrt (+ (* x x) (* y y)))) 3 4) binds x to 3 and y to 4, and then evaluates to 5. If there are multiple body statements, then each is executed in turn, but only the last is the return value. For example, ((lambda (x y) (display y) (display x) (sqrt (+ (* x x) (* y y)))) 3 4) will print 4 and 3, and then return the Pythagorean diagonal of 5.
In our specific circumstance, (lambda (c) c) is the identity function, which returns whatever it was given, and (lambda (cc) (display "@") cc) is almost the same, except it prints an @ when invoked. Similarly, (lambda (cc) (display "*") cc) prints an * before returning its passed value.
let* is an interesting beast. It comes from the let family of functions, which create bindings to variables. It is used in the form (let* (bindings) body), where bindings is in the form of ((var1 init1) (var2 init2) ...). With let, all the initN values are computed/evaluated/whatever-the-magic-that-LISP-performs-is-called, and then the bindings to the respective varN variables are made, so that they can then be referred to within the contents of body by name. Explicitly stated, first all of init1 to initN are computed, then bound to var1 through varN. With let*, however, the bindings are made sequentially: first init1 is computed and bound to var1, then init2 to var2, and so on. All of var1 through varN are visible to—and therefore usable by and referencable within—varNplus1 during computation of initNplus1. (There also exists a letrec in which the bindings happen before the computations, and then the values are filled in afterwards, allowing for recursive definitions, but that's not important to us right now.)
Armed with this knowledge, we can dissect the yin-yang puzzle.
The first thing to notice is that the general form of the puzzle is a single let* construct, with a yin binding followed by a yang binding, then an application of yin on yang. This signals to us that yin is always defined in a fresh environment, while yang exists only after yin does, i.e. within yin's continuation.
Now, we note the structure of each binding. Inspecting yin first, we see (call/cc (lambda (c) c)) generates a continuation at that point, and will evaluate as ((lambda (c) c) <cont>), which trivially reduces to <cont>. Then, this continuation is passed to (lambda (cc) (display "@") cc), which prints an @ and then returns its argument. So, in summary, a continuation is generated, an @ is printed, and then yin is bound to that continuation.
Note that ((lambda (cc) (display "@") cc) (call/cc (lambda (c) c))) is not the same thing as (call/cc (lambda (cc) (display "@") cc)). The former's continuation is about to be passed to the printing lambda, while the latter's continuation is outside of the printing lambda, just before the binding. This distinction will become important in a moment.
Looking now at yang, we see it is the same, except for two things. Firstly, it prints * and not @, and secondly, yin has already been bound to a continuation. When yin is bound, there was no yang; when yang is bound, however, there already exists a yin. This is important to note because continuations. Continuations is why.
So, each of yin and yang receives a continuation in order, and then they are applied, one on the other. We currently have "@*" in the output stream, because when the continuations were computed in the bindings of yin and yang, they passed through their specific printers. This is where the magic happens.
To disambiguate a little on what is meant by both yin and yang having continuations, consider the futures of the points in time where the the two continuations are generated. The to-be-yin continuation represents passing through the @-printer, then binding to yin, then evaluating and binding yang to its continuation, and finally evaluating (yin yang). The to-be-yang continuation, however, already has yin bound; all it has to do is pass through the *-printer, bind to yang, then evaluate (yin yang), where, again, yin is bound. This is as opposed to in the yin continuation, where neither yin nor yang has yet been bound.
Let us denote the currently existing yin and yang continuations as C0 and C1, respectively. (yin yang) is then (C0 C1). This invokes the C0 continuation with C1 as the return value. We go back to the generation of C0, which was in the yin binding line. The call/cc that gave us C0 now returns the value C1, which passes through the @ printer, and then is bound to yin. The output is now "@*@".
Now we must bind yang again. We once again call/cc on the identity function, but now, note that the future of yang is to appear in (yin yang) where yin is C1, not C0 like before. Therefore, yang generates a new continuation—call it C2—whose future is to pass through the *-printer, be bound to yang, and then evaluate (yin yang) => (C1 <new-yang-cont>).
So this C2 goes through the motions of passing through the identity function, passing through the *-printer (output now "@*@*"), and being bound to yang. yang is now C2, so (yin yang) => (C1 C2).
C1 "returns" C2. Since C1 was generated to be yang's continuation, after C0 was bound to yin, the yang call/cc now returns C2. Which then prints an asterisk (output "@*@**"), and binds to the yang whose yin is C0. (yin yang) => (C0 C2).
C0 "returns" C2. C0 was generated in the yin binding, so the yin call/cc returns C2. An @ is printed (output "@*@**@"), and C2 binds to yin. This initiates a new continuation for the yang call/cc, C3, whose future is to print an asterisk, bind to yang, and be passed as an argument for yin => C2. C3 prints an asterisk (output "@*@**@*"), and binds to the yang whose yin is C2. (yin yang) => (C2 C3).
C2 was generated by the yang whose yin was C1. An asterisk is printed ("@*@**@**"), yang => C3, (yin yang) => (C1 C3).
C1 was generated by the yang whose yin was C0. An asterisk is printed ("@*@**@***"), yang => C3, (yin yang) => (C0 C3).
C0 was generated for yin, so now an @ is printed ("@*@**@***@") and yin => C3. By now you can see a pattern forming. We can guess that, by the way that all the previous continuations acted, yang will make a C4, which will be passed down the line of C3, C2, C1, to C0, which will bind it to a yin and create a fresh continuation, C5. C5 will then proceed to go down the line, and so on.
The following is a short summary, detailing the explanation above, as seen by the evaluating the code directly. To keep it short, (lambda (c) c) has been rewritten as i, and the printing lambdas as p@ and p*, respectively.
(let* ((yin (p@ (call/cc i))) (yang (p* (call/cc i)))) (yin yang))
=> (let* ((yin (p@ (i C0))) (yang (p* (call/cc i)))) (yin yang))
=> (let* ((yin (p@ C0)) (yang (p* (call/cc i)))) (yin yang))
=> (let* ((yin C0) (yang (p* (call/cc i)))) (yin yang)) ; @
=> (let* ((yin C0) (yang (p* (i C1)))) (yin yang)) ; @
=> (let* ((yin C0) (yang (p* C1))) (yin yang)) ; @
=> (let* ((yin C0) (yang C1)) (yin yang)) ; @*
=> (C0 C1) ; @*
;; C0 returns C1 ; @*
(let* ((yin (p@ (call/cc i))) (yang (p* (call/cc i)))) (yin yang)) ; @*
=> (let* ((yin (p@ C1)) (yang (p* (call/cc i)))) (yin yang)) ; @*
=> (let* ((yin C1) (yang (p* (call/cc i)))) (yin yang)) ; @*@
=> (let* ((yin C1) (yang (p* (i C2)))) (yin yang)) ; @*@
=> (let* ((yin C1) (yang (p* C2))) (yin yang)) ; @*@
=> (let* ((yin C1) (yang C2)) (yin yang)) ; @*@*
=> (C1 C2) ; @*@*
;; C1 returns C2 ; @*@*
(let* ((yin C0) (yang (p* (call/cc i)))) (yin yang)) ; @*@*
=> (let* ((yin C0) (yang (p* C2))) (yin yang)) ; @*@*
=> (let* ((yin C0) (yang C2)) (yin yang)) ; @*@**
=> (C0 C2) ; @*@**
;; C0 returns C2 ; @*@**
(let* ((yin (p@ (call/cc i))) (yang (p* (call/cc i)))) (yin yang)) ; @*@**
=> (let* ((yin (p@ C2)) (yang (p* (call/cc i)))) (yin yang)) ; @*@**
=> (let* ((yin C2) (yang (p* (call/cc i)))) (yin yang)) ; @*@**@
=> (let* ((yin C2) (yang (p* (i C3)))) (yin yang)) ; @*@**@
=> (let* ((yin C2) (yang (p* C3))) (yin yang)) ; @*@**@
=> (let* ((yin C2) (yang C3)) (yin yang)) ; @*@**@*
=> (C2 C3) ; @*@**@*
;; C2 returns C3 ; @*@**@*
(let* ((yin C1) (yang (p* (call/cc i)))) (yin yang)) ; @*@**@*
=> (let* ((yin C1) (yang (p* C3))) (yin yang)) ; @*@**@*
=> (let* ((yin C1) (yang C3)) (yin yang)) ; @*@**@**
=> (C1 C3) ; @*@**@**
;; C1 returns C3 ; @*@**@**
;; etc...
At every "pass-down" from the C[N] continuation to the C[N-1], an asterisk is printed. When that most recent continuation is passed to C0, an @ is printed. Then a new continuation is formed, and another asterisk is printed, and then the asterisk-printing chain begins anew, with one more member this time.
Such is the nature of continuations.
QED.
Sources, in no particular order:- http://stackoverflow.com/questions/2694679/how-does-the-yin-yang-puzzle-work
- http://stackoverflow.com/questions/2827620/call-cc-in-lua-possible/2828499#2828499
- https://groups.google.com/forum/?fromgroups=#!topic/comp.lang.scheme/Fysq_Wplxsw
- https://groups.google.com/forum/?fromgroups=#!topic/comp.lang.scheme/pUedvrKYY5w
- http://people.csail.mit.edu/jaffer/r5rs_6.html
- http://community.schemewiki.org/?call-with-current-continuation
- http://www.madore.org/~david/computers/callcc.html
- http://www.madore.org/~david/programs/unlambda/
Also, Madore is an E2 user! Awesome!