Posted on Mon Mar 29 00:00:00 -0400 2010

A good friend of mine, Michael Hunger, is planning on describing a number of differing implementations of Conway’s Game of Life in an upcoming keynote. In pursuit of this, he recently emailed me requesting an ‘idiomatic’ version in the exciting yet really rather experimental programming language Ioke.

This left me with an interesting question floating in my mind: “What on earth is idiomatic Ioke?”. In fact, how can the notion idiomatic even exist in any fledgling medium?

However, I was undeterred and resolved on attempting to try my best to build something that at least I was happy with. After much writing and re-writing, polishing and folding I finally settled on the the notation I’ll explain in this post. Please note, you’ll need the latest edge build of Ioke to interpret it.

As a quick sidenote, if you haven’t previously looked at the GoL, I encourage you to take a quick peak at the Wikipedia entry before you continue with this article - it’s fun and interesting stuff. Rather than rewriting the description here’s an excerpt from the article itself:

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which
is in one of two possible states, live or dead. Every cell interacts with its eight neighbors, which are the
cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following
transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives on to the next generation.
4. Any dead cell with exactly three live neighbours becomes a live cell.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above
rules simultaneously to every cell in the seed — births and deaths happen simultaneously, and the discrete
moment at which this happens is sometimes called a tick (in other words, each generation is a pure function
of the one before). The rules continue to be applied repeatedly to create further generations.

I tackled the problem by considering the perspectives of the interface and implementation. For the interface I created a runner script, and for the implementation I created a GameOfLife object.

Game of Life Runner

A generic GoL runner might consist of the following three phases:

• Firstly, the initialisation of a life environment - this requires a grid size to be specified in terms of the number of rows and columns,
• Secondly for certain cells in the environment’s grid to be manually spawned - this is the seed of the pattern,
• Finally for a number of evolutions to be initiated with the possibility of displaying the state of the current evolution.

For this I created the following runner script:

#!/usr/bin/env ioke
;gol_runner.ik
use("gol")

;read in from the program arguments the number of evolutions to initiate
numTimes = System programArguments first toRational

;Phase 1: create the environment
life = GameOfLife mimic(rows: 5, columns: 6)

;Phase 2: Manually Spawn cells
[[1,0], [1,1], [1,2], [1,3], [1,4], [1,5]] each(coords,
  life grid spawnCell(*coords))

;Phase 3: Evolve the environment the requested number of times
;the current state which counts as the first evolution
life grid asText println

;initiate the following n-1 evolutions
(numTimes - 1) times(life evolve asText println)

Note that I’m also reading in the number of iterations to initiate from the program arguments. It might seem strange that I’m calling the method toRational on the first argument (which comes in as text), however this is currently the only way of converting text to an integer in Ioke at the moment. Ola has said that this is something he’s looking into improving.

Running the Runner

Now, if we assume the presence of a functioning GoL implementation within “gol.ik”, We can run this and see life evolving before our very eyes:

∴ /Users/sam/Development/gol
λ ./gol_runner.ik 8

+-------------+
|             |
| * * * * * * |
|             |
|             |
|             |
+-------------+

+-------------+
|   * * * *   |
|   * * * *   |
|   * * * *   |
|             |
|             |
+-------------+

+-------------+
|   *     *   |
| *         * |
|   *     *   |
|     * *     |
|             |
+-------------+

+-------------+
|             |
| * *     * * |
|   * * * *   |
|     * *     |
|             |
+-------------+

+-------------+
|             |
| * *     * * |
| *         * |
|   *     *   |
|             |
+-------------+

+-------------+
|             |
| * *     * * |
| *         * |
|             |
|             |
+-------------+

+-------------+
|             |
| * *     * * |
| * *     * * |
|             |
|             |
+-------------+

+-------------+
|             |
| * *     * * |
| * *     * * |
|             |
|             |
+-------------+

How lovely. I do hope that you appreciate ASCII-art as much as me! OK, so now for the actual implementation. For this I decomposed GoL into the following three objects: GameOfLife, Grid and CellData.

CellData

This is a very basic object which is essentially a nice package of useful cell information such as its liveliness, coordinates and number of live neighbours. Think of it as a basic struct of information. This object is generated by the Grid and used for the evolution process within the GameOfLife object.

GameOfLife

This is the environment, the containing object that is used by the runner. It describes the three phases described above, initialisation, spawning and evolving, each realised by a corresponding method. The source for this, which I will deconstruct below, is as follows:

GameOfLife = Origin mimic do(
  initialize = method(rows:, columns:,
    @grid = Grid withDimensions(rows, columns))

  spawnCell = method(row, col,
    grid spawnCell(row, col))

  evolve = method(
    nextGrid       = grid blankGrid
    survivingCells = grid filter(live?) filter(numLiveNeighbours in?(2..3))
    newCells       = grid reject(live?) filter(numLiveNeighbours == 3)

    (newCells + survivingCells) each(cellData,
      nextGrid spawnCell(cellData row, cellData col))

    @grid = nextGrid)
)

initialize

initialize = method(rows:, columns:,
  @grid = Grid withDimensions(rows, columns))

This is the standard Ioke initialisation hook method. This gets called when the containing object is mimiced (the only way in Ioke to create new objects). In this case we create a new Grid with the requested dimensions and assign it to a local cell called grid. Note that @grid is just shorthand for self grid.

spawnCell

spawnCell = method(row, col,
  grid spawnCell(row, col))

Here we essentially palm-off the logic to the grid object (explained below). I hope that one day Ioke will get the ability to delegate methods in a much more elegant fashion.

evolve

REXML could not parse this XML/HTML: 
<div>
  <pre><code class='ioke'>evolve = method(
  nextGrid       = grid blankGrid
  survivingCells = grid filter(live?) filter(numLiveNeighbours in?(2..3))
  newCells       = grid reject(live?) filter(numLiveNeighbours == 3)

(newCells + survivingCells) each(cellData, nextGrid spawnCell(cellData row, cellData col))

@grid = nextGrid)</code></pre> </div>

Here we essentially have all the logic for Conway’s Game of Life expressed in a very small number of succinct lines. We also get to see some of Ioke’s lovely sequence facilities in action.

Firstly, we create a new grid which is essentially the current grid, but with all the cells reset to the default state (empty). This is the grid we will populate for the next evolution; consider it a blank slate. Next we collect the set of cells which should survive from the current generation and also which cells will be spawned as a resultant of the correct number of live neighbour cells. As described above, the GoL rules state that a cell is spawned if it has exactly 3 live neighbours. Here we can see that Ioke makes expressing this remarkably elegant and readable:

newCells = grid reject(live?) filter(numLiveNeighbours == 3)

Here we take all the cells in the grid and reject the ones which are live (i.e. have live? set to a non-true value), we then filter again based on which cells have 3 live neighbours. How beautiful is that!

Finally, we combine the newly spawned cells and the surviving sells and we spawn a corresonding cell in the next grid which we then use to replace the current grid. Job done.

Grid

This is the grid of cells. Rather than using the standard initialize method hook I decided to write my own constructor-style method which has a slightly more intention-revealing name: withDimensions. This is implemented as follows:

withDimensions = method(rows, columns,
    with(
      state: Dict withDefault(0),
      numCols: columns,
      maxRowIdx: rows - 1,
      maxColIdx: columns - 1))

Here we initiate the new Grid object with some default cells representing dimensional information for the grid and also the state of the grid. This state is stored in a Dict which is a dictionary, or a hash in other languages. The state stores a value for each coordinate of the grid, where the value is either 0 for an empty cell and 1 for a live cell. The default for this dictionary is 0. The spawnCell method essentially sets this bit to 1 to indicate that the given cell is alive. The main reason for using the integers 0 and 1 to represent the liveliness of the cells is that they lend themselves very well for counting. This property is taken advantage of in countLiveNeighbouts:

countLiveNeighbours = method("Counts the number of live neighbours for a given set of cell coordinates",
    row, col,
    neighbourCoords = permutations((-1..1), (-1..1)) - [(0,0)]
    neighbourCoords inject(0, sum, (r_mod,c_mod), state[[row + r_mod, col + c_mod]] + sum))

This method essentially iterates through all the possible neighbour coordinates relative to the current cell and sums the number of live cells. Here we get a good feel for how Ioke allows functional style programming in a slightly more elegant manner than Ruby. Also note that Ioke allows you to pass in a documentation string as the first parameter to any method. This documentation string essentially acts as both an inline source comment and also is available to the runtime which makes it accessible from the repl and also by documentation generation tools such as DokGen.

One of the nicer Ioke features is its Rubyesque mixins. In this source I use the Sequenced mixin to give the Grid object a sequence interface:

mimic!(Mixins Sequenced)

This gives it the nice filter method for free which is used in the evolve method described above. To achieve this I just need to mimic the Sequenced mixin and implement a seq method. In this case Grid’s seq method piggybacks on the seq method of the list of all cells returned by allCells which is is a list of CellData objects:

seq = method(allCells seq)

Finally, there are a couple of methods which are used to display the current state. The main method for this used by the runner is asText which generates a nice pretty ASCII representation of a given grid.

Complete Source

OK, I realise that I haven’t covered everything in detail, but hopefully I’ve described enough to give you a taste of Ioke and left enough for you to work through and discover yourself. One thing to note is that this is probably the slowest GoL implementation (that wasn’t specifically written to be slow) that you’ll ever see. It’s so slow it’s painful. However, performance isn’t the main purpose of objective of Ioke - it’s an experiment in expressiveness. Hopefully this example illustrates this for you.

As a parting gift, here is the complete source of my GoL implementation. I’d love it if any of you would like to send me some feedback regarding this approach. This is my first GoL implementation, so I’m positive I have much to learn.

GameOfLife = Origin mimic do(
  initialize = method(rows:, columns:,
    @grid = Grid withDimensions(rows, columns))

  spawnCell = method(row, col,
    grid spawnCell(row, col))

  evolve = method(
    nextGrid       = grid blankGrid
    survivingCells = grid filter(live?) filter(numLiveNeighbours in?(2..3))
    newCells       = grid reject(live?) filter(numLiveNeighbours == 3)

    (newCells + survivingCells) each(cellData,
      nextGrid spawnCell(cellData row, cellData col))

    @grid = nextGrid)
)

GameOfLife Grid = Origin mimic do(
  mimic!(Mixins Sequenced)

  CellData = Origin mimic do(
    row = method(coords first)
    col = method(coords second))

  withDimensions = method(rows, columns,
    with(
      state: Dict withDefault(0),
      numCols: columns,
      maxRowIdx: rows - 1,
      maxColIdx: columns - 1))

  blankGrid = method("Resets the grid", with(state: Dict withDefault(0)))
  spawnCell = method("Animates a given cell", row, col, state[[row, col]] = 1)

  ;internal methods
  seq = method(allCells seq)
  permutations = method(a, b, a flatMap(i, b map(j, (i,j))))

  countLiveNeighbours = method("Counts the number of live neighbours for a given set of cell coordinates",
    row, col,
    neighbourCoords = permutations((-1..1), (-1..1)) - [(0,0)]
    neighbourCoords inject(0, sum, (r_mod,c_mod), state[[row + r_mod, col + c_mod]] + sum))

  allCellCoords = method("Generates a list of tuples representing the coordinates of all the cells",
    permutations(0..maxRowIdx, 0..maxColIdx))

  allCells = method("Generates a list of all the cells in the Grid with associated metadata",
    allCellCoords map((row, col),
      CellData with(coords: (row, col),
                    numLiveNeighbours: countLiveNeighbours(row, col),
                    live?: state[[row, col]] == 1)))

  ;for output purposes
  asList = method("Returns the list of cells as a list of 0s and 1s, with 1 representing a live cell",
    rowsOfCoords = allCellCoords seq sliced(numCols)
    cellList = []
    while(rowsOfCoords next?, cellList << (rowsOfCoords next map((row, col), state[[row,col]]))))

  asText = method("Returns the list of cells in a pretty ascii art representation",
    gridContents = asList map(map(i, if(i == 0, "  ", "* ")) join)
    "\n+-#{"--" * (numCols)}+\n| #{gridContents join("|\n| ")}|\n+-#{"--" * (numCols)}+")
)