Editing Multiple dispatch (section)

=== Emulating multiple dispatch ===

==== C ====
C does not have dynamic dispatch, so it must be implemented manually in some form. Often an enum is used to identify the subtype of an object. Dynamic dispatch can be done by looking up this value in a [[function pointer]] [[branch table]]. Here is a simple example in C:

<syntaxhighlight lang="c">
typedef void (*CollisionCase)(void);

void collision_AA(void) { /* handle Asteroid-Asteroid collision  */ };
void collision_AS(void) { /* handle Asteroid-Spaceship collision */ };
void collision_SA(void) { /* handle Spaceship-Asteroid collision */ };
void collision_SS(void) { /* handle Spaceship-Spaceship collision*/ };

typedef enum {
    THING_ASTEROID = 0,
    THING_SPACESHIP,
    THING_COUNT /* not a type of thing itself, instead used to find number of things */
} Thing;

CollisionCase collisionCases[THING_COUNT][THING_COUNT] = {
    {&collision_AA, &collision_AS},
    {&collision_SA, &collision_SS}
};

void collide(Thing a, Thing b) {
    (*collisionCases[a][b])();
}

int main(void) {
    collide(THING_SPACESHIP, THING_ASTEROID);
}
</syntaxhighlight>

With the C Object System library,<ref>{{Cite web | url=https://github.com/CObjectSystem/COS |title=C Object System: A framework that brings C to the level of other high level programming languages and beyond: CObjectSystem/COS |website=[[GitHub]] |date=2019-02-19}}</ref> C does support dynamic dispatch similar to CLOS. It is fully extensible and does not need any manual handling of the methods. Dynamic message (methods) are dispatched by the dispatcher of COS, which is faster than Objective-C. Here is an example in COS:

<syntaxhighlight lang="c">
#include <stdio.h>
#include <cos/Object.h>
#include <cos/gen/object.h>

// classes

defclass (Asteroid)
// data members
endclass

defclass (Spaceship)
// data members
endclass

// generics

defgeneric (_Bool, collide_with, _1, _2);

// multimethods

defmethod (_Bool, collide_with, Asteroid, Asteroid)
 // deal with asteroid hitting asteroid
endmethod

defmethod (_Bool, collide_with, Asteroid, Spaceship)
 // deal with asteroid hitting spaceship
endmethod

defmethod (_Bool, collide_with, Spaceship, Asteroid)
 // deal with spaceship hitting asteroid
endmethod

defmethod (_Bool, collide_with, Spaceship, Spaceship)
 // deal with spaceship hitting spaceship
endmethod

// example of use

int main(void)
{
  OBJ a = gnew(Asteroid);
  OBJ s = gnew(Spaceship);

  printf("<a,a> = %d\n", collide_with(a, a));
  printf("<a,s> = %d\n", collide_with(a, s));
  printf("<s,a> = %d\n", collide_with(s, a));
  printf("<s,s> = %d\n", collide_with(s, s));

  grelease(a);
  grelease(s);
}
</syntaxhighlight>

==== C++ ====
{{As of|2021}}, [[C++]] natively supports only single dispatch, though adding multi-methods (multiple dispatch) was proposed by [[Bjarne Stroustrup]] (and collaborators) in 2007.<ref>{{Cite web|last=|first=|date=2007-03-11|title=Report on language support for Multi-Methods and Open-Methods for C ++|url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2216.pdf|quote=Multiple dispatch – the selection of a function to be invoked based on the dynamic type of two or more arguments – is a solution to several classical problems in object-oriented programming.|archive-url=|archive-date=|access-date=|website=}}</ref> The methods of working around this limit are analogous: use either the [[visitor pattern]], dynamic cast or a library:

<syntaxhighlight lang="cpp">
 // Example using run time type comparison via dynamic_cast

 struct Thing {
     virtual void collideWith(Thing& other) = 0;
 };

 struct Asteroid : Thing {
     void collideWith(Thing& other) {
         // dynamic_cast to a pointer type returns NULL if the cast fails
         // (dynamic_cast to a reference type would throw an exception on failure)
         if (auto asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Asteroid-Asteroid collision
         } else if (auto spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Asteroid-Spaceship collision
         } else {
             // default collision handling here
         }
     }
 };

 struct Spaceship : Thing {
     void collideWith(Thing& other) {
         if (auto asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Spaceship-Asteroid collision
         } else if (auto spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Spaceship-Spaceship collision
         } else {
             // default collision handling here
         }
     }
 };
</syntaxhighlight>

or pointer-to-method lookup table:

<syntaxhighlight lang="cpp">
#include <cstdint>
#include <typeinfo>
#include <unordered_map>

class Thing {
  protected:
    Thing(std::uint32_t cid) : tid(cid) {}
    const std::uint32_t tid; // type id

    typedef void (Thing::*CollisionHandler)(Thing& other);
    typedef std::unordered_map<std::uint64_t, CollisionHandler> CollisionHandlerMap;

    static void addHandler(std::uint32_t id1, std::uint32_t id2, CollisionHandler handler) {
        collisionCases.insert(CollisionHandlerMap::value_type(key(id1, id2), handler));
    }
    static std::uint64_t key(std::uint32_t id1, std::uint32_t id2) {
        return std::uint64_t(id1) << 32 | id2;
    }

    static CollisionHandlerMap collisionCases;

  public:
    void collideWith(Thing& other) {
        auto handler = collisionCases.find(key(tid, other.tid));
        if (handler != collisionCases.end()) {
            (this->*handler->second)(other); // pointer-to-method call
        } else {
            // default collision handling
        }
    }
};

class Asteroid: public Thing {
    void asteroid_collision(Thing& other)   { /*handle Asteroid-Asteroid collision*/ }
    void spaceship_collision(Thing& other)  { /*handle Asteroid-Spaceship collision*/}

  public:
    Asteroid(): Thing(cid) {}
    static void initCases();
    static const std::uint32_t cid;
};

class Spaceship: public Thing {
    void asteroid_collision(Thing& other)   { /*handle Spaceship-Asteroid collision*/}
    void spaceship_collision(Thing& other)  { /*handle Spaceship-Spaceship collision*/}

  public:
    Spaceship(): Thing(cid) {}
    static void initCases();
    static const std::uint32_t cid; // class id
};

Thing::CollisionHandlerMap Thing::collisionCases;
const std::uint32_t Asteroid::cid = typeid(Asteroid).hash_code();
const std::uint32_t Spaceship::cid = typeid(Spaceship).hash_code();

void Asteroid::initCases() {
    addHandler(cid, cid, CollisionHandler(&Asteroid::asteroid_collision));
    addHandler(cid, Spaceship::cid, CollisionHandler(&Asteroid::spaceship_collision));
}

void Spaceship::initCases() {
    addHandler(cid, Asteroid::cid, CollisionHandler(&Spaceship::asteroid_collision));
    addHandler(cid, cid, CollisionHandler(&Spaceship::spaceship_collision));
}

int main() {
    Asteroid::initCases();
    Spaceship::initCases();

    Asteroid  a1, a2;
    Spaceship s1, s2;

    a1.collideWith(a2);
    a1.collideWith(s1);

    s1.collideWith(s2);
    s1.collideWith(a1);
}
</syntaxhighlight>

The ''YOMM2'' library<ref name="yomm2">[https://github.com/jll63/yomm2 yomm2], Fast, Orthogonal Open Multi-Methods for C++ by Jean-Louis Leroy.</ref> provides a fast, orthogonal implementation of open multimethods.

The syntax for declaring open methods is inspired by a proposal for a native C++ implementation. The library requires that the user registers all the classes used as virtual arguments (and their sub-classes), but does not require any modifications to existing code. Methods are implemented as ordinary inline C++ functions; they can be overloaded and they can be passed by pointer. There is no limit on the number of virtual arguments, and they can be arbitrarily mixed with non-virtual arguments.

The library uses a combination of techniques (compressed dispatch tables, collision free integer hash table) to implement method calls in constant time, while mitigating memory usage. Dispatching a call to an open method with a single virtual argument takes only 15–30% more time than calling an ordinary virtual member function, when a modern optimizing compiler is used.

The Asteroids example can be implemented as follows:

<syntaxhighlight lang="cpp">
#include <yorel/yomm2/keywords.hpp>
#include <memory>

class Thing {
  public:
    virtual ~Thing() {}
};

class Asteroid : public Thing {
};

class Spaceship : public Thing {
};

register_classes(Thing, Spaceship, Asteroid);

declare_method(void, collideWith, (virtual_<Thing&>, virtual_<Thing&>));

define_method(void, collideWith, (Thing& left, Thing& right)) {
    // default collision handling
}

define_method(void, collideWith, (Asteroid& left, Asteroid& right)) {
    // handle Asteroid-Asteroid collision
}

define_method(void, collideWith, (Asteroid& left, Spaceship& right)) {
    // handle Asteroid-Spaceship collision
}

define_method(void, collideWith, (Spaceship& left, Asteroid& right)) {
    // handle Spaceship-Asteroid collision
}

define_method(void, collideWith, (Spaceship& left, Spaceship& right)) {
    // handle Spaceship-Spaceship collision
}

int main() {
    yorel::yomm2::update_methods();

    std::unique_ptr<Thing> a1(std::make_unique<Asteroid>()),
        a2(std::make_unique<Asteroid>());
    std::unique_ptr<Thing> s1(std::make_unique<Spaceship>()),
        s2(std::make_unique<Spaceship>());
    // note: types partially erased

    collideWith(*a1, *a2); // Asteroid-Asteroid collision
    collideWith(*a1, *s1); // Asteroid-Spaceship collision
    collideWith(*s1, *a1); // Spaceship-Asteroid collision
    collideWith(*s1, *s2); // Spaceship-Spaceship collision

    return 0;
}
</syntaxhighlight>

Stroustrup mentions in ''The Design and Evolution of C++'' that he liked the concept of multimethods and considered implementing it in C++ but claims to have been unable to find an efficient sample implementation (comparable to virtual functions) and resolve some possible type ambiguity problems. He then states that although the feature would still be nice to have, that it can be approximately implemented using [[double dispatch]] or a type based lookup table as outlined in the C/C++ example above so is a low priority feature for future language revisions.<ref>{{cite book |last=Stroustrup |first=Bjarne |title=The Design and Evolution of C++ |publisher=Addison Wesley |location=Indianapolis, IN, U.S.A |year=1994 |chapter=Section 13.8 |isbn=978-0-201-54330-8|bibcode=1994dec..book.....S }}</ref>

==== D ====
{{As of|2021}}, as do many other object-oriented programming languages, [[D (programming language)|D]] natively supports only single dispatch. However, it is possible to emulate open multimethods as a library function in D. The ''openmethods'' library<ref name="openmethods">[https://github.com/jll63/methods.d openmethods], Open Multi-Methods for D by Jean-Louis Leroy.</ref> is an example.

<syntaxhighlight lang="d">
// Declaration
Matrix plus(virtual!Matrix, virtual!Matrix);

// The override for two DenseMatrix objects
@method
Matrix _plus(DenseMatrix a, DenseMatrix b)
{
  const int nr = a.rows;
  const int nc = a.cols;
  assert(a.nr == b.nr);
  assert(a.nc == b.nc);
  auto result = new DenseMatrix;
  result.nr = nr;
  result.nc = nc;
  result.elems.length = a.elems.length;
  result.elems[] = a.elems[] + b.elems[];
  return result;
}

// The override for two DiagonalMatrix objects
@method
Matrix _plus(DiagonalMatrix a, DiagonalMatrix b)
{
  assert(a.rows == b.rows);
  double[] sum;
  sum.length = a.elems.length;
  sum[] = a.elems[] + b.elems[];
  return new DiagonalMatrix(sum);
}
</syntaxhighlight>

==== Java ====
In a language with only single dispatch, such as [[Java (programming language)|Java]], multiple dispatch can be emulated with multiple levels of single dispatch:

[[File:UML class Java single dispatch.svg|UML class Java single dispatch.svg]]

<syntaxhighlight lang="java">
interface Collideable {
    void collideWith(final Collideable other);

    /* These methods would need different names in a language without method overloading. */
    void collideWith(final Asteroid asteroid);
    void collideWith(final Spaceship spaceship);
}

class Asteroid implements Collideable {
    public void collideWith(final Collideable other) {
        // Call collideWith on the other object.
        other.collideWith(this);
   }

    public void collideWith(final Asteroid asteroid) {
        // Handle Asteroid-Asteroid collision.
    }

    public void collideWith(final Spaceship spaceship) {
        // Handle Asteroid-Spaceship collision.
    }
}

class Spaceship implements Collideable {
    public void collideWith(final Collideable other) {
        // Call collideWith on the other object.
        other.collideWith(this);
    }

    public void collideWith(final Asteroid asteroid) {
        // Handle Spaceship-Asteroid collision.
    }

    public void collideWith(final Spaceship spaceship) {
        // Handle Spaceship-Spaceship collision.
    }
}
</syntaxhighlight>

Run time <code>instanceof</code> checks at one or both levels can also be used.