Graphics Bugs

One of the nice things about graphics programming is that even the bugs can be fun, here’s a picture I made earlier, it wasn’t quite what I’d intended, and I don’t think it’s going to be in the Tate Modern any time soon, but I rather like it:

Complex Fibonacci

There are a couple of ways to extend the Fibonacci series to a continuous function on real or complex numbers. Here’s a nice one: the grid shows the mapping of the unit strip, 0 <= re(z), 0 <= im(z) <= 1, grid points are 0.1 apart. The real axis is picked out in red, notice that it crosses itself exactly at the points of the Fibonacci series – twice at 1 after executing a loop-the-loop (clicking on the image should give you a larger version).

The function is just the standard Binet formula, interpreted over the complex plane:
z - -φ-z)/√5
or equivalently:
z - eiπzφ-z)/√5

For negative values, the function turns into a nice spiral (the exp component dominates). Here is the 0 <= im(z) <= 0.1 strip: The red parallelogram illustrates F(z+2) = F(z+1)+F(z) still holds, even for our complex quantities.

Most of the action takes place around the origin, so let’s zoom in:

The image of the real axis passing through the points -1,1,0,1,1,2,… is clearly visible (the real axis is on the outside, the origin is the leftmost point on the red parallelogram).

Sometimes the series is extended as z - cos(πz)φ-z)/√5 which produces a mapping that takes the real line to itself, ie. taking the real part of the exponential, which is also nice, here we see the mapping of the strip 0.1 <= im(z) <= 0.2:

Again, the red parallelogram illustrates the recurrence.

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…