days
-4
-4
hours
-2
-1
minutes
-3
-5
seconds
-2
-3
search
Scala Tutorial

Game of Life in Scala

HeikoSeeberger

In this tutorial managing director of WeigleWilczek, Heiko Seeberger shows us how to play the Game of Life in Scala.

There is always one question at the beginning of a tutorial: “What kind of example application should we build?” It should be appealing and, if possible come with a graphical user interface. However, making it too complex could end up breaking the mold. Furthermore we want to get along without any dependencies (except for test tools,) because we want to check out Scala itself and not drift into any frameworks like Lift or Akka.

So, we have chosen an idiomatic and simple implementation of the fantastic Game of Life. If you haven’t heard about this interesting biological simulation, you really should take a look. We will not focus on a highly performant or distributed solution, but rather attempt to present Scala to you as simply as possible. Join us in building this example step by step. You can take a look at the code provided on GitHub. Our sample project is open source and is published under the Eclipse Public License.

Using Git, you can take a look at the commit history to fully understand each step we take.

Development Environment

Another important question we have to answer: How should our development environment look? Java developers are used to the comfort offered by IDEs like Eclipse, IntelliJ IDEA or NetBeans and the release of Scala 2.8 has finally brought us a few good plugins for the “big” IDEs. Nevertheless, we will not require an IDE at this point! Developers tend to be picky about IDEs, which means that some might stop reading if we selected the “wrong” one. Moreover our example has very few lines of code, which is typical for Scala. Thus, we will get along with a plain text editor. But of course you may use any IDE to follow this example. Compiling? Testing? Running the application? For this matter we are bringing in a nice build tool called SBT (Simple Build Tool). If you know Ant or Maven, you will love SBT. If you’re new to SBT, you’ll quickly come to understand why it has “Simple” in its name. SBT is written in Scala itself and takes into account some of its specialities. Actually building works pretty fast, starting the interactive console (REPL) with the entire class path of the project just works, and we are able to cross-build against various Scala versions – these are just a few features we wish to highlight. Projects like Lift or Akka are already using SBT, or planning to use it.

Of course SBT is not the only possibility out there for compiling and running Scala code. So if you have your preferred IDE or want to use the command line tools that ship with the Scala distribution, you may skip the next part.

Starting a new SBT Project

Before starting our project, we need to “install” SBT. It’s really easy since SBT is only a JAR file: Download the latest version sbt-launch-0.7.4.jar from the SBT website, you’ll find this in the Downloads section. After that, just follow the simple steps provided in the Setup section: “how to create a startup script” Within MacOS it could look like this:

java -Xmx1024M -jar sbt-launch-0.7.4.jar “$@”

One more step before starting a project: make yourself a project-folder, e.g. gameoflife and go into that directory using the shell. Now we are good to go; run the SBT startup script to create a new project and answer the following questions:

gameoflife$ sbt

Project does not exist, create new project? (y/N/s) y

Name: gameoflife

Organization: com.weiglewilczek.gameoflife

Version [1.0]:

Scala version [2.7.7]: 2.8.0

 

Following the output, notice that SBT is downloading Scala 2.7.7 and Scala 2.8.0, which makes our lives easier as we don’t have to worry about that anymore. You may wonder why SBT is also downloading Scala 2.7.7? That’s because SBT itself runs on 2.7.7.

Starting SBT without any arguments will call the interactive SBT console, which provides commands such as exit, compile, test or run. Running exit or compile should be selfexplanatory, but what happens when we execute run? It will look for and execute a singleton object with a main method.

Now, there is a nifty little feature: when putting the “tilde” in front of the command, SBT will go into “triggered” mode where it will wait for changes in the filesystem and with any change, the command will be executed again. Using ~compile as an example, SBT will compile every time a file in the project is changed and saved. For further commands and details, please take a look at the excellent documentation on the SBT website. Running test for the first time will create some additional folders. When taking a look at illustration 1 you will see how your project should look. If you have ever worked with Maven, the src and target folders should look familiar, whereby the various Scala versions we are building our project against are held in the target folder. Looking at the project folder we can find configuration and downloaded files. We can drop libraries into the lib folder which are automatically added to the class path. Another feature compliant with Maven are “Managed Dependencies,” but we don’t actually need them here. Before we get down to business, let’s code up and run the most legendary piece of code. Switch into the folder src/main/scala and create Hello.scala:

object Hello {
def main(args: Array[String]) {
println("Hello World!")
}
}

 

Calling run in SBT will give us the well known “Hello World!” message.                                                                                       

Classes and Packages

Being a Java developer, we know the principles of object-orientated programming. Due to this, we will take an approach at Scala from the side we already know. That’s indeed possible, because Scala is a hybrid language combining the best features of object-orientated and functional programming. We won’t get too theoretical in this tutorial, but have outlined some of the basics of object-orientation in Scala in the adjacent box.

The Game of Life is all about dead and live cells. Therefore we will start with creating a file called Cell.scala in the source directory src/main/scala. There we define the class Cell using the keyword class, just like in Java:

class Cell



Starting with an empty class without fields or methods, we do not need curly braces or a semicolon thanks to the semicolon inference. Unlike Java, there is no access modifier public, because that is the default in Scala. Packages are similar yet more powerful compared to Java packages. One important difference is that there is no need to mirror the package structure in the file system. Therefore, it is possible to omit the “root package” of a project, but of course underlying packages should be represented by the directory structure. In our example we will have only the com.weiglewilczek. gameoflife package and therefore there is no need for subfolders. According to this our Cell should look like:

package com.weiglewilczek.gameoflife
class cell

The REPL

Although our cells are not too useful yet, we now want to introduce an important Scala tool: the interactive Scala console, also called Read Evaluate Print Loop (REPL). Running console in SBT will give us the REPL using the complete class path of our project. In the REPL we can write code and have it interpreted and executed immediately. With :help we can list various commands which we might need. First, let’s get our package imported. We’ll use the keyword import, followed by a whitespace and use the tab key to find our package with the autocompletion.

scala> import com.weiglewilczek.gameoflife._
import com.weiglewilczek.gameoflife._





Similar to Java’s “*” is the underline in Scala, which means that everything gets imported from our package. Now, let’s create a new instance of our cell using the keyword new just as we know it from Java. Since we are not using any arguments, parentheses are not needed yet.

scala> new Cell
res0: com.weiglewilczek.gameoflife.Cell = com...





Watching the REPL output, it will automatically create a new variable called res0 (later we will point out how we can provide our own variable names), printing its type and the result of the toString method. Let’s quit the REPL entering :quit (or :q) and get back to the code where we can give our cells some additional features.

Class Parameters, Fields and Methods

As cells are placed on a grid, we want to add their coordinates. Adding so called class parameters enclosed in parentheses after the class name will make this possible:

class Cell(x: Int, y: Int)





That looks different from that what we know from Java, right? First, there are no class parameters in Java and second, we annotate any parameters just like we do in UML, starting with the name followed by a colon and then the type.

OK, but what do these class parameters mean? And don’t we have a constructor? The compiler will take the class parameters and create the so called primary constructor for this class. This means that now we create our cells like this:

scala> new Cell(1, 2)
res0: com.weiglewilczek.gameoflife.Cell = com...





Class parameters are like private fields which means that we cannot access the coordinates and we cannot change the state of our cells. Later we will change the visibility of the coordinates,
but immutability is one of the most important principles of functional programming. Even in Java, immutable objects are well known and going by Effective Java it is always better to use immutable, rather than mutable, objects.

Using the keyword val defines an immutable field or local variable, just like using the final modifier in Java. There is also var to define mutable fields or local variables. Now we will create a private immutable field which will return the position of a cell as a String:

private lazy val position = "(%s, %s)".format(x, y)





But how does the compiler know that this field is a String? The Scala compiler is pretty smart: based on the value that is assigned, it recognizes that position shall be a String. This feature – called type inference – is also applicable for methods and generic types, making Scala code very lightweight even though it is statically typed.

But, what is the keyword lazy doing there? When using lazy, the initialization and therefore the evaluation of the “right side” only happens when the field is being approached for the first
time. Until now that was not happening, since position is a private field and it is not used internally in Cell. But taking a look at the REPL output suggests that we could use position to overwrite the toString method, because our cells are immutable:

override def toString = position





Using the keyword def will create a method. override must be used when overwriting concrete methods or fields and may optionally be used when implementing abstract ones. As before,
type inference allows us to omit the return type. In this case that’s fine, but when implementing non-trivial methods it is always good style to give the type. In our case it would look like this:

override def toString: String = position





Even if we do annotate the type, the code is still more lightweight than it is in Java: first, we don’t need curly braces when having a one-liner and second we don’t need a return statement, since a method returns the last line of a block by default. Moving ahead in this tutorial, we’ll see more of this in more complex methods. Let’s see how our changes will affect things on the REPL:

scala> new Cell(1, 2)
res0: com.weiglewilczek.gameoflife.Cell = (1, 2)





That looks better, right? However, we still can’t access the coordinates, because the class parameters are still private. Putting the keyword val in front will make them public:

class Cell(val x: Int, val y: Int) { ...





Let’s take a quick look into the REPL in order to see how this works. Now we are also using the keyword val to define a local variable with a meaningful name which we can use to further access our cell:

scala> val cell = new Cell(1, 2)
cell: com.weiglewilczek.gameoflife.Cell = (1, 2)
scala> cell.x
res0: Int = 1





 

                         

Case Classes

Now let’s get even easier. Using the keyword case in front of the class definition will convert our cell to a case class. This makes the compiler provide us with the following features,
amongst others:

• Class parameters are vals by default, so there is no need to write val in front of our parameters anymore.

• Instances may be created without the keyword new, but explaining this would be to much for our tutorial.

• Reasonable implementations are provided for equals, hashCode and toString; in this case we have overwritten toString ourselves, of course.

In listing 1, the complete code for our cells is shown after all these changes were made. Let’s take a quick look at the REPL, just to make sure that things work as expected:

scala> val cell = Cell(1, 2)
cell: com.weiglewilczek.gameoflife.Cell = (1, 2)
scala> Cell(1, 2) equals Cell(1, 2)
res0: Boolean = true
scala> Cell(1, 2) equals Cell(1, 1)
res1: Boolean = false




For Comprehensions

This might be a tick too early, but referring to our example it is necessary that we now look at one very interesting language feature called “for comprehensions.” In Scala like in other functional programming languages, it is common that everything has a return value. For example, there is an ifelse, but that’s not only for control flow like in Java but also has a result value, which can be assigned to a variable or can be used as a return value for a method. Therefore the if-else in Scala matches the conditional operator (x ? y : z) in Java. Now let’s talk about for comprehensions. In their primitive form, they are like loops:

for (i <- 1 to 10) { ... }




Exceptionally having no return value, they will only wield some sort of side effect. By the way, to is not a keyword, but a method which, because of one advanced feature called implicit conversions, may be used on Int values and returns a collection of the type Range. Having for comprehensions in their functional form, they end with the keyword yield and have a result value. A quick little example:

scala> for (i <- 1 to 10) yield i + 1
res0: ...IndexedSeq[Int] = Vector(2, 3, 4, 5, 6, 7, 8, 9, 10, 11)




We can observe that a collection (Range 1 to 10) is mapped onto another one (Range 2 to 11). Now we want to use for comprehensions in order to calculate the neighbours of a cell:

def neighbours: Traversable[Cell] =
for {
i <- (x - 1 to x + 1)
j <- (y - 1 to y + 1) if (i != x) || (j != y)
} yield Cell(i, j)




OK, let’s explain this from the top to the bottom:


• Since we do not have a trivial one-liner here, we are giving the return type; as one can observe, type parameters are defined in brackets.

• Using curly braces instead of round ones; thanks to this, we can write more lines without using a semicolon.

• Using two so called generators in an effort to run trough all x- and y-coordinates around our cell.

• To lock out our own cell we are using a filter.

• Employing yield creates a collection of neighbour cells.

Taking a look at listing 2, we see the complete code for our cell after applying these changes. Let’s take a quick look at the REPL again, where we find the eight neighbours for the given cell as expected:

scala> cell.neighbours
res1: Traversable[...Cell] = Vector((0, 1), (0, 2), (0, 3), ...)




Unit Testing with specs

Running code in the REPL will give us a good feel for our code, but of course the need for systematic testing also applies to Scala. We could use JUnit, but there are some Scala test tools which are very powerful in creating self-explanatory tests.

We are going to take a look at specs: Please download the current version 1.6.5 for Scala 2.8.0 (specs_2.8.0-1.6.5.jar) and put the JAR file into the lib directory of the project.

Switch to the src/test/scala folder, which is our test folder, and create a class called CellSpec. We will use the same package as we have used for Cell and extend the class Specification form specs. Put the following lines into the body of the class:

"A Cell" should {
"have eight neighbours" in {
Cell(0, 0).neighbours must haveSize(8)
}
}




That looks more like prose, but is valid Scala code. Again we have implicit conversions working for us, so that the methods should and can be called on the Strings or the method must on the result from neighbours. As a result, we have got a pretty self-explanatory test. Concluding, let’s see how tests are executed in SBT. Executing test will result in all tests being compiled and executed.

As we can see, the strings which describe the test in our Scala code are used in the test report. Failed tests in particular, are outlined very nicely. To see how a failed test looks, we just apply a little change in the for comprehension like this: i <- (x– 1 to x – 1):

[info] A Cell should
[info] x have eight neighbours
[info] 'Vector((-1, -1))' doesn't have size 8. It has size 1 …




Collections

After finishing the cells, we will move to the generations, which represent the collective of all cells at a specific time. This leads us to collections, which are perfectly made for demonstrating the functional character of Scala.

Taking a look at illustration 2 we will see important representatives of the collection hierarchy. Traversable with about 100(!) methods is found on top. That amount makes it clear that Scala collections are very powerful, which is typical for a functional programming language. We want to describe a generation based on its living cells. Let’s create a new class Generation with the class parameter / field aliveCells of the type Set[Cell]:

package com.weiglewilczek.gameoflife
class Generation(val aliveCells: Set[Cell] = Set.empty)




We would like to point out two things here: for one thing, collections are typed in Scala. No surprise, because Java generics also came from Martin Odersky, Scala’s “godfather.” Another thing, we are defining an empty Set as default value, which is a new feature of Scala 2.8. With this, we can create a generation without the aliveCells argument.

scala> val generation = new Generation
generation: com.weiglewilczek.gameoflife.Generation = ...
scala> generation.aliveCells
res0: Set[com.weiglewilczek.gameoflife.Cell] = Set()




Of course, defining preconditions is also a part of a good style in Scala. Let’s define a precondition where null is not valid for the aliveCells parameter. For this matter we use a method called require, which comes from the singleton object Predef whose members are automatically imported by the Scala compiler.

require(aliveCells != null, "aliveCells must not be null!")




Filtering Collections

According to the game rules, when moving from one given generation to the next we have to determine the (number of) alive neighbours for a cell. For this we can make use of our already implemented method Cell.neighbours, although we still have to determine which of the resulting neighbours are alive.

For this purpose we will employ the power of functional programming, as we use the filter method that is a member of every collection. This method does not take a “normal” argument, but a function. Functions are similar to methods, since they may be called with arguments and have a return value. However, functions are not members of a class, but objects themselves, just in terms of “everything is an object.” As for numbers and Strings, so called literals are available for functions, too, which gives us the opportunity to simply write down a function.

The filter method expects a function that takes a parameter of the same type as the one the collection is parameterized, and returns a Boolean. In our example we have to provide a function that has a Cell parameter:

private def aliveNeighbours(cell: Cell) =
cell.neighbours filter { neighbour => aliveCells contains neighbour }




We notice that function literals are written with the arrow symbol. On the left side we have our arguments and on the right side the body of the function. Once again, thanks to the type inference, we don’t have to give any types. Also, a shorter notation is possible. filter requires a function Cell => Boolean and looking at the contains method from the Set aliveCells we see the exact same signature. Luckily the Scala compiler is working for us, converting this method into
a function. All we have to write now is:

private def aliveNeighbours(cell: Cell) =
cell.neighbours filter aliveCells.contains




Besides the alive neighbours, we also need the dead ones. The code is pretty similar to aliveNeighbours. Although, since we are not only working with the contains method but also using some extra logic with the negation, we have to write the function the “wordy” way.

private def deadNeighbours(cell: Cell) =
cell.neighbours filter { neighbour => !(aliveCells contains neighbour) }




Our generation should at the moment look like listing 3.

Mapping Collections

Now we want to determine the next generation, which is built from cells that stay alive and those that wake up from the dead.

def next: Generation = {
val stayingAlive = ...
val wakingFromDead = ...
new Generation(stayingAlive ++ wakingFromDead)
}




Once again we can see that there is no return necessary, as the last line in Scala is always our return value. Both variables staylingAlive and wakingFromDead are supposed to be Sets, which allows us to use the ++ method to create a new Set[Cell] for the next generation. From what we already know, we are able to implement staylingAlive: Let’s filter out all alive cells which have only two or three neighbours:

val stayingAlive =
aliveCells filter { 2 to 3 contains aliveNeighbours(_).size }




This is another short form to write function literals: we abandon the parameter list and arrow symbol, directly writing the function body, where the underline is a placeholder for the missing parameter. Having more parameters would force us to supply more underlines. Of course we could also have provided a more explicit notation:

aliveCells filter { cell => 2 to 3 contains aliveNeighbours(cell).size }




The next step is to implement wakingFromDead. Luckily we don’t have to look at all the dead cells on the playing field, but only at those that are in the neighbourhood of alive cells, because only a cell with three neighbours will wake up. Therefore we have to provide a way to get from the alive ones to their dead neighbours. We already have the method dead-Neighbours for a single cell, but how do we retrieve the dead neighbours for all alive cells?

Getting our result in the imperative way often used in Java, we would probably provide some sort of loop and write very detailed code in order to define how things must happen. Using functional programming our life is a tad bit easier. We just write what we want, but not how it shall be done! OK, back to the topic! What we are trying to do here here in two steps: we know the set of alive cells (aliveCells) and want to transform this into the set of dead neighbour cells. Thereafter, we have to filter if the dead neighbour cells have got exactly three alive neighbours.

For our first task, we’ll try the collection method map, which transforms a collection into a new one. Let’s look at a quick example in the REPL:

scala> List(1, 2, 3) map { x => x + 1 }
res15: List[Int] = List(2, 3, 4)
When porting this to our example, it could look like this:
aliveCells map deadNeighbours




Once again, the Scala compiler makes our lives easier, making a function out of the deadNeighbours method, so that this code can compile. But that is not what we wanted, because we are transforming a Set[Cell] into a Set[Traversable[Cell]], since deadNeighbours returns a
Traversable[Cell] for every Cell. For such a case we have a collection method called flatMap, which takes nested collections and literally pounds them flat. Once again a little example in the REPL:

scala> List(1, 2, 3) map { x => List(x - 1, x, x + 1) }
res18: List[List[Int]] = List(List(0, 1, 2), List(1, 2, 3), List(2, 3, 4))
scala> List(1, 2, 3) flatMap { x => List(x - 1, x, x + 1) }
res19: List[Int] = List(0, 1, 2, 1, 2, 3, 2, 3, 4)




With this knowledge we can implement wakingFromDead in the following way:

val wakingFromDead =
aliveCells flatMap deadNeighbours filter { aliveNeighbours(_).size == 3 }




Taking a look at this, you can see that we are chaining two calls: First calling flatMap on top of aliveCells giving dead-Neighbours as an argument. Until now we have had a return value of Set[Cell] that will be called using filter with a function literal, which gives us the dead cells with three alive neighbours.

 

Listing 4 provides the complete code for the class Generation and Listing 5 provides a few tests, which feature two interesting source generations. On the one hand we have the so called “blinker:” three horizontally aligned cells that are transformed into three vertically aligned ones, and back again. On the other hand we have a generation called “block” which does not change at all.

Swing GUI

We’re almost there! It is fascinating to watch the process of how generations evolve. In order to see this, we are going to build a little graphical user interface.

The goal is to have a nice little tutorial, and not how to build a powerful visualization of the Game of Life. So we will create a basic user interface, shown in illustration 3, which has the following features:

• Only views a finite section of the infinite playing field.

• The opportunity to toggle the status of the displayed cells via the mouse at any time.

• A “next” button which take us to the next generation.

As we want to get along with Scala we are only using the Scala Swing library, which makes working with Swing easier. Unfortunately explaining in detail what we have done in listing 6 would break the mold of this tutorial. Even though it is not too much code, there are a few concepts used that are way ahead of the basics. In the following, we try to pick out a few nice little highlights.

First, we see how easy it is to write a Swing application: We are extending SimpleSwingApplication and overriding the top method. Components are built by adding more components to the contents field. Overwriting reactions in a component and adding so called Reactions is necessary in order to handle events. Actions are associated directly with a button, as calling the singleton object Button and providing the code for the action as an argument.

Next we return to a few concepts that we have talked about and used earlier, e.g. building the playing field with a for comprehension or passing a function determining whether a cell is alive or dead as an argument.

Even though the class SwingUI is a bit more complicated than we have learned up until now, we will get a good idea of the possibilities offered by Scala and the Scala Swing library.

Conclusion

So far we have covered the most important Scala basics. Not only have we learned about the language itself, but also discussed tools like the REPL and SBT. Hopefully with this practical example we have not only shown that Scala is concise (e.g. Cell) and understandable (e.g. CellSpec), but is also capable of offering straightforward solutions to many problems
through its functional character (e.g. Generation.alive-Neighbours).

We are certainly hoping to get some feedback, questions, bug-reports (please use the issue tracker) or ideas on how to improve our tutorial! Have fun with Scala!

Author
HeikoSeeberger
Heiko Seeberger is managing director of WeigleWilczek and is responsible for the technological strategy with a strong focus on Java, Scala, OSGi, Eclipse RCP, Lift and Akka. Additionally he is an active open source committer and shares his expertise in articles and conference talks.

Leave a Reply

Be the First to Comment!

avatar
400
  Subscribe  
Notify of