Multiple dispatch doesn't find the correct method using `Type`

filchristou · June 5, 2024, 5:17pm

I am in a confusing situation where I cannot find out why a method is not found.
Since it’s hard to explain I will directly post the MWE.

using Test

abstract type RSAState end
abstract type RSAAction end
abstract type RSAPOMDP{S<:RSAState,A<:RSAAction} end

struct RSAPOMDPState1 <: RSAState end
struct RSAPOMDPAction1 <: RSAAction end
struct RSAPOMDP1{S,A} <: RSAPOMDP{S,A} end

getdatatype(u::UnionAll) = getdatatype(u.body)
getdatatype(u) = u

statetype1(t::UnionAll) = statetype1(getdatatype(t))
# what I would consider enough
statetype1(t::Type{T}) where {T<:RSAPOMDP} = t.parameters[1]

statetype2(t::UnionAll) = statetype2(getdatatype(t))
# what actually works
statetype2(t::Type{T}) where {S,A,T<:RSAPOMDP{S,A}} = t.parameters[1]

RSAPOMDP1_1_1_2 = RSAPOMDP1{RSAPOMDPState1}

@testset let 
	#fail but shouldn't
	@test_throws MethodError statetype1(RSAPOMDP1_1_1_2)

	# doesn't fail
	@test statetype2(RSAPOMDP1_1_1_2) === RSAPOMDPState1 
end

To me statetype2(t::Type{T}) is a verbose version of statetype1(t::Type{T}) , so it is unexpected why statetype2 only works.

Is this a bug or a design choice?
In case that’s desired, can somebody explain why ?

adienes · June 5, 2024, 5:27pm

do note that

julia> RSAPOMDP1{RSAPOMDPState1} <: RSAPOMDP
false

not sure if that answers your question

nsajko · June 5, 2024, 5:40pm

The first issue (your bug): unsupported manipulation with UnionAll:

This is not documented and I don’t think it’s correct. How did you come to this implementation? What’s the required behavior?

The second issue (arguably a Julia bug): inheriting from an abstract type doesn’t (currently) propagate parameter constraints. So this:

Should rather be:

struct RSAPOMDP1{S<:RSAState,A<:RSAAction} <: RSAPOMDP{S,A} end

That affects the dispatch for statetype1 etc.

Julia issue on Github:

github.com/JuliaLang/julia

The behavior of type parameter constraint inheritance is not documented

opened 10:11PM - 18 Feb 24 UTC

brainandforce

kind:breaking domain:types and dispatch kind:minor change

If you have an abstract type with a constrained type parameter, subtypes whose parameters inherit from the type's parameters do not inherit the constraints. ```julia abstract type AbstractFoo{T<:Real} end struct Foo{T} <: AbstractFoo{T} end ``` ```julia-repl julia> supertype(Foo) AbstractFoo{T} where T julia> supertype(Foo{<:Real}} AbstractFoo julia> Foo <: AbstractFoo # This one is very much unexpected! false julia> Foo{<:Real} <: AbstractFoo true ``` This is true even though you can't construct a type which violates the constraints on its parent's parameters: ```julia-repl julia> Foo{String} ERROR: TypeError: in AbstractFoo, in T, expected T<:Real, got Type{String} Stacktrace: [1] top-level scope @ REPL[5]:1 ``` This is a subtle point that is not included in the documentation on abstract parametric types, but has caused me some headaches when some subtype relations broke unexpectedly. The above examples were tested on Julia 1.10 (version info below) running on Arch Linux in WSL2, installed with the AUR provided `julia-bin` package that provides the official release: ```julia-repl julia> versioninfo() Julia Version 1.10.0 Commit 3120989f39b (2023-12-25 18:01 UTC) Build Info: Official https://julialang.org/ release Platform Info: OS: Linux (x86_64-linux-gnu) CPU: 20 × 13th Gen Intel(R) Core(TM) i5-13600K WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-15.0.7 (ORCJIT, goldmont) Threads: 1 on 20 virtual cores ```

filchristou · June 5, 2024, 6:13pm

I guess I could do

statetype(t::Type{T}) where {S,A,T<:RSAPOMDP{S,A}} = S
actiontype(t::Type{T}) where {S,A,T<:RSAPOMDP{S,A}} = A

but A is unused in the first and S in the second. That’s why I started using the internal parameters, which drove me to distinguish from UnionAll and Type.
Reflecting on that, I guess it’s better to use the code above.

Benny · June 5, 2024, 9:12pm

Removing the indirection and likely inlining, the code currently does statetype1(t::UnionAll) = statetype1(t.body). It’s useless to dispatch on the internal DataType in the .body of a UnionAll:

julia> Vector isa Type{T} where T<:Array
true

julia> Vector.body isa Type{T} where T<:Array
false

I’m pretty sure it’s not meant for general use, it’ll fail for things unlike other instances:

julia> Vector .|> (identity, typeof)
(Vector, UnionAll)

julia> (Vector.body) .|> (identity, typeof)
ERROR: UndefVarError: `T` not defined
Stacktrace:
 [1] broadcastable(::Type{Array{T, 1}})
   @ Base.Broadcast .\broadcast.jl:740

The one thing I do use .body for is printing out the omitted trailing <:Any parameters in UnionAlls.

As much as I believe in manually duplicating or narrowing the parameter constraints at every definition so you don’t have to jump through source code or use reflection at runtime to discover the practical constraints, this still gets me and I wish the constraints could be computed for the type definition and incorporated into iterated unions. You cannot make a type like RSAPOMDP1{RSAPOMDPState1, String}, so why does RSAPOMDP1{RSAPOMDPState1} make RSAPOMDP1{RSAPOMDPState1, <:Any} instead of RSAPOMDP1{RSAPOMDPState1, <:RSAAction}? Problem is you can inexplicably write constraints that aren’t strictly narrower, and currently each parametric type must be compared at runtime to every constraint along the supertype chain (see below for a simple example) rather than a precomputed constraint intersection because typeintersect is documented to not always reach it. If you can’t compute a strict intersection every time, then it’s not safe to automatically put in iterated unions.

julia> Int<:Integer<:Real<:Number
true

julia> abstract type AB{Integer<:T<:Number} end

julia> struct B{Int<:T<:Real} <: AB{T} end

julia> supertype(B) # you can arbitrarily replace where clause
AB{T} where Int64<:T<:Real

julia> typeintersect(AB, supertype(B)) # seemed to work this time
AB{T} where Integer<:T<:Real

julia> B{Number} # fails check at B
ERROR: TypeError: in B, in T, expected Int64<:T<:Real, got Type{Number}
...
julia> B{Int} # fails check at AB
ERROR: TypeError: in AB, in T, expected Integer<:T<:Number, got Type{Int64}

nsajko · June 6, 2024, 7:33am

filchristou:

I guess I could do
statetype(t::Type{T}) where {S,A,T<:RSAPOMDP{S,A}} = S
actiontype(t::Type{T}) where {S,A,T<:RSAPOMDP{S,A}} = A
but A is unused in the first and S in the second.

Does this help?

statetype(::Type{<:RSAPOMDP{S}}) where {S} = S
actiontype(::Type{<:RSAPOMDP{<:Any,A}}) where {A} = A

filchristou · June 6, 2024, 9:07am

Thanks everybody for the answers. I tried scaling back to my problem form the MWE and I am confused again… It looks like statetype2(t::Type{T}) is not always triggered, even with the explicit type constraint definitions.

I just added one parameter to the struct.
Now, statetype2, statetype3, and statetype4 don’t work, although they are rather complete signatures.
And statetype4, which is reduced, and statetype5 works

using Test

abstract type RSAAction end
abstract type RSAState end

abstract type RSAPOMDP{S<:RSAState,A<:RSAAction,R<:Function} end

struct RSAPOMDP1{S<:RSAState,A<:RSAAction,R<:Function} <: RSAPOMDP{S,A,R} end

struct RSAPOMDPState1 <: RSAState end
struct RSAPOMDPAction1 <: RSAAction end

RSAPOMDP1_1 = RSAPOMDP1{RSAPOMDPState1, RSAPOMDPAction1}

# fail
statetype2(t::Type{T}) where {S,A,R,T<:RSAPOMDP{S,A,R}} = S
statetype3(t::Type{T}) where {S<:RSAState,A<:RSAAction,R<:Function,T<:RSAPOMDP{S,A,R}} = S
statetype4(t::Type{T}) where {S,A,R<:Any,T<:RSAPOMDP{S,A,R}} = S
# work
statetype5(t::Type{T}) where {S,A,T<:RSAPOMDP{S,A}} = S
statetype6(t::Type{T}) where {S,A,T<:RSAPOMDP{S,A,<:Any}} = S


@testset let 
	#fail but shouldn't ?
	@test_throws MethodError statetype2(RSAPOMDP1_1)
	@test_throws MethodError statetype3(RSAPOMDP1_1)
	@test_throws MethodError statetype4(RSAPOMDP1_1)

	# works
	@test statetype5(RSAPOMDP1_1) === RSAPOMDPState1 
	@test statetype6(RSAPOMDP1_1) === RSAPOMDPState1 
end

I would never suppose that there is a difference in the signature between statetype4 and statetype6. Actually all of them look similar and it’s surprising to me that they behave differently. It’s quite confusing to keep the type system happy…

nsajko · June 6, 2024, 9:50am

filchristou:

# fail
statetype2(t::Type{T}) where {S,A,R,T<:RSAPOMDP{S,A,R}} = S
statetype3(t::Type{T}) where {S<:RSAState,A<:RSAAction,R<:Function,T<:RSAPOMDP{S,A,R}} = S
statetype4(t::Type{T}) where {S,A,R<:Any,T<:RSAPOMDP{S,A,R}} = S

How Julia behaves here makes perfect sense, actually:

In these examples the method bodies happen not to use R. Consider however, what should the examples behave like had R been used in one of the method bodies.

Obviously R isn’t defined when the example functions are called with RSAPOMDP1_1 as argument, and attempting to use an undefined/unbound value will throw.

However it’s always better to catch an error early than late; this is a rationale for the dispatch behavior you observe.

filchristou · June 7, 2024, 6:32am

For me, it should get assigned the most generic possible type, which is <:Function or Function.
This would perfectly make sense for this application.

To give you an idea why this is inconvenient, image I define

julia> RSAPOMDP1_ = RSAPOMDP1{RSAPOMDPState1}

julia> RSAPOMDP1_.body #keep in mind
RSAPOMDP1{RSAPOMDPState1, A<:RSAAction}

Then, none of statetype[1-6] will work and I will have to define

statetype7(t::Type{T}) where {S,T<:RSAPOMDP{S,<:Any,<:Any}} = S

So, in order for my code to be robust, for a struct of N parametric types, I have to define N signatures ?

Benny · June 7, 2024, 7:22am

<:Function isn’t a type, it’s a type parameter variable (TypeVar) with a supertype constraint that specifies the wider parametric type is a set of parametric types. Vector{<:Function} includes Vector{Function}, Vector{typeof(+)}, Vector{typeof(-)}, etc. Vector{<:Function} and Vector{Function} are not the same type, so a method for retrieving the type parameter should not give the same result, let alone allow the former to have a value for a method’s static parameter. Calls like eltype(Vector{<:Function}) doesn’t even dispatch to the method with the static parameter, a separate fallback eltype(::Type) method without a static parameter exists to return Any. Don’t put things in the method’s where clause if you can’t guarantee the input has a value for it.

nsajko · June 7, 2024, 7:45am

Why not just use my suggestion from before:

filchristou · June 7, 2024, 8:38am

right. that will do.