Traits and `where` syntax

Internals & Design
,
1

From time to time I’ve been thinking about how traits might work in the future in Julia. At JuliaCon 2016 there was some discussion of syntax involving an extra set of ::, such as f(a::AbstractArray::Dense) instead of f(a::DenseArray). We played with this syntax in Traitor.jl but it was more of a toy model or demonstration - nonetheless I did implement (I think) a feasible multiple-argument, multiple-trait dispatch algorithm in a disgusting generated function.

I’d like to suggest an alternative formulation using the new where syntax, and ask if this is even theoretically feasible in the framework of UnionAll.

@Jeff.Bezanson has a branch (jb/subtype) which allows one to specify UnionAll types using syntax like Array{T} where T <: Real. The thing on the right of appears to be a predicate; an indicator function of which types of T are allowed, if you will.

Now we could imagine allowing arbitrary predicates on the RHS but while one can easily check if the predicate is true for a given concrete type, dispatch rules also require that we can calculate whether set of types (or UnionAll) is a superset of another (or ambiguous). So having Array{T,N} where f(N) for instance would be difficult to dispatch on since we cannot rank specificity compared to, e.g., Array{T,N} where g(N) for arbitrary f and g.

However, what if the predicate could be a function (or trait) which returns a type? So we could have

getindex(a::A, inds...) where A <: AbstractArray where linearindexing(A) <: LinearFast = ...

The method table for getindex would have to know about the trait linearindexing and compare (using the standard type tree) the specificity of this trait of all matching methods. If the trait doesn’t exist in another method definition, then Any is taken for that trait. A method would be selected from the possibly matching methods if and only if all the traits (in this picture I consider the type as simply one of the traits) are at least as specific as the others. Just like standard methods, there is the possibility for ambiguities.

This seemed to work quite well in Traitor.jl - I could have methods with arbitrary numbers of arguments and arbitrary numbers of traits each, and they would dispatch (or be ambiguous) as I predicted they should. (Note that having an unknown and arbitrary number of traits is currently much more difficult in Julia than the single-trait “Tim Holy Trait Trick”-type of thunk).

The question here is whether it would be feasible to add these here to the UnionAll types. We can make an trait-imbued UnionAll type with syntax like

A where A <: AbstractArray where linearindexing(A) <: LinearFast

A UnionAll could contain a list of trait keys and their associated upper bounds, one trait being the actual type. As far as I can tell, it would still be feasible to determine if B <: A by comparing all the traits that appear in A or B. Does this seem correct? Is there a counterexample?

3 Likes
2

x-ref: https://github.com/JuliaLang/julia/pull/18457#issuecomment-261755320

The other way around makes more sense to me:

linearindexing(A) where A <: AbstractArray

with linearindex returning a type which encodes which of the trait-categories of linearindex A belongs to.

3

Sorry, I got a bit confused. The code I wrote above defines a trait

LinearIndexing = linearindexing(A) where A <: AbstractArray  # (1)

using a UnionAll type. (NB this does not work on jb/subtype).

This could then be used like so:

LinearIndexing{Array} # == LinearFast
LinearIndexing{SparseMatrixCSC} # == LinearSlow

So this is a re-writing of the linearindexing(A) function to make it type-like.

Andy on the other hand proposed a way of using the trait in function dispatch (re-written using my definition (1) above):

getindex(a::A, inds...) where LinearIndexing{A} <: LinearFast = ...

So (1) is a map from the types to the trait-category (encoded with the types LinearSlow and LinearFast), whereas A where LinearIndexing{A} <: LinearFast is the identity map from the domain of all types which are part of the trait-category LinearFast to themselves (i.e. the set of all types belonging to LinearFast, which can then be used in function dispatch). I agree with Andy that this should in principle work and that the dispatch rules as they are now should work for this trait dispatch too.

Currently, this will not work on jb/subtypes as doing linearindexing(A) where A <: AbstractArray will apply linearindexing to the TypeVar A (which is a desired feature). For above to work the evaluation of linearindexing would have to be deferred until a concrete type is substituted for A. Maybe a special syntax is needed to indicate deferred evaluation? Say linearindexing<A> where A <: AbstractArray (to finally make use of the <> brackets.)

1 Like
4

Hmm… that seems to be a bit of a different approach to what I meant. I was trying for was a system to describe sets of (concrete) types with certain properties that make them useful to the Julia compiler.

What I mean is that if you have a pure function f_trait from (concrete) types to (possibly abstract) types, and the set of (concerte) types U such that f_trait(T) <: UpperBound, then I think these two properties hold:

  1. It is efficient to calculate if a concrete type T belongs to U. Simply evaluate f_trait(T) and ask if f_trait(T) <: UpperBound. Amongst other things, this lets you find all possible method signatures that match your (concrete) input to a function.

  2. For the same f_trait, it is efficient to calculate if U1 <: U2 by asking if UpperBound1 <: UpperBound2. This lets you find the most specific method signature to dispatch by. We might have zero, one or two of U1 <: U2 and U2 <: U1 because we can have zero, one or two of UpperBound1 <: UpperBound2 and UpperBound2 <: UpperBound1 (respectively: equality, one being more specific than the other, or ambiguity)

The beauty of the dispatch system (as I understand it) is that it relies these two steps alone, applied to the method’s signature as if it were at Tuple (which has special covariance rules to make this awesome). So the real thing want is something like UnionAll that lets you ask 1. and 2. of any (possibly abstract) type. The current type system is given by f = identity.

The final assertion, which I haven’t proved, is this:

3: If you take the intersection of the above sets of concrete types for multiple f_traits and associated UpperBounds, then you get a nice closed system of sets of concrete types, where 1. and 2. still hold. Here, taking the intersection of different traits (i.e. different f_trait, such as T where T <: AbstractArray where eltype(T) <: Number) are treated completely orthogonally, while taking the intersection of the same traits (e.g. T where T <: Real where T <: AbstractFloat) would behave exactly as UnionAll does currently.

Proving or disproving these 3 conjectures would be worthwhile; it would tell us whether this system of multiple-trait inheritance is feasible or infeasible.

1 Like
5

@andyferris What do you intend “something like UnionAll” to do? Why is it useful to the logic you are suggesting to know that some manner of coalescing multiple sets of traits has some trait present precisely n times and another only once?

set134 = Set([ 1, 3, 4 ])
set346 = Set([ 3, 4, 6 ])
UnionAll( set134, set346 ) == MultiSet([1, 3, 3, 4, 4, 6])
6

@jsarnoff the UnionAll type represents the union of many concrete types, I read the meaning of Array{T} where T <: Real as literally “the union of all concrete types Array{T} where T is a subtype of Real”. The UnionAll is a set.

However, the where operation is an intersection, not a union. We say

Set1 = Array{T} where T <: Any
Set2 = Set1{T} where T <: Real
Set3 = Set2{T} where T <: AbstractFloat

We then get this subset relationship: Set3 <: Set2 <: Set1

I’m suggesting that we allow things like

Set4 = Set3{T} where f(T) <: Integer

meaning we take an intersection of of the set of concrete types Array{T} that simultaneously satisfy T <: AbstractFloat and f(T) <: Integer.

I’m further raising the conjecture that the operations the Julia compiler needs to do on such sets to implement multiple-dispatch is efficient.

EDIT: As to the question of usage, once you have these traits, you will be able to dispatch on much more complicated sets of types. For an example from linear algebra, say matrix multiplication could dispatch on any M <: AbstractMatrix which has a layout(M) trait upper bounded Strided (which might have Dense as a subtype), and has an eltype(M) trait which is upper bounded by Union{Float64, Float32, Complex{Float64}, Complex{Float32}}, in which case we directly call the BLAS library. Otherwise, we fall back to a different method with the generic matrix multiplication algorithm implemented in Julia. Currently, there is a fair amount of logic that goes on to make this occur!

2 Likes
7

Yes, I just suggested to a way to write traits as UnionAll types (which went a bit off topic). Note though that this notation would be compatible with the dispatch things you are musing about.

8

Oh, good. That is what I thought you were saying, Andy.

9

Oh, I finally get what your syntax is doing! Cute.

So this works (in theory) if we define LinearIndexing (probably as a const or via a typealias, or maybe even with a new keyword), but if we make this a compulsory step, I feel it limits things in two ways:

  • I can’t just use eltype and other existing functions as traits - I have to first define the ElType trait “officially”.
  • I don’t see how this could be generalized to trait values. What I’m imagining is that isbits types and Symbol should be able to be trait values, just like they can slot into a TypeVar.

For an example of the second point, ndims could be a trait of an array - we could insert values using where syntax like Matrix = Array{T,N} where N === 2 (here === is the only predicate allowed, other than <:) or take this to a trait as AbstractMatrix = A where A <: AbstractArray where ndims(A) === 2, letting us remove N from AbstractArray entirely (I’m not advocating that we should remove N in this case).

The reason I bring this up is that in my projects I’ve found it to be very powerful to put less information in the type tree and more into trait functions, for instance in StaticArrays the size of the array is not in StaticArray{T,N} <: AbstractArray{T,N} but is defined via the Size trait. In this case, this turned out better than having StaticArray{T,N,Size}.

I’m not sure yet if the first point is a good thing or a bad thing. Without “officially declared traits” it, it might be hard to discover all the traits that might be used for dispatch, making ambiguity resolution even more tedious. In the worst case, someone could make an “anonymous trait” from an anonymous function, which would have it’s own type that no-one else could ever use, potentially even making it impossible to resolve a method ambiguity…

One way of resolving the second point would be to, e.g., have an NDims trait that returns Val{N}.