The call/cc yin-yang puzzle is an ancient piece of Scheme code, which was written—or more accurately discovered—by David Madore in the year 1999 upon his invention of the esoteric programming language Unlambda. It is a rite of passage for aspiring Schemers to grok these five lines, if they claim true mastery over the power of the continuation. This is my attempt at understanding of its mysterious action, from the only-slightly-less-ancient era of 2012.
Here is the code in its original glory.
(let* ((yin ((lambda (foo) (newline) foo) (call/cc (lambda (bar) bar)))) (yang ((lambda (foo) (write-char #\*) foo) (call/cc (lambda (bar) bar))))) (yin yang))
Here is a prefix of its output.
* ** *** **** *****
It prints increasingly long lines of asterisks; first one, then two, and so on. The challenge of the puzzle is to explain why.
To begin my analysis, let me rewrite the problem a bit, to make it a bit clearer what is going on:
(define I (lambda (bar) bar)) ; Identity (define N (lambda (foo) (newline) foo)) ; Newline (define A (lambda (foo) (write-char #\*) foo)) ; Asterisk (let* ((yin (N (call/cc I))) (yang (A (call/cc I)))) (yin yang))
Both bindings have the pattern of generating a continuation, printing something, and then binding the continuation.
I’ll do my best to explain what a continuation is in a second, but first off,
it behooves us to understand which flavour of
let we are using.
(let* ((a foo) (b bar)) blah) performs its assignments in a strictly-enforced order.
foo is evaluated, then bound to
a, and only then
bar is evaluated and bound to
This order of operations is crucial for the continuations to behave correctly.
a is bound and visible to
(b bar) when
bar is being computed. Keep this in mind.
I guess I should take a moment now to explain precisely what a continuation is, and how
call/cc gives us one,
for the sake of the readers that aren’t familiar.
A continuation, according to Wikipedia is “an abstract representation of the control state of a computer program”. For all intents and purposes, it is a snapshot of a partially executed program, packaged up into a function, with a hole at the current position. Invoking the function with an argument will plug that argument into the hole in the program, and continue execution from there.
If I may be permitted an example, consider the following code.
(define (pythag a b) (sqrt (+ (* a a) (* b b)))) (pythag 3 4)
Under some reasonable assumptions about the order of evaluation of expressions,1
the continuation of this program at the second
* operation would be the function
(lambda (arg) (sqrt (+ 9 arg))).
At that point, the program has just calculated that
(* 4 4) is equal to
16, and is poised to invoke the continuation with that result.
call/cc is short for
call-with-current-continuation, and what it does is it takes the current continuation of your program—at the
call/cc—wraps it up in a lambda, and just gives it to the program for use.
(call/cc f) evaluates to
(f Cont) where
Cont is the continuation of
(call/cc f), i.e. the current one when
call/cc is called.
While it is nothing if not aptly named, its behaviour can be a bit confusing and opaque, and its implications might be unclear at first.
Your first instinct might be to use
call/cc as an early abortion mechanism, a sort of hackish try-catch block where your
f can invoke the continuation to error out safely if if so desires.
But the true power is in calling something like
(call/cc I), using our identity function
I to let the continuation escape.
Then we can put it in our pocket, do some computation, and subsequently invoke the continuation with the result, effectively going back in time with information from the future.
Some operations, like outputs and
set!s, exist outside of the “program-timeline”,
so there is still a discernable narrative, from the programmer’s point of view.
However, this control of the flow of time and hence of the flow of the program
lets you implement arbitrarily interesting control structures, like
break-able loops, Pythonic generators, full coroutines, and so on, in a uniform way.
I’ll discuss the implementation of this feature a bit more towards the end of the post, but conceptually we now understand how continuations work, at least at a low level.
So let’s return to the puzzle.
I will proceed to evaluate2 it by hand one step at a time, displaying each line. Then we can refer back to it as I explain.
As a convention, I’ll name the continuations that are created
C2, and so on in turn.
A is called, I will record that with a comment at right.
(let* ((yin (N (call/cc I))) (yang (A (call/cc I)))) (yin yang)) (let* ((yin (N (I C0))) (yang (A (call/cc I)))) (yin yang)) (let* ((yin (N C0)) (yang (A (call/cc I)))) (yin yang)) (let* ((yin C0) (yang (A (call/cc I)))) (yin yang)) ; N (let* ((yin C0) (yang (A (I C1)))) (yin yang)) ; N (let* ((yin C0) (yang (A C1))) (yin yang)) ; N (let* ((yin C0) (yang C1)) (yin yang)) ; NA (C0 C1) ; NA (let* ((yin (N C1)) (yang (A (call/cc I)))) (yin yang)) ; NA (let* ((yin C1) (yang (A (call/cc I)))) (yin yang)) ; NAN (let* ((yin C1) (yang (A C2))) (yin yang)) ; NAN (let* ((yin C1) (yang C2)) (yin yang)) ; NANA (C1 C2) ; NANA (let* ((yin C0) (yang (A C2))) (yin yang)) ; NANA (let* ((yin C0) (yang C2)) (yin yang)) ; NANAA (C0 C2) ; NANAA (let* ((yin (N C2)) (yang (A (call/cc I)))) (yin yang)) ; NANAA (let* ((yin C2) (yang (A (call/cc I)))) (yin yang)) ; NANAAN (let* ((yin C2) (yang (A C3))) (yin yang)) ; NANAAN (let* ((yin C2) (yang C3)) (yin yang)) ; NANAANA (C2 C3) ; NANAANA (let* ((yin C1) (yang (A C3))) (yin yang)) ; NANAANA (let* ((yin C1) (yang C3)) (yin yang)) ; NANAANAA (C1 C3) ; NANAANAA (let* ((yin C0) (yang (A C3))) (yin yang)) ; NANAANAA (let* ((yin C0) (yang C3)) (yin yang)) ; NANAANAAA (C0 C3) ; NANAANAAA (let* ((yin (N C3)) (yang (A (call/cc I)))) (yin yang)) ; NANAANAAA (let* ((yin C3) (yang (A (call/cc I)))) (yin yang)) ; NANAANAAAN (let* ((yin C3) (yang (A C4))) (yin yang)) ; NANAANAAAN ...
Because the time-travel metaphor is probably the most apt way to understand the operation of the puzzle, thinking about the “past” and “future” of each continuation is crucial to following the behaviour.
So, to start,
yin spins up a continuation
C0, whose future is to be bound to
yin and then evaluate
yang creates a continuation of its own,
C1 lives in a timeline where
yin is bound to
We continue to the evaluation of
(yin yang) = (C0 C1).
C1 back in time to be bound to
yang generates a new continuation
C2, it’s in a different timeline
with a different
yin binding than its own past.
C2 and evaluate
(yin yang) = (C1 C2).
At this point,
C2 goes back (or maybe sideways?) in time to the creation of
C1, and binds
In this timeline,
(yin yang) = (C0 C2) sends
C2 even further back in time to be bound to
yang generates a new continuation
C3, it’s in a different timeline
with a different
yin binding than its own past.
C3 and evaluate
(yin yang) = (C2 C3).
(Do you notice history repeating itself?)
C3 is sent back to when
C1, so we eval
C3 is sent back to when
C0, so we eval
C3 is sent back to the very beginning, so we spin up
C4 and eval
Continuing the pattern, we see that
C[n+1] is created in a timeline where
We proceed to evaluate
(C[n] C[n+1]), which passes it down to
(C[n-1] C[n+1]), and so on down to
After that final step,
C[n+1] is the new
yin and we create the next continuation.
The continuations arrange themselves in a chain, and new continuations are passed down this chain until they reach
at which point they trigger the creation of the next continuation.
It remains to describe the printing.
Well, newlines are printed when we bind
yin—technically just before we bind it—and asterisks when we bind
Whenever we bind
yin, we know that the next step is to create a new continuation, and repeatedly bind it to
yang as we pass it down the chain to
Concretely, upon the binding of
yin, we print a newline, generate
n+1 asterisks—one for each of
C0 as we pass it down—and then bind
So altogether we should expect a newline, followed by 0+1 asterisks, then a newline followed by 1+1 asterisks, then a newline and 2+1 asterisks, and so on.
This is precisely the output of the yin-yang puzzle!
To finish off, I’ll make an attempt at rewriting the puzzle in so-called continuation-passing style, in which each function is called by explicitly passing its continuation, and each function is defined by evaluating the provided continuation with the computed result.
; CPS versions of "primitives" (define (I& x k) (k x)) (define (N& x k) (newline) (k x)) (define (A& x k) (write-char #\*) (k x)) (define (call/cc& f& k) (f& k k)) ; microwave on high for 4 min (define (yin-yang& k) (call/cc& I& (lambda (early-cont) (N& early-cont (lambda (yin) (call/cc& I& (lambda (later-cont) (A& later-cont (lambda (yang) (k (yin yang))))))))))) ; or pop it in the oven at 350 for 18 min (define (provide-cc& k) (call/cc& I& k)) ;=>(k k) (define (yin-yang) (provide-cc& (lambda (yin) (newline) (provide-cc& (lambda (yang) (write-char #\*) (yin yang)))))) (yin-yang) ; runs forever
Programming in this style seems at first like an exercise in pedantry,
but its purpose is to allow you direct access to the continuation, so that functions like
call/cc can be implemented very easily.
As well, by giving each function explicit control of the continuation, each function has the ability to abort computation at any time, or basically do whatever it wants.
Maybe it’s a bit scary to trust each and every function with that power,
but in any case this is why we tend only to give this power to the compiler, and make everybody else ask for permission to see the future.
Also it’s a bit of a misattribution of agency, because programming usually occurs at a level above CPS-transforms,
so this transformation can introduce multiple layers between what would otherwise be a single logical function—viz.
It’s pretty trippy to think about, though.
provide-cc& could be reasonably interpreted as ‘giving the future to the future’.
If you have the patience of a computer or a god, then you might want to try to perform a few beta-reductions and alpha-conversions on this code to see how the printing statements come out of the woodwork upon execution. Or if you’re sane you can just not do that.
In any case, that’s pretty much all I have to say about the yin-yang puzzle. Continuations themselves have many more interesting applications and theoretical implications, but that stuff could fill a book or five. So I’ll save the rest for another time.
Let me come clean and say that I’m not a computer scientist, nor a programmer, and I haven’t actually touched a Scheme interpeter in like three years. I couldn’t even be bothered to find one for this ‘blog post. So this is me merely covering my ass as I pretend to remember how Scheme works. ↩
See footnote 1. ↩