What is Single and Double Dispatch?

Question

i have wrote the visitor pattern as follow but i don't understand what is single and double dispatch. AFAIK, single dispatch is invoke a method based on caller type where double dispatch is invoke a method based on caller type and argument type.

I guess double dispatch is happen in single class hierarchy but why visitor class has two class hierarchy but it still considered as double dispatch.

void floppyDisk::accept(equipmentVisitor* visitor)
{
 visitor->visitFloppyDisk(this);
}

void processor::accept(equipmentVisitor* visitor)
{
 visitor->visitProcessor(this);
}

void computer::accept(equipmentVisitor* visitor)
{
 BOOST_FOREACH(equipment* anEquip, cont)
 {
  anEquip->accept(visitor);
 }

 visitor->visitComputer(this);
}

void visitFloppyDisk(floppyDisk* );
void visitProcessor(processor* );
void visitComputer(computer* );

Please explain using the example code i provided.

AFAIK, the first dispatch is happen on object who invoke the accept and second dispatch is happen on object who invoke the visit method.

Thanks.

Sap

Maybe reading this article can help you understand dispatch --not how it is implemented in c++, but the concept – Alphaalphabet

Answer 1

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.

Lunge

+1, multiple dispatch in languages that do not natively support it imply manually writting all the combinations, and that grows exponentially with the number of arguments to dispatch on, which is quite a good reason to try avoiding it. – Alphaalphabet

Answer 2

In your example, you are missing the basics of the mechanism: inheritance and virtuality. Let's assume the following class hierarchy, in addition to your code:

class equipmentVisited
{
  virtual void accept(equipmentVisitor* visitor) = 0;
}

class floppyDisk : public equipmentVisited
{
  virtual void accept(equipmentVisitor* visitor);
}

class processor : public equipmentVisited
{
  virtual void accept(equipmentVisitor* visitor);
}

class computer : public equipmentVisited
{
  virtual void accept(equipmentVisitor* visitor);
}

class equipmentVisitor
{
  virtual void visitFloppyDisk(floppyDisk* );
  virtual void visitProcessor(processor* );
  virtual void visitComputer(computer* );
}

// Some additional classes inheriting from equipmentVisitor would be here

Now, imagine you have this piece of code in some function:

equipmentVisited* visited;
equipmentVisitor* visitor;
// ...
// Here you initialise visited and visitor in any convenient way
// ...
visited->accept(visitor);

Thanks to the double dispatch mechanism, this last line allows any equipmentVisited to accept any equipmentVisitor, no matter what their actual static types are. Eventually, the right function will be called for the right class.

To summarise:

• The first dispatch calls accept() on the appropriate class
• The second dispatch calls the appropriate function on the class selected by the first dispatch

Bandage