Add type mixins to overcome subtype limitations


#21

I feel like each post starts over from scratch with no after-v1.0 end goal in sight

My personal understanding (and maybe I’m wrong!) is that allowing trait-based multiple dispatch has been discussed over time as the likely “Julia multiple inheritance” of the future. The subtyping algorithm needed to do this appears feasible (e.g. in Traitor.jl) so unless I missed something important I don’t think that side of things will hold this up. Multiple dispatch is Julia’s great strength - making it stronger would be killer, and I don’t see a good reason for not getting around to this (eventually).

IMO this should let us define and adhere to interfaces/concepts in a clear way (with the usual caveats that @TomasPuverle discussed about the implications of an interface changing - but generally Julia has done a decent job with deprecation messages). Of course this is just my opinion, and I can’t see the future, but my suggestion would be patient and see what is missing (if anything) in the post-traits world - traits would impact many things on Stefan’s list.

Regarding mix-ins, I’d speculate that trait-based interfaces would be function-based not field-based, so you would have to specify some small numbers of setters and getters for each interface you support instead of using particular field names (while I hate the overhead of setter/getters in C++/Java/etc, take a complex interface like AbstractArray in Julia and note that one has to define just one static trait (LinearFast/LinearSlow), one property (size), one getter method (getindex) and one setter method (setindex!). Amazing, but that’s what we get out of multiple dispatch (and single-trait “Tim Holy trait trick”), so I’d expect similar for other interfaces).

I’m not sure if speculative future features should go in the docs (depending on their level of likelihood and proximity, I suppose).


#22

I have worked with Julia for two years now and, after maybe some months of toil, have not missed structural inheritance or mixins. Having the generism of Julia makes has-a relationships a breeze to use.

That said, I am eagerly following the development of traits in the language, although I don’t see its relevance toward type mixins. Traits do not allow you to share many fields between types and I think that is a good thing. The idea that semantically similar types should be structurally similar is, I think, not a good idea in a language as generic as Julia is.


#23

If that was directed at my comment, then I agree. :slight_smile: Traits let types share interfaces and and requiring that types share fields seems both unnecessary and too restrictive (i.e. defining an interface in terms of a type’s fields doesn’t seem as powerful or generic as an interface defined in terms of fulfilling some (overloadable) methods, at least in Julia).

(Mixins are a common way of doing multiple inheretence - I was saying traits will bring this to Julia instead, so IMO we shouldn’t worry about mixins).


#24

But since the question comes up all the time, it would be nice to have a couple of paragraphs in the manual or the FAQ that explains

  1. the reasoning behind Julia’s design,
  2. how to solve common situations that people in OO solve with mixins.

#25

I have to admit I struggle with this a lot. Maybe someone can tell me what to do in a practical scenario. Say I really like the Julia standard Array but for some reason I am convinced it should have in addition to its default state a colour. If it were possible to do something like

type ColoredArray <<: Array
    c::Color
end

then my ColoredArray can be fed to all existing functions that take an Array. I do not have to look up what makes a type compliant with the informal Array concept. Moreover, if tomorrow the Array concept is enriched, my type will automatically benefit from these enhancements.

On the other hand, if I would build

type ColoredArray
    base::Array
    c::Color
end

I would have to delegate all Array API calls to the member field of this composite. Not only would I have to carefully study this API, I am responsible to keep it up-to-date. In addition, if I decide I want FlavoredArray and SmellyArray I would have to copy this a number of times (I guess in this case I can create an abstract type AugmentedArray and define delegation on that level, but still…).

Using macros doesn’t solve all of these problems because even though they might insert all fields of a different struct, they do not fit in my new type at the correct place of the type graph. The problem is that the designed of the standard Array should provide hooks for this kind of extension. If they do not anticipate me wanting to build on top of their work I will find myself at a dead end.


#26

as i understand it, your problem boils down to the informality of the “interface” concept in Julia. in this case, you want the new object to delegate the “array interface” to the base member, but this collection of methods only exists as a concept or documentation page, not as a language construct. that said, usually these interfaces are 5-10 methods, so it is not that big of a deal. some metaprogramming can simplify that further, if you have many types.


#27

I appreciate the effort, but I don’t think (and many with me as evidenced by e.g. this topic) this is a satisfactory solution. It is of linear complexity in the API size, as opposed to constant complexity for traditional structure based inheritance, and it does not solve the fragility issue (augmented or modified APIs are not automatically picked up).

Would the issue not be solved if for every composite type the compiler would generate an associated anonymous abstract parent type and that inheritance from a composite would imply inclusion of its field and inheritance from the implied anonymous abstract type?

So, if I write:

immutable Base
  x::Int
end

this would be lowered to

abstract AbstractBase
immutable Base <: AbstractBase
  x::Int
end

and when I write

immutable Derived <: Base
  y::Int
end

this is taken to mean

abstract AbstractDerived <: AbstractBase
immutable Derived <: AbstractDerived
  @includefieldsfrom Base
  y::Int
end

Then if a function

f(obj::Base) = @show obj.x

is lowered to

f(obj::AbstractBase) = @show obj.x

it will also match objects of type Derived.

I feel these issues stem from the fact that types can either signify data layout or dispatch behaviour and that most programming languages including Julia mix up the two.


#28

If there should be shared data layout between two objects of distinct concrete types, then that shared data layout should be factored out into an object. I feel that the behavior of inheriting data layout from a supertype is mixing up two distinct things that should be orthogonal: subtyping and data layout.

For example, here’s the classic rectangle-square example:

abstract type AbstractRectangle end
struct Rectangle <: AbstractRectangle
    width::Float64
    height::Float64
end

struct Square <: AbstractRectangle
    width::Float64
end

width(r::Rectangle) = r.width
height(r::Rectangle) = r.height

width(s::Square) = s.width
width(s::Square) = s.height

If this were written with Square <: Rectangle, then Square would have two unnecessary width and height fields.

Now suppose all shapes have some common data, like a name, fill color, and outline color. Then this should be done through composition:

struct ShapeData
    name::String
    stroke::Color
    fill::Color
end
name(sd::ShapeData) = sd.name
stroke(sd::ShapeData) = sd.stroke
fill(sd::ShapeData) = sd.fill

abstract type AbstractRectangle end

name(r::AbstractRectangle) = name(shapedata(r))
stroke(r::AbstractRectangle) = stroke(shapedata(r))
fill(r::AbstractRectangle) = fill(shapedata(r))

struct Rectangle <: AbstractRectangle
    shapedata::ShapeData
    width::Float64
    height::Float64
end

struct Square <: AbstractRectangle
    shapedata::ShapeData
    width::Float64
end

width(r::Rectangle) = r.width
height(r::Rectangle) = r.height
shapedata(r::Rectangle) = r.shapedata

width(s::Square) = s.width
width(s::Square) = s.height
shapedata(s::Square) = s.shapedata

This is better because other kinds of objects can use and work with ShapeData objects directly, instead of only as a collection of fields on AbstractRectangle objects. Furthermore, a new subtype of AbstractRectangle can choose to implement the stroke, fill, and name methods in a special manner, bypassing the ShapeData objects.


#29

I would say that the Julia type system is nearly optimal for scientific software. The problem with object-oriented programming for scientific software as embodied by C++ with its inherited data fields is that it leads developers to lock into certain solutions too early. The idea of “types” in scientific computation does not map well onto the C++ notions of inheritance. To give an example from my own experience with scientific projects, suppose that a developer proposes a Matrix class in C++ that supports operations like A(i,j), etc. Then a month later, the developer is asked to implement a derived class from the base class Matrix for symmetric matrices (or banded matrices or sparse matrices or…). Unless the original class was coded in a very specific way, it is unlikely to be extensible to some specific kind of matrix and will have to be rewritten from scratch.

I am perhaps walking on eggshells here, but I would claim that the ability to code in Matlab has advanced the field of scientific software much further than the ability to code with object-oriented programming. Julia attempts to maintain the flexibility of Matlab and yet provide a smart underlying type system so that high performance is possible.


#30

You are correct, but AFAIK the issue is more general and the arguments in favor of composition over inheritance apply equally well outside scientific software.


#31

Thank you for this. I understand this reasoning, and I can appreciate how in theory it solves the problem of API fragility. I also agree with your statement on orthogonality of type and layout.

However, the issue with the motivating example remains. For your approach to work, the author of Array should have defined

abstract AbstractArray
arraydata(x::AbstractArray) = x.arraydata

immutable Array <: AbstractArray
  arraydata
end

so that I can define an augmented version by

immutable ColoredArray <: AbstractArray
  arraydata
  color
end

The good thing is that if the maintainer of Array keeps delegation up to date, I can still compute det(colored_array), colored_array[1,1], …

The bad thing is that this is not what most Array implementations look like. In other words, if the original library author does not foresee that his types might be augmented this is not an option.

I also tried this approach

immutable ColoredArray{T,N}
    array::Array{T,N}
    color
end

convert{T,N}(::Type{Array{T,N}}, x::ColoredArray{T,N}) = x.array
ca = ColoredArray(rand(2,2),"red")

det(ca)

This fails because conversion (apart from during construction) is not called automatically in Julia.


#32

As someone pointed out, there are two separate issues here: (1) inheriting the fields of a “parent” struct, and (2) inheriting the methods of one or more “parent” types. Ignoring the first, how about this as a solution to the second:

Lets say that I want to create a Child type that inherits from a Parent type (written by somebody else). I would then construct the type as usual (possibly including Parent or all or some of its fields). Then I’d write a convert(::Type{Parent}, x::Child) method, possibly some promotion methods, and of course the methods that make my Child type useful and distinct from Parent. Finally I would do:

@inherit_methods Parent Child

The @inherit_methods macro would iterate over methodswith(Parent), check which ones are already covered by methods for Child, promotion rules, etc, and for the remaining ones create methods that take inputs of type Child, convert them to Parent and call that method.

I might also want to do things like

@inherit_methods AbstractArray{Parent} AbstractArray{Child}

or there might be a super-macro that does derived types automatically as well.

Multiple inheritance will be straightforward as long as the Child type knows how to convert itself into each parent. The order of precedence will be determined by the order in which the @inherit_methods calls are done.

If @inherit_methods becomes too popular and the dispatch table grows too large as a consequence, then special measures could be applied to avoid storing all the methods created by the macro, but I doubt that this would be necessary.

A drawback of this approach is that all Child methods must be created before calling @inherit_methods, or there might be lots of warnings about overwritten methods. This makes it hard for third parties to extend Child. A work-around might be to instead auto-create methods for an abstract type that Child is a subtype of.


#33

In the past I’ve proposed an extended version of @forward that knows about method sets. For example:

@protocol type IFoo
  foo(_)
  convert(::Type, _)
end

@forward MyType.field IFoo
# expands to
foo(x::MyType) = foo(x.field)
convert(t::Type, x::MyType) = convert(t, x.field)

This wouldn’t be too hard to implement without language support and, I think, solves the mentioned problems (and can be extended to solve others).

Part of the issue here is that interfaces aren’t always well defined, and that’s often a useful feature. You could define an array as something that support size and indexing, for example, but that doesn’t fit for Dagger arrays where map and reduce are fundamental, and indexing doesn’t make sense. Equally, an array type that stores its own sum would have sum as a primitive. In Julia interfaces are effectively layered, which is powerful but makes these things more messy.

A nice property of the above approach is that it decouples interfaces from types; you could have multiple overlapping interfaces for the same type, and grab the index-based-array or mapreduce-based-array interfaces as necessary.


#34

I think that’s fundamental - you should be able to implement multiple interfaces for a type.
Do you have those macros implemented somewhere? That does seem useful.


#35

Having a single type satisfy multiple interfaces is of course a crucial feature. The more interesting property that this gives you is that you can choose how you satisfy a given interface. For example, you can choose to implement an AbstractArray by forwarding a set of scalar operations (getindex, setindex!), or a set of vector operations (map, reduce) – each would be a separate protocol.

In classic OO, subtyping Array would force you to choose whatever Array had chosen as primitive (usually scalar ops).

I don’t have code up for this but it’s a reasonably simple macro to code up, for someone who cares about the problem (I’ve found the simpler @forward to be enough for my needs).


#36

I think it is still possible to do something similar to your example. You can define e.g. a Composeable array type as a subtype of AbstractArray and assume that all members have a data field. Then you know how to forward getindex, setindex! etc. and the following works:

# Define composeable type once
abstract type ComposableArray{T,N} <: AbstractArray{T,N} end
Base.getindex(a::ComposableArray,i...)=getindex(a.data,i...) 
Base.setindex!(a::ComposableArray,x,i...)=setindex!(a.data,x,i...)
Base.size(a::ComposableArray)=size(a.data)
Base.eltype{T}(a::ComposableArray{T})=T
Base.similar(a::ComposableArray)=similar(a.data)

# Now a concrete subtype
struct ColoredArray{T,N,C} <: ComposableArray{T,N} 
    data::Array{T,N}
    color::C
end

a=ColoredArray(rand(10,10),"blue")

#And we get all AbstractArray behavior for free
det(a)
a*rand(10,30)
a[:,2]
a[3,:]=5

#37

Hehe, some of us don’t have either your or @totalverb’s macro fu superpowers :smile:


#38

But in oo, one can just leave the base class to be more abstract and put scalar ops in a subclass.

Also, i assume dagger arrays can’t implement iteration since requires map/reduce…so they really shouldn’t be abstract arrays, right?


#39

This example is a decorator pattern (name borrowed from OO), which is handled by implementing the interface for AbstractArray, and delegating each interface function. For well-designed interfaces, this should be a minimal number of functions, as there should be generic code to handle other functions. For example

immutable ColoredArray{T,N} <: AbstractArray{T, N}
    array::Array{T,N}
    color
end

# AbstractArray interface
Base.size(A::ColoredArray) = size(A.array)
@compat Compat.IndexStyle(::Type{<:ColoredArray}) = Compat.IndexStyle(Array)
Base.getindex(A::ColoredArray, i::Int) = A.array[i]

# then
ca = ColoredArray(rand(2,2),"red")

det(ca)

#40

I couldn’t agree more.