Julia: drop dispatch rule that all method type parameters must be captured

[marius311]

It may be obvious that methods will only dispatch if all type parameters are captured, but based on my readings through the docs this was not something that had stuck in my mind (in fact, searching back I can't really find any mention of it, I'm only deducing this from trying various test cases). Anyway, it led to a bit of a hang up which I think could be avoided for others by documenting this more explicitly. In case it's not clear what I mean,

f(::T...) where T = T
f() # gives MethodError

g(::Union{Symbol,T}) where T = T
g(:x) # also MethodError

My real issue that led me here was similar to first example, where I wasn't able to figure out why a call wasn't dispatching until I eventually realized there was some lone parameter that wasn't matched for my particular arguments (and it was less obvious that this simplified example).

[marius311]

Hmm... actually, I can make the latter case work like I originally envisaged it working by introducing a dummy type which doesn't match, e.g.

abstract type dummy end
g(::Union{Symbol,T,dummy}) where T = T
g(:x) # gives Symbol

Anyone understand what's going on?

[yuyichao]

Are you sure you didn't have another method defining already?

[marius311]

Ah sorry you're right, disregard that, I had some other definition floating around that caused that.

[JeffBezanson]

My and @vtjnash 's current thinking is that it would be simpler to drop the method-type-parameters-must-match rule, and make dispatch-equality the same as type-equality. The only reason for that extra rule was that you can access the values of parameters inside the method body, and if values for them can't be determined it's not so clear what to do. However, that should only affect uses of those variables and not dispatch itself. Best would probably be to give a specific kind of error when such a parameter is accessed. If you don't use the parameter names inside the method, everything is perfect. Or, you can write code like this:

function f(x::T...) where T
    if length(x) == 0
        return something
    else
        do something with T
    end
end

and that will also work.

[vtjnash]

I've tried to do some analysis of this. Modulo missing coverage of cases in my code, I think the following 10 methods are the full extent to which Base dispatch will get affected by this change:

_absspvec_hcat(X::AbstractSparseArray{Tv, Ti, 1}...) where {Tv, Ti} in Base.SparseArrays at sparse/sparsevector.jl:874
_absspvec_vcat(X::AbstractSparseArray{Tv, Ti, 1}...) where {Tv, Ti} in Base.SparseArrays at sparse/sparsevector.jl:914
_totuple(::Type{Tuple{Vararg{E, N} where N}}, itr, s) where E in Base at tuple.jl:235
byteenv(env::Union{AbstractArray{Pair{T, B} where B, 1}, Tuple{Vararg{Pair{T, B} where B, N} where N}}) where T<:AbstractString in Base at process.jl:211
cat(catdims, A::AbstractArray{T, N} where N...) where T in Base at abstractarray.jl:1362
cat(catdims, xs::Union{Array{T, 1}, Array{T, 2}, Base.LinAlg.AbstractTriangular{T, A} where A<:(Array{T, 2} where T), Hermitian{T, A} where A<:(Array{T, 2} where T), Symmetric{T, A} where A<:(Array{T, 2} where T)}...) where T in Base.SparseArrays at sparse/sparsevector.jl:1016
convert(::Type{Tuple{Vararg{T, N} where N}}, x::Tuple) where T in Base at essentials.jl:69
eltype(::Type{#s48} where #s48<:Tuple{Vararg{E, N} where N}) where E in Base at tuple.jl:67
promote_leaf_eltypes(x::Union{AbstractArray{T, N} where N, Tuple{Vararg{T, N} where N}}) where T<:(AbstractArray{T, N} where N where T<:Number) in Base.LinAlg at linalg/generic.jl:1290
promote_leaf_eltypes(x::Union{AbstractArray{T, N} where N, Tuple{Vararg{T, N} where N}}) where T<:Number in Base.LinAlg at linalg/generic.jl:1289

Although there's some type system bugs which may cause other errors:

julia> const VecTuple{T} = Tuple{VecElement{T}}
Tuple{VecElement{T}} where T

julia> convert(VecTuple, (1,))
ERROR: MethodError: First argument to `convert` must be a Type, got T
Stacktrace:
 [1] (::Type{VecElement{T}} where T)(::Int64) at ./sysimg.jl:49
 [2] convert(::Type{VecElement{T}}, ::Int64) at ./sysimg.jl:50
 [3] convert(::Type{Tuple{VecElement{T}} where T}, ::Tuple{Int64}) at ./essentials.jl:162

# (note that VecTuple == Tuple{VecElement{T} where T}, so if it gets defined and cached first, the above would have succeeded)

But that bug exists independent of the change proposed here however, so it's not in scope to detect these cases.

[JeffBezanson]

Fixed by #23117

[StefanKarpinski]

I think this is far easier for people to understand:

# JULIA 0.7-DEV

julia> f(::Number...) = "heterogenous"
f (generic function with 2 methods)

julia> f(::T...) where T<:Number = "homogenous"
f (generic function with 1 method)

julia> f()
"homogenous"

Than the old behavior:

# JULIA 0.6

julia> f(::Number...) = "heterogenous"
f (generic function with 2 methods)

julia> f(::T...) where T<:Number = "homogenous"
f (generic function with 1 method)

julia> f()
"heterogenous"

[tkoolen]

See the linked StaticArrays issue above, referring to
https://github.com/JuliaArrays/StaticArrays.jl/blob/7276787a0b147135b758dd836b5951236e30558d/src/mapreduce.jl#L7-L11

After this change, what is the right way to define a vararg method for which at least one of the arguments must be of a given type?

[marius311]

After this change, what is the right way to define a vararg method for which at least one of the arguments must be of a given type?

I'm curious about this too. I had been using the fact that all arguments must match as a "feature" and will need to do some rethinking in 0.7.

In fact, for this reason I would suggest the "news item" in NEWS.md for this change be moved to "breaking changes." Perhaps if there's a simple succinct response to the above question, it even makes sense to include it in the new item as a suggested workaround.

[tkoolen]

Hmm, since my last comment I've learned that the method used by StaticArrays is more fragile than I originally thought, already in 0.6:

f(x::Number...) = "base"
f(x::Union{T, Number}...) where {T<:Int} = "specialization"

causes the first f to be overwritten. I thought the dispatch rule in question made it so that the bottom f would be distinct from, and more specific than the top one if one of the arguments was an Int. That does seem like a bug: either the second method should not overwrite the first, or the dispatch rule in question should be removed, and the second option was chosen.

The reason this works at all in StaticArrays in 0.6 is that the equivalent of the first f above for map doesn't exist in Base. It's more like:

f(x...) = "base"
f(x::Union{T, Number}...) where {T<:Int} = "specialization"

Still, in 0.6, f(1.) returns "base", whereas after this change it returns "specialization", which will be problematic for the StaticArrays map method. So the question in my previous comment remains.

[JeffBezanson]

We can only express "at least one argument is a StaticArray" if the other argument types aren't supertypes of StaticArray.

We would need to add an "existential Vararg" type for this. That could be a neat feature; Tuple{Exists{T}} is like Tuple{Vararg{T}} except something matches if at least one of the trailing values is of type T instead of all. At first thought, that seems much easier to implement than either a general Not type, or full regular types (i.e. allowing Vararg to occur more than once).

[tkoolen]

That could be pretty neat indeed.

Not required for this particular case, and perhaps going off topic, but I do wonder if at some point the full generality of something like C++'s enable_if (but hopefully nicer to work with) will be necessary to avoid ambiguities.

[yuyichao]

IIUC C++'s metaprogramming (enable_if included) is Turing complete so probably not.....

[c42f]

Tuple{Exists{T}} is like Tuple{Vararg{T}} except something matches if at least one of the trailing values is of type T instead of all

This is interesting. In 0.6 we used the "feature" which was removed here to support dispatching to the StaticArrays implementation of map (as pointed out by @tkoolen) for expressions like

map(+, [1,2,3], SVector(1,2,3), [1,3,4], [1,2,3], [1,2,3])

I'm not sure whether this was actually a good idea, but it seemed to work! If there's no other way to do this now in 0.7, we'll have to fall back to writing out several of the possible combinations for low numbers of arguments, and falling back to generic map for larger numbers of arguments. Obviously if we start writing out the options the number of combinations quickly explodes. Particularly dealing with the resulting ambiguities forced me to write out all the permutation of Static and non-Static arrays which was untenable above perhaps three arguments.

[c42f]

Though I guess another option for the particular case of map might be to redesign Base to give a bit more control over the output container of map, in a similar way to the Broadcast.containertype() machinery which was quite easy to extend for StaticArrays.

[tkoolen]

https://github.com/JuliaLang/julia/pull/23939 has presented me with another case where I would kind of need something like Tuple{Exists{T}} to (re-)implement broadcast! for a custom type (see 0.6 code). Is adding such a feature on the horizon?