Open StefanKarpinski opened 13 years ago
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.
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.
The first one. Everything in the type system is pretty fragile, hard to modify without unintended consequences.
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.
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
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`
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.
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.
@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.
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.
Hi there. I'm a new Julia user and multiple inheritance is important to me. Just adding my +1.
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.
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
Yes, extensible type unions are largely equivalent to multiple inheritance.
Ok then sorry for the noise. I thought we can cheat here
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.
The need of multiple inheritance arises in various applications. Examples where this is needed include:
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:
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.
3.Make multiple inheritance dispatch follow the order the inheritance was defined. So that C <: A, B
would be more A
, than it is B
and 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.
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
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:
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.
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.
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.
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 notifications@github.comwrote:
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 .
@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.
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
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.
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
+1
On Friday, March 28, 2014, Tobias Knopp notifications@github.com 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 .
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).
+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.
Bump
@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!
I'm pretty sure this won't be done by conventional multiple inheritance---instead, we'll likely improve our syntax for traits. See #2345.
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.
See #2345.
seems everybody agrees traits is the way to go, why not just close this issue?
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!)
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.
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.
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).
@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.)
I don't really understand the f(x)
and g(x)
notation – what does that mean here?
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)
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.
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?
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.
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.
@andyferris: #6975 might be the better place for your post.
Glad you did this! From the README it looks very nice, and I love the package name.
@andyferris @c42f Where would like comments?
@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?
In an email discussion we came to the conclusion that it made sense to have multiple inheritance in Julia with one fairly simple restriction:
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:
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 andf(b::B)
in another namespace without problems, so long as thef
s in these two namespaces are distinct generic function objects.