From Java to Scala in O's and X's

I've been doing a lot of evangelising on the Scala language, mainly to Java devs that I work with. A number of the have become very interested in the language and have started making an effort to learn more about it. The most common questions that seem to come up relate to how to move from the Java to Scala language and the key differences (such as a functional approach, building apps though composition and mixins, the type system and so on).

With this in mind I decided to build a small application that starts as a typical Java development and over a number of versions becomes a full-blown Scala implementation. All versions of the application are maintained so that it becomes possible to step through and see each new level of progression into the Scala way of doing things. The progressions can be presented quickly in an hour or so, or it is possible to spend much longer on each one discussing design decisions and so forth. Even without the Scala focus, it's also a good application for discussing different design and implementation strategies with Java developers.

To have an application where the domain is easy to understand I picked the age old Noughts and Crosses game (Tic-Tac-Toe for my American readers). The advantages of this game are that it is very simple to learn and understand, it has some interesting data structures and interesting set of rules that can be explored for selecting the best move to make. It can also be implemented quite happily in a handful of classes and a few hundreds of lines of code. The particular approach I selected was to have the game played by two computer players who each take it in turns to pick the best move to make until one either wins or the game is drawn because the grid is full.

Aside: Initially the rules were so optimised that my implementation only ever resulted in a drawn game. The final solutions therefore ensure that the first couple of moves are randomly selected in order to introduce a bit of interest.

All of the source code that I'm going to discuss is available on my github account at: http://github.com/skipoleschris/OandX

Version 1 - Typical Java Code

After spending so much time writing Scala (and the most Scala like Java code possible) it was surprisingly difficult dropping back into the type of Java code that you find on most projects. For this version I tried to adopt the Java coding style of a typical average Java developer. Code is written in basic Java and tests in Java using TestNG. The solution works find but has a number of code and design smells, specifically:

• 'null' is used to represent empty positions on the grid
• The grid is represented in a Java Bean style and so all details of how to work with the contents of the Grid are actually outside the Grid class - leading to a pattern of utility classes that contain large amounts of domain logic
• There is a lot of duplication in the WinScanner and MoveFinder classes
• MoveFinder in particular makes it very difficult to separate the rules being applied from the complex code implementing them
• MoveFinder has the most fantastic if ( ... == null ) multi-repeated check method!

Version 2 - Slightly Improved Java Code with ScalaTest

The next version improves the Java code slightly. (It's still code way below the level I would normally write, but this is an exercise in converting from Java to Scala, not in producing perfect Java code!). In particular, the Grid class now contains more domain logic; the WinScanner and MoveFinder classes have duplication removed; and the MoveFinder is implemented with a chain of filters rather than the nasty if clause. The MoveFinder in particular is still WAY too complex.

The other main feature of this version is that tests have been ported over to ScalaTest. I went for the BDD style of tests using FeatureSpec, GivenWhenThen and MustMatchers as I feel this shows the full power of DSL-like test constructs. Most Java developers I have show this to seem to find it very readable. Typical tests now look like:

feature("The OnX grid") {

  scenario("can have a token added to it") {
    given("a new grid")
    val grid = new Grid

    when("a token is added at a given position")
    grid.addToken(Grid.MIDDLE, Token.nought)

    then("that position contains the token")
    grid.getToken(Grid.MIDDLE) must be (Token.nought)
  }

}

Hopefully much more readable!

Version 3 - Java Without Semicolons

The third version ports the Java code directly to Scala with minimal use of advanced Scala language features. All I did here was convert classes and data structures directly, remove boilerplate code and use Scala for loop syntax. At this point it just looks and reads pretty much like a Java application.

For example, here's the same method from the MoveFinder class implemented in both Java and Scala:

private static class DoubleWinPositionFinder implements PositionFinder {
    @Override
    public Position findPosition(final Grid grid, final Token token) {
        final Set positions = new HashSet();
        for ( final Line line : grid.getLinesWithMatchingTokenAndTwoSpaces(token)) {
            for ( final Position position : line.getEmptyPositions() ) {
                if ( positions.contains(position) ) return position;
                else positions.add(position);
            }
        }
        return null;
    }
}

private class DoubleWinPositionFinder extends PositionFinder {
  def findPosition(grid: Grid, token: Token): Position = {
    var positions = Set[Position]()
    for ( line <- grid.linesWithMatchingTokenAndTwoSpaces(token) ) {
      for ( position <- line.emptyPositions.toList ) {
        if ( positions.contains(position) ) return position
        else positions.add(position)
      }
    }
    null
  }
}

This approach is a great way to get working with Scala. Just bring all your Java knowledge and coding style with you, make use of the Scala tools, test frameworks and so on and gradually move towards advanced Scala when you feel comfortable.

Version 4 - Moving Forwards With Scala

In this version, I moved to a much more Scala like model. In particular:

• The Grid class is now immutable, returning a new Grid on each change
• The Option[T] concept is now used as a replacement for null to allow better representation of empty positions
• The code uses more advanced functional concepts such as map, flatMap, filter and so forth.
• Mixins are used to compose the Grid with traits representing line handling, win scanning and move finding. This gives a much better represented Grid concept and smaller API surface area while still allowing separation of concerns into separate traits and classes

While I think this is a much better implementation than version 3, I am still not happy with the implementation of some of the line building logic and the move finder is still too complex and makes it difficult to separate the rules being applied from how they are implemented. In particular code like this (which finds all the empty positions on a list of lines) is just way too messy:

def emptyPositions(lines: List[Tuple2[List[Option[Token]], Position]]) =
  lines.filter(_._1 contains None).flatMap(empties => empties._1 zip positions(empties._2)).filter(_._1 == None).map(_._2)

This leads me to believe that while I am using some of the more advanced language features that something is wrong with my underlying data structures if the code gets this complex. However, looking at our move finder function we can see some simplification starting to take place:

private case object DoubleFreePositionFinder extends PositionFinder {
  def findPosition(token: Token) = {
    val allEmptyPositions = emptyPositions(linesWithMatchingTokenAndTwoSpaces(token))
    if ( allEmptyPositions.contains(Position(1, 1))) Some(Position(1, 1))
    else if ( allEmptyPositions.isEmpty ) None
    else Some(allEmptyPositions.head)
  }
}

Version 5 - The Final Solution

For version 5 I decided to approach the problem from a much more functional perspective. By switching my thinking from the object approach (i.e. what is my state and how can I encapsulate it) to a functional approach (i.e. what functions do I want to perform) I was able to realise an important concept. Although the noughts and crosses game is represented as a grid, all of the functions we want to apply are either on an individual position on the grid or on one of the eight lines that can be made from the grid. By switching my data structure to one more appropriate for applying these functions we end up with a significantly simplified set of functions for evaluating the game state.

For example, we can take a list of tokens, zip them with a list of positions and then apply functions across either the token part or the position part of the pair:

class Grid(tokens: List[Option[Token]]) extends TokensWithPositions
                                        with Lines
                                        with LineQueryDSL
                                        with WinCheck
                                        with MoveFinder {

  require(tokens.length == 9)

  val positions = for (row <- 0 to 2; column <- 0 to 2) yield Position(row, column)
  private val values = tokens zip Grid.positions

Lines can therefore be represented in exactly the same manner:

type Line = List[Pair[Option[Token], Position]]

This new structure greatly simplifies the rest of the application code when it comes to building and working with lines:

def emptyPositions(lines: List[Line]) = lines.flatMap(_.filter(_._1 == None).map(_._2))

The other main change in this version is separation of the rules for finding the best position for a player from how those rules are implemented. This is achieved through a custom DSL that allows defining the rules in a highly readable way. For example, the rule we saw previously now becomes:

private def doubleFreePosition(token: Token) =
  find linesHaving 2 positions Empty and 1 tokenMatching token select First take EmptyPosition

The DSL is a fairly simple one, implemented as a chain of filtering functions that reduce the lines down and then a selector that pulls the correct result from the matching lines. It actually turns out that the DSL is pretty easy to read and follow through, which also significantly simplifies the code and reduces duplication.

Although version 5 is a much better solution, there is still room for improvement and some functions that could certainly be implemented in a better way. Let me know when you find them and send me your better solution :-)

Version 6 - Adding Some Actors

The final version takes the code from version 5 and wraps actors around the classes. One actor for the game coordinator, one for the grid and one for each player. These actors are loosely coupled through message passing.

Noughts and Crosses is not the best demonstration for actors and concurrency as it's turn based nature makes it a purely sequential game. However, version 6 does allow the concept of actors to be demonstrated in an easily understood way and leads on to more detailed conversations about using actors for concurrent problems.

Conclusions

The Noughts and Crosses example shows how a Java programmer can migrate to Scala in a gradual manner, adding new Scala concepts as they become more comfortable. However, it's important to point out that Scala is certainly not a silver bullet for good software. Like all development it requires careful thought, good design, solid programming practice, good testing and constant refactoring. Any Scala application will only be as good as the developer(s) building it.