Claim (false): Julia isn't multiple dispatch but overloading

I don’t think so. The section on methods in the Julia manual you are referring to does not distinguish between runtime and compile time. My original point was that there is no real difference between what people in the Julia community call multiple dispatch and what is technically overloading when types are fully resolved. They are identical as far as a compiler is concerned; @tim.holy’s point is that because Julia’s dispatch is capable of occurring at runtime (when types are not fully resolved) we call the whole thing multiple dispatch - a point that I accept - with the addition that it would be helpful if examples emphasising Julia’s multiple dispatch had items where types are dispatched at runtime to clearly distinguish it from overloading.

2 Likes

What about Stefan Karpinski’s examples showing differences in behaviour between overloading and multiple dispatch, separately from compilation optimizations. I’m curious to hear your take on those.

Your definition doesn’t agree with the industry-standard meaning of the term. You can see that it’s incorrect without even having to consider multiple arguments or Julia code—it’s wrong already for single dispatch in C++, Java, C#, etc. Let’s consider C++, which makes this particularly easy to show because the virtual keyword on methods allows choosing between static (non-virtual) and dynamic (virtual) dispatch semantics. Here’s an example program:

#include <iostream>
using namespace std;

class Pet {
    public:
        string name;

        string common_name() { return "pet"; }
        virtual string latin_name() { return "animalia"; };

        virtual void describe() {
            string c = common_name();
            string l = latin_name();
            cout << name << " is a " << c << " (" << l << ")" << endl;
        }
};

class Dog : public Pet {
    public:
        string common_name() { return "dog"; }
        virtual string latin_name() { return "canis lupus familiaris"; }
};
class Cat : public Pet {
    public:
        string common_name() { return "cat"; }
        virtual string latin_name() { return "felis catus"; }
};

int main() {
    Dog fido;  fido.name  = "Fido";
    Cat felix; felix.name = "Felix";

    fido.describe();
    felix.describe();

    return 0;
}

If you compile and run this program, here’s what it prints:

Fido is a pet (canis lupus familiaris)
Felix is a pet (felis catus)

The common_name method is statically dispatched because it is non-virtual and the latin_name method is dynamically dispatched because it is virtual:

  • common_name() is “pet” for both pets because the method is selected solely based on the static type of this in the body of describe, which is always Pet.

  • latin_name() is “canis lupus familiaris” for a Dog and “felis catus” for a Cat because the method is selected based on the runtime type of this.

By your definition, these would both be static dispatch since the compiler can easily see that fido is a Dog and felix is a Cat and doesn’t need to actually do any runtime method selection. However, that disagrees with what people in the industry would call this: the non-virtual one is static dispatch (aka “early binding”) and the virtual one is dynamic dispatch (aka “late binding”). It doesn’t matter at all if the compiler actually does a runtime method lookup or not—the behaviors are different, which is what distinguishes them.

Whether dispatch is dynamic or static is a matter of language semantics (behavior), not implementation. It doesn’t matter when or how the actual method lookup is done: static dispatch dictates that one function body is called whereas dynamic dispatch dictates that a different function body is called. It doesn’t matter how it’s implemented, so if you’re looking at the implementation to see if the dispatch is actually done at runtime or not, you’re barking up the wrong tree.

In Julia there is only dynamic dispatch: there is no way to ask for static (non-virtual) dispatch behavior—it is all dynamic, all the time, on all of the arguments. There isn’t even a concept a static type by which one might statically select a method in principle. The fact that the compiler is very good at statically figuring out which method to call is fortunate but irrelevant.

30 Likes

Well, multiple dispatch as defined in the Julia manual is distinguished by dispatch on the types of all arguments. This is in contrast to dispatch based on the type of the first argument only.

You insist on conflating the meaning of this with dynamic versus static dispatch. I believe that both multiple dispatch and single dispatch as defined above can be both dynamic or static. C++ vs Python, if you will.

2 Likes

I have an extra question, to see if I can get your position straight.

I’m not sure about what the current state of the Julia interpreter is, but are you saying that if I start Julia in ‘interpreter mode’, I’m seeing multiple dispatch, but if I run it in ‘jit mode’ Julia loses its multiple dispatch? The behaviour is irrelevant?

What is the usefulness of this distinction?

2 Likes

I don’t believe that’s the main confusion.

The issue/different from “overloading” is that in C++ there’s also the concept of compile time type in additional to the runtime/true type of the object. It is indeed much closer in concept with static vs dynamic dispatch (at least some meaning of it).

FWIW, I’ve seen dynamic vs static dispatch to mean either a compiler optimization vs the use of compile time/runtime type so the confusion is understandable. In the context of julia though, compile time type simply do not exist and the meaning of static vs dynamic dispatch is reasonably clear.

Not as much in C++, where you have the use of compile time (overload, multiple argument) vs runtime (virtual function, single argument) in the language spec and also compiler optimization (devirtualization) to call virtual function statically.

And that’s why I said this absense of compile time type is the only difference and the main confusion. C++ style overload simply can’t exist without it and if one tries to look for such thing one can easily confuse it with the real type of the object (due to compiler optimization/specialization) and then conclude that multiple dispatch is just overloading.

5 Likes

One of the many things I like about Julia is that I don’t need to understand this post!

29 Likes

But we still read it!

20 Likes

I agree. I think the main confusion here is that the OP should be referring to “dynamic dispatch” instead of multiple dispatch. As it is, the discussion here doesn’t make much sense from the point of view of what the manual of Julia means by multiple dispatch. Discussions based on

“When I use a word,” Humpty Dumpty said in rather a scornful tone, “it means just what I choose it to mean – neither more nor less.”

are not likely to be very fruitful.

1 Like

I think I already conceded that you can call something multiple dispatch if it can (but not necessarily) occur at runtime. Your C++ example uses a virtual method to force overriding and runtime binding in inherited classes. I accept that C++ OOP can be called dynamic dispatch because it can occur at run time as well as compile time.

I have accepted that Julia does do multiple dispatch, but my point is that most of the time that dispatch is not dynamic but equivalent to overloading in a static language. I’m paraphrasing but your counter is that Julia is at runtime all the time, and the compiler is just an optimization over type labels so when that dispatch occurs doesn’t really matter - because you are at runtime all the time.

I think the distinction matters because we use dynamic dispatch when we have uncertainty about which methods need to be called, in C++ that’s virtual which is distinct from regular method overriding. Either way that uncertainty has to be paid for somehow, mostly with a performance penalty because the call occurs at runtime - just when the function is to be executed. A lot of the examples of multiple dispatch in Julia have no uncertainty about which method needs to be called, in fact practically speaking most of the time there’s no uncertainty and no need for dynamic binding. Which is why I re-wrote the example in D using only overloading which would be the equivalent to what the Julia code actually does - there is no uncertainty. If you add uncertainty, you force true dynamic dispatch to occur - which can not be emulated in a static language without runtime dispatch.

2 Likes

The fact that Julia goes to great pains to invalidate that “static” code as you define new methods makes this much less clear to me. Even in the cases where the dynamic dispatch happens to be compiled away, the language has to be prepared to throw that away to preserve its dynamic behaviors.

Because it’s the behavior that matters.

2 Likes

I get what you’re saying, but I’m not entirely sure what the take away is. We seem to have definitively answered the initial question that the thread started with: what Julia does is dynamic multiple dispatch and not function overloading. With a note saying something like “but function overloading is kind of like multiple dispatch except when it does the wrong thing.” Or maybe the note is more like: “Julia’s implementation of multiple dispatch is remarkably good at avoiding dynamic dispatch costs, but if your situation is sufficiently dynamic, sometimes you still have to pay for it.” :man_shrugging:

6 Likes

Yes something like that but I think examples showing multiple dispatch should lean towards things that are not easy to implement using overloading in a static language.

8 Likes

Perhaps something productive that could come out of this would be to sharpen up the C++ section of https://docs.julialang.org/en/v1/manual/noteworthy-differences/index.html to make it a bit more clear to someone like @dataSurfer what we mean when we say

In C++, by default, you have static dispatch, i.e. you need to annotate a function as virtual, in order to have dynamic dispatch. On the other hand, in Julia every method is “virtual” (although it’s more general than that since methods are dispatched on every argument type, not only this , using the most-specific-declaration rule).

Do you have any suggestions for how that can be phrased so that it’s more clear to you and others who share your intuitions and mindset?

5 Likes

This is not true in C++. The C++ compilers these days are fully capable of devirtualizing function calls by specializing (cloning) functions, inlining and inter procedual optimizations. It does not always do that of course, since the compiler may not always have the full picture.

It’s also not true for julia. When you write code like f(a, b) = g(a, b) there’s absolutely no way to figure out what method of g it is calling, just like C++. You always need context.

The only difference here that you need to get used to is that in julia, doing f(a, b) = g(a, b); f(x, y) is never going to be differernt from g(x, y), unlike C++, since the signature of f has absolutely no effect on the dispatch, and so there’s no point doing that in an example. Also, for the same reason, since the signature of the function generally have everything to do with dispatch in C++, people will just write the example like f(a, b) = g(a, b) without the f(x, y) which will look like nothing is known about the dispatch even though in both cases there’s no difference.

To make my point more clear. A C++ example,

// ----
struct Base {
    virtual int g() { return 1; }
};
struct Derived: Base {
    virtual int g() { return 2; }
};

int f(Base &b)
{
    return b.g();
}
// ----

int main()
{
    Derived d;
    return f(d);
}

The part in between // ---- is what you are going to see in a typical C++ example and since context is removed it’ll appear as if the dispatch is unknown, even though the value is always generated with a known type. And to proof the point, if you compile that code with either gcc or clang at O2 or higher, there’s no virtual function call at runtime. (Sure this is a simple example, but I’ll bet you that most C++ examples you’ll find are easy for compilers these days to optimize given the same kind of context you see in julia examples)

Now compare that to a julia example,

abstract type BaseT end
struct Derived <: BaseT end
f(::BaseT) = 1
f(::Derived) = 2
g(d::BaseT) = f(d)
g(Derived())

This will probably be shown as a whole in an example simply because there’s nothing in g(d::BaseT) = f(d) that tells you what this code is doing, the ::BaseT there never have any effect on the f(d), unlike in C++. Because of that, the context is generally included (since that’s the only way you get any idea about what object the code is running on) and it’ll look like the dispatch is known when the code is written, even though it’s every bit as uncertain as the c++ case since you can call g with a yet unknown derived type from BaseT.

(And another reason you’ll usually see context in julia example is that it makes the code runnable from the REPL, a fully runnable program in a C++ example is a much taller order although cppreference.com does a very good job and because of that, the virtual function example at virtual function specifier - cppreference.com can be compiled by a mordern compiler to have no ruutime dispatch)


Basically in both case, without the caller of g, it’s equally uncertain and with it it’s equally certain. The way C++ code is deployed typically does make one case more relavent then another but that has no effect on the spec of the language. JIT for C++ also exist which should be able to do specialization just like julia and writing a dummer julia compiler to make things looks more uncertain is trivial. That’s why the implementation difference is not very important…

8 Likes

I think that examples of multiple dispatch are often geared towards users of Matlab/Python/R etc. to show how it differs from class-based single-dispatch OOP (or even no dispatch at all). Whatever point you are making, it will be of interest to a limited audience of advanced programmers and computer scientists. Focusing on that in tutorials for people new to the concepts are likely to leave the audience baffled.

9 Likes

Maybe something like:

C++ objects are single dispatch, meaning that methods are bound to a single object, and methods can be static or dynamically (virtual) resolved. C++ has a notion of function overloading were multiple functions having the same name with different type signatures are resolved at compile time. In Julia every function or method is multiple dispatch meaning that whether or not the arguments have explicit type hierarchies, they are runtime though the specific way this occurs in the compiler varies depending on type specificity and resolution.

4 Likes

That’s what the C++ standard says (https://isocpp.org/wiki/faq/virtual-functions#dyn-binding-and-static-typing) any deviation from that is compiler dependent optimization. My point still stands, that dynamic dispatch is for uncertainty about types.

Same in julia, the fact that you think in most examples the code does not need runtime information is purely a compiler optimization.

And I’m pretty sure c++ standard does not require dispatch at runtime.

3 Likes

And that’s exactly the case I talked about above where the “dynamic” does not have the same meaning as what is usually used in julia. Using that meaning, all dispatch in julia is dynamic.