# Concrete vs parametric when determining type specificity

Consider these two methods:

``````foo(x::T, ::Vector) where T = "vector"
foo(x::T, ::AbstractVector{T}) where T = "abstract vector"
``````

Clearly, neither method signature is a subset of the other: `foo(1, [1.0])` matches only the first method, and `foo(1, 1:2)` matches only the second method. Nevertheless, Julia currently (v1.9.3) treats the first method as more specific than the second:

``````julia> foo(1, [1])
"vector"
``````

What’s the rule behind this decision? Given `Subtype{T} <: Supertype{T}`, does `Subtype` always beat `Supertype{T}`?

1 Like

It should be mentioned that the reason `foo(1, 1:2)` matches only the second method is precisely because `1:2 isa Vector` is false; so the first method is never even considered.

I’m not 100% sure, but I think this is due to diagonal types. Your first method is actually completely specified as

``````foo(x::T, ::Vector{S}) where {T,S} = "vector"
``````

Which is really talking about the type `Tuple{T, Vector{S}} where {T,S}` (tuple types are actually function signatures). Your other signature is `Tuple{T, AbstractVector{T}} where T`. Dispatch then asks the question which of these types is more specific:

``````julia> Base.morespecific(Tuple{T, Vector{S}} where {T,S}, Tuple{T, AbstractVector{T}} where T)
true
``````

The exact rule behind why is a bit complicated, but basically, once you fill in the concrete types from the dispatched values, you get this:

``````Tuple{Int, Vector{Int}}
Tuple{Int, AbstractVector{Int}}
``````

where the first is clearly more specific than the second, because `Vector` is more constraining than `AbstractVector` due to the subtyping relationship.

4 Likes

Comparing the types after the type parameters have been resolved is too late, though. Otherwise, these two methods would be the same, but they are not.

``````foo(::Int) = "a"
foo(::T) where T = "b"
``````
``````julia> foo(1)
"a"
``````
1 Like

I think the fact that

``````julia> typeof([1]) <: Vector <: AbstractVector{T} where T
true
``````

intuitively tells you `Vector` is more specific, thus the first method is used

2 Likes

There was an open access paper on Julia subtyping in 2018, I’ve still not read it, but it seems like it would be relevant for this question:

https://dl.acm.org/doi/pdf/10.1145/3276483

Sukera isn’t saying that call signatures fill in the type parameters of methods prior to dispatch, it’s just to illustrate that if you do, it’s easier to see why one method would be more specific.

I think this is tripping you up. This doesn’t imply that the methods lack a specificity order, and a specificity order doesn’t imply that there won’t be call signatures that only match 1 or the other. This is just one of the quirks of multiple dispatch + related parameters that do not occur under single dispatch, so it may seem relatively unusual (another example is method ambiguities, though that does occur in more languages due to method overloading). There is actually nothing unusual about your example, each call dispatches to the most specific and matching method; `foo(1, [1])` matches both methods, you can check with `invoke`:

``````julia> foo(1, [1])
"vector"

julia> invoke(foo, Tuple{T, AbstractVector{T}} where T, 1, [1])
"abstract vector"
``````
1 Like

This somewhat amounts to saying that for the purpose of determining specificity, each argument is considered independently. So in this example, the reasoning would be that the second argument considered independently is more specific for the `Vector` method than for the `AbstractVector` method, and the first argument is the same when considered independently so doesn’t change anything. I guess that would be not unreasonable…

I’m aware, but that paper is hard to stomach…

`foo(1, [1])` matching both methods is the point. My question is, why does Julia dispatch to the `Vector` method instead of giving me an ambiguity error.

1 Like

Because that method is more specific, as Sukera’s first reply demonstrated. The 2 methods are not ambiguous, `Base.isambiguous` is more definitive than `Base.morespecific`:

``````julia> m1, m2 = collect(methods(foo))
[1] foo(x::T, ::Vector) where T in Main at REPL[2]:1
[2] foo(x::T, ::AbstractVector{T}) where T in Main at REPL[3]:1

julia> Base.isambiguous(m1, m2)
false
``````

From my perspective the fact that an ambiguity error isn’t thrown should be classified as some sort of bug. Or there’s a documentation bug, because “exact rule behind why is a bit complicated” doesn’t cut it as an explanation for users.

1 Like

Why would you need to throw an ambiguity error, there isn’t an ambiguity.

How so? The only explanation so far was “it’s too complicated to explain”.

1 Like

That’s misleading, Sukera’s exact wording was “The exact rule behind why is a bit complicated, but basically…”. And yes, type theory is a dense subject and would be excessive, hence why Sukera used the call signature to follow up with:

The 1st is obviously more specific than the 2nd. It’s easy to extrapolate that to other call signatures that match both methods.

The only argument for ambiguity so far is that there are other call signatures that only match one or the other method; it’s not unusual to fall back to less specific methods, so the more interesting case is the call signature that only matches the more specific method (`foo(1, [1.0])`). But as explained already, that does not contradict one method being more specific than the other regardless of the call signature. The non-matching methods would just be excluded from the dispatch of those call signatures. Is it weird? Sure, like the rest of multiple dispatch. Is it a method ambiguity? Not at all.

1 Like

Well, yes, that’s the hand-waving part. As ettersi pointed out in their second comment, the “trick” of filling in the concrete types obviously doesn’t apply in general.

Which is why `Base.morespecific` and `Base.isambiguous` was brought up. But the hand-waving was enough to illustrate plainly why it’s reasonable that the example in the OP is not ambiguous. Type theory would not be as plain.

So applying that to the 2nd comment’s example:

``````julia> typeof(1) <: Int <: T where T
true

julia> T where T
Any
``````

Handwaving 2.0 works!

You’re free to read the source and find a better explanation https://github.com/JuliaLang/julia/blob/master/src/subtype.c#L4651-L4860

Well, yes - the methods are stored in the method table with their `Tuple{Int}` and `Tuple{T} where T` signatures. Dispatch tries to select the “most specific method” from that sorted table, but if it finds an exact match (i.e., the dispatched type is egal to the signature), of course that must be the most specific method (because signatures are unique per function - you can’t have two `foo(::Int)` methods on the same function) and it can stop looking. It’s really the parametric types that aren’t exactly matching at all times; the example with filled in types was only to illustrate why the tuple type with `Vector` is considered more specific than the one with `AbstractVector`. I didn’t mean to imply that “filling in the type parameters” is what’s actually going on.

Julia could certainly throw an ambiguity here, but then you’d get ambiguities all the time and you would have to concretely specify function signatures everywhere. Just `foo(::Real)` and `foo(::Integer)` would already be ambiguous on `Int` input, even though clearly `Integer` is more specific than `Real` (due to being a subtype of `Real`).

Yes of course the trick doesn’t work in general. That’s why I linked the more extensive docs on diagonal types above. Here it is again:

https://docs.julialang.org/en/v1/devdocs/types/#Diagonal-types

Note also that the second example by @ettersi is not the same case, because there are no parametric types there. That’s just regular subtyping determining specificity.

1 Like

Note that `(Tuple{T, Vector{S}} where {T,S}) <: (Tuple{T, AbstractVector{T}} where T)` is `false`.

There are two questions being asked here. What is subtyping and what is most specific.

I believe this paper only deals with the subtyping case.

I don’t think there is a precise notion of what is most specific has ever been formalized.

2 Likes

The reason that is false is diagonal typing, which is why Sukera brought it up. All it indicates is that some call signatures for the former do not match the latter, e.g. `foo(1, [1.0])`.

Again, that does not contradict a specificity order. jling’s `<:` comment was applied to individual arguments, not the full argument tuple types. For the 1st argument, `(T where T) <: (T where T)` (same type, so also vice versa), and for the 2nd argument, `Vector <: (AbstractVector{T} where T)` (not vice versa), so the 1st method is more specific. That logic is not any different from how we usually write more specific method signatures.

I’m not so sure your handwaving argument actually works

``````julia> Any <: T where T
true

julia> Base.morespecific(Tuple{Any, Any}, Tuple{T, T} where T)
false
``````

Yes that’s very typical of handwaving arguments, they’re not exact rules that work everywhere, and it’s not difficult to imagine examples outside their scope ad nauseum. They were more than adequate at illustrating the method specificity order in particular examples, as intended.