Life in Clojure

A few months ago I was looking at the Life in APL video on YouTube and it occurred to me that other than the use of mathematical symbols for functions, the approach was entirely functional. This made me wonder if it would be easier (and perhaps clearer) to do it in Clojure. My goal was to show that Clojure was just as capable, and hopefully easier than APL.

I created Life in Clojure to do this, and it worked out pretty well. What I need to do now is to record a REPL session for YouTube, just like the original. However, there are a couple of things that were shown in the APL video that are missing in Clojure, and I needed to fill in the gaps. It's these gaps that I've been thinking about ever since, wondering if I could/should do better.

Since I don't have a video, Life in Clojure is implemented in a namespace that contains a REPL session. Just use "lein repl" and paste in that namespace file and it'll do everything in the same order as the APL video, with a couple of deviations. I've commented each operation with the appropriate dialog from the original APL video, so it should be easy to see the parallels. However, for anyone who wants to see it running, the final program is implemented in the life.core namespace.

Setup

The first change between these Clojure and APL implementations is that Clojure needs to explicitly import things into the environment, while the APL video seemed to demonstrate all operations being available by default. Given that most of these were matrix operations, and APL specializes in matrix operations, then it isn't surprising that these are built in. Fortunately, all the applicable operations are available to Clojure via core.matrix, so this was a simple require, along with a project dependency. I suppose I will need to show these at the start of any video I make (if I ever make it).

Output

The APL video showed the use of a display function that prints a matrix to the console. Clojure's pretty-print will also show an m*n matrix reasonably well, and I could have chosen to use that. However, the APL code is also printing a vector, and then a matrix, where each element is an m*n matrix, and pretty-print just messes that up.

The APL demo seemed to be using a library function to handle this printing, so it didn't feel like cheating to write my own. It's a bit clunky, as it's specialized to only handle 2, 3 or 4 dimensions, but it works.

The bigger issue was showing the current state of the Life playing field. APL was using a draw function to update the contents of a text file, and opened a window that dynamically showed the contents of that file as it was updated. Using a file proxy like this made the display easy in APL, but it's hack that I did not think was worth duplicating. Instead, I created a function to convert the playing field into an image, and sent the image to the display.

Creating an image from the matrix was an easy Swing-based function (just draw filled-in rectangles based on the contents of each matrix cell, and return the image). However, rendering it was a little harder.

Following the APL approach, I wanted a function that would "send" the image to the screen, and forget about it. However, Swing requires an event loop, and several listener objects to allow the window to interact with the environment. These sorts of objects do not fit cleanly into a purely function program, but using proxies and closures does a reasonably good job.

I was able to hide the default window parameters (width/height, etc), but had trouble with the fact that the APL program simply sends the output to the rendered file without defining it as a parameter. The main problem is that the open-window function should return the created resource (the window) and this value should be captured and "written to" each time the life algorithm needs to re-render the playing field. I could do that, but introducing this resource handling into the main algorithm would get in the way of the "clarity" that the demo was trying to express. In the end, I opted to create a global atom (called canvas) that gets updated with each call to draw. I would not usually write my code this way, but it seemed to be the best way to duplicate the APL demo.

Of course, not a lot of programs use Swing these days. The majority of programs I see with GUIs use a browser for the UI. So when a couple of my friends saw this app, they suggested reimplementing it in ClojureScript, and rendering in a web page. Funnily enough, the DOM ends up being an equivalent to the global canvas that I have in the Swing application, so the calling code would not need to change its approach. However, core.matrix does not yet support ClojureScript, so I haven't tried this yet.

Matrix Math/Logic Operations

One minor inconvenience in using the APL approach is that it uses the C-style idiom that the number 0 is the value for "false" and anything else is "true". The APL demo algorithm uses 1 to indicate that a cell is occupied, and then uses addition between cells to determine the values for subsequent generations. This creates an elegant shortcut for determining occupation for subsequent generations in Life, but it isn't as elegant in Clojure.

Of course, Clojure truthy values identify all numbers as "true", and only nil or boolean "False" have a falsey value. Without the zero=false equivalence, then the algorithm gets more awkward. Based on that, I created a function that takes a single argument boolean function and returns an new function that returns the same result mapping false->0 and true->1. This allows matrix addition to be used as the basis of the AND and OR operations, just like in the APL demo. It works fine, but I'm uncomfortable that it currently only handles the 2 argument case for the AND and OR matrix operations. Also, I've since learned a little more about core.matrix, and I think there may be better ways to define these functions. I'll have to look into that a little more.

There is also a convenience function I created which is used to map a matrix to boolean 1/0 based on each cell being equal to a given value. It's a simple one-liner that makes it easier to compare to the equivalent APL code but it always felt a little inelegant. However, this might just be due to the need to map booleans to numbers.

The other APL function that wasn't directly available to me was the "take" of a matrix. This operation allows a 2-D "slice" from a larger matrix, but also deals with the insertion of a small matrix into a larger "empty" matrix. After some examining of core.matrix I discovered that shape provided similar functionality, though it needs help from compute-matrix to handle expansions. I wrapped this in the function takeof to duplicate how the APL demo used it.

Powers and Power Limits

Up to this point, everything was either translating a library from APL (display, the graphics output, or some simple wrappers to smooth out matrix access, and handle the integer/boolean equivalence in APL). But right at the end of the video, the APL demonstration uses a couple of functions that had no equivalents in the Clojure. These are the power function and the power-limit function.

The behavior of the power function is to take a single argument function and apply it to an argument, take the result and apply the function to that, and keep repeating the application of the function as many time as requires. The specific operation of power is to return a function that applies the argument function iteratively like this for the defined number of times.

As an example, the 5th power of clojure.core/inc applied to 0 is:

=> (inc (inc (inc (inc (inc 0)))))
5

So (power-function inc 5) returns a function that applies inc 5 times:

=> ((power-function inc 5) 3)
8

The power-limit function is similar, in that it iteratively applies the provided function, however it does not stop iterating until it reaches a fixpoint value. That is, until the output of the function is equal to the input.

An example function that has a fixpoint is:

(defn has-fixpoint [x] (min (inc x) 3))

This returns either the increment or 3, whichever is smaller. If this is applied iteratively, then it will always reach a value of 3 and stay there.

My first approach to this naïvely executed the provided function n times:

(defn power [f n]  (case n
    0 identity
    1 f
    (fn [x]
      (loop [r x, i n]
        (if (zero? i)
          r
          (recur (f r) (dec i)))))))

This works, but one look at it was enough to tell me I'd gone down a blind alley. case statements always suggest that something is inelegant, and loop/recur often means that the Clojure's laziness and seq handling are being ignored, which implies that I may have missed an abstraction. Both are a code smell.

That's when I remembered clojure.core/iterate. This function applies a function iteratively, returning an infinite lazy sequence of these iterations. The required power is just the nth entry in that sequence, so the power function just becomes:

(defn power [f n] #(nth (iterate f %) n))

Much better.

Similarly, I'd implemented the power-limit function using a loop until the input equalled the output:

(defn power-limit [f a]
  (loop [a a]
    (let [r (f a)]
      (if (= r a)
        r
        (recur r)))))

Unlike the original version of the power function, I like this approach, since it clearly does exactly what it is defined to do (apply the function, compare input to output, and either return the output or do it again).

I already mentioned that loop/recur often suggests that I've missed an abstraction. This, along with neglecting to use the iterate function for power, had me wondering if there was a more idiomatic approach here. That's when I realized that I could pair up the iterated sequence of the function with its successor, and compare them. The result is:

(defn power-limit [f a]
  (let [s (iterate f a)]
    (ffirst
      (drop-while (partial apply not=)
                  (map vector s (rest s))))))

The iteration sequence is captured in the let block so that it can be re-used when pairing the sequences in the map operation. The vector is being used here to capture each iteration with its successor in vectors of pairs. Because iterate is lazy, the sequence of iterations is only calculated as needed, and only calculated once.

The drop-while drops off all pairs of values where the values are not equal. The not= operation can take multiple arguments, so rather than pull each of the two values out, I'm using partial/apply to provide the pair as all the arguments. The result of the drop-while/map is a sequence of pairs of argument/results (which are all equal). The final result is to take the first value from the first pair, hence the use of ffirst.

Conceptually, I like it more, and I think that it fits into Clojure better. However, it's less clear to read then the loop/recur solution. So I'm torn as to which one I like more.