Dispatch on arrays where all elements in the array have a certain trait

[DilumAluthge]

Cross-posted from mauro3/SimpleTraits.jl#63

This is a feature I'd eventually like to see supported in Julia. I'm not 100% sure where I should post it, so I figured it might be appropriate to post it here.

Given an array, I'd like to dispatch to one method if all elements in the array have the FooTrait, and to a different method if all elements in the array have the BarTrait. Is this something that could be implemented in a traits package? Or would it need to be implemented in the Julia language itself?

Minimum working example

abstract type MyTrait end
struct FooTrait <: MyTrait end
struct BarTrait <: MyTrait end

struct A end
struct B end
struct C end
struct D end

MyTrait(::Type{A}) = FooTrait()
MyTrait(::Type{B}) = FooTrait()
MyTrait(::Type{C}) = BarTrait()
MyTrait(::Type{D}) = BarTrait()

f(x::T) where T = _f(MyTrait(T), x)
_f(::FooTrait, x) = "foo"
_f(::BarTrait, x) = "bar"
_f(::FooTrait, x::AbstractArray) = "foo array"
_f(::BarTrait, x::AbstractArray) = "bar array"

f(A()) # "foo"
f(B()) # "foo"
f(C()) # "bar"
f(D()) # "bar"

MyTrait(::Type{<:AbstractArray{T, N}}) where T where N = MyTrait(T)

f([A(), A()]) # "foo array"
f([B(), B()]) # "foo array"
f([C(), C()]) # "bar array"
f([D(), D()]) # "bar array"

f([A(), B()]) # I want this to return "foo array", but instead it throws "ERROR: MethodError: no method matching MyTrait(::Type{Any})"

[andyferris]

Ok a few thoughts.

The functionality in this package can be reproduced in plain Julia if you plan it out in advance, using a trait pattern like you have demonstrated. The design goal here was to allow blind composition with unkown number/types of traits.

You can specialise your MyTrait pattern on Union to get the desired behavior.

Now... For cases like Array{Any} you may need to iterate the collection at run-time to determine the trait. I’m not sure what to make of that, especially the way behaviour like this can potentially depend on type “widening” choices made by typejoin (or worse, inference) for performance considerations.

Does that help at all?

Edit: sorry I fumbled the mouse and accidentally closed the issue.

[mauro3]

I don't think this will ever be possible in Julia as an array type is not designed to contain precise information on the type of each of its elements, if they are of different type. You need to use a tuple instead.

abstract type MyTrait end
struct FooTrait <: MyTrait end
struct BarTrait <: MyTrait end

struct A end
struct B end
struct C end
struct D end

MyTrait(::Type{A}) = FooTrait # note I now use FooTrait and not FooTrait() in order to be able to use Union below
MyTrait(::Type{B}) = FooTrait
MyTrait(::Type{C}) = BarTrait
MyTrait(::Type{D}) = BarTrait

f(x::T) where T = _f(MyTrait(T), x)
_f(::Type{FooTrait}, x) = "foo"
_f(::Type{BarTrait}, x) = "bar"
_f(::Type{FooTrait}, x::Tuple) = "foo tuple"
_f(::Type{BarTrait}, x::Tuple) = "bar tuple"
_f(::Type, x) = "unknown"

f(A()) # "foo"
f(B()) # "foo"
f(C()) # "bar"
f(D()) # "bar"

MyTrait(T::Type{<:Tuple}) = Union{MyTrait(T.parameters[1]), MyTrait(Tuple{T.parameters[2:end]...})}
MyTrait(T::Type{Tuple{TT}}) where TT =  Union{MyTrait(TT)}

f((A(), A())) # "foo tuple"
f((B(), B())) # "foo tuple"
f((C(), C())) # "bar tuple"
f((D(), D())) # "bar tuple"

f((A(), B())) # "foo tuple"
f((C(), D())) # "bar tuple"
f((A(), D())) # "unknown"

Edit: you probably need to add some @pure to get static dispatch.

[DilumAluthge]

Would I be correct in saying that this functionality is not possible using traits, but would be possible if Julia had abstract multiple inheritance a la JuliaLang/julia#5?

[mauro3]

I doubt it.

[DilumAluthge]

If we had abstract multiple inheritance as described in JuliaLang/julia#5, then presumably the following would work. Am I mistaken?

abstract type AbstractA end
abstract type AbstractB end
abstract type AbstractC end
abstract type AbstractD end

abstract type FooTrait end
abstract type BarTrait end

struct A <: AbstractA, FooTrait end
struct B <: AbstractB, FooTrait end
struct C <: AbstractC, BarTrait end
struct D <: AbstractD, BarTrait end

f(::FooTrait) = "foo"
f(::BarTrait) = "bar"
f(::AbstractArray{<:FooTrait}) = "foo array"
f(::AbstractArray{<:BarTrait}) = "bar array"

f(A()) # this would return "foo"
f(B()) # this would return "foo"
f(C()) # this would return "bar"
f(D()) # this would return "bar"

f([A(), A()]) # this would return "foo array"
f([B(), B()]) # this would return "foo array"
f([C(), C()]) # this would return "bar array"
f([D(), D()]) # this would return "bar array"

f([A(), B()]) # this would return "foo array"

[datnamer]

I wonder if @HarrisonGrodin 's https://github.com/HarrisonGrodin/radical-julia would have some ideas here.

[timholy]

Interesting example, first case I've seen where it could conceivably make a difference. The key is really whether typejoin can return something more meaningful than Any, and unless typejoin learns about traits then it is limited to types.

But fundamentally I think they're still quite similar, with traits having the advantage that they can be added retrospectively without changing the original source definition. It's just a question of how deeply things percolate. It could get pretty complicated; which of potentially-multiple shared properties should it return?

[DilumAluthge]

But fundamentally I think they're still quite similar, with traits having the advantage that they can be added retrospectively without changing the original source definition.

Yeah I think being able to add traits retrospectively is a huge advantage of traits.

The key is really whether typejoin can return something more meaningful than Any, and unless typejoin learns about traits then it is limited to types.

Maybe as part of the process for adding a trait FooTrait to a type A, we add new methods for typejoin?

[DilumAluthge]

I don't know anything about how typejoin is implemented. How difficult would it be to give typejoin information about traits?

[timholy]

Certainly possible in principle, the real question is whether you have to give something else up. It's possible to come up with a list of properties that you'd wish a system might have and then have some pesky mathematician 😄 prove that you can't have all of them simultaneously. Having things be finitely decidable and yet amazingly flexible sounds like it might risk entering into such territory.

[DilumAluthge]

Honestly, now that I think about it, I don't necessarily need typejoin to figure out the correct Array type. I just need to be able to convert an array Any[A(), B()] to an array FooTrait[A(), B()]. Then I would define f(::AbstractArray{<:FooTrait}) = "foo array" and would call it like this: f(FooTrait[A(), B()]). I'm fine doing the conversion manually as long as the method dispatch works.

[DilumAluthge]

It could get pretty complicated; which of potentially-multiple shared properties should it return?

We make the user pick, i.e. you manually have to write your arrays as FooTrait[A(), B()] instead of [A(), B()] or Any[A(), B()].

[mauro3]

... as long as the fast/static dispatch works.

There is one problem: if you have an array with a non-concrete eltype, then Julia cannot do static dispatch as it doesn't know the concrete type of each element. This limitation already exists with the current functionality and I don't think multiple-inheritance could help with this. To get around this, you need a container typed on each element, i.e. a tuple as described above (or some other tricks like https://github.com/JuliaDiffEq/RecursiveArrayTools.jl#arraypartition, which could probably also include trait-tricks).

Another option to get good performance, is to use an eltype which is a "small Union". However, then you should be able to hand-code a traits implementation again.

[DilumAluthge]

That's a good point. I've removed the "fast/static" part. I really just want dispatch to work.

[andyferris]

Then you can use a trait, which is determined at runtime by iterating the entire container (the compiler will optimize this away when it can infer the element type well enough).

(Multiple inheritence won't work for that).

[DilumAluthge]

Trait constructors take types as arguments, right? So if I only have the type, I'm not able to iterate over the container, since I don't have the actual container.

[DilumAluthge]

I suppose I could change the trait constructor to instances instead of types. But won't that then negatively impact my fast static dispatch in cases such as MyTrait(::Type{A}) = FooTrait()?

(I'm assuming thatMyTrait(::Type{A}) = FooTrait() is faster than MyTrait(x::A) = FooTrait(), since that's how I've always seen Holy traits used, but I could be wrong?

[andyferris]

Same speed, actually, assuming type inference succeeds. The instance version is strictly more powerful than the type version, and is the pattern I have been leaning towards lately. Not sure if Tim or others have an opinion on this?

[mauro3]

Not sure if Tim or others have an opinion on this?

From a purity-point-of-view I'd think traits should operate with types and not instances, as I view them as a way to group types into a set and not instances. But sure, it can at times be useful.

I remember some discussion on this related to interfacing with python where the instance would also have been needed (Steven J. was stating this) but could not find it.

[MasonProtter]

Getting the appropriate type info into the array signature for heterogeneous arrays is one problem. Syntax wise, I think probably the way we'd want to express this in Traitor.jl is something like

@traitor f(x::AbstractArray{T}) where {T::FooTrait} = ...

E.g. if the type info is present in T, dispatch on it through the whereparams. My next plan for #10 (or more likely, another PR) is to get where expressions working.

In general, I'd like

@traitor f(x::T) where {T::FooTrait} = ...

to be equivalent to

@traitor f(x::::FooTrait) = ...

while also supporting things like diagonal dispatch and whatnot.