Yin Yang

An old puzzle about call/cc in Scheme. Don’t know the original source, possibly that place with the dome near the Charles River:

(let* ((yin ((lambda (cc) 
               (display #\@) cc) 
               (call-with-current-continuation (lambda (c) c))))
       (yang ((lambda (cc) 
                (display #\*) cc) 
                (call-with-current-continuation (lambda (c) c)))))
  (yin yang))

First thing is to simplify somewhat, we don’t seem to lose anything essential by getting rid of the outer lambdas:

(let ((yin (call-with-current-continuation (lambda (c) c))))
  (display #\@)
  (let ((yang (call-with-current-continuation (lambda (c) c))))
    (display #\*)
    (yin yang)))

OK, still seems to work. Let’s try and work this out informally – yin is bound to a continuation that sets yin to its argument, prints something, then binds yang to a continuation that prints something else and whatever the first continuation was applied to is applied to the argument of the second continuation. Hmmm, so far, as clear as mud, sounds like that Marx brothers sketch.

Let’s try and write down what the continuations are, to do that properly we need to convert to continuation passing style, CPS. Every function has an extra argument, its continuation and instead of returning a value, it calls its continuation on the value in a tail call. So, without further ado:

(define (id x) x)
(define ((id2 x) k) (k x))
(define (((throw k) x) k2) (k x))
(define ((ccc f) k) ((f (throw k)) k))

((ccc id2)
 (lambda (k) 
   (display #\@)
   ((ccc id2)
    (lambda (x)
      (display #\*)
      ((k x) id)))))

Here, id2 is a CPS-style identity function – it just applies the continuation k to its main argument x. throw can be used to replace the current continuation, ccc is our CPS style call-with-current-continuation, and uses throw to replace the current continuation.

id is our ‘top-level’ continuation, it doesn’t really matter what it is – it doesn’t ever get called.

Still as clear as mud, simplifying a bit more might help. Let’s give names to the continuation functions and pull them out to the top level as combinators:

(define ((g k) x) 
  (display #\*) 
  ((k x) id))

(define (f k) 
  (display #\@) 
  ((ccc id2) (g k)))

((ccc id2) f)

Now, running through our definition of ccc, we get:

((ccc id2) k) => ((id2 (throw k)) k) => (k (throw k))

Sort of what we expect, we call the current continuation with the current continuation (wrapped in throw, which essentially converts a continuation into a normal function that itself takes a continuation as a parameter). So now we have:

(define ((g k) x) 
  (display #\*) 
  ((k x) id))

(define (f k) 
  (display #\@) 
  ((g k) (throw (g k))))

(f (throw f))

Maybe some more inlining would help:

(define ((g k) x) 
  (display #\*) 
  ((k x) id))

(define (f k) 
  (display #\@) 
  (display #\*) 
  ((k (throw (g k))) id))

(f (throw f))

Or maybe we can get some insight by omitting the IO and just writing:

(define ((g k) x) ((k x) id))
(define (f k) ((g k) (throw (g k))))
(f (throw f))

Now:

(f (throw f)) => 
((g (throw f)) (throw (g (throw f)))) =>
(((throw f) (throw (g (throw f)))) id) =>
(f (throw (g (throw f)))) => 
((g (throw (g (throw f)))) (throw (g (throw (g (throw f)))))) =>
(((throw (g (throw f))) (throw (g (throw (g (throw f)))))) id) =>
((g (throw f))(throw (g (throw (g (throw f)))))) =>
(((throw f)(throw (g (throw (g (throw f)))))) id) =>
(f (throw (g (throw (g (throw f)))))) => ...

I’m sure you get the picture.

We can do a similar evaluation more succinctly by defining:

Tkxy = kx
Gkx = kxI
Fk = Gk(T(Gk))

And now:

F(TF) => 
G(TF)(T(G(TF)) => TF(T(G(TF))I =>
F(T(G(TF))) => 
G(T(G(TF)))(T(G(T(G(TF))))) => T(G(TF))(T(G(T(G(TF)))))I => 
G(TF)(T(G(T(G(TF))))) => TF(T(G(T(G(TF)))))I =>
F(T(G(T(G(TF))))) => ...
F(T(G(T(G(T(G(TF))))))) => ...

All the Ts and Is do here is cancel one another out, so we can define, even more succinctly (and inlining G a little):

Fk = k(Gk)
Gkx = kx

FF => 
F(GF) => GF(G(GF)) =>
F(G(G(F))) => G(G(F))(G(G(G(F)))) => G(F)(G(G(G(F)))) => 
F(G(G(G(F)))) => ...
...

It’s curious that here, F = λk.k(Gk) = λk.k(λx.kx) and λx.kx is eta-convertible to just k, so FF = (λk.k(λx.kx))(λk.k(λx.kx)) is eta-convertible to Ω = YI = (λx.xx)(λx.xx).

Returning to scheme, we can do a similar trick and get:

(define ((g k) x) (display #\*) (k x))
(define (f k) (display #\@) ((g k) (g k)))
(f f)

or inlining the first call to g in f:

(define (f k) (display #\@) (display #\*) (k (g k)))

Now our evaluation is:

(f f) => (f (g f)) => 
(f (g f)) => ((g f) (g (g f))) =>
(f (g (g f))) => ...

Simplifying further, we end up with the equivalent program:

((lambda(k)(display #\@)(display #\*)(k (lambda(x)(display #\*)(k x))))
 (lambda(k)(display #\@)(display #\*)(k (lambda(x)(display #\*)(k x)))))

and if that isn’t cute, I don’t know what is…

Advertisements


Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s