Method specificity is acyclic, isn't it?

New user here. (How new? Try… yesterday.) Someone recommended me this talk from JuliaCon 2019 by Bezanson and I was a little spooked by a point made at 22:58.

Here is his hypothetical type tree (with an extra complex type).

And here is a hypothetical set of method specializations, with direction of specificity between each specialization.

To summarize, in this scenario, there is a cycle in the graph of method specificity. Oops! That seems pretty bad and at first I was kind of shocked this could happen. However, I think the problem is starting from a false premise.

Yes, if you took every method of a generic function and you asked, for each pair, “if both of these methods were applicable, which would be more specific?” you could get such a cycle. However, if I understand correctly, the algorithm for method selection is, abstractly: find every applicable method, then sort by specificity, then select the most specific method. Since in Julia every value always has one concrete type, and there are no (instantiable) types which have more than one supertype, it is always possible to totally order the set of applicable methods for any given type.

To prove this to yourself, look at the example cycle. Even though the arrows are correct, there is no concrete type such that all of those methods will be applicable. It is impossible to trigger.

Why do the cycles exist in the first place? In the current type system the whole set of types makes a tree, right? The only applicable methods will be any method occupying a space on the path back to the root. Unions can create arbitrary links to any point between two strands; however, none of these paths can actually be “traveled”.

So there is no problem. Julia is even “less bad” than Bezanson suggests. Hopefully what I wrote makes sense and if this has already been explained before in a github issue or something someone please point me to it.

1 Like

The relation Union{Float64, AbstractComplex} -> AbstractFloat seems wrong to me. That is how I would break the cycle.

1 Like