Understanding dispatch through TypeVar

General Usage
, ,
1

I’m trying to understand how dispatch happens through TypeVars related to some debugging of Mooncake.jl internals. For example:

julia> foo(::Type{<:Array{T,N}}) where {T,N} = N
foo (generic function with 1 method)

julia> foo(Array{Float64,N}) where {N}
ERROR: UndefVarError: `N` not defined in static parameter matching
Suggestion: run Test.detect_unbound_args to detect method arguments that do not fully constrain a type parameter.
Stacktrace:
 [1] foo(::Type{Array{Float64, N}})
   @ Main ./REPL[1]:1
 [2] top-level scope
   @ REPL[2]:1

I’m confused why this matches the signature even though N is not concrete. The method does not have anything inherently wrong with it despite the error’s suggestion.

Another example:

julia> bar(::Type{<:Array{T,N}}) where {T,N} = T
bar (generic function with 1 method)

julia> bar(::Type{<:Array{T}}) where {T} = 1
bar (generic function with 2 methods)

julia> bar(Array{Float64,N}) where {N}
Float64

Shouldn’t it match the second method, not the first?

I also don’t fully understand where these types like (Array{Float64,N} where {N}).body appear in the wild. But Mooncake.jl is set up to handle them. So maybe there are certain cases of inference where these do appear?

2 Likes
2

I don’t know the answer here, however I’ll reference a relevant Github issue :wink:

Just to clarify one thing: whether the type parameter is concrete is certainly not relevant. Parameter matching succeeds when the lower bound on the parameter equals the upper bound on the parameter, which is not the case here where the default bounds (bottom and top types) obviously don’t equal each other.

Well, you could have used @isdefined N in the method body. Does that help?

First time I see this syntax! I wonder whether it is supported, or just an accidentally leaked implementation detail of the compiler frontend?

NB: you probably know this, but doing foo(Array{Float64}) seems to behave as you expect.

The second method is less specific due to subtyping:

julia> m1 = Tuple{Type{A} where {A <: Array{T, N}}} where {T, N}
Tuple{Type{A} where A<:Array{T, N}} where {T, N}

julia> m2 = Tuple{Type{A} where {A <: Array{T}}} where {T}
Tuple{Type{A} where A<:(Array{T})} where T

julia> m1 <: m2
true

julia> m2 <: m1
false
3

Thanks. Yeah my GH issue perhaps simplifies the weirdness a bit:

julia> foo(::T) where {T} = T;

julia> foo(::Type{T}) where {T} = Type{T};

julia> foo(Type{T} where {T})
Type{Type}

julia> foo(Type{T}) where {T}
ERROR: UndefVarError: `T` not defined in static parameter matching
#= ... =#

#= but, the following works fine =#

julia> bar(::T) where {T} = T;

julia> bar(Type{T}) where {T}
DataType

Ok. It kind of makes sense to me. So the method

julia> foo(::Type{T}) where {T} = T

matches (Type{T}) where {T} but not (Type{T} where {T}).

It just feels weird you can match on “parametric type that isn’t yet concretely defined” but not on a UnionAll - which, in my mind, looks like the same thing.

4

P.S., in case you have any insights, this came up in a discussion here: Failure of traversing through nested structures · Issue #661 · chalk-lab/Mooncake.jl · GitHub.

Basically, we were getting an “Unreachable reached” error, and @yebai found a fix to Mooncake.jl that literally just did

@generated function _build_fdata_cartesian(
    ::Type{P}, x::Tuple, fdata::Tuple{Vararg{Any,N}}, ::Val{nfield}, ::Val{names}
) where {P,N,nfield,names}
+   2*N
    quote
        processed_fdata = Base.Cartesian.@ntuple(

in the body, and it fixed things… (We haven’t found a MWE for Julia yet though)

5

Let’s look at what the call lowers to in v1.11.6:

julia> Meta.@lower foo(Array{Float64,N}) where {N}
:($(Expr(:thunk, CodeInfo(
    @ none within `top-level scope`
1 ─ %1 = Core.TypeVar(:N)
│        N = %1
│   %3 = N
│   %4 = foo
│   %5 = N
│   %6 = Core.apply_type(Array, Float64, %5)
│   %7 = (%4)(%6)
│   %8 = Core.UnionAll(%3, %7)
└──      return %8
))))

Cleaning that up a bit, it’s

let n = TypeVar(:N); UnionAll(n, foo(Core.apply_type(Array, Float64, n))) end

The overall expression is a UnionAll instantiation with a foo call in the leading section. Let’s look at its input:

julia> Core.apply_type(Array, Float64, TypeVar(:N))
Array{Float64, N}

julia> Core.apply_type(Array, Float64, TypeVar(:N)) |> typeof
DataType

julia> (Array{Float64, N} where N).body |> typeof
DataType

It looks like a UnionAll but it’s actually an internal component DataType. It dispatches to the method like any other DataType, though foo throws an error because TypeVar(:N) doesn’t provide an actual value required for the method parameter N used in the body (bar doesn’t use it in the body so it got a pass). The .body property tends to appear in internal type computation, like Base.unwrap_unionall. Presumably the real world version of foo alters the DataType component before instantiating the UnionAll.