This week I inadvertently learned a new language and new programming paradigm along the way. My language of choice was a dialect of Scheme, Guile, but it lacked the basic library support I wanted, so I went with Racket; after a few scripts, I went ahead and programmed Conway’s Game of Life.
The first thing I had to learn was some of the basic tenets of declarative or functional programming, having come from an imperative background. Namely that there are (more or less) no side-effects. That is to say, variables are immutible and state isn’t global.
Recursion replaces many of the tools (such as looping over state) I’m used to having. Advice comes to mind, which Jame Katz here at RC said in a presentation: n > Recursion provides a data-structure for free, the call stack.
Conway’s Game of Life
John Horton Conway, a famous mathematician, devised a “game” which is really a cellular automaton; a zero-player game which plays out depending on the seed or initial state. The basis of the game is a grid in which each node is either alive or dead and depending on that state each step in Life changes the grid, the rules stated succinctly on Wikipedia are :
- Any live cell with fewer than two live neighbours dies, as if caused by under-population.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by over-population.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Some interesting patterns emerge, such as the pulsing Oscillators patterns:
or the moving Glider patterns:
or the stationary Still Life patterns:
Displaying a Grid
Aside from the hoops I had to jump through in order to learn the functional paradigm, the Game of Life lent itself rather well to Racket’s constraints. The basic idea being that there is a State of the World, with certain live and dead nodes, and then the rules are applied and a new state is generated.
I chose to represent the grid as a list of lists; the first lists are the rows within those are lists of columns. Lists are a special data-structure in Racket and allow for folding, which I’ll get to later. Constructing a list of lists, however, is not quite as pretty as a vector of vectors (vectors in Racket are like arrays in other languages, immutable lists with efficient accessing) which allow for a
(build-vector n proc) → vector? n : exact-nonnegative-integer? proc : (exact-nonnegative-integer? . -> . any/c)
This constructs the list with a processes n times. To get the best of both worlds (though perhaps it’d be better to simply define a fold for vectors or a build for lists instead) I constructed the list of lists, the grid, like this (which my blog doesn’t highlight very helpfully):
(define (make-state) "A Vector of Vectors for the grid in Lists" (vector->list (build-vector rows (lambda (m) ;; m is the y coord (vector->list (build-vector cols (lambda (n) ;; n is the x coord (node #f n m dead-block))))))))
This uses a struct
node with the
alive boolean, its coordinates, and an image (Racket includes the 2htdp library with basic shapes or images as primitive data structures.
(struct node (alive x y img) #:transparent #:mutable)
For a small grid, (where
4) renders as:
(list (list (node #f 0 0 '()) (node #f 1 0 '()) (node #f 2 0 '()) (node #f 3 0 '())) (list (node #f 0 1 '()) (node #f 1 1 '()) (node #f 2 1 '()) (node #f 3 1 '())) (list (node #f 0 2 '()) (node #f 1 2 '()) (node #f 2 2 '()) (node #f 3 2 '())) (list (node #f 0 3 '()) (node #f 1 3 '()) (node #f 2 3 '()) (node #f 3 3 '())))
The aforementioned 2htdp library takes care of the graphical representation of the list, all I needed to do was draw it. The
place-image function draws an image ontop of a background (which in my case was a blank box:
(place-image image x y scene) → image? image : image? x : real? y : real? scene : image?
I then wrapped this function and set the
node-img to according to its state:
(define (draw-node n bkg) "Draw a node and set image according to status" (cond [(node-alive n) (set-node-img! n alive-block)] [(not (node-alive n)) (set-node-img! n dead-block)] [else (set-node-img! n dead-block)]) (place-image (node-img n) (+ (* cell (node-x n)) margin) ;; Shinnanigans for using (x y) like a regular grid (- (- (* cell (node-y n)) (- (* cell cols) margin))) bkg))
Problem was, there is no
background variable which I change each drawing, rather drawing once outputs another image, over which I had to draw the next node as if the first output was the background. That is to say, I needed to recursively draw the nodes, and my first implementation was just that, I passed in a list of nodes and the blank background to
(define (draw-nodes node-lst bkg) "Recursively draw all nodes" (if (= (length node-lst) 1) ;; If this (draw-node ;; Then this (car node-lst) ;; car takes the first item of list bkg) (draw-nodes ;; Else this (recursive call) (drop node-lst 1) ;; drop returns a list without the items before an index (draw-node ;; A draw-node function as the background (car node-lst) bkg))))
Turns out what I’m doing here is alike to taking the sum of a list, I’m calculating the accumulator n amount of times. This is what
(foldl proc init lst ...+) → any/c proc : procedure? init : any/c lst : list?
So, using a list of lists, I can simplify the function above as follows:
(define (draw-col nodes background) "Draw a column from a list of nodes" (foldl draw-node background nodes)) (define (draw-nodes nodes) "Draws a List of List node grid" (foldl draw-col background nodes))
foldl, (folding from the left) takes a process (
draw) to apply to a list (
nodes) which output and takes as parameter the accumulator (
background). This is one of the many clever tools which are common place in a functional paradigm but absent elsewhere.
And it’s pretty
So here’s a gif, mistakenly backwards, of an example Game of Life with this program: