[boost] Multimethods Design

From: Jesse Jones (jesjones_at_[hidden])
Date: 2004-09-22 05:19:18

There seems to be some interest in my multimethod library so I thought 
I'd post a message describing the design in more detail. In this 
message I'll focus on the API and ignore the implementation except when 
it affects the API. I may post another message later focusing on the 
implementation.

The vault is still full, so if you want to look at the code go to 
<https://sourceforge.net/projects/multimethods/>. The draft proposal to 
add multimethods as a core feature is also interesting: 
<http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1529.html#1.1.1>. 
Also <http://www.op59.net/accu-2003-multimethods.html> has some info on 
why multimethods are a Good Thing.

The design is actually quite simple. Function objects (aka methods) may 
be added to a generic function object. Then the generic function can be 
called with a set of actual arguments. It will then dispatch to the 
most specialized method using the dynamic type of the actual arguments. 
One way to think of this is as a form of runtime overloading.

The API for generic functions looks like this (using an arity 2 
function as an example):

       template <typename Result, typename Formal1, typename Formal2>
       class generic_function2 : public detail::base_generic_function< 
Result > {

When this is instantiated it creates a function object. Currently the 
arity is encoded in the class name, but presumably boost::preprocessor 
could be used to allow users to instantiate the classes in the way that 
boost:;function does. base_generic_function is a helper class that does 
all of the heavy lifting.

Method formal arguments and actual argument types must be compatible 
with Formal1 and Formal2 (this is checked at compile time). The formal 
argument types may also be any_type which means that the formal 
argument in the methods for that position may be of any type.

The API is as follows. First there are some standard typedefs:

       typedef Result result_type;
       typedef typename Formal1 first_argument_type;
       typedef typename Formal2 second_argument_type;

A default ctor (and compiler provided copy ctor/assignment op):

       generic_function2();

Members to add methods:

       template <typename R, typename T1, typename T2>
       generic_function2& operator<<(R (*method)(T1, T2));

       template <typename Functor>
       generic_function2& operator<<(Functor method);

If the method has the same arguments as an existing method a 
std::runtime_error exception is thrown. If the Functor version is used 
the functor must have result_type, first_argument_type, and 
second_argument_type typedefs.

A member used to invoke the generic function:

       template <typename T1, typename T2>
       RESULT operator()(const T1& arg1, const T2& arg2) const;

This works by building a list of the applicable methods and then 
sorting this list from most to least specific using the dynamic type of 
the actual arguments. A method A is more specific than another method B 
if, for a given set of actual argument, for each argument, A has a 
better match for the actual argument than B in at least one slot and 
the other arguments are no worse than B's (this is similar to the rule 
used for overloaded functions). Argument matching follows the usual C++ 
rules so derived types are better matches than base types and 
promotions are better matches than conversions. If no applicable 
methods or a most specific method cannot be found a runtime_error 
exception is thrown.

When a method is called it may call the next most specific method using 
one of the following methods:

     RESULT next_method();

     template <typename T1, typename T2>
     RESULT next_method(const T1& arg1, const T2& arg2);

The second overload calls the next method using a new set of actual 
arguments, but the types of those arguments don't affect which method 
is called. The first overload calls the next method with the last set 
of actual arguments that were used. If there are no more methods or the 
next method is ambiguous a runtime_error exception is thrown.

The only missing piece is that clients of the library must register 
polymorphic types if they want them to be treated polymorphically. This 
is done with a macro that looks like this:

     #define DECLARE_SUBTYPE(type, base)

This seems like a simple yet flexible API, but there's probably room 
for improvement. For example:

0) The names "generic function" and "method" seem potentially confusing 
in a C++ context (they're from Dylan and (I think) CLOS).

1) There's no support for removing methods. This seems like a good 
idea, but it's not possible to compare arbitrary function objects so 
we'd probably have to add an add_method member which returned a cookie 
that a remove_method member would take to determine which method to 
remove (similar to the way boost::signal works).

2) Policy decisions like type compatibility and ordering are hardwired 
into the code. It might make sense to refactor these into policy 
classes although I'm not sure what they'd be used for. Maybe special 
casing smart pointers.

3) The library allows lossy conversions like floats to chars. This was 
done so that it world work as much like normal C++ code as possible, 
but it's a pretty evil thing. Maybe an option could be added that would 
reject such conversions.

4) boost::bind is a bit annoying because it doesn't provide the 
typedefs that the library requires. This is a known issue with bind 
and, as far as I know, isn't  fixable. The workaround is to assign the 
result of boost:;bind to a boost:;function and add that to the generic 
function.

5) Method formal arguments can't be non-const reference types. The 
problem here is that typeid(const T&) == typeid(T&) == typeid(T). It 
might be possible to work around this, but the type code is already 
full of hacks working around typeid and type_info limitations...

6) It might be a good idea to add a member that will return a function 
pointer or boost:;function to the most specific method for a given set 
of types. This would allow users to skip the overhead of dispatching 
when using multimethods inside loops in some cases.

   -- Jesse