Why does Julia not support multiple traits?

Wouldn’t it be nice, if we could define a method like this:

# assuming Iterable{T} is an abstract type in Base,
# and merged into all relevant iterable classes.

function myfindmax(itr::Iterable{T})
    println("inferred type $T")
    findmax(itr)
end

julia>myfindmax(1:5)
inferred type Int64
(5,5)

And would then expect some statements to be true:

  1. the method is called only for itr objects, which “are” Iterables. Which means, there is a contract, assuring us, that we can call start, next, done, and eltype for our itr.
  2. we (and the compiler) can assume, that next(itr, i) returns an element of type T.

Now, there are may abstract types and data types, which “are” iterable. They respect the Iterable’s contract, but is is not manifested in the code. Nor is it possible to dispatch the methods according to this.

Now, AbstractArray for sure has more important properties, than being iterable, and there are many other types, which are important on their own, but as a matter of course are also iterable. Attaching such common properties is possible in other languages using multiple inheritance (C++) and traits (Scala). There are some technical difficulties in the implementation in those languages, due to the complexity of their type system. In Julia, is would not expect an essential technical challenge, because of its light-weight type system.
My understanding of abstract types in Julia, is

  • they specify the programmer’s intention to support a certain set of functions (interface, contract, trait).
  • they are used to select the method implementation according to argument types (method dispatch)

So, for bullet one, I do not see, why a programmer shouldn’t declare to support several traits.
For dispatching, currently, each type has a chain of direct supertypes, ending at Any. The dispatching algorithm has to find the method implementation, which is most specific for all its arguments. A subtype is more specific than its supertype. Therefore implementations of methods for abstract types at the Any - end of the chain can be hidden by others.
The situation does not change dramatically, if each type would have more than one direct supertype, generating a tree of supertypes instead of the chain. A possible solution with no impact to the dispatching algorithm would be linearisation of the tree. That means convert it into a linear list using a canonical algorithm. Best example I know for that is used in ‘Scala’, a strictly typed compiled language without multiple inheritance, with Traits, generating code for the JVM.

3 Likes

Did you see SimpleTraits.jl?

3 Likes

See also https://github.com/mauro3/Traits.jl for a now defunct traits/interface prototype. There are also links to other attempts in its readme: https://github.com/mauro3/Traits.jl#other-trait-implementations

4 Likes

See also Traitor, which doesn’t work yet but sketches out a tentative API for an implementation in Base. (It’s linked from SimpleTraits, so you probably already found it.)

Also worth pointing out that it’s easy for you to do this manually. For example (inspired by an example in the Traitor README):

foo(A) = foo((Size(A), Odor(A)), A)
foo(::Tuple{Big,Smelly}, A) = ...
2 Likes

I think, the principle has become clear to me. I made an example, which also infers the element type, as I wanted in my introductory example (now completed).

abstract type IterableTrait end
struct Iterable{T} <: IterableTrait end
struct NotIterable{T} <: IterableTrait end
IterableTrait(::Type) = NotIterable{Any}()
IterableTrait(::Type{A}) where {A<:AbstractArray{T}} where {T} = Iterable{T}()

myfindmax(itr) = myfindmax( IterableTrait(typeof(itr)), itr)
function myfindmax(::Iterable{T}, itr) where T
    println("inferred element type: $T")
    findmax(itr)
end

With the results:

julia> myfindmax([-1.0, -0.0, 0.0])
inferred element type: Float64
(-0.0, 2)
julia> myfindmax(1:5)
inferred element type: Int64
(5, 5)
julia> myfindmax(x for x in 1:5)
ERROR: MethodError: no method matching myfindmax(::NotIterable{Any},::Base.Generator{UnitRange{Int64},##1#2})
Closest candidates are:
  myfindmax(::Iterable{T}, ::Any) where T at REPL[178]:2
  myfindmax(::Any) at REPL[176]:1
Stacktrace:
 [1] myfindmax(::Base.Generator{UnitRange{Int64},##1#2}) at ./REPL[176]:1
 [2] macro expansion at ./REPL.jl:97 [inlined]
 [3] (::Base.REPL.##1#2{Base.REPL.REPLBackend})() at ./event.jl:73

That works fine and the functionality, which I requested, is there at runtime.

Why am I not content? It seems to me an ugly, boilerplate, work-around solution.
Some people say, “each design pattern is an indication for a missing language feature”. That was headed towards C++, Java, Jave-enterprise etc.
search engine result
I was hoping, Julia can do better!

In SimpleTraits.jl there is a iterator trait defined, which can then be used as

using SimpleTraits, SimpleTraits.BaseTraits
@traitfn f(x::::IsIterator) = 1
@traitfn f(x::::(!IsIterator)) = 2
f(1:3) # -> 1
f(:a) # -> 2

But yes, this should and will become a language feature.

“each macro is an indication for a missing language feature” :scream:

1 Like

I second this. Interfaces/traits should have a much simpler interface. In particular having two systems (Type hierarchy and traits is confusing)

I still think that abstract multiple inheritance is a very simple Interface that everybody directly understands. Its just part of the solution though.

1 Like

I would even say: Abstract types (in Julia) are traits. It would not be required to introduce a new concept, just allow each type definition to define more than one parent.
There would be an obvious extension to this concept towards interfaces (I saw your proposal): define means to allow the compiler (or runtime system) check the trait’s contract is met (all methods with required signatures are defined).

3 Likes

Each language features is an indicator of a missing macro.

9 Likes

Yes, this is essentially how it works in Java/c#: have interfaces which are fully abstract and implement against them. Without being able to implement multiple interfaces this useless though.

You can search “protocols” in Guthaben which Jeff envisioned to be a more generic “trait like” thing.

If you want to move this forward, I think a Concrete proposal (julep) Would be best

I think it makes sense to think about traits and interfaces/protocols as separate things.

A trait, I understand as a set of types, which can be used for dispatch. Using this definition, an abstract type indeed encodes such a set. One thing traits need to make them useful is that types can be added to them after creation; and this is where multiple inheritance would fall short (as the supertypes of a type are fixed at its creation/definition). Holy-traits are a pattern to create trait, which is extensible after its creation. Things which need to be figured out concerning traits are inheritance, intersections and such and what that means for method resolution; presumably set operations will do.

Now, as I see it, interfaces/protocols are a way specify which types belong to a certain trait: say the trait of all types supporting iteration means that each of its elements has to have methods start, next and done defined. The specification of these interfaces can be a bit intricate, this was discussed in #6975.

I think it is useful to keep a mental distinction of above two concepts even though they are quite intertwined.

2 Likes

Having learned a lot about traits, Holy Traits, Traitor.jl, multiple abstract inheritance, and protocols, I know clearer now, what I want. I see, that this discussion is very old and has not come to a conclusion yet. So I want to add my list of wishes. I don’t want to spoil the discussion, but be constructive.

My principles for the subject:

  • simplicity
  • orthogonality
  • liberal policy in type strictness
  1. The Julia type system with leaf types, abstract types, type unions, type parameters is close to perfect; together with the unique multiple dispatch an ideal working concept, I would not like to miss. Main purpose of abstract types is method dispatch and transport of type information. Whether the expected methods are missing for an object, is detected at runtime - no problem in a testing-oriented development approach. I love duck-typing!

  2. I want a (small) extension, though, that is multiple abstract inheritance. That would allow a leaf-type or abstract type to be contained in a set of super types, which is not restricted by the linear chain of super-types. To maintain method dispatch, a kind of linearisation of the supertype-set would be fine.

  3. It is not necessary to introduce much new syntax or a new feature. I think it is acceptable, that author of the base type has to decide, which supertypes his type belongs to. If remote extensibility is required, other concepts like (Holy-) traits or delegation, are still available.

  4. I do not see Jeff’s protocols as a replacement for abstract types, but as an optional additional property, the purpose of which is documentation, control (early error messages for undefined methods). There is a canonical order relation on the set of protocols (the inclusion of their methods sets), which must be compatible with the subtype relation on the set of types. (The map `{t | t is a type} → {p | p is a protocol} assigning a protocol to each type (default protocol does not have any methods) should be an order-homomorphism).

  5. I see multiple inheritance from leaf types problematic, infeasible, and unnecessary. Allow for extension of leaf-types by abstract types (singular inheritance from leaf-types).

  6. I would like to see automatically generated getter- (and setter) methods for some or all fields of a (mutable) struct.

  7. I would like to see automatically generated delegate methods for a field of a data type, if the field is typed with a protocol attached for all the methods mentioned in the protocol.

That needs more of an explanation than a name. I’m not entirely sure how that could be expected to be determined and easily understandable.

One thing I’ve been wondering is to what extend the base library would be designed differently if the language supported traits along the lines that @mauro3 describes. For example, would it then make sense to make something like Number a trait rather than an abstract type that one needs to inherit from? Same say for AbstractString, could that be a trait, and a concrete string implementation would not have to inherit from AbstractString?

My understanding is that the current plan is to deal with traits after 1.0 because one could probably just add them to the language without breaking anything. While that is true, the story seems less clear and simple in terms of the design of base, i.e. one could probably not move base from a mostly inheritance based design to a traits based design until 2.0. Or maybe one could? I haven’t thought much about it yet and would be quite interested to hear what others think.

2 Likes

I understand the term linearization as defined in the Scala Reference manual. In the case singular inheritance it returns the chain of supertypes starting with the type itself and ending with Any. In the case of multiple inheritance, the order of the list respects all defined subtype relationships.

Scala 2.11 Reference Chapter 5

5.1.2 Class Linearization

The classes reachable through transitive closure of the direct inheritance relation from a class C
are called the base classes of C. Because of mixins, the inheritance relationship on base classes forms in general a directed acyclic graph. A linearization of this graph is defined as follows.
Definition: linearization

Let C be a class with template C1 with … with Cn { stats }. The linearization of C, L( C)
is defined as follows:

L(C) = C, L(Cn) +⃗ … +⃗ L(C1)

Here +⃗ denotes concatenation where elements of the right operand replace identical elements of the left operand:

a, A +⃗ B == a, (A+⃗ B) if a ∉ B  A+⃗ B if a ∈ B

Example

Consider the following class definitions.

abstract class AbsIterator extends AnyRef { ... }
trait RichIterator extends AbsIterator { ... }
class StringIterator extends AbsIterator { ... }
class Iter extends StringIterator with RichIterator { ... }

Then the linearization of class Iter is
{ Iter, RichIterator, StringIterator, AbsIterator, AnyRef, Any }

Note that the linearization of a class refines the inheritance relation: if C
is a subclass of D, then C precedes D in any linearization where both C and D
occur. Linearization also satisfies the property that a linearization of a class
always contains the linearization of its direct superclass as a suffix.

For instance, the linearization of StringIterator is
{ StringIterator, AbsIterator, AnyRef, Any }
which is a suffix of the linearization of its subclass Iter. The same is not true for the linearization of mixins. For instance, the linearization of RichIterator is
{ RichIterator, AbsIterator, AnyRef, Any }
which is not a suffix of the linearization of Iter.

1 Like

My thesis is: we don’t need traits, if we have multiple abstract inheritance. For the standard library that would mean, some new abstract types (like Iterable) would be defined in Base and attached to the applicable existing classes. Minor effects to existing user code.

@tim.holy the image universary seems to use traits. Is this something that would we possible with protocols?

I personally find traits to be quite difficult to understand. Maybe someone could give an example how “Number” “Signed” … would be expresses in terms of traits.

One nice property of traits is a nice symmetry: I can define a new type and apply an existing (e.g. Base) trait to it, and I can also define a new trait and apply it to existing (e.g. Base) types. Abstract multiple inheritance does not give me that symmetry: I can define a new type that inherits from an existing abstract, but I can’t retroactively apply a new abstract base to an existing type. That seems like a pretty important limitation.

6 Likes

@rdeits I see your point. The problem is, that Julia does currently not allow to inherit from leaf types. Otherwise you could extend an existing class (leaf type) with an abstract type just by sub-classing.
So I should modify my wish-list with

  1. Allow for extension of leaf-types by abstract types (singular inheritance from leaf-types).

After that adaptation, I see no big differences between the “abstract type” and the “traits” approach. I want to preserve the other property of the abstract types, which is the possibility of type parameters.