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

I heard a rumour that Julia’s multiple dispatch is “fake news”, in reality it’s overloading because you compile the function before it is run and all you are doing in Julia is just a series of compile and run actions. Is this true?

Thanks in advance.

3 Likes

I mean…no? How does the presence or absence of a compiler affect whether something is multiple dispatch according to…some rumor you heard somewhere?

If you can clarify what you’re actually asking into something more precise, then I’m sure you’ll get a more precise and helpful answer.

13 Likes

Multiple dispatch is resolved at runtime but that’s not what Julia does, it produces code at compile time not runtime.

  • In the world of compiled languages every code must be compiled before it can run (this is different only in interpreted languages)
  • After a specific function has been compiled once it is not compiled again, specific means (in short): name of the function and number and types of parameters
  • In a complex Julia program there will be several compiled functions with equal names (only differing in parameters): multiple dispatch chooses the correct compiled function
  • method (or function) overloading doesn’t compile new methods if the parameters of a new call differ. The overloaded method must exist explicitely before it can be called.

So my answer is: NO, not true.

8 Likes

Maybe this code will clarify a few things:

f(x::Int) = 3x
f(x::Real) = 4x

x = if ARGS[1] == "Int"
    3
else
    3.0
end

println("f(x) = ", f(x))

Running the code twice produces different results:

$ julia test.jl Int
f(x) = 9

$ julia test.jl Real
f(x) = 12.0

This is impossible using compiled languages like C++, because you would need to define the type of the variable at compilation time for overloading to work.

28 Likes

You probably meant methods here instead of functions. It’s also not completely true, because the compiler can decide to inline certain function calls, in which case the code is compiled again.

They will still be the same function, but a function can have multiple methods depending on the argument types and number of arguments.

1 Like

Only when the type information is available. If it isn’t, dispatch will happen during runtime.

I am not quite sure what the question is here. Multiple dispatch is part of the semantics of the language, and optimizing when possible it with AOT compilation is part of the implementation that, incidentally, is responsible for a lot of the speed advantage of Julia.

Arguing that a compiler optimization allowed by the design of the language is “fake news” is a somewhat heterodox approach to discussing programming languages & their implementations.

23 Likes

This is conditional compilation not multiple dispatch.

Here is a great illustration of an other aspect of multiple dispatch vs. function overloading (in addition to the good example of @Maurizio_Tomasi) .

3 Likes

No. With no type information parameters are boxed, and you get whatever happens in dynamic languages and not runtime dispatch in the “OOP” meaning.

My use of the term “fake news” was being facetious and slightly provocative. It’s wasn’t meant to be offensive - I :heart: Julia.

3 Likes

Please don’t be intentionally provocative in a text-only forum where no one can read your tone. It’s unhelpful and unproductive.

20 Likes

I am not sure that the C++ terminology is very useful for understanding Julia.

Sorry, but I still don’t understand what the question is. Multiple dispatch in Julia has well-defined semantics. When type information is available, the compiler can optimize a lot of things about it.

No worries, I didn’t find it offensive, just meaningless.

8 Likes

What I’m saying is that this is not multiple dispatch, it’s function overloading. All you are doing is limiting the types the function meet can call by forcing them to be in a specific type range. You can do that in C++ and D. The resolution itself occurs at compile time.

1 Like

I don’t know what to tell you here: Julia’s dispatch always behaves as if it were fully dynamic. That it is usually optimized and implemented much more efficiently doesn’t change that fact, since an optimization, by definition doesn’t change observable behavior (aside from speed).

I’m curious what context this allegation of “fake news” would have come up in? It seems easy to dispel: come up with a situation where you’d want dynamic dispatch and see if what Julia does is static or dynamic. (Spoiler: it will be the dynamic behavior.)

34 Likes

@dataSurfer, you can check for yourself, no need to rely on rumors:

julia> g(c) = f(@inbounds c[1])
g (generic function with 1 method)

julia> f(::Int) = 1
f (generic function with 1 method)

julia> f(::Bool) = 2
f (generic function with 2 methods)

julia> g(Any[3])
1

julia> g(Any[true])
2

julia> code_typed(g, (Vector{Any},))
1-element Array{Any,1}:
 CodeInfo(
1 ─ %1  = Base.arrayref(false, c, 1)::Any
│   %2  = (isa)(%1, Bool)::Bool
└──       goto #3 if not %2
2 ─       goto #6
3 ─ %5  = (isa)(%1, Int64)::Bool
└──       goto #5 if not %5
4 ─       goto #6
5 ─ %8  = Main.f(%1)::Int64
└──       goto #6
6 ┄ %10 = φ (#2 => 2, #4 => 1, #5 => %8)::Int64
└──       return %10
) => Int64

So, two of the calls are made at compile-time after checking to see if it’s a Bool or an Int. But then notice that third Main.f(%1) call, which is what gets used if the input is neither a Bool nor an Int. That’s the runtime-dispatch version, which you can see in greater detail with

julia> code_llvm(g, (Vector{Any},))

define i64 @julia_g_264(%jl_value_t* nonnull align 16 dereferenceable(40)) {
top:
  %1 = alloca %jl_value_t*
  %gcframe = alloca %jl_value_t*, i32 3, align 16
  %2 = bitcast %jl_value_t** %gcframe to i8*
  call void @llvm.memset.p0i8.i32(i8* align 16 %2, i8 0, i32 24, i1 false)
  %thread_ptr = call i8* asm "movq %fs:0, $0", "=r"()
  %ptls_i8 = getelementptr i8, i8* %thread_ptr, i64 -15720
  %ptls = bitcast i8* %ptls_i8 to %jl_value_t***
  %3 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 0
  %4 = bitcast %jl_value_t** %3 to i64*
  store i64 4, i64* %4
  %5 = getelementptr %jl_value_t**, %jl_value_t*** %ptls, i32 0
  %6 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 1
  %7 = bitcast %jl_value_t** %6 to %jl_value_t***
  %8 = load %jl_value_t**, %jl_value_t*** %5
  store %jl_value_t** %8, %jl_value_t*** %7
  %9 = bitcast %jl_value_t*** %5 to %jl_value_t***
  store %jl_value_t** %gcframe, %jl_value_t*** %9
  %10 = bitcast %jl_value_t* %0 to %jl_value_t***
  %11 = load %jl_value_t**, %jl_value_t*** %10, align 8
  %12 = load %jl_value_t*, %jl_value_t** %11, align 8
  %13 = icmp eq %jl_value_t* %12, null
  br i1 %13, label %fail, label %pass

L5:                                               ; preds = %pass
  %14 = icmp eq %jl_value_t* %28, inttoptr (i64 140386210668768 to %jl_value_t*)
  br i1 %14, label %L10, label %L8

L8:                                               ; preds = %L5
  %15 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 2
  store %jl_value_t* %12, %jl_value_t** %15
  %16 = getelementptr %jl_value_t*, %jl_value_t** %1, i32 0
  store %jl_value_t* %12, %jl_value_t** %16
  %17 = call nonnull %jl_value_t* @jl_apply_generic(%jl_value_t* inttoptr (i64 140386134835232 to %jl_value_t*), %jl_value_t** %1, i32 1)
  %18 = bitcast %jl_value_t* %17 to i64*
  %19 = load i64, i64* %18, align 8
  br label %L10

L10:                                              ; preds = %pass, %L8, %L5
  %value_phi = phi i64 [ %19, %L8 ], [ 2, %pass ], [ 1, %L5 ]
  %20 = getelementptr %jl_value_t*, %jl_value_t** %gcframe, i32 1
  %21 = load %jl_value_t*, %jl_value_t** %20
  %22 = getelementptr %jl_value_t**, %jl_value_t*** %ptls, i32 0
  %23 = bitcast %jl_value_t*** %22 to %jl_value_t**
  store %jl_value_t* %21, %jl_value_t** %23
  ret i64 %value_phi

fail:                                             ; preds = %top
  call void @jl_throw(%jl_value_t* inttoptr (i64 140386213625328 to %jl_value_t*))
  unreachable

pass:                                             ; preds = %top
  %24 = bitcast %jl_value_t* %12 to i64*
  %25 = getelementptr i64, i64* %24, i64 -1
  %26 = load i64, i64* %25
  %27 = and i64 %26, -16
  %28 = inttoptr i64 %27 to %jl_value_t*
  %29 = icmp eq %jl_value_t* %28, inttoptr (i64 140386211212192 to %jl_value_t*)
  br i1 %29, label %L10, label %L5
}

Since you seem to know something about C/C++, you can check the source of jl_apply_generic yourself.

If you add enough methods to f, then Julia gives up on trying to guess and recompiles g to only use runtime dispatch (when it can’t figure out what the element type will be in advance):

julia> f(::Float64) = 3
f (generic function with 3 methods)

julia> f(::String) = 4
f (generic function with 4 methods)

julia> code_typed(g, (Vector{Any},))
1-element Array{Any,1}:
 CodeInfo(
1 ─ %1 = Base.arrayref(false, c, 1)::Any
│   %2 = Main.f(%1)::Any
└──      return %2
) => Any

A key point with this last version is the following: suppose PkgA defines g and those 4 methods of f. It precompiles them and saves them to the *.ji file. Now PkgB uses PkgA and defines a 5th method of f. g will not be recompiled because the limit for trying to be clever has already been exceeded. Nevertheless g will accurately dispatch to the new f method when fed a container with appropriate elements.

Runtime dispatch, Q.E.D.

35 Likes

Fair enough, here is an example, I guess I’m eating my own words a bit here, but to be fair most of the time you call Julia in examples people think are “multiple dispatch” are just overloading, the example below qualifies as multiple dispatch. Such cases exist but are a tiny minority.

abstract type Animal end
struct Lizard <: Animal name :: String end
struct Rabbit <: Animal name :: String end

race(l::Lizard, r::Rabbit) = "$(l.name) wins in wall climbing."
race(r::Rabbit, l::Lizard) = "$(r.name) wins in a normal race."
race(a::T, b::T) where T <: Animal = "$(a.name) and $(b.name) run forever."

function meet(a::Animal, b::Animal) 
    println("$(a.name) meets $(b.name) and they race!")
    println("Outcome: $(race(a,b))")
end

function spawnAnimal()
  rn = rand()
  if(rn > 0.5)
    return Lizard("Bayi")
  end
  return Rabbit("Sally")
end

function randomAnimals()
  a::Animal = spawnAnimal()
  b::Animal = spawnAnimal()
  meet(a, b) 
end


import InteractiveUtils: @code_warntype;

@code_warntype randomAnimals()

Output:

Variables
  #self#::Core.Compiler.Const(randomAnimals, false)
  a::Union{Lizard, Rabbit}
  b::Union{Lizard, Rabbit}

Body::Nothing
1 ─ %1 = Main.spawnAnimal()::Union{Lizard, Rabbit}
│   %2 = Base.convert(Main.Animal, %1)::Union{Lizard, Rabbit}
│        (a = Core.typeassert(%2, Main.Animal))
│   %4 = Main.spawnAnimal()::Union{Lizard, Rabbit}
│   %5 = Base.convert(Main.Animal, %4)::Union{Lizard, Rabbit}
│        (b = Core.typeassert(%5, Main.Animal))
│   %7 = Main.meet(a, b)::Core.Compiler.Const(nothing, false)
└──      return %7

This is true dynamic behaviour because the compiler doesn’t know which method it has to dispatch until the function is called.

4 Likes

Here’s a way to look at this that might be helpful. In static languages, the language comes with a system for assigning types to all expressions and if a program doesn’t follow the rules that allow it to do that, it doesn’t type check. In dynamic languages, there’s no such rule: instead of expressions having types, values have types and they just flow through the program. This is why static type theory people will sometimes describe dynamic languages as “unityped” because by their notion of what a type is, all expressions in a dynamic language have the type Any. Of course, dynamic language people think this is dumb because to them that’s not what a type is—it’s a classification of a value, not an expression.

Dynamic dispatch in static object-oriented languages like C++ and D is about allowing a little bit of that dynamic “values not expressions” behavior in an otherwise static language: if A has subtypes B and C and you have code where the type of an expression is A then when the program is running, the value that actually appears there can be of type B or C (let’s assume that A is strictly abstract). Now let’s say you have a variable a which has static type A, and then you see a.m(). Which m method gets called? If the dispatch is dynamic, then the method choice will depend on the actual runtime type of a: B.m will be called if a is an instance of type B; C.m will be called if a is an instance of type C.

If later in the code you see f(a) then this is not a method call but a static function call (let’s ignore unified function call syntax for the sake of simplicity, the concept also applies to non-virtual methods, so the syntax is kind of beside the point). What this means is that it doesn’t matter what the actual type of a is—the function that will be called is determined based on the static type of a, which is just A. So the function signature that will be called will be f(a::A) even if there is a function signature f(b::B) and a is an instance of type B (and likewise for C, of course).

How does this play out in Julia? There simply is no concept of the “static type” of any variable or expression. Yes, you can write a::A in a method signature or function body but all that does is ensure that a is an instance of type A, either by dispatch or type assertion. The only type associated with a is still it’s actual runtime type. You can test this quite easily by mocking up the above situation:

abstract type A end
struct B <: A end
struct C <: A end

f(a::A) = "it's an A"
f(b::B) = "it's a B"
f(c::C) = "it's a C"

g(a::A) = f(a)

In action:

julia> g(B())
"it's a B"

julia> g(C())
"it's a C"

If Julia’s dispatch were actually static function overloading, then the method of f which is called from g would be determined based on the static type of a which would be A and both of these would return "it's an A", but that’s not what happens. Instead, the method is determined based on the actual type of a just as in dynamic single dispatch in class-based object-oriented languages.

Note that this difference is independent of when the compiler happens to be able to figure out what method needs to be called—it’s a visible behavioral difference. Static dispatch means that the method f(::A) must be called whereas dynamic dispatch means that the appropriate f(::B) or f(::C) method must be called. Julia takes a hard stand on this: there is not even a concept of “the static type” of anything in the language, nor is there any way to choose static dispatch when calling a function.

35 Likes

I am confused. Aren’t multiple dispatch and dynamic versus static execution orthogonal concepts?

1 Like

Yes, that’s a good example because the randomness means that the compiler can’t “see through” the call and statically figure out which method to call, which makes it indisputable that this is dynamic because the dispatch actually occurs at runtime.

But that’s actually not relevant to the question of whether the behavior is static overloading or dynamic dispatch. If this were static function overloading then the only correct behavior would be for the meet(a, b) call in randomAnimals to call the function body with signature meet(::Animal, ::Animal), which doesn’t exist, so this code would necessarily throw an error (or fail to type check) if the semantics were static overloading—that would be the only correct behavior.

8 Likes

Right: static versus dynamic dispatch semantics and whether the compiler can figure out which function definition to call at runtime are mostly unrelated except that static semantics make it trivial to statically decide which function definition to call. The fact that one can often statically determine which method will be called in dynamic dispatch doesn’t make it any less semantically dynamic. Modern compilers do this all the time, it’s called “devirtualization”. Julia is particularly good at it.

10 Likes