A++ [Eric Torreborre's Blog]

Pragmatic IO - part 3

2011-12-09T10:29:00.001+09:00

A follow-up to my previous posts about IO.

Why types and laws matter

It's embarrassing to write post after post only to find out I keep being wrong :-). While the technique I described in my last post (using StreamT) works ok, I actually don't have to use it. The traverse technique explained in EIP works perfectly, provided that:

we write a proper Traverse instance using foldLeft (as explained in the first part of this post)
we trampoline the State to avoid Stack overflows due to a long chain of flatMaps during the traversal
we use the right types!

Get the types right

That's the point I want to insist on today. Last evening I read the revisited WordCount example in Scalaz-seven which is like the canonical example of using the EIP ideas. Two words in the comments struck my mind: "compose" and "fuse". Indeed, one very important thing about EIP is the ability to compose Applicatives so that their actions should "fuse" during a traversal. As if they were executed in the same "for" loop!

So, when I wrote in my previous post that I needed to traverse the stream of lines several times to get the results, something had to be wrong somewhere. The types were wrong!

instead of traversing with State[S, *] where * =:= IO[B], I should traverse with State[S, IO[*]]
what I get back is a State[S, IO[Seq[B]]], instead of a State[S, Seq[IO[B]]
this matters because passing in an initial state then returns IO[Seq[B]] instead of Seq[IO[B]]

Exactly what I want, without having to sequence anything.

Use the laws

Not only I get what I want, but also it is conceptually right as the result of an important traverse law:

  traverse(f compose g) == traverse(f) compose traverse(g)

That "fusion" law guarantees that composing 2 effects can be fused, and executed in only one traversal. It's worth instantiating f and g to make that more concrete:

  // what to do with the line and line number
  def importLine(i: Int, l: String): (Int, IO[Unit]) =
    (i, storeLine(l) >>= println("imported line "+i))

  // `g` keeps track of the line number
  val g : String => State[Int, String] =
    (s: String) => state((i: Int) => (i+1, s))

  // `f` takes the current line/line number and do the import/reporting
  val f : State[Int, String] => State[Int, IO[Unit]] =
    st => state((i: Int) => importLine(st(i)))

  // `f compose g` fuses both actions
  val f_g: String => State[Int, IO[Unit]] = f compose g

I'm really glad that I was able to converge on established principles. Why couldn't I see this earlier?

Scala and Scalaz-seven might help

In retrospect, I remember what led me astray. When I realized that I had to use a State transformer with a Trampoline, I just got scared by the Applicative instance I had to provide. Its type is:

  /**
   * Here we want M1 to `Trampoline` and M2 to be `IO`
   */
  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative] =
    Applicative.applicative[({type l[a] = StateT[M1, S, M2[a]]})#l]

I also need some Pure and Apply instances in scope:

  implicit def StateTMApply[M1[_]: Monad, S, M2[_] : Applicative] =
    new Apply[({type l[a]=StateT[M1, S, M2[a]]})#l] {
      def apply[A, B](f: StateT[M1, S, M2[A => B]], a: StateT[M1, S, M2[A]]) =
        f.flatMap(ff => a.map(aa => aa <*> ff))
    }

  implicit def StateTMPure[M1[_] : Pure, S, M2[_] : Pure] =
    new Pure[({type l[a]=StateT[M1, S, M2[a]]})#l] {
      def pure[A](a: => A) = stateT((s: S) => (s, a.pure[M2]).pure[M1])
    }

Once it's written, it may not seem so hard but I got very confused trying to get there. How can it be made easier? First, we could have better type annotations for partial type application, like:

  // notice the * instead of the "type l" trick
  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative] =
    Applicative.applicative[StateT[M1, S, M2[*]]]

  implicit def StateTMApply[M1[_]: Monad, S, M2[_] : Applicative] =
    new Apply[StateT[M1, S, M2[*]]] {
      def apply[A, B](f: StateT[M1, S, M2[A => B]], a: StateT[M1, S, M2[A]]) =
        f.flatMap(ff => a.map(aa => aa <*> ff))
    }

  implicit def StateTMPure[M1[_] : Pure, S, M2[_] : Pure] =
    new Pure[StateT[M1, S, M2[*]]] {
      def pure[A](a: => A) = stateT((s: S) => (s, a.pure[M2]).pure[M1])
    }

And with a better type inference, the first definition could be even be (we can always dream :-)):

  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative]:
    Applicative[StateT[M1, S, M2[*]]] = Applicative.applicative

Which means that it may even be removed, just import Applicative.applicative!

Actually Scalaz-seven might help by:

providing those instances out-of-the box
even better, provide combinators to create those instances easily. That's what the compose method does
give even better type inference. Look at the traverseU method here, no type annotations Ma!

Now that the fundamentals are working ok for my application, I can go back to adding features, yay!

Pragmatic IO - part 2

2011-12-08T15:32:00.001+09:00

A follow-up to my previous post about IO.

Learning by being wrong, very wrong

I didn't think that diving into the functional IO world would have me think so hard about how to use some FP concepts.

Mind the law

The technique I described at the end of my previous post didn't really work. It was wrong on many accounts. First of all, my
Traverse instance was buggy because I was reversing the traversed Stream. This is why I had inverted messages in the console. During the traversal, starting from the left, I needed to append each traversed element to the result, not prepend it:

  /**
   * WRONG: because each new element `b` must be appended to the result.
   * it should be bs :+ b instead
   */
  def SeqLeftTraverse: Traverse[Seq] = new Traverse[Seq] {
    def traverse[F[_]: Applicative, A, B](f: A => F[B], as: Seq[A]): F[Seq[B]] =
      as.foldl[F[Seq[B]]](Seq[B]().pure) { (ys, x) =>
        implicitly[Apply[F]].apply(f(x) map ((b: B) => (bs: Seq[B]) => b +: bs), ys)
      }
  }

It is important to mention here that proper testing should have caught this. There are some laws that applicative traversals must satisfy (see EIP, section 5. One of them is that seq.traverse(identity) == seq. This is obviously not the case when I returned a reverted sequence.

Not at the right time

Then I realized something also which was also worrying. On big files, my application would do a lot, then, report its activity to the console. This would definitely not have happened in a simple for loop with unrestricted effects!

So I set out to find a better implementation for my file reading / records saving. The solution I'm going to present here is just one way of doing it, given my way of constraining the problem. There are others, specifically the use of Iteratees.

My goal

This is what I want to do: I want to read lines from a file, transform them into "records" and store them in a database. Along the way, I want to inform the user of the progress of the task, based on the number of lines already imported.

More precisely, I want 2 classes with the following interfaces:

the Source class is capable of reading lines and do something on each line, possibly based on some state, like the number of lines already read.
The Source class should also be responsible for closing all the opened resources whether things go wrong or not
the Extractor class should provide a function declaring what to do with the current line and state. Ideally it should be possible to create that function by composing independent actions: storing records in the db and / or printing messages on the console
and, by the way, I don't want this to go out-of-memory or stack overflow at run-time just because I'm importing a big file :-)

Mind you, it took me quite a while to arrive there. In retrospect, I could have noticed that:

all the processing has to take place inside the Source.readLines method. Otherwise there's no way to close the resources properly (well unless you're using Iteratees, what Paul Chiusano refers to as "Consumer" processing)
the signature of the function passed to Source.readLines has to be String => State[IO[A]], meaning that for each line, we're doing an IO action (like saving it to the database) but based on a State
the end result of readLines has to be IO[Seq[A]] which is an action returning the sequence of all the return values when all the IO actions have been performed

Considering all that, I ended up with the following signatures:

  /**
   * @param  filePath the file to read from
   * @f      a function doing an IO action for each line, based on a State
   * @init   the initial value of the State
   * @return an IO action reading all the lines and returning the sequence of computed values
   */
   def readLinesIO[S, A](filePath: String)(f: String => State[S, IO[A]])(init: S): IO[Seq[A]]

and the Extractor code goes:

  // the initial state
  val counter = new LogarithmicCounter(level = 100, scale = 10)

  // a function to notify the user when we've reached a given level
  val onLevel            = (i: Int) => printTime("imported from "+filePath+": "+i+" lines")
  // a function to create and store each line
  def onCount(l: String) = (i: Int) => createAndStoreRecord(Line(file, l), creator)

  // for each line, apply the actions described as a State[LogarithmicCounter, IO[A]] object
  readLinesIO(file.getPath)(l => counter.asState(onLevel, onCount(l)))(counter)

I like that interface because it keeps things separated and generic enough:

reading the lines and opening/closing the resources goes to one class: Source
defining how the state evolves when an action is done goes to the LogarithmicCounter class
defining what to do exactly with each line goes in one class, the Extractor class

Now, the tricky implementation question is: how do you implement readLinesIO?

What not to do

Definitely the wrong way to do it is to use a "regular" traverse on the stream of input lines. Even with the trampolining trick described in my previous post.

Indeed traverse is going to fold everything once to go from Stream[String] to State[S, Seq[IO[B]]] then, with the initial State value, to Seq[IO[B]] which then has to be sequenced into IO[Seq[B]]. This is guaranteed to do more work than necessary. More than what a single for loop would do.

The other thing not to do is so silly that I'm ashamed to write it here. Ok, I'll write it. At least to avoid someone else the same idea. I had an implicit conversion from A to IO[A],...

That's a very tempting thing to do and very convenient at first glance. Whenever a function was expecting an IO[A], I could just pass a without having to write a.pure[IO]. The trouble is, some actions were never executed! I don't have a specific example to show, but I'm pretty sure that, at some point, I had values of type IO[IO[A]]. In that case, doing unsafePerformIO, i.e. "executing" the IO action only returns another action to execute and doesn't do anything really!

Learn your FP classes

I must admit I've been reluctant to go into what was advised on the Scalaz mailing-list: "go with StreamT", "use Iteratees". Really? I just want to do IO! Can I learn all that stuff later? I finally decided to go with the first option and describe it here in detail.

StreamT is a "Stream transformer". It is the Scala version of the ListT done right in Haskell. That looks a bit scary at first but it is not so hard. It is an infinite list of elements which are not values but computations. So it more or less has the type Seq[M[A]] where M is some kind of effect, like changing a State or doing IO.

My first practical question was: "how do I even build that thing from a Stream of elements?"

Unfolding a data structure

Unfolding is the way. In the Scala world we are used to "folding" data structures into elements: get the sum of the elements of a list, get the maximum element in a tree. We less often do the opposite: generate a data structure from one element and a function. One example of this is generating the list of Fibonacci numbers out of an initial pair (0, 1) and a function computing the next "Fibonacci step".

With the StreamT class in Scalaz, you do this:

  /** our record-creation function */
  def f[B]: String => M[B]

  /**
   * unfolding the initial Stream to a StreamT where we apply
   * a `State` function `f` to each element
   */
  StreamT.unfoldM[M, B, Seq[A]](seq: Seq[A]) { (ss: Seq[A]) =>
    if (ss.isEmpty)  (None: Option[(B, Seq[A])]).pure[M]
    else              f(ss.head).map((b: B) => Some((b, ss.tail)))
  }

The code above takes an initial sequence seq (the Stream of lines to read) and:

if there are no more elements, you return None.pure[M], there's nothing left to do. In my specific use case that'll be State[LogarithmicCounter, None]
if there is an element in the Stream, f is applied to that element, that is, we create a record from the line and store it in the database (that's the b:B parameter, which is going to be an IO action)
because M is the State monad, when we apply f, this also computes the next state to keep track of how many rows we've imported so far
then the rest of the stream of lines to process, ss.tail, is also returned and unfoldM will use that to compute the next "unfolding" step

One very important thing to notice here is that we haven't consumed any element at that stage. We've only declared what we plan to do with each element of the input stream.

Running the StreamT

In the StreamT object in Scalaz there is this method call runStreamT taking in:

a StreamT[State[S, *], A], so that's a StreamT where the state may change with each element of the Stream
an initial state s0
and returning a StreamT[Id, A]

Note: State[S, *] is a non-existing notation for ({type l[a]=State[S, a]})#l

That doesn't see to be game-changing, but this does a useful thing for us. runStreamT "threads" the State through all elements, starting with the initial value. In our case that means that we're going to create IO actions, where each created action depends on the current state (the number of lines read so far).

The cool thing is that so far we've described transformations to apply: Stream[String] to StreamT[State, IO[B]] to StreamT[Id, IO[B]] but we still haven't executed anything!

UnsafePerformIO at last

Then, I coded an unsafePerformIO method specialized for Stream[Id, IO[A]] to execute all the IO actions. The method itself is not difficult to write but we need to make sure it's tail-recursive:

  /** execute all the IO actions on a StreamT when it only contains IO actions */
  def unsafePerformIO: Seq[A] = toSeq(streamT, Seq[A]())

  /**
   * execute a StreamT containing `IO` actions.
   *
   * Each IO action is executed and the result goes into a list of results
   */
  @tailrec
  private def toSeq[A](streamT: StreamT[Id, IO[A]], result: Seq[A]): Seq[A] =
    streamT.uncons match {
      case Some((head, tail)) => toSeq(tail, result :+ head.unsafePerformIO)
      case None               => result
    }

Hidding everything under the rug

Let's assemble the pieces of the puzzle now. With an implicit conversion, it is possible to transform any Seq to a StreamT performing some action on its elements:

   /**
    * for this to work, M[_] has to be a "PointedFunctor", i.e. have "pure" and
    * "fmap" methods. It is implemented using the `unfoldM` method code seen above
    */
   seq.toStreamT(f: A => M[B]): StreamT[M, B]

Then, we can traverse a whole sequence with a composition of a State and IO actions:

   seq.traverseStateIO(f)

Where traverseStateIO is using the toStreamT transformation and is defined as:

  /**
   * traverse a stream with a State and IO actions by using a Stream transformer
   */
  def traverseStateIO[S, B](f: A => State[S, IO[B]])(init: S): Seq[B] =
    StreamT.runStreamT(seq.toStreamT[State[S, *], IO[B]](f), init).unsafePerformIO

[you'll get bonus points for anyone providing a Traverse[Stream] instance based on StreamT - if that exists]

Finally the Source.readLines method is implemented as:

  /**
   * this method reads the lines of a file and apply stateful actions.
   * @return an IO action doing all the reading and return a value for each processed line
   */
  def readLinesIO[S, A](path: String)(f: String => State[S, IO[A]])(init: S): IO[Seq[A]] =
    readLines(path)(f)(init).pure[IO]

  private
  def readLines[S, A](path: String)(f: String => State[S, IO[A]])(init: S): Seq[A] = {
    // store the opened resource
    var source: Option[scala.io.Source] = None
    def getSourceLines(src: scala.io.Source) = { source = Some(src); getLines(src) }

    try {
      // read the lines and execute the actions
      getSourceLines(fromFile(path)).toSeq.traverseStateIO(f)(init)
    } finally { sources.map(_.close()) }
  }

And the client code, the Extractor class does:

  val counter = new LogarithmicCounter(level = 100, scale = 10)

  // notify the user when we've reached a given level
  val onLevel            = (i: Int) => printTime("imported from "+filePath+": "+i+" lines")
  // create and store a record for each new line
  def onCount(l: String) = (i: Int) => createAndStoreRecord(Line(file, l), creator)

  // an `IO` action doing the extraction
  readLinesIO(file.getPath)(l => counter.asState(onLevel, onCount(l)))(counter)

Conclusion

I've had more than one WTF moment when trying to mix-in State, IO and resources management together. I've been very tempted to go back to vars and unrestricted effects :-).

Yet, I got to learn useful abstractions like StreamT and I've seen that it was indeed possible to define generic, composable and functional interfaces between components. I also got the impression that there lots of different situations where we are manually passing state around which is error-prone and which can be done generically by traverse-like methods.

Pragmatic IO

2011-12-05T15:51:00.000+09:00

This post is my exploration of the use of the IO type in a small Scala application.

A short `IO` introduction

Scala is a pragmatic language when you start learning Functional Programming (FP). Indeed there are some times when you can't apply the proper FP techniques just because you don't know them yet. In those cases you can still resort to variables and side-effects to your heart's content. One of these situations is IO (input/output).

Let's take an example: you need to save data in a database (not a rare thing :-)). The signature of your method will certainly look like that:

  /** @return the unique database id of the saved user */
  def save(user: User): Int

This method is not referentially transparent since it changes the state of the "outside world": if you call it twice, you'll get a different result. This kind of thing is very troubling for a Functional Programmer, that doesn't make him sleep well at night. And anyway, in a language like Haskell, where each function is pure you can't implement it. So how do you do?

The neat trick is to return an action saying "I'm going to save the user" instead of actually saving it:

  def save(user: User): IO[Int]

At first, it seems difficult to do anything from there because we just have an IO[Int], not a real Int. If we want to display the result on the screen, what do we do?

We use IO as a Monad, with the flatMap operation, to sequence the 2 actions, into a new one:

  /** create an IO action to print a line on the screen */
  def printLine(line: Any): IO[Unit] = println(line).pure[IO]

  /** save a user and print the new id on the screen */
                                           // or save(user) >>= printLine
  def saveAndPrint(user: User): IO[Unit] = save(user).flatMap(id => printLine(id))

Then finally when we want to execute the actions for real, we call unsafePerformIO in the main method:

  def main(args: Array[String]) {
    saveAndPrint(User("Eric")).unsafePerformIO
  }

That's more or less the Haskell way to do IO in Scala but nothing forces us to do so. The natural question which arises is: what should we do?

`IO` or not `IO`

Before starting this experiment, I fully re-read this thread on the Scala mailing-list, and the answer is not clear for many people apparently. Martin Odersky doesn't seemed convinced that this is the way to go. He thinks that there should be a more lightweight and polymorphic way to get effect checking and Bob Harper doesn't see the point.

Surely the best way to form my own judgement was to try it out by myself (as encouraged by Runar). One thing I know for sure is that, the moment I started printing out files in specs2, I got an uneasy feeling that something could/would go wrong. Since then,
IO has been on my radar of things to try out.

Luckily, these days, I'm developing an application which is just the perfect candidate for that. This application:

reads log files
stores the records in a MongoDB database
creates graphs to analyze the data (maximums, average, distribution of some variables)

Perfect but,... where do I start :-)?

Theory => Practice

That was indeed my first question. Even in a small Swing application like mine the effects were interleaved in many places:

when I opened the MongoDB connection, I was printing some messages on the application console to inform the user about the db name, the MongoDB version,...
the class responsible for creating the reports was fetching its own data, effectively doing IO
datastore queries are cached, and getting some records (an IO action) required to get other data (the date of the latest import, another IO action) to decide if we could reuse the cached ones instead

The other obvious question was: "where do I call unsafePerformIO?". This in an interactive application, I can't put just one
unsafePerformIO in the main method!

The last question was: "OMG, I started to put IO in a few places, now it's eating all of my application, what can I do?" :-))

Segregating the effects

Here's what I ended up doing. First of all let's draw a diagram of the main components of my application before refactoring:

   +-------+    extract/getReport       +------ IO +   store      +------ IO +
   + Gui   + <------------------------> + Process  + -----------> + Store    +
   +-------+     Query/LogReport        +----------+              +----------+
                                             | getReport               ^
                                             v                         |
                                        +------ IO +     getRecords    |
                                        + Reports  + ------------------+
                                        +----------+

Simple app, I told you.

The first issue was that the Reports class (actually a bit more than just one class) was fetching records and building reports at the same time. So if I decided to put IO types on the store I would drag them in any subsequent transformation (marked as IO on the diagram).

The next issue was that the Process class was also doing too much: reading files and storing records.

Those 2 things led me to this refactoring and "architectural" decision, IO annotations would only happen on the middle layer:

                                        +------- IO +            store
                               read     + Extractor + -----------------------------+
                               files    +-----------+          |                   |
                                             ^                 |                   |
                                             | extract         v                   v
   +-------+    extract/getReport       +----------+      +------ IO +        +----------+
   + Gui   + <------------------------> + Process  +      + Status   +        + Store    +
   +-------+     Query/LogReport        +----------+      +----------+        +----------+
                                             | getReport       ^                   ^
                                             v                 |                   |
                                        +------ IO +           |    getRecords     |
                                        + Reporter + ------------------------------+
                                        +----------+
                                             | createReport
                                             v
                                        +----------+
                                        + Reports  +
                                        +----------+

all the IO actions are being segregrated to special classes. For example extracting lines for log files creates a big composite IO action to read the lines, to store the lines as a record and to report the status of the extraction. This is handled by the Extractor class

the Status class handles all the printing on the the console. It provides methods like:

  /**
   * print a message with a timestamp, execute an action,
   * and print an end message with a timestamp also.
   *
   * This method used by the `Extractor`, `Reporter` and `Process` classes.
   */
   def statusIO[T](before: String, action: IO[T], after: String): IO[T]`

the Reports class only deals with the aggregation of data from records coming from the Store. However it is completely ignorant of this fact, so testing becomes easier (true story, that really helped!)
the Store does not have any IO type. In that sense my approach is not very pure, since nothing prevents "someone" from directly calling the store from the middle layer without encapsulating the call in an IO action. I might argue that this is pragmatic. Instead of sprinkling IO everywhere I started by defining a layer isolating the IO world (the data store, the file system) from the non-IO world (the reports, the GUI. Then, if I want, I can extend the IO marking the rest of the application if I want to. That being said I didn't do it because I didn't really see the added-value at that stage. A name for this approach could be "gradual effecting" (the equivalent of "gradual typing")
the Process class is not marked as IO because all the methods provided by that class are actually calling
unsafePerformIO to really execute the actions. This is the only place in the application where this kind of call occurs and the GUI layer could be left unchanged

All of that was not too hard, but was not a walk in the park either. Some details of the implementation were hard to come up with.

Under the bonnet: syntactic tricks

First of all, what was easy?

"Monadic" sequencing

Sequencing IO actions is indeed easy. I've used the for comprehension:

  def statusIO[T](before: String, action: IO[T], after: String): IO[T] = {
    for {
      _      <- printTime(before)
      result <- action
      _      <- printTime(after)
    } yield result
  }

"Semi-column" sequencing

But also the >>=| operator in Scalaz to just sequence 2 actions when you don't care about the first one:

  def statusIO[T](before: String)(action: IO[T]): IO[T] = printTime(before) >>=| action

"Conditional" sequencing

And, for the fun of it, I implemented a "conditional flatMap operator", >>=?:

  action1 >>=? (condition, action2)

In the code above the action1 is executed and, if the condition is true, we execute action2 and forget about the result of action1, otherwise we keep the result of action1.

"if else" with a twist

Not completely related to IO I also liked the ?? operator. Say I want to execute an action only if a file exists:

   if (file.exists) createRecords(file)
   else             ()

The else line really feels ugly. This kind of "default value" should be inferred from somewhere. Indeed! This "default value" is the Zero of a given type in Scalaz, so it is possible to write:

   file.exists ?? createRecords(file)

It just works (tm) but it's worth knowing where that zero values really comes from:

createRecords(file) returns IO[Int] (the last created id - that's a simplification of the real program)

there is a way to create a Monoid from another Monoid + an Applicative:

// from scalaz.Monoid
/** A monoid for sequencing Applicative effects. */
def liftMonoid[F[_], M](implicit m: Monoid[M], a: Applicative[F]): Monoid[F[M]] =
  new Monoid[F[M]] {
    val zero: F[M] = a.pure(m.zero)
    def append(x: F[M], y: => F[M]): F[M] =
      a.liftA2(x, y, (m1: M, m2: M) => m.append(m1, m2))
  }

in this case IO has an Applicative, M is Int so it has a Monoid hence IO[Int] defines a Monoid where the zero is IO(0). I had to open up the debugger to check that precisely :-)

Under the bonnet: it just works,... not

The next piece of implementation I was really happy with was the "logarithmic reporting". This is a feature I implemented using vars at first, which I wanted to make pure in my quest for IO.

What I want is to extract log lines and notify the user when a bunch of lines have been imported (so that he doesn't get too bored). But I don't know how many lines there are in a given file. It could be 100 but it could be 30.000 or 100.000. So I thought that a "logarithmic" counter would be nice. With that counter, I notify the user every 100, 1000, 10.000, 100.000 lines.

The LogarithmicCounter works by creating a State object encapsulating 2 actions to do, one on each tick, one when a
level is reached:

    // create and store a line on each `tick`
    def onCount(line: String) = (i: Int) => createAndStoreRecord(line, creator)

    // and notify the user when we've reached a given level
    val onLevel = (i: Int) => printTime("imported from "+filePath+": "+i+" lines")

    /** @return a State[LogarithmicCounter, IO[Unit]] */
    val readLine = (line: String) => counter.asState(onLevel, onCount(line))

The readLine method is used in a traversal of the lines returned by a FileReader:

    (lines traverseState readLine): State[LogarithmicCounter, Stream[IO[Unit]]]

Pass it an initial counter and you get back a Stream of IO actions which you can then sequence to get an IO[Stream[Unit]]:

    // initial traversal with a function returning a `State`
    val traversed: State[LogarithmicCounter, Stream[IO[Unit]]] = lines traverseState readLine

    // feed in the initial values: count = 1, level = 100 to get the end `State`
    val traversedEndState: Stream[IO[Unit]] = traversed ! new LogarithmicCounter

    // finally get a global action which will execute a stream of
    // record-storing actions and printing actions
    val toStore: IO[Stream[Unit]] = traversedEndState.sequence

Some readers of this blog may recognize one usage of the Essence of the Iterator Pattern - EIP and that's indeed what it is (my first real use case, yes!). traverseState is just a way to use the more traditional traverse method but hiding the ugly type annotations.

This kind of type-directed development is nice. You add some type here and there and you let the compiler guide you to which method to apply in order to get the desired results:

after the traversal I get back a State
if I want to get the final state, the Stream of IO, I need to feed in some initial values, that's the '!' method
if I want to get an action equivalent to the stream of actions, I need the sequence method which has exactly the type signature doing what I want

I was about to call it a day when I actually tried my application,... StackOverflow! What?!?

Trampolining to the rescue

It turns out that traversing a "big" sequence with a State is not so easy. First of all, State is an Applicative because it is also a Monad (please read the earlier EIP post for the details). So basically this amounts to chaining a lot of flatMap operations which blows up the stack.

Fortunately for me, Runar has implemented a generic solution for this kind of issue, like, less than 2 months ago! I leave you to his excellent post for a detailed explanation but the gist of it is to use continuations to describe computations and store them on the heap instead of letting calls happen on the stack. So instead of using State[S, A] I use StateT[Trampoline, S, A] where each computation (S, A) returned by the State monad is actually encapsulated in a Trampoline to be executed on the heap.

The application of this idea was not too easy at first and Runar helped me with a code snippet (thanks!). Eventually I managed to keep everything well hidden behind the traverseState function. The first thing I did was to "trampoline" the function passed to traverseState:

  /**
   * transform a function into its "trampolined" version
   * val f:             T => State[S, A]              = (t: T) => State[S, A]
   * val f_trampolined: T => StateT[Trampoline, S, A] = f.trampolined
   */
  implicit def liftToTrampoline[T, S, A](f: T => State[S, A]) = new LiftToTrampoline(f)

  class LiftToTrampoline[T, S, A](f: T => State[S, A]) {
    def trampolined = (t: T) => stateT((s: S) => suspend(st.apply(s)))
  }

So the traverseState function definition becomes:

  // with the full ugly type annotation
  def traverseState(f: T => State[S, B]) =
    seq.traverse[({type l[a]=StateT[Trampoline, S, a]})#l, B](f.trampolined)

However I can't leave things that like that because traverseState then returns a StateT[Trampoline, S, B] when the client of the function expects a State[S, B]. So I added an untrampolined method to recover a State from a "trampolined" one:

  /** @return a normal State from a "trampolined" one */
  implicit def fromTrampoline[S, A](st: StateT[Trampoline, S, A]) = new FromTrampoline(st)

  class FromTrampoline[S, A](st: StateT[Trampoline, S, A]) {
    def untrampolined: State[S, A] = state((s: S) => st(s).run)
  }

The end result is not so bad. The "trampoline" trick is hidden as an implementation detail and I don't get StackOverflows anymore. Really? Not really,...

The subtleties of `foldRight` and `foldLeft`

I was still getting a StackOverflow error but not in the same place as before (#&$^@!!!). It was in the traversal function itself, not in the chaining of flatMaps. The reason for that one was that the Traverse instance for a Stream in Scalaz is using foldRight (or foldr):

  implicit def StreamTraverse: Traverse[Stream] = new Traverse[Stream] {
    def traverse[F[_]: Applicative, A, B](f: A => F[B], as: Stream[A]): F[Stream[B]] =
      as.foldr[F[Stream[B]]](Stream.empty.pure) { (x, ys) =>
        implicitly[Apply[F]].apply(f(x) map ((a: B) => (b: Stream[B]) => a #:: b), ys)
      }
  }

and foldr is recursively intensive. It basically says: foldRight(n) = f(n, foldRight(n-1)) whereas foldl is implemented with a for loop and a variable to accumulate the result.

The workaround for this situation is simple: just provide a Traverse instance using foldLeft. But then you can wonder: "why is traverse even using foldRight in the first place?". The answer is in my next bug! After doing the modifications above I didn't get a SOE anymore but the output in the console was like:

  imported from test.log: 10000 lines [12:33:30]
  imported from test.log: 1000 lines  [12:33:30]
  imported from test.log: 100 lines   [12:33:30]

Cool, I have invented a Time Machine, Marty! That one left me puzzled for a while but I found the solution if not the explanation. The "left-folding" Traverse instance I had left in scope was being used by the sequence method to transform a Stream[IO] into an IO[Stream]. Changing that to the standard "right-folding" behaviour for a Stream traversal was ok. So there is a difference (meaning that something is not associative somewhere,...)

Conclusion

The main conclusion from this experiment is that tagging methods with IO made me really think about where are the effects of my application. It also encouraged functional programming techniques such as traverse, sequence and al.

I must however say that I was surprised on more than one account:

I stumbled upon a whole new class of bugs: non-execution. My effects were not executed improperly, they were not executed at all because I forgot to call unsafePerformIO!
I was not expecting to be needing an optimisation which had just been added to Scalaz, for something which I thought was a casual traversal
there are still some FP mysteries to me. For example I don't know yet how to traverse a full Stream
I also don't get why my messages were inverted on the console. I tried different experiments, with a Seq instead of a Stream, with Identity or Option as an Applicative instead of IO and I could only reproduce this specific behavior with Stream and IO

Anyway, I would say that it was overall worth using the IO type, at least for the architectural clarification and the better testing. It also brought back the warm, fuzzy feeling that things are under control. On the other hand refactoring to IO took me longer than expected and required more knowledge than just using vars and regular I/O. But that should really be accounted for in the 'investment for the future' column.

PS

There are certainly many stones left unturned in that post for programmers new to Functional Programming and Scalaz. I do apologize for that (this post is certainly long enough :-)) and I encourage those readers to ask questions on the Scalaz mailing-list.

Practical uses for Unboxed Tagged Types

2011-11-11T21:49:00.000+09:00

Another blog post to show that the esoteric type system tricks you read about Haskell or Scala actually have real uses.

Groovy vs Scala for log analysis

These days I'm implementing a non-critical application which deals with:

importing performance log files
parsing them and storing some structured data corresponding to each line
creating some graphs to show the maximum execution times, the cumulated maximum execution times, the events inside a given time range, and so on,...

This, in itself, is a very interesting exercise for me since I had coded a similar application more than 3 years ago in Groovy. After deciding that the Groovy implementation was slow and cumbersome, I decided to give it a go with Scala (and MongoDB for the backend :-)).

I've been really amazed to see that many of the things I learnt for free, on my spare time, were applicable in the case of that application, to yield much better code. This post shows one of these techniques: "Unboxed Tagged Types".

Unboxed what?

Two months ago, I saw this enigmatic tweet by @milessabin. I followed the link, read the code and thought: "oh nice, I see, at least Miles is having fun playing with Scala's type system". But I wasn't really able to see what that thing could be used for.

Then, this week, developing my log analysis application, I became midly annoyed about one specific messy point.

There is time and,... time

The log records I'm getting from the log files are all timestamped with a number of millis which are what Java's Date.getTime returns when you ask for it. That is to say, the number of milliseconds, as a Long, elapsed from January, 1st, 1970, 00:00:00.000 GMT (the so-called EPOCH time by people thinking that the world started in the seventies).

Not very user friendly. Usually you would like to display that as readable date, using the java.text.SimpleDateFormat class for example. So in Scala, you are very tempted to write code like that:

  val hhmmFormat = new SimpleDateFormat("hh:mm")

  implicit def toTimeDisplay(t: Long) = new TimeDisplay(t)

  case class TimeDisplay(time: Long) {
    def hhmm = hhmmFormat.format(new Date(time))
  }

  > val startTime: Long = 12398234093458L
  > startTime.hhmm
  res0: java.lang.String = 12:54

Then you move on, there's so much to do. In particular I wanted to be able to specify a time range to select exactly the events occuring during that time. The most straightforward way to do that is to give a "start time" and an "end time":

   /**
    * DaytimeRange(0, 2*60*60*1000) is 00:00 -> 02:00
    */
   case class DaytimeRange(start: Long, end: Long)

Here starts the ugliness. When I want to check if a startTime given by the log file is included in the DaytimeRange I have to do a conversion to make sure I'm using the proper Longs: the number of milliseconds since the start of the day, not the milliseconds since the EPOCH time!

Similarly, if I blindly try to reuse the hhmm method defined above, I need to make sure I apply that to a number of milliseconds corresponding to an EPOCH time and not just since the beginning of the day.

That's the recipe for disaster,...

Twitter forever

Fortunately the answer was right there, in my Twitter timeline (well in my memory of the timeline to be more precise :-)): use "Unboxed newtypes".

It all fits in a few lines of code but makes everything incredibly clear. First we define "Tagged types":

  type Tagged[U] = { type Tag = U }
  type @@[T, U] = T with Tagged[U]

Then we declare that there are 2 different types of time:

  trait Day
  trait Epoch

And we declare that a given Long will either represent the number of millis since 1970 or since the beginning of the day:

  type Epochtime = Long @@ Epoch
  type Daytime   = Long @@ Day

Daytime simply means that we have a Long value, with an additional Day type.

Finally, we provide 2 functions to create instances of those types from Longs:

  def daytime(i: java.lang.Long): Daytime     = i.asInstanceOf[Daytime]
  def epochtime(i: java.lang.Long): Epochtime = i.asInstanceOf[Epochtime]

with a method which explicitly converts EPOCH millis to "day" millis:

  def epochtimeToDaytime(time: Long): Daytime = {
    val calendar = Calendar.getInstance
    calendar.setTime(new Date(time))
    daytime(((calendar.get(HOUR_OF_DAY)* 60 +
              calendar.get(MINUTE))    * 60 +
              calendar.get(SECOND))    * 1000 +
              calendar.get(MILLISECOND))
  }

Using the new toys

We can use the Daytime type for our DaytimeRange class:

  case class DaytimeRange(start: Daytime, end: Daytime)

There's no risk that we now accidentally create a DaytimeRange instance with Longs which do not represent elapsed millis since the beginning of the day. The compiler reminds us to write code like:

  /** @return the number of millis from a string representing hours and minutes */
  def hhmmToDaytime(s: String): Daytime = ...

  DaytimeRange(hhmmToDaytime("10:00"), hhmmToDaytime("10:20"))

And if we want to create a DaytimeRange instance from 2 startTimes found in the log file:

  DaytimeRange(epochtimeToDaytime(s1), epochtimeToDaytime(s2))

Similarly, we can use the Epochtime for the hhmm display

  implicit def toEpochtimeDisplay(t: Epochtime) = new EpochtimeDisplay(t)

  case class EpochtimeDisplay(time: Epochtime) {
    // here new Date expects a Long, but this is ok because Epochtime *is* a Long
    def hhmm = hhmmFormat.format(new Date(time))
  }

We can safely reuse this code to display a DaytimeRange instance:

  case class DaytimeRange(start: Daytime, end: Daytime) {

    // the developer *has* to think about which kind of time he's handling
    def show = daytimeToEpochtime(start).hhmm + " -> " + daytimeToEpochtime(end).hhmm

  }

Final comments

It's practical

This technique is very pratical because it avoids making silly mistakes with Longs representing different concepts while still keeping the ability to use them as Long objects without having to "Unbox" them. Indeed we could also have created a case class like:

  case class Daytime(time: Long)

But then we would have had to "unbox" the time value everytime we wanted to do an addition or a comparison.

WTF?

I had a compiler puzzler when with my first implementation:

  case class DaytimeRange(start: Daytime, end: Daytime)
             ^
  found   : Double
  required: AnyRef

  Note: an implicit exists from scala.Double => java.lang.Double, but methods inherited from Object are
  rendered ambiguous.  This is to avoid a blanket implicit which would convert any scala.Double to any AnyRef.
  You may wish to use a type ascription: `x: java.lang.Double`.

Go figure what that means in this context,... After much head scratching, I found a workaround:

  type Epochtime = java.lang.Long @@ Epoch
  type Daytime   = java.lang.Long @@ Day

  def daytime(i: java.lang.Long): Daytime     = i.asInstanceOf[Daytime]
  def epochtime(i: java.lang.Long): Epochtime = i.asInstanceOf[Epochtime]

I used java.lang.Long instead of scala.Long because it looks like we need to get AnyRef objects while scala.Long is only AnyVal. But the compiler message is still very obscure in that case.

This is not a unit system!

Because Epochtime and Daytime are still Longs, it is still possible to add them and make a mess!

Kudos to @retronym too

You'll see that Unboxed Tagged Types are also part of the next scalaz7. Jason came up with the @@ type alias and is using the tag types to distinguish "multiplicative" monoids from "additive" monoids. Or conjonctive vs disjonctive. This means that given a Monoid[Boolean], we can specify if it does an AND or if it does an OR. Scalaz is becoming the ultimate toolbox,...

Scala collections are awesome

2011-10-26T07:45:00.001+09:00

This is just a small post to show how incredibly easy it is to use scala concurrency constructs to speed-up your work.

Doing the job

This question occured to me as a new enhancement was requested for specs2. In specs2, the processing of examples was very sequential:

all the examples are executed concurrently
then they are reported to the console

The concurrent execution of examples makes it generally fast enough that the reporting appears fast on the screen. However, if examples take a long time to execute, you might think that sbt is stuck with nothing whatsoever being reported back to you. You might even think that the compilation is still going on!

I changed that in specs2 and now the examples are reported as soon as they are executed. But I also thought: "this question must happen all the time, for all sorts of tasks". This is why I'm going to demonstrate how straightforward it is to speed-up your computations or your scripts with just a few annotations and imports.

Let's say I have some jobs to execute, each of them taking a random time:

  def job(i: Int) = {
    Thread.sleep(50 * random.nextInt(i))
    println("executed "+i)
    i
  }

And I have a function to report the results:

  def report(i: Int) = println("  reported "+i)

Naively

The naive approach for executing and reporting the jobs would be:

  def naive(n: Int) = (1 to n).map(job).foreach(report)

  scala>naive(3)
  executed 1
  executed 2
  executed 3
    reported 1
    reported 2
    reported 3

Unfortunately this is slow since all the jobs are executed in sequence, then reported.

Wrongly

If we want to make a better use of our laptop's cores, we can write:

  def parallel(n: Int) = (1 to n).par.map(job).foreach(report)

This is better, because now the jobs are executed in parallel, but not satisfying because the reporting now comes out of order:

  scala>parallel(3)
  executed 3
  executed 1
  executed 2
    reported 3
    reported 1
    reported 2

Fast and right

The trick to have best of both worlds is to use futures and seq:

  import actors._
  import Futures._

  def best(n: Int) = (1 to n).par.map(future(job)).seq.foreach(f => report(f()))

In the code above, we execute concurrently each job in a Future. Then we force the collection to be evaluated sequentially again with seq and we report each result with f(), using the Future.apply method to wait until the value is available:

  scala>best(3)
  executed 3
  executed 1
    reported 1
  executed 2
    reported 2
    reported 3

Conclusion

With a few minor modifications to the first code version we managed to do exactly what we wanted. Having this kind of power in the toolbox feels great, and I hope this post contributes a bit more to showing that Scala is also a practical language (because there's nothing wrong with being academic :-)).

Update

Before I get flamed down in the comments, here an interesting update :-).

As soon as I published this post, I started wondering if the best behavior had anything to do with parallel collections at all. It turns out that using futures only gives good results as well:

  def futures(n: Int) = (1 to n).map(future(job)).foreach(f => report(f()))

  scala>futures(3)
  executed 2
  executed 1
    reported 1
  executed 3
    reported 2
    reported 3

However, if the input collection is a view, the results are completely different:

  def futures(n: Int) = (1 to n).view.map(future(job)).foreach(f => report(f()))

  scala>futures(3)
  executed 1
    reported 1
  executed 2
    reported 2
  executed 3
    reported 3

Hence the use of par is really necessary, in this scenario, to get a fully parallel execution.

Counting words - part 2

2011-10-12T08:49:00.000+09:00

In this small post, I'm going to show how I used Functional Reactive Programming (FRP) to improve the GUI part of the small application presented in the previous post.

The best article to read on the subject is Deprecating the Observer Pattern (DOP). This article explains what are the drawbacks of using a listener-based approach to components communication in a user interface and proposes FRP as an alternative.

Be reactive

What I've been using is a simplified yet powerful version of the code described in DOP, using the Reactive library by Naftoli Gugenheim. In this library you have 2 essential concepts: EventStreams and Signals:

EventStream[T] is a collection of values of type T happening at certain moments in time
Signal[T] is a value of type T which can change from time to time

They are actually 2 sides of the same coin (more or less) as explained in this video: from an EventStream you can get a Signal by holding the last emitted value and from a Signal you can get an EventStream by getting all the changes.

The great thing about an EventStream (let's focus on that one for now) is that you can manipulate it like a collection of objects:

you can filter it to get only the events you're interested in
you can map the events to other events
you can flatMap with a function returning another EventStream and so on,...

But how is this helpful for GUI programming?

With GUI components

The hard reality of Swing GUI components is that they are really mutable at heart. Once you compose a GUI with components (say a Frame) containing other components (say a TextField), then, when anything happens in your application, you mutate the innermost components heavily (by changing the text color for example). When you add publish/subscribe mechanisms on top of that, you add even more developer-managed mutability since you need to add-remove listeners to the whole graph of components. It is also not very easy to understand how events "flow" between components.

The way I see the usage of FRP with GUIs is:

components are seen as either creating values to propagate (like a button action) or consuming values (like a text field change with the new value). Hence they have a role of an EventStream source or of an EventStream sink (sometimes both)
those components explicitely declare the abstract type of streamed events they're expecting. For a given TextField this might be something like NewSelectedFile whether the selection comes from a FileChooser or from a simple TextField
the event streams can be merged, filtered, mapped functionally, with no side-effect so that the logic of events routing is very composable and explicit

Let's see that more precisely in the context of my simple application.

An example

In my WordCount application, the first thing the user does is to select a file to count. Then she is supposed to click on the "Count" button to start the count before the results are displayed. In terms of graphical components I have:

    val openFileMenuItem = OpenFileMenuItem("./src/test/resources")
    val countAction      = CountAction()

What you don't see above is that those 2 custom GUI components have been declared as extending EventStream[T] (simplified code for the explanation):

    OpenFileMenuItem ... with EventStream[File]
    CountAction      ... with EventStream[Unit]

This means that when you open a file using the OpenFileMenuItem you're providing new File events which other components can react on, and when you invoke the CountAction you, well,... you just pressed the button, there's no meaningful value to convey, so the Unit type is appropriate here (the clients just want to know that something happened).

Then we can compose those 2 EventStreams:

  val filePath: Signal[String]  = openFileMenuItem.map(_.getPath).hold("")
  val doCount: EventStream[Any] = filePath.distinct.change | countAction

First we do a bit of filtering, because we just need the file path as a Signal[String] (using hold to transform the stream to a signal, with an empty initial value).
Then we declare that we need to do a count whether there's a distinct change in the file path value, or (|), if the user pressed countAction button.

How do we "consume" this doCount stream of events? We flatMap it to another stream of events providing the results of the counting:

 val results: EventStream[Results] =
   doCount flatMap { doIt => WordCounter.count(filePath.now).inBackground }

For each doCount event we flatMap it (actually we forget about it,...) and we use the current value of the filePath to count the number of words.

The expression computeValue.inBackground computes a value using the SwingUtils.invokeLater method to avoid computations being done on the event dispatch thread (this might cause grey screens). The inBackground method returns an EventStream[T] to signal consumers that the value is ready.

Since the result of counting is an EventStream[Results] I can then "plug" it into the GUI component doing the display:

  val resultsPanel = ResultsPanel(results)

And that's it. The ResultsPanel component doesn't care where the values come from, who created them. It is also interesting to see how the ResultsPanel declares its sub-components:

  object ResultsPanel {
    def apply(results: EventStream[Results]) = {
      new ResultsPanel(TotalWordsNumbers(results),
                       ReferencesTable(results.map(_.references)),
                       ErrorMessageBox(results.map(_.message)))
    }
  }

There are 3 sub-components and they use different parts of the Results event stream, so we use the map function to restrict exactly the stream to what is needed:

TotalWordsNumbers uses the full Results object to display the total words count (the one we really want), the references word count and the full text word count (to check that the count is ok)
ReferencesTable just needs the references
ErrorMessageBox needs the error message so we just map that

Finally, how is the event stream used in the component itself? Let's look at the ErrorMessageBox component:

  case class ErrorMessageBox(message: EventStream[String]) extends TextField with Observing {
    foreground = Color.red
    font = new Font("Courier", Font.PLAIN, 15);
    editable = false

    message.foreach { m => text = m }
  }

The important line is the last one where we declare that for each message event, we change the text attribute of the TextField to the new value m.

Some implementation notes

If you read the actual code, you'll find quite a few differences with the real implementation:

the inBackground mechanism is enhanced with an additional actionProgress eventStream which fires events before and after the action to execute. This is used to change the main frame cursor to a waiting watch when the computation takes some time
I found useful to introduce a trait called Trigger for EventStream[()]

I also added an EventStreamSourceProxy[T] extends EventStream[T] trait which can be mixed in any GUI class. This trait uses an internal EventSource[T] which is the implementation of the EventStream[T] and can be used to fire events. For example:

// When the action is executed (a file is selected) we fire an event and
// the whole `OpenFileMenuItem` component acts as an `EventStream[File]`.
case class OpenFileMenuItem(start: String) extends MenuItem("Open") with EventStreamSourceProxy[File] {
  ...
  action = new Action("Open") {
    def apply() {
      ...
      source.fire(fileChooser.selectedFile)
    }
  }
}

I had some difficult debugging time with the Observing trait. If you place it on an object that's going to be garbage collected, your components will not be notified of new events. This happened to me as I placed it on a class used for an implicit conversion, in order to get a new shinyMethod (tm):
```
implicit def toComponent(a: A): ImplicitComponent = new ImplicitComponent(a)
class ImplicitComponent(a: A) extends Observing {
  def shinyMethod = a
}
```

Features ideas

This is something which amazed me: just having to think about event streams made me rethink the application functionalities. How? When I started thinking about what would trigger a word count I realized that:

there is no reason why the user should have to click the "Count" button when the file is selected, we can do the count and display the results right away
thinking about event stream as a flux made me realize that the file can be polled regularly for changes and the results displayed whenever there's a change

Changing my program to incorporate those 2 ideas was soooo easy:

the first idea is reflected by the doCount event stream definition given above, we just say that we want to count whenever there's a file selection or a count action
```
val doCount: EventStream[Any] = filePath.distinct.change | countAction
```

creating a file poller is easy using the Timer class from the reactive library

class FilePoller(path: Signal[String], delay: Long = 500) extends Trigger {

  private var previousLastModified = new File(path.now).lastModified()

  val timer = new Timer(0, delay, {t => false}) foreach { tick =>
    def newLastModified = new File(path.now).lastModified()
    if (newLastModified > previousLastModified || newLastModified == 0) {
      previousLastModified = newLastModified
      source.fire(())
    }
  }
}

The `FilePoller` uses a `path` signal regularly. If the underlying file is modified, a notification event is triggered.

then the final version of doCount becomes:

lazy val filePoller                = new FilePoller(filePath)
lazy val doCount: EventStream[Any] = filePath.distinct.change | countAction | filePoller

I don't know about you but I really find nice that the abstractions in my implementation give me hints about what the application could do! For me this is a good sign that FRP is really well-suited for the job of GUI programming.

Counting words

2011-10-11T16:47:00.000+09:00

In this 3 parts post I want to show:

how standard, out-of-the-box, Scala helped me to code a small application
how Functional Reactive Programming brings a real improvement on how the GUI is built
how to replace Parser Combinators with the Parboiled library to enhance error reporting

You can access the application project via github.

I can do that in 2 hours!

That's more or less what I told my wife as she was explaining one small problem she had. My wife is studying psychology and she has lots of essays to write, week after week. One small burden she's facing is keeping track of the number of words she writes because each essay must fit in a specific number of words, say 4000 +/- 10%. The difficulty is that quotations and references must not be counted. So she cannot check the file properties in Word or Open Office and she has to keep track manually.

For example, she may write: "... as suggested by the Interpretation of Dreams (Freud, 1905, p.145) ...". The reference "(Freud, 1905, p.145)" must not be counted. Or, "Margaret Malher wrote: "if the infant has an optimal experience of the symbiotic union with the mother, then the infant can make a smooth psychological differentiation from the mother to a further psychological expansion beyond the symbiotic state." (Malher cited in St. Clair, 2004, p.92)" (good luck with that :-)). In that case the quotation is not counted either and we must only count 3 words.

Since this counting is a bit tedious and has to be adjusted each time she does a revision of her essay, I proposed to automate this check. I thought "a few lines of Parser Combinators should be able to do the trick, 2 hours max". It actually took me a bit more (tm) to:

write a parser robust enough to accommodate for all sorts of variations and irregularities. For example, pages can be written as "p.154" or "pp.154-155", years can also be written "[1905] 1962" where 1905 is the first edition, and so on
use scala-swing to display the results: number of words, references table, file selection
write readers to extract the text from .docx or .odt files

Let's see now how Scala helped me with those 3 tasks.

Parsing the text

The idea behind parser combinators is very powerful. Instead of building a monolithic parser with lots of sub-routines and error-prone tracking of character indices, you describe the grammar of the text to parse by combining smaller parsers in many different ways.

In Scala, to do this, you need to extend one of the Parsers traits. The one I've choosen is RegexParsers. This is a parser which is well suited for unstructured text. If you were to parse something more akin to a programming language you might prefer StdTokenParsers which already define keywords, numeric/string literals, identifiers,...

I'm now just going to comment on a few points regarding the TextParsing trait which is parsing the essay text. If you want to understand how parser combinators work in detail, please read the excellent blog post by Daniel Spiewak: The Magic behind Parser Combinators.

The main definition for this parser is:

  def referencedText: Parser[Results] =
    rep((references | noRefParenthesised | quotation | words | space) <~ opt(punctuation)) ^^ reduceResults

This means that I expect the text to be:

a repetition (the rep combinator) of a parser
the repeated parser is an alternation (written |) of references, parenthetised text, quotations, words or spaces. For each of these "blocks" I'm able to count the number of words. For example, a reference will be 0 and parenthetised text will be the number of words between the parentheses
there can be a following punctuation sign (optional, using the opt combinator), but we don't really care about it, so it can be discarded (hence the <~ combinator, instead of ~ which sequences 2 parsers)

Then I have a function called reduceResults taking the result of the parsing of each repeated parser, to create the final Result, which is a case class providing:

the number of counted words
the references in the text
the quotations in the text

Using the RegexParser trait is very convenient. For example, if I want to specify how to parse "Pages" in a reference: (Freud, 1905, p.154), I can sequence 2 parsers built from regular expressions:

  val page = "p\\.*\\s*".r ~ "\\d+".r

appending .r to a string returns a regular expression (of type Regex)
there is an implicit conversion method in the RegexParsers trait, called regex from a Regex to a Parser[String]
I can sequence 2 parsers using the ~ operator

The page parser above can recognize page numbers like p.134 or p.1 but it will also accept p134. You can argue that this is not very well formatted, and my wife will agree with you. However she certainly doesn't want to see the count of words being wrong or fail just because she forgot a dot! The plan here is to display what was parsed so that she can eventually fix some incorrect references, not written according to the academia standards. We'll see, in part 3 of this series how we can use another parsing library to manage those errors, without breaking the parsing.

One more important thing to mention about the use of the RegexParsers trait is the skipWhitespace method. If it returns true (the default), any regex parser will discard space before any string matching a regular expression. This is convenient most of the time but not here where I need to preserve spaces to be able to count words accurately.

To finish with the subject of Parsing you can have a look at the TextParsingSpec specification. This specification features a ParserMatchers trait to help with testing your parsers. It also uses the Auto-Examples feature of specs2 to use the text of the example directly as a description:

  "Pages"                                                                           ^
  { page must succeedOn("p.33") }                                                   ^
  { page must succeedOn("p33") }                                                    ^
  { pages must succeedOn("pp.215-324") }                                            ^
  { pages must succeedOn("pp.215/324") }                                            ^
  { pages("pp. 215/324") must haveSuccessResult(===(Pages("pp. 215/324"))) }        ^

Displaying the results

The next big chunk of this application is a Swing GUI. The Scala standard distribution provides a scala-swing library adding some syntactic sugar on top of regular Swing components. If you want to read more about Scala and Swing you can have a look at this presentation.

The main components of my application are:

a menu bar with 2 buttons to: select a file, do the count
a field to display the currently selected file
a results panel showing: the number of counted words and the document references

count example, note that the parsing is not perfect since the word counts do not add up!

If you have a look at the code you will see that this translates to:

an instance of SimpleSwingApplication defining a top method and including all the embedded components: a menu bar, a panel with the selected file and results
the subcomponents themselves: the menu items, the count action, the results panel
the "reactions" which is a PartialFunction listening to the events created by some components, SelectionChanged for example, and triggering the count or displaying the results

I was pretty happy to see that much of the verbosity of Swing programming is reduced with Scala:

you don't need to create xxxListeners for everything
there are components providing both a Panel and a LayoutManager with the appropriate syntax to display the components: FlowPanel, BoxPanel, BorderPanel
thanks to scala syntax you can write action = new Action(...) instead of setAction(new Action(...))

This is nice but I think that there is a some potential for pushing this way further and create more reusable out-of-the-box components. For example, I've created an OpenFileMenuItem which is a MenuItem with an Action to open a FileChooser. Also, something like a pervasive LabeledField with just a label and some text would very useful to have in a standard library.

I also added a bit of syntactic sugar to have actions executed on a worker thread, instead of the event dispatch thread (to avoid grey screens), using the SwingUtilities.invokeLater method. For example: myAction.inBackground will be executed on a separate thread.

Eventually, I was able to code up the GUI of the application pretty fast. The only thing which I didn't really like was the Publish/React pattern. It felt a bit messy. The next part of this series will show how Functional Reactive Programming with the reactive library helped me write cleaner code.

Reading the file

I anticipated this part to be a tad difficult. My first experiments of text parsing were using a simple text file and I knew that having the user (my wife, remember,...) copy and paste her text to another file just for counting would be a deal-breaker. So I tried to read .odt and .docx files directly. This was actually much easier than anything I expected!

Both formats are zipped xml files. Getting the content of those files is just a matter of:

reading the ZipFile entries and find the file containing the text

val rootzip = new ZipFile(doc.path)
rootzip.entries.find(_.getName.equals("word/document.xml"))

loading the xml as a NodeSeq
```
XML.load(rootzip.getInputStream(f)))
```

find the nodes containing the actual text of the document and transform them to text

// for a Word document text is under <p><t> tags
(xml \\ "p") map (p => (p \\ "t").map(_.text) mkString "") mkString "\n"

For further details you can read the code here.

Recap

That's it, parser combinators + scala-swing + xml = a quick app solving a real-world problem. In the next posts we'll try to make this even better!

The Essence of the Iterator Pattern

2011-06-24T16:53:00.018+09:00

"The Essence of the Iterator Pattern"(EIP) is the paper I liked the most last year. It gave me a brand new look over something which I had be using for years: the for loop.

In this post I'll try to present some ideas of that paper and show how to implement the solution described by the authors using Scalaz-like code. A minimum previous exposure to functional programming, functors and monads will definitely help!

What's in a for loop?

That was really what hooked me. What do you mean "what's in a for loop"?. Is there anything magic in that construct I've been using for years?

The introduction of EIP shows an example of a for loop to iterate on elements (not the C-like for used with an index). I'm transmogrifying it here to Scala but the idea remains the same:

  val basket: Basket[Fruit] = Basket(orange, apple)
  var count = 0

  val juices = Basket[Juice]()
  for (fruit <- basket) {
    count = count + 1
    juices.add(fruit.press)
  }

We start from a "container" of fruits: Basket. It could actually be anything, a List, a Tree, a Map... Then the for loop actually does 3 things:

it returns a container having the same "shape"; juices is still a Basket
it accumulates some kind of measure. Here, the number of fruits in the count variable
it maps the elements to other elements: pressing the fruits to get some juice

And this for loop is actually not the most complex:

the count variable could influence the mapping of elements: juices.add(fruit.press(harder=count))
we could have several variables depending on each other: cumulative = cumulative + count
the mapping could also influence a "measure" variable: liquid = liquid + fruit.press.quantity

The purpose of EIP is to show that the "essence" of what happens in the for loop above can be abstracted by an Applicative Traversal. And the authors go on showing that given this Applicative abstraction, we get an incredible modularity for programming.

The Applicative typeclass

How can an Applicative traversal be better than a for loop, and what does that even mean?? EIP has a lot of sentences and expressions which can be hard to grasp if you don't have a strong functional programming / Haskell background. Let's try to dissect that slowly and start with the formal definitions anyway.

What is a Functor?

The first thing we need to talk about is the Functor typeclass:

  trait Functor[F[_]] {
    def fmap[A, B](f: A => B): F[A] => F[B]
  }

One way of interpreting a Functor is to describe it as a computation of values of type A. For example List[A] is a computation returning several values of type A (non-deterministic computation), Option[A] is for computations that you may or may not have, Future[A] is a computation of a value of type A that you will get later, and so on. Another way of picturing it is as some kind of "container" for values of type A.

Saying that those computations are Functors is essentially showing that we can have a very useful way of combining them with regular functions. We can apply a function to the value that is being computed. Given a value F[A] and a function f, we can apply that function to the value with fmap. For example, fmap is a simple map for a List or an Option.

Pointed Functor

By the way, how do you even create a value of type F[A]? One way to do that is to say that F[_] is Pointed:

  trait Pointed[F[_]] {
    def point[A](a: => A): F[A]
  }

That is, there is a point function taking a value of type A and returning a F[A]. For example, a regular List is Pointed just by using the constructor for Lists:

  object PointedList extends Pointed[List] {
    def point[A](a: => A) = List(a)
  }

Then combining the 2 capabilities, pointed and functor, gives you a PointedFunctor:

  trait PointedFunctor[F[_]] {
    val functor: Functor[F]
    val pointed: Pointed[F]

    def point[A](a: => A): F[A] = pointed.point(a)

    def fmap[A, B](f: A => B): F[A] => F[B] = functor.fmap(f)
  }

The PointedFunctor trait is merely the aggregation of a Pointed and a Functor.

What about Applicative then? We're getting to it, the last missing piece is Applic.

Applic

Applic is another way to combine a "container" with a function.

Instead of using fmap to apply the function to the computed value we suppose that the function is itself a computed value inside the container F (F[A => B]) and we provide a method applic to apply that function to a value F[A]:

  trait Applic[F[_]] {
    def applic[A, B](f: F[A => B]): F[A] => F[B]
  }

Let's take an example. Say I have a way to compute the price of a Fruit when the market is open:

  def pricer(market: Market): Option[Fruit => Double]

If the market is closed, pricer returns None, because we don't know what are the prices. Otherwise it returns a pricing function. Now if I have a grow function possibly returning a Fruit:

  def grow: Option[Fruit]

Then, using the Applic instance, you can price the Fruit:

  val price: Option[Double] = applic(pricer(market)).apply(grow)

The price will necessarily be an Option because you may not have a pricer nor a Fruit to price. And a bit of renaming and pimping reveals why we're using the term "Applicative":

  val pricingFunction = pricer(market)
  val fruit = grow

  val price: Option[Double] = pricingFunction ⊛ fruit

In a way we're just doing a normal function application, but we're just doing it inside the Applicative container. Now we have all the pieces to build the Applicative functor that EIP is talking about.

Applicative Functor

An Applicative Functor is the aggregation of an Applic and a PointedFunctor:

  trait Applicative[F[_]] {
    val pointedFunctor: PointedFunctor[F]
    val applic: Applic[F]

    def functor: Functor[F] = new Functor[F] { 
      def fmap[A, B](f: A => B) = pointedFunctor fmap f 
    }
    def pointed: Pointed[F] = new Pointed[F] { 
      def point[A](a: => A) = pointedFunctor point a 
    }

    def fmap[A, B](f: A => B): F[A] => F[B]     = functor.fmap(f)
    def point[A](a: => A): F[A]                 = pointed.point(a)
    def apply[A, B](f: F[A => B]): F[A] => F[B] = applic.applic(f)
  }

Let's see how that can be implemented for a List. fmap and point are straightforward:

   def fmap[A, B](f: A => B): F[A] => F[B] = (l: List[A]) => l map f
   def point[A](a: => A): F[A]             = List(a)

apply turns out to be more interesting because there are 2 ways to implement it, both of them being useful:

apply a list of functions to each element and gather the results in a List:

def apply[A, B](f: F[A => B]): F[A] => F[B] = (l: List[A]) =>
 for { a <- l; func <- f } yield func(a)

zip the list of functions to the list of elements to apply each function to each element

def apply[A, B](f: F[A => B]): F[A] => F[B] = (l: List[A]) =>
 (l zip f) map (p => p._2 apply p._1)

There is even a third way to use List as an Applicative by using the fact that List is a Monoid. But more on that later, for now we still have to see how all of this relates to the for loop...

Traversing the structure

When we do a for loop, we take a "structure" containing some elements and we "traverse" it to return:

that same structure containing other elements
a value computed from the structure elements
some combination of above

Gibbons & Oliveira argue that any kind of for loop can be represented as the following traverse operation:

  trait Traversable[T[_]] {
    def traverse[F[_] : Applicative, A, B](f: A => F[B]): T[A] => F[T[B]]
  }

That is, if the container/structure of type T has this traverse function using an Applicative F, then we can do whatever we would do with a for loop on it.

To get a better feel for this traverse function, we're going to implement the Traversable trait for a binary tree and then we'll see how can we loop on that tree.

A Binary Tree

For all the other examples in this post, we're going to use a very simple binary tree:

  sealed trait BinaryTree[A]
  case class Leaf[A](a: A) extends BinaryTree[A]
  case class Bin[A](left: BinaryTree[A], right: BinaryTree[A]) extends BinaryTree[A]

On the other hand, the first shot at the Traversable implementation is barely readable!

 def BinaryTreeIsTraversable[A]: Traversable[BinaryTree] = new Traversable[BinaryTree] {

   def createLeaf[B] = (n: B) => (Leaf(n): (BinaryTree[B]))
   def createBin[B]  = (nl: BinaryTree[B]) => 
     (nr: BinaryTree[B]) => (Bin(nl, nr): BinaryTree[B])

   def traverse[F[_] : Applicative, A, B](f: A => F[B]): 
     BinaryTree[A] => F[BinaryTree[B]] = (t: BinaryTree[A]) => {
     val applicative = implicitly[Applicative[F]]
     t match {
       case Leaf(a)   => applicative.apply(applicative.point(createLeaf[B]))(f(a))
       case Bin(l, r) =>
         applicative.apply(applicative.apply(applicative.point(createBin[B]))(traverse[F, A, B](f).apply(l))).
         apply(traverse[F, A, B](f).apply(r))
     }
   }
 }

This is a shame because the corresponding Haskell code is so concise:

  instance Traversable Tree where
  traverse f (Leaf x)  = pure Leaf ⊛ f x
  traverse f (Bin t u) = pure Bin  ⊛ traverse f t ⊛ traverse f u

A bit of pimping to the rescue and we can improve the situation:

def traverse[F[_] : Applicative, A, B](f: A => F[B]): BinaryTree[A] => F[BinaryTree[B]] = (t: BinaryTree[A]) => {
  t match {
    case Leaf(a)   => createLeaf[B] ∘ f(a)
    case Bin(l, r) => createBin[B]  ∘ (l traverse f) <*> (r traverse f)
  }
}

Informally the traverse method applies the function f to each node and "reconstructs" the tree by using the apply method (<*>) of the Applicative functor.

That's certainly still some Ancient Chinese to you (as it was for me) so we'd better see the traverse method at work now. But we need to take another detour :-)

Applicative Monoid

One simple thing we might want to do, when iterating on a BinaryTree, is to get the content of that tree in a List. To do that, we're going to use the 3rd way to use List as an Applicative, as mentioned earlier. It turns out indeed that any Monoid gives rise to an Applicative instance but in a way that's a bit surprising.

  /** Const is a container for values of type A, with a "phantom" type B */
 case class Const[A, +B](value: A)

 implicit def ConstIsPointed[M : Monoid] = new Pointed[({type l[A]=Const[M, A]})#l] {
   def point[A](a: => A) = Const[M, A](implicitly[Monoid[M]].z)
 }

 implicit def ConstIsFunctor[M : Monoid] = new Functor[({type l[A]=Const[M, A]})#l] {
   def fmap[A, B](f: A => B) = (c: Const[M, A]) => Const[M, B](c.value)
 }

 implicit def ConstIsApplic[M : Monoid] = new Applic[({type l[A]=Const[M, A]})#l] {
   def applic[A, B](f: Const[M, A => B]) = (c: Const[M, A]) => Const[M, B](implicitly[Monoid[M]].append(f.value, c.value))
 }

 implicit def ConstIsPointedFunctor[M : Monoid] = new PointedFunctor[({type l[A]=Const[M, A]})#l] {
   val functor = Functor.ConstIsFunctor
   val pointed = Pointed.ConstIsPointed
 }

 implicit def ConstIsApplicative[M : Monoid] = new Applicative[({type l[A]=Const[M, A]})#l] {
   val pointedFunctor = PointedFunctor.ConstIsPointedFunctor
   val applic = Applic.ConstIsApplic
 }

In the code above, Const is the Applicative instance for a given Monoid. Const contains values of type T where T is a Monoid and we progressively establish what are the properties that Const must satisfy to be Applicative.

it must first be Pointed. Informally, the point method puts the neutral element of the Monoid in a Const instance
then it must be a Functor. Here the fmap function doesn't do anything but changing the type of Const from Const[M, A] to Const[M, B]
finally it must be an Applic where the apply method of Applic uses the append method of the Monoid to "add" 2 values and return the result in a Const instance.

There is unfortunately a lot of typing vodoo thing here:

the type declaration for Const is Const[A, +B]. It has a type parameter B which is actually not represented by a value in the Const class! It is a phantom type. But it is actually indispensable to match the type declarations of the typeclasses
the type F that is supposed to be Applicative is... ({type l[A] = Const[T, A]})#l. Ouch, this deserves some explanation!

What we want is not so hard. The type Const[A, B] has 2 type parameters. We need a way to fix A to be T and get the resulting type which will have only one type parameter. The expression above is the most concise way to get this desired type:

{ type l = SomeType } is an anonymous type with a type member called l. We can access that type l in Scala by using #: { type l = SomeType }#l
Then, in { type l[A] = SomeType[T, A] }#l, l is a higher-kinded type, having a type variable A (actually SomeType[T, A] where T is fixed)

That was a really long detour for a mere for loop, isn't it? Now... profit!

Contents of a BinaryTree...

We're going to use the Traversable instance for the BinaryTree and the List Monoid Applicative to get the contents of a BinaryTree:

  import Applicative._

  val f    = (i: Int) => List(i)
  val tree = Bin(Leaf(1), Leaf(2))

  (tree.traverse[...](f)).value must_== List(1, 2)

Simple, for each element of the tree, we put it in a List then we let the List Monoid do its magic and aggregate all the results as we traverse the tree. The only difficulty here is the limits of Scala type inference. The ... stands for type annotations that the compiler requires:

  tree.traverse[Int, ({type l[A]=Const[List[Int], A]})#l](f)

Not pretty :-(

Update: As pointed out by Ittay Dror in the comments, List[Int] is not an applicative by itself and we need to put this list into a Const value to make it usable by the traverse function.

This is actually done by an implicit conversion method, liftConst, provided by the Applicative object:

  implicit def liftConst[A, B, M : Monoid](f: A => M): A => Const[M, B] = 
     (a: A) => Const[M, B](f(a))

Profit time

Not everything is lost! We can encapsulate a bit the complexity in this case. We can extract part of the code above and create a contents method which will work on any of Traversable instance (assume I'm pimping the following examples so that I can write tree.method instead of method(tree)):

  val tree: BinaryTree[Int] = Bin(Leaf(1), Leaf(2))
  tree.contents must_== List(1, 2)

This is based on the following definition:

  def contents[A]: T[A] => List[A] = {
    val f = (a: A) => Const[List[A], Any](List(a))
    (ta: T[A]) => traverse[({type l[U]=Const[List[A], U]})#l, A, Any](f).apply(ta).value
  }

It also turns out that the contents function is a specialized version of something even more generic, the reduce function, working with any Monoid:

  def contents[A]: T[A] => List[A] = reduce((a: A) => List(a))

  def reduce[A, M : Monoid](reducer: A => M): T[A] => M = {
    val f = (a: A) => Const[M, Any](reducer(a))
    (ta: T[A]) => traverse[({type l[A]=Const[M, A]})#l, A, Any](f).apply(ta).value
  }

The reduce function can traverse any Traversable structure with a function mapping each element to a Monoid element. We've used it to get the contents of the tree but can as easily get the number of elements:

  def count[A]: T[A] => Int = reduce((a: A) => 1)

  tree.count must_== 2

Can it get simpler than this :-)? Actually in that case it can! Since we don't need (a: A) at all we can use reduceConst:

  def reduceConst[A, M : Monoid](m: M): T[A] => M = reduce((a: A) => m)

  def count[A]: T[A] => Int = reduceConst(1)

It's like a Scala standard reduce on steroids because instead you don't need to provide a binary operation, you just need a Monoid instance.

.... and shape of a BinaryTree

We've addressed the question of doing some kind of accumulation based on the elements in the tree, now we're going to "map" them.

Monads are Applicatives too!

The following map method can be derived from the traverse method (note that no type annotations are necessary in that case, yes!):

  def map[A, B](mapper: A => B) = (ta: T[A]) => traverse((a: A) => Ident(mapper(a))).apply(ta).value

Here we're traversing with an Applicative which is very simple, the Ident class:

  case class Ident[A](value: A)

The Ident class is a simple wrapper around a value, nothing more. That simple class is an Applicative. But how?

Easy. Ident is actually a Monad and we can construct an Applicative instance from every Monad. This comes from the fact that a Monad is both a PointedFunctor and an Applic:

  trait Monad[F[_]] {
    val pointed: Pointed[F]
    val bind: Bind[F]

    def functor: Functor[F] = new Functor[F] {
      def fmap[A, B](f: A => B): F[A] => F[B] = (fa: F[A]) => 
        bind.bind((a: A) => pointed.point(f(a))).apply(fa)
    }

    def pointedFunctor: PointedFunctor[F] = new PointedFunctor[F] {
      val functor = Monad.this.functor
      val pointed = Monad.this.pointed
    }

    def applic: Applic[F] = new Applic[F] {
      def applic[A, B](f: F[A => B]) = a => 
        bind.bind[A => B, B](ff => functor.fmap(ff)(a))(f)
    }

    def applicative: Applicative[F] = new Applicative[F] {
      val pointedFunctor = Monad.this.pointedFunctor
      val applic = Monad.this.applic
    }
  }

And the Ident class is trivially a Monad (having a pointed and a bind member):

  implicit def IdentIsMonad = new Monad[Ident] {

    val pointed = new Pointed[Ident] {
      def point[A](a: => A): Ident[A] = Ident(a)
    }
    val bind = new Bind[Ident] {
      def bind[A, B](f: A => Ident[B]): Ident[A] => Ident[B] = 
        (i: Ident[A]) => f(i.value)
    }

  }

We can use our brand new map function now:

  tree.map((i: Int) => i.toString) must_== Bin(Leaf("1"), Leaf("2"))

We can even use it to get the "shape" of our container and discard all the elements:

  tree.shape must_== Bin(Leaf(()), Leaf(()))

The shape method just maps each element to ().

Decompose / Compose

I recap. We implemented a very generic way to iterate over a structure, any kind of structure (as long as it's Traversable), containing elements, any kind of element, with a function which does an "application", any kind of application. Among the possible "applications", we've seen 2 examples: collecting and mapping which are the essential operations that we usually do in a for loop.

Specifically we were able to get the contents of a tree and its shape. Is there a way to compose those 2 operations into a decompose operation that would get both the content and the shape at once? Our first attempt might be:

  def decompose[A] = (t: T[A]) => (shape(t), contents(t))

  tree.decompose must_== (Bin(Leaf(()), Leaf(())), List(1, 2))

This works but it is pretty naive because this requires 2 traversals of the tree. Is that possible to do just one?

Applicative products

This is indeed possible by noticing the following: the product of 2 Applicatives is still an Applicative.

Proof, proof. We define Product as:

  case class Product[F1[_], F2[_], A](first: F1[A], second: F2[A]) {
    def tuple = (first, second)
  }

I spare you the full definition of Product as an Applicative to just focus on the Applic instance:

  implicit def ProductIsApplic[F1[_] : Applic, F2[_] : Applic] =
    new Applic[({type l[A]=Product[F1, F2, A]})#l] {
      val f1 = implicitly[Applic[F1]]
      val f2 = implicitly[Applic[F2]]

      def applic[A, B](f: Product[F1, F2, A => B]) = (c: Product[F1, F2, A]) =>
        Product[F1, F2, B](f1.applic(f.first).apply(c.first), 
                           f2.applic(f.second).apply(c.second))
   }

That's not too complicated, you just have to follow the types. What's more troubling is the amount of type annotations which are necessary to implement decompose. Ideally we would like to write:

  def decompose[A] = traverse((t: T[A]) => shape(t) ⊗ contents(t))

Where ⊗ is an operation taking 2 Applicatives and returning their product. Again the lack of partial type application for Const muddies the whole (upvote SI-2712 please!):

val shape   = (a: A) => Ident(())
val content = (a: A) => Const[List[A], Unit](List(a))

val product = (a: A) => (shape(a).⊗[({type l[T] = Const[List[A], T]})#l](content(a)))

implicit val productApplicative = 
  ProductIsApplicative[Ident, ({type l1[U] = Const[List[A], U]})#l1]

(ta: T[A]) => { val (Ident(s), Const(c)) = 
  traverse[({type l[V] = Product[Ident, ({type l1[U] = Const[List[A], U]})#l1, V]})#l, A, Unit](product).
   apply(ta).tuple
  (s, c)
}

We can improve the code sligthly by moving the implicit definition for productApplicative inside the Applicative companion object:

  object Applicative {
   ...
   implicit def ProductWithListIsApplicative[A[_] : Applicative, B] = 
     ProductIsApplicative[A, ({type l1[U] = Const[List[B], U]})#l1]
 }

Then no implicit val productApplicative is necessary and the Applicative imports will be all we need.

Collection and dispersal

There is another way to do things "in parallel" while traversing the structure. The collect method that we're going to build will do 2 things:

it will accumulate some kind of state, based on the elements that we meet

it will map each element to another kind of element

So, as we're iterating, we can do a regular mapping while computing some kind of measure. But before that, we need to take a little detour (again?? Yes, again) with the State monad.

The `State` monad

The State Monad is defined by:

  trait State[S, +A] {
    def apply(s: S): (S, A)
  }

It is basically:

an object keeping some previous "state", of type S
a method to extract a meaningful value from this "state", of type A

this method computes a new "state", of type S

For example, a simple counter for the number of elements in a List[Int] can be implemented by:

  val count = state((n: Int) => (n+1, ()))

It takes the previous "count" number n and returns the new state n+1 and the extracted value (() here, because we don't need to extract anything special).

The State type above is a Monad. I encourage you to read "Learn You a Haskell" to get a better understanding on the subject. I will just show here that the flatMap (or bind) method of the Monad typeclass is central in putting that State to work:

  val count = (s: String) => state((n: Int) => (n+1, s + n))

  (count("a-") flatMap count flatMap count).apply(0) must_== (3, "a-012")

The count function takes the latest computed string and returns a State where we increment the current "state" by 1 and we have a new String as the result, where the current count is appended. So when we start with the string "a-" and we flatMap count 2 times, we get (3, "a-012") where 3 is the number of times we've applied the n+1 function and "a-012" the result of appending to the current string.

By the way, why do we need to apply(0)?

When we do all the flatMaps, we actually store "stateful computations". And they are executed only once we provide the initial state: 0!

Collecting elements

Let's now define a collect operation on Traversable which will help us to count:

  def collect[F[_] : Applicative, A, B](f: A => F[Unit], g: A => B) = {
    val applicative = implicitly[Applicative[F]]
    import applicative._

    val application = (a: A) => point((u: Unit) => g(a)) <*> f(a)
    traverse(application)
  }

This collect operation, defined in EIP, is different from the collect operation on Scala collections which is the equivalent of filter + map. The collect of EIP is using 2 functions:

f: A => F[Unit] which collects data from each element "effectfully" (that is, possibly keeping state)

g: A => B which maps each element to something else

So we could say that the EIP collect is a bit like fold + map. Knowing this, we can use collect to count elements and do some mapping:

  val count = (i: Int) => state((n: Int) => (n+1, ()))
  val map   = (i: Int) => i.toString

  tree.collect[({type l[A]=State[Int, A]})#l, String](count, map).apply(0) must_== 
  (2, Bin(Leaf("1"), Leaf("2")))

Here again the type annotations are obscuring the intent a bit and if type inference was perfect we would just read:

  val count = (i: Int) => state((n: Int) => (n+1, ()))
  val map   = (i: Int) => i.toString

  tree.collect(count, map).apply(0) must_== (2, Bin(Leaf("1"), Leaf("2")))

I don't know about you, but I find this a bit magical. With the Applicative and Traversable abstractions, we can assemble our program based on 2 independent functions possibly developed and tested elsewhere.

Dispersing elements

The next utility function proposed by EIP is the disperse function. Its signature is:

  def disperse[F[_] : Applicative, A, B, C](f: F[B], g: A => B => C): F[A] => F[T[C]]

What does it do?

f is the Applicative context that's going to evolve when we traverse the structure, but regardless of what the elements of type A are
g is a function which, for each element of type A says what to do with the current context value, B, and map that element back to the structure

Please, please, a concrete example!

Say I want to mark each element of a BinaryTree with its "number" in the Traversal (the "label"). Moreover I want to use the element name to be able to qualify this label:

  // a BinaryTree of Doubles
 val tree: BinaryTree[Double] = Bin(Leaf(1.1), Bin(Leaf(2.2), Leaf(3.3)))

 // the "label" state returning integers in sequence
 val labelling: State[Int, Int] = state((n: Int) => (n+1, n+1))

 // for each element in the tree, and its label, 
 // produce a String with the name and label
 val naming: Double => Int => String = (p1: Double) => (p2: Int) => p1+" node is "+p2

 // testing by applying an initial state (label `0`) and
 // taking the second element of the pair `(last label, resulting tree)`
 tree.disperse[elided for sanity](labelling, naming).apply(0)._2 must_==
   Bin(Leaf("1.1 node is 1"), Bin(Leaf("2.2 node is 2"), Leaf("3.3 node is 3")))

Note that the naming function above is curried. A more familiar way to write it would be:

  val naming: (Double, Int) => String = (p1: Double, p2: Int) => p1+" node is "+p2

But then you would have to curry that function to be able to use it with the disperse function:

  tree.disperse[...](labelling, naming.curried)

The implementation of disperse is:

  def disperse[F[_] : Applicative, A, B, C](f: F[B], g: A => B => C) = {
    val applicative = implicitly[Applicative[F]]
    import applicative._

    val application = (a: A) => point(g(a)) <*> f
    traverse(application)
  }

It is using the very capabilities of the applicative functor, the point method and the <*> application.

An overview of traversals

We've seen in the 2 examples above that we get different, specialized, versions of the traverse function by constraining how mapping and Applicative effects occur. Here's a tentative table for classifying other specialized versions of the traverse function:

function	map element	create state	mapped depend on state	state depend on element
`collect`	X	X		X
`disperse`	X	X	X
`measure`	X	X
`traverse`	X	X	X	X
`reduce`		X		X
`reduceConst`		X
`map`	X

The only function we haven't shown before is measure. It is mapping and accumulating state but this accumulation does not depend on the current element. Here's an example:

  val crosses = state((s: String) => (s+"x", ()))
  val map     = (i: Int) => i.toString

  tree.measure(crosses, map).apply("") must_==
  ("xxx", Bin(Leaf("1"), Bin(Leaf("2"), Leaf("3"))))

Other than not looking very useful, the code above is also lying! It is not possible to have a measure function accepting a State monad without having to provide the usual ugly type annotations. So the actual example is:

  tree.measureState(crosses, map).apply("") must_== 
  ("xxx", Bin(Leaf("1"), Bin(Leaf("2"), Leaf("3"))))

where measureState is a specialization of the measure method to States. I think that one take-away of this post is that it might be beneficial to specialize a few generic functions in Scala , like traverse, collect... for Const and State in order to avoid type annotations.

Composing traversals

There's another axis of composition that we haven't exploited yet.

In a for loop, without thinking about it, you may write:

  for (a <- as) {
    val currentSize = a.size
    total += currentSize
    result.add(total)
  }

In the body of that for loop, you have statements with dependency on each other. In an Applicative traversal, this translates to the Sequential composition of Applicatives. From 2 Applicatives, we can create a third one which is their Sequential composition. More precisely, this means that if F1[_] and F2[_] are Applicatives then F1[F2[_]] is an Applicative as well. You want the demonstration? Ok, go.

First, we introduce a utility function on ApplicFunctors:

  def liftA2[A, B, C](function: A => B => C): F[A] => F[B] => F[C] = 
    fa => applic.applic(functor.fmap(function)(fa))

liftA2 allows to lift a regular function of 2 arguments to a function working on the Applicative arguments. This is using the fact that an ApplicFunctor is a Functor so we can apply function: A => B => C to the "a in the box", to get a F[B => C] "in the box". And then, an ApplicFunctor is an Applic, so we can "apply" F[B] to get a F[C]

Armed with this function, we can write the applic method for F1[F2[_]]:

  implicit val f1ApplicFunctor = implicitly[ApplicFunctor[F1]]
  implicit val f2ApplicFunctor = implicitly[ApplicFunctor[F2]]

  val applic = new Applic[({type l[A]=F1[F2[A]]})#l] {
    def applic[A, B](f: F1[F2[A => B]]) = (c: F1[F2[A]]) => {
      f1ApplicFunctor.liftA2((ff: F2[A => B]) => f2ApplicFunctor.apply(ff))(f).apply(c)
    }
  }

It's not so easy to get an intuition for what the code above is doing except that saying that we're using previous definitions to allow a F1[F2[A => B]] to be applied to F1[F2[A]].

In mere mortal terms, this means that if we do an Applicative computation inside a loop and if we reuse that computation in another Applicative computation, we still get an Applicative computation. The EIP illustration of this principle is a crazy function, the assemble function.

The `assemble` function

The assemble function takes the shape of a Traversable and a list of elements. If there are enough elements it returns Some[Traversable] filled with all the elements (+ the reminder), otherwise it returns None (and an empty list). Let's see it in action:

        // the "shape" to fill
       val shape: BinaryTree[Unit] = Bin(Leaf(()), Leaf(()))

       // we assemble the tree with an exact list of elements
       shape.assemble(List(1, 2)) must_== (List(), Some(Bin(Leaf(1), Leaf(2))))

       // we assemble the tree with more elements
       shape.assemble(List(1, 2, 3)) must_== (List(3), Some(Bin(Leaf(1), Leaf(2))))

       // we assemble the tree with not enough elements
       shape.assemble(List(1)) must_== (List(), None)

What's the implementation of the assemble function? The implementation uses 2 Monads (which are also Applicatives as we know now):

the State[List[Int], _] Monad is going to keep track of what we've already consumed
the Option[_] Monad is going to provide, or not, an element to put in the structure
the composition of those 2 monads is State[List[Int], Option[_]] (our F1[F2[_]] in the ApplicFunctor definitions above

So we just need to traverse the BinaryTree with one function:

def takeHead: State[List[B], Option[B]] = state { s: List[B] =>
  s match {
    case Nil     => (Nil, None)
    case x :: xs => (xs, Some(x))
  }
}

The takeHead function is a State instance where each state application removes the first element of the list of elements if possible, and returns it in an Option.
This is why the result of the assemble function, once we apply it to a list of elements, is of type (List[Int], Option[BinaryTree[Int]]).

A recursive implementation

Just for the fun of comparison, I'm going to write a recursive version doing the same thing:

  def assemble(es: List[Int], s: BinaryTree[Unit]) : (List[Int], Option[BinaryTree[Int]]) = {
    (es, s) match {
      case (Nil, _)                      => (es, None)
      case (e :: rest, Leaf(()))         => (rest, Some(Leaf(e)))
      case (_, Bin(left, right))         => {
        assemble(es, left) match {
          case (l, None)       => (l, None)
          case (Nil, Some(l))  => (Nil, None)
          case (rest, Some(l)) => assemble(rest, right) match {
            case (r, None)            => (r, None)
            case (finalRest, Some(r)) => (finalRest, Some(Bin(l, r)))
          }
        }
      }
    }
  }
  assemble(List(1, 2, 3), shape) must_== (List(3), Some(Bin(Leaf(1), Leaf(2))))

It works, but it makes my head spin!

A classical for-loop implementation

By the way, what would be the real for loop version of that functionality? That one is not so easy to come up with because AFAIK there's no easy way to iterate on a BinaryTree to get a similar BinaryTree with just a for loop! So, for the sake of the argument, we're going to do something similar with just a List structure:

  def assemble[T](es: List[T], shape: List[Unit]) = {
    var elements = es
    var list: Option[List[T]] = None
    for (u <- shape) {
      if (!elements.isEmpty) {
        list match {
          case None    => list = Some(List(elements.first))
          case Some(l) => list = Some(l :+ elements.first)
        }
        elements = elements.drop(1)
      } else {
        list = None
      }
    }
    (elements, list)
  }
  assemble(List(1, 2, 3), List((), ())) must_== (List(3), Some(List(1, 2)))

Contrast and compare with:

  List((), ()).assemble(List(1, 2, 3)) must_== (List(3), Some(List(1, 2)))

where you just define List as a Traversable:

  implicit def ListIsTraversable[A]: Traversable[List] = new Traversable[List] {

    def traverse[F[_] : Applicative, A, B](f: A => F[B]): List[A] => F[List[B]] = 
      (l: List[A]) => {
        val applicative = implicitly[Applicative[F]]
        l match {
          case Nil       => applicative.point(List[B]())
          case a :: rest =>
            ((_:B) :: (_: List[B])).curried ∘ f(a) <*> (rest traverse f)
      }
    }

  }

The Applicative composition is indeed very powerful, but we're going to see that there are other ways to compose functions and use them with Traversables.

Monadic composition

This paragraph is exploring the fine relationships between applicative composition and monadic composition when doing traversals. We've seen that Applicative instances can be composed and that Monads can be Applicative. But Monads can also be composed using the so-called Kleisli composition. If we have:

  val f: B => M[C]
  val g: A => M[B]

Then

  val h: A => M[C] = f ∎ g // is also a function from a value to a Monad

If we have 2 "monadic" functions f and g, we can then compose them, in the Kleisli sense, and use the composed version for a traversal. Indeed we can, but does this traversal have "nice properties"? Specifically, do we have:

  traverse(f ∎ g) == traverse(f) ∎ traverse(g)

The answer is... it depends.

Monad commutativity

EIP shows that, if the Monad is commutative, then this will always be true. What is a commutative Monad you ask?

A Monad is commutative if for all mx: M[X] and my: M[Y] we have:

    val xy = for {
     x <- mx
     y <- my
   } yield (x, y)

   val yx = for {
     y <- my
     x <- mx
   } yield (x, y)

   xy == yx

This is not the case with the State Monad for example:

   val mx = state((n: Int) => (n+1, n+1))
   val my = state((n: Int) => (n+1, n+1))

   xy.apply(0) must_== (2, (1, 2))
   yx.apply(0) must_== (2, (2, 1))

Monadic functions commutativity

Another slightly different situation is when we have a non-commutative Monad but commutative functions:

  val plus1  = (a: A) => state((n: Int) => (n+1, a))
  val plus2  = (a: A) => state((n: Int) => (n+2, a))
  val times2 = (a: A) => state((n: Int) => (n*2, a))

Here plus1 and times2 are not commutative:

  (0 + 1) * 2 != (0 * 2) + 1

However it is obvious that plus1 and plus2 are commutative. What does that mean when we do a traversal?

If we traverse a simple List of elements using monadic composition we get:

List(1, 2, 3).traverse(times2 ∎ plus1) === 22
List(1, 2, 3).traverse(times2) ∎ List(1, 2, 3).traverse(plus1) === 32

We get different results. However, when f and g commute we get the same result:

List(1, 2, 3).traverse(plus2 ∎ plus1) === 10
List(1, 2, 3).traverse(plus2) ∎ List(1, 2, 3).traverse(plus1) === 10

Applicative composition vs Monadic composition

Another question we can ask ourselves is: if we consider the monadic functions as applicative functions (because each Monad is Applicative), do we get the nice "distribution" property we're after? The answer is yes, even when the functions are not commutative:

List(1, 2, 3).traverse(times2 ⊡ plus1) === 4
List(1, 2, 3).traverse(times2) ⊡ List(1, 2, 3).traverse(plus1) === 4

Well... more or less. The real situation is a bit more complex. List(1, 2, 3).traverse(times2 ⊡ plus1) returns a State[Int, State[Int, List[Int]]] while the second expression returns a State[Int, List[State[Int, Int]] so what I'm hiding here is some more manipulations to be able to query the final result with some kind of join.

Conclusion

You wouldn't believe it but I've only shown here half of the ideas presented in EIP!

To finish off this post here's 3 take-away points that I've learned while writing it:

functional programming is also about mastering some of these higher-level control structures like Applicative. Once you master them, your toolbox expands considerably in power (just consider the assemble example)
Scalaz is an incredible library but somewhat obscure to the beginner. For this post I've rewritten all the typeclasses I needed to have, and lots of examples (using specs2 of course). That gave me a much better understanding of the Scalaz functionality. You may consider doing the same to learn Scalaz (my code is available on github)
Scala is lacking behind Haskell in terms of type inference and it's a real pain for higher-order, generic programming. This can be sometimes encapsulated away by specializing generic functions to very common types (like traverseState instead of traverse). Again, please upvote SI-2712!

Finally, I want to mention that there are many other Haskell functional pearls waiting to be transliterated to Scala. I mean, it's a shame that we don't have yet any equivalent for "Learn you a Haskell" or "Typeclassopedia" in the Scala world. I hope that my post, like this other one by Debasish Ghosh, will also contribute to bridge the gap.

specs2 migration guide

2011-05-21T10:18:00.027+09:00

Rewrite is rarely the right option

Well, except when that's the only one :-).

Before starting specs2, I did try to refactor specs. It turned out that my first design was clearly not adapted to my goals. So I eventually decided to start from a blank page, as explained here. While I wanted to keep most features I didn't try to go for a 100% backward compatibility. I tried to think to features as part of the design space and wanted to be sure I had enough design freedom (a complementary view is that implementation is part of the features space).

That being said, I know that migrating to a new API is not something that people just do for the sheer fun of it. They have to have compelling reasons for doing so.

What are the good reasons why one would like to use specs2 instead of specs?

concurrent execution of examples: that's one major thing that is enabled by specs2 new design. Easy and reliable
acceptance specifications: something which was really experimental in specs and which is now completely integrated. You can use it to create an executable User Guide for example
nifty features such as Auto-Examples (an example here), implicit Matchers creation or Json matchers
lots of small fixes and consistency changes so that writing tests/specifications is just a pleasure!

Now that you've decided to take the ride with specs2, what are the steps for a successful migration?

Just replace org.specs._ with org.specs2.mutable._

The first thing to do is to switch the base import from org.specs._ to org.specs2.mutable._. For simple specifications, with no context setup and simple equality matchers, nothing else is required.

However, depending on the specs features you've been using you'll have to change a few more things:

matchers
context setup
ScalaCheck
miscellaneous: arguments, specification title, specification inclusions, tags, ...

Most of those changes have specific motivations which I leave out of this post to keep it short. If you have questions on any given change please ask on the mailing-list.

You may also want to watch this presentation by @prasinous to learn how she did her own migration of the Salat project.

Matchers

Most of the matchers in specs2 have simply been copied over from the same matchers in specs. There are however some differences:

mustBe, mustNotBe and other mustXXX variants don't exist anymore. Only must_==, must_!=, mustEqual, mustNotEqual are left. Otherwise you have to write must not be(x) instead of mustNotBe
the matchers having not as a prefix have been removed too. You're encouraged to write must not beEmpty instead of must notBeEmpty
the verify matcher has been removed, so you should write f(a) must beTrue instead of a must verify(f) (or better, use ScalaCheck properties!)
beLike used to take a PartialFunction[T, Boolean] as an argument. It is now PartialFunction[T, MatchResult[_]] which allows better failure messages: a must beLike { case ThisThing(b) => b must be_>(0) }. If you have nothing special to assert, just return ok: a must beLike { case ThisThing(_) => ok }
the fail() method has been removed in favor of the simple return of a Failure object: aFailure or failure(message)
String matchers: ignoreCase and ignoreSpace matchers for string equality are now constraints which can be added to the beEqualTo matcher: eEqualTo(b).ignoreSpace.ignoreCase
Iterable matchers: only and inOrder are now constraints with can be applied to the contain matcher instead of having dedicated matchers like containInOrder
Option matchers: "beSomething" is now just beSome
xUnit assertions have been removed

There are certainly other differences, I'll keep the list updated as I'll see them.

Contexts

That's the tough part! There are 3 ways to manage contexts in specs:

"automagic" variables
before / after methods
system / specification contexts

All of this has actually been reduced to the direct use of Scala natural features: the easy creation of traits and case classes. And a few support traits to avoid duplication of code. You definitely should read the User Guide section on Contexts before starting your migration.

Automagic variables

This was a very cool functionality of specs but also the greatest source of bugs! In specs you can nest examples, declare variables in each scope and have those variables being automatically reset when executing each example:

  "this system" should {
   val var1 = ... 
   "example 1" in {
     val var2 = ...
     "subexample 1" in { ... }
     "subexample 2" in { ... }
   }
   "example 2" in { ... }
 }

Handling those variables is a lot less magic in specs2. What's the simplest way to get new variables in Scala? Simply open a new scope by placing some code into a new object! That's it, nothing more to say:

  "this system" should {
   "example 1" in new c1 {
     // do something with var1
   }
   "example 2" in new c1 {
     // do something else with a new var1
   }
 }
 trait c1 {
   val var1 = ...
 }

Well, almost :-). It turns out that the body of an Example has to be something akin to a Result. In order to allow our context, and everything inside, to be a Result, we need to have our c1 trait extend the Scope trait and benefit from an implicit conversion from Scope to Result:

  import org.specs2.specification._

 trait c1 extends Scope {
   val var1 = ...
 }

From there, having nested contexts, like the ones in the first specs example is easy. We use inheritance to create them:

  "this system" should {
   "example 1" in {
     "subexample 1" in new c2 { ... }
     "subexample 2" in new c2 { ... }
   }
   "example 2" in new c1 { ... }
 }
 trait c1 extends Scope { val var1 = ... }
 trait c2 extends c1 { val var2 = ... }

Before / After

In specs, you can run setup code as you would do with any kind of JUnit code. This is done by declaring a doBefore block inside a sus:

  "this system" should {
   doBefore(cleanAll)
   "example 1" { ... }
   "example 2" { ... }
 }

In specs2, there are several ways to do that. The first one is as simple as running that code into the Scope trait:

  "this system" should {
   "example 1" in new c1 { ... }
   "example 2" in new c1 { ... }
 }
 trait c1 extends Scope {
   val var1 = ...
   cleanAll
 }

This works well for "before" setup but we can't easily setup any "after" behavior because we need additional machinery to make sure that the teardown code is executed even if there is a failure. This is where you can use the After trait and define the after method:

  "this system" should {
   "example 1" in new c1 { ... }
   "example 2" in new c1 { ... }
 }
 trait c1 extends Scope with After {
   def after = // teardown code goes here
 }

For good measure, even if it's not necessary, there is a corresponding Before trait and before method for the setup code.

Remove duplication

If you don't need any "local" variable in your contexts, but only before/after behavior, you can reduce the amount of code in the example above with the AfterExample trait (or BeforeExample for before behavior):

  class MySpec extends Specification with AfterExample {

   def after = // teardown code goes here

  "this system" should {
    "example 1" in { ... }
    "example 2" in { ... }
  }
}

Yet another alternative is to use an implicit context:

  implicit val context = new Scope with After {
   def after = // teardown code goes here
 }

 "this system" should {
   "example 1" in { ... }
   "example 2" in { ... }
 }

BeforeSus / AfterSus / BeforeSpec / AfterSpec

Some other declarations in specs, like beforeSpec, allow to specify some setup code to be executed before all the specification examples. In specs2, the Specification is seen as a sequence of Fragments and you have to insert a Step Fragment at the appropriate place:

  step(cleanDB)

  "first example" in { ... }

  "second example" in { ... }

  step(println("finished!"))

Specification / sus contexts

The purpose of Contexts in specs is to be able to define and reuse a given setup/teardown procedure. As seen above, in specs2, traits extending Before or After play exactly the same role.

ScalaCheck

With specs there is a special matcher to check ScalaCheck properties. It comes in 4 forms:

property must pass
generator must pass(function)
function must pass(generator)
generator must validate(partialFunction)

In specs2 we're using the fact that the body of an Example expects anything that can be converted to a Result, so there are implicit conversions transforming ScalaCheck properties and Scala functions to Results and the examples above become:

(we suppose that the function to test has 2 parameters of type T1 and T2, and 2 implicit Arbitrary[T1] and Arbitrary[T2] instances in scope)

"ex" in check { property }
"ex" in check { function }
or "ex" in check (arbitrary1, arbitrary2) { function } to be explicit about the Arbitrary instances to use
no equivalent
no equivalent

You can also notice that specs2 uses implicit Arbitrary instances instead of Gen instances directly but creating an Arbitrary from a Gen is easy:

  import org.scalacheck._

 val arbitrary: Arbitrary[T] = Arbitrary(generator)

Miscellaneous

Arguments

This is also a part of your specifications which is likely to necessitate a change. In specs there were several ways to modify the behavior of the execution or the reporting:

detailedDiffs()
shareVariables()
setSequential()
Command-line options: -sus, -ex, --color, -finalstats,...
Configuration objects

All of this has been completely redesigned in specs2:

all the arguments can be specified from inside the Specification
most of them can be passed on the command-line as Strings

And just to be specific about what's not going to compile during your specs2 migration:

detailedDiffs() needs to be replaced by a diffs(...) or your own Diffs object
shareVariables() makes no sense because all variables are shared in specs2 unless you isolate them in Contexts
setSequential() is replaced with the addition of a sequential argument

DataTables

DataTables have not really changed, except for their package being org.specs2.matcher instead of org.specs.util. You may however get a few compilation errors because of the ! operator as explained here. Just replace it with !! in that case.

Specification title

In specs the specification title is a member of the Specification class whereas Specifications in specs2 are traits. If you want to specify a Specification title in specs2 you can insert it as a Fragment:

  class MySpec extends Specification { def is =
   "Specification title".title ^
   ...
                              ^ end
 }

 class MySpec extends mutable.Specification {
   "Specification title".title
   ...
 }

Include a specification in another one

This used to be done with include or isSpecifiedBy/areSpecifiedBy. In specs2 there are 3 ways to "include" other specifications with different behaviours which mostly make sense with the HmtlRunner:

If you have a "parent" specification spec1

include(spec2) will include all the Fragments of spec2 into spec1 as if they were part of it

link(spec2) will include all the Fragments of spec2 into spec1. When executing spec1, spec2 will be executed and the html runner will create a link to a separate page for spec2

see(spec2) will include all the Fragments of spec2 into spec1. When executing spec1, spec2 will not be executed but the html runner will create a link to a separate page for spec2.

Tags

The tagging system in specs2 has been completely changed but not in way drastic way for users of the API. The major difference is that tags are positional which opens new possibilities for tagging like creating Sections.

Conclusion

There are certainly a million other small differences between your specification written with specs and what it will look like with specs2. I can only apologize in advance for the additional work, offer my best support, and hope that you'll be able to rip out more benefits and more fun of writing specifications with specs2!

Scalacheck generators for JSON

2011-02-18T05:58:00.011+09:00

More than 6 months without a single post, because I've been focusing on the creation of specs2, which should be out in a few weeks (if you want to access the preview drop me a line).

Among the new features of specs2 there will be JSON matchers to help those of you handling JSON data. When developing those matchers I used ScalaCheck to test some of the utility functions I was using. I want to show here that writing custom data generators with ScalaCheck is really easy and almost follows the grammar for the data.

Here's the code:


/**
 * Generator of JSONType objects with a given tree depth
 */
import util.parsing.json._
import org.scalacheck._
import Gen._

trait JsonGen {

  implicit def arbitraryJsonType: Arbitrary[JSONType] = 
    Arbitrary { sized(depth => jsonType(depth)) }
   
  /** generate either a JSONArray or a JSONObject */
  def jsonType(depth: Int): Gen[JSONType] = oneOf(jsonArray(depth), jsonObject(depth))

  /** generate a JSONArray */
  def jsonArray(depth: Int): Gen[JSONArray] = for {
    n    <- choose(1, 4)
    vals <- values(n, depth)
  } yield JSONArray(vals)

  /** generate a JSONObject */
  def jsonObject(depth: Int): Gen[JSONObject] = for {
    n    <- choose(1, 4)
    ks   <- keys(n)
    vals <- values(n, depth)
  } yield JSONObject(Map((ks zip vals):_*))

  /** generate a list of keys to be used in the map of a JSONObject */
  def keys(n: Int) = listOfN(n, oneOf("a", "b", "c"))

  /** 
   * generate a list of values to be used in the map of a JSONObject or in the list
   * of a JSONArray.
   */
  def values(n: Int, depth: Int) = listOfN(n, value(depth))

  /** 
   * generate a value to be used in the map of a JSONObject or in the list
   * of a JSONArray.
   */
  def value(depth: Int) = 
    if (depth == 0) 
      terminalType 
    else 
      oneOf(jsonType(depth - 1), terminalType)
  
  /** generate a terminal value type */
  def terminalType = oneOf(1, 2, "m", "n", "o")
}
/** import the members of that object to use the implicit arbitrary[JSONType] */
object JsonGen extends JsonGen

Two things to notice in the code above:

The generators are recursively defined, which makes sense because the JSON data format is recursive. For example a jsonArray contains values which can be a terminalType or a jsonType. But jsonType can itself be a jsonArray

The top generator used in the definition of the Arbitrary[JSONType] is using a "sized" generator. This means that we can tweak the ScalaCheck parameters to use a specific "size" for our generated data. Here I've choosen to define "size" as being the depth of the generated JSON trees. This depth parameter is propagated to all generators until the value generator. If depth is 0 when using that generator, this means that we reached the bottom of the Tree so we need a "terminal" value. Otherwise we generate another JSON object with a decremented depth.

You can certainly tweak the code above using other ScalaCheck generators to obtain more random trees (the one above is too balanced), with a broader range of values but this should get you started. It was definitely good enough for me as I spotted a bug in my code on the first run!

Random Hacks of Kindness

2010-06-09T21:17:00.002+09:00

Pure kindness

My last coding week-end is worth a few notes. I participated to the Random Hacks of Kindness event in Sydney. The idea is to gather techies and make them code during the week-end on software projects that help the organisations working on humanitarian crises, like the earthquake in Haiti.

I joined the event thinking that, for once, the code I would create would have a direct impact on people lives! Not that working in banking, telecom, or testing tools has no benefit, for no one, but this is guaranteed to help.

First of all I want to say that the organization was flawless, with a very nice room at the University of New South Wales and all the network equipment you would expect: a proper wifi network, video and audio facilities, an additional meeting room, a nice terrace to appreciate the view around and get fresh inspiration/air.

It is also worth mentioning that food and (non-alcoholic) drinks were provided in abundance (maybe because the crowd was less that expected :-)).

Then I must say that one big success factor to the event was the incredible energy conveyed by Heather, a (completely jet-lagged :-)) Canadian girl who animated and coordinated the teams locally and across the continents. A special thank also to Martin Bliemel (from the University) who co-organized and Tolmie for the videos and pictures! (including a video of me if you crawl the links below well enough, you should find it!)

"Crises are chaos, so expect chaos"

One day before the beginning of the week-end the list of projects was published. I had a quick look, the list was huge. My first thought was: "wow, a lot of Python over there. How can I be effective in 2 days only?".

I also realized that most projects had very vague specifications, some looked more like brainstormings indeed.

Eventually, when I arrived on Saturday morning, I had really no idea where I could bring any meaningful contribution, so I just followed someone who had chosen one project and seemed really motivated by it: the PersonFinder project. It turned out that he eventually went on to something else, leaving me and 2 others continuing the project.

But that's the rules of the game. As an introduction for the week-end, Heather reminded us that crises situations generate a lot of chaos, so that's only normal that we experience part of that during the week-end.

For me, that chaos took the form of a long "What am I supposed to do for God's sake?!!" during most of the Saturday (you can read that here).

We did a lot of research: what is already there? what's valuable? How could it be done? It was like a mini business plan for the day. Of course that's a bit frustrating for a software developer who wants to save the world by coding like a madman, but I kept thinking to myself that laying down the foundations of what could be a productive coding session for others, if not for me, was definitely worthwhile. So that become my objective for the week-end:

define exactly what needs to be done
prepare the environment (development, test)
code at least a single, well-defined, small feature

Another way of saying it: reduce the chaos,... Actually most of that became clear to me after I had a discussion with Alice, from the DC team, who had a well-defined idea of where we should go with the project. If only I had that discussion to start with,...

I learned a lot

Let's say it straight, I failed to deliver even a single small feature. But I learned a lot! On the "functional" side, I learned that:

there's a whole ecosystem of "crises software" with platforms like sahana (PHP, Python) or usahidi (PHP)

the integration of social web services is only at its infancy. Website like pipl do not offer a public API for example. There a Google Social Graph API, but it's still in the Labs.

there is available data on the web which is incredibly difficult to grab. For example, knowing my full name, you can easily get my personal address. But for that, you have to know in which country I live and which white page directory website to use. There's no generic query for that kind of search. Hmm, I'd be interesting in knowing which "semantic web" initiative or magical pattern language addresses that in a near future

Web 2.0-this, Social-that, this is a bit of chaos too. Quizz question: what's Google Wave? An email client, a wiki, a code-review tool, a forum? Not only the frontiers and definitions blur, but the amount of possibly related data grows exponentially. Managing all that, including in "crisis" environments will require a lot of "social" heuristics, mixing all kind of CS and social knowledge

The technical side was very illuminating too, as I'm way behind the curve in terms of web technologies:

I learned how to install and deploy a Google Web App on the Google App Engine (GAE)
I realized that my Java skills were useful after all, with the GAE
I read about the Twitter search API (kudos, effective and well-documented)
I had a look at JSON as a data format

That may seem silly but for the first time, the whole notion of webservice started to make sense to me!

And now?

Well, the features are still not fully delivered. Thanks to the heroic work of the DC team, we've made some progress but nothing has been yet approved and reused. Can we do better next time? Sure we can:

we need to have "Product Owners". People who know what they *want* to be done and are able to specify it. Then they can validate the deliverables and can be a stable point of contact after the event is finished

we need more preparation on the projects: for example, what to install for development and testing, some hints about what could be used in the solution. I'm killing a bit the fun and brainstorming aspect of the event here, but the next point is

make a clearer separation between:

"proof of concept" projects: show me this could work
"brainstorming" projects: what could be cool
"prototype" projects: cool + some code
"feature" projects: add a new functionality
"problem-solving" projects: fix something by using a brilliant algorithm for example
"specification" projects: prepare the problem statement for a "feature" project

I think that by making clear what are the expectations and deliverables on each type of project we give more chances to the community to converge towards something eventually useful and durable.

My personal dilemma is that I would love to contribute more to what was started but I have a few open-source commitments that are taking priority over this at the moment. On the other hand I will be really happy to be involved next year in the preparation of the event so that everyone can get the maximum out of it. And that's because, as one of my colleagues said at work:

These projects have a spiritual meaning

OSCON 2010

2010-05-28T07:04:00.005+09:00

The slides

Those are the slides I used to present my talk:

http://github.com/etorreborre/oscon-2010/raw/master/src/main/resources/oscon_2010_specs.pptx
http://github.com/etorreborre/oscon-2010/raw/master/src/main/resources/oscon_2010_specs.pdf

Thank you

I want to add a thank to:

Dean Wampler and Alex Payne for thinking about me to make a presentation
Edd Dumbill and Shirley Bailes for the organization
Scott Berkun (www.scottberkun.com) for giving useful tips to make my talk "suck less"

GuiceModules and TestComponents, a powerful combination

2010-05-13T16:11:00.013+09:00

Important update!! [21/05/2010, see at the bottom]

Sorry everyone, that doesn't work

In this previous post, I was mentioning a way to inject the dependencies of a TestComponent without having to inject the component itself.

The objective was, if I pick up the example I was using, to have a TestComponent called "CustomerOrder". That TestComponent is responsible for setting up a proper Customer and its Order, so that they both can be injecting into the TestCases needing them. But the additional requirement was not to have to inject the CustomerOrder component itself.

It turns out that what I was advising to do, create a binding of the CustomerOrder in the CustomerOrderModule doesn't work at all!

And all my other attempts at solving this issue usually ended up in initialization errors where a TestComponent was relying on another for his setup, but that other one was not initialized.

The proper trick

It is actually simple and I don't understand why I haven't been able to come up with it in the first place.

The idea is to:

get a set of all the modules, including their transitive dependencies
create an injector for this set of modules
inject the modules themselves!


   /**
    * Use all the bindings of this module, including the additional ones
    * to inject dependencies
    * 
    */
   public  T inject(final T object) {
     injector().injectMembers(object);
     return object;
   }
   /**
    * @return an injector initialized with all the transitive bindings of this module
    */
   private Injector injector() {
     if (injector == null) {
        injector = Guice.createInjector(getModules());
        injectModules();
     }
     return injector;
   }
   /**
    * modules are injected one after the other following their dependencies order:
    * If module A depends on module B, then module B must be injected first 
    */
   private void injectModules() {
     final List sorted = new ArrayList(getModules());
     Collections.sort(sorted, new GuiceModuleComparator());
     for (final GuiceModule m : sorted)
       injector.injectMembers(m);
   }

Because the modules are now injected, if you add a dependency inside the module, that dependency will be initialized when the Module is injected. So nothing stops me to inject the CustomerOrder TestComponent into its module so that anytime someone uses the module, the CustomerOrder TestComponent will be fully set-up.

Now, how does the code above solves the initialization issues I've been mentioning?

Well, I guess that you noticed something in that code, the modules are sorted before they're injected. Indeed they are sorted following the "natural" pre-order of their transitive dependencies with the following Comparator:


  private static class GuiceModuleComparator implements Comparator {
    public int compare(final GuiceModule o1, final GuiceModule o2) {
      if (o1.getModules().contains(o2))
        return 1;
      else if (o2.getModules().contains(o1))
        return -1;
      return 0;
    }
  }

This sorting ensures that "low-level" modules will be injected first, then modules depending on them will be injected, respecting the actual dependencies.

So now I can write:


  /** 
   * The bindings definitions
   */
  public class CustomerOrderModule extends GuiceModule {
    // this injection will setup the Customer/Order before they're used anywhere
    @Inject CustomerOrder customerOrder;
    @Override protected void configure() { 
      bind(Customer.class).toInstance(new Customer());
      bind(Order.class).toInstance(new Order());
    }
  }
  /** 
   * The CustomerOrder TestComponent setting up a "typical" 
   * Customer and its Order
   */
  public class CustomerOrder extends TestComponent {
    @Inject Customer customer;
    @Inject Order order;
    @Override protected void before() { 
      // set up the Customer and order instances here
      order.setCustomer(customer);
    }
  }
  /** 
   * A test case using the Customer and its Order
   */
  public class OrderingTestCaseextends TestComponent {
    // the customer and order can be injected without having to
    // inject the CustomerOrder TestComponent!!
    @Inject Customer customer;
    @Inject Order order;

    @Test public void anOrderMustHaveACustomer() {
      assertEquals(customer, order.getCustomer());
    }
    @Override public GuiceModule module() { 
      return new CustomerOrderModule();
    }
  }

Please ask

That's all there is to it. I understand that this may be a bit difficult to grasp at first, but then you realize that you only have a few concepts:

a GuiceModule specifies bindings
GuiceModules can to have dependencies to other GuiceModules
a TestComponent is either setting data (aka TestFixture) or is a TestCase
a TestComponent specifies its GuiceModule to define its required bindings

Give it a go, I've been using that for a while now on my project, and the flexibility we got for defining and reusing TestComponents has been really great. And if you have any trouble don't hesitate to ask, I'll be happy to provide some more complete code samples and explanations.

Important update!! [21/05/2010]

Live and learn, they say. Well the sorting of modules proposed above doesn't work either. What I really want is a topological sort. I'm glad that Cedric Beust posted this article once, explaining how he was dealing with the dependencies in TestNG, because that's essentially the same problem here.

So, for the courageous who want to follow the GuiceModules/TestComponent way, here is the sorting code you will need:


/**
 * This sort algorithm is taken from http://en.wikipedia.org/wiki/Topological_sorting
 * @return the list of sorted modules according to the Topological order
 */
public List sortedModules() {
 final List result = new ArrayList();
 final Map visited = new HashMap();
 for (final GuiceModule m : getModules())
   visited.put(m, false);
 for (final GuiceModule m : getModules())
   visit(m, result, visited);
 return new ArrayList(result);
}

/**
 * visit a module and add it only if it comes after other modules
 */
private void visit(final GuiceModule m, final List result, final Map visited) {
  if (!visited.get(m)) {
    visited.put(m, true);
    for (final GuiceModule other : getModules()) {
      if (!m.equals(other) && !visited.get(other) && GuiceModuleComparator.compare(other, m) < 0)
        visit(other, result, visited);
      result.add(m);
    }
  }
}

This is exactly the time when I don't regret reading blog posts as a morning routine in the morning!

Mini-Parsers to the rescue

2010-05-06T20:30:00.016+09:00

An example of curryfication

I'm implementing a reasonably complex algorithm at the moment with different transformation phases. One transformation is a "curryfication" of some terms to be able to transform some expressions like:

f(a, b, c)

to

.(.(.(f, a), b), c)

Being test-compulsive, I want to be able to test that my transformation works. Unfortunately the data structures I'm dealing with are pretty verbose in my tests.

One of my specs examples was this:


"A composed expression, when curried" should {
  "be 2 successive applications of one parameter" + 
  "when there are 2 parameters to the method expression" in {
    ComposedExp(MethodEx(method), const :: arb :: Nil).curryfy must_==
      Apply(Apply(Curry(method), Curry(const)), Curry(arb))
  }
}

But Apply(Apply(Curry(method), Curry(const)), Curry(arb))) is really less readable than .(.(method, const), arb). And this can only get worse on a more complex example.

With the help of a mini-parser

So I thought that I could just write a parser to recreate a "Curried" expression from a String.

A first look at the Scala 2.8.0 Scaladoc(filter with "parser") was a bit scary. Especially because my last parser exercise was really a long time ago now.

But no, parser combinators and especially small, specific parsers like the one I wrote, are really straightforward:


object CurriedParser extends JavaTokenParsers {
  val parser: Parser[Curried] = application | constant
  val constant = ident ^^ { s => Curry(s) }
  val application = (".(" ~> parser) ~ (", " ~> constant <~ ")") ^^ { case a ~ b => 
    Apply(a, b) 
  }    
  def fromString(s: String): Curried = parser.apply(new CharSequenceReader(s)).get
}

In the snippet above I declare that:

my parser returns a Curried object

my parser is either an application or a constant (with the | operator)

a constant is a Java identifier (ident is a parser inherited from the JavaTokenParsers trait)

a constant should be transformed to a Curry object

an application is composed of two parts (separated by the central ~ operator). The first part is: some syntax ("(") and the result of something to parse recursively with the parser (i.e. an application or a constant). The second part is a constant, surrounded by some syntax (", " and ")"). Note that the syntactic elements are being discarded by using ~> and <~ instead of ~.

once an application is parsed, part 1 and part 2 are accessible as matchable object of the form a ~ b and this object can be used to build an Apply object

the fromString method simply passes a String to the parser and gets the result

I have to say that this parser is really rudimentary. It doesn't handle errors in the input text, there absolutely needs to be a space after the comma, and so on.

Yet it really fits my testing purpose for a minimum amount of development time.

Open question

I hope that this post can serve as an example to anyone new to Scala wanting to play with parsers and I leave an open question for senior Scala developers:

Is there a way to extends the case classes representing algebraic datatypes in Scala so that:

each case class has a proper toString representation (that's already the case and that's one benefit of case classes), but that representation can be overriden (for example to replace Apply(x, y) with .(x, y))

there is an implicit parser that is able to reconstruct the hierarchy of objects from its string representation

We need an algebra for Guice modules

2010-03-10T16:39:00.021+09:00

Or,... I missed something (which is still highly probable).

Anyway, I want to share today the small library I've created to ease the life of my co-workers when faced with the tedious task of writing unit tests.

I won't do that again and again (and again)

I love writing unit tests. Ah, the smell of the CPU burning cycles to pass all those little creatures to green! Yet, starting from a blank page can be really tedious.

If you're like me, working with some kind of major Client-Server system, with tons of business objects and a fair deal of interfaces, you may find that just starting writing the first line of test code is no piece of cake. You're likely to need:

some kind of "reference" data in your system, like a list of customers or a list of products
some live-like data, like current prices
some elaborate building of your "object under test", like a ConfirmationProcessor for orders confirmation
some infrastructure to make sure that you don't need to go to a real database (think "mocks" here)
some infrastructure to make sure that you don't need to access external webservices (think "mock" one more time)

Phew! I can pretty much guarantee that if you've gone through the trouble of coding all this machinery once, for your first test class, you will desperately want to reuse it a for your next test class!

Injection is for everyone: interfaces, objects, mocks and, yes, tests

If I rephrase the requirements above a bit differently, what I really, really, want is the ability to create Test Components where:

one Test Component represents my Server, with all interfaces being mocks (those are RMI interfaces in my case)

one Test Component provides a set of factories to create business objects easily and make as if they were saved on the Server (this uses the previous Test Component, right?). Once initialized, this component maken sure that a mininum of default "reference" objects are already saved (a customer and a product for example)

one Test Component named CustomerOrder represents the "typical" customer order, with all necessary customer data, product selection,... This component also provides easy methods to change the product or the payment details, possibly using a DSL to do that concisely

one Test Component is for the ConfirmationProcessor, what you really want to test, an object which creates and sends confirmations to the customer for their orders. This component, for example, is using a mock for the DiscountCalculator because it is not relevant in the context of sending confirmations

It must be clear, from the description above, that those Test Components may have lots of dependencies between them. Instantiating all those components properly can rapidly become a nightmare, but it happens that we know exactly how to deal with this nowadays.

Different shapes and flavors are available for Dependency Injection and I went with my favorite: Google Guice. Guice is going to "inject" all the required objects for my test:

a mock Server
a set of factories
a typical customer order
the context of my test

Show me the code

First of all, I need to show what I mean by TestComponent:


/** something with a Guice module */
public interface HasGuiceModule {
  GuiceModule module();
}

/**
 * A simple test component using a Guice Module to inject its members
 * when invoked by JUnit through the @Before annotation.
 *
 * If necessary, after the members injection, the subclass can use the localSetup method
 * to add more initialization (like creating an initial customer) or more
 * expectations (for mock objects)
 */
public abstract class TestComponent implements HasGuiceModule {
  @Before
  public void setup() {
    inject();
    localSetup();
    expectations();
  }

  private void inject() {
    module().inject(this);
  }

  protected void localSetup() {}
  protected void expectations() {}
}

The component above is really JUnit-oriented but you could as easily add a main method which would call the setup.

Armed with this, I can create my first concrete Test Components, leaving out the module() method definition for now:

public class MockServer extends TestComponent {
  @Inject
  Connection connection;

  @Inject
  CustomerInterface customers;

  @Inject
  ProductInterface products;

  @Inject
  OrderInterface orders;

  // do all the wiring when the members have been injected with Guice
  @Override
  protected void expectations() {
    when(connection.getCustomersInterface()).thenReturn(customers);
    when(connection.getProductsInterface()).thenReturn(products);
    when(connection.getOrdersInterface()).thenReturn(orders);
  }

  protected GuiceModule module() { /** to be defined later */ }
}

public class Factories extends TestComponent {
  // this server interface provides methods to individual objects: a customer
  // a payment method, a customer address,...
  @Inject CustomerInterface customers;

  // this factory provide easy to use methods to create
  // fully setup customers with delivery address, payment method,...
  // it uses the CustomerInterface interface to do so
  @Inject CustomerFactory customerFactory;

  protected GuiceModule module() { /** to be defined later */ }
}

public class ConfirmationProcessorTest extends TestComponent {

  // the class under test
  @Inject ConfirmationProcessor processor;

  // the standard order, it uses the OrderFactory and CustomerFactory to save and
  // update the customer and order
  @Inject CustomerOrder customerOrder;

  @Test public void aConfirmationForAGoldCustomerMustDisplayStars() {
    // a DSL for describing customer types
    customerOrder.setCustomerType("Gold 5Y 4*");
    confirmationMustContain("*******");
  }

  private void confirmationMustContain(String content) {
    assertTrue(processor.
               confirmationFor(customerOrder.customer()).contains(content));
  }

  protected GuiceModule module() { /** to be defined later */ }
}

The code above shows a classic JUnit4 class, with one method annotated with @Test. The nice things to notice are:

the test data is injected in the form of a Test Component with a ready-to-use initial state
that Test Component provides convenient ways to refine the initial state with data relevant to the test objective

So what's Guicy here?

So far, so good, but you must definitely feel that I left out part of the actual magic here. What about this module() method? How are GuiceModules defined? And why a GuiceModule and not a Guice,...,Module (i.e. com.google.inject.Module)?

The module() method is very straightforward. It just returns a GuiceModule which describes

the bindings for the TestComponent:

public ConfirmationProcessor extends TestComponent {
  protected void module() {
    return new ConfirmationProcessorModule();
  }
}
// and
public ConfirmationProcessorModule extends GuiceModule {
  // bindings go here
}

So, what is a GuiceModule? Actually, a GuiceModule is mostly a regular com.google.inject.AbstractModule. It allows you to describe the bindings for a specific TestComponent. However, it is refinable, test-friendly and composable with other modules.

Let's see how it works with several examples:

A simple module

public MockServerModule extends GuiceModule {
  @Override protected void configure() {
    // equivalent to bind(Customers.class).toInstance(mock(Customers.class))
    // this binding declares that in every TestComponent using this GuiceModule
    // the Customers interface will be a mock
    mockAndBind(CustomerInterface.class);
  }
}

A module dependent on another

public MockFactoriesModule extends GuiceModule {
  @Override protected void configure() {
    // in these bindings, we declare that the factories are
    // going to use an in-memory representation of the database
    // the job of a Mock database is to use the mock server interfaces
    // to make as if a saved object was always returned when required
    bind(CustomersDatabase.class).to(MockCustomersDatabase.class);
  }
  @Override protected Set<GuiceModule> modules() {
    // add a MockServerModule to the list of dependent modules
    return module(MockServerModule.class);
  }
}

A module with dependencies and local mocks

public ConfirmationProcessorModule extends GuiceModule {
  @Override protected List<Class<?>> mocks() {
    return classes(DiscountCalculator.class);
  }
  @Override protected Set<GuiceModule> modules() {
    return modules(CustomerOrderModule.class);
  }
}

A module refining another one and composed with other modules for a complex setup

new ConfirmationModule() {
  @Override protected List<Class<?>> spies() { 
    return classes(ConfirmationProcessor.class); 
  }
}.remove(MockPrinterModule.class).add(RealPrinterModule.class)

As you can see on those examples, there is a lot of flexibility to allow you to reuse your existing modules as much as possible:

by refining them with additional mocks / spies (subclassing the mocks method)
by adding another module to form a larger one
by removing / replacing another module

One question however remains unanswered. The dependencies among modules could be rather hairy and knowing that you can't declare bindings more than once with Guice, how do you manage to avoid conflicts? You can't afford to add modules referencing one another and face the nightmare of digging out why a given module has been referenced twice.

Transitive dependencies and Set of GuiceModules

The answer to this issue is simple. It is coded in the GuiceModule#getModules() method:

public Set<GuiceModule> getModules() {
  Set<GuiceModule> result= new HashSet<GuiceModule>();
  result.addAll(dependentModules); // a private list of added modules
  result.addAll(modules()); // the ones declared by the subclass

  for(GuiceModule m: modules()) {
    result.addAll(m.getModules());
  }
  for(GuiceModule m: modulesToRemove()) {
    result.removeAll(m.getModules());
  }
  result.add(this);
  return result;
}

The GuiceModule#getModules() method adds or removes modules following all dependencies transitively (and recursively). The design is also kept voluntarily simple here. A Set makes sure that 2 "same" modules are never returned based on them being equal. And 2 modules are considered to be equal if they have the same class.

This forbids the possibility of parameterizing modules but I haven't found the need yet to do that. My guess is also that evolving the design to accommodate that situation shouldn't be too difficult (add a smarter equal method).

Now my real question to the knowledgeable people around here is: is there a better way to do so with Guice?

I've found a way to override bindings from a module with bindings from another module. I've seen that you can create a hierarchy of injectors. I've seen that you can use scopes to specify the applicability of your bindings. But I haven't found anything like a simple "algebra" for modules so that they can be added, subtracted (or unioned / intersected if you prefer). Maybe this post title is provocative enough that I can get an enlightened answer!

Anyway, the supporting code I'm presenting here is just a few lines. All the heavylifting is done in Guice for dependencies resolution as well as in the Factories I've created to mock out the Server and create smart test data.

Last.tips.com

A Test Component is declaring lots of bindings but and in order to get the corresponding members injected, you either need to:

inject the component itself to your test
inherit from it

Let's take an example. You want to use the "standard" order built by the CustomerOrder TestComponent. You could write:

public class MyTestWithAnOrder extends TestComponent {
  // injecting the CustomerOrder builds an order which itself is injected
  // forgetting that line would end up with an "empty" order 
  // (order.equals(new Order()))
  @Inject CustomerOrder customerOrder
  @Inject Order Order
  public GuiceModule module() { return new CustomerOrderModule(); }
}

You can also write:

public class MyTestWithAnOrder extends CustomerOrder {
  // the order member can be inherited and properly setup by the superclass
  public GuiceModule module() { return new CustomerOrderModule(); }
}

But here's a trick. If you declare the following binding in the CustomerOrderModule:

public class CustomerOrderModule extends GuiceModule {
  @Override protected void configure() { 
    ...
    bind(Order.class).toInstance(new Order());
    bind(CustomerOrder.class).toInstance(new CustomerOrder);
    ... 
  }
}
// given that CustomerOrder looks like
public class CustomerOrder extends TestComponent {
  @Inject Customer customer;
  @Inject Order order;
  @Inject OrderFactory orderFactory;

  // this is where, as a post-construct step, the order object gets fully setup  
  @Inject 
  protected void localInit() {
    orderFactory.saveAsStandardOrder(order);
  }
  public void GuiceModule module() { return new CustomerOrderModule(); }
}

Then, you can just access the order dependency in your test without having to reference the CustomerOrder TestComponent:

public class MyTestWithAnOrder extends TestComponent {
  // it just works (tm)
  @Inject Order Order
  public GuiceModule module() { return new CustomerOrderModule(); }
}

The other tip I want to share is the addition on the Factories objects of autoGet() methods.

Let's say you need, for your test, to make as if a customer existed in the database. The usual thing to do is to use the test factory to create a new Customer object and use mocks to have it returned when someone calls getCustomer(id). But you may actually not really care about which customer it really is. So why not go one step further with an autoGet() method?

Calling autoGet() on the factory will just set-up the mock object representing the CustomerInterface on the Server so that every time a customer is requested with an id, you simply create one on the fly and return it! (see here to see how to do it with Mockito).

Conclusion

I think the take-away points from this post are:

Test components are worth investing in
But then they have to be highly reusable
Guice is a great tool to manage dependencies
Dependencies are better off with some operations to combine them

And the last, last, important thing about having TestComponents and dependencies carefully outlined is that it forces you to think about your design. If you find yourself having too many components and objects to inject for a given test, it may very well be sign of a potent code smell.

A FIT-like library for Scala

2009-04-22T10:59:00.021+09:00

Ever since I started the specs project, I saw the possibility to provide a better FIT-like library for Scala developers.

Having been a Fitnesse user in the past, I was dissatisfied with the following:

having interpreted tables with no possibility for automated refactoring

being limited to tables and not being able to add simple expectations close to the specification text

being limited to tables while my domain data could be too complex to fit in a tabular format, hence supplementary work when trying to map business concepts to FIT tables

A tool for developers

I first started with the following assumption: most "business users", "subject matter experts" (SME) can't write and maintain FIT specifications. This point of view is not shared by everyone, but my experience shows me that the most workable FIT process is:

A SME gives examples of what is expected, on the blackboard, on a paper, on an excel spreadsheet, whatever
A developer walks through the examples with the SME, asking questions, negociating features,... This is the most important part: communicating clearly the specifications through examples.
A developer writes and implements the examples with the FIT library
The developer comes back to the SME to clarify hidden assumptions and preconditions as writing things down precisely often shows under-specified parts
The developer completes the executable specification and refactors it
The SME validates the final result which should be as readable as possible for her. Possibly, she adds some variations on the first examples, iterating on the whole process

The main conclusion of the small process depicted above is that:

We can use developer tools because developers are the primary users for the FIT-like specification tools

Of course, this isn't the end of the story. SME are indeed secondary users of those tools and we should take care of them in the future.

But let's focus for now on our primary users. If we create a tool for developers:

An IDE can be used to edit, refactor and navigate the specifications (think Eclipse, IntelliJ)
A high-level language can be used to produce them (think Scala of course!)
The specifications can be stored in a Source configuration and control system (think Subversion, git,...)

Basic specifications

I first started with this vision: a specification should be some free text, explaining what the system is supposed to do. Among that text there are sentences or text fragments which represents examples of what the system should really be doing. I want to be able to "tag" those fragments and "link" them to a piece of code implementing the actions on the system and my expectations.

Free text mixed with executable code = ...? Scala XML literals of course!

Having XML literals in Scala allows to write any kind of text and where necessary, insert some code in curly braces {} to be executed. So my first idea was to allow the developer to:

write some specification text in a Scala file, with minimal decorum to create a Specification class:

class HelloWorldSpecification extends HtmlSpecification {

"The greeting application" is <textile>

h3. Presentation

This new application should say "hello" in different languages.

</textile>
}

"tag" part of that text that I consider being an example which should be executed

For example,<ex>by default, saying hello by default should use English</ex>

add a piece of code implementing the example and setting expectations

For example,<ex>by default, saying hello by default should use English</ex>
{ greet must_== "hello" }

I also liked the idea of using wiki markup to introduce simple formatting features to the Specification. Hence the use of tags showing that the Specification text should be interpreted as Textile marked-up text (the other available markup language is Markdown).

The result of this specification can be seen here. The first example executes without any issue and is highlighted as green text:

For example,by default, saying hello by default should use English

You can note that this constrast a lot with other Specification libraries approaches, like Cucumber, where:

Text is interpreted and mapped to methods. If I write "Given I have entered 50 in the calculator", there should be a method like I_have_entered_x_in_the_calculator

The specification flow is imposed through the use of the "Given, when, then" format. My personal feeling is that this is detrimental to writing a good specification where more text, images, tables are needed to explain the expected behavior than just scenarii descriptions

Nesting tables all the way down,...

The first shots at my HtmlSpecifications were encouraging. Simple literate specifications can even be a good way to give examples of an API usage, as in the Mockito specification for specs.

However, I really was missing the table formats I used to work with in Fitnesse.

Then came the next "vision": tables are good, nested tables are better because they can look closer to the data structures we're juggling with all day long. So I should allow tables to be nested and composed of other tables. Hey, even having tabs would be nice, wouldn't it?!

The good news is that nothing else that pure Scala was needed for that.

Let me introduce: Properties, Fields and Forms

Properties

The basic building block of a Form is a Property (of type Prop in specs, Property being reserved for something like this).

A Prop is something which has:

a label
an expected value
an actual value
a constraint

The most common type of property is declared like this in a Form:

// "Name" is the property label, "Eric" is its actual value
val name = prop("Name", "Eric")

and the expected value can be set with:

name("Bob")

Once executed the property will check for the equality of the actual and expected value, using a beEqualTo matcher. Note that it is possible to change the matcher used to check the values:

val name = prop("Name", "Eric").matchesWith(equalToIgnoringCase(_))
name("eric").execute.isOk // true

Fields

Actually there is an even simpler building block for Forms than a Prop: a Field. A Field is simply a piece of input or output data with a label:

val firstName = field("First name", "Eric") // just a name and value

val tradeId = field("Trade id", trade.getId) // retrieved from the database

Forms

Armed with Props and Fields, building a Form is plain easy:

declare the props and fields of the form
declare how they should be layed out

class Person extends Form {
val firstName = prop("First name", "Eric")
val lastName = prop("Last name", "Torreborre")
tr(firstName)
tr(lastName)
}

In the Person form above, we decided that the properties should be displayed on 2 different rows but they might as well be displayed on the same row:

   tr(firstName, lastName)

And this can get arbitrarily more complex because you add also forms in a row:

   tr(firstName, lastName, address) // address is a Form representing the address

Tabs are also very easy to use when there is more data to organize:

class ClubMember extends Form {
new tabs() {
 new tab("Contact details") {
   tr(field("First name", "Eric"))
   tr(field("Last name", "Torreborre"))
 }
 new tab("Sports") {
   th2("Sport", "Years of practice")
   tr(field("Squash", 10))
   tr(field("Tennis", 5))
   tr(field("Windsurf", 2))
 }
}
}

Special forms

As usual, as few patterns emerge when you start using something more frequently. For example, it is pretty common to display data in straightforward tables with column headers. In that case, each cell should be a property with no label and the properties labels should be used to create the header row. The TableForm serves exactly that purpose:

class PayLine(vDate: String, p: Double, r: Double) extends LineForm {
val valueDate = field("Value date", vDate)
val pay = prop("NPV_PAY_NOTIONAL", pricePay(valueDate))(p)
val rec = prop("NPV_REC_NOTIONAL", priceRec(valueDate))(r)
}
new TableForm {
tr(PayLine("6/1/2007", -1732.34, 0.0))
tr(PayLine("4/30/2008", -580332.88, 0.0))
}.report

In a TableForm, each row is a LineForm whose properties and fields will not have their labels displayed inside the table, but which will be used to build the table header. There is an even more cryptic (at least to the eyes of some,...) way of creating such a table using a DataTable, the DataTableForm:

new TradePrice {
"Value date"    | "NPV_PAY_NOTIONAL"    | "NPV_REC_NOTIONAL"    |
"6/1/2007"      ! -1732.34              ! 0.0                   |
"4/30/2008"     ! -580332.88            ! 0.0                   | { (vDate: String, pay: Double, rec: Double) =>
tr(vDate, prop(pricePay(vDate))(pay), prop(priceRec(vDate))(rec))
}
}.report

In that example, the properties are created on the fly, without any label at all, because the table header will be directly taken from the DataTable header.

BagForm

This is certainly the most advanced table featured at the moment. In many situations, each row of the table maps to an entity of the domain (let's say a "Customer").

The BagForm allows to specify that a Seq of actual entities should match the expected one declared on each row:

case class CustomerLine(name: String, age: Int) extends EntityLineForm[Customer] {
// the prop method accepts a function here, taking the proper attribute on the "Entity"
prop("Name", (_:Customer).getName)(name)
prop("Age", (_:Customer).getAge)(age)
}
class Customers(actualCustomers: Seq[Customer]) extends BagForm(actualCustomers)

// usage example
new Customers(customersFromTheDatabase) {
tr(CustomerLine("Eric", 36))
tr(CustomerLine("Bob", 27))
}

Each Customer EntityLineForm declares some properties whose actual values are "extracted" from an actual entity.

When the table is constructed (see "usage example"), each line is tested against the actual entities passed as parameter (customersFromTheDatabase), then only the best matches are kept to create the final table, based on the number of successful properties on each line. And if some expected rows are not matched by any actual entity, they are added at the end of the table as failures. A picture is worth 1000 words, the result is here.

Conclusion

The paint on LiterateSpecification and Form is still fresh! I'm promoting it as "Alpha" for the next specs release (1.5.0), because I expect a few bugs to crop in here and there and lots of additional features to be necessary to support "industrial" specifications.

In any case, I expect that the vision I had and the support of the Scala language will allow everyone to create beautiful specifications with lots of examples to discuss with Subject Matter Experts.

Try it, send me all your feedback, I hope you'll like it, I sure do!

How we decide

2009-03-11T22:36:00.006+09:00

For once, let's think about something else than programming. Or will we ;-)?

The bookshop

Two weeks ago, going back home after some consulting, I arrived early at the airport with a few dollars in my pocket, and I decided to stop by the book shop to have a look at some refreshing mental food.

Haha, I wish that was so easy! I had a first round, looking at almost all the books, then I narrowed down my choice to a few books, maybe 2 or 3 and started thinking really hard.

"Do I prefer a short and small book?"

"Should I take the most interesting?"

"Should it rather be entertaining? I should relax"

"Do I have enough cash? If not, is that worth withdrawing more money?"

"Do I rather to read a more political book?"

"Do I need a book at all?"

All this thinking (I'm not kidding, I spent at least 20 minutes) convinced me that this was the book I should buy: How we decide.

Feelings can be a good decision-maker

This book was for me a very good follow-up on Damasio's book Descartes' error where we learn, through different stories, the role of emotions in the decision making process. Like the story of that guy having a brain injury and not feeling any more emotions.

One morning, coming to Damasio's lab he explained everyone how he's been able to stay very calm in his car, avoiding a deadly car accident due to the iced road that morning. After the session, as he was about to leave, the doctor asked him to select the best date for the next appointment. That emotionless guy stood there, weighting for 30 minutes all the possibles options that were open on his schedule. The team just wanted to strangle him for not being able to make up his mind!

This kind of story is one of many showing the power of emotions or, you could say, the power of the unconscious decision circuits. Most of other Jonas Lehrer examples are taken from games, whether decisions must be taken fast, like baseball or american football, or whether decisions are very complex, like chess or backgammon.

In all those cases, Jonas Lehrer tells us that we have "dopamin learning circuits" which are directly connected to the reward system. Some neurons register when "it's good", when "it works", while others register the surrounding context and the consequences of our actions. The net result is that we progressively get a "feeling", an "intuition" of what works and what doesn't.

For example, Garry Kasparov has a global feeling of what is a good strategic position on the chessboard. Joe Montana had an instinctive feeling of when was the best moment to make a pass on the field. We must also note that both of them have spent a lot of time thinking hard about how they failed, how they made mistakes.

Is there anything we can use out of this for programming?

We should fail early, fail often and try to learn as much as possible from our failures:

by reducing the develop-test cycle so that we have very frequent feedbacks of when changes are breaking stuff

by using retrospectives/post mortems to analyse what is right when working as a group of people on a project

by scrutinizing the code when it hurts. We have to change 100 lines of code all over the place for a seemingly innocent evolution. That hurts, doesn't it? Let's use this as a reinforcement for extreme refactoring. Next time we have to decide if we should refactor or not, the decision should feel obvious

This is also a good justification for code elegance. Code is elegant when it's easy to read, modify, reuse and getting that feeling helps making all the micro-decisions when writing code:

naming
formatting
refactoring
abstracting
checking, validating

Dont always trust your feelings, Luke

Our "dopamin circuits" are trained to recognize success or failure patterns and give us a good feeling of what the next decision should be. Unless we totally fool ourselves.

For example, we're easily fooled by randomness, thinking we understand how probabilities work. In 1913, in a casino at the Roulette wheel, the Black color came out 26 times in a row! Can you imagine the number of people who put all their money on the White after the tenth or fifteenth time,... Even if you're reminded that each draw is independent from the previous one, wouldn't you bet all your money too?

That's not the only situation where we should make better use of our reason. Behavioral science has now plenty of evidence showing how limited our rationality is:

we sometimes just don't learn from failing patterns. In some crisis situations, when emotions are high, we keep doing the wrong thing despite any adverse evidence. It's just impossible to think out of the box.

we're generally very bad at understanding probabilities. For example, if there are 10 lottery tickets at 10$ and the reward is 200$, there's no reason not to play. But if we learn that we buy one ticket while another guy/gal buys the remaining 9 tickets we usually find the situation unfair and we don't play!

we're subject to "framing issues" and "loss aversion". Will you prefer your doctor to say that you have 20% chances to die or 80% chances to live?

The solution here is to use our frontal precortex and really try to take rational decisions knowing our natural biaises and weaknesses.

Is there anything we can use out of this for programming?

Programming is a highly rational activity, but not always. Let's not forget to use our frontal precortex when:

we have "impossible" bugs. Especially under pressure, we're can sometimes be completely stucked on a bug just thinking: "this is impossible!!!! I'm doing A, I should have B!!!!". In this situation the best is to stop and brainstorm. Try to come out with as many ideas as possible. Then carefully select and experiment each of them. There's no magic in programming, things happen for a reason, so let's try to find it fast!

we're tuning for performance. Performance tuning should be as scientific as possible. If I have the feeling that X could be slowing down my system, I shouldn't tweak anything unless I have real evidence that X is the culprit

we're interacting with others and our ego gets in the way

Too much information

Rationality= good. Too much rationality = bad.

Yes, this not obvious but for example, too much information is not the necessary ingredient for a good decision:

some clients are tasting and comparing strawberry jams. They do a first ranking of their preferences. Now we ask them to think about why they like them and the rankings are completely changed! I have the feeling that this is related to Condorcet's paradox.

numerous studies suggest that "experts" may not be good predictors of what's really going to happen in their field (well, also because they can be biaised by their own opinions)

before MRI, doctors were sending patients with back pains to rest for a few days. Now they can see inside the body they suggest surgery and medecine. Even to well-being patients!

Is there anything we can use out of this for programming?

Focus!

when tuning performance, it is very easy to be completely overwhelmed by data. I would suggest taking one "red flag" only (like a display issue) and making a thourough analysis of that only issue until it is completely explained, ignoring what's not relevant

lean programming suggests that accumulating huge backlogs of features and issues may not be the best and most way to make decisions. One reason is that we're very sensitive to irrelevant alternatives.

Conclusion: Emotions vs Reason?

I really learned something with that book. When too many rational criteria come up to my mind on which book I should buy, I'm just losing my time and most probably I am going for a bad choice. I'd rather let my emotions drive me and learn instinctively what a good decision is for me (talk about an obsessional guy,...).

In conclusion, the debate is not such much "emotions or reason" but more why and how we use both of them to make our decisions.

An exercise with arrows in Scala

2009-02-13T23:28:00.016+09:00

I'm still a bit fascinated by the so-called "computing models" that you get when programming with monads or arrows.

That fascination comes from that fact that the things I'm using everyday can be abstracted to useful entities. Of course, it is pretty well-known to programmers that functions can be described formally with parameters, types, return values and so on. Given the definition of functions you can even compose them and create a useful function out of 2 other ones.

But I was pretty amazed, when reading the paper from John Hughes on Arrows, to see that there are lots of properties and combinators that you can define for your basic computing blocks. And that these combinators, defined at an abstract level, can then be used to structure the concrete and dirty work of your everyday functions.

The Challenge

3 few weeks ago, I was intrigued by the small challenge brought up by Debasish Gosh, about translating one Haskell snippet to Scala. The function clusterBy, in Haskell, is defined by:

clusterBy :: Ord b => (a -> b) -> [a] -> [[a]]

clusterBy f = M.elems . M.map reverse . M.fromListWith (++) . map (f &&& return)

Basically, it takes a list of elements and returns a list of lists, where the elements are grouped according to their result via a function. If 2 elements have the same result with f, then they end up in the same list. For example:clusterBy length ["ant", "part", "all"] => [["all", "ant"], ["part"]]That example looked interesting to me for 2 reasons:

that's not the kind of thing that you program in one line with Java
it uses Arrows and I remembered that some code for Arrows in Scala was available

So I set out to rewrite the clusterBy function in Scala, using Arrows.

The solution

Here's my solution (partial here, read more at the end):

def clusterBy[A, B](l: List[A])(f: A => B) =

  (listArr(f &&& identity) >>> arr(groupByFirst) >>> arr(second) >>> arr(reverse))(l)

And the clusterBy function in action as a specs expectation:

clusterBy(List("ant", "part", "all"))(_.length) must beEqualTo(List(List("all", "ant"), List("part")))

Let's dissect the clusterBy function to understand what exactly Arrows are bringing to the table.

"Lifting" a function to an Arrow (what the h...?)

First of all, for our understanding, we can remove some noise:

arr(groupByFirst) is just taking a function, groupByFirst, and "lifting" it to make it an Arrow object which can play nicely with other arrows using the >>> operator.

There are implicit definitions in the Arrows object transforming functions to Arrows but unfortunately type inference didn't seem to authorize me the removal of arr(...). If I could do it, I would get something like:

def clusterBy[A, B](l: List[A])(f: A => B) =

 (listArr(f &&& identity) >>> groupByFirst >>> second >>> reverse)(l)

>>>, the "sequence" operator

How should we read that expression now?

The >>> operator reads very easily. It says:

f1 >>> f2 => take the result of f1 and give it to f2.

It is the equivalent of the composition operator, except that it reads the other way around, from left to right. With composition we would have "f2 . f1". The >>> operator (arguably) follows the natural reading flow (well, in English at least,...).

&&&, the "branching" operator

The next important operator is &&&:

f1 &&& f2 => A function with takes an input and returns a pair with the results of both f1 and f2.

So (f &&& identity) in our example simply takes an element and creates a pair containing the result of the application of f and the element itself:

(f(x), x)

But what we want to do is to apply this function (an Arrow more precisely) to the list of elements which is our input. That's exactly what listArr does! It creates a Arrow taking a list (read "enhanced function") from a function taking a single element.

Reading the whole expression in detail

With all that knowledge, let's read again the definition now with our example as an illustration.

The input data is:

List("ant", "part", "all")

"take the list of elements and return (f(x), x) for each element":

listArr(f &&& identity)

=> List((3, "ant"), (4, "part"), (3, "all"))

"then group by the first element", i.e. create a list of pairs where the first element is f(x) and the second element is a list of all y where f(x) == f(y))

>>> groupByFirst

=> List((4, List("part"), (3, List("ant", "all")))

"then take the second element"

>>> second

=> List(List("part"), List("ant", "all"))

Note that the "second" function defined here just takes the second element of a pair. This means that the >>> operator is smart enough to know that we're operating on lists of pairs and not on a single pair!

"then reverse the list"

>>> reverse

=> List(List("ant", "all"), List("part"))

The hidden stuff under the carpet

To be able to create this nice one-liner in Scala, I had to create special-purpose functions: groupByFirst, reverse, second.

First of all, you can argue that the real meat of the clusterBy function is actually the groupByFirst function:

def groupByFirst[A, B] = new Function1[List[(A, B)], List[(A, List[B])]] {

  def apply(l: List[(A, B)]) =

    l.foldLeft(new HashMap[A, List[B]]: Map[A, List[B]]) { (res: Map[A, List[B]], cur: Pair[A, B]) =>

val (key, value) = cur

      res.update(key, value :: res.getOrElse(key, Nil))}.toList

}

And actually if you look at Debasish's blog, there are full Scala solutions that fill the same space as the groupByFirst function. On the other hand, I find that the Arrows notation shows pretty well the process flow between "elementary" functions.

Then you can wonder why I couldn't basically "detach" the reverse operation from the List class, like this maybe?

def reverseList[T](l: List[T]) = l.reverse

def reverse[T] = reserveList _

However, this just doesn't work because the type inference seems to be not constrained enough when it comes to sequence the functions with the >>> operator. The only way I found to have this working was to define a Function1 object:

def reverse[T] = new Function1[List[T], List[T]] {

  def apply(l: List[T]) = l.reverse

}

This last issue is maybe the biggest drawback when using Arrows with Scala. Now I can propose my own challenge to the Scala community. Can you find a better way ;-) ?...

Doing my homework

2009-01-05T12:46:00.008+09:00

The mapFilter function

I recently tried to write a function using Scala which would apply a function to a list, then filter all the resulting elements according to a criteria. In my infinite wisdom I named it "mapFilter". Here is an example of what I expected:

mapFilter(List(1, 2), (x:Int) => if (x%2 == 0) Some(x*2) else None)
// returns List(4)

Of course I wanted this function to be as efficient as possible so it had to do the job in one pass. Otherwise, I could just use a combination of "map" and "filter" to do the trick:

def mapFilter[T, U](l: List[T], f: T =>Option[U]): List[U] = {

l.map(f(_)).filter(_.isDefined).map(_.get)

3 passes on the list, we can definitely do better than this!

Using flatMap

Somehow I remembered that the Option class is a Monad, and my subconscious related the bind operation of monads to the flatMap operation on Iterable. I should be able to do something with it,...

Then I experimented this:

List(1, 2) flatMap { (x:Int) => if (x%2 == 0) Some(x*2) else None }

Bingo, it works!

Now, if you read the signature of the flatMap method (on the Iterable trait), understanding how this works is not so clear:

def flatMap[B](f: A => Iterable[B]): Iterable[B]

Option is not an Iterable, this shouldn't compile! Yes, it does, because any Option can be implicitly converted to an Iterable thanks an implicit conversion:


object Option {
  /** An implicit conversion that converts an option to an iterable value */
  implicit def option2Iterable[A](xo: Option[A]): Iterable[A] = xo.toList

Sometimes I wish there was a way to display all the available implicit definitions for a given scope,...

Monads again,...

What about the "Monadic" stuff then? Tony Morris, on the Scala mailing-list, left me a message hinting at a purer solution:

Hi Eric,
You can write mapFilter using Scalaz which has a MonadEmptyPlus data
structure. I suggest you do not use the available subversion of the
List.flatMap type signature from which to learn

So I thought that I should do my homework, have a look at it and understand why MonadEmptyPlus was a good way to write the mapFilter function.

You can find all the code from the scalaz project here. The package I'm exploring today is the "control" package.

A bit of Scalaz exploration

Let's jump right to the MonadEmptyPlus:


trait MonadEmptyPlus[M[_]] extends MonadPlus[M] with MonadEmpty[M]

Ohhh. We are high on abstraction here, because MonadPlus is:

trait MonadPlus[M[_]] extends Monad[M] with Plus[M]

And MonadEmpty is, as you can guess:

trait MonadEmpty[M[_]] extends Monad[M] with Empty[M]

Last but not least, Monad is:

trait Monad[M[_]] extends Pure[M] with Bind[M] with Functor[M] with Apply[M]

Honestly, I didn't suspect that my homework would take me so long! Yet, since every concept and notion of what is a Monad seems to be carefully crafted in Scalaz, this is a good idea to spend a bit of time trying to understand each of them.

Pure

The Pure trait is defined by:


/**
 * Project the given value into the environment that is abstracted over. 
 */
def pure[A](a: A): P[A]

It actually says that you can take any value of some type A, and using the "pure" function, put it in a "Container" of type P, called the "environment" here. I guess that the idea is to say that once the value is well protected and controlled in its container, it is "pure". That being said, this is still very abstract. Fortunately we have some implicit values in the the Pure object giving us some examples of what it means to be "pure":

 implicit val OptionPure = new Pure[Option] {
  def pure[A](a: A) = Some(a)
}
implicit val ListPure = new Pure[List] {
  def pure[A](a: A) = List(a)
}

A Pure[Option] of the value a is simply the value "a" inside the "Some" container. So if you think of Monads as "Containers" for computation then "pure" is what creates the container with a value inside.

Bind

Bind is the evil twin of Pure and, as far as I'm concerned, the essence of monads because it is the basis of computing with Monads:


/**
 * Binds a function through an environment (known also as sequencing).
 */
trait Bind[BD[_]] {
  /**
   * Binds the given value with the given value through the environment.
   */
  def bind[A, B](f: A => BD[B], ba: BD[A]): BD[B]
}

Every word is important here. You have an "environment" again. This "environment" or "Container" contains values which have been put there using the pure function for example. Now, what you want to do is to apply a function to the value inside the container, without the value leaving it. So you "bind" a function to the environment. Again, concrete examples, given by the implicit values in the Bind object will help us understand what's going on:

implicit val OptionBind = new Bind[Option] {
  def bind[A, B](f: A => Option[B], a: Option[A]) = a flatMap f
}
implicit val ListBind = new Bind[List] {
  def bind[A, B](f: A => List[B], a: List[A]) = a flatMap f
}

When I bind a function to an Option, like Some(4), it is as if I'm doing:


val f = x => Some(x + 2)

bind(f, Some(4))

1. apply the function to the inner element

Some(f(4)) === Some(Some(6))

2. "flatten" the inner result by removing the inner "box"

Some(6)

This brings 2 remarks here:

1. "bind" for a monad is indeed the "flatMap" function of an Iterable in Scala. It maps the value then flatten the results. The big difference is in the function signature. While flatMap is a method on Iterable and accepts a function returning another Iterable, the bind function accepts a "Container" type of any sort and returns the same container type; Binding to an Option will return an Option, binding to a List will return a List ("I suggest you do not use the available subversion of the List.flatMap type signature from which to learn"...)

Functor

2. why is it necessary to have a "bind" operation? If I want to get Some(6) as a result, something like "map" should be enough. True. And this even has a name, this is the "fmap" operation of the Functor trait (also mixed in by Monad):


trait Functor[F[_]] {
 /**
  * Maps the given function across the given environment.
  */
  def fmap[A, B](f: A => B, fa: F[A]): F[B]
}

The "fmap" operation just means transforming the value(s) inside the Container to something else. But the bind operation offers an additional advantage. It allows to compose functions returning values in the Container. I can't compose directly 2 functions returning an Option:

val f = (x:Int) => if (x % 2 == 0) Some(x) else None
val g = (x:Int) => if (x % 3 == 0) Some(x) else None

// this doesn't work since g returns an Option and f expects an Int
val composed = f . g // ??

But I can compose them using "bind":

// this works as expected
val composed: (Int => Option[Int]) = (x:Int) => g(x).bind(f)

Apply

The definition of Apply is this one:


trait Apply[AP[_]] {
  def apply[A, B](f: AP[A => B], fa: AP[A]): AP[B]
}

And a good example is provided for Lists:


implicit val ListApply = new Apply[List] {
  def apply[A, B](f: List[A => B], a: List[A]) = f flatMap (f => a map(f(_)))

We take a list of functions, a list of values, and we return a list with the results of all the functions applied to all the values. Actually this is the essence of the "Applicative" model of programming, so I don't really understand why it's been added to the Monad trait. I guess it is because monad computations imply applicative computations as described here.

Empty and Plus

Now that the tour of Monad is over, we can look at the Empty and Plus traits.

Empty is very easy, it just returns an empty "Container" (named "Environment" here):

trait Empty[E[_]] {
  /**
   * Returns the empty environment.
   */
  def empty[A]: E[A]
}

implicit val OptionEmpty = new Empty[Option] {
  def empty[A] = None
}

implicit val ListEmpty = new Empty[List] {
  def empty[A] = Nil
}

Plus defines what it means to "append" or "merge" two environments together. Its result is very specific to the underlying Container type as you can see with the implicit values:


trait Plus[P[_]] {
  /**
   * Appends the two given values.
   */
  def plus[A](a1: => P[A], a2: => P[A]): P[A]
}

implicit val OptionPlus = new Plus[Option] {
  def plus[A](a1: => Option[A], a2: => Option[A]) = a1 orElse a2
}

implicit val ListPlus = new Plus[List] {
  def plus[A](a1: => List[A], a2: => List[A]) = a1 ::: a2
}

Empty and Plus are indeed defining some kind of addition operation on Monads, aren't they?

The real academic mapFilter function ;-)

With all that at hand I should now be able to create my mapFilter function ;-)


import scalaz.control._
def mapFilter[T, A[_], U](f: T => A[U], m: A[T])(implicit m1: MonadEmptyPlus[A])= {

  m1.bind(f, m)
}

Is that all? Yes, let's try it:


// Note that Scala type inferencer doesn't infer the types here
mapFilter[Int, List, Int]((x:Int) => if (x%2 == 0) List(x*2) else Nil,
                          List(1, 2))

However we may wonder: is that really necessary to have a MonadEmptyPlus? No, a simple Monad is also ok:


def mapFilter[T, A[_], U](f: T => A[U], m: A[T])(implicit m1: Monad[A]) = {

m1.bind(f, m)

And that's understable with the List example because we're using "flatMap" under the covers! But this is not totally satisfying. Somehow, I would like to enforce that if f returns the empty element for a given MonadEmptyPlus, then that element is filtered from the result.

Even better with FoldRight

We can actually define this using another abstraction from the control package: FoldRight.


trait FoldRight[F[_]] {
  /**
   * Fold the given function across the given environment.
   */
  def foldRight[A, B](t: F[A], b: B, f: (A, => B) => B): B
}

FoldRight works exactly as the foldRight method on Iterable in Scala and allows us to use the Empty and Plus definition from MonadEmptyPlus, accumulating the mapped values, unless they're empty:


def mapFilter[T, A[_], U](m: A[T], f: T => A[U])
                         (implicit m1: MonadEmptyPlus[A], f1: FoldRight[A]) = {
  f1.foldRight[T, A[U]](m, m1.empty, (t, result) => m1.plus(f(t), result))
}

And that's the end of the assignement for today!

Conclusion

This exploration of Scalaz was very interesting for me because:

The abstractions are nicely separated
Implicit values provide lots of concrete examples
The programming style is very close to the use of type classes in Haskell (which wraps my mind in a new way). The drawback is less type inference by Scala
I had to think again about that "bind" function and why it was so special
It gives me the desire to understand more deeply what are the differences between the so-called "models of programming": functor, monads, applicative, arrows,...
I haven't been blogging for a looooonnnnng time.

Commando programming

2008-10-15T04:55:00.014+09:00

When you program for a trader you don't have time to write tests

I've been wondering for some time if the quote above, or a variant like: "you don't have time to refactor your code", was really true or not. I generally bug my colleagues when they don't write tests along with their code and I usually prophetize that they will actually spare time by writing tests instead of losing time.

Unfortunately I don't have strong evidence if this is true or not. The only thing I can say is that almost every time I've tried to take shortcuts in my developments, I've been bitten by very silly bugs and regretted my recklessness!

Anyway, what would you do if you had to code at the speed of light for a drug-addict trader (and they really need drugs those days,...)? What kind of practices would you adopt to go faster? How would you prepare yourself for those situations?

With those questions in mind, I was happy to be recently involved in a one week project where the biggest part of my job was to do some "Commando programming" to create the necessary tools to support the project.

In this post, I'll do my own retrospective of that project and try to highlight the points which I think are decisive in the context of "Commando programming". Actually most of the "Ding!" points (does that ring a bell to you?) below are applicable to any programming situation. The only difference is that there's no time for preparation in a "Commando" situation. You have to be seriously fit for the job.

This post is too long, that's the Steve Yegge syndrom,... So here's a summary of the take-away points, so you can get a first impression if it's worth reading or not:
Ding! Know your destination
Ding! Be a fast code-reader
Ding! Know at least one scripting language really well
Ding! Know your platform ecosystem
Ding! Don't rewrite anything
Ding! Take careful risks and prototype
Ding! Have at least one high-level functional test
Ding! Test the difficult stuff
Ding! Isolate the file system
Ding! Use the console
Ding! Have lots of sample data
Ding! Time is money, concepts are time
Ding! PPP: Practice, Practice, Practice!!!
Ding! Cool down and document/review your code
Ding! Cool down and take a break

The project: go see your doctor, now!

In my company we've setup a methodology and a set of tools to assess the performance of our customers deployments and one of them asked us to come over for one week to deploy this so-called "HealthCheck" process. After the first initial interviews, we determined that one very essential objective of the project was to reduce the time to save a trade from 1.2 seconds to less than 500 ms. Very clear and quantifiable objective, that's a good start!

Ding! Know your destination

First point here, this may look totally obvious but still it needs to be said: the overall user objective must be very clear for everyone.

This point is important for at least 4 reasons:

It's hard to say that you're going fast if you don't know where you're going!
The fastest development in the world is the one you don't do because you don't need it
It helps a lot, as seen later, to have a clear overall objective when negotiating with yourself or with your customer the next micro-task to develop
Developing fast is not the alpha and omega of productivity. Seeing the project from its overall objective can make you realize that saving other people's time may actually more important than saving your own

Reading the thermometer

Assessing the performance of our systems involves parsing and analyzing lots of different log files: client requests, server requests, database requests, sql execution times, workflow times, garbage collection times,... The scripts we started working with were shell scripts doing the following:

Reading and managing log files, including archiving old versions
Parsing the files and extracting the time spent for a given "quantity" (client request, SQL call,...)
Computing small statistics: minimum / average / maximum time
Creating graphs in order to be able to spot "spikes" that we will be able to label as "Red flags"

The scripts we had were doing the job, but were pretty slow considering the amount of data we had to process. More than one hour could be spent just running the scripts on a subset of the log files.

Analyzing the scripts, I thought that I could implement something more effective,(...)

Ding! Be a fast code-reader

Commando programming may involve reading a lot of code that's not yours before being able to do anything else. This has been written before: we usually spend far more time reading code than writing it. Reading code faster will necessarily speed you up.

(...) more effective so I started prototyping something using Ruby. Why Ruby? Because I knew I would be fast to implement my ideas with it. Or was I?

Ding! Know at least one scripting language really well

No, I wasn't so fast,... I haven't programmed in Ruby for quite some time and I've forgotten many of the idioms or methods of the core api. My head is so full of Scala nowadays, that I would certainly have been faster using Scala for that task. The morality here is that knowing a "scripting" language is very helpful but you really need to have everything in your mental RAM in order to be effective.

This goes for api knowledge as well as "environmental" knowledge: you should spend no time figuring out how to develop/build/test/deploy your code. Being stuck for 2 hours because you don't know how to set a class path for example is a huge waste of value.

Anyway, I was able to show the effectiveness of using a language like Ruby to speed up the analysis time so I decided to officially port the scripts from shell to another language. But now which language should I select for my commando developments?

Choosing a language is a vast question and the criteria governing that choice may not be entirely related to the intrinsic language features. This choice may also be governed by more "contextual" considerations, like the ability of other developers to learn the language and associated tools.

In my case, Groovy was the winner for 4 reasons:

It has all sort of features to help write code faster like closures, literals,...
It can access Java libraries and I was planning to integrate some Database analysis tools we had written in Java
That's one of the closest language to Java on the JVM so other developers will be able to pick up the new scripts faster. And it is usually better known than JRuby, Scala or Jython for example

Ding! Know your platform ecosystem

I also knew, when choosing Groovy, that I would be able to use all sorts of niceties. One of them was the Ant integration which allowed me to easily reuse the exec task (see below). Knowing my way around Ant was a good thing (I know that's not exceptional for a Java developer, it's just an example ;-) ).

Rewrite everything?

That was the most "dangerous" part of this project.

I would honestly have preferred avoiding it. Since I had to replace one small part of the scripts with some new Groovy logic and also, since the scripts would need to be extended anyway, I decided to rewrite them all in Groovy.

Ding! Don't rewrite anything

Haha, I just said I did it! Well, not that you can never rewrite code or some library part, but you have to be damn sure about what you're doing. So,...

Ding! Take careful risks and prototype

Doing "Commando programming" will undoubtedly require taking risks and trying out some solutions before going on. More than ever, it needs to be done with lots of care because the last thing you want, is to find yourself in the middle of the road at the end of the week, because you didn't have time to finish implementing your new "Grand Vision", whatever it is.

In my case I mitigated the risks a lot by "wrapping" the existing shell commands in my Groovy scripts. So I was essentially running the same thing but executed from Groovy! That was really worth it because in the process, I could also reduce a lot the existing amount of code thanks to the usual Groovy tricks.

Test or not to test

Now we come to the meat of the discussion! TDD, BDD, unit tests, code-and-see, what should be done? I honestly don't have a definitive answer but here's what I did.

Ding! Have at least one high-level functional test

You need to have at least one high-level functional test guiding you in your developments. Something which you can come back to and say: "this case still doesn't pass, I'm not finished yet". You may actually have implemented more code than just what was necessary to pass that test case but at least this primary use case should be ok.

Ding! Test the difficult stuff

Complex logic is definitely something you want to isolate and test early. If you don't unit test it thoroughly, it will usually haunt you in the most painful way: hidden inside all the rest. Besides, this complex logic usually means "value" for your customer, more than anything else, so it's worth cherishing it.

Ding! Isolate the file system

Actually, you should soon realize that any interaction with the file system is slowing you down.
Being able to mock the file system, or to write to temporary files with automatic clean up is a huge time-saver for unit testing. In a "Commando" situation you would be prepared with this and have all sorts of functions and ready to use design to help with this. In my case, I had to write all lot of it,...

Ding! Use the console

The Read-Eval-Print loop. In my developments I found very useful to test interactively my regular expressions inside the Groovy console. Whether or not I turned those expressions to actual unit tests,... I didn't do it all the time I must say. One reason is that, once I had confidence that this regular expression was encapsulated in a higher-level concept, like "extractClassName", it would be right forever.

Ding! Have lots of sample data

If possible try to gather as much sample data as you can and run it through your program. Does it blow-up right away? Well, that's actually good, it may be the sign that you forgot a requirement. Instead of spending time trying to refine your requirements until they're exhaustive, or try to think about all possible cases, run the system with the maximum data available. There are 2 drawbacks to this: one is the time spent re-executing large datasets and analyzing failures, the other is not knowing what to look at! Your program may not break with enough smoke to prove you wrong.

On my project I had lots of log files I could run my scripts against. And fortunately my scripts broke in very unambiguous ways, showing where I was wrong.

To design or not to design

So you're programming like hell, you don't have time to draw all those nifty UML diagrams or devise the best design patterns for the job. "We'll design when we'll have time."

But is it really buying you time? I don't think so. I'm not saying that you should write diagrams or add tons of interface and clever indirections.

But you need design in the sense that the problem and solution domains should be very, very clear to you.

Ding! Time is money, concepts are time

So it's worth taking a bit of time and think: "What's really this system like?". Clarifying the concepts is very, very important. For us, it was first of all giving proper names to our analysis concepts:

An entity can have measurable properties ("A trade server has requests")
For each property, you can define several quantities ("each request can take some average time")
For a given "Test environment", we can run several "Test campaigns"

This helped a lot in our discussions, in structuring the scripts and planning our actions.

The next step was to realize that the type of queries we wanted to execute to analyze logging data looked pretty much like SQL queries: "between 15:00 and 15:03. return all update queries with a time > 300ms and group them by workflow rules". This gave us a good hint that the next step for our scripts would be to put everything in a database!

Coding

Consider this:

"I know where I'm going, I have a clear mind about my system and it's concepts, I know how to write minimal and effective tests, is there anything more I could do now to speed up my coding?"

Let's reformulate the sentence above:

"I know I want a gold medal at the Olympics, I know I'll get it by being a table tennis champion and I know the rules of the game, I have a very good racket, is there anything more I could do now to be the best at table tennis?"

Ding! PPP: Practice, Practice, Practice!!!

That's so obvious I'm ashamed to have to write it,... but that makes a real difference for "Commando programming":

technique: practice your regular-expression-fu for example, or know how to write a parser for a simple language (I planned to do that for the verbose gc logs but we didn't have time nor interest to rewrite this part)
libraries: no time should be spent looking at the API docs
tools: if you need remote debugging, it should be fast to setup, because you did it thousands of times before
computer science: you should have at least a good sense of the complexity of your algorithms
integration: how to call Excel from Groovy to create graphics was one of our coding issues
system / network tools: that wasn't too necessary on our project, but I can imagine this making a real difference in other settings

Cooling down for a minute

Two things of equal importance I've also noticed during that week. First of all, when I tried to go fast I couldn't help but noticing entropy. Yes my code was doing the job, but at the same time it wasn't always consistent, documented, properly named or refactored.

Ding! Cool down and document/review your code

This really can look like a pure loss of time. But I really observed that it wasn't. For 2 reasons:

Actually it doesn't take that long to review/document/refactor the code (try it at home)! Except maybe for the naming part, it's a bit like playing sudoku, you just try to make things fall into place
I observed that I was much less dragged down implementing new feature on clear-cut code with obvious intentions, I had much less mental noise. You know, like: "This computeTotal function is actually also sorting the results, so I know I don't have to do it there". If computing and sorting are better separated or named, that can reduce the "mental tax" while reasoning about something else.

The second thing is the equivalent of "cooling down the code",... applied to your body!

Ding! Cool down and take a break

We're not machines. I was so enthusiastic with that project that I almost coded day and night (and I was away from my family,...). But I also observed one very interesting phenomenon: time was slowing down! Sometimes I was just starring at my screen without realizing that 5 minutes had passed without doing nothing substantial. That should be a clear signal for taking a break. This gives me an interesting idea: "stopwatch" programming. Prepare the list of tasks you want to program and program features by 5, 7 or 10 minutes cycles. And watch out when you have almost empty cycles.

The doctor says: fit for service

Conclusion for the project: it was very successful (this doesn't happen all the time so I'm glad to report it). We were able to analyze and spot 3 major bottlenecks and give good recommendations so that our maximum saving time was eventually around 400 ms. The tools served us, but actually ours brains served us more.

But what's the biggest room in the world? The room for improvement ;-) ! I think we'll be able to transfer more of that wisdom to smarter analysis scripts in the future.

Back to the original question

When you program for a trader you don't have time to write tests

True? False? At the light of my experience of this project, the first thing I'm really convinced of is the first part of the sentence: "You don't have time"!

And if you don't have time, you can essentially do 2 things:

Observe and experiment: whatever makes you spare time is good. In my case, writing tests is a proven way to go faster for example
Practice, learn, invest: new tools, new languages, new libraries, contests, coding dojos,...

Ok. Thanks for listening, I leave you there, I have to go,... and practice my "Commando-fu"!

My first ICFP contest, Part 2: parser combinators are so cool

2008-07-27T15:14:00.004+09:00

This is the sequel to my last post on participating to the ICFP contest 2008.

The Setup

As Curt wrote it, we entered the contest doing things that should have been done well before:

setting up the wifi access so that I can connect with my laptop (it never worked so Bryan had to get out and buy new network cables)
exchanging keys to access the Subversion repository
learning how to use the build and test system

I guess that we need to make some mistakes (at least) once oneself before getting it!

However, the biggest lesson for me in this contest, was the use of Parser Combinators.

Do you speak Martian?

The second programming task in the contest, after setting up the network connection to be able to receive messages and send back commands, was to parse the input messages giving the position of the Martian rover, and its immediate environment.

As the task specifies, there are 5 kinds of messages:

initialization messages -> what's the map like? what are you technical constants?
telemetry stream -> where are you, what's your speed, what's around?
adverse event -> crashed in a crater!
success -> yes, home!
end of run -> time and status

The format of those messages is not particularly complex but the telemetry message can contain an unlimited number of obstacles descriptions for example.

For many developers, the most obvious way to transforms meaningless strings to meaningful objects like Telemetry or Martian, would be to start traversing the string, check for characters like 'T' for Telemetry, or 'I' for Initialization then pass the rest of the string to another function and continue slicing the string until all data is analyzed.

Parser combinators

But Haskell developers know better,... They can just describe the grammar of the messages they're parsing by combining parsers, then applying the resulting parser to the string input.

Something like that:


telemetry :: Parser Message
telemetry = do ts <- int
               state <- accelStateParser
               turning <- turningStateParser
               spaces
               x <- double
               y <- double
               dir <- double
               speed <- double
               obstacles <- obstaclesParser
               messageEnd
               return $ Telemetry ts state turning x y dir speed obstacles

accelStateParser :: Parser AccelState
accelStateParser = (accelerating <|> braking <|> rolling)

accelerating = stateParser 'a' Accelerating
braking = stateParser 'b' Braking
rolling = stateParser '-' Rolling

stateParser :: Char -> a -> Parser a
stateParser c cons = do _ <- char c
                        return cons

turningStateParser :: Parser TurningState
turningStateParser = hardleft <|> softleft
                         <|> hardright <|> softright
                         <|> straight

hardleft  = stateParser 'L' HardLeft
softleft  = stateParser 'l' SoftLeft
hardright = stateParser 'R' HardRight
softright = stateParser 'r' SoftRight
straight  = stateParser '-' Straight
obstaclesParser :: Parser [Object]
obstaclesParser = do l <- many obstacleParser
                     return l

obstacleParser :: Parser Object
obstacleParser = do code <- oneOf "bchm"
                    spaces
                    case code of
                         'b' -> object Boulder
                         'c' -> object Crater
                         'h' -> object Home
                         'm' -> martian
                         _   -> error "Can't get here in parser!"

object :: (Circle -> a) -> Parser a
object cons = do x <- double
                 y <- double
                 r <- double
                 spaces
                 return $ cons (Circle (x:.y) r)

martian :: Parser Object
martian = do x <- double
             y <- double
             dir <- double
             speed <- double
             spaces
             return $ Martian (Circle (x:.y) 0.4) dir speed

In the above code, you can read that the parser for telemetry messages is a sequence of different parsers: a timestamp parser, a acceleration state parser, a turning state parser, ..., a parser for lists of obstacles. And a parser for list of obstacles is just "many" parsers for one obstacle. This is indeed as easy as being able to describe a grammar for that mini-language.

"k" should better be 1

But I didn't say that describing a grammar was easy! For instance, at first, we made a mistake in the way we managed spaces. We had almost each parser trying to consume spaces before doing its job. This generated unnecessary ambiguity in the parsing.

For example, let's say that you want to be able to parse this kind of message:


" O T O O T"

(honestly, I don't know why you would like to do something like that but you're the boss here)

You'd better combine those 3 parsers:

spaces -> will consume any number of spaces

oneParser = char 'O' >>= spaces -> will consume 'O' followed by any number of spaces

twoParser = char 'T' >>= spaces -> will consume 'T' followed by any number of spaces

If you define parsers differently, having "oneParser" and "twoParser" consuming spaces before they parse their character, which parser should be used on the first space of the message?

Actually, parser combinators in Haskell are also capable of backtracking and "unparsing" results if the chosen parser was not appropriate (trying things with the the "try" parser combinator). But why add more complexity when things can be described more directly?

Of course, there is a formal theory behind the example above: LL(k) grammars, where LL(1) is a type of grammar only needing to look at the next character to know which parser to use. But there's nothing like a simple "real-life" example to be able to grasp it.

Compare and contrast

Now, honestly, most other contest solutions were not using Parser combinators and the aren't soooo ugly (in Dylan for example). I think they're just less readable and more error-prone because of index manipulation.

For fun and comparison, I also developed a similar parser in Scala:


  def telemetryMessage = for { timestamp    <- intNumber
                               accState     <- accelState
                               turnState    <- turningState
                               vehicleX     <- doubleNumber
                               vehicleY     <- doubleNumber
                               vehicleDir   <- doubleNumber
                               vehicleSpeed <- doubleNumber
                               obstacles    <- objects }
                          yield Telemetry(timestamp, accState(), turnState(),
                                          vehicleX, vehicleY, vehicleDir, 
                                          vehicleSpeed, obstacles)
                        
  def accelState = (  
      "a" ^^^ Accelerating
    | "b" ^^^ Braking
    | "-" ^^^ Rolling
  )
 
  def turningState = (  
      "l" ^^^ SoftLeft
    | "L" ^^^ HardLeft
    | "-" ^^^ Straight
    | "r" ^^^ SoftRight
    | "R" ^^^ HardRight
  )

  def objects = rep(objectParser)
  def objectParser: Parser[Object] = (
      "b" ~ spaces ~> circleParser ^^ (new Boulder(_))
    | "c" ~ spaces ~> circleParser ^^ (new Crater(_))
    | "h" ~ spaces ~> circleParser ^^ (new Crater(_))
    | "m" ~ spaces ~> martianParser
  )
     
  def circleParser = for { x <- doubleNumber
                           y <- doubleNumber
                           r <- doubleNumber }
                     yield new Circle(x, y, r)
                    
  def martianParser = for { circle <- circleParser
                            dir    <- doubleNumber
                            speed  <- doubleNumber }
                      yield new Martian(circle, dir, speed)

The interesting things in the Scala implementation, although it could seem a bit ugly at first sight, are:

the use of a sequence operator "~>" getting rid of what has already been parsed. Indeed, when we have parsed "b " we know we need to create a Boulder object. The 'b' character and the space are then not usefull anymore

the use of functions to transform the parsed string into a meaningful object, like "l" ^^^ SoftLeft, creating a new SoftLeft object (it's a case class) when parsing "l"

implicit definitions. In the example above I don't need to declare my parser for 'l' as letter("l"). Combining "l" with another parser automatically creates a parser for the character 'l'

Why XML?

One of the reasons for the ubiquitous adoption (and hate!) of XML is, I think, the general availability of parsers and binding libraries. This is why this often becomes the easiest option for configuration files (is it changing with YAML and JSON?).

It doesn't have to be that way. I hope that parser combinators can now bring another legitimate option when considering the implementation of an external mini-language for configuration or protocol. They're simple to use and readily available on your Java platform through Scala. Try them at home!

My first ICFP contest, Part 1: ten days to learn Haskell

2008-07-08T22:32:00.006+09:00

I wanted to do that since I read Tom's Moertel post on his participation to the ICFP contest 2001. I Told my wife: "One day, I'll participate to the ICFP contest" (head slightly tilted up with a brilliant and determined look in the eyes).

One day, I'll participate to the ICFP contest

Fortunately, that day came quick as I met, last month, other geeks in Tokyo ready to get into the race. I should say über-geeks when I realize the gaps I have in my knowledge of some fields of computing compared to them. System and network programming being only the emerged part of the iceberg.

I met them for the first time during the monthly meeting of the Tokyo Society for the Application of Currying (try to explain that to your grandma). That night we decided that we would form a team for the next ICFP contest. Then, we spent the next week discussing the team name, that was the difficult decision. The easy one was the language we would use. What is THE language of choice for functional hackers? Haskell of course! [flaming starts here]

But how do you learn Haskell in 10 days and hope to be able to contribute at least a little?

Learn Haskell in 10 days!

Actually, I've reading about Haskell for a while now, starting with the very enjoyable A History of Haskell: Being LazyWith Class. From there and working with Scala for the past year, I had understood the following:

the "functional" approach vs the "sequential" approach
immutable data structures
functions as first-class objects
lazy evaluation
thinking in types
thinking in higher-ranked types
Options / Maybe
List operations: map, folds,...
pattern matching
type classes / traits

This makes an impressive list of language features but I must say that Scala is a really "transitional language" for Java programmers towards Haskell. Riiiight. I "understand" it but how well can I program within 10 days?

The laundry list

Using a programming language always involves a wealth of down-to-earth considerations worth getting right as fast as possible. Here is my list and how I organized my environment:

the compiler: I used GHC and the Hugs interpreter for Windows
the editor: I used the Functional plugin for eclipse, providing editing, compilation, creation of an executable
the librairies: I downloaded / compiled and installed QuickCheck2 and otherwise used the bundled libraries with GHC
code coverage: hcp (not really indispensable for a beginning but a nice to have for a non-strict language. I was happy to eventually get it to work)

This is clearly non-optimal yet (and I wonder if it can be on Windows?) and I'll certainly explore:

a better editor: considering what can be done in Java, it's pretty amazing that there is no high-class editor for Haskell. I'll try Yi of course, but it's still in its infancy. "Rename function" or "Rename data type" should be pretty accessible (provided enough open-source or company support, that is,...)
a build/test/continuous integration system. The guys from Starling Software have their own system for that matter (QAM) and I haven't seen yet such a standard thing for Haskell.
more libraries, libraries management: I still haven't done it on windows but I plan to install Cabal and download the whole Hackage.
Switching to linux forever. I'll certainly cover this in part 2 but Windows seems less and less a decent alternative for hackers (I didn't say developers ;-) ).

Yes, all set-up! I can start my first tutorial!

No, I'd rather do a code dojo first

Why bother using a tutorial when I have a nice little programming exercise at hand? I did it in Java, I did it in Ruby, I did it in Scala, it was time to use Haskell.

Basically the question is: write a program to transform Roman number back and forth to Integers: unromanize("MCMLXXII") == 1972.

Here is my solution with Haskell:



-- SOME VALUES DECLARATION
-- definition of the roman letters with their numerical value
romansList = [("I", 1), ("IV",4), ("V", 5), ("IX", 9), ("X", 10), ("XL", 40),
              ("L", 50), ("XC", 100), ("C", 100), ("CD", 400), ("D", 500), 
              ("CM", 900), ("M", 1000)]
-- numerical values only
values = map snd romansList
-- letters only
letters = map fst romansList

-- return the value corresponding to a letter
value :: String -> Int
value c = findWithDefault 1 c (fromList romansList)

-- return the letter corresponding to a value
letter :: Int -> String
letter i = findWithDefault "I" i reversed       
          where reversed = fromList(map switch romansList)
                switch = (\(x, y) -> (y, x))

-- to get the value of a RomanString, start
-- from the end and accumulate the value of each letter
-- substract the value of the current letter if its value is
-- inferior to the previous one
-- ex: "XIV" -> 5 (for "V") - 1 (for "I") + 10 (for "X")
unromanize :: String -> Int
unromanize s = fst(foldr add (0, 0) s)

add :: Char -> (Int, Int) -> (Int, Int)
add c (total, lastElem) = 
    if (lastElem <= val) then (total + val, val)                           
                         else (total - val, val)
                           where val = value [c] 
                           -- [c] is the Char 'c' as a String   

-- return the RomanString corresponding to an Int value 
-- start with an empty string and the value to convert 
-- use the romanizeString function to compute the RomanString 

romanize :: Int -> String
romanize i = fst $ romanizeString ("",  i)

-- if the remainder is 0, there is no more conversion to do
-- otherwise, try to substract the biggest possible RomanChar from the remainder
-- this RomanChar is then appended to the current result
romanizeString :: (String, Int) -> (String, Int)
romanizeString result@(res, remain) =
   if (remain == 0) then result
                    else romanizeString(res ++ (letter maxi), remain - maxi)
                        where maxi = maxValue remain
                              maxValue r = last (takeWhile (<= r) values)

And here is a simple QuickCheck properties that I wrote to check the conversion:


prop_unromanize_romanize :: Int -> Property
prop_unromanize_romanize x = x >= 0 ==> unromanize(romanize x) == x

First impressions

Working on that simple example (but also on string generators to check the reverse property romanize(unromanize) -- much more tricky) led me to the following observations:

programming in Haskell really "feels" pure and elegant. There is an economy of symbols which is quite remarkable for such an expressivity

not having variables feels like programming in a straight jacket when coming from an imperative background! But the feeling disappears quickly

the "functional/data" orientation makes a whole different mental model when you come from an object-oriented perspective. It looks like your objects, encapsulating their data and showing only their business logic have been turned inside out and methods carefully separated from data.

browsing the libraries feels like there a huge drive towards abstraction in Haskell. Nowhere else I've seen concepts decomposed so that Monoids would emerge and be reused

new language, new librairies. It really takes time but Haskell libraries are full of jewels which are really worth knowing inside out (the same can certainly be said from many languages)

although the Prelude contains a lot of useful functions, some facilities you may find in scripting languages are missing. We recently discussed the lack of a "split" operation for Strings on the Haskell mailing-list recently. I know that different people have different semantics for a "split" operation but not including any kind in the standard library feels like it's missing something

the compiler is your friend! It goes at great length explaining you why and where you failed to properly type your program

Go, go, go

After those 2 or 3 sessions of installation and programming I was very far from being able to code on my own for the contest, yet I would be able to pair-up and provide a vigilant pair of eyes on someone else code. Stay tuned for part 2: the contest!

Everyday monads

2008-07-03T22:37:00.009+09:00

Abstraction

Abstraction is the bread and butter of our trade, right? The problem is that when you abstract too much, you don't always know where you came from and why.

You see? The sentence above is already very abstract ;-). Let's try to be more concrete. I want to talk about Monads and the kind of problems they solve:

monads --> powerful abstract beast
problems they solve --> very concrete

A classical code sample

I was trying to fix an issue with our software 2 days ago when I realized that part of my data wasn't valid: "What!? My exposure is not valid, how come!?". A quick look at the code revealed that the validity of an exposure is determined by the following (actually simplified,...):

public boolean isValid() {
   return traded && !matured && 
          !excluded && !internal && leId > 1;
}

Of course I started blaming the programmer: thank you smart boy, I know that my exposure is not valid but would you have the decency to explain me WHY? Is it untraded and/or matured and/or excluded,...?

I quickly realized why more precise error reporting hadn't been written: time to market. Writing big if/then/else and accumulating error messages is tedious, error-prone and boring to the extreme.

Monads to the rescue!

Somehow, that's the kind of problem that Monads can solve. One way to see Monads is to consider them as a convenient way to chain computations:

you put something in the Monad
you apply one or more functions to it, the results stay in the Monad ("What goes in the Matrix, stays in the Matrix" as I've read somewhere)
then you can extract the final result

Here is the use of a Monad (coded in Scala but you could achieve the same kind of effect in Java) to solve the problem:

def isValid(e: Exposure) = { e.traded ?~! ("is not traded") ?~! (!e.matured, "is matured") ?~! (!e.excluded, "is excluded") ?~! (!e.internal, "is internal") ?~! (e.leId > 1, "doesn't have a defined legal entity") } val exposure = new Exposure exposure.traded = false exposure.matured = true isValid(exposure) match { case f: Failure => { println(f.messages.mkString("exposure is not valid because: it ", ", it ", "")) } }

It outputs:
exposure is not valid because: it is not traded, it is matured, it doesn't have a defined legal entity

So, at the (small) expense of changing the operator from && to ?~! and adding a specific message at each step we get a nice failure message indicating precisely what went wrong.

How does this work?

I implemented this cryptic ?~! operator as a small variation of the existing ?~! method on the Can class from the lift webframework.

A Can is kind of box which either be Empty, Full(of something) or a Failure(reason). So when you perform computations on a Can, either:

there is nothing to do (Empty) --> the result will stay Empty or become a Failure
there is a value (Full(value)) --> the result will either stay Full or become a Failure
it is a Failure --> it will stay a Failure, possibly with an additional error message

What are the 2 operations I need on the Can objects? First of all I need an operation to "put a boolean in the monad". Here I have used an implicit definition:

  implicit def returnCan(b: Boolean): Can[Boolean] = if (b) Full(true) else Empty

then I need one method which will either return the same Can if some boolean is true or a new Failure accumulating one more error message:


def ?~!(b: Boolean, msg: String): Can[A] = {
  if (b) this else Failure(msg :: this.messages)
}

What happens if the first boolean expression is false?

an Empty Can is created (representing a failure with no cause yet)
the ?~!(msg: String) method is called and returns a Failure(msg)
when the ?~!(b: Boolean, msg: String) method is called, it either returns the same Failure, or create a new one with one more error message

And what happens if the first boolean expression is true?

a Full Can is created (representing a success)
the ?~!(msg: String) method is called and returns the Full can
when the ?~!(b: Boolean, msg: String) method is called, it either returns the same Full can if b is true, or create a new Failure Can with one error message

What I will not do in this post

Although that would be interesting, I will not try to show why the behavior described above actually correspond to a Monad, with the mandatory Monad laws. The first reason is that it is too late to do so ;-). The second reason is that I'm not sure it matters much. What is certainly more important is that Monads, Arrows, Applicative Functors and their kind provide powerful models of computations which can also be applied to Everyday-Enterprisey jobs.

And, by the way, Scala provides syntactic sugar for operators definition, but there is really nothing which avoid us to do the same thing in Java:



// warning!! pseudo-java code!!
class Result {
  private List messages = new ArrayList();
  private Result(List msgs) {
    this.messages = msgs;
  }
  public Result andCheck(Boolean b, String msg) {
    if (b) return this; 
    else return new Result(messages.append(msg));
  }
  static public check(Boolean b, String msg) {
    return new Result().andCheck(b, msg);
  }
}

public Result isValid(e: Exposure) = {
  check(e.traded, ("is not traded")).
  andCheck(!e.matured, "is matured").
  andCheck(!e.excluded, "is excluded").
  andCheck(!e.internal, "is internal").
  andCheck(e.leId > 1, "doesn't have a defined legal entity")
}

Eureka

I hope I haven't brought more confusion on the topic of Monads with that not-very-formal post. This is a world I'm just starting to explore and I just love when I can have some "Eureka" moments and write better code!

Edit distance in Scala

2008-06-09T10:48:00.004+09:00

How handy.

I was just looking for a way to highlight differences between 2 strings for my Behavior-Driven Development library, specs. And reading the excellent Algorithm Design Manual. Intuitively, I was thinking that there was a better way to show string differences than the one used in jUnit:

Expected kit<t>en but was kit<ch>en

Expected <skate> but was <kite>

The first message shows that <t> has been replaced by <ch>, while the second message says that everything is different! There must be a way to find the minimal set of operations necessary to transform one string to another, right?

The Levenshtein distance

There is indeed. The "Edit" distance, also called "Levenshtein" distance, computes exactly this, the minimal number of insertions, deletions and substitutions required to transform "World" into "Peace" (5, they're very far apart,...).

The computation is usually done by:

examining the first 2 or last 2 letters of each string
assuming the eventual transformation which may occur for those 2 letters:

they're equal: "h..." and "h...." --> distance = 0
the first one has been removed: "ah..." and "h..." --> distance = 1
the second one has been inserted: "h..." and "ah..." --> distance = 1
they've been substituted: "ha..." and "ga..." --> distance = 1

3. saying that the final distance is the minimum of the distance when choosing one the

4 possibilities + the distance resulting from the consequences of that choice

You can notice that many variations are possible: the distance could be different depending on the letters being added or removed, there could be more allowed operations such as the swapping of 2 letters (distance 1 instead of 2 substitutions of distance 2),...

Then the final result can either be constructed incrementally or recursively. Incrementally, for "skate" and "kite" you will compute costs from any small prefix to another prefix:

"s" to "k" --> distance 1
"s" to "ki" --> distance 2
"sk" to "ki" --> distance 2
"ska" to "kit" --> distance 3

Then you increase the prefix size and you reuse the distance numbers found for smaller prefixes. The different results can be stored in the following matrix:

s k a t e

k 1 1 2 3 4
i 2 2 2 3 4
t 3 3 3 2 3
e 4 4 4 4 2

Recursively, you do the inverse and you establish that the distance between 2 strings can be computed from knowing the distance between smaller prefixes and you travel the matrix to its upper left corner.

This is a very good example of Dynamic Programming, where the optimal quantity (the distance at [i, j] in the matrix) you're looking for only depends on:

the optimal quantity for a subset of the data (the distance at [i-1, j-1], [i-1, j], [i, j-1])
the resulting state (the substrings defined by a position [i-x, j-x] in the matrix)
not how you got to that resulting state

The EditDistance trait

For the record, I will write here the code I'm using for the implementation, which is constructing the solution incrementally, as opposed to the recursive solution presented on Tony's blog, here.

The few interesting things to notice about this code are:

the algorithm itself ("initializing the matrix"), which is very straightforward
the minimum function which is a bit strange because it is not comparing all alternatives. The cost for an insertion is only computed if the cost for a suppression is not better than the cost for a substitution. I would like to work out a formal proof on why this is correct by my intuition tells me that a substitution is generally a "good" operation. It has the same cost as an insertion or a suppression but processes 2 letters at the time. So if we find a better cost using a suppression, it is going to be the best
the matrix traversal to retrieve one of the possible paths showing the letters which needs to be transformed for each string: not so fun code with a lot of corner cases
the "separators" feature which allows to select the separators of your choice to display the string differences


trait EditDistance {
  /**
   * Class encapsulating the functions related to the edit distance of 2 strings
   */
  case class EditMatrix(s1: String, s2: String) {
    /* matrix containing the edit distance for any prefix of s1 and s2: 
       matrix(i)(j) = edit distance(s1[0..i], s[0..j])*/
    val matrix = new Array[Array[int]](s1.length + 1, s2.length + 1)

    /* initializing the matrix */
    for (i <- 0 to s1.length;
         j <- 0 to s2.length) {
      if (i == 0) matrix(i)(j) = j // j insertions
      else if (j == 0) matrix(i)(j) = i  // i suppressions
      else matrix(i)(j) = min(matrix(i - 1)(j) + 1, // suppression
                              matrix(i - 1)(j - 1) + (if (s1(i - 1) == s2(j - 1)) 0 
                                                           else 1), // substitution
                              matrix(i)(j - 1) + 1) // insertion
   
    }
    /** @return the edit distance between 2 strings */
    def distance = matrix(s1.length)(s2.length)

    /** prints the edit matrix of 2 strings */
    def print = {
      for (i <- 0 to s1.length) {
        def row = for (j <- 0 to s2.length) yield matrix(i)(j)
        println(row.mkString("|"))
      }
      this
    }

    /** @return a (String, String) displaying the differences between each 
         input strings. The used separators are parenthesis: '(' and ')'*/
    def showDistance: (String, String) = showDistance("()")

    /**
     * @param sep separators used to hightlight differences. If sep is empty,
     * then no separator is used. If sep contains one character, it is 
     * taken as the unique separator. If sep contains 2 or more characters, 
     * the first 2 characters are taken as opening separator and closing 
     * separator.
     *
     * @return a (String, String) displaying the differences between each 
     *  input strings. The used separators are specified by the caller.
     */
    def showDistance(sep: String) = {
      val (firstSeparator, secondSeparator) = separators(sep)
      def modify(s: String, c: Char): String = modifyString(s, c.toString)
      def modifyString(s: String, mod: String): String = { 
         (firstSeparator + mod + secondSeparator + s).
         removeAll(secondSeparator + firstSeparator)
       }
      def findOperations(dist: Int, i: Int, j:Int, s1mod: String, s2mod: String): (String, String) = {
        if (i == 0 && j == 0) {
            ("", "")
        }
        else if (i == 1 && j == 1) {
            if (dist == 0) (s1(0) + s1mod, s2(0) + s2mod)
          else (modify(s1mod, s1(0)), modify(s2mod, s2(0)))
        }
        else if (j < 1) (modifyString(s1mod, s1.slice(0, i)), s2mod)
        else if (i < 1) (s1mod, modifyString(s2mod, s2.slice(0, j)))
        else {
          val (suppr, subst, ins) = (matrix(i - 1)(j), matrix(i - 1)(j - 1), 
                                           matrix(i)(j - 1))  
          if (suppr < subst)
            findOperations(suppr, i - 1, j, modify(s1mod, s1(i - 1)), s2mod)
          else if (ins < subst)
            findOperations(ins, i, j - 1, s1mod, modify(s2mod, s2(j - 1)))
          else if (subst < dist)
            findOperations(subst, i - 1, j - 1, modify(s1mod, s1(i - 1)), 
                                           modify(s2mod, s2(j - 1)))
          else
            findOperations(subst, i - 1, j - 1, s1(i - 1) + s1mod, s2(j - 1) + s2mod)
        }
      }
      findOperations(distance, s1.length, s2.length, "", "")
    }
    def min(suppr: Int, subst: Int, ins: =>Int) = {
      if(suppr < subst) suppr
      else if (ins < subst) ins
      else subst
    }
  }
  def editDistance(s1: String, s2: String): Int = EditMatrix(s1, s2).distance
  def showMatrix(s1: String, s2: String) = EditMatrix(s1, s2).print
  def showDistance(s1: String, s2: String) = EditMatrix(s1, s2).showDistance
  def showDistance(s1: String, s2: String, sep: String) = EditMatrix(s1, s2).showDistance(sep)

  private def separators(s: String) = (firstSeparator(s), secondSeparator(s))
  private def firstSeparator(s: String) = if (s.isEmpty) "" else s(0).toString
  private def secondSeparator(s: String) = {
    if (s.size < 2) firstSeparator(s)  else s(1).toString
  }
}

Conclusion

What's the conclusion? Computer science is useful of course, but you only recognize it once you know it!

Algorithmic panic - take 2

2008-05-08T21:58:00.007+09:00

Shame, shame, shame.

The Blog Writing Rule

Writing at least one blog entry per month. That should be feasible, no? Unfortunately, last Friday, I was already more than 10 days late, so I had to do something!

And, when pressing the "Post" button, I had this awkward feeling that something was not really right with my "solution". Not really on the "speed" side because I knew that my list accesses were sloppy, but even on the "correctness" side. But I was past the date, damn it!

Fortunately, someone's watching

Ok, enough justifications. I was in fact very pleased to get so many insightful comments, be it on my blog, or on reddit. It's a pleasure to see that so many people care for The Truth on the Internet ( ;-) )

So I tried my best to review things up and to derive the maximum number of lessons out of theses errors. I'll start with that, then I'll copy the revised version of the algorithm.

Lessons learned

Check your definitions. The median definition is very straightforward,... if you have an odd number of elements. For an even number, you can elaborate several definitions, such as that one. For the code below, I choose to take define the median as a pair of values, which is both "middle" elements if the list is even. Pairs of values are then conveyed across all computations, so that it's always possible to eventually take the mean value if you feel like it

Don't trust test generation. I promise my tests were green when I posted! However, the generation parameters were very bad: the number of tests was too small, the number and range of elements in the lists also. The solution here was tested on larger samples (up to 8000 tests), with larger lists (of same size or different sizes)

Check your invariants. In this kind of "Divide and Conquer" approach, I should make sure that I have indeed the same problem, on a smaller scale, after dividing it. The code below shows that it is possible to take the same number of elements on each list, so that the median of the resulting lists is unchanged

Know your data structures. I knew that the most basic list was not necessarily efficient but I must say that I didn't check anything. And, in fact, when Jorge pointed out that List had an O(n) access for size, I was quite surprised. The other interesting thing is that optimizing an operation can be totally feasible but quite tricky to implement (see the medianOfSortedListAndOneElement function below). And of course, takeWhile(_) was pretty bad!

The algorithm

First of all, lets start by the definition of the median as a couple of values, which may be the same if the list has an odd number of elements:


  case class ExtendedSeq(list: Seq[Int]) {
    def median: (Int, Int) = {
      if (list.isOdd)
        (list(list.size / 2), list(list.size / 2))
      else
        (list(list.size / 2 - 1), list(list.size / 2))
    }
    def isOdd = list.size % 2 != 0
  }

If elements access and size are O(1) as in the RandomAccessSeq collection, that should be ok in terms of complexity (thanks Jorge).

Here is the heart of the algorithm:


  def median(l1: Seq[Int], l2:Seq[Int]): (Int, Int) = {
    if (l1.isEmpty) l2.median
    else if (l2.isEmpty) l1.median
    else if (l1.size == 1) medianOfSortedListPlusOneElement(l2, l1(0))
    else if (l2.size == 1) medianOfSortedListPlusOneElement(l1, l2(0))
    else {
      val (m1, m2) = (l1.median, l2.median)
      m1.intersection(m2) match {
        case Some(m) => m
        case None => if (m1 < m2) median(trimLists(l1, l2)) 
                     else median(trimLists(l2, l1))
      }
    }
  }

The code above starts by checking some special cases: one empty list, a list + one element, then 2 "regular" median values.

The first observation is that, if the median values (which are pairs of values) have a non-empty intersection, this intersection will be the median of both sorted lists.

This is the not-so readable code for checking if there is an overlap between 2 pairs:


case class ExtendedPair(pair1: (Int, Int)) {
  def intersection(pair2: (Int, Int)) = {
    if (pair2._1 <= pair1._1 && pair1._2 <= pair2._2) Some(pair1)
    else if (pair1._1 <= pair2._1 && pair2._2 <= pair1._2) Some(pair2)
    else if (pair1._1 <= pair2._1 && pair2._1 <= pair1._2 && pair1._2 <= pair2._2)
      Some((pair2._1, pair1._2))
    else if (pair2._1 <= pair1._1 && pair1._1 <= pair2._2 && pair2._2 <= pair1._2) 
      Some((pair1._1, pair2._2))
    else None
  }
}

Finally, if there is no overlap, we need to remove elements from both lists so that the median of the remaining 2 lists will be the same as the median of the original lists:


def trimLists(l1: Seq[int], l2: Seq[Int]) = {
  val removableElements = if (l1.size < l2.size) l1.size / 2 else l2.size / 2 
  (l1.drop(removableElements), l2.take(l2.size - removableElements))
}

This time, I removed the same number of elements below the lower median and above the higher one (but still, a written mathematical proof would be more satisfying than "it's obvious that,...").

On the complexity side, I still have to check that I can find a data structure (a Seq) providing drop and take operations in O(1). From what I read of the implementation of RandomAccessSeq, that should be the case. RandomAccessSeq is using indexes to provide O(1) "slicing" operations as suggested by Mikko in the comments of the previous post.

Brutal force

And finally, I can't resist showing you the horror of finding the median of a sorted list and a supplementary element in O(1). There may be a subtle trick to do that (please say, if you find it!), but I used the brutal force:


def medianOfSortedListPlusOneElement(list: Seq[Int], element: Int) = {
  if (list.size == 1){
    if (element >= list(0))
      (list(0), element)
    else
      (element, list(0))
  } 
  else if (list.isOdd) {
    if (element >= list(list.size / 2)) {
      if (element <= list(list.size / 2 + 1))
        (list(list.size / 2), element)
      else
        (list(list.size / 2), list(list.size / 2 + 1))
    } else {
      if (element >= list(list.size / 2 - 1))
        (element, list(list.size / 2))
      else
        (list(list.size / 2 - 1), list(list.size / 2))
    }
  } else {
    if (element >= list(list.size / 2 - 1)) {
      if (element <= list(list.size / 2))
        (element, element)
      else
        (list(list.size / 2), list(list.size / 2))
    } else {
        (list(list.size / 2 - 1), list(list.size / 2 - 1))
    }
  }
}

Not pretty, uh? Like the final approach for the 4-colors theorem.

Measuring the complexity

On my way to this post, I wanted to implement something which would store the test data and say if the curve looks like an O(log(n)), an O(nlog(n)),... In fact it doesn't seem so easy to do without any human validation and tweaking of the test data size until the complexity really shows. I'm thinking that using an utility to graph the performances and compare it with known complexities would be a good first step.

But maybe driving the test generation so as to get a good confidence on the possible complexity of the algorithm would be even better. I'll try to have a look at that,... Maybe for my next post?

Thanks for all the comments, I hope I didn't add more and more silliness to my previous errors.

PS: I liked a lot Tom's comments about the 2-keys indexing problem. Indeed, the problem was underspecified, in terms of access frequency, memory, etc,... And a log(n) solution would certainly be ok in my specific case.

Algorithmic panic

2008-05-02T22:23:00.005+09:00

Last week I read a blog post about an interview for Google and I thought: "Oh my god, I don't know how to do that, I'm lost, I have no idea, I will never find the solution".

Flashback

Two weeks ago, I've ordered and started reading the excellent book, "The Algorithm Design Manual". That book is very good. Teaching algorithms and data structures can be something very dry when you consider it from a very scholar perspective. But it becomes really fun and challenging when you realize that:

it solves real worthy problems
no amount of processing power can be overcome a clever algorithm when there is one
there's often no "right" solution but a combination of different approaches with different trade-offs

So the book is filled with "war stories" showing the author investigating some problems, trying to ask relevant questions until there's a "ah-ah" moment where the problem is sufficiently characterized. Then the solution is refined to get a completely satisfying result.

Decode this!

For example, the author and his team had to provide a new way to decrypt DNA fragments, knowing that there was a new technique using small probes returning small fragments of the whole string. Say your DNA is ATGCCTCGATTG, the probes will find AT, TG, GA, TT, TG, all of which are substrings of the initial string. And from all those pieces, you have to find the original DNA string. For this kind of problem, the sheer number of elements kills instantly any brutal-force approach. Originally they had to sequence DNA fragments of 50.000 characters, knowing that more that 1.5 million pieces should be combined to get the answer. Don't try this at home!

Binary tree > HashTable > Suffix Tree

For their algorithm to work they had to set up a dictionary allowing the search of substrings of length k inside strings of length 2k. The question is: how to do that very efficiently? A student proposed a HashTable which would do the job in O(log(k)). But this was still too slow! Hey, what can be faster than a HashTable??!! A Suffix Tree.

In this specific case they were searching elements which looked very close to one another, just being different by one character. And a suffix tree happens to organize the suffixes of a set of strings so that it's easy to search for a string which is just one character away.

Understanding the structure of the problem yielded much better results than a HashTable: for a 8000 characters long DNA, the HashTable time was 2 days against 650 seconds for the SuffixTree (the "compressed" version, because the original one was blowing up the memory!). That was my "ah-ah" moment.

The dreadful interview question

So I thought I was ready for any algorithmic question. Until I read the blog: "find the median of 2 sorted lists in O(log(n))". I don't know why, reading that blog, I imagined myself over the phone, trying to solve this problem and my mind got totally blank. Panic.

The same night, going to bed, I told myself: ok, relax, have a fresh look at it. And I slept happily a few minutes later because the principle of the solution wasn't that difficult.

First of all, the median of a sorted list is the middle element. That's an O(1) search! Then, given the medians for each list, the median of both lists is something like the median of the 2 sublists of all elements between median1 and median2. That's where we get our O(log(n)) from, because with a recursive search, we're pretty sure to cut the problem size by 2 at each step.

I programmed the rest the day after. Again, I think that this is a tribute to Scala. The result is really readable and I used ScalaCheck to verify it by generating lists of same and different sizes. On the other hand, I had hard time figuring out the proper bound conditions (ScalaCheck was very helpful here):



trait Median {
  def median(l1: List[Int], l2:List[Int]): Int = {
    if (l1.isEmpty || l2.isEmpty || l1.last <= l2.head) (l1 ::: l2).median
    else if (l2.last < l1.head) (l2 ::: l1).median
    else {
      val (m1, m2) = (l1.median, l2.median)
      if (m2 < m1) median(l1.takeBetween(m2, m1), l2.takeBetween(m2, m1))
      else if (m2 > m1) median(l1.takeBetween(m1, m2), l2.takeBetween(m1, m2))
      else m1
    }
  }
  implicit def toExtendedList(list: List[Int]) = ExtendedList(list)
  case class ExtendedList(list: List[Int]) {
    def takeBetween(a: Int, b: Int) = list.dropWhile(_ <= a).takeWhile(_ <= b) 
    def median = list(list.size / 2)
  }
}

Data structures everywhere

Funnily, yesterday, one of my colleagues asked me if I knew an easy, fast and clever way to access some values classified with 2 keys:

there's only one value for (key1, key2)
she wants to get the value for (key1, key2) (fast,...)
she wants to get all values for key1 (fast again,...)
she wants to get all values for key2 (fast also,...)

This looks like a very classical problem for Java programmers but surprisingly I found no existing, open-source, solution for this (if you know that, please tell me. I looked at things like TreeMaps or MultiMaps for example but they don't fit the requirement of a fast 2 key search with either of the keys).

After some research and some thinking we concluded that 3 hashmaps sharing the values and dedicated to answer each different query fast would be the best thing to do. But now that I know that HashTables are not the ultimate solution to everything,...

PDD: Properties Driven Development

2008-03-13T21:58:00.028+09:00

Quick quizz: 1 + 2 =? and 1 + 2 + 3 =? and 1 + 2 + 3 + 4 =?

In other words, what is the result of the sumN function, which sums all integers from 1 to n?

If we had to use a "direct" (some would say "naive") TDD approach, we could come with the following code:
[Warning!! The rest of the post assumes that you have some basic knowledge of Scala, specs and Scalacheck,... ]

"the sumN function should" {
  def sumN(n: Int) = (1 to n) reduceLeft((a:Int, b:Int) => a + b)
  "return 1 when summing from 1 to 1" in {
    sumN(1) must_== 1
  }
  "return 2 when summing from 1 to 2" in {
   sumN(2) must_== 3
  }
  "return 6 when summing from 1 to 3" in {
    sumN(3) must_== 6
  }
}

But if we browse our mental book of "mathematical recipes" we remember that

sumN(n) = n * (n + 1) / 2

This is actually a much more interesting property to test and Scalacheck helps us in checking that:



"the sumN function should" {
  def sumN(n: Int) = (1 to n) reduceLeft((a:Int, b:Int) => a + b)
  "return n(n+1)/2 when summing from 1 to n" in {
    val sumNInvariant = (n: Int) => sumN(n) == n * (n + 1) / 2
    property(sumNInvariant) must pass
  }
}

Even better, Scalacheck has no reason to assume that n is strictly positive! So it quickly fails on n == -1 and a better implementation is:



"the sumN function should" {
  def sumN(n: Int) = {
     assume(n >= 0) // will throw an IllegalArgumentException if the constraint is violated
     (1 to n) reduceLeft((a:Int, b:Int) => a + b)
  }
  "return n(n+1)/2 when summing from 1 to n" in {
     val sumNInvariant = (n: Int) => n <= 0 || sumN(n) == n * (n + 1) / 2
    property(sumNInvariant) must pass          
  }   
}

This will be ok and tested for a large number of values for n. Using properties is indeed quite powerful. Recreation time! You can now have a look at this movie, where Simon Peyton-Jones shows that Quickcheck (the Haskell ancestor of Scalacheck) detects interesting defaults in a bit packing algorithm.

Fine, fine, but honestly, all those examples look very academic: graph algorithms, mathematical formulas, bits packing,... Can we apply this kind of approach to our mundane, day-to-day development? Tax accounting, DVD rentals, social websites?

I am going to take 2 small examples from my daily work and see how PDD could be used [yes, YAA, Yet Another Acronym,... PDD stands for Properties Driven Development (and not that PDD)].

From the lift framework (courtesy of Jamie Webb): a 'camelCase' function which transforms underscored names to CamelCase names
From my company software: some pricer extension code for Swaps where fees values have to be subtracted from the NPV (Net Present Value) under certain conditions

I'll develop the examples first and try to draw conclusions latter on.

Example 1: camelCase

So what are the properties we can establish for that first example? Can we describe it informally first?

The camelCase function should CamelCase a name which is under_scored, removing each underscore and capitalizing the next letter.

Try this at home, this may not be so easy! Here is my proposal:



def previousCharIsUnderscore(name: String, i: Int) = i > 1 && name.charAt(i - 1) == '_'
def underscoresNumber(name: String, i: Int) = {
  if (i == 0) 0
  else name.substring(0, i).toList.count(_ == '_')
}
def indexInCamelCased(name: String, i: Int) = i - underscoresNumber(name, i)
def charInCamelCased(n: String, i: Int) = camelCase(n).charAt(indexInCamelCased(n, i))

val doesntContainUnderscores = property((name: String) => !camelCase(name).contains('_'))

val isCamelCased = property ((name: String) => {
  name.forall(_ == '_') && camelCase(name).isEmpty ||
  name.toList.zipWithIndex.forall { case (c, i) =>
    c == '_' ||
    indexInCamelCased(name, i) == 0 && charInCamelCased(name, i) == c.toUpperCase ||
    !previousCharIsUnderscore(name, i) && charInCamelCased(name, i) == c ||
    previousCharIsUnderscore(name, i) && charInCamelCased(name, i) == c.toUpperCase
  }
})
doesntContainUnderscores && isCamelCased must pass

This property says that:

the CamelCased name must not contain underscores anymore
if the name contains only underscores, then the CamelCased name must be empty
for each letter in the original name, either:
- it is an underscore
- it is the first letter after some underscores, then it becomes the first letter of the CamelCased word and should be uppercased
- the previous character isn't an underscore, so it should be unchanged
- the previous character is an underscore, so the letter should be uppercased

Before running Scalacheck, we also need to create a string generator with some underscores:



implicit def underscoredString: Arbitrary[String] = new Arbitrary[String] {
def arbitrary = for { length <- choose(0, 5)                                                  string <-   vectorOf(length, frequency((4, alphaNumChar),                                                                (1, elements('_'))))                       } yield List.toString(string)  }

This works and in the process of working on the properties I observed that:

the full specification for CamelCasing name is not so easy!

it is not trivial to relate the resulting name to its original. I had to play with indices and the number of underscores to be able to relate characters before and after. However, if that code is in place, the testing code is almost only 1 line per property to check

the properties above specify unambiguously the function. I could also have specify weaker properties with less code, by not avoiding to specify that some letters should be unchanged or that the CamelCased name contains an uppercased letter without checking its position.

Example 2: Pricer extension

The logic for this extension is:

to have the NPV (NetPresentValue) being calculated by the Parent pricer
to collect all fees labeled "UNDERLYING PREMIUM" for that trade
to subtract the fee value from the NPV if the valuation date for the trade is >= the fee settlement date
to apply step 3 only if a pricing parameter named "INCLUDE_FEES "is set to true, while another pricing parameter "NPV_INCLUDE_CASH" is set to false

This looks certainly like a lot of jargon for most of you but I guess that it is pretty close to a lot of "Business" requirements. What would a property for those requirements look like (in pseudo Scala code)?



(originalNPV, fees, valuation date, pricing parameters) =>

if (!INCLUDE_FEES ||  NPV_INCLUDE_CASH)
  newNPV == originalNPV
else
  newNPV == originalNPV - fees.reduceLeft(0) { (fee, result) => result +
              if (fee.isUnderlyingPremium && fee.settlementDate <= valuationDate)      
                fee.getValue    
              else      
                0
            }

The most remarkable thing about this property is that it looks very close to the actual implementation. On the other hand, Scalacheck will be able to generate a lot of test cases:

an empty fee list
a list with no underlying premium fee
a list with a fee which settle date is superior to the valuation date
a list with a fees which settle date is inferior to the valuation date
the 4 possible combinations for the values of the pricing parameters

You can also notice that I use as the first parameter the originalNPV, which doesn't directly come from a generator but which would be the result of the original pricer with the other generated parameters (fees, valuation date, pricing parameters).

Conclusion

As a conclusion, and at the light of the 2 previous examples, I would like to enumerate the result of my recent experiments with Properties-Driven-Development:

First of all is that PDD is TDD, on steroids. In PDD, we also have data and assertions but data are generated and assertions are more general.

I don't believe that this replaces traditional TDD in all situations. There are situations where generating even 4 or 5 cases manually is easier and faster. Especially when we consider that making an exact oracle (the savant word for verification of test expectation) is sometimes tedious as in the camelCase function. In that situation developping the cases manually using the == method would have been much faster

PDD on the other hand allow the specify very clearly what is the rule. This is something that you would have to infer reading several examples when using TDD

On the other hand having several examples also facilitate the understanding of what's going on. "foo_bar" becomes "FooBar" is more easy to catch than "if a letter is preceded by,..."

PDD is very good at generating data you wouldn't think of: empty list, negative numbers, a string with underscores only,...

A tip: sometimes, it is useful to include in the generated parameters the result returned by the function you want to test. For example, in the second example, my parameters could be: (originalNPV, newNPV, fees, valuation date, pricing parameters). That way, when Scalacheck reports an error, it also reports the actual value you got when showing a counter-example

Sometimes the properties you want to check will almost mimic the implementation (as in example 2). I think that this is may be very often the case with business code if written properly or that this may show that your code is missing a key abstraction

It really gets some time to get your head wrap around finding properties. And soon you'll start thinking things like: "I know that property A, B and C characterize my function, but are they sufficient?" and you realize that you coming close to Programming == Theorem Proving

As a summary, PDD is not the long awaited Silver Bullet (sorry ;-) ,...) but it is indeed a wonderful tool to have in your toolbox. It will help you test much more thoroughly your programs while seeing them yet another way.

A++ [Eric Torreborre's Blog]

Pragmatic IO - part 3

Why types and laws matter

Get the types right

Use the laws

Scala and Scalaz-seven might help

Pragmatic IO - part 2

Learning by being wrong, very wrong

Mind the law

Not at the right time

My goal

What not to do

Learn your FP classes

Unfolding a data structure

Running the StreamT

UnsafePerformIO at last

Hidding everything under the rug

Conclusion

Pragmatic IO

A short IO introduction

IO or not IO

Theory => Practice

Segregating the effects

Under the bonnet: syntactic tricks

"Monadic" sequencing

"Semi-column" sequencing

"Conditional" sequencing

"if else" with a twist

Under the bonnet: it just works,... not

Trampolining to the rescue

The subtleties of foldRight and foldLeft

Conclusion

PS

Practical uses for Unboxed Tagged Types

Groovy vs Scala for log analysis

Unboxed what?

There is time and,... time

Twitter forever

Using the new toys

Final comments

Scala collections are awesome

Doing the job

Naively

Wrongly

Fast and right

Conclusion

Update

Counting words - part 2

Be reactive

With GUI components

An example

Some implementation notes

Features ideas

Counting words

I can do that in 2 hours!

Parsing the text

Displaying the results

Reading the file

Recap

The Essence of the Iterator Pattern

What's in a for loop?

The Applicative typeclass

What is a Functor?

Pointed Functor

Applic

Applicative Functor

Traversing the structure

A Binary Tree

Applicative Monoid

Contents of a BinaryTree...

Profit time

.... and shape of a BinaryTree

Monads are Applicatives too!

Decompose / Compose

Applicative products

Collection and dispersal

The State monad

Collecting elements

Dispersing elements

An overview of traversals

A short `IO` introduction

`IO` or not `IO`

The subtleties of `foldRight` and `foldLeft`

The `State` monad

The `assemble` function