Is multiple dispatch the same as function overloading?

Isn’t multiple dispatch the same as function overloading?

4 Likes

You can do runtime dispatch on multiple argument types. AFAIU in e.g. C++ you can only do that during runtime by the use of virtual functions, which only dispatch on the type of the class instance.

Is a major difference not also that C++ only allows dispatch on built-in types?

1 Like

No C++ allows dispatch on user defined types. In fact I think it only allows runtime dispatch on builtin types. The julia multiple dispatch is indeed similar to the static function overloading but it’s at runtime (i.e. using the dynamic type and not static type) and is more expressive since we have specificity.

The main difference between multiple dispatch and function overloading (esp. as implemented in C++/other OOP langs.) is that overloaded functions still generally have an implicit receiver of fixed type, which constrains method dispatch to only those variants defined for the receiver. Julia, on the other hand, being more of a functional language, dispatches on all arguments.

The classic way of demonstrating this is to imagine you are implementing a game of Asteroids™. As part of the implementation, you need to provide methods for what happens when two game objects collide. So, at first you define (in, for argument’s sake, Java):

public class Asteroid {
  public void collideWith(Asteroid other) { /*...*/ }
  public void collideWith(Ship other) { /*...*/ }
}

public class Ship {
  public void collideWith(Asteroid asteroid) { /*...*/ }
}

Now, let’s imagine that you’re implementing the sequel: Moar Asteroids™. In this version you introduce bullets that the ship can fire. So now you have to add:

public class Asteroid {
  /*...*/
  public void collideWith(Bullet bullet) { /*...*/ }
}

public class Ship {
  /*...*/
  public void collideWith(Bullet bullet) { /*...*/ }
}

public class Bullet {
  public void collideWith(Asteroid asteroid) { /*...*/ }
  public void collideWith(Ship ship) { /*...*/ }
  public void collideWith(Bullet other) { /*...*/ }
}

Or, in other words, 5 new methods for one new type. Let’s say the sequel is so successful that you are implementing the third game in the series: Space Rocks™, and in this version there are also missiles…

Ok, I won’t bore you with an even longer code listing, but if you work it out you’ll see that to add a 4th type of game object you now need to implement 8 new methods, and this number will continue to grow as you add more types.

Now consider the alternate implementation of in Julia, making smart use of multiple dispatch and optional typing:

# Asteroids™ 
abstract type GameObject end
struct Asteroid <: GameObject end
struct Ship <: GameObject end

# Collisions are symmetric
collide(a::GameObject, b::GameObject) = collide(b, a)

collide(first::Asteroid, second::Asteroid) =  #...
collide(asteroid::Asteroid, ship::Ship) =  #...

# Added for Moar Asteroids™
struct Bullet <: GameObject end

collide(first::Bullet, second::Bullet) =  #...
collide(bullet::Bullet, asteroid::Asteroid) =  #...
collide(bullet::Bullet, ship::Ship) =  #...

# etc...

As you can see, the major difference is that we only need to consider each possible set of argument types once, since we can dispatch on all the arguments instead of just all-but-the-first as in Java.

Now, could you write an overloaded C++ global function that effectively does the same? Um…maybe? (Honestly, not sure, my C++ is a bit rusty in this regard.) Technically, I suppose the difference between “multiple dispatch” and “function overloading” is a bit semantic. The pragmatic difference is how each is used, as above.

28 Likes

Being a First Steps question, I suspect the asker was probably looking for a simple “they are similar, but…” kind of answer! If not, then please enjoy the rest of the discussion :slight_smile:

1 Like

Not sure I follow - wouldn’t we in Julia also have to define

collide(asteroid::Asteroid, bullet::Bullet) =  #...
collide(ship::Ship, bullet::Bullet) =  #...

?
(unless we followed some dismal code convention that required us to always pass the arguments e.g in alphatical order of the types).
And wouldn’t that end us up with the same number of functions?

EDIT: just saw this:

Collisions are symmetric

So @jballanc I think I see it know - it is the possibility to dispatch on the abstract type (in collide(a::GameObject, b::GameObject)) specifically only when there isn’t a more specific type defined? That’s neat.

I suspect the asker was probably looking for a simple… answer

The asker might be a professor of computer science for all we know (even if the category is “first steps in julia”) - a good technical question deserves a good technical answer.

2 Likes

As far as I understand, multiple dispatch means dynamic dispatch based on the types of several argument instead of just a single special argument.

Here is an example in C++:

#include <iostream>
#include <vector>

// abstract base class
class A {
public:
    virtual int foo(A* a) {
        return 1;
    }
};

// a concrete class with special behavior
class C1 : public A {
public:
    virtual int foo(A* a) {
        return 2;
    }
    virtual int foo(C1* a) {
        return 3;
    }
};

// a concrete class with default behavior
class C2 : public A {
};


int main() {
    std::vector<A*> v {new C1(), new C2()};
    for (auto e1: v) {
        for (auto e2: v) {
            std::cout << e1->foo(e2) << std::endl;
        }
    }
}

This prints

2
2
1
1

Here, only for the “first argument”, i.e., e1, the runtime type is taken into account while the type of the “second” argument is considered only at compile time.

In Julia, the method is chosen by the runtime types of all arguments. Therefore, we have the following behavior:

abstract A
foo(x::A, y::A) = 1

type C1 <: A end
foo(x::C1, y::A) = 2
foo(x::C1, y::C1) = 3

type C2 <: A end

function main()
    v = [C1(), C2()]
    for e1 in v
        for e2 in v
            println(foo(e1,e2))
        end
    end
end

main()

results in

3
2
1
1

Note the difference for the first method call, i.e., v[0]->foo(v[0]) vs. foo(v[1], v[1]).

4 Likes

My C++ is rusty, but AFAICT in C++ “dynamic” means “runtime”, as opposed to “compile time”. These concepts don’t map well to Julia, where the compiler may select a method when it has enough information available. This is one of the sources of large efficiency gains.

6 Likes

Yup, and even more than that, we needn’t have implemented the symmetric nature of collisions in the first version in order to take advantage of it in the second. This is a subtle, but extremely important aspect of multiple dispatch: because dispatch is performed on all arguments, any existing library can be extended with new methods and types that insert themselves in the dispatch chain.

To give a slightly contrived example, let’s say you have a networking library that takes a destination server type and a path, and manages retrieving the contents of that path in a robust manner (i.e. the library handles disconnects, etc.):

using NetworkFetcher
host = HTTPServer("http://example.com")
data = fetch_resource(host, "/path/to/data.csv")

Now, let’s say that you want to add the ability to also manage FTP downloads. Somewhere in NetworkFetcher there’s a call to open a connection to the server:

module NetworkFetcher
  abstract Server
  struct HTTPServer
  # ...
  end
  function fetch_resource(server::Server, path)
    connect(server)
    # ...
  end
  # ...
end

In order to extend this library to handle FTP servers, you don’t need to re-implement any of the logic in fetch_resource, you only need to create a new implementation of connect that knows how to talk to FTP servers:

using NetworkFetcher
struct FTPServer
  # ...
end
function connect(server::FTPServer)
  # ...
end
host = FTPServer("ftp://example.com")
data = fetch_resource(host, "/path/to/data.csv")

If you look, this general paradigm is already used in a number of Julia libraries (off the top of my head, I know FileIO.jl does something like this).

Also in Julia there is static and dynamic dispatch. Static dispatch happens when inference can figure out the concrete type. For example (with the definitions from my previous post):

function static_dispatch()
    c1 = C1()
    c2 = C2()
    foo(c1, c1)
    foo(c1, c2)
    foo(c2, c1)
    foo(c2, c2)
    nothing
end

@code_warntype static_dispatch()

prints

Variables:
  #self#::#static_dispatch
  c1::C1
  c2::C2

Body:
  begin  # line 23: # line 24:
      $(QuoteNode(3)) # line 25:
      $(QuoteNode(2)) # line 26:
      $(QuoteNode(1)) # line 27:
      $(QuoteNode(1)) # line 28:
      return Main.nothing
  end::Void

(In this case, the method invocations have been replaced with their constant return values, so this is not the best example).

Static dispatch is the same in C++:

    C1 c1 = C1();
    C2 c2 = C2();
    std::cout << c1.foo(&c1) << std::endl;
    std::cout << c1.foo(&c2) << std::endl;
    std::cout << c2.foo(&c1) << std::endl;
    std::cout << c2.foo(&c2) << std::endl;

which prints the same values

3
2
1
1

Thus, multiple dispatch in Julia is only special at runtime, i.e., when the type cannot be statically inferred (there might be more subtle differences in static dispatch, too).

This example is a bit unfortunate, as it uses only single dispatch (and also static dispatch if host would not be a non-const global variable). Therefore, this would work very similar in, e.g., C++.

See also:

5 Likes

Heh, yeah I realized that in trying to make my example “simpler”, I watered it down to the point that I think the true advantages are not so clear. Multiple dispatch is definitely a topic that takes some time to fully understand and appreciate (much like macros).

1 Like

The following short C++ experiment demonstrates dispatch based on two types in several ways. I’m not sure exactly how runtime types vs. compile-time types applies to C++, but I thought I’d share my findings:

oliver@oliver-arch:~/programming/cpp % cat dispatch.cpp

#include <typeinfo>
#include <stdio.h>
#include <iostream>
using namespace std;

template <typename T1, typename T2>
void f(T1, T2) { printf("%s,%s\n", typeid(T1).name(), typeid(T2).name()); }

void g(int, int) { cout << "I,I" << endl; }
void g(int, double) { cout << "I,D" << endl; }
void g(int, char) { cout << "I,C" << endl; }
void g(double, int) { cout << "D,I" << endl; }
void g(double, double) { cout << "D,D" << endl; }
void g(double, char) { cout << "D,C" << endl; }
void g(char, int) { cout << "C,I" << endl; }
void g(char, double) { cout << "C,D" << endl; }
void g(char, char) { cout << "C,C" << endl; }

template <typename T1, typename T2>
void h(T1 a, T2 b) { g(a, b); }

int main() {
    int a;
    double b;
    char c;
    f(a, a);
    f(a, b);
    f(a, c);
    f(b, a);
    f(b, b);
    f(b, c);
    f(c, a);
    f(c, b);
    f(c, c);
    cout << endl;

    g(a, a);
    g(a, b);
    g(a, c);
    g(b, a);
    g(b, b);
    g(b, c);
    g(c, a);
    g(c, b);
    g(c, c);
    cout << endl;

    h(a, a);
    h(a, b);
    h(a, c);
    h(b, a);
    h(b, b);
    h(b, c);
    h(c, a);
    h(c, b);
    h(c, c);
    cout << endl;

    return 0;
}
oliver@oliver-arch:~/programming/cpp % g++ dispatch.cpp -o dispatch && ./dispatch
i,i
i,d
i,c
d,i
d,d
d,c
c,i
c,d
c,c

I,I
I,D
I,C
D,I
D,D
D,C
C,I
C,D
C,C

I,I
I,D
I,C
D,I
D,D
D,C
C,I
C,D
C,C

For types known at compiletime, the combination of operator overloading and templates in C++ gives something very similar to Julia (well, in reality C++ has tricks like SFINAE for generic insanity that has no Julia equivalent, and more if you count concepts in C++20). So in principle, you have much more powerful control of compile time generic programming in C++ (often at the cost of your sanity) . But…

None of that works for types that are not known at compiletime. That would require http://www.stroustrup.com/multimethods.pdf (talked about for decades, so don’t hold your breath). Static and dynamic polymorphism in C++ are incompatible and almost different languages.

Moreover, in Julia you don’t need to consider what is compile time or runtime, and it can still figure out when to devirtualize and inline (which is very difficult for C++ due to its compilation model). Much easier to reason when you can just let the compiler do its job. (post withdrawn by author, will be automatically deleted in 24 hours unless flagged)

Edit: oops, accidentally hit the “withdraw post” on the orginal, but thought it might be worth reposting if there is anyone who finds it useful.

8 Likes

It is not the same, function overloading is a specific case of multiple dispatch, where you just use the type or class of the arguments, to provide the dispatch.

Multiple Dispatch allows for an arbitrary dispatch function that takes all the parameters and can do anything to decide the dispatch, for instance you could take x,y,z as parameters, then determine named directions like northeast above, or southwest below, and then define a method for each named direction. At least this is how you can do it in the Common Lisp Object System.

A function in Julia is essentially just a name. Associated with that name is a number of methods, one for every possible combination of arguments. So when you call a function in Julia, it will look in a table of methods. These methods are sorted according to the specificity of the argument types. Hence it will try to match the calling signature with as specific types as possible first. When it cannot find that it will start looking for slightly more abstract types further down the list.

Eventually it will get to the method with the most abstract arguments at the bottom of the list.

I have a picture illustrating how this works in this medium article. I try to explain multiple dispatch in Julia by contrasting a code example to implement a custom type to represent temperatures in Julia and Python.

1 Like

I know :slight_smile: I think I also did two years ago when I wrote that comment :smiley: My question was the same as the OP, i.e. the semantic difference between dispatch and overloading. Anyway, that medium article is really nice!

1 Like

There is a good explanation of the differences with Julia vs C++ examples here:

6 Likes