Implicit double dispatch revisited

8 02 2008

In my first post on this topic I showed how generic types can be treated polymorphically in Scala. I employed Scala’s implicits and view bounds to emulate overloading of methods with arguments having the same type erasure.

def foo[T <% Dispatcher&#91;T&#93;&#93;(x: T) {
  x.dispatch(new Switch {
    def case_(x: String) {
      println("Got a string " + x)                
    def case_(x: int) {
      println("Got a int " + x)
Method foo can be called for any type T for which a conversion to the type Dispatcher&#91;T&#93; is in scope. Dispatcher&#91;T&#93; has a dispatch method for the type T. The method takes a Switch instance and calls its case_ method passing along the dispatched value. See <a href="">Implicit double dispatch</a> for details.

trait Switch {
  def case_(s: String)
  def case_(n: int)

There are two things I don’t like. First, when calling foo with a list argument the list is not passed on as a whole to the respective case_ method. Rather is the case_ method called once for every element of the list iteratively. Second, the foo method is also callable with arguments of type String and type int, not only for Lists of these types.

I generalized my initial code to address these issues. The revisited code is again available on my code page.

To address the first issue I simplified the implementation of foo to

def foo[T <% Dispatcher&#91;T&#93;&#93;(x: T) = x.dispatch()
The signature is as before and allows foo to be called for all types T which are implicitly convertible to Dispatcher&#91;T&#93;. The implementation is much simpler however. It still calls the dispatch method of its Dispatcher&#91;T&#93; argument but this time without an argument. 
&#91;sourcecode language="java"&#93;
abstract class Dispatcher&#91;T&#93;(value: T) {
  def dispatch()
  def dispatch(l: List&#91;T&#93;)
Again Dispatcher&#91;T&#93; is responsible for handling values of type T. But now there is an additional dispatch method for handling lists of values of type T. The implicit conversion methods create specialized Dispatcher&#91;T&#93; instances for concretes types.
&#91;sourcecode language="java"&#93;
implicit def string2Disp(value: String) = new Dispatcher(value){
  def dispatch() = println("String: " + value)
  def dispatch(l: List&#91;String&#93;) =  println("List&#91;String&#93;: " + l)
The above code is for converting a String to a Dispatcher&#91;String&#93;. (Converting an int to a Dispatcher&#91;int&#93; works analogous). The method returns a new instance of type Dispatcher&#91;String&#93; whose dispatch methods outputs the original value. For the first method this is the value originally passed to string2Disp. For the second method the value is a list of strings passed as argument. To see how this second method is called and where that list argument comes from let's take a look at how lists are converted to their respective Dispatcher objects.
&#91;sourcecode language="java"&#93;
implicit def list2Disp&#91;T&#93;(value: List&#91;T&#93;)(implicit x2Disp: T => Dispatcher[T]) = new Dispatcher(value) {
  def dispatch() = x2Disp(null.asInstanceOf[T]).dispatch(value)
  def dispatch(l: List[List[T]]) = println("List[List[_]]: " + l)        

Say a List[String] is to be converted to Dispatcher[List[String]]. The Scala compiler looks for an implicit argument to be passed for the x2Disp parameter. It finds the string2Disp method and passes it for the x2Disp parameter. Now there is a trick in the implementation of the first dispatch method: a call to x2Disp returns an instance of Dispatcher[String] which is subsequently used to call dispatch on passing along the original list of strings. The argument passed to x2Disp does not matter since any instance of Dispatcher[String] will do. So we simply pass null casted to the right type T.
The second dispatch method which takes a list of lists is similar to the dispatch method for lists in the case of Dispatcher[String] from above. The dispatch mechanism thus works for arguments of type List[List[List[…]]] up to an arbitrary depth (at least in theory).

To address the second issues, all that has to be done is to further restrict the applicable types for the foo method. Such a restriction should only allow lists to be passed as arguments, not individual values. I did not succeed to express such a constraint as an upper bound along the lines of

def foo[T <% Dispatcher[T] <: List[T]](x: T) = x.dispatch() [/sourcecode] or similarly. However using existential types the same effect can be achieved:

def foo[T <% Dispatcher[T] forSome { type T <: List[_] }](x: T) = x.dispatch() [/sourcecode] This effectively limits type T further to lists convertible to Dispatcher[T]. With this signature in place the following calls to foo are not legal anymore [sourcecode language="java"] foo("A String") foo(42) [/sourcecode] while all of the following still works as expected: [sourcecode language="java"] val ints: List[int] = Nil foo(ints) // empty list of ints val strings: List[String] = Nil foo(strings) // empty list of strings // Simple lists foo("one"::"two"::"three"::Nil) foo(1::2::3::Nil) // List of lists foo((1::2::3::Nil)::(4::5::6::Nil)::Nil) foo(("one"::"two"::Nil)::("three"::"four"::Nil)::Nil) [/sourcecode] Finally one may ask: where is the double dispatch? Well, it is hidden inside the implicit argument passed to list2Disp. The first dispatch is explicitly done by the foo method. If we deal with a list, the second dispatch is done on the object returned by the call to the x2Disp argument which was implicitly passed on the first dispatch.