18 March 2014

In this series of articles I want to talk about how to build the popular Conway’s game of life in Scala with a functional and test-driven approach. We did this with the London Scala User Group during an Hack The Tower event and it was a really fun way to get people involved in Scala and to see some TDD in action.

The game of life is an example of cellular automata in which an imaginary universe is represented by a board divided in cells that can be alive or dead; at each generation of the simulation the board evolves to a new status; some cells dye, other cells live on and other get born following four simple rules:

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

It’s amazing how, given an initial state with some living cells, these four simple rules can give birth to a variety of more or less chaotic behaviours. To start with this we are going to imagine that we have an infinite board and on this board we keep track only of living cells. We will avoid using classes and other OO-like constructs and we’ll focus on functions and data types.

Data types

All the simulation functions will be contained in a Scala object named LifeSym; this is the definition of our basic data types:

object LifeSym {
  type Cell = (Int, Int)
  type Board = Set[Cell]
  // ...
}

What this means is that Cell will be a type alias for a pair of Int and Board will be a Set of Cell. We also need some convenience functions to create and access our data structures as follows:

object LifeSym {
  // ...
  def cell(x: Int, y: Int): Cell = (x, y)
  def board(cs: Cell*): Board = cs.toSet
  def x(c: Cell) = c._1
  def y(c: Cell) = c._2
  // ...
}

The board function accepts a variable number of Cell parameters, which makes the creation of a board nicely resemble a DSL:

val b = board(cell(1, 2), cell(1, 3), cell(1, 4))

Drafting a solution

The rules of the game depend very much on the neighbourhood of a cell, so there should be a function that tells us given a cell what are its living neighbours and if two cells are neighbours; to determine these two things is needed in turn a function to get the neighbouring coordinates of a cell, i.e. the points that have 1 of distance between any x and/or y. Once we have this building blocks we can write a function that creates the next generation for a given board and the function that calculates the evolution of a board over multiple steps. The signatures of this functions could be as follows:

object LifeSym {
  // ...
  val neighbourOffsets: Set[(Int, Int)] = (for {
    x <- -1 to 1
    y <- -1 to 1
  } yield (x, y)).toSet - ((0, 0))

  def neighbourCoordinates(c: Cell): Set[Cell] = ???
  def areNeighbours(c1: Cell, c2: Cell): Boolean = ???
  def livingNeighbours(b: Board, c: Cell): Set[Cell] = ???
  def nextGeneration(b: Board): Board = ???
  def sym(b: Board, steps: Int): List[Board] = ???
}

Missing implementations

The ??? is a special value defined in the standard Scala library; it is defined as follows:

def ???: Nothing = throw new NotImplementedError

This is a place-holder commonly used when stubbing out ideas. Its type is Nothing that in Scala is the type that is descendant of any other type (as Any is the ancestor of any other type) so it will type-check in almost any situation, it doesn’t have any instance and is the type returned by throwing an exception. Hitting a ??? at runtime will result in an error saying that an implementation is missing.

Neighbour offsets generation

The only implemented property in the above functions is neighbourOffsets, which is a Set containing all the pairs having x and y within the [[-1, 1]] range except when they are both equal to 0; it is constructed using for comprehension and removing the (0, 0) pair from the generated set. The need for double parenthesis may not be clear for people new to Scala so it probably deserves a bit of explanation: what happens is that in Scala all the operators are actually methods defined as a normal method would be defined; syntactic sugar makes it possible to use them (as well as normal methods) without the . and without parenthesis.

This means is that when you write somewhere:

val x = 2 + 2

Scala actually translates it to:

val x = 2.+(2)

If we used only one set of parenthesis as in:

val mySet: Set[(Int, Int)] = ...
mySet - (0, 0)

This would be translated to:

val mySet: Set[(Int, Int)] = ...
mySet.-(0, 0)

The parenthesis would be assumed to belong to the method invocation and not to a tuple constructor and the compiler would complain that it doesn’t know how to apply the - function of Set[(Int, Int)] to two integer parameters as it expects a single pair of integers instead. With two set of parenthesis instead the compiler can correctly translate the invocation as follows:

val mySet: Set[(Int, Int)] = ...
mySet.-((0, 0))

Which type checks fine and is what we actually meant.

Going TDD - The utility functions

We drafted our functions, it’s time to write some tests for how we expect them to work. Doing this we will be able to quickly implement and validate them as well as be sure that the functionality remain the same if later we (or someone else) will decide to change something and the tests will also work as a basic runnable documentation for the API. We are going to use ScalaTest version 2.0, to get started we’ll have to define the test class as follows:

import org.scalatest._

class LifeSymTest extends FunSpec with Matchers {

  import LifeSym._

  // ...
}

ScalaTest is a test framework that supports many styles, from unit testing to more BDD-like approach. In this case I’m going to use an approach that is in between Unit testing and BDD, so I extend the FunSpec class and mix in the Matchers trait to use the nice DSL that it provides for defining expectations. Let’s start writing our tests for the first three functions into the test suite defined above:

describe("LifeSym") {
  it("should correctly identify neighbouring coordinates") {
    neighbourCoordinates(cell(1, 1)) should equal(
      Set(cell(0, 0), cell(0, 1), cell(0, 2), cell(1, 0),
        cell(1, 2), cell(2, 0), cell(2, 1), cell(2, 2)))
  }

  it("should correctly tell if two cells are neighbours or not") {
    areNeighbours(cell(2, 3), cell(4, 5)) should be (false)
    neighbourCoordinates(cell(4, 5)) foreach {
      c => areNeighbours(c, cell(4, 5)) should be (true)
    }
  }

  it("should produce a list of living neighbours of a cell") {
    val simpleBoard = board(cell(2, 3), cell(4, 5), cell(5, 6))
    livingNeighbours(simpleBoard, cell(2, 3)) should be (empty)
    livingNeighbours(simpleBoard, cell(4, 5)) should equal(Set(cell(5, 6)))
    livingNeighbours(simpleBoard, cell(5, 6)) should equal(Set(cell(4, 5)))
  }
  // ...
}

Looking at this code it is possible to appreciate how the Scala language puts some emphasis on being able to write nice domain specific languages within itself by using the richness of its syntax and abstractions. The describe and it nesting is provided by the FunSpec class while should, be, equal and empty are provided by the powerful Matchers trait.

In a real-world scenario you may probably want to write more test cases for each functions, but what we have here cover the basics of what these functions should provide us. To run the test fire an sbt shell and give the test command as follows:

> test
[info] LifeSymTest:
[info] LifeSym
[info] - should correctly identify neighbouring coordinates *** FAILED ***
[info]   scala.NotImplementedError: an implementation is missing
[info] - should correctly tell if two cells are neighbours or not *** FAILED ***
[info]   scala.NotImplementedError: an implementation is missing
[info] - should produce a list of living neighbours of a cell *** FAILED ***
[info]   scala.NotImplementedError: an implementation is missing
[info] ScalaTest
[info] Run completed in 1 second, 585 milliseconds.
[info] Total number of tests run: 3
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 0, failed 3, canceled 0, ignored 0, pending 0
[info] *** 3 TESTS FAILED ***
[error] Failed: Total 3, Failed 3, Errors 0, Passed 0
[error] Failed tests:
[error]   org.lsug.restlife.test.LifeSymTest
[error] (test:test) sbt.TestsFailedException: Tests unsuccessful
[error] Total time: 2 s, completed 23-Feb-2014 18:05:13

The actual output will contain also stack traces, I removed them as they are not really important at the moment. What the output tells us is which tests failed and a bit of useful information. We will now implement the functions and try to get our tests passing. It is a fun and useful exercise to get the bar green when playing with a pet project as we are doing now; in the real world, in a big software that needs to be maintained for a long time by many people, this approach has also many other advantages:

  • It is way quicker to run a suite of tests rather than checking things manually
  • The tests will be run in CI, ideally before merging topic branches, thus catching breaking changes before they make it into a release.
  • Tests will help refactoring parts of the system when they become old as even not knowing all the details you can validate your work quickly by running them.
  • If written in a good way tests will work as a living documentation of the code base.

Implementing the functions

The neighbourCoordinates function should get the neighbouring offsets that we defined above and apply each of them to the given cell to produce a new set of coordinates. In Scala, when we want to produce a new collection starting from one we have and applying some transformation we are most likely looking at a use case for the map function:

def neighbourCoordinates(c: Cell): Set[Cell] = neighbourOffsets.map { case (ofX, ofY) => cell(x(c) + ofX, y(c) + ofY) }

The map function is defined for many container types (e.g. collections, Option, Future) and for a fictional Container type is defined as follows:

trait Container[T] {
  def map[U](f: T => U): Container[U]
}

The Scala collection map actually has a slightly more complex signature, but for most practical purposes this is the one you should think about. The function applies a provided function from T (the type inside the container) to a type U and returns a new container of U. In our case both T and U are equal to Cell and the container type is Set. The case statement used as the parameters part of a closure is a way to de-construct the pair of offset coordinates into its two components. The function body creates a new cell whose coordinates are taken from the given cell plus the given offsets. In Java or any imperative language this could’ve been written as:

public Set<Cell> neighbourCoordinates(Cell cell) {
  Set<Cell> newSet = new Set<Cell>();

  for (Cell c : neighbourOffsets) {
    newSet.add(new Cell(cell.getX() + c.getX(), cell.getY() + c.getY()));
  }

  return newSet;
}

Lots of ceremonies for a very simple task. Higher order functions as map are one of the most powerful tools in the toolbox of a functional developer. Let’s give a run to tests to see if we did everything right:

> test
[info] LifeSymTest:
[info] LifeSym
[info] - should correctly identify neighbouring coordinates
[info] - should correctly tell if two cells are neighbours or not *** FAILED ***
[info]   scala.NotImplementedError: an implementation is missing
[info]   at scala.Predef$.$qmark$qmark$qmark(Predef.scala:252)
[info] - should produce a list of living neighbours of a cell *** FAILED ***
[info]   scala.NotImplementedError: an implementation is missing
[info] ScalaTest
[info] Run completed in 1 second, 462 milliseconds.
[info] Total number of tests run: 3
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 1, failed 2, canceled 0, ignored 0, pending 0
[info] *** 2 TESTS FAILED ***
[error] Failed: Total 3, Failed 2, Errors 0, Passed 1
[error] Failed tests:
[error]   org.lsug.restlife.test.LifeSymTest
[error] (test:test) sbt.TestsFailedException: Tests unsuccessful
[error] Total time: 2 s, completed 23-Feb-2014 18:37:03

The test we designed for the first function is passing! We can then implement the other functions as follows:

def areNeighbours(c1: Cell, c2: Cell): Boolean = neighbourCoordinates(c1).contains(c2)

def livingNeighbours(b: Board, c: Cell): Set[Cell] = b.filter(other => areNeighbours(c, other))

So areNeighbours is using the neighbouring coordinates set of the first given cell to check if it contains the second cell; livingNeighbours is instead using the areNeighbours function to filter the board and retain only the cells that are neighbours of the provided one. The filter function is as map a powerful tool that allow to express in a very concise way things that in an imperative language would take explicitly iterating over a loop in a rather verbose way.

Running our tests now this is the output:

> test
[info] LifeSymTest:
[info] LifeSym
[info] - should correctly identify neighbouring coordinates
[info] - should correctly tell if two cells are neighbours or not
[info] - should produce a list of living neighbours of a cell
[info] ScalaTest
[info] Run completed in 1 second, 276 milliseconds.
[info] Total number of tests run: 3
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 3, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[info] Passed: Total 3, Failed 0, Errors 0, Passed 3
[success] Total time: 1 s, completed 23-Feb-2014 18:42:24

Going TDD - The generation functions

Everything works as expected, our tests are passing, we can now re-iterate to build the functions that will actually do the simulation on top of our results. Let’s continue on this path and let’s add the tests for the remaining two functions; let’s start by writing the expectations of each of the four rules of the game of life and to apply them to the nextGeneration function:

it("should kill cells having less than two neighbours") {
  // All isolated cells
  nextGeneration(board(cell(1, 0), cell(3, 5), cell(9, 10))) should be (empty)
  // One neighbours cells
  nextGeneration(board(cell(0, 0), cell(0, 1))) should be (empty)
}

it("should allow cells with two or three neighbours to survive") {
  // (0, 1) has 2 neighbours
  nextGeneration(board(cell(0, 0), cell(0, 1), cell(0, 2))) should contain((0, 1))
  // (1, 1) has 3 neighbours
  nextGeneration(board(cell(0, 0), cell(1, 1), cell(2, 2), cell(0, 2))) should contain((1, 1))
}

it("should kill cells that have more than three neighbours") {
  val c = cell(1, 1)
  val neighbours = LifeSym.neighbourCoordinates(c)

  val boards = for {
    i <- 4 until 9
  } yield {
    neighbours.take(i)
  }

  boards.foreach { b => nextGeneration(b) should not contain(c)}
}

it("should create new cells at positions with 3 alive neighbours") {
  // A board with three cells in a corner shape
  val b = board(cell(0, 0), cell(1, 1), cell(1, 0))
  val evolution = nextGeneration(b)

  evolution.size should equal(4)
  evolution should equal(b + cell(0, 1))
}

Now, for the final missing function, let’s write a test that checks that a well-known shape, an oscillator, is correctly evolved:

it("should correctly evolve a 3-cells vertical oscillator") {
  val b = board(cell(3, 2), cell(3, 3), cell(3, 4))
  val bs = sym(b, 4)

  bs should equal {
    board(cell(2, 3), cell(3, 3), cell(4, 3)) ::
    board(cell(3, 2), cell(3, 3), cell(3, 4)) ::
    board(cell(2, 3), cell(3, 3), cell(4, 3)) ::
    board(cell(3, 2), cell(3, 3), cell(3, 4)) :: Nil
  }
}

The pattern we are testing for is formed by three contiguous cells in a vertical line; this is expected to evolve by switching to horizontal and to vertical again. We are now only missing the implementations of the missing functions that can be done as follows:

def nextGeneration(b: Board): Board = {
  // Create a set that contains all the cells that should survive as they have 2 or 3 living neighbours
  val survivingCells = b.filter { c =>
    val neighboursCount = livingNeighbours(b, c).size
    neighboursCount == 2 || neighboursCount == 3
  }

  // Create a set that contains all the cells that should be created as they are near
  // three living cells
  val spawiningCells = b.flatMap(neighbourCoordinates).filter { c =>
    !b.contains(c) && livingNeighbours(b, c).size == 3
  }

  // The next generation is the union of the above sets
  survivingCells ++ spawiningCells
}

def sym(b: Board, steps: Int): List[Board] = {
  // Define a tail-recursive private function that runs the evolution a given number
  // of times and accumulate calculated states
  @tailrec
  def runBoard(b: Board, s: Int, states: List[Board] = Nil): List[Board] =
    if (s == 0) states
    else runBoard(nextGeneration(b), s - 1, b :: states)

  // Use the defined function to calculate the states
  runBoard(b, steps)
}

The sym function is quite trivial, being just a convenience to invoke the nextGeneration function a given number of times accumulating the results found each time in a list of board states.

The next generation function uses again the power of higher order functions to calculate the cells that should be surviving or spawning between generations. The spawiningCells calculation uses another powerful and very common function defined for all collections and many container types; the presence of this function in Scala is also an hint that we are probably dealing with a monad, which is a concept that we won’t discuss in this article. The definition of the flatMap function for a container type could be represented as follows:

trait Container[T] {
  def flatMap[U](f: T => Container[U]): Container[U]
}

What this definition means is that flatMap will accept a function that from each element in our container creates a new container with some derived elements. All these containers will be then merged somehow to provide a single container of the target type as result. In our case we are using this function applying the neighbourCoordinates function as the argument, which from each cell in our board will provide a set that contains all the cells that are in its neighbourhood; when flatMap flattens the resulting sets all duplicates will be dropped as this is the semantic of a set. We then filter the resulting cells choosing only the non-living ones that have exactly three neighbours. Let’s run the test suite to check that everything works as expected:

> test
[info] LifeSymTest:
[info] LifeSym
[info] - should correctly identify neighbouring coordinates
[info] - should correctly tell if two cells are neighbours or not
[info] - should produce a list of living neighbours of a cell
[info] - should kill cells having less than two neighbours
[info] - should allow cells with two or three neighbours to survive
[info] - should kill cells that have more than three neighbours
[info] - should create new cells at positions with 3 alive neighbours
[info] - should correctly evolve a 3-cells vertical oscillator
[info] ScalaTest
[info] Run completed in 1 second, 806 milliseconds.
[info] Total number of tests run: 8
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 8, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[info] Passed: Total 8, Failed 0, Errors 0, Passed 8
[success] Total time: 2 s, completed 24-Feb-2014 23:15:59

All tests pass and through our TDD approach we can see that everything works as expected in a small unit without having to build an UI or having to run manually any piece of code. We have guarantees that given a board it will evolve accordingly to our expectations; if we discover later that missed anything and/or that there is a bug hidden somewhere, we will recreate it in our tests and use them as a validation step and a regression detector for our fix.

Making an UI with ScalaFX

We will now briefly see how to introduce ScalaFX and write a quick & dirty UI to show the simulation. It would be possible to simply use the JavaFX framework, but the ScalaFX library wraps around it to provide a more convenient Scala-like API. To introduce it we will need to do some changes to the build file:

import sbt._
import Keys._

object AutomataBuild extends Build {
  lazy val scalaFx = "org.scalafx" % "scalafx_2.10" % "1.0.0-M7"
  lazy val scalaTest = "org.scalatest" % "scalatest_2.10" % "2.0" % "test"

  // ScalaFX
  lazy val scalaFxSettings = Seq(
    unmanagedJars in Compile += Attributed.blank(
      file(System.getenv("JAVA_HOME") + "/jre/lib/jfxrt.jar")),
    fork in run := true
  )

  lazy val lsgu_automata = Project(id = "lsgu-automata", base = file("./"),
    settings = Project.defaultSettings ++ scalaFxSettings ++ Seq(
      libraryDependencies ++= Seq(
        scalaTest,
        scalaFx
      )))
}

There is a bit more of ceremony introduced due to the fact that JavaFX is part of the standard JRE distribution and it doesn’t have any hosted artifact to depend on. This means that from now on to compile and run this application we will need to have the environment variable JAVA_HOME set to the JRE path. On my Fedora installation this boils down to executing this shell command before running sbt:

$ export JAVA_HOME=/usr/java/latest/

Once this is done we can write the following code to display a board that can interact with mouse events and a button to start/stop the simulation:

// Some imports...

object LifeApp extends JFXApp {
  // Whether or not we are running a simulation at the moment
  val running = new SimpleBooleanProperty()
  // Last time a new frame has been rendered
  var lastTime = 0L

  // The timer object that will be used to update the board during the simulation
  val timer = AnimationTimer { now: Long =>
    // Push a new frame every 200 ms
    if (now - lastTime >= 200000000) {
      setBoard(LifeSym.nextGeneration(board))
      lastTime = now
    }
  }

  // A button to allow starting/stopping the simulation
  val startStopButton = new Button("Start") {
    // Conditional binding of ScalaFX properties
    text <== when(running) choose "Stop" otherwise "Start"
    // Handler for the button press event
    onAction = (p1: ActionEvent) => {
      running() = !running()
      if (running()) {
        timer.start()
      } else {
        timer.stop()
      }
    }
  }

  // Class that represents a cell in the UI at the given board coordinates
  class Cell(val rx: Int, val ry: Int) extends Rectangle {
    // Whether or not the cell is alive
    val alive = new SimpleBooleanProperty()

    // A setter for the alive property
    def alive_=(v: Boolean) { alive() = v }

    // If the simulation is not running switch the status of the cell on click
    onMouseClicked = (p1: MouseEvent) => if (!running()) { alive() = !alive() }

    // Positioning and sizing properties
    x = rx * 10
    y = ry * 10
    width = 8
    height = 8

    // Nice rounded corners
    arcWidth = 2
    arcHeight = 2

    // Conditional property binding for the cell background colour
    fill <== when (hover && running.not()) choose Color.gray(0.6) otherwise (when (alive) choose Color.gray(0.9) otherwise Color.gray(0.1))
  }

  // Create a new cell instance with the given board coordinates and the given status
  def cell(rx: Int, ry: Int, a: Boolean = false) = new Cell(rx, ry) {
    alive() = a
  }

  // Initialise a 100x70 UI-board of dead cells
  val cells = for {
    rx <- 0 to 100
    ry <- 0 to 70
  } yield cell(rx, ry, false)

  // Creates a logical board from the current UI-board state
  def board: Board = cells.filter(_.alive()).map(c => LifeSym.cell(c.rx, c.ry)).toSet

  // Updates the UI-board cells' status with the given logical board
  def setBoard(b: Board): Unit = {
    cells.foreach(c => c.alive() = b.contains(LifeSym.cell(c.rx, c.ry)))
  }

  // Initialise the UI
  stage = new PrimaryStage {
    scene = new Scene {
      root = new BorderPane {
        fill = Color.gray(0)
        center = new AnchorPane {
          content = cells
        }
        bottom = new BorderPane {
          padding = Insets(5)
          center = startStopButton
        }
      }
    }
  }
}

The code is commented and I’m not going to explain everything as this article would grow too much if I go delving into the details of ScalaFX. Moreover this was the first time I used it as well and I wouldn’t probably be accurate. To run the application, given that you have set your JAVA_HOME directory in a correct way, you just execute from the sbt session the command:

run

Have fun!

Conclusions

This closes this small journey in the land of Scala and TDD. You can find the full annotated source code in this repository.

There is much more to say, we barely scratched the surface of TDD and of the various libraries we used. As an example I’d really like to be gather a better understanding of ScalaFX and to find a good way to write tests for the UI code; maybe I will do something about it and I will dig a bit deeper in another article.



blog comments powered by Disqus