Testing with Scala for Fun and Profit

Sometimes I like Scala, and sometimes I really like Scala.

So, I was writing some algorithms to compute the median of a sequence of values, just for the fun of it, adapting from pseudo-code description of an algorithm. The problem with pseudo-code is that it is pseudo-precise, meaning my algorithm was pseudo-correct, so I wanted to test it to ensure it really worked.

As it happens, the median of values has a trivial implementation that could be used to test against. So, one import and one one-liner afterwards, I had a quick way to test it from the REPL, where I could then experiment with the failing test case to understand what went wrong:

import org.scalacheck.Prop._
forAll((lst: List[Double]) => lst.nonEmpty ==> (myAlgorithm(lst) == lst.sorted.apply((lst.size - 1) / 2))).check

That uses the Scalacheck library, the best way to test algorithms in my opinion. What I'm doing with forAll is saying that for all inputs (List[Double]) of that function, the conditions must hold true. Specifically, if the input is not empty, then the result of my algorithm must be equal to the result of the trivial implementation of median. That will result in a property (class Prop).

I then tell it to check that property, which will be done by automatically generating input, with some heuristics to improve the chance of catching boundary cases, and testing the condition for each such input. If 100 tests pass, it finishes by saying:

+ OK, passed 100 tests.

Or, if it fail at some point, it will say something like this:

! Falsified after 0 passed tests.                                             
> ARG_0: List("-1.0") (orig arg: List("-1.0", "8.988465674311579E307"))

To be honest, my one-liner was slightly longer, because I was using arrays and arrays in Java do not have a useful toString method, so I had to tell Scalacheck how to print the array. Both Scalatest and Specs support integration with Scalacheck too, so this can be easily turned into part of a test suite.

Now this helped me achieve correctness, but I was also interested in how fast the code could run. I had three different algorithms (including the trivial implementation), and two of them could be further refined by abstracting over the selection of a pivot (quicksort-style). At that point, I decided to build a small framework which would help me test everything automatically.

I wanted to test each algorithm three times for different input sizes. The basic measurement algorithm was done by one of the methods in my toolkit:

import java.lang.System.currentTimeMillis

def bench[A](n: Int)(body: => A): Long = {
  val start = currentTimeMillis()
  1 to n foreach { _ => body }
  currentTimeMillis() - start
}

This should be familiar to anyone who ever did microbenchmarking with Scala. With that in hand, another one liner got the results I wanted:

println(bench(50000)(myAlgorithm(Array.fill(500)(nextDouble))))

Which worked well enough for a while, but really didn't scale as I got more algorithm variations and tested them with different settings. So, to get the results for each algorithm, I wrote this:

import scala.util.Random.nextDouble

def benchmark(algorithm: Array[Double] => Double,
              arraySizes: List[Int]): List[Iterable[Long]] = 
    for (size <- arraySizes)
    yield for (iteration <- 1 to 3)
        yield bench(50000)(algorithm(Array.fill(size)(nextDouble)))

Which let me pass a list of sizes I wanted to test the stuff at, and run each benchmark three times, to give me a feel for the variation in the results. Next, I made a list of the algorithms I wanted tested:

val algorithms = sortingAlgorithm :: immutableAlgorithms

That's the list I started with, but it grew as I added other algorithms. As for the immutable algorithms, they were all the same method call, but passing different pivot selection as parameters. As it got a bit verbose, I decided to apply a bit of DRY. First, I made a list of my pivot selection algorithms:

val immutablePivotSelection: List[(String, Array[Double] => Double)] = List(
    "Random Pivot"      -> chooseRandomPivot,
    "Median of Medians" -> medianOfMedians,
    "Midpoint"          -> ((arr: Array[Double]) => arr((arr.size - 1) / 2))
)

Next, I used that list to produce a list of median algorithms using each of these pivot selections:

val immutableAlgorithms = for ((name, pivotSelection) <- immutablePivotSelection)
        yield name -> (findMedian(_: Array[Double])(pivotSelection))

With the list of algorithms in hand, it was a simple for comprehension to produce a list of results:

val benchmarkResults: List[String] = for {
    (name, algorithm) <- algorithms
    results <- benchmark(algorithm, arraySizes).transpose
} yield formattingString format (name, formatResults(results))

The transposition let me see each size on a different column, making it easier to compare the algorithms when displayed together. Anyway, once I had that ready, I could also easily use the list of algorithms to test them:

def test(algorithm: Array[Double] => Double, 
         reference: Array[Double] => Double): String = {
    def prettyPrintArray(arr: Array[Double]) = arr mkString ("Array(", ", ", ")")
    val resultEqualsReference = forAll { (arr: Array[Double]) => 
        arr.nonEmpty ==> (algorithm(arr) == reference(arr)) :| prettyPrintArray(arr)
    }
    Test.check(Test.Params(), resultEqualsReference)(Pretty.Params(verbosity = 0))
}

val testResults = for ((name, algorithm) <- algorithms)
    yield formattingString format (name, test(algorithm, sortingAlgorithm._2))

I could even make the test method more general, but parameterizing the type of the algorithm, and adding a parameter for a no-parameter function generating the input. This could be easily done, but it was not needed by the time I was finished.

I find the final result of a certain elegance (then again, I'm obviously biased), that's not the reason I really like Scala. What I really, really like about it, is how I could start very small, with a few easy commands on the REPL, and then use that as the basis for an increasingly more flexible framework to do the tests I wanted.

If anyone is interested in seeing the full code, it can be found here.

Sieve of Eratosthenes (the real one) Scala One-Liner

Here's a cute Sieve of Eratosthenes one liner (which I'm posting mostly so I won't loose it again):

(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))

It requires the forward pipe operator, such as the one provided by Scalaz or the one defined here.

Type Class pattern example

I was pleasantly suprised by the popularity of my last article, but some people expressed the wish to see a more practical example, outside Scala library. It is always difficult to use practical examples in blog articles, as they often require a lot of context to be properly understood and introduce a lot of unnecessary complexity.

So I'm going to compromise here. The example below discuss a common task in many systems, but which I'm going to present in a very simplistic manner. Specifically, how to format stuff for output.

There is much discussion about the proper place to handle output formatting. On one hand, for instance, we have the toString method available on every Java object. It is not uncommon to have serializer, toXML, or similar stuff either. On the other hand, such approach is not scalable and mixes business rules with presentation concerns, and architectures such as Model-View-Controller try to avoid it.

So let's try to solve this problem using the type class pattern. First, let's create or type class for a formatter which produces XML output (NodeSeq class), just as described in the last article. This time, there is one method we want this type class to have, though. Here it is:

import scala.xml.NodeSeq

abstract class FormatterXML[T] {
  def format(input: T): NodeSeq
}

To test it, we'll create a very simple method that takes this type class and use it to print stuff to the console.

def output[T](what: T)(implicit formatter: FormatterXML[T]) = println(formatter.format(what))

And, to finish the initial example, we'll create a simple class, good old Person, to test it. We'll put the implicit type class object inside the companion object of Person, so that it can be found automatically. Already, the class Person has become free of concerns about formatting, though companion object might be too close for some. This, however, is not necessary, as we'll see later.

In the code below, as in other examples later on, I'm declaring the case class and the companion object in the same line, so that it can be easily pasted on REPL (which won't recognize the companion object as a companion object otherwise). I added a test line too at the end.

case class Person(name: String, age: Int); object Person {
  implicit object Formatter extends FormatterXML[Person] {
    def format(input: Person): NodeSeq = <Person><Name>{input.name}</Name><Age>{input.age}</Age></Person>
  }
}

output(Person("John", 32))

So far, this can be trivially done in other ways, so we are gaining nothing. We'll gradually increase the complexity so that benefits of this approach start to show up. First, we'll create a Song class which has a Person member, so that we show off composition of the formatter.

case class Song(title: String, author: Person); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      <Author>{implicitly[FormatterXML[Person]].format(input.author)}</Author>
    </Song>
  }
}

output(Song("War Pigs", Person("Ozzy Osbourne", 61)))

Now, I'm sure all of you must be up in arms right now, because, as everyone knows, Ozzy Osbourne wasn't the sole author of War Pigs. We need to change the Song class to accomodate more authors, but that will make the formatter more complex. To help us here, let's create a formatter for generic lists, that we can use to simplify the Song formatter:

def ListFormatterXML[T](implicit formatter: FormatterXML[T]) = new FormatterXML[Traversable[T]] {
  def format(input: Traversable[T]): NodeSeq = <List>{input map formatter.format}</List>
}

Here we start to see an advantage to this approach. This method will work for any list (any traversable, in fact!), as long as there is a formatter for its members. Anyway, let's see the Song again:

case class Song(title: String, authors: Person*); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      <Authors>{ListFormatterXML[Person].format(input.authors)}</Authors>
    </Song>
  }
}

output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

This works, but having as the sole child of looks a bit weird. Let's do away with this:

def ListFormatterXML[T](kind: String)(implicit formatter: FormatterXML[T]) = new FormatterXML[Traversable[T]] {
  def format(input: Traversable[T]): NodeSeq = <List>{input map formatter.format}</List>.copy(label = kind)
}

case class Song(title: String, authors: Person*); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      {ListFormatterXML[Person]("Authors").format(input.authors)}
    </Song>
  }
}

output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

Personally, I like this better, but your milleage may vary. Anyway, let's increase complexity a bit. If we want scalability, we'd better make the formatter more flexible, able to handle many different formats. Let's redefine our type class, in a way that avoids changes to the code we have written so far:

abstract class Formatter[T, Format] {
  def format(input: T): Format
} 

abstract class FormatterXML[T] extends Formatter[T, NodeSeq] {
  def format(input: T): NodeSeq
}

We also need a new output, but here we have a problem. How do we specify the format type explicitly while, at the same time, inferring the input type? I'll confess not having given much thought to this problem, but the following code will work:

def as[F] = new {
  def output[T](what: T)(implicit formatter: Formatter[T, F]) = println(formatter.format(what))
}

With this new definition in place, we can recompile Person, Song and ListFormatterXML above, and try it out like this:

as[NodeSeq].output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

And, without changing any of that code, let's add a new output format to conclude this article:

implicit object PersonFormatterString extends Formatter[Person, String] {
  def format(input: Person): String = "%s, age %d" format (input.name, input.age)
}

def ListFormatterString[T](kind: String)(implicit formatter: Formatter[T, String]) = new Formatter[Traversable[T], String] {
  def format(input: Traversable[T]): String = input map formatter.format mkString (kind+" ", ", ", "; ")
}

implicit object SongFormatterString extends Formatter[Song, String] {
  def format(input: Song): String = input.title+" "+ListFormatterString[Person]("by").format(input.authors)
}

as[String].output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

Implicit tricks -- the Type Class pattern

Some people have been recently discovering the Scala equivalent of Haskell's Type Classes. I was a bit suprised because I thought everyone with enough Scala experience already knew about them, but, apparently, I was wrong.

A type class is basically a way to classify types based on the methods they offer. It offers an alternative to inheritance, in that you can group many different classes (types) that share a common set of methods, just like a superclass can be used to group its subclasses.

While Scala does not support type classes directly, the same patterns that hold true for Haskell can be simulated by using implicits in Scala. Perhaps a bit improperly, Scala programmers have been calling this pattern "type classes" as well.

It will feature proeminently in Scala 2.8, where examples can be found with Numeric, Ordering and even, I think, CanBuildFrom. In fact, one can find many questions on Stack Overflow related to Numeric being used precisely as a type class.

So, let me give a simple example of the kind of usage this can be put to. This is something someone just asked me on the #Scala channel on IRC, and I decided it makes for a nice example.

The problem put to me was restricting the options of a type parameter T without resorting to inheritance. For instance, if I want a method to work for Long and Int, but not any other type, there is no way to express that through a superclass. But the type class pattern can be used to solve it!

Here is the idea: I'll create an abstract class that will represent my type class. I'll then create elements representing the classes belonging to that type class. Finally, I'll use an implicit parameter to restrict my type parameter to that type class.

First, my abstract class:

abstract class Acceptable[T]

Yes, that's it. Not much to it, is there? Well, most often I would add to that class the methods I wish that type class to have. For instance, Numeric have all the normal operators you'd expect from classes that represent numbers. In this case, however, that won't be necessary, so I'm keeping it simple.

Next, let me create the members of my type class. I wish to create two of them: one for Int, and another for Long. To make them available without need for any import statements, I'll put them inside the companion class to Acceptable. Also, note that they are implicits.

object Acceptable {
  implicit object IntOk extends Acceptable[Int]
  implicit object LongOk extends Acceptable[Long]
}

Little to it, right? So, how do I get to use it? Well, let's create a simple method that will only accept Int and Long, as we wanted:

def f[T: Acceptable](t: T) = t

That weird declaration of T is called a context bound in Scala lingo. It's new to Scala 2.8, precisely to make this stuff easier. What it actually does is automatically define an implicit parameter -- and, for that very reason, it cannot be combined with other implicit parameters, though you can always use the full syntax to get the same result. Here's the full syntax:

def f[T](t: T)(implicit ev: Acceptable[T]) = t

So, does it work? Well, here is a small session using it:

scala> f(1)
res0: Int = 1

scala> f(1L)
res1: Long = 1

scala> f(1.0)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Double]
       f(1.0)
        ^

scala> f(1: Byte)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Byte]
       f(1: Byte)
        ^

Now, to those of you who may think this is neat but of little use, I'll point you to two examples of its usage in the new collections: the methods sum and max. If you try to call sum on a list of things that are not Numeric, it won't work -- at compile time. Likewise, if you try max on a list of things for which there are no Ordering available, it won't compile either. This way, these methods could be safely added to the collections without resorting to throwing exceptions at run-time!

This is just little window into what is possible -- enough to get a hang on the pattern without risking information overload. But look around, as there is much more to it!