Dispatch on constrained value type parameters


#1

Hello,

I’m working with AbstractArrays, and I would like to execute a method foo that takes two AbstractArrays when the number of dimensions of the first arrays is twice that of the first’s. An error should be thrown otherwise.

The only way I could achieve this is with @eval but with a finite number of dimensions. A MWE follows.

const ndimmax = 10

for n in 1:ndimmax
    @eval foo(::AbstractArray{S, $(2n)}, ::AbstractArray{T, $n}) where {S, T} = println("do something...")
end

This does the job as long as the number of dimensions remains small:

julia> foo(rand(10, 10), rand(10))
do something...

However I was wondering if there is another way I could achieve this ? It wouldn’t make sense to use @generated functions since the value type parameters would be outside the quote…

Thanks!

V.


#2

Wouldn’t this require an esoteric language with dependent typing like idris


#3

Hi,

I wasn’t even aware there were languages that were doing this… Thanks for the tip!

This isn’t much of a limitation (in my case, the type parameter N refers to the dimension of a multi-index, which will not exceed 4), but I’ve been scratching my head on this and was wondering whether there already existed a way to do this in julia…


#4

No, this isn’t something you can easily express through dispatch. If all you want to do is throw am error if the condition is not met, I would suggest doing exactly that: check the condition at run time and throw an error if it fails.

If the runtime check is too expensive or if you really need to dispatch to some other method if your condition doesn’t hold, then it might be possible to express what you want with a combination of traits and @pure abuse, but I wouldn’t suggest going down that road unless it’s necessary.


#5

Just for fun, here’s a demonstration of how you might do this with traits. I had assumed that Base.@pure would be necessary, but it seems that it’s not (Julia 1.0 is much better at this sort of thing):

"""
Public-facing method, which checks our condition on N1 and N2 and 
then calls the _foo() method containing the actual implementation.
"""
function foo(x1::AbstractArray{T1, N1}, x2::AbstractArray{T2, N2}) where {T1, T2, N1, N2}
    _foo(is_ok(N1, N2), x1, x2)
end

"""
Returns Val{true}() if N1 == 2 * N2, Val{false}() otherwise.

This looks type-unstable, but Julia's constant propagation seems
to allow it to infer the result when N1 and N2 are constants
"""
is_ok(N1, N2) = Val(N1 == 2 * N2)

_foo(::Val{true}, x1, x2) = x1
_foo(::Val{false}, x1, x2) = error("x1 should have twice as many dimensions as x2")
julia> foo(zeros(2, 2), zeros(2))
2×2 Array{Float64,2}:
 0.0  0.0
 0.0  0.0

julia> foo(zeros(2, 2, 2), zeros(2))
ERROR: x1 should have twice as many dimensions as x2
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] _foo(::Val{false}, ::Array{Float64,3}, ::Array{Float64,1}) at ./REPL[4]:1
 [3] foo(::Array{Float64,3}, ::Array{Float64,1}) at ./REPL[1]:6
 [4] top-level scope at none:0

Through the magic of constant propagation, this is even type-stable:

julia> @code_warntype foo(zeros(2, 2), zeros(2))
Body::Array{Float64,2}
6 1 ─     return x1  

#6

That’s amazing.


#7

Why Val wrap everything?

function foo(x1::AbstractArray{T1, N1}, x2::AbstractArray{T2, N2}) where {T1, T2, N1, N2}
    _foo(is_ok(N1, N2), x1, x2)
end
is_ok(N1, N2) = N1 == 2 * N2
_foo(v, x1, x2) = v ? x1 :  error("x1 should have twice as many dimensions as x2")
julia> @code_warntype foo(zeros(2, 2), zeros(2))
Body::Array{Float64,2}
2 1 ─     return x1  

works just as well.


#8

Thanks for the input, along the line of @rdeits’s solution:

 @generated function bar(::AbstractArray{S, N}, ::AbstractArray{T, M}) where {S, N, T, M}
    if N == 2M
        :(println("do something..."))
    else
        :(error("ndims(x) != ndims(y)"))
    end
end

#9

Would this be just as efficient?

function foo(x1::AbstractArray{T1, N1}, x2::AbstractArray{T2, N2}) where {T1, T2, N1, N2}
    N1 == 2*N2 || error("x1 should have twice as many dimensions as x2")
    return x1
end

If so it seems simpler, avoiding intermediate _foo trait or using a generated function.


#10

Yeah, that’s what I was alluding to in my first post. It’s clear, efficient, and super simple. The trait stuff is only useful if you want to do something like dispatch to different methods based on some condition.


#11

So that calculation happens at compile time? How far can you go with calculated traits like that?


#12

There should be no theoretical limitation, but if you go overboard with doing calculations using types you pay in compilation time. It is best to benchmark particular cases.


#13

No traits, but I like @andyferris’s A practical introduction to metaprogramming in Julia, where he demonstrates (video) in the section “Multiple dispatch as a metaprogramming technique” that Julia’s type system is Turing complete.