Things n' Stuff Thoughts about the universe in general

In short – no, and as I’ve seen people get baffled by that more then once – and the interesting effects that occur when programmers assume that it works, here’s a short explanation of what is multi-dispatch and why it doesn’t work in Java.

So what is multi-dispatch? multi-dispatch (or multiple dispatch or multimethods – as you like) is a object oriented programming language feature which is kind of hard to explain: when a method is called, in order for the compiler or run-time to choose the correct method to invoke from several methods with the same name, the number and type of the arguments in the call are compared to find the method implementation that best matches these arguments. This is called overloading.

The problem occurs when you consider what to do when a method is implemented more then once, where each implementation uses arguments that can be mapped one to the other – for example the types of one call are all specialized implementations of the types of another call. This will be made clearer by an example:

Imagine two classes, lets call them Feline and Cat, where Cat is obviously a specialization of Feline (Cat extends Feline in Java-speak). So what to make of a class that implements the following methods ?

public void pet(Feline feline) {
...
}
public void pet(Cat cats) {
...
}

When obviously, if I want to pet a Feline then the first method will be called, and if I have the more specialized Cat that I want to pet then the second method will be called.

So no problems, right ? Well, lets consider a more complex example, if you will. The below code can be downloaded here¹.

class Shape { }
class Triangle extends Shape { }
class Square extends Shape { }
class Circle extends Shape { }
class Canvas {
    public void draw(Shape s) {
        System.out.println("Drawing shape " + s);
    }
}
class SpecialCanvas extends Canvas {
    public void draw(Triangle t) {
        System.out.println("Special drawing triangle " + t);
    }
    public void draw(Square s) {
        System.out.println("Special drawing square " + s);
    }
}
class Dispatch {
    public static void main(String...args) {
        SpecialCanvas c = new SpecialCanvas();
        System.out.println("Try to draw some shapes:");
        for (Shape s : new Shape[] { new Circle(), new Triangle(), new Square() })
            c.draw(s);
        System.out.println("Lets try a plain triangle instead");
        c.draw(new Triangle());
    }
}

This is a pretty standard object oriented example with a twist – we have a general Shape type and more specialized types for each common geometrical shape. We then create three such shapes (Circle, Triangle and Sqaure) and pass each to the SpecialCanvas‘s draw() method. You’d notice that SpecialCanvas does not override the original draw(Shape) from Canvas but instead offers two methods of its own to specifically draw a Triangle or a Square.

Most people who were at least introduced to the concept of polymorphism in object oriented programming would usually expect that the program would call the standard draw routine for the first object in the list, the special triangle drawing routine for the second object and the special square drawing routine on the last object. It might surprise you then that the output from the Java program for the main loop would be:

Try to draw some shapes:
Drawing shape Circle@190d11
Drawing shape Triangle@a90653
Drawing shape Square@de6ced


As you can see, Java receives the correct objects in order – a circle then a triangle and lastly a square and sends them all to the original Canvas method. The problem is that the above code example is neither overriding (implementing the same method in a child class so it will be called instead of the method of the parent class) nor is it really overloading² – as a Triangle is also a Shape and its not strictly clear which method needs to get called when you try to call draw() with an object that is kind of a Shape. To further complicate matters, the Java compiler (or language – depend on where you want to put the blame) doesn’t warn against this type of usage, but instead tries to guess as to what you want it to do, but as it must determine the correct method to call during compilation³ it uses what it has – the declared type of the variable – to guess the correct method to call.

This is clearly demonstrated by the last part of the program whose output is:

Lets try a plain triangle instead
Special drawing triangle Triangle@c17164

The same draw() call, now given a declared type of Triangle correctly resolves to the special drawing routine in SpecialCanvas.

A language that support multi-dispatch needs to consider the type of the arguments to the call at run time and dispatch the call to the method that best matches (needs the least up-casting to) the arguments of the call. C++ supports this in a rather convulated way (which is messy and doesn’t play well with virtual method dispatch – and that explains why the wikipedia article doesn’t show a C++ example and just notes that C++ is capable of multi-dispatch) and this also explains why from the languages listed in the article to natively support multi-dispatch, none would look familiar to the casual observer 😉 .

1. you probably want to rename the file to Dispatch.java before compiling it – I didn’t feel like fiddling with wordpress to get it to set the file name correctly [↩]
2. The wikipedia Multiple Dispatch article makes a mess trying to explain how multi-dispatch is related to overloading – trying to say something to the effect that the object of the method call is the first argument of the call and overloading is determining the method on argument other then the first. Which is technically correct but will totally confuse anyone who hasn’t learned programming language design and philosophy and who haven’t programmed in Perl [↩]
3. at compile time instead of at run-time, it has to do with the fact that Java’s run-time is a simple VM that doesn’t have the required features to support such detection at run-time [↩]

This entry was posted on Thursday, January 10th, 2008 at 02:45 and is filed under Software. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.