Multiple dispatch unexpected function call

[Wikunia]

I just encountered weird behavior with multiple dispatch which I didn’t expect.

julia> abstract type AbstractType end

julia> struct ExampleType<:AbstractType end

julia> struct Concrete{AT<:AbstractType} end

julia> is_same(c1::Concrete, c2::Concrete) = false
is_same (generic function with 1 method)

julia> is_same(c1::Concrete{T}, c2::Concrete{T}) where T = true
is_same (generic function with 2 methods)

julia> c1 = Concrete{ExampleType}()
Concrete{ExampleType}()

julia> c2 = Concrete{ExampleType}()
Concrete{ExampleType}()

julia> is_same(c1,c2)
false

I expected it to call the method with T as they both have the parametric type ExampleType.
Was able to “fix” it by specifying T <: AbstractType but it seems weird that Concrete itself is the same as Concrete{<:AbstractType} and then is more specialized than {T}.

Would understand an “ambiguous” error but maybe someone can point to an example where a change in behavior would result in another unexpected outcome.

Main questions:

1. What behavior did you expect?

• false
• true
• ambiguous

2. Is my understanding correct to why it returns false?
3. Is there a specific reason why my expected behavior would result in other problems?

cc @arsh

[goerch]

The type lattice seems to be consistent

@show Concrete{ExampleType} <: Concrete && Concrete <: (Concrete{T} where T) 
@show Concrete <: Concrete{ExampleType}
@show (Concrete{T} where T) <: Concrete
@show (Concrete{T} where T) <: Concrete{ExampleType}

showing

Concrete{ExampleType} <: Concrete && Concrete <: (Concrete{T} where T) = true
Concrete <: Concrete{ExampleType} = false
(Concrete{T} where T) <: Concrete = false
(Concrete{T} where T) <: Concrete{ExampleType} = false

[lmiq]

I think that there are two things going on. First, note that these two are the same method:

julia> f(c1::Concrete, c2::Concrete) = false
f (generic function with 1 method)

julia> f(c1::Concrete{<:T}, c2::Concrete{<:T}) where T<:AbstractType = true
f (generic function with 1 method)

Meaning both arguments can be concrete, but different, types.

And the <: in Concrete{<:T} makes an important difference, because this is another method:

julia> f(c1::Concrete{T}, c2::Concrete{T}) where T<:AbstractType = true
f (generic function with 2 methods)

which is less specific, I think because of the type of variance of the type system (the thing that makes Vector{Int} <: Vector{Real} == false).

I have the impression that what you have there is a mix of these things. And I agree it is confusing.

[goerch]

And this

@show Concrete <: (Concrete{T} where T<:AbstractType) && (Concrete{T} where T<:AbstractType) <: Concrete

yielding

Concrete <: (Concrete{T} where T <: AbstractType) && (Concrete{T} where T <: AbstractType) <: Concrete = true

seems to explain the dispatch you see.

[jakobnissen]

If I understand correctly, what happens is:

• Concrete is the same as Concrete{T} where {T <: AbstractType}, following the definition of Concrete, where the upper bound of the typevar is AbstractType
• Concrete{T} where T is the same as Concrete{<: Any}, by definition.
• Hence, the signature is_same(c1::Concrete, c2::Concrete) is more specific than is_same(c1::Concrete{T}, c2::Concrete{T}) where T, and the call dispatches to that.

This can be confirmed by looking at the method table of is_same, where the methods are displayed from more to less specific:

julia> methods(is_same)
# 2 methods for generic function "is_same":
[1] is_same(c1::Concrete, c2::Concrete) in Main at REPL[4]:1
[2] is_same(c1::Concrete{T}, c2::Concrete{T}) where T in Main at REPL[5]:1

Relevant issues:

• https://github.com/JuliaLang/julia/issues/37901
• https://github.com/JuliaLang/julia/issues/6383

[StefanKarpinski]

Another way to put this is that if you change this definition:

is_same(c1::Concrete{T}, c2::Concrete{T}) where T = true

to this:

is_same(c1::Concrete{T}, c2::Concrete{T}) where {T<:AbstractType} = true

then the example works the way you expect it to. The confusing thing, as @jakobnissen explained, is that even though Concrete requires T <: AbstractType, dispatch doesn’t know about that and considers the unbounded T in the signature to be broader than intuitively expected because you know that T <: AbstractType has to be true for any actual instance of Concrete but dispatch doesn’t know that.

[lmiq]

@jakobnissen

Concrete is the same as Concrete{T} where {T <: AbstractType} , following the definition of Concrete , where the upper bound of the typevar is AbstractType

The additional thing I find confusing here is that this above, specifically, does not seem to be true:

julia> is_same(c1::Concrete, c2::Concrete) = false
is_same (generic function with 1 method)

julia> is_same(c1::Concrete{T}, c2::Concrete{T}) where T<:AbstractType = true
is_same (generic function with 2 methods)

(two methods)

meaning Concrete is exactly identical to Concrete{<:T} where T<:AbstractType (with the <:).

Here it cannot make any difference, but if Concrete was a container where the field could be abstract, then that would be different.

[StefanKarpinski]

This is kind of the heart of the issue:

julia> Concrete == (Concrete{T} where {T<:AbstractType})
true

julia> Concrete == (Concrete{T} where T)
false

julia> Concrete <: (Concrete{T} where T)
true

So the type system considers Concrete to be a strict subtype of Concrete{T} where T, which is weird and confusing because there can’t actually be any instances of Concrete{T} where T that aren’t Concrete.

[Mason]

Here’s what I find surprising about this behaviour that I’m surprised hasn’t been focused on more: f(c1::Concrete{T}, c2::Concrete{T}) where T is applicable to only a diagonal subset of types.

E.g. if we have N possible type parameters, then

f(c1::Concrete, c2::Concrete)

could have N^2 possible specializations, whereas

f(c1::Concrete{T}, c2::Concrete{T}) where T

only has N possible specializations because it requires that the parameters match. To me, this means that this method is strictly more specific and hence should be prioritized by dispatch.

[goerch]

@Wikunia

julia> is_same(c1::Concrete, c2::Concrete) = false
is_same (generic function with 1 method)
julia> is_same(c1::Concrete{T}, c2::Concrete{T}) where T = true
is_same (generic function with 2 methods)

One more question: does anyone see a way to call the second method or isn’t this dead code?

[yha]

I also feel like this is the more surprising thing here.
Here is a simpler example of this surprise:

g(x::Number, y::Number) = "numbers"
g(x::T, y::T) where T = "T"

g(1, 1.0)   # == "numbers"
g("a", "b")  # == "T"
g("a", 1)  # MethodError
g(1, 2)  # == "numbers" (!)

Why is the last line not an ambiguity error?

[StevenWhitaker]

If I understand correctly what others have said, the logical flaw with this argument is that, although f(c1::Concrete, c2::Concrete) could have N^2 possible specializations, f(c1::Concrete{T}, c2::Concrete{T}) where T could have M (not N) possible specializations because

@StefanKarpinski

dispatch doesn’t know about that and considers the unbounded T in the signature to be broader

so the comparison isn’t quite so straightforward based on the number of possible specializations. One could argue that an ambiguity error makes sense in this case, though.

Note also that when we have f(c1::Concrete{T}, c2::Concrete{T}) where T <: AbstractType then your argument does hold.

[Wikunia]

Well Number is more special than T so I don’t think it’s confusing.

[yha]

A number is of course more special than T, but the set of values valid for (::Number, ::Number) is not more specific than the set for (::T, ::T) where T. For example, the first is applicable to (1,2.0), while the latter isn’t.
So this is an exception to the rule (if there is such a rule) that the most specific applicable method is invoked.

[Mason]

@StevenWhitaker

If I understand correctly what others have said, the logical flaw with this argument is that, although f(c1::Concrete, c2::Concrete) could have N^2 possible specializations, f(c1::Concrete{T}, c2::Concrete{T}) where T could have M (not N ) possible specializations because

Sure, I get why it’s happening this way, I just think that for the non-diagonal case it’s a non-issue. But for the diagonal case, I think this is really just bad behaviour because a strictly more specific method is being ignored in favour of a less specific method.

To me, this smells like a bug.

[goerch]

@Mason

Here’s what I find surprising about this behaviour that I’m surprised hasn’t been focused on more: f(c1::Concrete{T}, c2::Concrete{T}) where T is applicable to only a diagonal subset of types.

Correct. But given the type equality Concrete == (Concrete{T} where T <: AbstractType) you might have to compare

f(c1::Concrete{T}, c2::Concrete{U}) where {T <: AbstractType, U <: AbstractType }
f(c1::Concrete{T}, c2::Concrete{T}) where {T <: AbstractType}

or in other words, is f(c1::Concrete, c2::Concrete) referring to the first or second method?

[Mason]

Ohh, I understand now. I had forgotted by the time I got to the bottom of the thread that concrete’s type parameter was defined to be a subtype of AbstractType. I thought that AbstractType was just an arbitrary choice here.

I find this less disturbing now, given that this behaves as I’d expect:

julia> struct Concrete{AT} end

julia> is_same(c1::Concrete, c2::Concrete) = false
is_same (generic function with 1 method)

julia> is_same(c1::Concrete{T}, c2::Concrete{T}) where T = true
is_same (generic function with 2 methods)

julia> is_same(Concrete{Int}(), Concrete{Int}())
true

I guess it’s just a bit of a footgun that one needs to know what the contraints are on the original type paramters before writing the diagonal method if they want it to take it’s proper place in the precedence list, but not so bad as I thought it was.

[goerch]

@Mason

julia> is_same(Concrete{Int}(), Concrete{Int}())
true

But how do you manage to get this one given that Int is not a subtype of AbstractType? Ah, I see you dropped the type restriction on AT?

[goerch]

Now let use check the diagonalization argument

abstract type AbstractType end

struct ExampleType1<:AbstractType end
struct ExampleType2<:AbstractType end

struct Concrete{AT<:AbstractType} end

is_same(c1::Concrete{AT}, c2::Concrete{AT}) where {AT <: AbstractType} = true
is_same(c1::Concrete{AT1}, c2::Concrete{AT2}) where {AT1 <: AbstractType, AT2 <: AbstractType} = false

c1 = Concrete{ExampleType1}()
c2 = Concrete{ExampleType1}()
@show is_same(c1,c2)

c1 = Concrete{ExampleType1}()
c2 = Concrete{ExampleType2}()
@show is_same(c1,c2)

yielding

is_same(c1, c2) = true
is_same(c1, c2) = false

Looks good to me.

[goerch]

@goerch

f(c1::Concrete, c2::Concrete) referring to the first or second method?

Here is the MWE

abstract type AbstractType end

struct ExampleType1<:AbstractType end
struct ExampleType2<:AbstractType end

struct Concrete{AT<:AbstractType} end

is_same(c1::Concrete{AT}, c2::Concrete{AT}) where {AT <: AbstractType} = true
is_same(c1::Concrete{AT1}, c2::Concrete{AT2}) where {AT1 <: AbstractType, AT2 <: AbstractType} = false
is_same(c1::Concrete, c2::Concrete) = nothing

c1 = Concrete{ExampleType1}()
c2 = Concrete{ExampleType1}()
@show is_same(c1,c2)

c1 = Concrete{ExampleType1}()
c2 = Concrete{ExampleType2}()
@show is_same(c1,c2)

yielding

is_same(c1, c2) = true   
is_same(c1, c2) = nothing

Looks good to me, too.