Understanding Double Dispatch C++

Understanding double dispatch C++

Well, obviously, you really don't have fightwho declared in your Creature class, so you need to declare it there, and declare it as virtual.

Double dispatch works in a way that for call (this assumes Warrior& w = ..., not Warrior w):

w.fight(m);

First the virtual mechanism will chose Warrior::fight instead of Monster::fight and then the overloading mechanism will pick Monster::fightwho(Warrior& m) instead of Warrior::fightwho(Warrior& m). Note that it would make more sense if you would have:

Warrior w;
Monster m;
Creature& c1 = w;
Creature& c2 = m;
c1.fight(c2); // not w.fight(m)

Therefore, the method which will eventually be called will be dispatched according to type of the object on which you call it and type of the object sent as argument, i.e. double dispatch

Additionally, please note that this might not be the best example as your types are members of the same hierarchy. Visitor design pattern is a good example of double dispatch implementations in languages which don't support it as first class citizens (i.e. C++ and derivatives: Java, C#...)

As @CrazyCasta correctly notes, when your class hierarchy starts to grow, this approach becomes much harder to maintain and can result in explosion of number of methods, so choose carefully...

What is Single and Double Dispatch?

In short, single dispatch is when a method is polymorphic on the type of one parameter (including the implicit this). Double dispatch is polymorphism on two parameters.

The typical example for the first one is a standard virtual method, which is polymorphic on the containing object's type. And the second one can be implemented via the Visitor pattern.

[update] I assume that in your example, floppyDisk, processor and computer each inherit from a common base class which defines accept as a virtual method. Similarly, the visit* methods should be declared virtual in equipmentVisitor, which should have some derived classes with different visit* implementations. [/update]

Assuming the above, accept is polymorphic on both this and equipmentVisitor. The floppydisk, processor and computer each have their own implementation of accept, so when the visitor calls accept, the cal is dispatched based on the type of the callee. Then the callee calls back the visitor's type specific visit method, and this call is dispatched based on the actual type of the visitor.

In theory there can be triple, quadruple etc. dispatch too, although I have never seen this implemented in practice (in languages that don't support double and higher dispatches by nature, that is - I seem to remember that Smalltalk does?). Double dispatch using Visitor in C++ and similar languages is already quite mind-boggling in itself, so the implementation of triple and higher dispatches would simply be too complicated to be used in real applications.

Double dispatch in C#?

The visitor pattern is a way of doing double-dispatch in an object-oriented way.

It's useful for when you want to choose which method to use for a given argument based on its type at runtime rather than compile time.

Double dispatch is a special case of multiple dispatch.

When you call a virtual method on an object, that's considered single-dispatch because which actual method is called depends on the type of the single object.

For double dispatch, both the object's type and the method sole argument's type is taken into account. This is like method overload resolution, except that the argument type is determined at runtime in double-dispatch instead of statically at compile-time.

In multiple-dispatch, a method can have multiple arguments passed to it and which implementation is used depends on each argument's type. The order that the types are evaluated depends on the language. In LISP, it checks each type from first to last.

Languages with multiple dispatch make use of generic functions, which are just function delcarations and aren't like generic methods, which use type parameters.

To do double-dispatch in C#, you can declare a method with a sole object argument and then specific methods with specific types:

using System.Linq;  

class DoubleDispatch
{ 
    public T Foo<T>(object arg)
    { 
        var method = from m in GetType().GetMethods()
                   where    m.Name == "Foo" 
                         && m.GetParameters().Length==1
                         && arg.GetType().IsAssignableFrom
                                           (m.GetParameters()[0].GetType())
                         && m.ReturnType == typeof(T)
                   select m;

        return (T) method.Single().Invoke(this,new object[]{arg});          
    }

    public int Foo(int arg) { /* ... */ }

    static void Test() 
    { 
        object x = 5;
        Foo<int>(x); //should call Foo(int) via Foo<T>(object).
    }
}       

What exactly happened that we need double dispatch/visitor in c++

You went too deep, it's way simpler.

C++ virtual functions enable dynamic dispatching based on the type of a single parameter, this. Double dispatching, as the name implies, is dynamic dispatching based on the type of two parameters. Since the language does not provide this feature, the Visitor pattern just uses the built-in single dispatching twice, using each dynamic parameter as this in turn.

You could conceivably implement a Visitor performing triple dispatching or more by continuing this game of musical chairs until all of the dynamic parameters have been this once and been dispatched correctly before the final call.

C++ double dispatch example

Because the argument to printMe() is the pointer to the abstract base class, Printer:

virtual void printMe(Printer *p){

And the purpose of the "double-dispatch" design pattern is to implement print() passing the appropriate derived Document class as a parameter.

Without the overloads for the derived Document classes, the only method in the base class is the one that takes the abstract Document base class:

     p->print(this);

And without the additional overloads, this just calls the same virtual method that takes the virtual Document base class as a parameter.

The sequence of events is:

1. The virtual base class Printer gets called with the parameter being the virtual document class Document.

2. The actual printer implementations use on the actual class that's derived from Document.

3. So, Document's pure virtual printMe() method gets called, from print() that takes the Document pointer as a parameter.

4. The only parameter that printMe() takes is the virtual Printer base class pointer.

5. So, whatever printMe() calls, it can only call the methods defined in the virtual Printer base class.

6. Therefore, if the actual printer implementation needs to use the derived Document class, those methods have to be virtual methods in the Printer base class.

7. Those virtual methods don't really have to be print() overloads. They can be anything. It might be more clear, to some, to name them something different, like printPDF() and printDoc(). If you were to rewrite them, as such, it might be clearer what's going on.

Double Dispatch in C++

One way (certainly not the only way) is to call a virtual function on foo, passing it bar. Each derived type of foo implements this dispatch function the same way, which will pass itself to a virtual handler function in bar.
When you need to add more, you extend the interfaces to accept the new type(s). All the foo functions have the same implementation but they differ such that "this" is correctly the dynamic type of the object.

Also, Andrei Alexandrescu had a nice investigation into this with design alternatives in his (now not-so-modern) book Modern C++ Design, which still covers the idea but is written for c++98, but definitely still worth reading (though many things it says can't be done are now part of C++, partly due to that book.)

See it live: https://godbolt.org/z/oRyVJx

This example has 3 Foo classes, and 2 Bar classes.

#include <iostream>

class BarBase;

class FooBase { 
public:
    virtual ~FooBase() = default;
    virtual void dispatch(BarBase*) = 0;
};

class Foo1;
class Foo2;
class Foo3;

class BarBase {
public:
    virtual ~BarBase() = default;
    virtual void accept(Foo1*) = 0;
    virtual void accept(Foo2*) = 0;
    virtual void accept(Foo3*) = 0;
};

class Bar1 : public BarBase {
public:
    void accept(Foo1*) override;
    void accept(Foo2*) override;
    void accept(Foo3*) override;
};

class Bar2 : public BarBase {
public:
    void accept(Foo1*) override;
    void accept(Foo2*) override;
    void accept(Foo3*) override;
};

class Foo1 : public FooBase {
public:
    void dispatch(BarBase* bar) override { bar->accept(this); }
};

class Foo2 : public FooBase {
public:
    void dispatch(BarBase* bar) override { bar->accept(this); }
};

class Foo3 : public FooBase {
public:
    void dispatch(BarBase* bar) override { bar->accept(this); }
};

void Bar1::accept(Foo1 * f) { std::cout << "Bar1 accepting Foo1\n"; }
void Bar1::accept(Foo2 * f) { std::cout << "Bar1 accepting Foo2\n"; }
void Bar1::accept(Foo3 * f) { std::cout << "Bar1 accepting Foo3\n"; }
void Bar2::accept(Foo1 * f) { std::cout << "Bar2 accepting Foo1\n"; }
void Bar2::accept(Foo2 * f) { std::cout << "Bar2 accepting Foo2\n"; }
void Bar2::accept(Foo3 * f) { std::cout << "Bar2 accepting Foo3\n"; }

//
// Doesn't know which types of foo and bar it has, but it doesn't matter...
//
void call(FooBase& foo, BarBase& bar) {
    foo.dispatch(&bar);
}

int main() {
    Foo1 f1;
    Foo2 f2;
    Foo3 f3;
    Bar1 b1;
    Bar2 b2;

    call(f1, b1);
    call(f2, b1);
    call(f3, b1);
    call(f1, b2);
    call(f2, b2);
    call(f3, b2);
}

output:

Bar1 accepting Foo1
Bar1 accepting Foo2
Bar1 accepting Foo3
Bar2 accepting Foo1
Bar2 accepting Foo2
Bar2 accepting Foo3

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

How can I implement double dispatch when I don't know all the classes in advance?

Why it doesn't work

The problem with your double dispatch implementation is that you expect that the most specific equalityCheck() is called.

But your implementation is totaly based on a polymorphic base class, and equalityCheck(const A*) overloads but does not override equalityCheck(const Base*) !

Otherwhise said, at compile time the compiler knows that A::equalityBounce() could call equalityCheck(A*) (because this is an A*), but unfortunately it calls Base::equalityCheck() which has no specialised version for an A* parameter.

How to implement it ?

For the double dispatch to work, you need to have type specific implementations of the double dispatched equalityCheck() in your base class.

For this to work, the Base needs to be aware of its descendents:

struct A; 

struct Base {

    virtual bool operator==(const Base& rhs) const
    {
        return rhs.equalityBounce(this);
    }

    virtual bool equalityBounce(const Base* lhs) const = 0;
    virtual bool equalityCheck(const Base* lhs) const = 0;
    virtual bool equalityCheck(const A* lhs) const = 0;
};

struct A : public Base {
    ...
    bool equalityBounce(const Base* lhs) const override{  
        return lhs->equalityCheck(this);
    }
    bool equalityCheck(const Base* rhs) const override {
        return false; 
    }
    bool equalityCheck(const A* rhs) const override{
        return a == rhs->a;
    }
};

Note the use of override to make sure that the function really overrides a virtual function of the base.

With this implementation it will work, because:

• A::equalityBounce() will call Base::equalityCheck()
• among all the overloaded versions of this function, it will choose the Base::equalityCheck(A*) because this is an A*
• the invoked Base *lhs object will call its equalityCheck(A*). If lhs is an A* it will hence go for A::equalityCheck(A*) which will produce the expected (correct) result. Congratulations !
• suppose lhs would be a pointer to another class X also derived from Base. In this case, lhs->equalityCheck(A*) would call X::equalityCheck(A*) and could also return the correct response, taking into consideration that you'd compare an X with an A.

How to make it extensible ? The double-dispatch map !

The problem with the double dispatch using a strongly typed language, is that the "bounced" object needs to know about how to compare to specific (known in advance) classes. As your source object and your bounced object are of the same polymorphic base type, the base needs hence to know all involved types. This design limits seriously the extensivbility.

If you want to be able to add any derived type without knowing it in advance in the base class, then you have to go through dynamic types (be it dynamic_cast or typeid):

I propose you here a proposal for dynamic EXTENSIBILITY. It uses single dispatch for comparing two objects of the same type, and a double-dispatch map to compare different types between them (returning by default false if nothing was declared):

struct Base {
    typedef bool(*fcmp)(const Base*, const Base*);  // comparison function
    static unordered_map < type_index, unordered_map < type_index, fcmp>> tcmp;  // double dispatch map

    virtual bool operator==(const Base& rhs) const
    {
        if (typeid(*this) == typeid(rhs)) {  // if same type, 
            return equalityStrict(&rhs);     // use a signle dispatch
        }
        else {                              // else use dispatch map.  
            auto i = tcmp.find(typeid(*this));
            if (i == tcmp.end() ) 
                return false;              // if nothing specific was foreseen...
            else {
                auto j = i->second.find(typeid(rhs));
                return j == i->second.end() ? false : (j->second)(this, &rhs);
            }
        }
    }
    virtual bool equalityStrict(const Base* rhs) const = 0;  // for comparing two objects of the same type
};  

The A class would then be rewrtitten as:

struct A : public Base {
    A(int eh) : a(eh) {}
    int a;
    bool equalityStrict(const Base* rhs) const override {  // how to compare for the same type
        return (a == dynamic_cast<const A*>(rhs)->a); 
        }
};

With this code, you can compare any objects with an object of the same type. Now to show extensibility, I've created a struct X, with the same members than A. If I want to allow to copare A with X, I just have to define a comparison function:

bool iseq_X_A(const Base*x, const Base*a) {
    return (dynamic_cast<const X*>(x)->a == dynamic_cast<const A*>(a)->a);
}  // not a member function, but a friend.  

Then to make dynamic double dipatch work, I have to add this function to the double-dispatch map:

Base::tcmp[typeid(X)][typeid(A)] = iseq_X_A;

Then the resutls are easy to verify:

Base *w = new A(1), *x = new A(2), *y = new X(2);
std::cout << (*w == *w) << "\n";  // true returned by A::equalityStrict
std::cout << (*w == *x) << "\n";  // false returned by A::equalityStrict 
std::cout << (*y == *x) << "\n";  // true returned by isseq_X_A

---

Related Topics