Introduction
This article is about multimethods, and a program called Cmm that I have written which adds support for multimethods to C++. I will first explain what multimethods are, and then indicate situations where they could be useful. Finally I will briefly describe how to build projects that use Cmm.
I will be assuming that the reader is familiar with a few C++ features that are relevant to the discussion - for example inheritance, virtual functions, runtime type information (RTTI) and overload resolution. Also, familiarity with the terms static type and dynamic type is useful.
Multimethod resources
The Cmm system itself is available from www.op59.net/cmm/ . This site has complete source code plus documentation that goes into many of the details that have been left out of this article.
Multimethods are not a new idea; for example, the Dylan language (see www.functionalobjects.com/resources/index.phtml ) supports them natively, as does CLOS (Common Lisp).
Bjarne Stroustrup writes about multimethods in The Design and Evolution of C++ (Section 13.8, pages 297-301), and even presents a suggested syntax (which is used by Cmm).
If one restricts oneself to Standard C++, it is possible to approximate multimethods at the expense of verbosity in source code. See Item 31 in Scott Meyer's More Effective C++ and chapter 11 of Andrei Alexandrescu's Modern C++ Design .
The Frost project ( www.flewid.de/julian/ ) adds support for multimethods to the i386-version of the GCC compiler.
Terminology
The term multiple dispatch is often used instead of multimethods; it means essentially the same thing. The term double dispatch is a special case of multiple dispatch with two parameters.
An introduction to multimethods
Multimethods can be looked on as generalising two C++ mechanisms: function overloading (where more than one function exists with the same name but different parameter types) and virtual functions (where the code that is called depends on the dynamic type of a parameter, rather than its static type).
Function overloading
Function overloading will be familiar to most C++ programmers - if some code calls a function with name foo, and there are multiple foo functions declared, the compiler will decide which one to call based on the static types of the parameters. Often, only one of the available functions matches the parameters, but if there is more than one available matching function, the compiler will try to find an unambiguously best match. If one doesn't exist, it will give a compilation error.
Virtual functions
If you have a reference to a base class, and call one of the class's virtual functions, the actual function that gets called depends on what the reference actually refers to at runtime - typically it will be a more derived class. Thus the function that is called depends on the dynamic type (the actual type at runtime, probably a derived class) rather than the static type (the base class that the compiler sees).
Unifying function overloading and virtual functions
Multimethods unify these two ideas by making the choice of which function to call depend on the dynamic types of one or more parameters. Consider a Shape base class with two derived classes Square and Triangle :
struct Shape {...};
struct Square : Shape {...};
struct Triangle : Shape {...};
If we have two functions called Overlap that take different parameter types:
bool Overlap(Square& a, Square& b) {...}
bool Overlap(Square& a, Triangle& b) {...}
then the compiler will resolve a call to the Overlap function:
Square square; Triangle triangle; Overlap( square, triangle); // calls second Overlap function
It can do this because it knows that the type of the first parameter is Square , and the type of the second parameter is Triangle .
However, if we have only Shape& references to derived classes:
Shape& sq = * new Square; Shape& tr = * new Triangle;
Then, although we can see that sq and tr are in fact references to instances of Square and Triangle , the compiler has to ignore this when deciding which function to call - only the static type of the parameters is considered:
Overlap(sq, tr); // compile error - // no matching Overlap(Shape&, Shape&)
Multimethods allow one to say that the overload resolution of a particular function should happen at runtime, using the dynamic types of the parameters. Cmm's syntax for this looks like:
bool Overlap(virtual Shape& a,
virtual Shape& b);
bool Overlap_(Square& a, Triangle& b) {...}
bool Overlap_(Triangle& a, Square& b) {...}
The Overlap(virtual Shape& a, virtual Shape& b); prototype declares the function as dispatching using the dynamic types of its two parameters, while the Overlap_() functions are the real functions that it can call [ 1 ] .
Just as with compile-time overload resolution, it is possible that there is no matching implementation function for a particular combination of dynamic types, or that there is more than one function that matches, but with none of them consistently more specialised than the others. Because this is only discovered at runtime, all the dispatch function can do is to throw an exception - this is what Cmm's dispatch function does.
This can occur in the above example if we try to pass two Circle s to Overlap .
The details of the resolution are essentially the same as the standard C++ compile-time ones (except that only inheritance conversions are considered; conversion operators are ignored). An implementation is considered best if the following 2 conditions apply:
-
All of the best implementation's parameter types match the dynamic types.
-
Each of the best implementation's parameter types is at least as derived as the corresponding parameter type in any other matching implementation.
We cannot have duplicate implementations, so the second condition implies that for each other matching implementation X, the best implementation must have at least one parameter type that is more derived than the corresponding parameter type in X.
Syntax
The trailing underscore in implementation function names is ugly, but it allows one to define an implementation that takes the base parameters, which would otherwise clash with the generated dispatch function.
One possible alternative would be to allow the caller to decide whether dispatch uses dynamic or static types, rather than the callee:
Shape& sq = * new Square; Shape& tr = * new Triangle; bool Overlap( Square& a, Square& b; bool Overlap( Square& a, Triangle& b); Overlap( sq, tr); // compile error - // no matching Overlap( Shape&, Shape&); Overlap( virtual sq, virtual tr); // Ok, caller says uses dynamic types.
Runtime costs
If a multimethod has just one virtual parameter, it is basically the same as a conventional C++ virtual method. In this case, the dispatch can be performed efficiently in terms of both speed and memory usage by making use of vtables (see Stroustrup & Ellis: The C++ Annotated Reference Manual).
When there is more than one virtual parameter, the dispatch mechanism is more complicated; it has to map from a set of more than one dynamic type to a function pointer, by applying the two overload resolution rules mentioned above. This is rather slow and complicated. Cmm's implementation caches the results in a std::map , so that only the first call for a particular combination of dynamic types is slow - subsequent ones are limited primarily by the speed of the std::map implementation.
Ideally, Cmm would optimise the single-virtual parameter case by using conventional C++ virtual methods, but I haven't got round to implementing this.
Why multimethods?
Multimethods and encapsulation
In some ways, multimethods are rather contrary to the object-oriented approach to programming. They are not part of a class definition, and can be added after a class has been designed, which goes against the whole idea of classes having well-defined and fixed interfaces - for example adding a multimethod with a single virtual parameter is like adding a virtual method to a class, except that it can be done without changing the class definition.
On the other hand, it's often useful to be able to add to an existing interface - the real world often changes under our feet in unpredictable ways, making designs obsolete through no fault of the original designer. The set-in-stone nature of C++ classes can often get in the way when this happens. One of the nice things about C++ templates is that they can work with existing types. For example, std::vector<int> works even though the int type was designed decades before std::vector . Similarly the traits technique allows even built-in types to have extra information associated with them.
I've only had a brief look at the Dylan language (which has multimethods designed in from the start), but it is interesting that it still has a mechanism (Modules) to group code together. I'm not familiar with how this works yet, but it would be interesting to try to provide something similar for C++/Cmm, so that we can use the extensibility of multimethods when necessary, but still have some sort of encapsulation enforced by default. C++ namespaces seem close to what is required because they group functions together and can be re-opened, but one cannot make a namespace a friend of a class, and re-opening a namespace is perhaps too easy. There seems to be an increasing discussion on Usenet these days about whether Object Orientation has been over-sold over the last few years. The introduction of templates in C++ has provided different abstraction techniques that are more appropriate for tasks such as containers, and also emphasised global functions operating on external data, instead of objects containing their own methods. Multimethods are similar in that they are global functions that operate on external data, and allow the same sort of extensibility to existing classes.
Multimethod examples
There are a couple of specific situations where I've felt the need for multimethods.
GUI event dispatching
Event dispatching is so common that we often do not think of it as being interesting. However, I think that dispatching events in an extensible way requires multimethods. The event-dispatching problem is: given an event (e.g. one of: mouse click, key press, redraw request etc) and a particular window in a GUI, call the appropriate code. There are two parameters here - the event, and the window. Typically, the window will be created by an application, and we'd expect it to contain information specific to the application - a text editor window might contain a pointer to the text that it is showing, while a dialogue box might contain a set of button handles. Similarly, it seems natural to design the event types as different classes, such as MouseClick , RedrawRequest , KeyPress etc, each with their own data - MouseClick would have the coordinates of where the mouse was clicked, RedrawRequest would have information about which parts of a window require redrawing plus a drawing context.
The simplest way for an application writer to provide the handler functions for their window-type would be to write a function for each event type. It is the event dispatcher's task to choose which of these functions to call. The dispatcher will be aware of all sorts of different windows, each with their own set of handler functions, so its problem is to map from the types of two parameters that are known only at runtime, to a particular function. This is multimethods.
Things can be simplified if there are small fixed number of different event types. In this case, one can perform half of the dispatch with a fairly small and fast switch statement, and then perform the rest by calling a virtual function belonging to the window. But if one is interested in having an extensible system of events, then this breaks down; it's interesting that two widely-used GUI systems, Windows and KDE, both use special mechanisms to implement event dispatching: wizard-generated event code in Windows, and signals/slots in the Qt library used by KDE.
If multimethods were available, one could write GUI code like:
// System-wide gui.h
struct Window {...}; // polymorphic base class
struct Event {...}; // polymorphic base class
struct MouseClick : Event {int x, y;};
struct RedrawRequest : Event {int x1, y1, x2, y2;};
...
void HandleEvent(virtual Window&,
virtual Event&);
void HandleEvent_( Window&, Event&);
/* Generic handler for all events and windows. Probably does nothing. */
// An application
#include "gui.h"
struct MyWindow : Window {...};
// extra data for our window
void HandleEvent_(MyWindow& w,
MouseClick& m){...}
void HandleEvent_(MyWindow& w,
RedrawRequest& r){...}
Natural-language-specific error messages
I ran into trouble a long time ago because I didn't provide a way of generating natural-language-specific error messages from a command-line application I wrote. In truth, I couldn't see a nice way of doing it, so I used hard-coded English text messages.
Looking back, I think the problem arose because generating error messages actually requires multimethods.
If an error occurs, one would like to create an error object that encodes all the available information about the problem (including dynamic information such as filenames), and pass it to whatever error-handling system is used (e.g. throw it, or put the data in a global variable and return an error code). Somewhere else, someone will want to display some information about the error to the user.
The bit of code that created the original error object doesn't want to be concerned with what language will be used to display the error message. Instead, it is better to have a separate function that takes the information in the error object, and displays it in a language-specific way. Note that this will often be more complicated than simply using printf( "Couldn't open file `%s' because error code %i", filename, e) - because some languages would require the order of the error code and the filename to be reversed. In general, we need to have different natural-language-specific functions that format the information in different ways.
I think the natural way of doing this would be to have different classes for each language, and use multimethods to select a display function appropriate to a particular language and a particular error type:
struct Language {...};
struct Error {...};
void ShowError( std::ostream& out, virtual Language&, virtual Error&);
void English : Language {...};
void FileError : Error {
std::string filename;};
void ShowError_( std::ostream& out,
English& l, FileError& e){...}
We could ensure that an English message is generated if language-specific functions aren't available, or at last resort, a generic catch-all message:
void ShowError_(std::ostream& out, English& /*l*/, Error& e)
{
out << "Unrecognised error with typeid " << typeid( e).name() << "\n";
}
void ShowError_(std::ostream& out, Language& l, Error& e)
{
English english;
out << "No support for specified language; using English:\n";
ShowError( out, english, e);
}
The multimethod approach has the advantage that the application code can be written in a natural-language-neutral way, and more than one language can be supported at runtime. In fact, if the dispatch mechanism could cope with the addition of new types at runtime, then one would be able to add new languages even after the application had been shipped. To do this, Cmm would require that C++'s RTTI can cope with new types; I don't know whether real systems' dynamic linking support this sort of thing.
Building with Cmm
Cmm is a command-line program that adds support for multimethods to C++. It does this by working as a source-code translator for a C++ language extension, reading in Cmm source code and outputting C++ source code. In practise, a two-stage translation is necessary.
Cmm has two modes of operation. The first is with the -c flag, and takes an input file that is typically a pre-processed source-file that contains multimethod declarations. As well as translating this into legal C++, Cmm will also write information to a separate file about what multimethod implementations are in the file.
The second mode of operations is with the -l flag. This reads in a set of information files generated by cmm -c, and uses these to generate dispatch functions that are actually appended to one or more of the C++ files that were generated by cmm -c.
The result of running cmm -c and cmm -l is a set of Standard C++ source files that can be compiled and linked as normal.
Assuming there are two Cmm source files one.cmm and two.cmm (plus any other header files that they use), then a complete build using the GNU tools would be done by:
g++ -E -x c++ one.cmm > one.cmmpp
g++ -E -dM -x c++ one.cmm >> one.cmmpp
g++ -E -x c++ two.cmm > two.cmmpp
g++ -E -dM -x c++ two.cmm >> two.cmmpp
cmm -c one.cmmpp one.cpp one.cmmi
cmm -c two.cmmpp two.cpp two.cmmi
cmm -l one.cmmi two.cmmi
g++ -c -o one.o one.cpp
g++ -c -o two.o two.cpp
g++ -o foo.exe one.o two.o
The first four commands run the two .cmm source files through the C++ pre-processor, with the added detail that any #define s that are still active at the end of the pre-processed text are appended to the generated pre-processed source, using g++ -dM. Note that the alternative way of doing this in one command using g++ -dD doesn't seem to work properly; maybe there are some GCC gurus out there that can shed light on this?
The cmm -c commands then generate modified copies of the pre-processed text, in the files one.cpp and two.cpp . Extra information is also generated in the files one.cmmi and two.cmmi .
The cmm -l command then uses the information in one.cmmi and two.cmmi to append new C++ source code (the actual dispatch code) to zero or more of the .cpp files.
Finally, the one.cpp and two.cpp files are compiled and linked as standard C++ source files.
This build process is rather clumsy, and I'm not absolutely clear how to use Make to optimise builds yet - for example if one Cmm file is changed, this could result in any of the generated C++ files changing, because Cmm appends dispatch code to them.
Endnotes
Cmm has to be able to parse C++ source code, which is not particularly easy. However, I decided that multimethods are sufficiently interesting and useful that it is worth taking the trouble to extend the language so that they are easy to use with a simple syntax and straightforward semantics.
The alternative approach is to work within the language, as exemplified by Scott Meyers and Andrei Alexandrescu. This has obvious advantages, but I think that the resulting syntax is too messy to be used in everyday programming.
[ 1 ] These Overlap_() functions can be in separate compilation units and don't even have to be declared in a header. Cmm will still find them because it has access to all compilation units during the build.
