| Packages Used: |
| Perl 5.004 or later............................CPAN Class::ISA 0.2..................................CPAN Memoize 0.48..................................CPAN Class::Multimethods 1.15..................CPAN |
I can still remember the precise moment I first fell in love with polymorphism.
I had just delivered the final version of a medium-sized system (20,000 lines of C++) for running psychophysical visual perception experiments. The system could generate and animate a wide range of visual stimuli in 3D, using left-right stereograms viewed through LCD-shuttered glasses. It had its own scripting language and could run a controlled series of experiments, record a subject's responses, and generate reports and statistics on the results. It had real-time feedback mechanisms. It optimized its graphics to ensure that minimal frame-rates were always met. It was just what the doctors ordered.
So naturally, the very next day, I get this phone call: "It's a great system, Damian. Works like a charm. Easy to use. Does everything we'd hoped. It's just what we ordered. Now could we just add..."
And of course what they wanted was an entirely new category of visual simulus. As well as being able to investigate stereo perception (by sending a slightly offset version of the same signal to both eyes), they now wanted to study differences in left-brain/right-brain neurophysiology, by sending completely different signals to each eye. And could they have it by Friday? As it turned out, they could.
The main stimulus-display subsystem was based on a tightly-coded while loop that did little more than call the draw_me() method of the current Stimulus object. Normally, this object was of the subclass StereoStimulus, but it took all of twenty minutes and about forty lines of code to derive a new subclass called LeftRightStimulus, instantiate an object of that type, and plug it into the display loop. The LeftRightStimulus object encapsulated two subobjects (left_stim and right_stim), each of the existing type MonoStimulus. The complete LeftRightStimulus::draw_me() method looked like this:
// Warning: C++ code! void LeftRightStimulus::draw_me(Viewpoint* vp) { left_stim->draw_me(vp->left_eye()); right_stim->draw_me(vp->right_eye()); }
The new behavior worked the first time. The display loop didn't miss a beat, the graphics optimizer didn't bat an eye, the LCD shutter synchronization mechanism didn't even notice. Every one of the original 20,000 lines of code continued to work as smoothly as before, except now they could handle the new stimulus as well.
The kind of cleverness that allowed me to replace one object with another-and thereby have new behaviors invoked by old code-is known as polymorphism (literally: "many forms"). It's a feature of any language in which the same method call can be applied to many types of objects, which then respond uniquely, each according to its own class. And as you can see, it's a mighty useful and powerful technique.
Unfortunately, I can also remember the precise moment-a few short weeks later-when I fell out of love with polymorphism.
Several can you just adds... down the line, the psychologists decided they now wanted to do what they called "motion tracking under distraction." That is, they wanted to have a subject follow one stimulus with a cursor while other stimuli appeared randomly on the screen (perhaps in another window), and to make the subject respond in various ways (i.e. click the mouse, press a button, select the window) when certain conditions were detected.(1 Psychologists generally run these kinds of tests on their students (i.e. future psychologists), which explains a great deal.)
The problem was that this kind of interaction requires the system to respond appropriately to events of various types, applied to stimuli of various sorts, in windows of various kinds. But you can't just call the handle_me() method of some Event object, because that won't distinguish between the different types of stimuli and windows. Likewise you can't call the handle_event() of a Stimulus object, because that won't identify the specific kind of event and window involved.
So the standard polymorphic mechanism fails, because methods are selected using just a single piece of information-the class of the object on which a method is called. That's known as single dispatch, and it's all you get with most object-oriented programming languages. If your program needs to decide what to do based on the classes of two or more objects at once, then you're out of luck.
In the end, giving the boffins their "motion tracking under distraction" involved a large amount of recoding of the existing system, a number of ugly hacks around the limitations of single dispatch,(Most of which are reported in: Chatterton, D.F. & Conway, D.M., Multiple dispatch in C++ and Java, Proc. TOOLS Pacific 1996, Monash University, Melbourne Australia, pp. 75-87, 1996. and a sense of tragic disillusionment. What I had needed was a generic way of selecting the right method to handle the specific combination of event, stimulus, and window objects. And regular polymorphism just couldn't cut it.
What is Multiple Dispatch?
Like most object-oriented languages, Perl polymorphically selects the subroutine to be invoked in response to a method call. The subroutine selected is the one belonging to the invoking object's class. Hence, a call to $objref->method(@args) invokes CLASSNAME::method, where CLASSNAME is the class into which the $objref object was blessed.
If the class in question doesn't have a suitable method, then the dispatch procedure searches "upwards" through the various superclasses of the object's class, looking for an appropriate subroutine. If that search fails, the dispatch procedure searches the complete inheritance hierarchy again, looking for an AUTOLOAD() subroutine instead.
The important point is that whichever subroutine the method dispatcher eventually selects, it was all determined by the class of the original object on which the method was invoked. That is, according to the type of the first argument only.
As the anecdote above indicates, for most applications the ability to select behavior based on a single type is sufficient. In terms of their expressive power, such single dispatch mechanisms provide the same functionality as a "case" statement. The dispatch mechanism uses the class of the method's first argument like the selector of a switch statement in C, and the various polymorphic methods that can be invoked correspond to the various cases that could be selected. Alternatively, you can think of a polymorphic method as a 1D lookup table, where the first argument's type is the key and the method to be invoked is the corresponding value.(In fact, many languages (including Perl) use such lookup tables to implement, or optimize, calls to polymorphic methods.)
However, some applications like the motion tracking experiment mentioned above need to select the most applicable polymorphic method on the basis of more than one argument. Hence they require a more complex dispatching behavior: something equivalent to nested switches or multidimensional tables. The object-oriented equivalent of those constructs is called multiple dispatch. Whereas single dispatch considers only the first argument and searches for a subroutine compatible with it alone, multiple dispatch works by considering the actual class of every one of a method's arguments, and searching for a subroutine with a set of (typed) parameters compatible with them all.
Typical situations where multiple dispatch is needed include:
• Processing events in an graphical user interface, where the correct response to an event depends not just on the graphical object that receives it, but also on the type of event, and the current mode of the interface (i.e. whether it's active or not, what types of events are enabled, and so on).
• Performing image-processing operations between heterogeneous images, such as a blend between two images that may be in different formats. Using multiple dispatch, the common case where the two images are in the same format can be handled by one (optimized) subroutine, and cases where conversions are required can be delegated to a more general (but probably less efficient) method.
• Handling binary operations on different numerical types (integer, rational, arbitrary-precision, etc.) Often the return type of such an operation will depend on the types of both operands: integer + integer gives integer, integer + rational gives rational, arbitrary-precision + rational gives arbitrary-precision) Multiple dispatch lets you supply a separate method for each combination of operands, and then enables the program to automatically find the right one each time.
• Implementing simulations in which a diversity of objects interact. For example, in a physical simulation, the interaction of two objects colliding will depend on the nature of both (hard/hard, hard/brittle, soft/hard, brittle/sticky, and so on). Using multiple dispatch, handlers for each type of object-object interaction can be coded separately, and the correct handler selected automatically, based on which types of objects are involved.
Generally speaking, multiple dispatch is needed whenever two or more objects belonging to different class hierarchies need to interact, and you find yourself doing different things depending on which objects are being combined.
Note that multiple dispatch isn't the same thing as overloaded functions (in C++ or Java). In those languages, you can define two or more methods with the same name but different parameter lists, and the compiler works out which one to call based on the nominal types of the arguments you specify. In other words, the compiler analyzes the argument type information, selects the corresponding target method, and hardcodes a call to it. That means that if you then call the overloaded method with a set of arguments belonging to derived classes, you still invoke the method that handles the original base class arguments.
In multiple dispatch, on the other hand, the method is always chosen polymorphically, by examining the actual run-time types of the objects you passed as arguments, not the compile-time types of the pointers or references through which those arguments were passed. Hence, if you pass derived objects as arguments, you get the method that handles derived objects.
Multiple Dispatch via "Tests-in-Methods"
Let's consider the example of an object-oriented GUI, since that's probably the most familiar application that can make good use of multiple dispatch. In such a system there would be classes for various types of windows:
package Window; package ModalWindow; @ISA = qw( Window ); package MovableWindow; @ISA = qw( Window ); package ResizableWindow; @ISA = qw( MovableWindow );and for various types of events:
package Event; package ReshapeEvent; @ISA = qw( Event ); package AcceptEvent; @ISA = qw( Event ); package MoveEvent; @ISA = qw( ReshapeEvent ); package ResizeEvent; @ISA = qw( ReshapeEvent ); package MoveAndResizeEvent; @ISA = qw( MoveEvent ResizeEvent );and for various modes that the entire interface may be in:
package Mode; package OnMode; @ISA = qw( Mode ); package ModalMode; @ISA = qw( Mode ); package OffMode; @ISA = qw( Mode );But what happens when a Window has to handle a specific Event in a certain Mode ? That will happen repeatedly in the GUI's event loop:
while ($next_event = shift @event_queue) { $focus_window->receive_event($next_event, $current_mode); }
So each of the classes in the Window hierarchy needs a polymorphic method (receive_event()) that expects two arguments: an Event and a Mode, and determines how to handle the resulting combination. Listing 1 shows an implementation of the Window hierarchy with suitable handler methods.
Notice that each receive_event method of the various classes has what amounts to a nested case statement inside it (hence the description "tests-in-methods"). These if statements are needed to work out which combination of argument types has actually been received, and hence what action to take. Also note that the last alternative in each method is always the same: give up and pass the arguments to the parent class, in the hope that it will be able to handle them.
The various cases that are directly tested don't explicitly cover all possible combinations of argument types. To do so would require a total of 96 alternatives (4 window classes x 6 event types x 4 modes). Instead, the handlers rely on the inheritance relationships of the various classes. For example, there is no specific test to detect a ResizableWindow object receiving a MoveEvent in OffMode. If that actually ever happens, the following sequence ensues:
• ResizableWindow::receive_event() is called, and tests for the various cases it handles. None match, so it executes the else block, invoking its parent class's receive_event method on the same set of arguments.
• In response, MovableWindow::receive_event() is called, and tests for the various cases that it handles. Once again, none match, so the else block is selected and invokes the grandparental receive_event() method on the same arguments.
• That means that Window::receive_event() is called, and it too tests its various cases. The first case discovers that the MoveEvent argument can be treated as a Event (since the MoveEvent class inherits from Event). Then it discovers that the modes also match exactly. Hence it executes the code of the first case.
The result is that the set of arguments (ResizableWindow, MoveEvent, OffMode) have collectively been treated polymorphically, as if their types were (Window, Event, and OffMode). Since there was no case to explicitly handle the actual combination it was given, receive_event() has located a case that will handle it more generally-by abstracting the first two arguments.
This type of "best fit" behavior is extremely useful, because it means you can code the cases you want to handle specially, and then provide one or more catch-all cases (handlers that take base-class parameter types) to deal with other argument combinations.
Normally, a polymorphic method like receive_event() selects the subroutine to call by the type of its first argument alone and, if necessary, works its way up that argument's inheritance tree to find a suitable method. Here, in contrast, it's as if the receive_event() was able to select the appropriate action on the basis of the combined types of all three arguments, working its way up all three inheritance hierarchies at once to find a suitable response.
That's polymorphism with a vengeance!
Multiple Dispatch via a Table
Of course, vengeance always comes at a price. In this instance, instead of the (already high) cost of doing a single polymorphic dispatch on the receive_event() method, the dispatch mechanism now has to do that dispatch, and then test the various cases, and then perhaps re-dispatch receive_event() to a parent class, and then repeat the tests there as well. You can just feel the performance of your application ebbing away.
It would be far better if the call to receive_event() went directly to a single method, which then determined the classes of the arguments involved, looked up the appropriate handler in some table, and invoked that handler directly. No multiple tests, no re-dispatch; just one subroutine call, one table lookup, and the handler is invoked. Listing 2 illustrates the implementation of just such a method.
This version of the Window hierarchy uses a three-dimensional dispatch table, stored in the lexical hash %table. Each dimension of the dispatch table represents the range of possible parameter types of one of the three arguments passed to the receive_event() method: the first dimension representing the Window argument; the second representing the Event argument; the third, the Mode argument.
The table must have entries for each possible combination of Window, Event, and Mode subclasses. To make this less tedious (remember, there are 96 distinct combinations), the init() subroutine is provided. This subroutine takes three references to arrays and a reference to an anonymous subroutine. The three arrays specify the respective sets of parameter types for which the anonymous subroutine should be used as a handler. Consider this call to init() :
init [qw(ModalWindow)], [qw(ReshapeEvent ResizeEvent MoveEvent MoveAndResizeEvent)], [qw(Mode OnMode ModalMode OffMode)] => sub { print "Modal windows can't handle reshape events\n" };
This can be interpreted as:
Locate every dispatch table entry corresponding to a call where the first argument is a ModalWindow; the second argument is either a ReshapeEvent or ResizeEvent or MoveEvent or MoveAndResizeEvent; and the third argument is any mode (Mode or OnMode or OffMode or ModalMode). To each such entry, assign a reference to the specified anonymous subroutine.
The three nested foreach loops in init() iterate through the class names in each array, installing a reference to the handler subroutine ($handler) in the corresponding entries in the dispatch table. In other words, each of the arrays specifies a set of parameter classes, whose objects may appear as the corresponding argument, and the specified handler is called for every combination of parameters in those classes.
Typically, there will be no special handler for most combinations of parameter types, so most of the dispatch table entries will correspond to cases that use the most generic possible behavior. Hence, the first step in setting up the dispatch table is to initialize the entire table to point to a general handler (#case 0). That is:
init $windows, $events, $modes => sub { print "Window $_[0]->{_id} can't handle a ", ref($_[1]), " event in ", ref($_[2]), " mode\n" };
Note that the three lexical variables-$windows, $events, and $modes-were set up with complete lists of the various subclasses of each hierarchy, specifically to make this general initialization easier.
Once the universal "catch-all" case has been set up, particular table entries can be overwritten, to redirect them to more specific handlers. First (#case 1), every combination that includes an OffMode parameter is reinitialized to refer to the handler specific to OffMode. Then (#case 2), every combination of arguments with a ModalWindow, a ReshapeEvent (or any derived class), and a Mode (or any derived class) is given a special handler. Next (#case 3), a hander is installed for the (ModalWindow, AcceptEvent, any-kind-of-mode) combination, and then (#case 4) one for the more specific (ModalWindow, AcceptEvent, OffMode) combination. The initialization process continues until all the handlers are correctly set up.
Once the table is complete, implementing the actual receive_event() method is straightforward. The method simply determines the class of the three arguments (by applying ref to each of them), and then looks up the corresponding entry in %table to retrieve the appropriate handler. If the entry isn't defined, an exception is thrown. Otherwise the handler is called, and passed the original argument list.
As promised, there is only a single receive_event() method, which handles every call on any type of Window object. To make sure that happens, the method is defined in the base class (i.e. in Window) and the derived classes simply inherit it unchanged.
Also note that because this change to the internals of the multiple dispatch mechanism is safely encapsulated within the receive_event() method, the GUI's event loop doesn't have to change at all when a dispatch table is used instead of "tests-in-methods".
while ($next_event = shift @event_queue) { $focus_window->receive_event($next_event, $current_mode); }
Ah, the joys of object orientation!
Order for Table One!
Obviously the whole technique will only work if the dispatch table is correctly set up, which in turn requires that the various table entries must be initialized in the right order. That order is determined by the relationships within and between the set of classes that each argument accepts.
For example, consider the following two initializations:
# initialization A init [qw(Window)], [qw(Event)], [qw(Mode OnMode OffMode ModalMode)] => sub { print "universal handler" }; # initialization B init [qw(Window)], [qw(Event ResizeEvent)], [qw(OffMode)] => sub { print "specific OffMode handler" };
If these initializations had occurred in the opposite order, then the dispatch table entry for the combination (ModalWindow, Event, OffMode) would initially be set up to refer to the OffMode handler, only to be immediately-and incorrectly-overwritten with a reference to the more general "universal" handler.
This same problem may occur wherever there is an overlap in the set of cases covered by two handlers. Obviously, some kind of rule is needed to determine the order in which a given set of table initializations should be performed.
The way to determine the correct order for any two initializations is to work out which of the handlers covers the widest range of cases. Typically, either one handler will cover a superset of the other handler's cases (in which case it's obviously the more general of the two and should be initialized first), or each handler will cover a non-overlapping set of cases (in which case the initialization order doesn't matter), or else there will be some non-inclusive overlap in the cases covered (which is a damn nuisance-so we'll leave it to the next section).
Ignoring the problem of overlapping coverage for the moment, it's relatively straightforward to determine which of two handlers should be initialized first. To do so, you have to ascertain the least-derived class name in each parameter set of each handler. That is, for each argument of each handler, you have to determine the one class within its parameter set that is an ancestor for all the other classes in the same set. For example, within a set such as [qw(ReshapeEvent Event ResizeEvent)], the least-derived class is Event, since it's the ancestor of the other two.
Once you've determined the two lists of least-derived parameter types, you use them to compare the two handlers in question argument-by-argument. The goal is to find an argument position for which the least-derived parameter in one handler is an ancestral class of the least-derived parameter in the other handler. Huh?
Well, looking at initializations A and B above, you can see that, for A, the least-derived parameter classes of the three arguments are (Window, Event, Mode). That's because the first two parameter sets have only one candidate each (Window and Event, respectively), so those classes are automatically the least-derived for those parameters. For the third parameter set, there are four candidates, but Mode is the base class of the other three, so it's clearly the least-derived. By similar logic, the least-derived parameter classes in initialization B are (Window, Event, OffMode).
Having now determined the least-derived parameter class in each argument position of both handlers, you can compare them, one argument position at a time. For their first arguments, the least-derived class of each handler is Window, so they're "equal" at that point. Likewise, the least-derived class for both handlers' second arguments is Event, so they're still equal. Only when you compare the final arguments is there a difference: Mode vs OffMode. Since Mode is an ancestor of OffMode, initialization A wins. Winning implies that initialization A sets up the more general of the two handlers, and hence it should be performed first.
Ordering Disorders
Working out the ordering of two (or more) initializations isn't always so easy, even when each parameter set has only a single element. Consider the following case:
# initialization C init [qw(Window)], [qw(AcceptEvent)], [qw(OffMode)], => sub { print "Window $_[0]->{_id} can't accept in OffMode!\n" }; # initialization D init [qw(ModalWindow)], [qw(Event)], [qw(Mode)] => sub { print "Modal window $_[0]->{_id} can't handle event!\n" };
Comparing the parameter sets for the first argument position suggests that initialization C should be done first (since Window is an ancestor of ModalWindow). However, the opposite conclusion is reached when you compare the parameters for the second argument: Event is the base class of AcceptEvent, so initialization D should come first. The parameter types for the third arguments also suggest that initialization D should be done first (since OffMode is derived from Mode).
Cases such as this are inherently ambiguous. Suppose, for example, that the actual set of arguments passed to receive_event() was (ModalWindow, AcceptEvent, OffMode). Clearly the handler for (Window, AcceptEvent, OffMode) could handle these arguments: it would just treat the ModalWindow argument polymorphically as a Window. Equally clearly, the (ModalWindow, Event, Mode) handler could handle the call, by treating the AcceptEvent argument polymorphically as a Event and the OffMode argument polymorphically as a Mode.
There are several ways to resolve this ambiguity. You might decide that the initialization with the greatest number of more general arguments should come first, in which case initialization D wins (with two ancestral parameter types to C's one). This is known as the "most specific first" policy.
Or you might still follow the algorithm described in the previous section, and effectively give priority to the leftmost parameter where there is a difference. In that case, initialization C wins since the difference in the first parameters favors it. This approach is known as the "leftmost argument wins" policy.
Or you might choose to complain that the two handlers really do make the (ModalWindow, AcceptEvent, OffMode) combination ambiguous, and demand that a third handler be provided specifically for that case. This policy is known as noli accipere nullum stercum.
Generally speaking, it doesn't matter which resolution policy you choose to apply, so long as it's well documented and used consistently. The few languages with built-in support for multiple dispatch generally opt for giving leftmost arguments priority, but that's mainly because it's an easy rule for language designers to implement and for programmers to remember; it doesn't necessarily lead to more predictable or appropriate dispatching behavior.
Comparing the Two Approaches
Having now looked at two very different approaches to implementing multiple dispatch-"tests-in-methods" and dispatch tables-the obvious question is: Which is better?
Multiple dispatching via tables is clearly superior in terms of execution speed. For the implementations shown above, a single call to a handler is dispatched through a dispatch table approximately twice as fast as through a method with embedded tests. That translates to an average improvement of around 20% in real applications, where the cost of actually executing the handler typically dominates the cost of invoking it.
Many developers also find dispatch tables easier to maintain, since the various calls to init() explicitly document the expected behavior for every combination of argument classes. On the other hand, experienced object-oriented programmers may find the use of methods with nested tests more illuminating, because the polymorphism of the initial single dispatch and the subsequent calls to isa allow them to reason abstractly about the overall behavior of the handlers.
Despite its poorer run-time performance, the "tests-in-methods" approach has one indisputable advantage over a fixed dispatch table: it is able to handle requests involving arguments of classes that are not explicitly named in the handlers.
For example, suppose you derived a new type of window from ResizableWindow, called CollapsibleWindow, and a new mode from OnMode called, ActiveMode. If the GUI event hander were called on a set of arguments with classes (CollapsibleWindow, ResizeEvent, ActiveMode), then the "tests-in-methods" version of the handler would initially call the inherited method ResizableWindow::receive_event(), because that's the one that CollapsibleWindow inherits:
sub ResizableWindow::receive_event { my ($self, $event, $mode) = @_; if ($event->isa(MoveAndResizeEvent) && $mode->isa(OnMode)) { print "Moving and resizing window $self->{_id}!\n" } elsif ($event->isa(ResizeEvent) && $mode->isa(OnMode)) { print "Resizing window $self->{_id}!\n" } else { $self->SUPER::receive_event($event,$mode) } }
That method will try each of its tests and discover that the second test suceeds, because the ResizeEvent object is-a ResizeEvent (obviously), and the ActiveMode object is-a OnMode (since it inherits directly from that class). Even though there's no specific code to handle the many new argument combinations created by adding the two new classes, the existing handlers can still make use of inheritance relationships to treat all three arguments polymorphically.
In contrast, if you were using the dispatch table approach, then the receive_event() method inherited from class Window would be called:
sub receive_event {
my ($type1, $type2, $type3) = map {ref} @_;
my $handler = $table{$type1}{$type2}{$type3};
die "No suitable handler found" unless $handler;
$handler->(@_);
}
It would attempt to look up the entry for the new combination in %table, but fail to find it (since no entries for either CollapsibleWindow or ActiveMode were ever initialized). Instead of handling the request in some reasonable way, this version of receive_event() will throw a tantrum.
To add the new classes into the table-dispatched application, you have to ensure that you've also covered all possible combinations of those classes with appropriate extra initializations. For example, to cover the (CollapsibleWindow, ResizeEvent, ActiveMode) combination you could extend the initialization from this:
init [qw(ResizableWindow)], [qw(ResizeEvent)], [qw(OnMode)] => sub { print "Resizing window $_[0]->{_id}!\n" };to this:
init [qw(ResizableWindow CollapsibleWindow)], [qw(ResizeEvent)], [qw(OnMode ActiveMode)] => sub { print "Resizing window $_[0]->{_id}!\n" };
Dynamic Dispatch Tables
Of course, it's not particularly difficult to redesign the dispatch table mechanism so that it can automatically treat unfamiliar argument types polymorphically. To do so, you just need to supply a means of extending the dispatch table whenever it's asked for an unknown combination of types.
That means, on failing to find a suitable entry in the dispatch table, receive_event() will have to search upwards through the various argument hierarchies until it finds a combination of ancestral parameter classes that does have an entry in the table. Listing 3 illustrates the surprisingly extensive changes (in bold) required to provide this new behavior.
The central concern of those changes is what happens when the table doesn't specify a handler for a particular set of arguments. And what happens is that receive_event() compiles a list of the ancestral classes of each argument, and then searches through the full set of combinations of those ancestors (in three nested foreach loops), looking for a combination with an entry in the table. If such an entry is found, it's guaranteed to handle the actual argument types.(...because one of the consequences of an inheritance relationship is that each object conceptually is an instance of every one of its ancestral types, and can be treated as such whenever necessary.)
The ancestors() subroutine is used to compute the set of ancestral classes for each argument. Starting with a list consisting of just the class itself, it iteratively splices the parents of each class into the list, using the symbolic reference @{"$ancestors[$i]::ISA"} (hence the need for no strict "refs"). Each parent list is spliced in just after the class itself, and this eventually produces a depth-first, left-to-right listing of the various ancestors of the original class.
Note that instead of rolling your own hierarchy traversal mechanism, you could use the Class::ISA module (CPAN/authors/id/S/SB/SBURKE/Class-ISA-0.2.tar.gz) to generate the very same ancestry lists. You could also use memoization-see Bricolage: Memoization in TPJ #13-to improve the overall performance of ancestors(), by caching the various ancestor lists it returns.
In any case, having determined the ancestry of each of its arguments, the receive_event() method then iterates through three nested foreach loops, stepping through each combination of possible argument types until it finds a suitable handler. The order of the nested loops (i.e. foreach (@ancestors1)...foreach (@ancestors2)...foreach (@ancestors3)) is important here because that nesting gives priority to the leftmost argument. In other words, combinations featuring the most-derived classes of the leftmost arguments are tried first. This is an extension of the "leftmost argument wins" ambiguity resolution policy described earlier.
Most importantly, once a handler is found for a previously unknown set of argument types, that handler is assigned to the corresponding entry of the dispatch table. That way, the search won't have to be repeated the next time the same set of argument types is encountered.
Because receive_event() can now cope with missing table entries, the initialization process can be made much simpler. It's no longer necessary to ensure that every possible combination of argument classes has a handler, since a suitable polymorphic substitute for any missing combination will be automatically located when the table is forced to extend. So long as you remember to initialize the critical default case: (Window, Event, Mode), then every actual combination of arguments will find its way back there if no more appropriate handler is found.
Hence the init() subroutine can be simplified, so that it merely initializes the entry for the three least-derived classes handled by a particular handler. And those single class names can now be passed as scalar strings rather than as anonymous arrays.
No Free Lunch...
It's important to recognize that extending the dispatch table mechanism in this way comes at a cost. For a start, it greatly complicates receive_event(), which is unfortunate if you're planning to use a number of different multiply-dispatched methods, and will need to implement a distinct dispatch table mechanism for each.
The greater complexity of the mechanism also reduces the dispatch table's raw performance by around 60% for each call in which the table has to be extended. Amortized over a large number of calls, this reduces the real-world performance by around 15-20% (once all combinations have been handled at least once and the table is fully extended).
Of course, the simplified initialization process compensates somewhat for this loss of performance. Unlike the "tests-in-methods” approach, which distributes the various possible handlers amongst numerous methods throughout the first argument's hierarchy, the dynamic table-driven dispatch collects all the alternatives together and specifies them in a generic way that makes the dispatch process much easier to predict. Better still, since each initialization sets up only a single table entry, it doesn't matter what order they're applied in.
...But A Free Side-Salad
Although multiple dispatch is not the same as subroutine overloading in statically-typed languages like C++, under Perl's dynamic typing system the two concepts are more-or-less equivalent. Listing 4, for example, shows an implementation of a subroutine called debug(), which invokes different anonymous subroutines depending on the type of argument it receives.5
The overall structure of the debug() subroutine is identical to the receive_event() method in Listing 3 except that, because the subroutine takes only a single parameter, the table extension mechanism is considerably simplified. The debug_for() subroutine takes the place of init() in previous examples, and is used to initialize the (one-dimensional) dispatch table.
The rest of the code consists of initializations of handlers for various cases. The first case is interesting, in that the specified parameter type is the empty string. This indicates that the handler is to be used when the argument passed is a scalar value, rather than a reference. That's because the ref function returns undef when applied to a non-reference, which is then converted to the empty string when $argtype is used as a key into the %table hash.
The second initializer sets up a handler for objects of class Window. Of course, this case also covers objects of any class derived from Window (courtesy of the dispatch table extension mechanism).
The last four cases set up handlers for references to standard Perl scalars, arrays, hashes, and subroutines. This is interesting because it highlights the fact that the table-driven dispatch doesn't really know anything about classes per se. It just dispatches to whichever handler the ref function tells it to use.
Also note that the handlers for array and hash references recursively call debug() to display their contents, thereby ensuring that the debug() subroutine can handle nested data structures (arrays of arrays, hashes of hashes, hashes of arrays of subs, and so on) correctly. Best of all, the handlers don't even need to detect what kind of hierarchical data structure their array or hash is storing, because the overloaded debug() method sorts it out automatically.
The Class::Multimethods Module
The hand-crafted approaches to multiple dispatch shown above are fine for small applications where it's relatively easy to work out the necessary tests (in the "tests-in-methods" approach) or to construct suitable dispatching mechanisms (for a dispatch table).
But the number of possible cases (and potential handlers) grows with the product of the size of the various class hierarchies involved, and that way lies madness. For example, adding a single new type of window to the GUI adds 24 extra cases (1 new window type x 6 existing events x 4 existing modes). By adding a single class, you just made the already complex task of setting up handlers about 25% more difficult.
Moreover, most of us simply aren't able to directly comprehend the consequences of simultaneous changes in multiple interacting hierarchies.6 Imagine adding that one extra window subclass, and a few extra events specific to it, and throwing in another possible mode. Do any of the existing handlers become ambiguous? If so, the dispatch of existing method calls may also be affected. How many additional handlers will be required? If you're using "tests-in-methods”, will the order of testing have to change? And what happens if that new window subclass inherits from two existing classes (for example, combining MovableWindow and ModalWindow to create a MovableModalWindow)?
In such cases, it can be particularly hard to ensure that all possible combinations of arguments are covered, and dispatched in a consistent and predictable manner. Even if you do manage to encode the correct set of choices, testing and maintenance can become a nightmare. And on top of everything else, you still have to rebuild a separate dispatch table, lookup method, and extension mechanism for each new multiply-dispatched method you add.
As usual, the CPAN offers some Applied Laziness that solves these problems. The Class::Multimethods module (CPAN/authors/id/ DCONWAY/Class-Multimethods-1.15.tar.gz) generalizes and automates the dynamic dispatch table technique described above. It exports a subroutine called multimethod() that can be used to specify multiply-dispatched methods without the need to manually implement the underlying multiple dispatch mechanisms.
For example, the code in Listing 5 shows the multiply-dispatched receive_event() method from Listing 3, but implemented using Class::Multimethods. Note that there's no explicit handler subroutine, no ancestors() subroutine, no %table hash, no hardcoded extension mechanism, and no table initializations.7 Instead, you just say what you mean, and get what you want, with a syntax that's temptingly like subroutine overloading. Now, how much would you expect to pay?
But wait, there's more. The Class::Multimethods module also provides mechanisms to distinguish different types of scalar arguments (say, numeric versus string), to ignore certain arguments entirely, to specify how ambiguous calls are handled, to recover when no handler can be found, and to test the consistency of a given set of multiply-dispatched handlers. All these features are fully described in its extensive documentation.
Damian Conway (damian@csse.monash.edu.au) is a reformed C++ junkie, now doing community service by applying his academic Computer Science background to the betterment of Perl programming. Or in the words of his colleagues: "throwing away his career in order to go hacking.” This article is adapted from his book Object Oriented Perl.