pfm: .plan, site map, about

Learning Scala

Some time ago I’ve decided I’d like to learn Scala. I remember a friend of mine learning it a few years ago and my general impression of the language: quite powerful, but with a concise syntax. Concise syntax is a great advantage over Java, but I didn’t know Scala too well so this comparison is far from fair.

The problem I’ve been solving was counting (and displaying) combinations of chess pieces on a board where none of them would take / capture another.

Since Scala is a functional language, I’ve been focusing on using typical approaches found in functional programming: recursion (with tail-call optimization when possible) instead of while-do iteration, simple immutable data structures and so on.

My initial approach has been to represent a chess board as a 2-dimensional vector (Scala has a persistent data structures, including one called vector, based on Clojure’s implementation of a similar data structure). That way I could provide O(1) access to each piece on the board. I’ve implemented figures as case classes, with two special objects (scala has singletons built into the language):

• Nothing, representing a free location on the board, and
• Captured, representing a location on the board that was not occupied by any figure, but it was unsafe to put any figure there because it would be taken by another one.

My assumption has been that a persistent data structure would save me from OOM thanks to sharing common parts of board representations. Well, it hasn’t. I’ve launched my first version of the program with a 7×7 board and got an OutOfMemoryError quite soon (though it did work well with boards small enough). So I’ve faced the good old problem of being fast or correct.

I’ve started redesigning my code to reduce the memory footprint by taking another approach:

1. each figure would know its location and based on its coordinates it would calculate unsafe locations;
2. internally, board would be represented by a list of figures on the board (therefore adding a new figure was cheap and easy to repeat with different configurations: by “consing” a new list);
3. everything else would need to be calculated.

With this approach there was very little to store in memory but probably a large amount of repeated calculations. Nonetheless this version of my code did produce output for a 7×7 board (after 100 minutes of computation).

Among other problems I’ve found when implementing the second approach was that in my first solution, pieces didn’t have any state so I could instantiate them all at the beginning of the program and place on the board when appropriate. This had to be changed with introduction of piece coordinates as state. So I’ve introduced a kind of a factory:

object Pieces {
  def rook(x: Int, y: Int):   Piece = Rook(x, y)
  def queen(x: Int, y: Int):  Piece = Queen(x, y)
  def knight(x: Int, y: Int): Piece = Knight(x, y)
  def bishop(x: Int, y: Int): Piece = Bishop(x, y)
  def king(x: Int, y: Int):   Piece = King(x, y)
}

and instead of passing object instances, I’ve been passing curried functions:

val rookProducer = Pieces.rook _
val rook = rookProducer(3, 1)

Another thing I like a lot about functional programming are higher-order functions. I’ve used them in my solution as well:

def isCaptured(x: Int, y: Int): Boolean = {
  anyItem((p) => p.wouldCapture(x, y, dim), pieces)
}

def wouldCaptureExisting(newp: Piece): Boolean = {
  anyItem((p) => newp.wouldCapture(p.x, p.y, dim), pieces)
}

private
def anyItem(pred: (Piece) => Boolean, pcs: List[Piece]): Boolean = pcs match {
  case Nil => false
  case p :: ps => pred(p) || anyItem(pred, ps)
}

Short explanation: isCaptured checks whether location (x, y) is taken by any piece on the board while wouldCaptureExisting does it for a new piece that’s not yet on the board.

The key take-away is that Scala code is highly expressive and helps avoid unnecessary code duplication. And thanks to support for tail-call optimization it encourages recursive approach, which often is a good way to deconstruct bigger problems into smaller ones. However, it isn’t always easy to design a recursive algorithm to have that tail call without an additional argument to aggregate results.

This work by Piotr Mieszkowski is licensed under CC-BY-SA 4.0