Scala popularity

I had 5 posts in this blog throughout 2010 -- two in January, two in June. One post January of this year. Given that, I'm pretty sure no one follows my blog except, perhaps, as a forgotten automatic tracker of some sort.

Well... I decided to blog about something back on Sunday, which is a terrible day to blog something if you want hits. Late Sunday. Looking at statistics for Monday, though, I see that I have hit three times more hits than my previous record in a single day.

It is a heartening indication of how much interest Scala is attracting nowadays.

On Scala 2.9's road...

I suspect a lot of people are eagerly waiting for the parallel collections on Scala 2.9. The thing is... it's just not my thing. I like that it is being made available, but it's just not a pervasive feature for my small daily needs.

So, while I was somewhat bored by Scala 2.9, after the huge jump 2.8 was, there has been some nice improvements. For one thing, the jLine library used by REPL was replaced with one based on this (the canonical repository to the jLine actually used in Scala is here) giving a much superior experience. Now one can edit input that spans multiple lines (longer than the number of columns in the screen) without trouble, search the history, etc. There's even something to show its key-bindings: just type :keybindings.

And speaking of REPL, it doesn't stop there, by a long margin! There's :javap, which will happily decompile a class or file, :type which will show an expression's type without evaluating it, and :implicits to show what implicits are in scope. Add -v to that last one, and it will show those that come with Predef by default.

Those of you pasting code into REPL, or wanting to define companion objects, or pretty much any other feature that depends on the content of the next line, you'll be happy to know there's now :paste. Instead of instantly evaluating each line, it will wait until you hit ^D.

More recently, a few features came up that will help those that like to do Scala scripting. The -absolute-cp parameter will ensure relative paths on classpaths will be made absolute based on where the script is being run from, not where the compilation daemon was started at. If you don't even know what I'm talking about, then trust me: that will save you a lot of pain.

Another option, -max-idle, will let you specify how long the compilation daemon will stay up when idle, and even disable its auto-shutdown.

And just to make scripting even nicer, SBT's Process library is now available in Scala, as sys.process! Now we can do stuff like this:

import sys.process._

Process cat new URL("http://databinder.net/dispatch/About") !

"find src -name *.scala -exec grep null {} ;"  #|  "xargs test -z"  #&&  "echo null-free"  #||  "echo null detected"  !

Another interesting scripting feature is that not only will files containing a single object with a main method be runnable as if it were a script, but jar files produced by scala when it compiles scripts will be runnable like programs. For example:

% cat script.scala
object FiddleDeeMain {
  def main(args: Array[String]): Unit = {
    println(args mkString " ")
  }
}
% scala -nocompdaemon script.scala a b c
a b c

And, conversely,

% cat script2.scala
println(args mkString " ")

% scala -save script2.scala arg1 arg2
arg1 arg2

% scala script2.jar arg1 arg2
arg1 arg2

On the library side, a few things have happened too. Some changes where made to view, which made it much faster than it used to be. Arguably, its previous lack of performance resulted from a bug, so if you had performances issues with it, you might want to check it out again. Also on the performance front, another change with lots of potential is the introduction of a new hash code algorithm -- murmur3.

To those of you who like writing methods and classes with Numeric and Ordering, you'll probably like to know that you can now add "import Numeric.Implicits._" and "import Ordering.Implicits._" and avoid all that messy implicit parameter handling. For example:

import Numeric.Implicits._

def sum[N: Numeric](lst: List[N]) = lst reduceLeft (_ + _)

It might not seem much for a single method like that, but if you use this stuff often, I'm sure you see the advantages.

There are plenty of small changes that will make life easier, or more intuitive. For example, -5.abs will now work. Scaladoc is much faster. Many bugs have been fixed, even on places you'd never guess there were bugs (scary thought).

An interesting improvement is the introduction of DelayedInit. While most people won't ever hear of it -- unless it starts getting used in DSLs --, it enabled the rehabilitation of a much criticized feature: the Application trait. It is not that Application was a bad idea, but it was badly implemented. Given all that has been written about staying away from it, its new implementation was also given a new name, which we can now start using in our blogs everywhere: App.

On the realm of experimental stuff that may never make 2.9 at all, I'm pretty fond of -Yrich-exceptions. It adds some capabilities to exceptions on REPL. One example is lastException.show, which will display the source code location of the exception, if available (to use it, point SOURCEPATH to the source code).

There are plenty of other improvements, way too many to talk about: better docs, better error messages, better performance, bug fixes, more methods, new traits and classes, not to mention improvements made for people creating compiler plugins or working on Scala itself. If you want to get more dibs into Scala 2.9, there's a japanese site tracking the changes, though only looking through the commit log one can truly feel the scope of what Scala 2.9 is. Kudos to Scala's development team!

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.