Home Blog Resume

##### Multiprocessing Conway's Game of Life in Erlang
2017-10-12

This is an implementation of Conway’s Game of Life written in Erlang, a general-purpose, concurrent, functional programming language. A lot of this essay will be an attempt to document not just the novel syntax but the different problem-solving and architecting ideas that go into developing in Erlang.

# The Game

Conway’s Game of Life is a cellular automaton, which means it’s a set of cells which turn themselves on and off frame-by-frame according to some set of rules. Specifically, Conway’s GOL takes place on an infinite 2D grid of squares, each of which cares about its eight cardinal neighbors. The entire game consists of

• a) a starting configuration, and
• b) a set of rules by which to evaluate if a cell lives or dies. In this case, Conway relies on rules which can be written as B3/S23, which means a cell is born if it has three living neighbors, and survives if it has either two or three living neighbors. (There are lots of variants.)

Conway’s GOL has become famous for the shockling high complexity and variety of its emergent patterns, as you can see in the 100x100 randomly-seeded grid above.

# Computing The Game

In practice, the complexity of computing Conway’s Game of Life depends on the size of the grid in question and the length of the simulation. It would be fairly easy to render the world as a matrix of binary 1s and 0s, or Trues and Falses; each tick in the world could be a matrix and each next tick could read off the states of the previous tick.

But I think the problem generalizes nicely to Erlang in the sense that it fits the Actor model, in which each cell might be its own process living on some VM, and each update / neighbor-check might be a message or series of messages passed between the elements of the grid.

# Erlang

Erlang is a little esoteric but not much more so than Haskell or any functional language. The basics for us go something like this:

spawn spawns a process, the function function from module module with args [arg1, arg2...]; Ref captures the PID of that process, and ! lets us pass messages to a unique instance of a process. This is the whole mechanism for Erlang; the VM aggressively cleans up processes which are done processing things (or waiting to process things).

# Semaphores

Before we get into the specifics of simulating Conway’s Game of Life, let’s discuss two small abstractions which make message passing between objects slightly easier.

## Latch

One is a latch, which is basically a counter; you give it a spring-loaded message, and it only sends that message once it’s reached a certain number of recieved messages.

## Collector

The other is a collector, which waits for a certain number of bits of information, and then sends them all in aggregate somewhere.

I defined the collector here with the ability to carry some bit of metadata over its lifetime, from initialization to final payload. This becomes useful in preserving the relative statelessness of each of our cells.

# Writing A Game Of Life

Now that we have a sense of how the game works and language and tools in which to write it, let’s try and design how the board and cell objects look and interact.

## The board

We want to initialize the board with dimensions, a starting pattern, and a lifespan for which to run. It should create, control, and eventually destroy the cells. It should also collate the current state of each board and output that state in some useful way.

Each tick of the board should consist of three stages:

• the board should ask each cell to report its current state, and then the board should output that aggregate state.
• then the board should ask each cell to check_ns check its neighbors and decide which state it would like to assume next. Once the cells are done, they should report back, so that the board knows it’s alright to move on to the next phase,
• when the board asks each cell to alter_st alter its state. Once the cells are done, they should report back…

so that the board knows it’s alright to loop these three stages over and over until the lifespan of the game is run out.

We have a base case: when a board has no frames left to run, it dies.

And some not-base cases. Sometimes a board has an action it needs to take.

When our board is waiting for a report, it expects a payload like {data, Meta, Data}. It collects the Data, uses it to draw the gameboard at that frame, and then calls action() at the next stage, check_ns, and with one fewer frame left to go.

When our board is waiting for anything else, it expects a simple pong. Depending on the current stage, it will know to switch over to the next stage in the cycle.

## The cells

Each cell of the board should know its own index and current state. When asked, they should be able to report one or both of those bits of information. Additionally, they should know the PIDs of their neighbors so that, if asked, they can query those neighbors (through a Collector) to discover their states and determine its next state.

This neighbor determination actually occurs in the board.erl initialization process, and the neighbor determination algorithm is abstracted away into neighbors.erl.

We have an initialization function init, which starts a cell with knowledge of its own index and starting state.

A cell always is waiting to receive a signal. When the game is over, the main/1 function in conway.erl ends and all these other processes die automatically.

The actual math of Conway’s GOL can be written quite simply:

# Output

The board object collects a sorted list of all nodes and states, like

We need a way to translate that into a still frame (a .png) of the gif we want to write eventually. Sadly, this task is best abstracted into a language with better graphics rendering capabilities. We write out this data into plaintext files and then run renderFrame/render.hs, which looks in /tmp for the file in question and writes it in-place to a .png.

The render script (render.hs) is really just a wrapper around Graphics.Rasterific:

# Tying it all together

We just need one central conway.erl which exports main/1, which lets us call this from the command line.

I wrote a teeny fog.erl module which wraps the builtin random number generator, which is how we achieve the main gif at the top of the page, where the starting state is a random haze of pixels. For the other patterns, we manually define the starting pattern with a list (not array) of ones and zeros.

# Performance

It took about 30s to render the 100x100 grid above for 100 frames, which is not too bad. One optimization that could have helped would have been to decouple the time it takes to write out the frame from the main board tick loop by spawning a process and not waiting for it to complete before dying. There might be a resource constraint there where it’s not great to have more than, say, 10 copies of render.hs running at once; a mutex might be a useful resource for solving that issue in a concurrent way.

Additionally, it would have been very cool to learn how to write bitmaps in raw binary. Erlang isn’t so good at image rendering, but it’s quite good at interfacing with the machine at a lower level; writing out raw bitmaps with individual pixels colored in (or not) might have been an elegant solution here.

# Results

OK, here are some cool oscillators I stole from Wikipedia. You can call them by name as the first argument to the conway executable under Run. They are:

• blinker
• toad
• beacon
• pulsar
• pentadecathlon
• random (seen at the top of the page)

View the source code on GitHub.