Double Dispatch/Multimethods in C++

Multiple dispatch and multi-methods

They are the same.

When you call a virtual method in C++, the actual method to run is based on the runtime type of the object them method is invoked on. This is called "single dispatch" because it depends on the type of a single argument (in this case, the implicit 'this' argument). So, for example, the following:

class Base {
  public:
    virtual int Foo() { return 3; }
}

class Derived : public Base {
  public:
    virtual int Foo() { return 123; }
}

int main(int argc, char *argv[]) {
  Base* base = new Derived;
  cout << "The result is " << base->Foo();
  delete base;
  return 0;
}

When run, the above program prints 123, not 3. So far so good.

Multiple-dispatch is the ability of a language or runtime to dispatch on both the type of the 'this' pointer and the type of the arguments to the method. Consider (sticking with C++ syntax for the moment):

class Derived;

class Base {
  public:
    virtual int Foo(Base *b) { cout << "Called Base::Foo with a Base*"; }
    virtual int Foo(Derived *d) { cout << "Called Base::Foo with a Derived*"; }
}

class Derived : public Base {
  public:
    virtual int Foo(Base *b) { cout << "Called Derived::Foo with a Base*"; }
    virtual int Foo(Derived *d) { cout << "Called Derived::Foo with a Derived*"; }
}

int main(int argc, char *argv[]) {
  Base* base = new Derived;
  Base* arg = new Derived;

  base->Foo(arg);

  delete base;
  delete arg;
  return 0;
}

If C++ had multiple-dispatch, the program would print out "Called Derived::Foo with a Dervied*". (Sadly, C++ does not have multiple-dispatch, and so the program prints out "Called Derived::Foo with a Base*".)

Double-dispatch is a special case of multiple-dispatch, often easier to emulate, but not terribly common as a language feature. Most languages do either single-dispatch or multiple-dispatch.

Implementing double dispatch with two class hierarchies in C++

Either your base observer class needs to know how to observe any event type, or your base event class needs to know how to be observed by any observer type. Otherwise your double dispatch simply loses the type information gained from your initial dispatch.

In your case, if you added virtual void observe( EventA* evt ) to your BaseObserver class then EventA::beObservedBy would call that version of the observe method and ObserverX would correctly override it.

Why does double dispatch not work in C++?

This is not single dispatch but double dispatch: you want the method to depend both on the actual/real type of the object it is invoked on, and on the actual/real type of the argument.

This issue can be solved by the Visitor design pattern.

C++ double dispatch extensible without RTTI

The first thing to realize is that double (or higher order) dispatch doesn't scale. With single
dispatch, and n types, you need n functions; for double dispatch n^2, and so on. How you
handle this problem partially determines how you handle double dispatch. One obvious solution is to
limit the number of derived types, by creating a closed hierarchy; in that case, double dispatch can
be implemented easily using a variant of the visitor pattern. If you don't close the hierarchy,
then you have several possible approaches.

If you insist that every pair corresponds to a function, then you basically need a:

std::map<std::pair<std::type_index, std::type_index>, void (*)(Base const& lhs, Base const& rhs)>
                dispatchMap;

(Adjust the function signature as necessary.) You also have to implement the n^2 functions, and
insert them into the dispatchMap. (I'm assuming here that you use free functions; there's no
logical reason to put them in one of the classes rather than the other.) After that, you call:

(*dispatchMap[std::make_pair( std::type_index( typeid( obj1 ) ), std::type_index( typeid( obj2 ) )])( obj1, obj2 );

(You'll obviously want to wrap that into a function; it's not the sort of thing you want scattered
all over the code.)

A minor variant would be to say that only certain combinations are legal. In this case, you can use
find on the dispatchMap, and generate an error if you don't find what you're looking for.
(Expect a lot of errors.) The same solution could e used if you can define some sort of default
behavior.

If you want to do it 100% correctly, with some of the functions able to handle an intermediate class
and all of its derivatives, you then need some sort of more dynamic searching, and ordering to
control overload resolution. Consider for example:

            Base
         /       \
        /         \
       I1          I2
      /  \        /  \
     /    \      /    \
    D1a   D1b   D2a   D2b

If you have an f(I1, D2a) and an f(D1a, I2), which one should be chosen. The simplest solution
is just a linear search, selecting the first which can be called (as determined by dynamic_cast on
pointers to the objects), and manually managing the order of insertion to define the overload
resolution you wish. With n^2 functions, this could become slow fairly quickly, however. Since
there is an ordering, it should be possible to use std::map, but the ordering function is going to
be decidedly non-trivial to implement (and will still have to use dynamic_cast all over the
place).

All things considered, my suggestion would be to limit double dispatch to small, closed hierarchies,
and stick to some variant of the visitor pattern.

What is - Single and Multiple Dispatch (in relation to .NET)?

C# uses single dispatch, which includes overloaded methods. When you have the code

stringBuilder.Append(parameter);

the dispatcher looks at all methods defined on the stringBuilder's class, and finds the correct one.

For a multiple dispatch example, let's look at Prolog (which is the first one I could think of). You can define a function in prolog as such:

func(Arg1, Arg2) :- ....body....

This is not defined inside any class but in a global scope. Then, you can call func(Arg1, Arg2) on any two arguments and this function will be called. If you want something like overloading, you have to validate the argument types inside the function, and define it multiple times:

func(Arg1, Arg2) :- is_number(Arg1), is_string(Arg2), ....body....
func(Arg1, Arg2) :- is_string(Arg1), is_list(Arg2), ....body....
func(Arg1, Arg2) :- is_number(Arg1), is_list(Arg2), ....body....

Then, any two argument types you would send would both be checked - that is the multiple dispatch part.

In short, single dispatch only looks at methods defined on the first argument (in our first example, the stringBuilder), then resolves the correct overload to call using the other arguments. Multiple dispatch has methods/functions defined in the global scope and treats all arguments the same during overload resolution.

I hope I made myself clear, this is a pretty tough subject.

---

Update: I forgot to mention, multiple dispatch happens at runtime while single dispatch happens at compile time.
Update #2: Apparently, that was not true.

Multiple dispatch in C++

Multi-dispatch is the ability to choose which version of a function to call based on the runtime type of the arguments passed to the function call.

Here's an example that won't work right in C++ (untested):

class A { };
class B : public A { };
class C : public A { }

class Foo
{
  virtual void MyFn(A* arg1, A* arg2) { printf("A,A\n"); }
  virtual void MyFn(B* arg1, B* arg2) { printf("B,B\n"); }
  virtual void MyFn(C* arg1, B* arg2) { printf("C,B\n"); }
  virtual void MyFn(B* arg1, C* arg2) { printf("B,C\n"); }
  virtual void MyFn(C* arg1, C* arg2) { printf("C,C\n"); }
};

void CallMyFn(A* arg1, A* arg2)
{
  // ideally, with multi-dispatch, at this point the correct MyFn() 
  // would be called, based on the RUNTIME type of arg1 and arg2
  pFoo->MyFn(arg1, arg2);
}

...

A* arg1 = new B();
A* arg2 = new C();
// Using multi-dispatch this would print "B,C"... but because C++ only
// uses single-dispatch it will print out "A,A"
CallMyFn(arg1, arg2);

---

Related Topics