RFC: Language Support for Traits — Yay or Nay?

Thank you, this is exactly the boat I was in until you elucidated it.

The idea presented here does feel a bit like playing with fire, so it’s definitely worth asking whether the benefits justify the danger.

Note, that a proper cost/benefit analysis cannot be made unless we have a good idea how well we can control the flames.

1 Like

I think correctly specifying via the types of functions in packages what capabilities (like generic indexing or 1-based indexing) are supported is that killer application. See also the discussion in the thread about 0-based indexing being a poison pill.

I find traits in Scala pretty useful.

I actually don’t think traits are the right solution for this one. I think this is better addressed by instead making it easier to use 1-based indices to access containers without 1-based indices, so that 1-based indexing can be considered “generic” again.

One idea is to make a 1-based index type, as illustrated by the OrdinalIndexing.jl package: e.g., v[1st], v[2nd], v[(1:5)th]. Such indices offer a 1-based indexing assurance.

Another idea is to make a 1-based indexing view, as @DNF ponders in this post: e.g. OneBasedView(v)[1:5]. This seems inconvenient, but to illustrate how it’s not so bad: you could write a function like this:

hermitian!(A) = let A = OneBasedView(A), (m, n) = size(A)
    m == n || error("Matrix must be square")
    @inbounds for i = 1:m, j = i:n
        A[i, j] = A[i, j] + A[j, i]'
        A[j, i] = A[i, j]'
    end
end

Notice that OneBasedView is called only once at the top, and the rest of the function accesses A through this view.

These possibilities are also pondered in this thread.

1 Like

@uniment, if your post is indirectly asking the question, “mind if I try adding better traits to Julia?” then by all means go for it! No one wants to hold back a trait-enthusiast, I was just explaining the challenges.

Just keep in mind that there are good reasons for being conservative when it comes to merging big PRs that might add features we’d later regret—with Julia in stable release mode, there is no going back once a release has been made. Demonstrating tangible benefit from your work as early as possible will help convince a lot of people that big PRs should be merged.

2 Likes

I wouldn’t call myself that. I’m just an engineer, and when people complain, my animal instinct is to seek a technical solution :sweat_smile: I’ll let others debate whether traits are important enough to justify language support (I’m currently undecided).

My intent here is to add some heat to anneal the problem, to test whether we’re stuck in a local optimum or if we’ve found the best solution. What I’ve seen suggested that we hadn’t. An idea came to mind that appears to address the pain points, so I wanted to test it through dialog rather than putting in tremendous effort implementing it only to discover it was a poor idea from the outset.

I appreciate that this approach is often preferable. However, for this idea, proper implementation as a package would take maybe ten times as much effort and yield an inferior and unpleasant result, so it’s a poor approach and winning the package popularity contest wouldn’t be a good litmus test. I’ll also take this opportunity to point out that approaches that are optimal for packages aren’t always optimal for language-level solutions. Brainstorm/debate/rubber duck debug seems more appropriate for now.

Speaking of which, through this rubber ducking I found something I legitimately dislike about this proposal. Take the idea of dispatching on a container’s element type:

foo(A::AbstractArray{E}) where {E<:ElType} = ...

Naturally we would wish to extend this idea, to be able to dispatch on the traits of the element type. But this proposal offers no such mechanism. :frowning:

Maybe :: could be used?

foo(A::AbstractArray{E::ETr} where {E<:ElType, ETr>:ElTraits} = ...

I can’t say I’m a fan of this syntax though.

Also, by this proposal we’d be able to express vararg traits like so:

bar(x::X::XTr...) = ...

but there’s currently no way to express this using Vararg or NTuple. It could be expressed as:

bar(x::Vararg{X::XTr})

Still, the syntax irks me. It doesn’t feel right.

What I think you’re looking for is the sort-of dual to Union - instead of being a subtype of one of its parameters, you’d want to require T to be a subtype of ALL of its parameters (I don’t recall the proper type theoretic name, so I’ll just call this Join for now - think of it as a non-eager typejoin, just aggregating types without collapsing to Any or some Union). That is, in your Platypus example you’d write it like

abstract type HasDuckBill end
abstract type LaysEggs end

abstract type Mammal end

struct Platypus <: Join{HasDuckBill, LaysEggs, Mammal} end
struct CanadianGoose <: Join{HasDuckBill, LaysEggs, Bird} end

foo(arr::AbstractArray{T}) where {T <: Join{HasDuckBill, LaysEggs}} = "Platypus or Goose"

This can of course lead to lots of ambiguity errors, e.g. if we just add the innocent looking

foo(arr::AbstractArray{T}) where {T <: Mammal} = "Not a bird!"

then

foo(Platypus[])

is ambiguous. This particular approach still has the disadvantage of not being able to easily add new traits to existing objects, since it keeps the type system of julia nominal (see the docs and wikipedia). This is in principle fixable - just don’t require Join to be declared a supertype, i.e. don’t make it a nominal part of the type system - but I haven’t thought about the consequences of that too deeply. It’s so far the best I’ve come up with to introduce traits & multiple abstract subtyping to julia though :person_shrugging: I quite like it, but solving the issues with it I haven’t found yet and actually implementing that is probably worth a master level thesis (who knows, maybe I’ll come back to this approach when I go for a masters…)

4 Likes

Are you thinking of

2 Likes

That looks about right, yes! Good to know that built-up intuition about where our type system has holes leads to existing theory :smiley: Now integrating that theory (and, if possible, in a backwards compatible way) is the hard part… I still like to think Join is a good name for this, since in principle Join{Int, Float16} <: typejoin(Int, Float16) should hold as well, I think.

I usually think of “join” as corresponding to union and “meet” as corresponding to intersection. Julia’s typejoin may be using “join” in some other sense I’m not familiar with.

Yes, that is the usual terminology and I agree that calling it Join is confusing in that sense - it wasn’t meant as a serious suggestion as a name either way, Meet is just as good (and delightfully concise) :slight_smile: The name is yak shaveable.

1 Like

I’ve been chewing on this for a minute and woke up this morning with this exact thought! Glad I’m not crazy :grin:

I think that this captures essence of what people sometimes clumsily complain about Julia’s type system – “I want to inherit from two types.”

You don’t need a separate construct for traits, I think. Just a smart way to pass on behavior from multiple supertypes.

1 Like

These are essentially like interfaces in Java. Our abstract types are essentially the same as Java interfaces.

In your case though, does order of the multiple subtyping matter?

I think you’re right. I’m trying to express a position in an object type hierarchy and the possession of a set of traits; the solution to my dissatisfaction is to find a more concise way to express this, and the most concise expression is as an intersection—a construct that Julia simply doesn’t have.

I think it could be backwards-compatible. Simply put, instead of x::X asserting typeof(x)<:X, and instead of having methods dispatch on typeof, imagine if we instead had x::X assert traitsof(x)<:X and methods dispatch on traitsof.

Maybe it could work like this:


Intersecting Types and Traits

First, introduce a new type. You called it Meet, but to keep the spirit of shaven yaks alive I’ll call it Intersection. In a tree-shaped type hierarchy, the notion of an intersection is useless; Intersection{Signed, Number} is Signed, and Intersection{String, Int} is Union{}. With such a type system, there’s simply no way that Intersection could be useful (hence we don’t have it). But let’s introduce it.

Next, introduce the notion of multiple hierarchies. Currently we have only one: the hierarchy of objects with a top of Any and a bottom of Union{}, and all types declared in all modules share this hierarchy. A trait such as Growable doesn’t belong on this hierarchy—growability isn’t a category of thing; it’s a property that belongs on its own plane of existence.

To express this, maybe we could have a “type module” to declare a completely separate hierarchy:

type module Growable
    struct Is end
    struct IsNot end
end
Growable.Is <: Growable.Any # true
Main.Any != Growable.Any # true
Intersection{Growable.Is, Growable.IsNot} # Growable.Union{}

With orthogonality assumed, the intersection of a type in the Growable hierarchy with a type in the object hierarchy will be irreducible—i.e., Intersection{AbstractString, Growable.Is} cannot be reduced to Union{}, but instead must remain Intersection{AbstractString, Growable.Is}. In fact, every trait should exist in its own hierarchy, ideally orthogonal to every other trait, so that intersections with multiple traits can be formed.

Let’s finalize the specification of Intersection. Like Union and Tuple, Intersection types are covariant in their parameters, so that if T1<:T2 and MyTrait.TA<:MyTrait.TB, then Intersection{T1, MyTrait.TA} <: Intersection{T2, MyTrait.TB}. Also, like Union, order doesn’t matter.

Next, imagine if we have these definitions:

traitsof(x) = Intersection{typeof(x), traits(typeof(x))}
traits(::Type{T}) where T = Any 

As before, traits could be a special function, in that it dispatches on its argument’s typeof instead of traitsof.

For a type that doesn’t have any traits, you can see how traitsof(x) reduces to typeof(x), and therefore x::X is backward-compatible. And if x now becomes traitful, but X is still just a supertype, x isa X remains true and x::X still asserts correctly.

Then, to add traits to a type, we can perform a trick similar to the OP:

add_traits(T, Tr) = let Trs = Intersection{traits(T), Tr}
    eval(:( traits(::Type{var"#T"}) where var"#T"<:$T = $Trs ))
end

I think we have all the pieces we need now. With this, function dispatch could work like this:

# function call
f(a, b, c, d)

# method signature
f(::Any, ::B, ::CTrait.Tr, ::Intersection{D, DTrait.Tr})

# this method is chosen if:
traitsof(a) <: Any        &&
traitsof(b) <: B          && 
traitsof(c) <: CTrait.Tr  &&
traitsof(d) <: Intersection{D, DTrait.Tr}

# (and, of course, if this is the most specific method 
#  that satisfies these constraints.)

Here’s a question: what should typeof(Growable.Is) be? Should Growable.Is isa Type? If so, then maybe we can make this shorter with ∩(A::Type, B::Type) = Intersection{A, B}.

Are there any concerns with this? Would it work? Did I miss something? Can I choose better function names?


Taking a stab at method ambiguities

One thing I’ve noticed about method ambiguities is that anecdotally it seems like they don’t need to exist. Namely, ambiguities are introduced and resolved, but if methods were written in a different order (i.e., starting with the method that solved the ambiguity) the ambiguity would never have existed.

Maybe we can leverage Julia’s dynamic nature—which gets in the way sometimes by forcing method definitions to be sprinkled around type declarations (and vice versa) because of the linear evaluation order—and put it to use here. Namely, every time a method is declared, we could check if it creates any ambiguities with existing methods and throw an error if it does. That would alleviate concerns over method ambiguities by making them strictly impossible to begin with.

Is it generally true that ambiguities can be avoided throughout the course of declaring a function’s methods by properly ordering evaluation? Or am I wrong—would throwing errors on ambiguous method declarations cause some valid method signatures to be unreachable?

1 Like

That’s the same thing. In julia (& with multiple dispatch) , while we declare subtype relations explicitly, in practice that is only really true if we can really use the subtype in every place where we’d expect (at most) the supertype. I.e., given a T <: S and a function foo(::S), the declared relationship T <: S doesn’t really matter if foo(::S) then doesn’t succeed (while it’s of course nice to declare your intent, right now there is no explicit layer in the compiler checking for that & warning you ahead of time, aside from JET.jl). You can say that the type S “possesses” the trait “Passable as the sole argument to foo” (which is really all that’s needed). In general, this definition of subtyping is called the Liskov Substitution Principle. From this, it follows naturally that declaring T <: Meet{S, R} means "T MUST be able to be used in any place that we’d expect either S or R (or get an ambiguity error, if e.g. both foo(::S) and foo(::R) but no foo(::T) exist).

Trivially, if we have T <: S then Meet{T, S} simplifies just to T for all S for which T <: S holds. Meet{Union{}, T} always simplifies to Union{}, because Union{} <: T is always true. Additionally, Union{Meet{}, T} becomes just T again. (Try and plug in various types of the chain Union{} <: Int <: Integer <: Any and see what you get - in your head with Meet and in the REPL with Union).

Julia does not have a tree shaped hierarchy - it’s a partially ordered lattice, with typejoin being the join operation and typeintersect being the meet operation. Thus, Any is the Top of that lattice (there are no “greater” elements in the partial order) and Union{} is the Bottom of that lattice (there are no “smaller” elements in the partial order).

That’s where the tricky cases come in - what about typejoin(Meet{}, Any)? Or typeintersect(Meet{}, Union{})? Should they return Any and Union{} respectively, delegating Meet to just an intermediary? I think so, but that’s part of what I haven’t worked out yet. Other parts are what should happen with typejoin(Meet{S, T}, Meet{T, R}) or typeintersect(Meet{S, T}, Meet{R, Q}) (I suspect it would be T and Union{} respectively - haven’t worked it out yet).

Similarly, since we can’t subtype concrete types, it doesn’t really make sense to form a Meet{Int, T} - that then ought to be disallowed as well, only allowing Meet to be used with abstract types in its parameters.

Having arrived at this, we can view Meet in a different light - allowing multiple abstract inheritance of julia behavior, because abstract types are already our interface definitions (possibly extended by concrete structs - concrete structs that directly subtype Any are a bit of a PITA, but luckily strengthening the guarantees of the direct super type is not a breaking change generally speaking).

This is not necessary and introduces unnecessary complexity in the type lattice. Again, there is no hierarchy - it’s a partially ordered lattice. What you’re proposing would mean having multiple type lattices (i.e. multiple type systems) in one language, effectively splitting the type system in two. Now you have a meta-problem - partially ordering those lattices and resolving conflicts & ambiguities between them.

Yes, but that would mean requiring julia to typecheck function signatures ahead of time for all possible calls, which is undesirable in a dynamic language (in fact, that’s how statically typed languages work - you get a compiletime error when there’s a call that is ambiguous, instead of a runtime ambiguity error. The method may have been added in a language with global eval, after all).

Definitely, but I think implementing a nice trait system first would be substantially easier. Rewriting Base to take advantage of it everywhere would definitely be breaking and would also be a lot harder. I’d save it for whenever there’s more resources and a desire for a 2.0 release.

I’d also like to mention my current favorite implementation of traits–WhereTraits.jl.

1 Like

Definitely, but I think implementing a nice trait system first would be substantially easier. Rewriting Base to take advantage of it everywhere would definitely be breaking and would also be a lot harder.

That, however, may be where the bar is now. (Not the breaking part—the art would be doing what can be done without being breaking—but in terms of “a lot of work”.) Now that we’re in the 1.x stable release series, there’s well-justified reluctance to substantial new features without there being a “consumer”: how else do you know whether you’ve gotten the design right, and that the change yields real benefits without causing problems elsewhere? Surely you’ve noticed this in the discussion of https://github.com/JuliaLang/julia/pull/24990? This is kind of a more refined version of Julia is not at that stage of development anymore–deep changes are now harder. That’s the price of Julia’s success!

2 Likes

I don’t understand WhereTraits.jl enough to know what’s going on here. Is this performance a fundamental architectural limitation, or is it just an artifact of its current state of implementation?

julia> using WhereTraits
       @traits f(a) where {isodd(a)} = (a+1)/2
       @traits f(a) where {!isodd(a)} = a/2

julia> @btime f(2)
       @btime f(3)
  25.911 ns (0 allocations: 0 bytes)
  25.402 ns (0 allocations: 0 bytes)
2.0

For comparison:

julia> g(a) = isodd(a) ? (a+1)/2 : a/2
       @btime g(2)
       @btime g(3)
  2.300 ns (0 allocations: 0 bytes)
  2.300 ns (0 allocations: 0 bytes)
2.0

I get the appeal of wanting to dispatch on arbitrary predicates, but I’m not yet sure if it’s worth it. Totally open to being talked into it though.

Hmm, at a glance that looks a bit similar to what refinement types would look like (something I think might be a nice fit with Julia).

Elaboration

Refinement types would allow for something like:

function somescore(val::Int) where {0 <= val <= 60 && iseven(val)}
  # stuff
end

function getval(list::Vector, index::Int) where {firstindex(list) <= index <= lastindex(list)}
  # stuff
end

What’s nice about a refinement type system is that it can be checked that a function will respect its contracts at compile time. I’d imagine that this functionality would go quite some way to helping ensure the correctness of programs too.

For further reading, I’d recommend giving https://arxiv.org/pdf/2010.07763.pdf a look.

Racket, Ruby, Scala, and Haskell have all had refinement types added on top, which gives me hope that this actually could be viable for Julia.

3 Likes

@schlichtanders would know best.

1 Like