RFC: Language Support for Traits — Yay or Nay?

Internals & Design Internals
, , , ,
1

A repeated gripe I see from the local gray-hairs about Julia’s type system pertains to the lack of language support for multiple inheritance through traits—to manage those pesky behaviors that fall outside the type hierarchy.

Five years ago, the attitude seemed to be pretty strongly that language-level traits were right around the bend:

To quote @tim.holy in the Holy Traits OP:

It’s a little ugly

There was a flurry of competing ideas, but since then it feels like it tapered off and Holy Traits were written into the language manual. What happened? Was it found that language-level traits support would cause too many method ambiguities? Was no agreeable approach found? Was it decided that macros in packages such as from SimpleTraits.jl or WhereTraits.jl are the best approach? Did fear over too much change set in from the Python 3 drama? Was it simply placed on the back burner as more pressing matters arose?

I have an idea.

A Simple(r) Language-Level Traits Idea

An idea that’s been rattling around my otherwise vacant mind has been that dispatch could occur simultaneously on type hierarchy and on traits, using patterns and concepts that are already familiar.

First, imagine if a traits function was defined:

traits(::Type{T}) where {T<:Any} = Union{}

such that calling traits(T) would return the traits that T implements (by default none).

Utilities like this might be helpful for associating and disassociating traits with a type:

add_traits(T::Type, Tr) = let Trs = Union{traits(T), Tr}
    eval(:(traits(::Type{var"#T"}) where {var"#T"<:$T} = $Trs))
end
subtract_traits(T::Type, Tr) = let Trs = Core.Compiler.typesubtract(traits(T), Tr, 0)
    eval(:(traits(::Type{var"#T"}) where {var"#T"<:$T} = $Trs))
end

Let’s consider how dispatch could be reworked for these traits.

Currently, dispatch resembles something like this:

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

# method signature
f(::Any, ::B, ::Any, ::D)

# this method is chosen if:
typeof(a) <: Any &&
typeof(b) <: B   && 
typeof(c) <: Any &&
typeof(d) <: D

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

Now, imagine if type-annotation were extended into type-trait-annotation with a syntax similar to Traitor.jl: x::X::XTr where x is the identifier, X is the type, and XTr the trait(s), allowing for both type and traits to be specified:

  • x without decoration has no type or trait annotation;
  • x::X has just type-annotation;
  • x::::XTr has just trait-annotation; and
  • x::X::XTr annotates both type and traits.

Then, dispatch could work like this:

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

# method signature
f(::Any, ::B, ::::CTr, ::D::DTr)

# this method is chosen if:
typeof(a) <: Any && traits(typeof(a)) >: Union{} &&
typeof(b) <: B   && traits(typeof(b)) >: Union{} &&
typeof(c) <: Any && traits(typeof(c)) >: CTr     &&
typeof(d) <: D   && traits(typeof(d)) >: DTr

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

Unlike Traitor.jl, if DTr is a set of traits Union{DTr1, DTr2}, then d’s traits must include both: increasing the size of the set DTr tightens the specification. So while the type annotation D gets more specific as you progress down a type hierarchy, the traits annotation DTr gets more specific as you go up.

For example, to express the idea “the platypus is a mammal with a duck bill”:

abstract type Mammal end

struct Platypus <: Mammal  legs; tail  end
struct HasDuckBill end
struct LaysEggs end
add_traits(Platypus, Union{HasDuckBill, LaysEggs})

show(io::IO, ::::HasDuckBill) = print(io, "Probably a duck type...")
show(io::IO, ::Mammal::HasDuckBill) = print(io, "Maybe a platypus?")
show(io::IO, ::Mammal::Union{HasDuckBill, LaysEggs}) = print(io, "Probably a platypus.")
show(io::IO, ::Platypus) = print(io, "Definitely a platypus!")

An example a little closer to something you might see:

foo(A::AbstractArray, args...) = ... # default for arrays
foo(A::AbstractArray::IndexCartesian, args...) = ... # trait specialization
foo(A::AbstractArray::IsStrided, args...) = ... # trait specialization
foo(A::AbstractArray::Union{IndexCartesian, IsStrided}, args...) = ... # deeper trait specialization
foo(v::AbstractMatrix::Union{IndexCartesian, IsStrided}, args...) = ... # deeper type specialization

Of course, traits should be overloadable with custom methods, which hopefully would satisfy @klacru. Wrapper types might find it useful to inherit traits from the type they wrap:

traits(::Type{T}) where {T<:Symmetric{A,B}} where {A,B} = traits(B)

Matching on multiple objects that share the same traits:

foo(x::::Tr, y::::Tr) where {Tr<:Union{}} = ...

For completeness, to illustrate the contrast between type and trait annotation specificity:

x::Any::Union{} # most-general (matches any object)
x::Union{}::Any # most-specific (matches no object)

I like that this seems to be backwards-compatible, retaining the type hierarchy which works smoothly most of the time, and only adding traits when they’re really needed—when some behaviors for a type are orthogonal to its type hierarchy. Most code would remain as-is.

Unfortunately, I think trying to mock this up with a macro would be pretty messy and a low-fidelity representation, so I might only try if there’s a very compelling reason.

Would it work? Does it need a more/less sophisticated trait inheritance mechanism? Does it open room for dispatch ambiguity that couldn’t be solved by the patterns in the manual? Would it be necessary to impose constraints on traits? Would it necessitate new design patterns? Does it make dispatch too complex and inefficient? Are there any glaring weaknesses? Are Holy Traits good enough? Should we be using macros? Please share your thoughts!

7 Likes
2

I find your proposal still too complicated. Instead of

struct HasDuckBill end
struct LaysEggs end
add_traits(Platypus, Union{HasDuckBill, LaysEggs})

Why not

@trait Platypus HasDuckBill, LaysEggs

And an important proviso is that you need not be the owner of Platypus to be allowed to do that (you should be allowed to do that in another package than the one defining Platypus).

Otherwise OK for the syntax how to use traits in method declarations.

3

If what you’re really asking about is “why isn’t this in the core language yet?”, I think the issues are that

  1. bare dispatch-leveraging (“Holy”) traits do work, and since we use them in a couple of places in Base’s own code they should be documented
  2. there are packages that implement nicer syntax
  3. there are some uncertainties about the impact widespread trait-usage would have in terms of ambiguities, which becomes more serious given that
  4. implementing a nice trait system and then making Julia exploit it would likely be a multi-month job, and
  5. if someone did that work, it’s possible it would be a breaking change and thus wouldn’t be merged unless we think that it + the sum of other Julia 2.x changes would be worth it.

All in all, no one has stepped forward to invest that kind of time.

IMO, a better approach would be to generate enough unity/enthusiasm in the package community that a core framework gets adopted by multiple packages and there are clear demonstrations of the benefits. Then eventually that core framework might just move into Julia. But part of the point is that it doesn’t have to move into the language to become ubiquitous: packages are nearly on the same footing as Base, especially now that we can cache native code. So my recommendation is that if someone wants to make this happen, the best place is to start with the package ecosystem. ArrayInterface is perhaps a poster-child for such efforts, but it doesn’t focus on syntax as much as what traits we actually want to have (which I think is a good thing).

24 Likes
4

would a trait be able to tackle https://github.com/JuliaLang/julia/issues/37790?

5

Is it really possible to have a package implement the above proposal? That is, can a package implement a system where you can add a trait to a type you don’t own? Or is some modification of the compiler needed?

1 Like
6

I think, this proposal would fit well into #37790 as an additional implementation variant.
The discussions there, which were never concluded, would also apply to here.
Specially there is no solution for the proliferation of dispatch ambiguity.
The predicate “if this is the most specific method” seems to indicate this.

IMO the proposal to invert the meaning of Union when applied to traits is not acceptable (actually an intersection is meant).

The idea of adding and removing traits to types dynamically I have doubts, how that goes with type inference.

7

Technically yes, but only if the package is already written with such a trait extension & associated trait dispatch in mind. I.e. if the package already has a Holy Trait dispatch machinery for its own internal traits, a third party can “just” hook into that. You obviously can’t add such a dispatch layer if it’s not already there.

2 Likes
8

Would it be correct to say that in other languages like rust, traits govern which function you can call given some arguments, while in Julia people want a trait system that governs which method you should call given some arguments. The problems with the latter have been mentioned before, because one type can have arbitrarily many traits you have ambiguity problems very quickly.

So I don’t see trait dispatch as the main thing, rather traits can be used inside functions to direct the flow of the program given what the arguments support. We have that already with Holy traits. The other thing would be some syntax sugar to ensure that certain methods can only be called with arguments fulfilling the listed traits. But that would and could not contribute to dispatch logic.

4 Likes
9

Sure:

growable(::String) = DoesNotGrow()

is an example. ArrayInterface does this a lot.

1 Like
10

The problem with Holy Traits remains that you can only use them if the function owner opted into supporting traits. E.g. if I define a trait MyTrait, there is no way I can define Base.show(::IO, ::::::MyTrait) without type piracy.

This makes Holy Traits significantly less useful than something build directly into the dispatch machinery, and it’s a primary reason we haven’t seen all that much trait usage in the package ecosystem compared to regular dispatch.

4 Likes
11

EDIT: No, @mason is correct, this does require piracy. (I knew he was correct, just didn’t see how!)

I thought type piracy is extending a function you don’t own with types you don’t own. So Base.show(::IO, ::::::MyTrait) should be OK.

2 Likes
12

It’s something we want to be okay, but is not okay with Holy traits unless someone modifies Base.

The reason is that with Holy Traits id have to write something like

Base.show(io::IO, x) = Base.show(io, has_my_trait(x), x) # <—— Piracy

In order to do the dispatch step I want which is

Base.show(io::IO, ::MyTrait, x) = …

That is: with Holy Traits, in order to dispatch on the trait you first need to add an intermediate step that involves adding methods with types you don’t own. Therefore, you must own the function to enable trait dispatch.

5 Likes
13

I take your point. Do you take mine? If you were to go about being the brave soul who does the steps in RFC: Language Support for Traits — Yay or Nay? - #3 by tim.holy, how would you do it? First, you’d create a package called BaseRewrite that overwrites lots of methods in Base to make them traitful. Then you’d create branches of a bunch of packages to depend on BaseRewrite and demonstrate that voila, the world is suddenly full of unicorns.

The main point is that development in Base itself is hard: it’s much easier to prototype in a package and then move it into Base. I haven’t followed this area carefully since the early days of my proposal, but I’m not aware that anyone has written BaseRewrite and shown how much better life gets.

5 Likes
14

I’ve yet to see a proposal for formalizing traits that saves more than three lines of code with reasonable logic.

2 Likes
15

It’s my impression that traits are a handy feature which Julia is nonetheless unfortunately not super well-equipped to support

16

I’ve looked at rust traits a lot lately and tbh I was surprised by how little there was there despite all the talk The best thing I saw was “derive” for traits but that has some serious limits depending on the kind of trait being implemented.

My point isn’t to put down any effort, but point out that there has to be something more than some nice shorthand that is solved. I’m not convinced that overcoming some inconvenience in dispatch patterns or inheritance is ever going to be sufficient incentive. If you could somehow overcome type instabilities, invalidations, or some other existing issue then you’d be on to something

3 Likes
17

Oops, for some reason I deleted this from my OP: I think also traits might have to be a special function, in that traits is not called to dispatch on the traits of its argument (to avoid stackoverflow).

It could be similar to that, or new keywords could be reserved; I just wanted to express the idea in terms of existing Julia as much as possible for clarity.

To make this idea “work” as a package—that is to say, to hack the idea so that on a surface syntax level it works with the current dispatch system—I’d make a macro which would wrap function arguments such that whenever calling a function,

f(a, b, c, d)
# is transformed to
f(TTr(a), TTr(b), TTr(c), TTr(d))

where TTr is defined as:

struct TTr{X, XTr}  
    x::X
    TTr(x::X) where X = new{X, traits(X)}(x)  
end

Then, method signatures would be transformed like this:

f(a, b::B, c::::CTr, d::D::DTr) = ...
# is transformed to
f(a::TTr{<:Any, >:Union{}}, b::TTr{<:B, >:Union{}}, c::TTr{<:Any, >:CTr}, d::TTr{<:D, >:DTr}) = ...

It should work quite handsomely with methods defined and called like this.

However, you’re confronted with the fact that this would only work for functions that have already been declared this way; nothing in Base and no other package would be compatible with this function call, so you’d have to know at the callsite not to use this macro on those. It would be an un-composable package, an island of its own. Unless…

Yikes!

I believe this proposal, implemented in the compiler, isn’t breaking (at least if we consider it okay to break code which uses the pattern var::Type1::Type2, which I’d argue is already broken). Code that already implements Holy traits would still work; it just wouldn’t be necessary to do it that way anymore. And code that doesn’t use any traits would work as-is.

Implementing it as a package, however, would require breaking literally everything and a herculean effort to make it work again.

Yes, this is the sort of insight I’m hoping to gain here. What are the most onerous and insidious possibilities you can imagine this proposal would open? Would they be infeasible to address through proper patterns and use of Test.detect_ambiguities? Would we need new tools to understand the interactions? Would such problems be solvable, or would it be a Pandora’s box?

Possibly, but I feel like that problem is better solved by adding better support for wrapper structs. My ideas on that topic aren’t mature enough to be worth sharing though.

This is exactly what inverting the meaning does: when you query whether an object implements a set of traits, increasing the size of the query set decreases the size of the set of objects that match the criterion, since the latter set is an intersection. An object that implements a very large set of traits is a special object, as the set of such objects is very small.

Being able to dispatch on both type hierarchy and traits allows for further intersection.

This is an excellent example of how this proposal would allow greater extensibility. This is probably also the best example of why this idea could open up unexpected dispatch ambiguities, because every object must show :sweat_smile: If this problem is resolvable, then perhaps any such problem would be.

For example, suppose I define MyTrait2 and show(::IO, ::::MyTrait2), and I have an object ::Foo for which traits(Foo) >: Union{MyTrait, MyTrait2}. This creates an ambiguity for ::Foo’s show method, unless we either define show(::IO, ::::Union{MyTrait, MyTrait2}), or we define show(::IO, ::Foo).

Is it possible to develop a set of rules—language features, design patterns, best practices, etc.—by which such an ambiguity could readily either a) be anticipated and avoided, or b) be detected and resolved? Perhaps we’d want some friction in the process of adding traits to a type, because adding a new trait can suddenly introduce dispatch ambiguities? Or maybe we’d want type hierarchy visualization tools? Or maybe we’d want language features to enforce orthogonality of traits? What would trait orthogonality even mean? I’m spitballing here and wide open to ideas.

It seems like maybe traits should continue to be considered an “advanced” feature, a tool with sharp edges that neophytes would be discouraged from using unless there are ways to put safeties in place. I suspect that the extra :: should also add friction to cause a preference toward dispatching on the type hierarchy instead of traits, but maybe I’m wrong.

As @Mason points out, this isn’t just about saving three lines of code. Functions that don’t already dispatch on traits, cannot be extended to. And functions that do, can’t be extended to specialize on new trait categories (groupings of traits that are returned by a GetThisTrait function). By contrast, this proposal makes such trait categories unnecessary.

That curse is also a blessing: it forces trait dispatch to be rather specialized in what trait categories it can dispatch on, which alleviates the potential for ambiguities (the ambiguities for the show method example above are impossible with Holy traits). But it makes further specialization impossible.

Can I interest you in type-parameterizing Core.Box? As shown here, that could result in immediate performance improvements. I also have ideas for how to reduce the number of boxes that are generated, but perhaps that should be for a different post (infact, I already pondered a simple one here that garnered zero attention, and this one only became an argument. I’m also hoping to build support for this one.).

18

Honest question: are traits that useful? Do we have some nice examples of “killer application” like we do for multiple dispatch?

I understand the interest, but I also value the language being “simple” instead of implementing a bunch of “potentially useful” features and becoming loaded with footguns like Scala and C++

5 Likes
19

For me traits are a limited feature which provides a lot of the benefits that would come if it was possible for a concrete type to inherit from several abstract types (not inherit only from a single one as is the case in Julia). There are a lot of useful patterns available in languages where it is possible to inherit from several abstract types. Having traits in Julia helps a lot in translating such patterns. And I think also this is a good way to think and get intuition about how to design traits and what is possible with them.

2 Likes
20

Yes, I do totally take your broader point – This is very hard to do and there are many real problems with it. My above comment was mostly trying to give people context for a very concrete limitation of so called ‘Holy traits’. Many people ‘feel’ these limitations but don’t necessarily have a precise understanding or way of phrasing them.

That’s not actually how I would do this, for the same reason I wouldn’t implement multiple dispatch as a series of chained double-dispatches in a single dispatch language. My plan instead has been to wait for the compiler pass infrastructure to solidify a little more (and for some free time to manifest) and then try to implement it as an overlay pass. And you may recall that I in fact did briefly roll up my sleeves at one point and implemented a form of Betray for Traitor.jl.

I think trying to just shoehorn it into existing packages won’t really show much benefit though, since those packages were written with the limitations of the current situation in mind.

5 Likes