Squawks of the Parrot

What the heck is: Multimethod dispatch (MMD)

AKA Signature-based dispatch, and a number of other names.

This is a way for your program to have multiple subroutines, functions, or methods with the same name that differ only in the types of their signatures. That means you can have a subroutine foo that takes an integer, one that takes a string, and a third that takes a pointer to a structure of type bar. Same name, different parameter types. The compiler or your runtime then figures out which one to use. With statically typed languages it can be done at compile time, with dynamically typed languages it's done at runtime.

In fact, your code might look like:

sub foo(int a) {
print "An integer!";
}

sub foo(float a) {
print "A float!";
}

sub foo(string a) {
print "A string!";
}

What happens is that, when your code calls foo(), something (either the compiler or the runtime) takes a look at its parameter and decides which of your foo subs should be called. If the parameter's an int, the first foo is called. If it's a float, the second function is called, and if it's a string, the third function is called. This can be something of a disconcerting thing, if you're not used to it.

Now, before we go any further it's important to note that almost all languages that let you do this either require some sort of notation on the sub or method declaration, or have multimethod dispatch as a very fundamental construct, so either you've asked for it or you're expecting it. It's not, generally, something that springs itself on you. (If you were worried about accidentally doing this)

Why would you do this? Well...

If you've worked with a dynamically typed language, you've probably written code that looks something like:

method foo (object bar) {
if (bar.isa("integer")) {}
elsif (bar.isa("string")) {}
elsif (bar.isa("Thing")) {}
elsif (bar.isa("Widget") {}
}

where your method takes an object as a parameter, and at runtime you figure out what type of object it is. If you've done that, you've undoubtedly messed it up once or twice, and you've probably also used other people's code that does this and you've wanted to add a path for your object type, but couldn't.

If you've done operator overloading, you've probably also done MMD. Operator overloading (really a subject of another WTHI) is more or less when you can define how some basic operator such as addition or multiplication works for your class. Whenever you have this sort of overloading you're pretty much forced to do some sort of MMD if you want to Do The Right Thing, and that means checking the type of the other operand. Multiplication with an integer on the left and a matrix on the right does something very different than multiplication with a matrix on both sides. Or it does if you implement any sort of standard multiplication. Languages that do overloading without doing MMD make writing proper overloaded operators a pain.

Even in a language that has no concept of multimethod dispatch, it's still there, at least a little. Consider the following snippet of C:

c = a + b;

No biggie, right? Nothing multimethod there. Well... Try it. The C compiler will emit different code depending on the types of a and b. If they're both integers you'll get one set, if one of them is a float you'll get another, and if they're both floats you'll get a third. Multimethod dispatch, based on type. You just can't get to it in C.

One big benefit to multimethods is that they are generally (though not always) considered to live outside any namespace or object package, so you can add in your own foo method to any class, and it Just Works. Or, more to the point, you can add your "multiply(int, matrix)" function to the mix without having to thump the int class. (if you even can) One other benefit, in an OO language, is that generally the compiler or runtime will do the best it can. If you have a foo method that takes two strings, and instead call it with two objects that are subclasses of strings, the compiler (or runtime) will walk the inheritance tree of the arguments looking for the closest match, for some version of closest, and call that. If one can't be found, you get an error.

Now that you know what they are, there's the why question. Why do this?

Well, efficiency is one reason. You can have different versions of a routine that are optimized for the different types of the parameters. As in the C compiler case, you may want to emit different code depending on the operand types, to go as fast as possible.

Speed of dispatch is another--odds are the MMD code in the compiler or runtime is very well optimized for speed, and likely will outstrip anything you can do by hand. Even if your own code is faster, the next rev of the compiler or runtime may beat it, which is how these things often go.

Bug reduction is another. It's a lot less error prone to have one chunk of code, provided in the compiler or runtime, to figure out what routine to call based on the arguments than it is to have each of a thousand subs and methods hand-roll the code at their start. It's dull, boring code and very easy to get wrong.

Correctness is yet another reason. If you want your language to behave properly in the face of operator overloading (and you might not, depending on how you feel about overloading) you have to allow for very different behaviour based on the argument types. Matrix * Matrix does something very different than Matrix * Integer. (And different still from Integer * Matrix, but that's another story) This isn't even any sort of "I'm doing something wacky with operators!" it's just correctness.

Since multimethods generally live outside any class it makes doing proper operator overload extensions easier as well. While I know it "breaks encapsulation to inject a method into another class" you really do have to in many cases to get it right. Consider the matrix example we've been batting around. Integer * Matrix is an important case, but most operator overloading systems check the left-hand side to see what they should do. Since the Int class probably came standard, it undoubtedly has no idea what a matrix is, or what to do with it. Your Matrix class, on the other hand, does know what to do, so having the int*matrix version in the matrix class makes sense. It also means that when you create your own Foo class, which also knows about matrices (though matrix has no idea about Foo) you can have it provide code to handle the matrix case. While you can't handle all eventualities, with MMD you can at least handle more.

MMD. Interesting, useful, and in many cases what you're doing already, only in a less sucky way.

Posted by Dan at May 27, 2003 06:13 PM | TrackBack (0)

# $table = Data::Table::Model->new();
#
# $table->add_row( $arrayref )
# $table->add_row( $arrayref,[$idx1, $idx2, $idx3 ] )
# $table->add_row( $obj,    [$meth1, $meth2,$meth3 ] )
# $table->add_row( $hashref,[$key1, $key2, $key3 ] )
# $table->add_row( $coderef )
# $table->add_row( $coderef,[$arg1, $arg2, $arg3 ] ) #aref is argument to coderef
# $table->add_row( $coderef, {key=>val, key1=>val1,key2=>val2})#href is argument to coderef