The call/cc Yin-Yang Puzzle

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. First, foo is evaluated, then bound to a, and only then bar is evaluated and bound to b. This order of operations is crucial for the continuations to behave correctly. In particular, 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,¹ 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. More precisely, (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 evaluate² 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 C0, C1, C2, and so on in turn. Whenever N or 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. yang creates a continuation of its own, C1, and C1 lives in a timeline where yin is bound to C0. We continue to the evaluation of (yin yang) = (C0 C1). This sends C1 back in time to be bound to yin!

Now when yang generates a new continuation C2, it’s in a different timeline with a different yin binding than its own past. We bind yang to 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 yang. In this timeline, yin is C0, so (yin yang) = (C0 C2) sends C2 even further back in time to be bound to yin.

Now when yang generates a new continuation C3, it’s in a different timeline with a different yin binding than its own past. We bind yang to C3 and evaluate (yin yang) = (C2 C3). (Do you notice history repeating itself?)

C3 is sent back to when yin was C1, so we eval (C1 C3).
C3 is sent back to when yin was C0, so we eval (C0 C3).
C3 is sent back to the very beginning, so we spin up C4 and eval (C3 C4).

Continuing the pattern, we see that C[n+1] is created in a timeline where C[n] binds yin. 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 (C0 C[n+1]). 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 C0, 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 yang. 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 C0.

Concretely, upon the binding of C[n] to yin, we print a newline, generate C[n+1], print n+1 asterisks—one for each of C[n], C[n-1], …, C0 as we pass it down—and then bind C[n+1] to yin anew. 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. yin-yang&.

It’s pretty trippy to think about, though. The function 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.