Re:Typed Clojure Game of Life
by tikhonj on Thursday October 03, 2013 @01:51PM
(#6490621)
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
(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!
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:
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:
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:
We can use basically the same transition function as in the post: And the actual step algorithm: (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...