Typed Clojure Game of Life

I've always liked the Game of Life implemented with stencil convolution[1]. It's very declarative.

Stencil convolution[2] transforms a matrix (often an image) by taking a small matrix--the stencil--and using it as a set of weights to add all that cell's neighbors. Let's imagine our stencil is the following matrix:

    1 2 3
    4 5 6
    7 8 9

Then, to process each cell in the big matrix, we start by putting the 5 over that cell. The new value for the cell is going to be 1 times the cell up and to the left plus 2 times the cell directly above plus 3 times the cell up and to the right and so on.

If we represent the Game of Life as a matrix--a two dimensional array of Ints--we can use a stencil to easily compute the neighbor count. We would use this matrix:

    1 1 1
    1 0 1
    1 1 1 

Applying this stencil gives us a function that goes from the matrix of alive cells to a matrix of neighbor counts. Then, to do a step in the game of life, we just zip the two matrices together with the transition function.

The neat bit is that the real code looks pretty close to what I have just said! For example, here is how the stencil looks:

    neighbors = [stencil2|1 1 1
                          1 0 1
                          1 1 1|]

We can use basically the same transition function as in the post:

    transition a 2 = a
    transition _ 3 = 1
    transition _ _ = 0

And the actual step algorithm:

    step grid = R.computeUnboxedS . R.zipWith transition grid $ 
                  mapStencil2 (BoundConst 0) neighbors grid

(BoundConst 0) just tells the stencil to treat every square outside the large input matrix as 0. R.computeUnboxedS just turns the result of zipWith back into an unboxed array.

Now, the computeUnboxedS function call is not really intuitive. Unless you knew how the API was supposed to work, you would not think of it. This is where Haskell's types come in, acting like active documentation: you can see that you need the computeUnboxedS function because that's the only way to get from the type at the result of zipWith to the type you actually want!

Anyhow, this is not the best way to implement life, admittedly. The biggest shortcoming is that, since you're using an array, the field is always bounded to the same size and you're always representing every cell, even ones that won't be alive for generations. Mostly, this is just a great example to see how stencil convolution works!

[1]: http://www.slideshare.net/kizzx2/repagolpdf

[2]: http://research.microsoft.com/en-us/um/people/simonpj/papers...

It's a bit tongue-in-cheek to compare this to Edward Kmett's FP Complete articles on Cellular Automata, but they're a really interesting read if you want to get your feet wet with some advanced Haskell programming

https://www.fpcomplete.com/user/edwardk/cellular-automata

The series began as trying to explain the value of the Store Comonad for generalizing the "Cellular Automata are Comonads" notion, but then dipped into how to build resumable folds to implement CRC hashing for pngs.

The final article pulls a really great trick out where by writing down a very general type for cellular automata as comonads it was possible to automatically generate code which generalizes CAs to stranger topologies (like a cylinder).

The final code including the CA code, the strange topologies, the PNG encoder, and a webserver to display the whole thing online is all probably shorter than the Java CA code would have been here.

> my gen Y attention span

I can't believe people internalize this "Gen Y" shit. It's just ageism. There's always been something to distract us.

The FP Scala vs. OO Scala was nice to include. All too often you see simply OO Scala.

My try on a more 'idiomatic' haskell version : https://gist.github.com/arianvp/6814753

I have no idea what the inputs need to be. I coded by types. Code compiles but has never been tested but probably works. (Ha, gotta love haskell)

edit: Think it works

> I couldn't bring myself to do a Java version but I'd expect it to be several times larger

I'm a big fan of Clojure and don't have much love for Java, but this is a little unfair. I especially think doing a Java 8 version with lambdas would be an interesting comparison.

Interesting that the Haskell version is the most concise and also has as much or more typing than the rest!

Obligatory http://www.youtube.com/watch?v=a9xAKttWgP4 APL version explained.

Here's one I found online http://dfns.dyalog.com/s_life.htm

    life←{                             ⍝ John Conway's     "Game of Life".
        ↑1 ⍵∨.^3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵ ⍝ Expression for next generation.
    }

Completely awesome convolution method.

The width of each window isn't the same for Scala compared the others. It'd have been nice to see them all the same width with text wraparound.