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

General Usage
81

I think a subtler point here is that when you write some generic library code, you have no idea how it’s going to be called, so you don’t know if the compiler will be able to figure out the correct runtime types or not. Examples that are simple to present and understand also tend to be easy for the compiler to figure out statically, and ways to prevent the compiler from guessing static types in these situations generally seem contrived. But real life is often not so simple. Often as not, libraries get used in situations where static overloading becomes either incorrect or overly restrictive. So static overloading is fine until it isn’t—and as a library author, which case you’re in is not within your control. As a library user, the perspective is even worse: a library that uses static overloading works in simple cases and fails in ways that are to you as a user, mysterious and hard to predict, as you try to do something more complex.

Another way to understand this may be that static overloading, despite being superficially syntactically similar to multiple dispatch, has zero additional expressive power over not having any kind of overloading. The compiler literally translates static overloading to something you could write in C with no overloading by renaming things. Multiple dispatch, on the other hand, can only be emulated in C by building a runtime dynamic dispatch system using void pointers and lookup tables. There is really more expressive power there. Exponentially more expressive power, in fact: the number of possible specializations of a generic function is the product of the cardinalities of the sets of possible types of all of the arguments to the function, so if there are two possibilities for each argument, that’s at least 2^n for n arguments. Single dispatch is linearly more powerful than static because it is proportional to the number possible types of the first argument, so 2 if there are two possibilities. Yet another way to say this is that dynamic multiple dispatch solves the expression problem whereas static overloading does not.

15 Likes
82

For people with some math background, I think the clearest function that Julia has that could not be written any other way is inner(x,y,z)=x'*y*z. This is a function which in Julia works for all appropriately sized vectors and matrices, and can easily be specialized for any combination of matrix structure. Any performance equivalent and equally generalizable C++ function would he orders of magnitude harder to make.

10 Likes
83

I entirely agree: dynamic dispatch is key in writing correct generic code. It is essential that the (runtime) types of all arguments are known to correctly specialize a method. But I guess that my point here is more like: how often do you have to account for the types of two or more arguments in order to decide which method is going to be called? In other words, your f(a, b) = g(a, b) example does not look at all like the traditional examples illustrating multiple dispatch, most of which look like:

f(x::A, y::B) = implemAB
f(x::A, y::A) = implemAA
f(x::B, y::A) = ...

Exactly, and I guess this is my point: I’m always struggling to come up with real-life examples that are:

  • convincing enough for seasoned developers to understand the interest of multiple dynamic dispatch (as opposed to single dynamic dispatch that they might have in their favorite language)
  • simple enough for less experienced developers to understand.

I’m not sure we’re speaking of the same thing here. My understanding is that you’re speaking of the number of possible specializations of the same method. And what I tried to say in my post above was exactly that: the magic about Julia is the compiler’s ability to generate optimized code for all specialized versions of a method. This happens all the time, is key in how Julia operates and achieves performance, and I don’t have much difficulty explaining the benefit of this.

I might not use the correct vocabulary here, but I referred to multiple dispatch as the mechanism thanks to which a method is selected among the list of all methods associated to a given generic function. In other words, I’m referring to situations where the types of several arguments are used to select the correct method.

One such real-life situation is the intersection of two “primitives” which could be of several types:

intersect(::Segment, ::Segment)  = # specific algorithm
intersect(::Segment, ::Circle)   = # another, specific algorithm
intersect(c::Circle, s::Segment) = intersect(s, c)

These are cases where multiple dispatch does offer you the possibility to write (yourself) specific methods for each combination for which it is necessary or beneficial. But in such cases you (as the developer) pay the price of implementing a (potentially large) number of methods.


I’m not sure I’m clear here, so please don’t get me wrong:

  • I really like multiple dispatch and use it all the time (especially to organize code in large projects)
  • I see the interest of dynamic dispatch, and have no difficulty convincing others of this (especially since this often comes for free!)
  • I see the interest of dynamically dispatching on the types of multiple arguments to select the most appropriate method for a given call to a generic function, but I find it less straightforward to explain
  • it is however very clear and easy to explain that, once a method has been selected, specialization of this method for the actual types of its arguments is really useful performancewise
4 Likes
84

All the time.

Hence the whole reply where I talked about this simple case. Claim (false): Julia isn't multiple dispatch but overloading - #50 by yuyichao .

To summarize, there’s no point in writing out f(a, b) = g(a, b) in an example since that is not the point about multiple dispatch. Most examples, including c++ ones, are focused on demostrating a particular feature, and it’s usually preferred to make it clear what’s the input argument is and to make everything as clear as possible. Writing out real code that actually take advantage of the features to do things that are complex enough to give some people the illussion that it “requires multiple dispatch” is not the point of most examples, and that illusion is, well, just an illusion anyway…

In your “tranditional example”, whenever you are calling it, it requires every bit of multiple dispatch even though it might seem clear to you what it is doing. Confusing the reader of the code is not a requirement of multiple dispatch (and dynamic in c++ sense).

2 Likes
85

Well, first, this is not what the OP was asking for to start with (the question was about whether this exists). And then as I said, this happens every time you call a function. It’s very natral since there’s no distinction between runtime and compile time types and so natural that you don’t realize you are doing it.

And of course it’ll be strictly harder to find explicit examples demostrating this than anything else, since what you are looking for is a strict subset of both. And since a good example for either dynamic (c++ sense) dispatch and multiple dispatch are always going to use one concept for clearity, you are guaranteed to not find the explicit use of one feature in another in a way that’s important for understanding (even though they are used). Otherwise what you have is a terrible example for either.

And I’m not sure if there’s a need for such an example. It’s not helpful to learn the language and made up examples like this are not ways to convince anyone.

1 Like
86

Did you mean inner(x,y,z)=x'*y*z?

87

Yes. Fixed.

88

I was rather referring to the OP’s statement that “it’s important to have examples that distinguish it from simple emulation using regular overloading in a static language.” But you’re right, my point was rather that it’s (IMO) important to have examples that illustrate the usefulness of (dynamic) multiple dispatch as opposed to (dynamic) single dispatch. Sorry if I derailed the thread.

Yet the documentation offers plenty of examples, which I think is useful for people to learn.

One such examples, illustrating multiple dispatch, looks like

f(x::Float64, y::Float64) = 2x + y
f(x::Number, y::Number) = 2x - y

and, a bit later to illustrate ambiguities:

g(x::Float64, y) = 2x + y
g(x, y::Float64) = x + 2y
g(x::Float64, y::Float64) = 2x + 2y

This illustrates very well how multiple dispatch works, but not so well why and when you’d use this feature (I do agree that made up examples aren’t terribly convincing). If I had a better example to propose, I’d have made a PR, but the truth is that I don’t have one. I guess my question boils down to this: couldn’t we find nicer illustrations of multiple dispatch? The closest I have is the one I posted above regarding shapes intersections.

One could argue that, in the early stages of learning Julia, such contrived examples are enough to illustrate how multiple dispatch works. Later on, Julia learners can understand the potential that multiple dispatch offers them. For lack of better examples, this is also what I do when teaching Julia. I just would find life easier if I had more meaningful examples to propose in the early stages. I was just hoping that someone would already have come up with simple yet more meaningful examples.

89

That’s exactly my point. I didn’t say examples are useless, and I didn’t say there should be no examples. I said made up examples like these are not to convince anyone. A convincing example proving usefulness of multiple features is guaranteed to be not factorizable to individual features (or it won’t be convincing) and that of itself make it a very bad example for learning.

4 Likes
90

Thanks, I think I understand you point better now.

91

Also I would say for myself, if I was just learning it, I would know that I do not yet have a feel of things and knowing two features are useful should be enough to know that the combination of them is useful in general. The counterexample to this is something that needs more explaination (i.e. why can’t I use two features together).

And along that line, coming up with such an example in this case is also trivial. Take whatever multiple (static) dispatch case you have and just say I may not know the type at runtime/when I write the code, because someone else might be feeding me the input. If you are not happy with this then the only difference I can see between this and your case is that you have a real motivation behind the example you show. Now if that motivation is what you want, then your main difficulty is to find a motivation that’s easy enough to understand for your target audience. I’ll say that the subset of such audience that still can’t just take a small package and read the code to learn/convience themself is pretty small so at that stage you can just use real code and there are a lot out there.

And then if you are just complaining about why is there not a summary of how different features are used in different package. I would agree that such thing could be useful for advanced learners. Though maintaining it would be hard.

92

Both “simple” and “convincing” are very subjective terms (and you can always claim that an example is too simple to be convincing etc), but, again, there are plenty of examples in Base and the standard libraries, to the point that it is hard to read more than 100 LOC without running into one.

Eg a somewhat compact yet still demonstrative example is how the methods of setdiff and setdiff! are organized, with a generic fallback, specializations for Sets, vectors, BitSets. These could even fit on a slide I guess. But again, there are zillion other nice examples, eg algebra for number types, a lot of LinearAlgebra, etc.

Multiple dispatch is one of those things that you don’t realize you need until you are using it, and then you wonder how you could ever program without again. Julia’s parametric multiple dispatch is a game changer in the same way CLOS was. However, if you are out to convince people about its usefulness, you run into the Blub paradox — a lot of context is needed to evaluate it, which is acquired with practice.

7 Likes
93

As a side note, I find this thread super helpful in understanding how Julia’s semantics compare with languages like C++.

14 Likes
94

Mee too. I must say I also had the same questions as the OP back when I was learning Julia. I honestly hope @dataSurfer didn’t get the impression that the community didn’t appreciate this thread and his/her contending replies (and that of all other experts involved here of course). They were quite illuminating.

12 Likes
95

Thanks for the reference to the Blub paradox. I guess that’s more or less what I was referring to when I was speaking of C++ developers used to OOP and single dynamic dispatch, but I didn’t know the term had been coined.

Yes, I guess practice and time are the best way to get people convinced about the usefulness of multiple dispatch (and learn how and when to use it themselves at the same time). And in order to convince people to take that time and practice, I think @StefanKarpinski’s JuliaCon talk is a really useful resource.

3 Likes
96

I am probably missing something. How could permanent runtime type check (and runtime method selection) help to achieve better performance?

97

The key is that by compiling methods for specific types, you avoid far more type-checks than you add. This is because if you have a function and the input types of the arguments, you can figure out the types of all variables used in the function (yes there are some exceptions). The result of this is that for almost all functions, the compiler never has to perform type-checks. Instead most code will be type specific assembly code that is as fast as optimized C. The benefit of this approach over something like C is that you only have to write the code once, and Julia is smart enough to compile special versions for all the combinations of types it needs.

2 Likes
98

Are you are basically agree that runtime type check make performance worse but arguing that Julia compiler is trying hard (and is good) to avoid dynamic dispatch?

Because it is (“for almost all functions, the compiler never has to perform type-checks”) useless for almost all cases?

99

That’s more or less correct but the compiler isn’t trying very hard. The approach julia take is to specialize on the argument type in the compiler, and then teach the users to exploid it for peerformance so it’s not just the job of the compiler if you are trying to compare it with a different language/approach.

In theory, if is certainly true that you can write code that will require runtime type check most of the time, but,

  1. That’s generally not the case for real code
  2. If you actually need it then there’s usually no way around it and not allowing it make writing some code much harder…
4 Likes
100

The way I see it, in an expressive language some type checks are inevitable. This is because if you don’t want to write the same code over and over, you need functions that can accept a variety of types as input.
This means you (semantically compilers in some but not all cases can solve this) either need type checks for your arguments to the functions, or in the functions themselves.
Interpreted languages use the second. The downside of this approach is that it makes all your operations slow even in places where the compiler can actually figure out the types (like + or other simple operations).
By making the choice Julia does, most code doesn’t have any type-checks at all, and Julia almost never has type checks in code that could be written in another language without type checks.

3 Likes