Java.next #3: Dispatch

This is Part Three of a series of articles on Java.next. In Part Three, I will explore how the Java.next languages (JRuby, Groovy, Clojure, and Scala) support dispatch.

For my purposes here, dispatch is a broad term covering various methods of dynamically choosing behavior: single dispatch, switch/case, pattern matching and multiple dispatch. These concepts are not generally grouped together, but they should be. They are used to solve similar problems, albeit in very different ways.

Single dispatch

Let me start with single dispatch. In Java, methods can be selected based on the type of the object they are invoked on. All the Java.next languages support single dispatch, too:

  ; clojure
  (fly vehicle speed)

  // Java, Groovy, or Scala
  vehicle.fly(speed)            

  # ruby
  vehicle.fly speed

In all of these languages, the actual implementation of fly can vary depending on the run-time type of vehicle. (Clojure also supports multiple dispatch, where the implementation can vary based on the type of speed -- more on that later.)

Better switching

Another way to dynamically choose behavior is with a switch statement. Java has a simple switch statement, based on its historical kinship with C and C++. Switch statements have gotten a bad name, so much so that programmers are encouraged to replace them with polymorphism where possible.

This anti-switching bias is based on the limited kind of switching allowed in languages such as Java. In Java.next, there is a different story. The Java.next languages all have powerful switching capabilities, allowing you to switch on any criteria you like. As an example, consider a method that calculates a letter grade, taking input that is either a number or letter grade.

Ruby's case statement

Here is letter_grade in Ruby:

  def letter_grade(val)
    case val
      when 90..100: 'A'
      when 80...90:  'B'
      when 70...80:  'C'
      when 60...70:  'D'
      when 0...60:   'F'
      when /[ABCDF]/i: val.upcase
      else raise "Not a valid grade: #{val}"
    end
  end

In Ruby, the switch/case variant is called case. The Ruby when clause can take arbitrary expressions. Above you see ranges and regular expressions side-by-side in the same case expression. In general, the when clause expects objects that implement a well-known threequals method, ===. Many Ruby objects have sensible === implementations: ranges match numbers in the range, regular expressions match strings containing the regular expression, classes match instances of the class, etc. But any object can implement ===, so you can implement arbitrarily complex dispatch with Ruby case.

Groovy's switch statement

Here is letterGrade in Groovy:

  def letterGrade(val) {
    switch(val) {
     case 90..100: return 'A'
     case 80..<90:  return 'B'
     case 70..<80:  return 'C'
     case 60..<70:  return 'D'
     case 0..<60:   return 'F'
     case ~"[ABCDFabcdf]": return val.toUpperCase()
      default:  throw new 
                IllegalArgumentException("Invalid grade: $val")
    }
  }

In Groovy, the switch/case variant is called switch. If you compare this code with JRuby, you will see minor syntactic differences:

  • Groovy switch keeps faith with Java, so you have to return or break out
  • Groovy uses default where Ruby uses else.
  • Groovy's top-exclusive range uses ..< whereas Ruby's uses ... .
  • Groovy uses isCase instead of ===. (This is not visible in the code sample, but you would need it to test case matches individually.)

The general ideas are the same. Both JRuby and Groovy provide far more powerful and general approaches than Java's switch.

Clojure's cond function

In clojure, as in many Lisps, you can switch on arbitrary functions using cond. One possible approach to letter-grade would be:

  (defn letter-grade [grade]
    (cond 
     (in grade 90 100) "A"
     (in grade 80 90) "B"
     (in grade 70 80) "C"
     (in grade 60 70) "D"
     (in grade 0 60) "F"
     (re-find #"[ABCDFabcdf]" grade) (.toUpperCase grade)))

In Clojure, regular expressions look like #"...". The in function above is not part of Clojure. I wrote the code the way I wanted it to read, and then wrote this function:

  (defn in [grade low high]
     (and (number? grade) (<= low grade high)))

In Clojure, I probably wouldn't use a regular expression for the letter-matching step, but I wrote the example that way for symmetry with the others.

Clojure's cond is just the tip of the iceberg. Clojure-contrib includes a set of macros for other variants of switch/case, and later in this article I will demonstrate Clojure's multiple dispatch.

Scala's pattern matching

Scala's pattern matching is a powerful generalization of the switch/case idiom in many programming languages. Scala provides out of the box support for pattern matching on

  • constants
  • variables (which can be used in the match result)
  • constructors
  • sequences
  • tuples
  • types

With pattern matching, implementing letterGrade is a snap:

  val VALID_GRADES = Set("A", "B", "C", "D", "F")
  def letterGrade(value: Any) : String = value match {
    case x:Int if (90 to 100).contains(x) => "A"
    case x:Int if (80 to 90).contains(x) => "B"
    case x:Int if (70 to 80).contains(x) => "C"
    case x:Int if (60 to 70).contains(x) => "D"
    case x:Int if (0 to 60).contains(x) => "F"
    case x:String if VALID_GRADES(x.toUpperCase) => x.toUpperCase()
  }

In this implementation, numeric grades and letter grades are both matched first by type. Then, case expressions also allow a guard that limits possible matches to some condition. So, for example, the first case above matches only if value is an Int (type match) and between 90 and 100 (the guard).

Scala's guard expressions are cool, but the combination of type+guard does not exactly parallel the other implementations of letterGrade, which rely on arbitrary predicates in case expressions. Scala can do this too: Scala extractors allow you to create arbitrary patterns. Here is one approach to letterGrade using extractors:

  def letterGrade(value: Any) : String = value match {
    case NumericA(value) => "A"
    case NumericB(value) => "B"
    case NumericC(value) => "C"
    case NumericD(value) => "D"
    case NumericF(value) => "F"
    case LetterGrade(value) => value
  }

Behind the scenes, NumericA and friends are objects that implement an unapply method to determine if and how a value should match the pattern.

A more complex example

Scala's pattern matching is much more general than the letter grade example shows. To see this, check out Daniel Spiewak's series introducing Scala for Java programmers. In Part 4, he gives an example of pattern-matching working in conjunction with case classes, which I will explore below.

Scala's case classes

Case classes offer several interesting properties when compared to regular classes:

  • Case classes automatically get a factory method, e.g. Foo(1) instead of new Foo(1)
  • Case classes automatically get reasonable implementations for toString, hashCode, and equals.

These properties are so useful that Scala programmers use case classes for all kinds of things. But their true purpose is revealed in conjunction with patterns: Case classes work directly with pattern matching, without having to write an extractor as in the previous example.

  class Color(val red:Int, val green:Int, val blue:Int)

  case class Red(r:Int) extends Color(r, 0, 0)
  case class Green(g:Int) extends Color(0, g, 0)
  case class Blue(b:Int) extends Color(0, 0, b)

  def printColor(c:Color) = c match {
    case Red(v) => println("Red: " + v)
    case Green(v) => println("Green: " + v)
    case Blue(v) => println("Blue: " + v)

    case col:Color => {
      print("R: " + col.red + ", ")
      print("G: " + col.green + ", ")
      println("B: " + col.blue)
    }

    case null => println("Invalid color")
  }

The printColor method pattern-matches Red, Green, and Blue to provide special behavior for basic colors. Because these are case classes we can capture the actual color value v. All other colors fall through to a general Color, which prints a more generic message.

Clojure's defmulti

Scala's pattern-matching is a signature feature of the language. How do the other Java.next languages compare? To implement printColor in Clojure, I begin by defining a structure to capture a color:

  (defstruct color :red :green :blue)

Where the Scala example defined basic colors with case classes, in Clojure I can use functions:

  (defn red [v] (struct color v 0 0))
  (defn green [v] (struct color 0 v 0))
  (defn blue [v] (struct color 0 0 v))

Now for the fun part. I will define a multimethod named color-string, which dispatches based on which basic colors are present in the color struct.

  (defmulti color-string basic-colors-in)

basic-colors-in is a dispatch function that reports which colors have nonzero values:

  (defn basic-colors-in [color]
    (for [[k v] color :when (not= v 0)] k))

Now I can define multiple implementations of color-string. The basic syntax is

  (defmethod method-name dispatch-value function-body)

So for the three pure colors, I can define color-string as

  (defmethod color-string [:red] [color] (str "Red: " (:red color)))
  (defmethod color-string [:green] [color] (str "Green: " (:green color)))
  (defmethod color-string [:blue] [color] (str "Blue: " (:blue color)))

I can also provide a catch-all implementation by specifying a dispatch-value of :default:

  (defmethod color-string :default [color] 
    (str "Red: " (:red color) ", Green: " (:green color) ", Blue: " (:blue color)))

Multimethods are more powerful than polymorphic single dispatch in two important ways:

  1. With polymorphic single dispatch, the dispatch function is always the type of the the first argument. With multimethods, the dispatch function can be any arbitrary function, e.g. basic-colors-in above.
  2. With polymorphic single dispatch, polymorphism is limited to the first parameter. The dispatch function for a multimethod can look at all parameters, and vary based on any of them. (This feature is not needed in the color-string example above, but see Runtime Polymorphism for an example.)

Like Scala's pattern matching, Clojure's defmulti provides an extremely powerful and extensible dispatch mechanism.

Accidently blue

Both the Scala and Clojure code above take special action for colors that are declared to be pure blue:

  // Scala
  scala> printColor(Blue(10))          
  Blue: 10
  ; Clojure
  user=> (color-string (blue 10))
  "Blue: 10"

What about colors that are not declared as blue, but are, nevertheless, purely blue. These colors are accidentally blue:

  // different result for accidental blues
  scala> printColor(new Color(0, 0, 10))
  R: 0, G: 0, B: 10
  ; all blues equal
  user=> (color-string (struct color 0 0 10))
  "Blue: 10"

The Scala example was written to dispatch based on type, so it treats accidentally blue colors different from "real" Blues. The Clojure example, on the other hand, dispatches based on the actual color values, so all solid blues are treated the same, no matter how they are created.

Of course, nothing stops me from "fixing" the Scala example, e.g. by dispatching on something other than type:

  case class Color(val red:Int, val green:Int, val blue:Int)

  object ColorDemo {
    def colorString(c:Color) = c match {
      case Color(r,0,0) => "Red: " + r
      case Color(0,g,0) => "Green: " + g
      case Color(0,0,b) => "Blue: " + b

    case col:Color => {
      "R: " + col.red + ", " +
      "G: " + col.green + ", " +
      "B: " + col.blue
    }

    case null => "Invalid color"
      case null => "Invalid color"
    }
  }

Or, I could "break" the Clojure example by adding a type tag, and dispatching on that instead. Rich Hickey posted this example on the Clojure mailing list:

  (defstruct color :red :green :blue)

  (defn color-class [name r g b]
   (assoc (struct color r g b) :tag name))

  (defn red [v] (color-class :red  v 0 0))
  (defn green [v] (color-class :green 0 v 0))
  (defn blue [v] (color-class :blue 0 0 v))
  (defmulti color-string :tag)
  (defmethod color-string :red [c] (str "Red: " (:red c)))
  (defmethod color-string :green [c] (str "Green: " (:green c)))
  (defmethod color-string :blue [c] (str "Blue: " (:blue c)))
  (defmethod color-string :default [{:keys [red green blue]}]
     (str "Color, R: " red ", G: " green ", B: " blue)) 

This version now works like the original Scala version, treating "accidental" blue differently from things marked with a :tag of :blue.

Note that multimethods are open. I can add new colors later without having to modify the existing code:

  (defn orange [r g] (color-class :orange r g 0))
  (defmethod color-string :orange [{:keys [red green]}]
     (str "Orange, R: " red ", G: " green)) 

Dynamic Scala?

If you are a dynamic language programmer fearing the tyranny of the Scala compiler, pattern matching is a cause for rejoicing. With pattern matching, you can bypass static typing and get the flexibility of much more dynamic dispatch. Consider: Scala's pattern matching can be used to dispatch on arbitrary predicates. These predicates are not limited to type relationships known at compile time, so a Scala program that uses pattern matching as the cornerstone of its dispatch strategy can be as dynamic as an extremely dynamic Ruby program. Put another way: Scala's catch-all match default (_) is the moral equivalent of Ruby's method_missing.

Conclusions

Dispatch takes many forms. Single dispatch, switch statements, pattern matching, and multiple dispatch all meet similar needs: Selecting runtime behavior in response to varying runtime conditions.

Flexible dispatch is a key element of Java.next. All of the Java.next languages support dispatch strategies that are far more flexible than Java's single dispatch. These strategies are not perfectly interchangeable, but have a great degree of overlap. For example, Clojure's multimethods and Scala's pattern matching look quite different on the surface but can be used to solve similar problems.

Dispatch can be based on criteria more dynamic than the type system, even in Scala.


Notes

  • This article is based on the JVM Language Shootout talk. Check the schedule for a talk near you.
  • Thanks to Ola Bini, Justin Gehtland, Jason Rudolph, Daniel Spiewak, Venkat Subramaniam, and Greg Vaughn for their feedback on a draft of this article.
  • Thanks to Chouser and Rich Hickey for feedback on the Clojure examples.
  • Feedback on how to improve these examples is most welcome!

Revision History

  • 2008/08/29. Fixed fencepost error in Groovy code (Thanks Scott!). How irritating -- I have working unit tests for all the code and get burned by copy and paste.
  • 2008/08/30. Better Scala pattern match in second example, per Stefan's suggestion.