Could type ambiguity based on `Union` of concrete types be eliminated?

MWE:

julia> foo(::Union{Int, Float64}, ::AbstractArray, ::AbstractArray) = 1
foo (generic function with 1 method)

julia> foo(::Int, ::Any, ::Any) = 2
foo (generic function with 2 methods)

julia> foo(1, [1], [1])
ERROR: MethodError: foo(::Int64, ::Vector{Int64}, ::Vector{Int64}) is ambiguous.

Candidates:
  foo(::Int64, ::Any, ::Any)
    @ Main REPL[2]:1
  foo(::Union{Float64, Int64}, ::AbstractArray, ::AbstractArray)
    @ Main REPL[1]:1

Possible fix, define
  foo(::Int64, ::AbstractArray, ::AbstractArray)

I would assume the first method of foo is equivalent to defining two methods:

foo(::Int, ::AbstractArray, ::AbstractArray) = 1

foo(::Float64, ::AbstractArray, ::AbstractArray) = 1

whose argument signatures are either subsets or disjoint sets of the respective signatures of foo(::Int, ::Any, ::Any). So, Could the current MethodError have been avoidable?

Specificity

Let’s define something like this:

"""
    strict_subtype(l::Type, r::Type)::Bool

Predicate, tell whether `l` is a strict subtype of `r`.
"""
strict_subtype(l::Type, r::Type) = (l <: r) && !(r <: l)

The rule with Julia’s method specificity is that strict_subtype(l, r) implies that l is more specific than r (with additional rules for breaking some ties that can arise). As briefly mentioned here:

There’s also a request for more docs on the specificity on the issue tracker:

Base.morespecific is a predicate useful for playing around with type/method specificity in the REPL:

Ambiguity

A MethodError pointing out the ambiguity gets thrown when there’s no most specific method for a call. This is useful to prevent programmer error, as it’s better to fail loudly than silently proceed in an unexpected manner.

It would be possible, in a future Julia release, to eliminate any specific MethodError that currently arises due to ambiguity by defining-out the ambiguity, giving some of the methods greater specificity. Indeed, @Lilith proposes to eliminate almost all MethodErrors that currently arise due to ambiguity:

That said, I think that introducing arbitrary rules just to make the specificity a total order (where any two elements are comparable) seems like a horrid idea. The ambiguities (from the programmers’ perspectives) wouldn’t actually be resolved, rather they would just be masked by defining them out. While it would make Julia a slightly more powerful language, because some programs that now throw MethodErrors would become valid; it could, I think, lead to frustrating debugging experiences due to unintuitive specificity rules, and to difficult-to-fix interface design issues all across the ecosystem. Defining-out an ambiguity “fixes” the issue from the language’s perspective, but it would still leave the issue where there’s, for example, two packages, and the authors of both packages expect their method to be more specific. That issue would just be hidden.

The specific example

Regarding your specific example, neither method is clearly more specific:

  • for the first argument position: Int is, as a strict subtype, more specific than Union{Int, Float64}
  • for the second or third argument position: AbstractArray is, as a strict subtype, more specific than Any

In the REPL:

julia> a1 = Union{Int, Float64}
Union{Float64, Int64}

julia> b1 = Int
Int64

julia> a2 = AbstractArray
AbstractArray

julia> b2 = Any
Any

julia> strict_subtype(b1, a1) && Base.morespecific(b1, a1)
true

julia> strict_subtype(a2, b2) && Base.morespecific(a2, b2)
true

So (potentially after some additional undocumented tie breaking gives up) the two signatures end up being incomparable, with neither of them the more specific one:

julia> a = Tuple{Union{Int, Float64}, AbstractArray, AbstractArray}
Tuple{Union{Float64, Int64}, AbstractArray, AbstractArray}

julia> b = Tuple{Int, Any, Any}
Tuple{Int64, Any, Any}

julia> Base.morespecific(a, b)
false

julia> Base.morespecific(b, a)
false
5 Likes

Hi Nsajko! Thanks for the patient and detailed reply, as always!

I understand that the behavior from my example is fully expected with respect to the current design of the multiple dispatch system. My focus is more on the inconvenience, specifically the code redundancy, caused by such a behavior. If I want to resolve the type ambiguity caused by the first argument, I need to split

foo(::Union{Int, Float64}, ::AbstractArray, ::AbstractArray) = code1

into

foo(::Int, ::AbstractArray, ::AbstractArray) = code1

foo(::Float64, ::AbstractArray, ::AbstractArray) = code1

where the only difference between the two methods is the argument signature. The body of the function (code1) is repeated twice.

Admittedly, I could write another core function without any constraint on the first argument

foo_core(a1::Any, a2::AbstractArray, a3::AbstractArray) = code1

to be called by those two methods:

foo(a1::Int, a2::AbstractArray, a3::AbstractArray) = foo_core(a1, a2, a3)

foo(a1::Float64, a2::AbstractArray, a3::AbstractArray) = foo_core(a1, a2, a3)

This could be a solution so far.

However, the fact that the user can resolve this type of ambiguity issue by simply doing a manual “union splitting” on the first argument of foo(::Union{Int, Float64}, ::AbstractArray, ::AbstractArray) made me realize the type ambiguity caused by Union (of concrete types) is not on the same level of difficulty as many other. Hence, the solution may also not be as drastic as the one @Lilith proposed.

Specifically, the subtle difference is that, unlike UnionAll or other abstract types (e.g., Real), a Union of concrete types only encloses a finite number of concrete types. In fact, Julia has already implemented union splitting to improve the type stability of function calls. I think a similar strategy can be applied here to eliminate such “type ambiguity.”

Maybe someone from the core development team could enlighten me on the feasibility of realizing union-splitting-based removal of type ambiguity. That would be much appreciated. Nevertheless, I understand that we are not in the 0.X era anymore, so this post is just to fuel my theoretical curiosity about the potential evolution of Julia’s multiple dispatch system. Thanks for reading!

2 Likes

This doesn’t really solve your concern regarding how union types should be dealt with from a type-specificty angle, but there are methods for solving your code-duplication problem. See this blog post from Oxinabox: Resident Eval, Top level metaprogramming patterns in JuliaLang. The first example is exactly your situation.

2 Likes

Thanks for the reference!