What is the partial order used for multiple dispatch?

General Usage
,
1

In the docs, one can find that a paragraph on multiple dispatch but the dispatching algorithm is not described.

My question is: given two tuples args1, args2 of arguments (or types), what is the partial order < which is used to compare args1, args2 in order to select the “correct” function call (Jeff’s thesis?). I guess, when args1, args2 are uncomparable for <, the algo return a method ambiguity error.

This is a seemingly simple question but it never crossed my mind despite the fact that I use multiple dispatch seemingly ! Could the algo fail to find the “best” method? For example using (+(::Matrix, ::Matrix) instead of +(::Symmetric, ::Symmetric) (very bad example but you get the gist).

1 Like
2

I think the definitive documentation is the source code:

There is a more readable exposition here:
https://dl.acm.org/doi/10.1145/3276483

2 Likes
3

Overall, one should dispatch to the most specific method which matches the actual arguments.

If the actual arguments have type A (a Tuple of the individual argument types), and there are method signatures S and T which both match, i.e. A <: S and A <: T, then S is more specific if S <: T but not T <: S. (At least that’s what I like to think…)

So, the whole thing boils down to the subtype relation <: described in the link above.

4

A really good place to see this (at least to a first-order approximation) is simply methods! The method table is stored in sorted order. So Julia can just walk top-down, looking for the first method that matches (<:) the given args. This has gotten more complicated since I last looked — Julia needs to consider world ages, too — but it’s a good first step.

All cases that “fail” are ambiguity errors.

4 Likes
5

That’s gold remark!

6

Here’s a simple application of the rules. It can get quite complicated with parametric types and many arguments.

julia> f(a::Signed, b::Integer) = "si"  # Tuple{Signed, Integer}
julia> f(a::Integer, b::Signed) = "is"  # Tuple{Integer, Signed}
julia> f(a::Integer, b::Integer) = "ii" # Tuple{Integer, Integer}

argument type: Tuple{Int, UInt} matches the first and third
but the first (Tuple{Signed, Integer}) is a subtype of the third,
so the first is more specific:

julia> Tuple{Signed, Integer} <: Tuple{Integer, Integer}
true
julia> f(1, UInt(1))
"si"

argument type: Tuple{UInt, Int} matches the second and third.
The second is a subtype of the third, so the second is more specific:

julia> Tuple{Integer, Signed} <: Tuple{Integer, Integer}
true
julia> f(UInt(1), 1)
"is"

argument: Tuple{Int,Int} matches all the methods.
The two first are subtypes of the third, but none of them is a subtype of the other, so there’s not a unique most specific signature.
We get an error with a suggestion of a signature which would remove the ambiguity. That is, a new signature which is a subtype of both of them:

julia> Tuple{Signed, Integer} <: Tuple{Integer, Signed}
false
julia> Tuple{Integer, Signed} <: Tuple{Signed, Integer}
false
julia> f(1,1)
ERROR: MethodError: f(::Int64, ::Int64) is ambiguous.

Candidates:
  f(a::Integer, b::Signed)
    @ Main REPL[2]:1
  f(a::Signed, b::Integer)
    @ Main REPL[1]:1

Possible fix, define
  f(::Signed, ::Signed)

julia> typeintersect(Tuple{Integer, Signed}, Tuple{Signed, Integer})
Tuple{Signed, Signed}
1 Like