A pure game of life.

Pure functional programming is at the heart of scalable software design... Even when your not using a functional language.  If you've ever wondered why "learning a functional language might make you a better developer", then this post is for you.  We will take a simple problem: Conway's game of life, and demonstrate a purely functional approach to its implementation.

** update: since writing this post, I've discovered an amazing treatment of the exact same subject by Manual Rotter about 2 months ago, which is here : http://programmablelife.blogspot.com/2012/08/conways-game-of-life-in-clojure.html ** 

Just because it looks like an array doesn't mean you have to code it that way.

The simplest and most intuitive implementation of Conway's game of life uses a 2D array of cells wherein the cells are mutated to reflect the updated state during each "turn" of the game.  

Using an array data structure as a crutch for modelling 2 dimensional data, such as that in the game of life, seems like an obvious and direct approach.  

However, it comes at a very high cost.  By using the physical "place" where cell datas are stored, as the mechanism for looking up the state of cells and simulating our world, we constrain and complicate the entire simulation needlessly.  

You might be tempted to ask: How could a 2D array possibly be a bad choice for modelling a 2D world ? 

A recent talk on The Value of Values by Rich Hickey sheds light on some of the pitfalls of such "place" oriented programming - its an amazing talk, and it really extols the virtues of declarative and functional problem solving in a new light.  In particular, we can consider this scenario:

1) Storing the universe in a 2D array means that the game of life's universe size is limited to the amount of memory available.  We cannot simulate an infinitely large universe.

2) The board cannot be dynamically expanded/shrunk at runtime. 

3) If we want to apply a new feature from the universe (i.e. simulating a "natural disaster") we would have to mutate the state of the board, and can thus lead to multiple intermediate states for the universe in a given turn.

4) We must take into account the fact that, while updating the cells, you have a board that is in an intermediate state.  This might, for example, require us to copying the 2D array into a "previous" object, while writing a new 2D array out.  

Suddenly it becomes clear that the 2D array is an unscalable model for the game of life !

The reason for this is that it couples the core feature of the board - which is the simple operation of knowing wether a cell is alive or dead - to a data structure, or, as Rich Hickey might call it: a "place".  The "place" then limits the dynamics of the simulation ~

So lets try our hand at a purely functional solution to the game of life - one which doesn't couple the universe to any particular data structure, while lazily evaluating cell states.  

The basic premise of this solution is as follows:

1) The board itself is a function, rather than an array.

2) The "first" state of the board is defined as a function as well.

3) To view the results of play of a "turn" of the game, we simply apply this function to a set of coordinates - we never need to calculate or store the entire board in memory.

4) To play multiple turns - we can simply apply the board function to itself over and over again.

5) For the actual playing of the game (i.e. viewing the whole board), we simply can run Clojure's doseq against a list comprehension of the cells - this can stream the data to stdout. 

So... here's the code! Its a little bit raw at the moment, but it should be self explanatory.  This is a first iteration and comments are of course certainly welcome.  I've put this in a branch of the learn-clojure repo.

Please not - this is purely theoretical, since it doesn't use any memoization, the performance hits could really hurt you.



A pure game of life in Clojure.

(ns problems.life) 

;This function determines wether a cell is alive or dead.
;Its a simplified version of the classic life function.
; f: the initial board function (f), 
; x, y (the x/y coordinates)
(defn live [f x y] 
  (let [neighbors
                  (+ 
                   (max 0 (f x (dec y)))
                   (max 0 (f x (inc y))) 
                   (max 0 (f (inc x) y))
                   (max 0 (f (dec x) y))
                   (max 0 (f (dec x) (dec y)))
                   (max 0 (f (inc x) (inc y)))
                   (max 0 (f (dec x) (inc y)))
                   (max 0 (f (inc x) (dec y))))]
    (cond
      (= neighbors 0) 0
      (= neighbors 1) 1
      (= neighbors 2) 1
      (= neighbors 3) 0
      :else 0)))

;The gameboard is a function with -1's for boundaries.
(defn boardstart [x y]
  (cond 
     (or (> x 2) (> y 2) (> 0 x) (> 0 y)) -1 ; Out of range
     (= 0 x) 1 ; Cells on top are alive.
     :else 0))

;Create a function which will dynamically calculate the state of the board when invoked.
(defn newboard [f]
  #(cond 
     (> 0 (f %1 %2)) -1 ; Out of range
     :else (live f %1 %2)))

;Print the current state of the board
(defn printstate [board size]
  (println "starting state dump")  
  (doseq [x (range size) y (range size)] 
      (println x " " y " | " (board x y))))

;To play, we simply call newboard over and over again. 
;The effect is simply to calculate the gameboard functionally, so 
;the board is recalculated at every call. Next step will be to add a bitcache or something
;of the sort that is decoupled from the calling of the board.  
(defn main1 []
  (print "\n------------\n")
  (printstate boardstart 3)
  (print "\n------------\n")
  (printstate (newboard boardstart) 3)
  (print "\n------------\n"))
  (printstate (newboard (newboard boardstart)) 3)