# Traits and \`where\` syntax

**URL:** <https://discourse.julialang.org/t/traits-and-where-syntax/988>\
**Category:** Internals & Design\
**Tags:** proposal, traits\
**Created:** [December 16, 2016, 7:31am UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988 "2016-12-16T07:31:01Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![andyferris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andyferris/32/235_2.png) [@andyferris](https://discourse.julialang.org/u/andyferris)\
**Post date:** [December 16, 2016, 7:31am UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/1 "2016-12-16T07:31:01Z")

</div>

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](https://github.com/andyferris/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

```julia
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

```julia
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?

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [December 16, 2016, 7:43am UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/2 "2016-12-16T07:43:42Z")

</div>

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

The other way around makes more sense to me:

```julia
linearindexing(A) where A <: AbstractArray

```

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

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [December 16, 2016, 10:20am UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/3 "2016-12-16T10:20:08Z")

</div>

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

```julia
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:

```julia
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):

```julia
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](https://github.com/JuliaLang/julia/pull/18457#issuecomment-262428920)). 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.)

---

<div class="post-metadata">

**Author:** ![andyferris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andyferris/32/235_2.png) [@andyferris](https://discourse.julialang.org/u/andyferris)\
**Post date:** [December 16, 2016, 11:10am UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/4 "2016-12-16T11:10:06Z")

</div>

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 `UpperBound`s, 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.

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [December 16, 2016, 1:00pm UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/5 "2016-12-16T13:00:02Z")

</div>

@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])

```

---

<div class="post-metadata">

**Author:** ![andyferris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andyferris/32/235_2.png) [@andyferris](https://discourse.julialang.org/u/andyferris)\
**Post date:** [December 16, 2016, 1:15pm UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/6 "2016-12-16T13:15:07Z")

</div>

@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

```julia
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

```julia
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!

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [December 16, 2016, 1:54pm UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/7 "2016-12-16T13:54:52Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [December 16, 2016, 2:18pm UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/8 "2016-12-16T14:18:44Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![andyferris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andyferris/32/235_2.png) [@andyferris](https://discourse.julialang.org/u/andyferris)\
**Post date:** [December 18, 2016, 11:36pm UTC](https://discourse.julialang.org/t/traits-and-where-syntax/988/9 "2016-12-18T23:36:49Z")

</div>

> [@mauro3](#):
>
> 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.

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}`.