Multiple Dispatch in C++

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

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).
    }
}       

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.

How to do multiple dispatch on interface in C#?

Use dynamic to select appropriate method overload at runtime:

public class RenderManager
{
    public void Render(IPage page, Renderer renderer)
    {
        try
        {
            renderer.RenderPage((dynamic)page);
        }
        catch (RuntimeBinderException ex)
        {
            throw new Exception("Page type not supported", ex);
        }
    }
}

But of course dynamic typing has performance costs. Benefits - when new type of page added, all you need to change is renderer - just add another overloaded method.

---

Another option is visitor. In this case each page should do dispatching (seems like your second approach):

public interface IPage
{
    void Render(Renderer renderer);
}

public class StaticPage : IStaticPage
{
    public void Render(Renderer renderer)
    {
        renderer.RenderPage(this);
    }
}

public class RenderManager
{
    public void Render(IPage page, Renderer renderer)
    {
        page.Render(renderer);
    }
}

In this case page 'knows' about rendering. And you still should modify renderer when adding new pages.

Is Fortran a multiple dispatch programming language?

Interface blocks (introduced by the interface keyword) are often used for generic interfaces. They work like C++ generics, no dynamic dispatch. You must distinguish static dispatch and dynamic dispatch. Both Fortran and C++ only have single dynamic dispatch by polymorphism using classes and inheritance/overloading.

But interface blocks themselves have several independent kinds of usage in Fortran and only some deal with some kind of overloading. Often they just work like a function declaration in a C++ header.

Take the example from https://www.geeksforgeeks.org/function-overloading-c/ :

void add(int a, int b)
{
  cout << "sum = " << (a + b);
}
 
void add(double a, double b)
{
    cout << endl << "sum = " << (a + b);
}

In Fortran you can do the same but instead declaring both subroutines with the same name straight away, you define two specific subroutines with a different name and make a generic interface for them

interface add
  procedure add_ints
  procedure add_doubles
end interface

...

subroutine add_ints(a, b)
  integer :: a, b
  print *, "sum = ", (a + b)
end subroutine
 
subroutine add_doubles(a, b)
  double precision :: a, b
  print *, "sum = ", (a + b)
end subroutine

This is the good old static dispatch.

Multiple dispatch solution with full maintainability

What I have done for multiple dispatch (turn out my comment into answer):

// Generic IVisitor
// Do: using MyIVisitor = IVisitorTs<Child1, Child2, ...>
template <typename ... Ts> class IVisitorTs;

template <typename T, typename ... Ts>
class IVisitorTs<T, Ts...> : public IVisitorTs<Ts...>
{
public:
    using tuple_type = std::tuple<T, Ts...>;
    using IVisitorTs<Ts...>::visit;

    virtual ~IVisitorTs() = default;
    virtual void visit(const T& t) = 0;
};

template <typename T> class IVisitorTs<T>
{
public:
    using tuple_type = std::tuple<T>;

    virtual ~IVisitorTs() = default;
    virtual void visit(const T& t) = 0;
};

namespace detail {

// retrieve the index of T in Ts...
template <typename T, typename ... Ts> struct get_index;

template <typename T, typename ... Ts>
struct get_index<T, T, Ts...> : std::integral_constant<std::size_t, 0> {};

template <typename T, typename Tail,  typename ... Ts>
struct get_index<T, Tail, Ts...> :
        std::integral_constant < std::size_t, 1 + get_index<T, Ts...>::value > {};

// retrieve the index of T in Tuple<Ts...>
template <typename T, typename Tuple> struct get_index_in_tuple;

template <typename T, template <typename...> class C, typename ... Ts>
struct get_index_in_tuple<T, C<Ts...>> : get_index<T, Ts...> {};

// get element of a multiarray
template <std::size_t I>
struct multi_array_getter
{
    template <typename T, std::size_t N>
    static constexpr auto get(const T& a, const std::array<std::size_t, N>& index)
    -> decltype(multi_array_getter<I - 1>::get(a[index[N - I]], index))
    {
        return multi_array_getter<I - 1>::get(a[index[N - I]], index);
    }
};

template <>
struct multi_array_getter<0>
{
    template <typename T, std::size_t N>
    static constexpr auto get(const T& a, const std::array<std::size_t, N>& index)
    -> decltype(a)
    {
        return a;
    }
};

// Provide an implementation of visitor
// by forwarding to C implementation (which may be non virtual)
template <typename IVisitor, typename C, typename...Ts> struct IVisitorImpl;

template <typename IVisitor, typename C, typename T, typename...Ts>
struct IVisitorImpl<IVisitor, C, T, Ts...> : IVisitorImpl<IVisitor, C, Ts...>
{
    virtual void visit(const T& t) override { C::visit(t); }
};

template <typename IVisitor, typename C, typename T>
struct IVisitorImpl<IVisitor, C, T> : IVisitor, C
{
    virtual void visit(const T& t) override { C::visit(t); }
};

// helper to expand child type to IVisitorImpl
template <typename IVisitor, typename C>
struct IVisitorImplType;

template <typename ... Ts, typename C>
struct IVisitorImplType<IVisitorTs<Ts...>, C>
{
    using type = IVisitorImpl<IVisitorTs<Ts...>, C, Ts...>;
};

// Create an multi array of pointer of function
// (with all combinaisons of overload).
template <typename Ret, typename F, typename Arg>
class GetAllOverload
{
private:
    template <typename...Ts>
    struct Functor
    {
        // function which will be in array.
        static Ret call(F&f, const Arg& arg)
        {
            return call_helper(f, arg, make_index_sequence<sizeof...(Ts)>());
        }
    private:
        // The final dispatched function
        template <std::size_t ... Is>
        static Ret call_helper(F&f, const Arg& arg, index_sequence<Is...>)
        {
            using RetTuple = std::tuple<Ts&...>;
            // static cast is suffisant if arg is the abstract type
            // when given arg is concrete type, reinterpret_cast is required.
            // TODO: build a smaller table with only possible value to avoid that
            return f(reinterpret_cast<typename std::tuple_element<Is, RetTuple>::type>(std::get<Is>(arg))...);
        }
    };

    // helper class to create the multi array of function pointer
    template <std::size_t N, typename Tuple, typename...Ts>
    struct Builder;

    template <typename...Ts, typename...Ts2>
    struct Builder<1, std::tuple<Ts...>, Ts2...>
    {
        using RetType = std::array<Ret (*)(F&, const Arg&), sizeof...(Ts)>;

        static constexpr RetType build()
        {
            return RetType{ &Functor<Ts2..., Ts>::call... };
        }
    };

    template <std::size_t N, typename ...Ts, typename...Ts2>
    struct Builder<N, std::tuple<Ts...>, Ts2...>
    {
        template <typename T>
        using RecType = Builder<N - 1, std::tuple<Ts...>, Ts2..., T>;
        using T0 = typename std::tuple_element<0, std::tuple<Ts...>>::type;
        using RetType = std::array<decltype(RecType<T0>::build()), sizeof...(Ts)>;

        static constexpr RetType build() {
            return RetType{ RecType<Ts>::build()... };
        }
    };

public:
    template <std::size_t N, typename VisitorTuple>
    static constexpr auto get()
    -> decltype(Builder<N, VisitorTuple>::build())
    {
        return Builder<N, VisitorTuple>::build();
    }
};

template <typename Ret, typename IVisitor, typename F, std::size_t N>
class dispatcher
{
private:
    std::array<std::size_t, N> index;

    struct visitorCallImpl
    {
        template <typename T>
        void visit(const T&) const
        {
            *index = get_index_in_tuple<T, IVisitor>::value;
        }

        void setIndexPtr(std::size_t& index) { this->index = &index; }
    private:
        std::size_t* index = nullptr;
    };

    template <std::size_t I, typename Tuple>
    void set_index(const Tuple&t)
    {
        using VisitorType = typename IVisitorImplType<IVisitor, visitorCallImpl>::type;
        VisitorType visitor;
        visitor.setIndexPtr(index[I]);

        std::get<I>(t).accept(visitor);
    }
public:
    template <typename Tuple, std::size_t ... Is>
    Ret operator () (F&& f, const Tuple&t, index_sequence<Is...>)
    {
        const int dummy[] = {(set_index<Is>(t), 0)...};
        static_cast<void>(dummy); // silent the warning unused varaible
        constexpr auto a = GetAllOverload<Ret, F&&, Tuple>::
            template get<sizeof...(Is), typename IVisitor::tuple_type>();
        auto func = multi_array_getter<N>::get(a, index);
        return (*func)(f, t);
    }
};

} // namespace detail

template <typename Ret, typename Visitor, typename F, typename ... Ts>
Ret dispatch(F&& f, Ts&...args)
{
    constexpr std::size_t size = sizeof...(Ts);
    detail::dispatcher<Ret, Visitor, F&&, size> d;
    return d(std::forward<F>(f), std::tie(args...), make_index_sequence<size>());
}

Example usage

struct A;
struct B;
struct C;
struct D;

using IAVisitor = IVisitorTs<A, B, C, D>;

struct A {
    virtual ~A() = default;
    virtual void accept(IAVisitor& v) const { v.visit(*this); }
};
struct B : A {
    virtual void accept(IAVisitor& v) const override { v.visit(*this); }
};

struct C : A {
    virtual void accept(IAVisitor& v) const override { v.visit(*this); }
};
struct D : A {
    virtual void accept(IAVisitor& v) const override { v.visit(*this); }
};

class Object {
    public:
        virtual double foo (A*, A*) { std::cout << "Object::foo A,A\n";  return 3.14; }
        virtual double foo (B*, B*) { std::cout << "Object::foo B,B\n";  return 3.14; }
        virtual double foo (B*, C*) { std::cout << "Object::foo B,C\n";  return 3.14; }
        virtual double foo (C*, B*) { std::cout << "Object::foo C,B\n";  return 3.14; }
        virtual double foo (C*, C*) { std::cout << "Object::foo C,C\n";  return 3.14; }
        virtual char foo (A*, A*, A*) const { std::cout << "Object::foo A,A,A\n";  return '&'; }
        virtual char foo (C*, B*, D*) const { std::cout << "Object::foo C,B,D\n";  return '!'; }  // Overload of foo with three arguments.
        virtual void bar (A*, A*, A*) const { std::cout << "Object::bar A,A,A\n"; }
        virtual void bar (B*, B*, B*) const { std::cout << "Object::bar B,B,B\n"; }
        virtual void bar (B*, C*, B*) const { std::cout << "Object::bar B,C,B\n"; }
        virtual void bar (B*, C*, C*) const { std::cout << "Object::bar B,C,C\n"; }
        virtual void bar (B*, C*, D*) const { std::cout << "Object::bar B,C,D\n"; }
        virtual void bar (C*, B*, D*) const { std::cout << "Object::bar C,B,D\n"; }
        virtual void bar (C*, C*, C*) const { std::cout << "Object::bar C,C,C\n"; }
        virtual void bar (D*, B*, C*) const { std::cout << "Object::bar D,B,C\n"; }
        double fooMultipleDispatch (A*, A*);
        char fooMultipleDispatch (A*, A*, A*);
};

class FooDispatcher
{
public:
    explicit FooDispatcher(Object& object) : object(object) {}

    template <typename T1, typename T2>
    double operator() (T1& a1, T2& a2) const
    {
        return object.foo(&a1, &a2);
    }

    template <typename T1, typename T2, typename T3>
    char operator() (T1& a1, T2& a2, T3& a3) const
    {
        return object.foo(&a1, &a2, &a3);
    }
private:
    Object& object;
};

double Object::fooMultipleDispatch (A* a1, A* a2)
{
    return dispatch<double, IAVisitor>(FooDispatcher(*this), *a1, *a2);
}
char Object::fooMultipleDispatch (A* a1, A* a2, A* a3)
{
    return dispatch<char, IAVisitor>(FooDispatcher(*this), *a1, *a2, *a3);
}

int main() {
    A a_a;
    B a_b;
    C a_c;
    D a_d;
    A* a[] = {&a_b, &a_c, &a_d, &a_a};
    Object object;

    double d = object.foo (a[0], a[1]);  // Object::foo A,A  (no multiple dispatch)
    d = object.fooMultipleDispatch (a[0], a[1]);  // Object::foo B,C
    std::cout << "d = " << d << std::endl;  // 3.14

    object.fooMultipleDispatch (a[0], a[3]);  // B,A -> so best match is Object::foo A,A

    const char k = object.fooMultipleDispatch (a[1], a[0], a[2]);  // Object::foo C,B,D
    std::cout << "k = " << k << std::endl;  // !
}

Live example

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.

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

---

Related Topics