Title: Multimethods

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.

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.

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.

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 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.

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).

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 Circles 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:

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.

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.

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.

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:

The first four commands run the two .cmm source files through the C++ pre-processor, with the added detail that any #defines 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.

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.