Githubhttp://github.com/ambuc/conway

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:


Ref = spawn(module, function, [arg1, arg2..])
Msg = {foo, bar}
Ref ! Msg

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.


-module(latch).
-compile(export_all).

% Starts a latch reporting to Ref, waiting for N pings.
init(Ref, N) -> spawn(?MODULE, loop, [Ref, N]).

% Ends a latch reporting to Ref.
loop(Ref, 0) -> Ref ! pong;

% Recieves a ping and returns a latch waiting for N-1 pings.
loop(Ref, X) ->
  receive ping -> loop(Ref, X-1)
  after   1000 -> erlang:error(latch_timeout)
  end.

Collector⌗

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


-module(collector).
-compile(export_all).

% Starts a collector reporting to Ref, waiting for N reports.
% Optionally bundled with Metadata of any type, as a secondary payload.
init(Ref, Meta, N) -> spawn(?MODULE, loop, [Ref, Meta, [], N]).

% Ends a collector reporting to Ref.
% Sends a payload like {data, Meta, Data}
loop(Ref, Meta, Data, 0) -> Ref ! {data, Meta, Data};

% Recieves a payload and returns a collector waiting for N-1 more payloads.
loop(Ref, Meta, Data, X) ->
  receive D    -> loop(Ref, Meta, [ D | Data ], X-1)
  after   1000 -> erlang:error(collector_timeout)
  end.

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.


% Starts a GOL with Frames (an integer) frames left to live.
% Its initial state is a list of 1s or 0s, and it has dimensions X by Y.
init(Initial_State, Frames, {X, Y}) ->

  io:format("Drawing ~w frames on an ~w x ~w grid...~n",[Frames, X, Y]),
  out:cleanOutputFolder(),
  Size = X * Y,
  Is   = lists:seq(1,Size),
  io:format("Initializing ~w cells...~n",[Size]),
  Cs   = [ cell:init(I,L) || {I,L} <- lists:zip(Is,Initial_State) ],
  S    = #state{frames=Frames, stage=report, size=Size, cells=Cs, x=X, y=Y},
  % Once we have created the cells, we need to broadcast out a list of their
  % neighbor's PIDs to them.
  io:format("Linking      ~w cells...~n",[Size]),
  [ C ! {moore, neighbors:getNPids(I,X,Y,Cs)} || {I,C} <- lists:zip(Is,Cs) ],
  io:format("Linked       ~w cells...~n",[Size]),
  action(S).

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


action(#state{frames=0}) ->
    io:format("Writing out to /tmp/conway/gif.gif.~n")
  , os:cmd("convert -delay 20 -loop 0 $(ls /tmp/conway/frame_* | tac ) /tmp/conway/gif.gif")
  , io:format("Wrote   out to /tmp/conway/gif.gif.~n")
  ;

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


action(S) ->
  case S#state.stage of
    % If we need to collect the states of all the cells, we create a Collector
    % which knows to report back to the Board when it's done. We tell the
    % Collector it needs to collect X*Y data points.
    %
    % Then we broadcast out {CollectorPid, report} to each of the cells, to tell
    % them to self-report their {index, life} to the Collector.
    %
    % Then we switch over to waiting for the Collector to ping us back.
    report   -> C_Ref = collector:init(self(), nil, S#state.size),
                [ C ! {C_Ref, report  } || C <- S#state.cells],
                waiting(S);
    % Similarly, if we need to tell all the cells to check their neighbors, we
    % create a Latch which knows to report back to the Board when it's done. We
    % tell the Latch it needs to collect X*Y pings.
    %
    % Then we broadcast out {LatchPid, check_ns} to each of the cells, to tell
    % them to check their neighbors and ping the Latch when they're done.
    %
    % Then we switch over to waiting for the Latch to ping us back.
    check_ns -> L_Ref = latch:init(self(), S#state.size),
                [ C ! {L_Ref, check_ns} || C <- S#state.cells],
                waiting(S);
    % FInally, if we need to tell all the cells to alter their states, we create
    % a Latch and broadcast our message just as we did above.
    alter_st -> L_Ref = latch:init(self(), S#state.size),
                [ C ! {L_Ref, alter_st} || C <- S#state.cells],
                waiting(S);
    _        -> erlang:error(weird_stage)
  end.

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.


waiting(S = #state{stage=report}) ->
  receive {data, _, Data} -> out:writeData(S#state.frames, S#state.x, Data),
                             io:format("~w frames left.~n",[S#state.frames]),
                             action(S#state{ stage=check_ns
                                           , frames=(S#state.frames-1)
                                           })
  after 1000 -> erlang:error(board_timeout)
  end;

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.


waiting(S) ->
  receive pong ->
    case S#state.stage of check_ns -> action(S#state{stage=alter_st});
                          alter_st -> action(S#state{stage=report  })
    end
  after 1000 -> erlang:error(board_timeout)
  end.

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.


init(Index, Life) -> spawn(?MODULE, loop, [ #state{index=Index, life=Life} ]).

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.


% we are waiting to receive...
loop(S) ->
  receive
    % ... a moore neighbor space,
    {moore, NPids}   -> loop(S#state{npids=NPids});
    % ... a request to check their neighbors' states, decide their desired
    % state, and ping back to a latch L when done,
    {L, check_ns}    -> Ref = collector:init(self(),L,length(S#state.npids)),
                        [ NPid ! {Ref, alive} || NPid <- S#state.npids ],
                        loop(S);
    % ... a payload from the above collector, allowing them to decide their
    % desired state, and ping a latch on receipt,
    {data, L, NData} -> L ! ping,
                        loop(S#state{desire=getDesire(S#state.life,NData)});
    % ... a request from the board to ping a latch and flip to their new state,
    {L, alter_st}    -> L ! ping,
                        loop(S#state{life=(S#state.desire)});
    % ... a request to report their {index,life},
    {C, report}      -> C ! {S#state.index, S#state.life},
                        loop(S);
    % ... a request to report their life,
    {Ref, alive}     -> Ref ! S#state.life,
                        loop(S);
    % ... or a request to die.
    die              -> ok;
    _                -> erlang:error(weird_input)
  after 10000        -> erlang:error(cell_timeout)
  end.

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


% Takes a current state and data about the states of their neighbors, and
% decides whether to live or die.
getDesire(Curr, NData) ->
  decide(Curr, length(lists:filter(fun(X) -> X =:= 1 end, NData))).

% Encodes the GOL rules.
% - Any live cell with fewer than two live neighbours dies, as if caused by
%   underpopulation.
% - 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
%   overpopulation.
% - Any dead cell with exactly three live neighbours becomes a live cell, as if
%   by reproduction.
% Formally, this might be encoded as "B3/S23".
decide(0,3) -> 1;
decide(0,_) -> 0;
decide(1,2) -> 1;
decide(1,3) -> 1;
decide(1,_) -> 0.

Output⌗

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


[(0,0),(1,0),(2,1),(3,0)... (<index>,<life>)]

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:


size = 5
white = PixelRGBA8 255 255 255 255
black = PixelRGBA8   0   0   0 255

-- is called once per frame, like 
-- $ render.hs /tmp/conway/data0001 /tmp/conway/frame0001.png
main = do
  [inPath, outPath] <- getArgs
  grid <- fmap words $ readFile inPath
  let height = length $ grid
  let width  = length $ head $ grid
  let datum = id
          $ map snd
          $ filter ((=='1').fst)
          $ zip (concat $ grid)
                [(x,y) | y <- [0..height-1], x <- [0..width-1]]
  let img = renderDrawing (width*size) (height*size) white
          $ mapM_ (uncurry pixelAt) datum
  writePng outPath img

pixelAt :: Int -> Int -> Drawing PixelRGBA8 ()
pixelAt x y = withTexture (uniformTexture $ PixelRGBA8 0 0 0 255)
            $ fill
            $ rectangle (V2 (fromIntegral $ x*size) (fromIntegral $ y*size))
                        (fromIntegral size)
                        (fromIntegral size)

Tying it all together⌗

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


-module(conway).

%% API exports
-export([main/1]).

% Modify this file to generate your own.
main([Pattern]) ->
  case Pattern of
    "random"  -> board:init( fog:getFog(100,100), 100, {100,100} );
    "blinker" -> board:init( [0,0,0,0,0
                             ,0,0,1,0,0
                             ,0,0,1,0,0
                             ,0,0,1,0,0
                             ,0,0,0,0,0], 2, {5,5});
    %            board:init(<initial_state>, <runtime>, {<width>,<height>})
    ...
  end.

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)⌗