Julia: abstract multiple inheritance

[StefanKarpinski]

In an email discussion we came to the conclusion that it made sense to have multiple inheritance in Julia with one fairly simple restriction:

If two abstract types are are used for dispatch in the same "slot" of the same generic function object then they cannot share a common, concrete descendant (all types share None as a common abstract descendant).

This restriction, together with Julia not allowing inheritance from non-abstract types, seems to address all the practical issues one typically encounters with multiple inheritance. The following, for example, would be disallowed:

abstract A
abstract B

type C <: A, B
end

f(A) = 1
f(B) = 2 # ERROR: A and B share a common descendant

Note that a generic function is an object external to all types, not a name inside of a type as it would be in a traditional object-orientation language. Thus, one can have f(a::A) in one namespace and f(b::B) in another namespace without problems, so long as the fs in these two namespaces are distinct generic function objects.

[JeffBezanson]

I'm not sure this blocks version 1.0. I agree we want it, but realistically it will take a bunch of time to settle and we know julia is perfectly usable without it.

[StefanKarpinski]

Is it that you think this will be very tricky to implement (understandably), or that you think the "no incest" rule will not be sufficient to make multiple inheritance sane? I would be willing to take a crack at this, but I'm afraid it may be beyond me.

[JeffBezanson]

The first one. Everything in the type system is pretty fragile, hard to modify without unintended consequences.

[StefanKarpinski]

Ok, that's fair. I think I won't even attempt this then. Too hard and mucking about with the type system is definitely your expertise rather than mine.

[koffie]

Maybe the no-incest rule in the initial suggestion can be weakened in a way similar to the following:

abstract A
abstract B

type C <: A, B
end

f(C) = 3
f(A) = 1
f(B) = 2 # no error since f is defined for all common descendants of A and B

[toivoh]

It seems to me that the no-incest rule presupposes that all descendents of A and B are known.
What if the system defines

abstract A
abstract B

f(::A) = 1
f(::B) = 2

and then a user comes along and defines

type C <: A, B
end

It seems a bit harsh that this should invalidate the function f itself. But it could of course refuse to accept a C, unless one of the following methods had been given:

f(::C)    = 3  # as in @koffie's post
f(::A::B) = 3  # method that applies to all common descendents of `A` and `B`

[toivoh]

Another thought about multiple inheritance (which I am for) is that it seems like it could make things a lot trickier for type inference; the intersection of two abstract types would never be empty. If there were some kind of mechanism to specify that two types are disjoint (e.g., can not share a common descendent), that might help.

[StefanKarpinski]

The thinking here was that the f function is either part of the interface to the A abstraction or the B abstraction, but having it be part of both interfaces would be weird and probably a bit broken. Requiring f(::C) to be defined when C <: A, B would probably be sufficient and is similar to how we handle method ambiguities already.

[toivoh]

@StefanKarpinski: That's very reasonable. My point was just that you cannot know at the time of the method definition for f whether there will ever exist a common descendent of A and B, so I think the question of when/if to issue ambiguity warnings/errors will be a bit trickier.

[diegozea]

What about something like dominant and recessive alleles on biology http://en.wikipedia.org/wiki/Dominance_%28genetics%29

Indicate one abstract (parent) to have dominant alleles (methods) over the other (maybe the first on the list), and in case of redundancy choose the dominant.

[jcrudy]

Hi there. I'm a new Julia user and multiple inheritance is important to me. Just adding my +1.

[jcrudy]

Also, @diegozea's suggestion is basically what is done by Python's method resolution order (mro), which I have found very sensible. There is always the possibility of having multiple method name conflicts and wanting a different resolution for each one. In python, that situation is handled by the super method.

[tknopp]

In Gtk.jl (JuliaLang/Gtk.jl#20) there is also a need for inheriting from multiple interfaces. This might be faked by using type Unions but this has the drawback that the Union type cannot be extended. Therefore the question: Might it be possible to allow to extend Union types? Or is this almost the same as multiple inheritance and therefore the same effort to implement? @JeffBezanson, @StefanKarpinski

[StefanKarpinski]

Yes, extensible type unions are largely equivalent to multiple inheritance.

[tknopp]

Ok then sorry for the noise. I thought we can cheat here

[StefanKarpinski]

Unfortunately, not. It's generally worth spitballing ideas since you never know when an odd one is going to turn out to be remarkably effective.

[lindahua]

The need of multiple inheritance arises in various applications. Examples where this is needed include:

• Graph package: https://github.com/JuliaLang/Graphs.jl/issues/16
• Statistical modeling: https://github.com/JuliaStats/Roadmap.jl/issues/4

To me, _abstract types_ in Julia plays more or less a similar role as _interfaces_ in Java/C# and the _concepts_ once proposed to the C++ 0x standard. With such a mechanism, one can write generic algorithms based on interfaces/abstract types. Algorithms that are decoupled from specific types have been proven to be very flexible in practice and have substantially higher chances of being reused in multiple contexts.

However, the power of interface-oriented programming is seriously restricted in Julia due to the single-inheritance requirement. In many of the situations, a specific type would implement multiple sets of interfaces so as to work with different algorithms. Without the support of inheriting from multiple abstract types, we have to resort to various stopgaps to work around the issue, often resulting in less-than-desirable interface design.

I understand that allowing multiple inheritance would further complicate the issue of method resolution that is already quite complicated, and major efforts would be needed to provide a satisfactory solution. However, I think the benefit of multiple inheritance is worthy of the efforts, as it would vastly improve the design of many libraries, thus making Julia a even greater language to use.

A difficulty has already been mentioned and discussed above is that the same method might be defined for two different abstract types while some descendant types might inherit from both. In my opinion, this issue can be addressed from two aspects:

1. We should encourage orthogonal interface design -- this would reduce the chance the same method being defined for two distinct abstract types.
2. In cases where this happens, we can raise ambiguity error at the calling site, and suggest the code author to write a specialized method to resolve the ambiguities:

abstract A
abstract B
type C <: A, B
    ....
end
foo(A) = "a"
foo(B) = "b"
c = C()
foo(c)   # raise an error here & suggest a specialized method

If foo is not called on c (or any instances of a descendant type that inherits both A and B), we don't have to do anything. This provides maximal flexibility without compromising type safety.

[ivarne]

3.Make multiple inheritance dispatch follow the order the inheritance was defined. So that C <: A, B would be more A, than it is Band foo(c) would dispatch to foo(x::A)

That will probably be more complex to implement, but I think it should be on the list of alternatives.

[knuds]

In the end of this video is how it is solved in scala
http://www.youtube.com/watch?v=LH75sJAR0hc
It starts around 1:10:00

[vtjnash]

I'll start by mentioning that I don't know where this is going, I'm just typing to see where it goes. My thoughts on this are that the current situation is a fundamental weakness of using a type system. There are probably basically two things we want to use the type system to express:

1. "This concrete type needs these fields to implement some behavior" -- Julia's DataTypes are exceptionally good at this.
2. The concept that "you will be able to do X-like things with this object" (where X is a function, e.g., "this thing can be iterated using start/next/done" or "this thing can do math with +-*/ but not %" or "this thing is a list implementation, but doesn't have a show method"). Julia has abstract types (and type-unions) as a stand-in for declaring these behavioral attributes, whereby the user indicates the intention to fulfill various method contracts. However, they require a strong a-priori knowledge of use cases (or good generalized patterns like iteration). This gets us really far (with a bit of duck typing). But then we come across cases where the author couldn't foresee the use-case in the design of their type system and so the user gets a no-method error. So then we demand multiple inheritance, so that the user can formalize the duck typing.

What I seem to be coming to is a analysis of the behavior that would result from eliminating abstract types. Instead of an a-priori type-tree, we often want to say: abstract Iterable has start,done,next, abstract AbstractArray has setindex!,getindex!,endof,length,size, abstract Number has +,-,*,/
but for numbers, somehow we still want to be able to have Real, Complex, etc. and for arrays to have ndims, because we want to dispatch on those. So lets extend it even further in my crazy hypothetical world: abstract AbstractVector{T} isa AbstractArray has ndims==1,eltype==T (where ndims and eltype are functions that take a DataType, and most everything else is specially formatted keywords). abstract Real isa Number has isreal==true, abstract Integer isa Real has isinteger==true, isinteger(::Union(Int8,Int16,Int32,Int64,Int128))==true (false case is implicit, because it doesn't has it)

In conclusion, the only way to make this work that I can see is to have the user declare which method they want to call. And since the type system is fluid, they must always declare it so that it doesn't break from loading other code :(

Perhaps there is some way to resolve it by preferring local methods? So, in the event of an ambiguity, the system would prefer methods declared in the current module, or methods declared in modules in it's global scope, then finally methods declared in any scope. However, (like @ivarne 's suggestion), this only seems to work well for single dispatch (which is quite boring anyways), and doesn't generalize well for multiple dispatch.

[lindahua]

Without abstract types, the capability of multiple dispatch would be severely impaired. Nearly the entire eco-system of the Julia is built upon multiple dispatch based on abstract type hierarchies (most important generic methods are defined on abstract types).

Admittedly, the power of multiple dispatch + abstract types comes with a lot of challenges. Dealing with ambiguities being one of them. We should face these challenges instead of eliminating the key aspects that define Julia.

Make no mistake, I am just against getting rid of abstract types, I am not against the proposals of how abstract types might be defined & used.

[vtjnash]

My discussion was rather long and probably confusing, probably impossible, and not much to the point. I actually wasn't proposing eliminating abstract types, but drastically changing how they are created. I was suggesting that the type tree should (hypothetically) be split based upon its true purpose. Concrete types would not have direct inheritance, but would inherit from abstract types based upon what methods can be called on them.

But all that doesn't really address the issue that Julia needs to disambiguate what the user intended for the type to "act like" when it implements multiple abstract type contracts.

[toivoh]

It's an interesting idea, but I'm not sure where it would go either. I
agree that abstract types are far from perfect for talking about which
interfaces that an object supports.

Perhaps dispatch based on this kind of classifications would be quite
confusing, especially if a type would suddenly change classification.

On the other hand, it is a special case of pattern dispatch :) If I ever
manage to release my new version of PatternDispatch.jl, it should allow to
toy with this kind of dispatch, as well as dispatch based on something
close to multiple inheritance. One key question is whether it would be able
to weed out enough false/undesired ambiguity warnings, or if Julia would if
such as scheme were implemented for multiple dispatch.

On Tue, Mar 18, 2014 at 2:16 PM, Jameson Nash [email protected]:

My discussion was rather long and probably confusing, probably impossible,
and not much to the point. I actually wasn't proposing eliminating abstract
types, but drastically changing how they are created. I was suggesting that
the type tree should (hypothetically) be split based upon its true purpose.
Concrete types would not have direct inheritance, but would inherit from
abstract types based upon what methods can be called on them.

But all that doesn't really address the issue that Julia needs to
disambiguate what the user intended for the type to "act like" when it
implements multiple abstract type contracts.

Reply to this email directly or view it on GitHubhttps://github.com/JuliaLang/julia/issues/5#issuecomment-37930764
.

[jakebolewski]

@vtjnash what you are describing sounds exactly like clojure's protocols. (See http://www.ibm.com/developerworks/library/j-clojure-protocols/, and (page 19) http://www.manning.com/fogus/Sample-Ch9.pdf).

Note however that Clojure's protocols are limited to single dispatch. This limitation only exists because Clojure is a hosted language and the JVM can optimize single dispatch extremely well. I think an even more powerful version Protocols could be designed for Julia to take advantage of efficient multiple-dispatch, although I'm not sure what form it would take.

[vtjnash]

yes, it does sound exactly like the clojure protocols. they "solve" the dispatch issue by requiring namespacing and dispatching only on the first parameter. My motivating use case (Gtk.jl) very nearly does the same thing in Gtk.GAccessors -- only the first parameter is typed and all of the functions are tucked away in this module (with a plan to export them using the getindex syntax of a[:b] so that it isn't extremely awkward for the user to access them)

---

Yes, extensible type unions are largely equivalent to multiple inheritance.

@StefanKarpinski well, so, what if we were to allow the user to extend a type unions (or, because they are essentially the same, a type-union-like "type interface" thing), but only at type creation? perhaps that would give the benefits of multiple dispatch with less method ambiguity issues (since no methods have been defined yet for the new type). this doesn't push the interface definition back quite as far as Clojure allows, but it also doesn't have the same ambiguity that seems to result from attempting that

Requisite code sample:

typealias MyUnion Union(A,B,C)
type Z <: AbstractZ, MyUnion, MyUnion2, MyUnion3
  #type `Z` inherits from at most one abstract type, and any type unions
end
# now all _direct_ uses of MyUnion (in method parameter lists, types, or bodies of methods) are redefined as Union(A,B,C,Z)
# most ambiguities would hopefully be avoided at this point in execution, since Z doesn't have any methods currently, except those inherited from its parent or the type union

while it may require tracking some additional information to check for new ambiguities, i think that information may already need to be tracked for #265

this might mean that any method conflicts would need to be addressed in the body of the type

type Z <: MyUnion
  Main.conflict_method(::Z, ::Z) = 2
end

or perhaps it is just a design/runtime error to mix abstract and typeunions in a way that would result in a method ambiguity and would not happen in well-designed code.

[tknopp]

I think that the idea of defining interfaces using

  abstract Iterable has start,done,next

is very nice. There would have to be at any time a check whether a user defined type actually implements tha interface or not. Besides documentation this is what defining interfaces really brings us. Instead of a method not defined error deeply in some function, one has the opportunity to get high level error messages.

All this reminds me a lot on C++ and the Concept-light proposal that might make it for C++14 or C++17. Its also mainly about making compiler messages better. In Julia, the ability to restrict parametric types gives us the first half of Concepts. Beeing able to define what abstract types have to provide would be the second half.

And of course abstract multiple inheritance would make the "interface proposal" even more useful

[vtjnash]

+1

On Friday, March 28, 2014, Tobias Knopp [email protected] wrote:

I think that the idea of defining interfaces using

abstract Iterable has start,done,next

is very nice. There would have to be at any time a check whether a user
defined type actually implements tha interface or not. Besides
documentation this is what defining interfaces really brings us. Instead of
a method not defined error deeply in some function, one has the
opportunity to get high level error messages.

All this reminds me a lot on C++ and the Concept-light proposal that
might make it for C++14 or C++17. Its also mainly about making compiler
messages better. In Julia, the ability to restrict parametric types gives
us the first half of Concepts. Beeing able to define what abstract types
have to provide would be the second half.

And of course abstract multiple inheritance would make the "interface
proposal" even more useful

—
Reply to this email directly or view it on GitHubhttps://github.com/JuliaLang/julia/issues/5#issuecomment-38904013
.

[MikeInnes]

I mentioned this on the mailing list, but for the record:

It occurs to me that we actually already have multiple inheritance – for example, [1, 2, 3] inherits from Array{T, N}, Vector{T}, AbstractArray{Int, 1} etc. Yes, you can think of this as single inheritance with parents, but parentage is really just a way to prioritise types: "X is an Array first, and an AbstractArray second, so if there's any ambiguity dispatch on the former".

Would it be possible to extend this idea to multiple inheritance? So you can inherit from as many types as you like, but you _must_ explicitly declare which types are more important. Ambiguities only have to be resolved once, and there's no extra burden when writing polymorphic functions (which also means that you can add inheritance to a type after it has been defined, safely).

[pbazant]

+1 For abstract multiple inheritance. If I understand it correctly, multiple dispatch can be viewed as single dispatch on the lattice of tuple types. A dispatch ambiguity arises when the set of (tuple) types for which there is an implementation does not form a sublattice in the "big" lattice of all tuples. A check of this kind is already performed in Julia, issuing a warning if an ambiguous dispatch is possible. Could not the same algorithm be used to detect possible ambiguities and issue warnings in the presence of multiple inheritance? In other words, I do not see much difference from the present situation. In any case, it would be nice to treat dispatch ambiguities in an uniform way.

Moreover, there are meets in the type lattice even if only single-element tuples are considered. For example
Array{Int64,1}<:Array
true
Array{Int64,1}<:AbstractArray{Int64,1}
true
but
Array<:AbstractArray{Int64,1}
false
AbstractArray{Int64,1}<:Array
false
In this case, no warning is issued and the dispatch prefers Array, which seems sort of arbitrary.

[zenna]

Bump

[kmsquire]

@zenna, bumping is good, bumping with a little bit of discussion of how this would help something you're working on would be even better!

[timholy]

I'm pretty sure this won't be done by conventional multiple inheritance---instead, we'll likely improve our syntax for traits. See #2345.

[prcastro]

While Trait.jl is very nice, it feels like a hack on top of Julia's syntax. It would be really useful to have something like that on Base.

[timholy]

See #2345.

[skariel]

seems everybody agrees traits is the way to go, why not just close this issue?

[timholy]

In my opinion: because closing the last remaining single-digit issue in julia should be a ceremonial occasion, with champagne, speeches, and paddleboats.

(Not to mention having the code that implements traits!)

[StefanKarpinski]

Until we have some more language-level support for traits, I don't think we should close this. The traits experiment seems to be working pretty well, but it's still not without some awkwardness.

[afbarnard]

Huh, with all the mentions of "type graph" in the documentation on types I expected that multiple inheritance was already implemented. (I'm still learning.) Anyway...

The use case I have in mind is using a matrix as a graph representation. That is, it would be nice to be able to say something like

abstract Graph
abstract AbstractArray{T<:Real,2} <: Graph

Then one would implement all the graph methods for AbstractArrays and be done. This is novel compared to the other examples (e.g. #2345) because it would be adding a user-defined type above a library type. I also don't know if traits would solve this problem because the basic interface for a graph is at least several methods.

But perhaps composition is a better approach than multiple inheritance in this case:

abstract Graph
type ArrayGraph <: Graph
    array::AbstractArray
end
# methods: graph_type, number_nodes, number_edges, has_node?, has_edge?, node_value, edge_value, neighbors, etc.

I don't have a sense which approach is better or more idiomatic in Julia. That is part of what I am asking. Anyway, newcomers like myself would likely benefit from (more and more complex) examples in the documentation demonstrating Julia design idioms, and such examples would probably preempt some of these questions. (Perhaps I could contribute an example myself once I thought this through more.)

The composition approach would be the idiomatic answer in Go, but Go also has interfaces which can be (almost) arbitrarily mixed and matched. (And so there would be a Graph interface implemented by some concrete type.)

Incidentally, the people crying out for subtypes of concrete types might be pacified with the Go approach of embedding other concrete types and adding syntactic sugar for member access.

[StefanKarpinski]

Multiple inheritance isn't only way a type graph can cease to be a tree. Julia has covariant tuple types, union types, parametric types, and type vars, so the type graph is actually a fairly complicated graph. (It's an unbounded lattice to be specific.) Some examples of non-trivial type intersections:

julia> typeintersect(Tuple{Int,Number}, Tuple{Real,Float64})
Tuple{Int64,Float64}

julia> typeintersect(Tuple{Int,Number}, Tuple{Real,Complex})
Tuple{Int64,Complex{T<:Real}}

julia> typeintersect(Union{Int,Float64}, Union{Int,String})
Int64

julia> T = TypeVar(:T, Union{}, Number)
T<:Number

julia> typealias IntTuple{N} NTuple{N,Int}
NTuple{N,Int64}

julia> typeintersect(Tuple{T,T}, IntTuple)
Tuple{Int64,Int64}

If you're interested in more, you may want to read @JeffBezanson's PhD thesis, which goes into this subject in a significant amount of depth.

The idea of using sparse matrices to represent graphs is an old one. You've actually managed to hit on the subjects of two Julia co-creators' PhD theses: @ViralBShah's PhD thesis was largely about using sparse matrices to implement efficient distributed graph algorithms. The abstract ends with:

The duality between sparse matrix algorithms and graph algorithms is used to build a toolbox to compute with graphs in Star-P.

@ViralBShah and @alanedelman can probably say much more useful things about whether it's a good idea to actually implement graphs as sparse matrices, or if it's better to keep them as separate data structures and leverage the duality to make certain computations more efficient.

As a community, it seems like we're leaning towards using traits instead of multiple inheritance. There's even been discussion of potentially replacing single inheritance with a traits-based approach. This design aspect of the language has yet to play out.

Incidentally, the people crying out for subtypes of concrete types might be pacified with the Go approach of embedding other concrete types and adding syntactic sugar for member access.

Can you elaborate on how you see this working? Go does seems to have found a nice way of duck typing with static types, but it's unclear to me how one can make Go-style implicit interfaces work with Julia's dynamic typing and dispatch (we can already do normal duck typing).

[afbarnard]

@StefanKarpinski, I wasn't suggesting to combine Go-style implicit interfaces and Julia's type system, merely that supporting some kind of structure reuse in concrete types would make some people feel better, and Go implements one way of doing that. I was basically thinking of doing something along the lines of embedding for structs with the accompanying syntactic sugar for field access (explained in the section of the Go documentation on Embedding), but embedding also works for interfaces, so maybe that's what you are referring to. There may be something in the way Go does method dispatch for embedded interfaces that could inform this discussion of multiple inheritance. Let me know if this is getting off topic and we can open a discussion elsewhere.

Here's an example of what it might look like to copy Go struct embedding for Julia.

type PointValue
    x::Vector{Float64}
    f::Float64
end
type PointValueGradient
    embed PointValue # This means the fields of PointValue are embedded here
    g::Vector{Float64}
end
pvg = PointValueGradient(x, f(x), g(x)) # Flattened construction
(pvg.x, pvg.f, pvg.g) # Example of (flattened) access to fields

In the last line pvg.x is syntactic sugar for pvg.PointValue.x, and similarly for pvg.f, but pvg.g is direct access. Go does not flatten the struct representation for construction as I have done, so such flattening would be an extra convenience. (Go expects PointValueGradient(PointValue(x, f(x)), g(x)) for construction.) Indeed, to flatten or not to flatten seems like an important design choice. (Go chose not to flatten, only to provide some syntactic conveniences.)

[StefanKarpinski]

I don't really understand the f(x) and g(x) notation – what does that mean here?

[afbarnard]

Sorry, I didn't realize I used the same names in multiple ways. I meant f() and g() to be arbitrary functions, distinct from the fields f and g. The relevant parts equivalently rewritten without name reuse:

xpt = [...] # A n-dimensional point, x
fx = func(xpt) # Some function of x
gx = grad(xpt) # The corresponding gradient of x
pvg = PointValueGradient(xpt, fx, gx)

[StefanKarpinski]

So if type B embeds A then the constructor of B passes the corresponding arguments through to the constructor of A? What if A has custom constructors? Related discussion here: https://github.com/JuliaLang/julia/issues/4935.

[datnamer]

What is the latest thinking here? Is this still being considered or will abstract types be deprecated in favor of traits? Or is it being shelved entirely until after 0.5?

[mauro3]

It looks like multiple-inheritance will not be implemented but instead some sort of protocol/traits system (but I guess this issue will stay open for the time being). What happens to single inheritance is being discussed. See #6975. Definitely not 0.5 material though, 0.6 at the earliest.

[andyferris]

I wasn't sure where to post this, but I thought here looked like a central enough location. After the JuliaCon 2016 hackathon, where a discussion on trait syntax and implementation (if I remember correctly, between @timholy, @StefanKarpinski, @JeffBezanson, I think maybe @carnaval, and certainly several others) took place, @c42f and I went ahead and made a package called Traitor.jl which implemented the syntax (via a macro) and the trait behaviour (via a @generated thunk) as discussed at the hackathon. I'm not sure if the result of that discussion has been documented anywhere?

As a quick overview of (my memory of) that discussion, the idea was to have function signatures that look like f(x::T::Trait) or even f(x::::Trait) (equivalent to f(x::Any::Trait)) to define trait-based dispatch. Standard multiple-dispatch takes precedence, but each "standard" method can be associated with several trait-based "submethods". Traits are defined on a type-level. A trait class is an abstract type, like abstract Size, and a specific trait is a subtype, like immutable Big <: Size; end. To assign a trait to a type, you use the trait class constructor, writing e.g. Size(::Type{BigInt}) = Big. In that example the trait is nominated explicitly, but they might also be computed (which might be useful for defining interfaces? I dunno...).

Finally, traits of the same class can be combined in a type union (e.g. Union{Big, Small}) or the intersection of traits from different classes can be combined in a Tuple-type (e.g. Tuple{Big, Smelly}). The latter gives you some kind of "multiple inheritance".

Anyway, the package isn't fully fleshed out (and most likely still buggy!!), but it is intended to be a playground to explore the syntax and trait system discussed at the hackathon.

[mauro3]

@andyferris: #6975 might be the better place for your post.

[timholy]

Glad you did this! From the README it looks very nice, and I love the package name.

[JeffreySarnoff]

@andyferris @c42f Where would like comments?

[andyferris]

@mauro3 Thanks for that, I'll add a reference there.

@timholy Thanks. The name (and README) was born of delirium after lack of sleep on the plane back to Australia. :)

@JeffreySarnoff I'm not sure precisely what you mean - but to me it is reasonable to discuss here or at #6975 about the syntax and general trait dispatch discussed at JuliaCon (as I understood it and explained above) or raise an issue on the package for specific implementation details, to make PRs or other requests. Does that make sense?

[mauro3]

Concerning the syntax for trait functions: there was a long discussion over on https://github.com/JuliaLang/julia/issues/11310#issuecomment-170421099 about function syntax (also linking into the the type system overhaul: https://github.com/JuliaLang/julia/issues/8974). This should probably be considered together with trait-function syntax.

And whilst multiparameter traits are not on the table, maybe thoughts on syntax should still keep them in mind. Julia has a tendency to get to the most generic implementation eventually (a recent case in point would be not-one-based indexing).

[andyferris]

@mauro3 Thanks again fro the reading material. I've tried to understand - but could you please explain what multiparameter traits are? (are they traits of combinations of types?)

Furthermore (and I've tried to understand this one before!) what exactly is UnionAll planned to be/mean?

[mauro3]

Yes, multiparameter traits involve more types. Say, there could be a
trait which contains all Tuples{A,B} for which A+B is possible.

If I recall correctly, UnionAll is the following: in Julia parameterized
function signatures are more expressive than how types can be expressed.
The set of allowed argument tuples of say f{X}(x::X,y::X) = ... cannot
be currently expressed as type. UnionAll would allow to express the
type {X}(::X,::X).

It would be good to also be able to express the types constrained by
traits, combining above with your syntax this may be
{X}(::X::T1,::X::T2). In Traits.jl, the multiparameter traits use
syntax like {X,Y; Tr{X,Y}}(::X,::Y) as straight appending to the ::X
does not work anymore.

[andyferris]

OK cool. I think we could probably do that trait for Tuples already.

abstract CanAdd
immutable Addable<: CanAdd; end
immutable NotAddable <: CanAdd; end

CanAdd{T1,T2}(::Tuple{T1,T2}) = method_exists(+, Tuple{T1,T2}) ? Addable : NotAddable

The question is how to apply this to a function definition, etc. I see all of these syntax and type issues are interrelated now.

EDIT: Fixed typo in code

[JeffreySarnoff]

x::Type::Trait{ trait1, trait2 }
Because there ciuld be something else that would follow the second ::, and looks like Union{...}

[andyferris]

Indeed, we've decided to use Tuple{} instead of Trait{} since it is already a part of the language and that's how collection of types of arbitrarily length necessarily must be stored internally at the moment. It might not seem so important if/when {...} get's lowered to Tuple{...}.

So the package allows x::Type::Tuple{ trait1, trait2 } where trait1 might be a single trait type, or a Union{...} of them (from the same class). When there is no Tuple the, the macro inserts it for you (for user-friendliness in the case you only have one trait), and the lack of trait annotation corresponds to Tuple{} (c.f. Trait{}).

To be more general, I _suppose_ you could put a further union on the outside to combine multiple dispatch patterns into one signature, but I guess getting diagonal/multi-parameter dispatch etc. working would be just as (or more) important.

[mauro3]

@andyferris, yes the trait declaration works but there is no syntax to use it in a trait-function. Consider f(x,y,z)= (G(x,y),H(y,z)). Traitifying, we'd need (x,y) part of CanG trait and (y,z) part of CanH trait.

[tbenst]

I'd love to see this in Julia. And I think it's necessary if we want to use category theory in Julia. Hlearn / Subhask provide a motivating example of how powerful and flexible multiple inheritance can be for designing machine learning frameworks.

In Hlearn, we can define a new type that is an instance of Metric and contains instances of Equivalence, and suddenly we can do nearest neighbor queries using cover trees among many other algorithms:

data Bp = A | T | C | G | N
type instance Logic Bp = Bool
instance Eq_ Bp where
    A==A = True
    T==T = True
    C==C = True
    G==G = True
    N==_ = True
    _==_ = False

data DNA = DNA [BP]
instance Metric DNA where
    distance = levenshtein

Behind the scenes, this is all enabled by multiple inheritance. SubHask takes this to an extreme, allowing for custom non-boolean logics. But the beauty of the type system, is that as algorithm users we can use complicated topologies without needing to touch the underlying algorithm. For additional motivation, see Physics, Topology, Logic and Computation: A Rosetta Stone.

Edit: I realize this also would benefit from formal type interfaces. I don't know Julia well enough to say if anything else is block this, but my impression is that multiple inheritance is the big one

[ChrisRackauckas]

Was closing this on purpose?

[quinnj]

Lol, there was a commit in TerminalMenus.jl that fixed "#5", and it closed this issue......

[StefanKarpinski]

Yikes.

[AzamatB]

Can this go into 2.0?

[StefanKarpinski]

Possibly. It’s not decided or designed yet.

[datnamer]

So hypothetically how will/could implementing this affect all the compiler and subtyping optimizations/ bug fixes? Will there be a non trivial amount of work that will have to be duplicated? If so, perhaps it would be better to do this sooner rather than later.

[StefanKarpinski]

Have at it :grin:

[datnamer]

Fair enough. Past work is sunk, but I'm just wondering to what extent future compiler work would be rendered moot.

[JeffreySarnoff]

It is unclear to me why you would presuppose meaningful future compiler work would at odds with bringing abstract multiple inheritance to Julia. The use of abstract single inheritance will persist gregariously. The type system is very coherent and self-expressed in the implementation of Julia. That abstract multiple inheritance provides room for the application of augmented/additional compilation techniques is not future compiler work negating in any serious way afaik.

[DilumAluthge]

seems everybody agrees traits is the way to go, why not just close this issue?

I think that there is still important functionality that is not possible with traits as they currently exist in Julia but would be possible if we had abstract multiple inheritance.

One example is the ability to dispatch on arrays in which all of the objects have the FooTrait. With abstract multiple inheritance, this would look something like:

abstract type AbstractA end
abstract type AbstractB end
abstract type AbstractC end
abstract type AbstractD end

abstract type FooTrait end
abstract type BarTrait end

struct A <: AbstractA, FooTrait end
struct B <: AbstractB, FooTrait end
struct C <: AbstractC, BarTrait end
struct D <: AbstractD, BarTrait end

f(::FooTrait) = "foo"
f(::BarTrait) = "bar"
f(::AbstractArray{<:FooTrait}) = "foo array"
f(::AbstractArray{<:BarTrait}) = "bar array"

f(A()) # this would return "foo"
f(B()) # this would return "foo"
f(C()) # this would return "bar"
f(D()) # this would return "bar"

f([A(), A()]) # this would return "foo array"
f([B(), B()]) # this would return "foo array"
f([C(), C()]) # this would return "bar array"
f([D(), D()]) # this would return "bar array"

f([A(), B()]) # this would return "foo array"

f([A(), B()]) # this would return "bar array"

As discussed in https://github.com/andyferris/Traitor.jl/issues/9 and https://github.com/mauro3/SimpleTraits.jl/issues/63, this is not possible with traits as they currently exist in Julia.