Squawks of the Parrot

What the heck is: multimethod dispatch (MMD) good for?

In the last entry, modulo a rant or two, I explained what multimethod dispatch is, but I didn't really make a good case for what it's useful for. The comments on the entry gave some examples, but I think it warrants a bit more explanation.

I should start by noting that MMD is one of those features that you will use in a few very specific circumstances. This isn't the equivalent of addition we're talking about (though it does get used under the hood as part of addition) here. You'll either need it in a few well-defined places and use it, or you won't. If you don't, well, that's fine.

MMD is used in those places where you have a method that can take multiple types of things, and want to do something based on information in the inputs. Generally this means we check the types of the data, and do things differently depending on what types are passed in, but MMD isn't required to be limited to this. More on that in a bit.

Let's, for a moment, ponder a well-designed OO GUI system. (Yes, I know, but this is a thought experiment. Suspend your disbelief for a moment and follow along :) This system has an object for each GUI element, as well as a fully OO based event system. Even better, this system has typed events, so each event that you can get is a subclass of the generic Event class. Key presses, mouse clicks, window moves, resolution changes--they all have their own object type.

Your program, like so many other GUI systems, just spins its wheels, forever grabbing events and dispatching them off to do... something. Whatever's appropriate. In our case here, let's assume that each event comes with the GUI element the event applies to, just to make things easier. (The system tracks which GUI element each thing happened to, since it's a well-designed GUI system) The main loop of your program may look like:

  while (1) {
    ($widget, $event) = GetEvent();
    $widget->handle_event($event)
  }

How do you process the event? Well, your widget classes all have code that looks like:

  class Window {
    method handle_event(Event $event) {
      switch($event->type) {
        case KeyPress {
        }
        case MouseDown {
        }
        case SingleClick {
        }
        case DoubleClick {
        }
      }
    }
  }

(Keeping in mind that I'm mostly making up syntax here) The handle_event method for each GUI element type needs to check the type of the event and do something based on that event type. This is what happens now, though you generally aren't lucky enough to have the event actually come in as a typed object, instead getting an event structure or something. Still, we're pondering an OO GUI system, and the type of an object is as good a place (or better) as any to put the event type info.

Anyway, big switch statement. Ick. Maintenance pain, definitely, and one big glob of code. How could MMD make this better? Well, the class would then look like:

  class Window {
    multimethod handle_event(KeyPress $event) {
    }
    multimethod handle_event(MouseDown $event) {
    }
    multimethod handle_event(SingleClick $event) {
    }
    multimethod handle_event(DoubleClick $event) {
    }
  }

Rather than one big method, we have one method per type. This gets us a number of wins.

First, of course, the system handles dispatching, rather than our code. That's less code for us to have to write (albeit only a little less) and, more importantly, the system is likely far better optimized for fast dispatch than we can be, because the system is in a position to cheat unmercifully. We, as application programmers, have to play by stricter rules.

Second, we've isolated the code for each event type into separate methods, which makes maintenance a bit safer. Twidding code for one event doesn't risk the code for the rest. (Not a common problem, but a problem nonetheless) There is the potential for code duplication, but that's not usually an issue, since often the code to handle each event type will be in separate subroutines anyway.

Third, we've probably eliminated a sub dispatch. While simple event handling code can be put, with some risk, in the body of the switch, odds are if there's more than a few lines needed to handle it the code will be factored out to a separate subroutine. That means two dispatches for each event, while the MMD form has a single dispatch. (Not a huge savings per call, granted, but if we're in an event-heavy system efficiency translates to responsiveness)

Finally, it's easy to add support for new event types after the fact, and in classes we don't have access to. The window class may well be provided by the system, with a default event handler that takes plain Events and quietly discards them. The system instructions could well be "to handle an event of type X, add in a MMD handle_event that takes an event of the type you want to handle", or "To override default behaviours, add a handle_event that takes an event of type X in your Window child class". This provides a nice system--you get a fallback handler automatically, along with default behaviors the system provides (likely with full and evil access to the internals of the system) without having to explicitly redispatch. You want to handle an event of type X? Great, handle just it. You don't need to have a generic handle_event that dispatches to the parent handle_event for everything you don't understand. (You can, but that's error prone. We don't like errors)

Another place that MMD is used, as I talked about before, is in operator overloading. This is a place where being able to add in options to the dispatch table is extraordinarily useful. Without MMD, dispatch for overloaded operators is traditionally done based on the type of the left-hand side. That's fine if your object is on the left and it knows about the type of the object on the right, but less fine if your fancy object is on the right, or doesn't have a clue as to what to do with the object on the right. (Not that MMD will guaranteed save you, but at least there's an option)

Type based dispatching also has a nice property of allowing for closest-match lookups. If you have any sort of inheritance hierarchy, at some point you'll come across the case where no method exactly matches the types in the signature. In that case, what do you do?

You could just bail, of course. Fall back to the default method, or throw an exception, or otherwise pitch a fit. But that's not tremendously helpful. What most MMD systems do, then, is to find the closest match. This is done reasonably simply if you consider each level of the inheritance tree a unit of distance. If there's an exact match, it's 0 units away. If you have a Foo, and Foo inherits from Bar, then Foo is one unit from Bar. What you do, then, is look at each of the possible versions of a method and find out how 'close' you are to it. If your types all match, you're 0 units away, and you've got the method. If not, then you figure out how far away you are. This can be done simply, by figuring out how far off each parameter you have is and adding the distances up, or treating the parameters in the declared methods as defining a point in N-dimensional space and figuring out how far you are from each possibility. The former's easier, the latter is more correct, so which you choose to implement depends on how comfortable you (or the people implementing the engine) are with distances in N-dimensional spaces. Luckily, for speed reasons, the distance table can be completely precalculated, so the engine doesn't have to throw in the speed hit of transcendental functions in each method dispatch. When multimethods are defined, yes, but that's pretty rare relative to the number of times they're used.

Earlier I said that we generally dispatch on type, but we don't have to, and that's true. Type-based MMD is done mainly in the interest of speed--it's usually very quick to check the types of your parameters and look up in a big table to see which 'real' method you want to dispatch to, but you certainly aren't limited to that. Haskell, for example, allows you to dispatch based on the values that are passed, as well as their types. This is a tremendously powerful mechanism, though one that's not often implemented. (I have a nagging suspicion that's as much because it becomes close to impossible to mathematically prove a program's correctness with this scheme as the cost, and the folks doing language research tend to be of a theoretical bent. I may be wrong, though)

So you could certainly have something that looks like:

  multi foo(int i < 5) {
    print "Smaller than 5!";
  }
  multi foo(int i >= 5) {
    print "5 or bigger!";
  }

in your program, if your language supports it.

The implementation issues are a bit of a pain, and while implementation issues shouldn't always get in the way, an explanation is generally warranted.

In a pure type-based MMD system, all we really need for each sub/method that can do MMD is an N-dimensional table, one dimension per parameter that participates in dispatch. Each type has a number assigned to it, so at dispatch time we grab the numbers, index into the table, and dispatch to the resulting method. It's quick, though in its naive implementation it can be pretty memory-hungry. (There are optimizations for that, of course) We can even take advantage of inheritance to find the best match if we don't have an exact match.

In a value or expression based MMD system, it's not that easy. We need to evaluate the parameters to get their values, then run through all the expressions in the type signatures until we find one that matches. This can potentially take quite a while, relatively speaking. It also requires evaluating the parameters to the function at least once for the dispatch, which may cause an unusual and potentially unpredictable number of fetches of active data. It is, though, a much more interesting dispatch mechanism in a loosely typed language like Perl.

Now, in more concrete news, Perl 6 will support type-based MMD. That's no big deal. Any language that uses Parrot's native dispatching will also get the benefits of MMD, though whether you can actually declare a sub or method as MMD in that language is a separate question. (One who's answer is "No", I expect) I don't know if Perl 6 will support value-based dispatch, but it could. Parrot, however, will. Or, more to the point, Parrot will support arbitrary fallback lookup mechanisms. The default will be MMD type-based lookup, but we could, and probably will, provide a MMD value-based lookup that could alternately be swapped in, since it's not any more trouble and, more importantly, has no particular overhead, as it's just one more potential vector off an inflection point (fallback dispatch) that we need to make indirect and overridable anyway, and we can add as many different ways as we like without additional overhead.

So... Even if Perl 6 doesn't do it, and Parrot doesn't provide it by default, you (or someone Altogether Too Clever) could add it in after the fact, try out some different syntaxes, and work something out for Perl 6.2. The nice thing about it is that, since MMD is already going to be in, it's not like value-based MMD will be adding in a new concept, it'll just be adding in a new variant of an existing concept, which is a much easier thing.

Posted by Dan at June 3, 2003 02:29 PM | TrackBack (3)