Typed Clojure Game of Life(logaan.github.io)

93 pointsby logan-campbell13 anni fa22 comments

logaan.github.io

http://logaan.github.io/clojure/core.typed/2013/10/02/core.typed-game-of-life.html

9 comments

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...

tel13 anni fa

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.

gboudrias13 anni fa

> 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.

logan-campbell13 anni fa

I don't actually identify as Gen Y (I had to look up the dates) or as a particularly distractible person. I just wanted a pithy way of saying that the protocol issue I hit wasn't necessarily an inherent issue, but rather that I chose not to deal with it.

gboudrias13 anni fa

I understand the intent, and I don't want to undermine your point, I just find it offensive, but that would certainly put me in the minority.

hashtree13 anni fa

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

arianvanp13 anni fa

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

tel13 anni fa

The list comprehension is great, but man is prefix ((.).(.)) scary. I always rename that to (.:), use it infix, define it pointfully, and comment calling it "two-argument compose".

breckinloggins13 anni fa

> 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.

logan-campbell13 anni fa

The code is up at https://github.com/logaan/typed-game-of-life and I'd be very happy to accept a pull request with a Java example. I've done a few side by side comparisons of Clojure / Scala / Java and the Java has always been several times larger than Cloure / Scala. In a couple of cases it was 20-30x larger.

Java 8 may indeed improve this situation. Does it also introduce higher order functions for working with collections?

breckinloggins13 anni fa

Yes, through the Stream API.

logan-campbell13 anni fa

Sweet.

appamatto13 anni fa

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

chongli13 anni fa

In Haskell it's generally considered bad form to omit type annotations for your top-level functions. There is even a compiler warning for this sort of thing. Thankfully, the Haskell plugins for good editors (vim or emacs) provide hotkeys to automatically insert an inferred type annotation for a function you specify.

tel13 anni fa

It's naked-looking without them. Valid, but all the documentation is hidden.

alipang13 anni fa

Yeah this mysterious "typed haskell" thing seems to imply that the other version doesn't have types, while of course they are inferred.

bjz_13 anni fa

The source he posted on Github calls it 'annotated'[1]. I'm guessing it was just a poor choice of word.

[1] https://github.com/logaan/typed-game-of-life/blob/master/src...

logan-campbell13 anni fa

You're correct. Annotated was just too many characters to fit inside the columns I used for the thumbnail view.

I'm not so proficient a developer that I could write any amount of Haskell code without being acutely aware of its statically typed nature.

willvarfar13 anni fa

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.

kaoD13 anni fa

Certainly awesome. Note that this implementation is toroidal. My take on J[1] (code-golfed) based in the same algorithm:

  l=:[:+/(3 4=/[:+/(,/,"0/~i:1)|.])*.1,:]

De-golfed:

  life =: [: +/ (3 4 =/ [: +/ (,/ ,"0/~ i:1) |. ]) *. 1 ,: ]

[1] http://www.jsoftware.com

skndr13 anni fa

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.

MBlume13 anni fa

the picture lets you see the height and width of all of them and I think both parameters tell you things about the "shape" of the code