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

General Usage
101

We are talking about runtime type checks (RTTC). If they are avoidable by compiler by most of time they are most of time oposite to inevitable.

RTTC is not necessary to avoid writing code over and over. For example C++ is using templates for this purpose.

I suppose it is true only for type stable code. So Julia’s choice is for example making global variables problematic from this point of view.

If we are trying to look at this discussion retrospectively it seems we still have problem to find good example of useful multiple dynamic dispatch (MDD).

I am afraid that performance is not the key feature why to choose MDD (ie why to choose type instability). I suppose simplicity and reusability could be that features.

So what is good example of MDD (D for dynamic is bold)?

102

You introduced RTTC into this discussion without clearly defining what it means in the context of Julia. Eg RTTC implementations in the JavaScript world usually do some kind of recovery (coercion, etc). It is not clear what behavior you are implying for Julia code when you talk about “RTTC”. (With the idiomatic/widely used duck typing approach, you just get method errors).

As explained many times in this discussion, to discuss Julia, it is important to decouple the semantics from the implementation. The semantics of multiple dispatch are clearly defined, but the implementation is evolving. Eg before union splitting,

f(flag) = flag ? 1 : missing
g(x::Int) = x + 1
g(x::Missing) = x
h(flag) = g(f(x))

was “dynamic”, now it is still not “static” (depending on how you define the term) but does not involve the same cost. On the one hand, this is an important detail for writing performant code. On the other hand, this is pretty much irrelevant for the semantics of multiple dispatch. Because of this, I find the motivation for an example with dynamic method lookup difficult to understand.

That said, there are many examples of multiple dispatch in Julia (incl Base, standard libraries, third party packages) where either the setup or the code prevents the compiler from determining the types (the motivation for the latter is to prevent the compiler from wasting time on certain code paths). You can locate quite a few by searching for eg @nospecialize or containers with forced type Any.

103

I like to understand what do you mean. Are you telling that C++ templates or/and function overloading are semantically multiple dispatch? If not which property of semantic multiple dispatch do you think is broken?

104

I wasn’t talking about C++ at all.

None. I think that multiple dispatch is a gift to mankind from the Lisp Gods. Combined with the power of Julia’s parametric types and the idioms that evolved since (traits!), it’s just perfection.

Hope this helps to clarify.

3 Likes
105

About RTTC (runtime type check).

Julia doc is ls linked to wiki which is saying:
" Multiple dispatch or multimethods is a feature of some programming languages in which a function or method can be dynamically dispatched based on the run time (dynamic) type or, in the more general case, some other attribute of more than one of its arguments. "

and

“When working with languages that can discriminate data types at compile time, selecting among the alternatives can occur then. The act of creating such alternative functions for compile time selection is usually referred to as overloading a function.”

Understanding this two ideas is crucial to discuss properly about question brought by this discussion thread.

If we want multiple dispatch which is not simple function overload we need to discuss about code where data type is checked in runtime to chose proper specialized method.

From performance point of view this type check needs sources (CPU, memory) so it is worse if there is way to avoid it by static overloading. (which is why I react in first place)

106

You are laboring under a misconception. When the compiler can prove something AOT, no “runtime” check is necessary to implement multiple dispatch.

Which is kind of the central idea for Julia.

4 Likes
107

It is not about my conception. It is about conception of question which was bring here by @dataSurfer . (question about dynamic dispatch and overloading).

Second question is about performance gain by multiple dispatch introduced by @ffevotte which I think is problematic idea.

Your conception is your paradigm and you could have your truth there. I understand what you mean. But it (sorry) bring not any new light into 2 problems I was talking about.

108

You are just repeating the arguments that were done to death further up in the thread. I suggest you go back and read before continuing.

3 Likes
109

Semantics: what does it mean to write down some code

Dynamic dispatch/Runtime type checks, etc: how does a given language implementation achieve code that carries out that meaning.

Only the semantics are defined by the Julia language specification. The compiler is free to use any implementation of those semantics. Sometimes it’s going to use a dynamic dispatch, sometimes it can determine that it’s safe to just jump directly to a particular “hard coded” method choice. The same thing is true say for something like a sqrt function. Sometimes the compiler might need to check that the argument is positive and if not throw an error… other times it might know the argument is positive and skip the check… whether it checks or not is irrelevant to the proper functioning of the code it only matters for how fast the calculation is…

Same story for whether a method call uses dynamic dispatch. sometimes it’s needed to produce the right answer, other times it isn’t needed and the code is then faster… both ways give the same answer.

2 Likes
110

Right. I was about to say the same thing to everyone. They are really referring to method overloading. Multiple dispatch is when the method returns a different value based on what is calling it. For languages that don’t support it that is what the visitor pattern solves. SmallTalk supports multiple dispatch from what i am told.

111

I can’t believe this is appearing in a Julia forum… I don’t believe this is not trolling :laughing:

1 Like
113

Ha ha. Fido is barking up the wrong tree. I love it.

114

I apologize ahead of time for resurrecting an old thread here, but I think a brief summary of this discussion might be helpful for posterity. There is a lot of confusion in this thread over semantics and definitions, which likely makes it rather time consuming and difficult to read for newcomers and non-CS folk. I am actually a computer scientist by training, so perhaps I can help a bit here.

Conclusion 1: Julia does have multiple dispatch, not just static overloading.

Put in the simplest terms, multiple dispatch is when functions/methods are called based on the runtime types of more than one argument. Contrary to what is claimed by @dataSurfer (OP), whether or not Julia’s compiler can infer these types during specialization is irrelevant. A simple example to illustrate this:

f(x::Real) = x + 1
f(2.0)

The static type of x in f is Real. The runtime type is Float64. In a language with static dispatch/overloading, + would be invoked with an argument of type Real (regardless of the runtime type of x), whereas in Julia, it will be invoked with the runtime type of Float64.

As pointed out by @StefanKarpinski and @yuyichao, there is no such concept of a static type in Julia, since all types are resolved at runtime, either via a dynamic type check or via type inference during compilation.

Conclusion 2: “Compile-time” in Julia has a different meaning than in static languages.

It seems to me like one of the more significant sources of confusion in this discussion was the precise meaning of compile-time vs runtime in Julia. The meaning of compile-time in Julia is fundamentally different than compile-time in C/C++, Java, or other statically typed languages. In Julia, compilation happens lazily (or “just in time”) and functions are compiled based on the specific runtime types supplied by the caller. In statically typed languages, compilation happens entirely ahead of time (before anything is executed) and functions are compiled based on their static types as declared by the programmer in the source code, full stop. Any further inlining or clever optimizations by the compiler are completely irrelevant to the actual semantics of the type system.

So this argument:

…is not correct because it confuses the two meanings of “compile time”. In C/C++, Java, etc, functions are not compiled “when you call them” but rather ahead of time based on the type information available in the source code.

Example of multiple dispatch vs single dispatch and static dispatch

Taking inspiration from @Oscar_Smith’s example, let’s consider a very simple implementation of ordinary least squares:

ols(x,y) = inv(x'x)x'y

This very naive implementation already works for any appropriately sized x and y, including the multivariate case where x is a matrix or multiple-target case where y is a matrix. Furthermore, if x and y have special types (e.g. Diagonal, Tridiagonal, SparseMatrixCSC, etc.), we get the potentially optimized implementations of ', *, and inv for free.

How would we accomplish this with single dispatch and/or static overloading?

Well first, we would need types on x and y, since the implicit type for a type-free parameter in Julia is Any. With static overloading, the compiler (in a static language, not in Julia) would then try to find ', *,inv methods with types Any which of course should not generally be defined. So we would need to at least have:

ols(x::AbstractVector{T}, y::AbstractVector{T}) where {T} = ...
ols(x::AbstractMatrix{T}, y::AbstractVector{T}) where {T} = ...
ols(x::AbstractMatrix{T}, y::AbstractMatrix{T}) where {T} = ...

However, this is still not enough. In order to accomplish similar behavior with static overloading, we would need concrete overloads for each special type, e.g:

ols(x::Tridiagonal, y::AbstractVector{T}) where {T} = ...
ols(x::SparseMatrixCSC{T}, y::SparseVector{T}) where {T} = ...
# etc.. for all matrix/vector type combinations

This is not very scalable. Alternatively, if we wanted to leverage single dispatch, we would need to define the operations inv,*,' as methods on each concrete matrix/vector subtype, and * specifically would need to be implemented for each combination of vector-vector, matrix-vector, matrix-matrix, and this would need to be repeated for each specialized implementation.

It gets even worse when you need to handle the case where x and y both have special (structured) types, since you need to handle x*y and y*x (not for ols, but in general) separately. Single dispatch is by nature not commutative.

Julia’s multiple dispatch therefore allows for an enormous amount of (often very efficient) synergy between types and implementations which do not necessarily know anything about each other. This simply isn’t possible with static overloading, and is often prohibitively difficult with single dispatch. For those of you who teach Julia to students, I would definitely recommend emphasizing this point!

I hope that my necromancy will be useful to future Discourse lurkers who stumble upon this thread :slight_smile: If not, then I apologize! Happy coding!

62 Likes
115

I wonder how this part of the reasoning changes if JET.jl is considered part of Julia static typechecker?

116

It doesn’t. JET does abstract interpretation using the same approach as Julia’s own type inference and optimization passes and even reuses large parts of the existing compiler infrastructure for its analysis. It doesn’t change any of the language semantics.

6 Likes
117

I am able to promote this summary to be the solution (didn’t know that I have that power :slight_smile: ). I like the summary, any objections to make it the solution? I didn’t checked if there are other answers in this thread which deserve it too. At least to have a solution would help those who stumble over this thread.

4 Likes
118

I would also nominate this answer by @StefanKarpinski which touched on a lot of the same points that I raised in my summary.

2 Likes
119

Best if @dataSurfer would do this.

120

It may be a good idea to add the answer to the FAQ of Julia’s manual, given that Julia cites multiple dispatch as a main feature. I was also confused by this for a long time.

1 Like
121

I marked yours as the answer because I think it’s a better overview of the whole discussion and it refers to mine so people can find it that way if they want more detail.

10 Likes