Type chains for multiple dispatch

Internals & Design
,
1

Dear fellow Julians,

I’m currently trying to design a package for computational differential geometry, and I’ve encountered a few places in my design where a certain enhancement of the dispatch semantics would be of great help for simplification and improving robustness.

Consider a parametric abstract base type like follows

abstract type AbstractLinearVector{N,T,S} <: FieldVector{N,T} end

where N is the size of the vector, T the element type and S an abstract type that indicates the space the vector lives in. The latter is only there for using it as a dispatch parameter. StaticArrays provides the FieldVector supertype.

A concrete vector type would be created from a parametric type that could for example be

struct  TangentVector3{T} <: AbstractLinearVector{3,T,AbstractTangentSpace}
   x::T; y::T; z::T 
end

The user of the package is supposed to define custom vectors like this for whatever space is introduced. However, there should be some common behaviour for all subtypes of AbstractLinearVector. For example, I wish to have a common set of promotion rules. The only way Julia offers this right now would be to manually define a promotion rule for each newly introduced vector. Clearly, this could be simplified using macros, but it would complicate the design and the usage of the package.

If one could however simply write something like

promote_rule( ::Type{U{T1}<:AbstractLinearVector{N,T1,S}}, ::Type{U(T2)<:AbstractLinearVector{N,T2,S}}  ) where {U,N,T1,T2,S} = U(promote_type(T1,T2))

with the intuitive meaning of dispatching on only subtypes of AbstractLinearVector if both arguments have the same subtype, but with a different single parameter and share common supertype parameters N and S. It would also allow the use of the subtype in the function definition and be compatible with @generated. Unlike constructs like U::Type{<:AbstractLinearVector{N,T1,S}, which would not reveal the parameter or the stripped type and be incompatible with @generated.

The idea could be extended to cover arbitrary subtype-chains and to work for non-type arguments. This can be useful for defining type-stable operators, for example.

I’m not familiar enough with the internals of multiple dispatch to be able to judge if something like this is feasible at all. In case I’m missing a powerful feature that makes this superfluous, I would love to learn about it.

Thanks,

Andreas

2 Likes
2

I think @otde is in a good position to chime in here as they very recently were faced with a similar situation.

The basic answer is to use less types, and distinguish between differently behaving but similarly laid out types through parameters.

That is, why do you need a bunch of different types like TangentVector3{T}? Can’t you just have LinearVector{N, T, S} by a struct and then define TangentVector3{T} = LinearVector{3, T, TangentSpace}?

I’ll lay out what I mean here:

First, instead of an abstract type AbstractLinearVector, we’ll make it a struct that holds an SVector:

using StaticArrays, Rematch

abstract type AbstractSpace end

abstract type   TangentSpace <: AbstractSpace end 
abstract type CoTangentSpace <: AbstractSpace end

struct LinearVector{N, T, S <: AbstractSpace} 
    data::SVector{N, T}
end

Next, we implement promotion:

Base.promote_rule(::Type{LinearVector{N, T1, S}}, ::Type{LinearVector{N, T2, S}}) where {N,T1,T2,S} = 
    LinearVector{N, promote_type(T1, T2), S}

and then indexing and addition:

Base.getindex(u::LinearVector, inds...) = getindex(u.data, inds...)

function Base.:(+)(u::LinearVector, v::LinearVector)
    promote_type(typeof(u), typeof(v))(u.data + v.data)
end

Notice that this defines addition to only happen between two LinearVectors of the same size N and belonging to the same vector space S, but it is agnostic about the element types of the two vectors.

Now, let’s define a convenient type alias say for 3d tangent and cotangent vectors as well as some constructors for them:

  TangentVector3{T} = LinearVector{3, T,   TangentSpace}
CoTangentVector3{T} = LinearVector{3, T, CoTangentSpace}

function TangentVector3(x, y, z)
    sv = SVector{3}(x, y, z)
    TangentVector3{eltype(sv)}(sv)
end
function CoTangentVector3(x, y, z)
    sv = SVector{3}(x, y, z)
    CoTangentVector3{eltype(sv)}(sv)
end

Now we can make some vectors and play around with them:

u, v =   TangentVector3(1, 2, 3),   TangentVector3(4, 5, 6)
l, m = CoTangentVector3(1, 2, 3), CoTangentVector3(4, 5, 6)

julia> u + v
LinearVector{3,Int64,TangentSpace}([5, 7, 9])

julia> l + m
LinearVector{3,Int64,CoTangentSpace}([5, 7, 9])

julia> u + m
ERROR: MethodError: no method matching +(::LinearVector{3,Int64,TangentSpace}, ::LinearVector{3,Int64,CoTangentSpace})
Closest candidates are:
  +(::Any, ::Any, ::Any, ::Any...) at operators.jl:529
  +(::LinearVector{N,T,S}, ::LinearVector{N,U,S}) where {N, T, U, S} at REPL[8]:2
Stacktrace:
 [1] top-level scope at REPL[17]:1

The error in the last line was because there is no sensible way to add a tangent vector a cotangent vector. Nice!

Finally, you might worry that you lost nice syntax like u.x to get the x component, but we can actually easily implement that as well

using Rematch

function Base.getproperty(u::LinearVector{3, T, S}, s::Symbol) where {T, S<:Union{TangentSpace, CoTangentSpace}}
    @match s begin
        :x => u[1]
        :y => u[2]
        :z => u[3]
        _  => getfield(u, s)
    end
end

julia> u.x
1

julia> l.z
3

I used Rematch here for the nice pattern matching syntax, but you can easily implement that as a conditional instead.

1 Like
3

Thank you for the very elaborate answer. You must understand that this is already the n-th iteration of trying to find a good design that is computationally efficient, easy to use and doesn’t require a lot of jumping through hoops.

I understand how your design works, but if the user would like to create a new vector and use the typical element nomenclature, like (dx,dy,dz) for a cotangent vector, then he’d have to write the Rematch code again.

The StaticArrays FieldVector more or less drove me to the design I have now, and I was just surprised that if I follow the natural way of one requirement, I have to break the elegance and simplicity of something else. I agree that composition over inheritance would be a good choice, but there should be enough flexibility in the language to make both work.

And more than a few times I’ve encountered the situation in which a construction like the one I have proposed here would have saved everything. So this post is more than just “how do I get my package working as intended?”, it’s about something that I would find tremendously useful and whose non-existence forces me to take exhausting and frustrating detours.

So thanks again for your solution. I will consider it, but I would be so much happier if the wonderfully intuitive type matching system would receive this, in my eyes also intuitive, semantic and syntactic extension.

Thanks,
Andreas

4

Hi Andreas.

One option here would be to do export @match inside your package, and then when you document what a user needs to do when defining new types, tell them that if they want special element nomenclature, they can write things like

function Base.getproperty(u::CoTangentVector3, s::Symbol)
    @match s begin
        :dx => u[1]
        :dy => u[2]
        :dz => u[3]
        _  => getfield(u, s)
    end
end

You could even provide a macro that would be used like

@components SomeType dx dy dz

and macroexpands to

function Base.getproperty(u::SomeType, s::Symbol)
    @match s begin
        :dx => u[1]
        :dy => u[2]
        :dz => u[3]
        _  => getfield(u, s)
    end
end

so that users don’t have to write it out themselves.

I think it’s fair to say that inheritance in julia is less simple and automatic than some users would like. In many of these cases, it’s because the julia developers identified a very subtle corner case to the behaviour that many of us think would be simple and intuitive that ends up being a bit of a show-stopper.

However, it seems your main gripe here revolves around a different issue than most inheritance issues, it’s really just about how to do nested dispatch on both a type and it’s parameter, i.e. I think if this worked, we could solve your original question pretty easily.

julia> f(::Type{U{T}}) where {U, T} = U{Int}
ERROR: TypeError: in Type{...} expression, expected UnionAll, got TypeVar
Stacktrace:
 [1] top-level scope at REPL[96]:1

Perhaps this is worth opening an issue on the julialang issue tracker, though I suspect it might be too hard to do nicely in the dispatch system due to how ambiguous it is.

2 Likes