Derek Wyatt's Blog

I’ve been working on a book since March, 2012 called Akka Concurrency and on Monday, Oct 15th 2012, it went live at Artima. I’m really happy to see it make this milestone – it’s been a long time coming!

The book builds on the existing, and excellent Akka Documentation by going beyond the what and the basic how of Akka and into the why, as well as covering some more of the esoteric bits of the how as well. It’s a unique pleasure to see the wonderful documentation that the Akka team has developed. If they hadn’t done such a great job, I believe that I wouldn’t have wanted to write this book in the first place.

I hope that the Akka community finds it helpful and it brings more developers into this fantastic toolkit. Please head over to Artima and have a look at the book. Take a look at the table of contents, as well as the sample chapter and, if you like it, you just might want to grab a copy!

I recently enjoyed a couple of days with Heiko Seeberger and Josh Suereth as they dragged me through some Advanced Scala Training and it was quite awesome. As an exercise, to test out my new found skills I pimped a new method onto “numbers” in Scala and I thought it might be instructive to share.

The Goal

The goal is really quite simple. All we want to do is add a new method, squared onto “numbers”. I don’t mean Int directly, but anything that Scala considers a number. We should see things like this:

5.squared    // == 25
25.0.squared // == 625.0

The Code

The code is wonderfully simple for this.

implicit def numeric2Powerable[A : Numeric](i: A) = new {
  def squared: A = implicitly[Numeric[A]].times(i, i)
}

Done. What we’ve managed to do in such a small amount of code is quite surprising. Let’s break it down.

• implicit: The implicit puts the conversion definition into the local scope so that we can get a transparent conversion from our number to our pimped object.
• [A : Numeric]: This is a context bound. It states that the type parameter we’re going to constrain this implicit conversion to must have an instance of the Numeric type class in scope. It’s this constraint that limits the types we’re pimping down to being numbers.
• implicitly[...]: Because we’ve chosen the “clean” declaration for the context bound (as opposed to the slightly uglier curried parameter version) the instance of the type class has not been bound to an identifier that we can later use. In order to get access to the instance, we must “look it up”. Because scala.Predef is always imported by default, and because implicitly is defined there, we have access to it, and this is what we use to resolve the implicit instance.

The reset is self-explanatory.

That’s all there is to it. We’ve defined an implicit conversion from a number to a new pimp-class, used a type class to narrow the target types for the pimp, and pulled in the instance of the type class to give us a concrete tool to use in performing the computation. Not bad for a couple of lines of code.

Addendum: Missingfaktor showed me another little fun bit that you can add on to the code above to make the implementation feel more natural. We can import the implicits that are defined on Numeric to give us some infix notation instead.

implicit def numeric2Powerable[A : Numeric](i: A) = new {
  import Numeric.Implicits._
  def squared: A = i * i
}

It doesn’t change the API at all, but it does look a little niftier with respect to the implementation. It’s a little less simple, from an instructive point of view, because you start to wonder where the implicitly wandered away to. So, some more explanation is probably in order.

Specifically, what we’re importing is:

object Numeric {
  trait ExtraImplicits {
    implicit def infixNumericOps[T](x: T)(implicit num: Numeric[T]): Numeric[T]#Ops = new num.Ops(x)    
  }
  object Implicits extends ExtraImplicits { }
}

So, it’s really the infixNumericOps that we’re pulling in, and it’s delegating to Ops. So, what’s Ops?

Ops is defined as an inner class to the Numeric type trait and looks like:

class Ops(lhs: T) {
  def +(rhs: T) = plus(lhs, rhs)
  def -(rhs: T) = minus(lhs, rhs)
  def *(rhs: T) = times(lhs, rhs)
  def unary_-() = negate(lhs)
  def abs(): T = Numeric.this.abs(lhs)
  def signum(): Int = Numeric.this.signum(lhs)
  def toInt(): Int = Numeric.this.toInt(lhs)
  def toLong(): Long = Numeric.this.toLong(lhs)
  def toFloat(): Float = Numeric.this.toFloat(lhs)
  def toDouble(): Double = Numeric.this.toDouble(lhs)    
}

So, when we stitch this together, here’s what happens:

1. We bring infixNumericOps into scope.
2. We then invoke i * i, which is equivalent to i.*(i).
3. The * can’t be found on i since i is of type A.
4. However, now that we have infixNumericOps in scope, the compiler can use that conversion to create an instance of Numeric[A]#Ops.
5. Numeric[A]#Ops does have * defined for type A, thus, a new Ops is constructued, holding our value i within it.
6. The compiler then applies the * operator to to the second value of i and we’re done.

Cooler, but a hell of a lot more complicated to explain :)

A couple of people pointed out that my posting about why Monads are so awesome left a bit too much to the imagination. I tossed in an update that should make it less mysterious about what the heck I’m talking about.

Update: In the comments below, Alex is trying to educate me on something… I’m still not entirely sure what he’s on about but it’s been keeping me thinking about this post. I’ve modified it a bit here and there to try and be more correct. Essentially, I think I’ve been attributing too much to Monads where only part of what I like is attributed to them where the other part is attributed to partial functions (or function composition).

Ok, I’m no Monad expert by any stretch of the imagination… seriously. But, I did something today that has me so jazzed about Monads, partial functions and Scala in general, that I just gotta share.

So my task was to take some JSON and convert it to a structure of my own classes, but still really general – i.e. we’re not talking about “real” marshalling here.

So I took a simple approach, and used the Scala Library’s JSON Module. I had to deal with type-casting, defaulting of values, and constraint checking (i.e. field X must be defined). The code to do all of this is so simple and so awesome that it’s just hard to believe. Now, it’s not perfect… I’ll shore it up over the next while as need requires… but it’s passing all of my tests pretty nicely right now.

I want to convert the following JSON:

{
  "vendor"  : "Whoever", // required
  "colour"  : "blue",    // default to "None"
  "widgets" :            // default to Empty list of strings
  [
    {
      "name"    : "One",   // required
      "flavour" : "Lime"   // default to Strawberry
    },
    {
      "name"    : "Two",   // required
      "flavour" : "Banana" // default to Strawberry
    }
  ]
}

to the following concrete Scala:

case class Widget(name: String, flavour: String)
case class Contract(vendor: String, colour: String, widgets: List[Widget])
Contract("Whoever", "blue", List(Widget("One", "Lime"),
                                 Widget("Two", "Banana")))

I used a Pattern Matching example for this sort of thing from an awesome StackOverflow post as a starter and then fleshed it out to meet my requirements. Here it is:

// Types we need
case class Widget(name: String, flavour: String)
case class Contract(vendor: String, colour: String, widgets: List[Widget])

object Contract {
  // The class caster that came from the StackOverflow page
  // Yeah, this can throw exceptions... I don't care about
  // those for this example
  class ClassCaster[T] {
    def unapply(a: Any): Option[T] = Some(a.asInstanceOf[T])
  }

  // Concrete instances of the casters for pattern matching
  object AsMap extends ClassCaster[Map[String, Any]]
  object AsList extends ClassCaster[List[Any]]
  object AsString extends ClassCaster[String]

  // It can happen
  case class ContractException(message: String) extends Exception(message)

  // Returns an Either that is a hell of a lot more deterministic than
  // throwing exceptions around
  def fromJSON(json: String): Either[ContractException, Contract] = {
    // Helps us get rid of boilerplate
    def error[T](prefix: String): Option[T] =
      throw ContractException("%s must be specified".format(prefix))

    // Catch the exceptions and turn them into Left() instances
    try {
      val parsed = JSON.parseFull(json)
      if (parsed.isEmpty) throw ContractException("Unable to parse JSON.")

      // Here comes the monad / partial function love...
      val contract = for {
        Some(AsMap(map))  < - List(parsed)
        AsString(vendor)  <- map get "vendor" orElse error("vendor")
        AsString(colour)  <- map get "colour" orElse Some("None")
        AsList(widgets)   <- map get "widgets"
      } yield Contract(vendor, colour, for {
          AsMap(widget)     <- widgets
          AsString(name)    <- widget get "name" orElse error("name")
          AsString(flavour) <- widget get "flavour" orElse Some("Strawberry")
        } yield Widget(name, flavour)
      )
      Right(contract.head)
    } catch {
      case e: ContractException =>
        Left(e)
      case e =>
        Left(ContractException(e.getMessage))
    }
  }
}

It’s very impressive what this code actually handles when you start digging into it. I’m sure you can easily think about what it would be like to code this in Java (or spaghetti monster forbid C++) and know that it’s going to be a lot more verbose and probably a lot less reliable.

UPDATE: One of the key reasons why the above is so cool is this:

<- map get "colour" orElse Some("None")
<- widget get "name" orElse error("name")

By using a generator syntax (<-) and the get function on Map we get to work at a higher abstraction that allows us to chain the decision making process rather than what the imperative approach would demand of us. It’s the monadic and compositional nature of Option that allows us to do this. Consider:

String colour = map.get("colour");
if (colour == null)
  colour = "None";

String name = widget.get("name");
if (name == null)
  error("name");

I’m going to editorialise (I mean, this is my blog after all) and point out the following problems:

• It’s unclear. Sure, if you’ve seen it a million times (and let’s face, you have… we all have) you know exactly what this “means” but that’s not because its meaning is clear.
• It’s not syntactically atomic. Some nasty merge, or some careless programmer can easily insert something between lines 1 and 2 that uses colour.
• It’s repetitive in a bad way (is there a good way?). That pattern is going to be copy-pasted over and over again. How many times do you see “colour” in there? Yeah… three. So if I copy-paste that and forget to change the third one, you get this:

String flavour = widget.get("flavour");
if (flavour == null)
  colour = "None";

GHACK!

We need to program at a higher level.

I took a look at Scala Streams tonight (or was that last night? When am I posting this?) and thought I’d share what I learned from Literate Programs and the Scala source code.

Streams

For the uninitiated, a Stream in Scala helps realize one of the fundamental concepts of Functional Programming, that of laziness. In essence, a Stream as infinite – think of a collection that just goes on and on and on and on and on and on. It would be asinine to construct the entire collection before ever using it as that would only ensure that you never used it. A Stream is evaluated on an as-needed basis and only up to the point that you need it.

The Delicious, Delicious Code…

Let’s illustrate using good ol’ Fibonacci Numbers. We’ll construct a Stream recursively because that’s more fun and it gives more meat to discuss. (This example comes straight from the Literate Programs website but I’m hoping to explain it in a bit more depth, and not get it too wrong in the process)

import scala.math.BigInt
lazy val fibs: Stream[BigInt] = BigInt(0) #::
                                BigInt(1) #::
                                fibs.zip(fibs.tail).map { n => n._1 + n._2 }

(Note: The above must all be on one line or the compiler is going to have a tough time pimping it out)

Sweet and delicious, no?

Dissection

Let’s break it down:

lazy

Strictly speaking, this isn’t needed, but why not be as lazy as you can possibly be? For the truly uninitiated, this ensures that the fibs value is not evaluated until it’s actually used.

val fibs: Stream[BigInt]

“What the hell is this? I thought Scala inferred types!”, I hear you scream. Scala does infer types but we’re defining a recursive value here and Scala needs to understand that the recursive call is a recursive call on a Stream as opposed to a String or some other completely unrelated type.

BigInt(0) #:: BigInt(1) #::

The Fibonacci series starts with 0 and 1 so we shove those in right here. But what’s this #:: stuff? Here’s our first real magical point and even the somewhat initiated may be scratching their heads at this one.

If you look at the Stream api you won’t find the #:: member function anywhere, and indeed you shouldn’t as we’re not working with a Stream right now, but a BigInt.

So with that realization in place, we must also recognize that methods ending in : are right associative. What this means is that the object we’re calling the #:: method on is actually the Stream object that is returned from the map command at the end of the call (we’ll get back to that, just hang on). Remember how we had to declare that fibs was a Stream instead of letting Scala infer it? Well, that’s (one of the reasons) why we need to do that.

Now we know that the method is being called on the Stream but when we look at the api for Stream, again we don’t see that method call. So where is it?

This method gets pimped on through the implicit def consWrapper[A](stream: => Stream): ConsWrapper[A] method defined on the Stream companion object. Scala will resolve the lack of a #:: method on Stream by finding an implicit conversion to a type that does have that method, and this is the ConsWrapper. The result of that method is to return a new Stream.

Ok, but how’s that of any use? The conversion to ConsWrapper is going to kill us due to the fact that it’s going to call the recursive function… or is it? Well, of course it’s not. If you look at the paramter to the ConsWrapper you’ll see why this doesn’t cause immediate recursion: new ConsWrapper(tl: => Stream[A]). That’s a by-name parameter. This means that it’s not invoked until it’s used.

Wow, that’s a lot of stuff for one bullet point.

fibs.zip(fibs.tail)

Go look at the Stream api again, specifically the zip. I’ll wait.

You didn’t read it, did you? Fine… on your own head, be it.

The size of the Stream returned by tail is one-less than the size of the Stream itself. This means that the zipped result is going to be the size of the Stream returned by tail, not the size of the Stream itself. So, in the initial case (where the Stream is Stream(0, 1, [Stream]), the zipped result is actually Stream((0, 1), ([Stream])) because the tail, of one element, is paired with the head.

Stream.zip creates a Cons cell containing (this.head, that.head) as the Cons head and (this.tail zip that.tail) as the Cons tail but as a Stream of (A1, B) so we’re not evaluating it now – we’ll evaluate it when it gets called.

map { n => n._1 + n._2 }

Hmmm… I hesitate to say “duh?” but it really does seem appropriate to do so. I mean, if you’ve made it this far, you know what this does.

Use it

Ok, so what happens when we evaluate it? Let’s get the first 20 numbers:

scala> fibs take 20 foreach println
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
scala>

That looks right to me.

WTF?

Some of you may still be scratching your heads because I wasn’t terribly clear on how this actually works. How is it that each number is evaluated as needed? Well, first let’s prove that it is so. I’m going to modify the code slightly.

import scala.math.BigInt
lazy val fibs: Stream[BigInt] =
    BigInt(0) #::
    BigInt(1) #::
    fibs.zip(fibs.tail).map(n => {
      println("Evaluating: %s -> %s".format(n._1, n._2))
      n._1 + n._2
    })

Now let’s take the first 5:

scala> fibs take 5 foreach println
0
1
Evaluating: 0 -> 1
1
Evaluating: 1 -> 1
2
Evaluating: 1 -> 2
3
scala>

And let’s take them again…

scala> fibs take 5 foreach println
0
1
1
2
3
scala>

And let’s take the first 7…

scala> fibs take 7 foreach println
0
1
1
2
3
Evaluating: 2 -> 3
5
Evaluating: 3 -> 5
8
scala>

Ok, so it works; things are properly evaluated in a lazy manner. But how?

Why…

The culprit behind this magic appears to be the interplay between the Cons class, the StreamIterator class and the LazyCell class:

final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A]
// Note that the head is a value of type A and the tail is a by-name Stream

final class StreamIterator[+A](self: Stream[A]) extends Iterator[A] {
  class LazyCell(st: => Stream[A]) {
    // Note the laziness
    lazy val v = st
  }
  private var these = new LazyCell(self)
  def next: A =
    if (isEmpty) Iterator.empty.next
    else {
      // Evaluate the laziness
      val cur = these.v
      // And the concrete value of type A
      val result = cur.head
      // Assign the next lazy cell to be the Stream in the tail
      these = new LazyCell(cur.tail)
      result
    }
}

Couple that together with the recursively defined zip we saw earlier, and you’ve got your lazy Stream of Fibonacci numbers.

I love this stuff…