What is Single and Double Dispatch?

nicholas picture nicholas · Jul 16, 2010 · Viewed 10.3k times · Source

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.

Answer

Péter Török picture Péter Török · Jul 16, 2010

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.