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:
- 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 overcrowding.
- 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.
All the simulation functions will be contained in a Scala
LifeSym; this is the definition of our basic data types:
What this means is that
Cell will be a type alias for a pair of
Board will be a
Cell. We also need some convenience functions to create and access our data structures as follows:
board function accepts a variable number of
Cell parameters, which makes the creation of a board nicely resemble a DSL:
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:
??? is a special value defined in the standard Scala library; it is defined as follows:
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:
Scala actually translates it to:
If we used only one set of parenthesis as in:
This would be translated to:
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:
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:
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:
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
it nesting is provided by the
FunSpec class while
empty are provided by the powerful
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
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 is defined for many container types (e.g. collections, Option, Future) and for a fictional
Container type is defined as follows:
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
U are equal to
Cell and the container type is
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:
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:
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
Now, for the final missing function, let’s write a test that checks that a well-known shape, an oscillator, is correctly evolved:
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:
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:
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:
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:
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:
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.