Feature request: Add syntactic sugar for covariant actual type parameters

[toivoh]

As per discussion in https://groups.google.com/forum/#!topic/julia-users/alavN8tRdyI :
Let e.g.

Array{<:Real}

act like RArray given by

typealias RArray{T<:Real} Array{T}

This convenient shortcut should go a long way in those cases where people would want covariant types.

The type parameter of Array{<:Real} might become anonymous or hidden; it probably doesn't matter so much since you would rarely re-provide it, e.g. Array{<:Real}{Int}.

[simonbyrne]

I agree something like this is necessary. This could also be addressed by triangular dispatch (#3766).

[toivoh]

The main motivation is to avoid having to explicitly parametrize methods in many cases (and also avoid having to create a lot of type aliases). Like

f(a::Array{<:Real}, b::Array{<:Real}) = a+b

instead of

f{s<:Real,T<:Real}(a::Array{S}, b::Array{T}) = a+b

or

typealias RArray{T<:Real} Array{T}
f(a::RArray, b::RArray) = a+b

How would triangular dispatch help in this case? Or are you thinking about some other kind of case?

[simonbyrne]

Ah, I see your point.

I was thinking of occasions where you have two or more nested types:

immutable Foo{S <: AbstractArray}
   data::S
end

and then I want to dispatch on real arrays. At the moment, I don't think it's possible to dispatch directly. You could define

typealias RArray{T<:Real} Array{T}

bar{S<:RArray}(a::Foo{S}) = ...

Alternatively, if we had triangular dispatch

bar{T<:Real,S<:Array{T}}(a::Foo{S}) = ...

or, with your proposal

bar(a::Foo{<:Array{<:Real}}) = ...

[toivoh]

Ok, that should be useful way to use this idea as well.

[lindahua]

+1

This makes a lot of function declarations more concise.

[JeffBezanson]

+1 I would like to have this.

I believe a bit of theoretical work is needed to figure out what <:Real actually is. Is it a type? Does it make sense to write isa(x, <:Real)? Is there an implied "forall" quantifier somewhere, and if so, where does it go in T{S{R{<:Real}}}? How does it relate to partially-specialized types like Array and Array{Int}? And so on.

[StefanKarpinski]

Given the current semantics of covariant parametric types, I agree that this is really useful – but, as @JeffBezanson points out, not entirely clear yet. Basically, it allows you to write the covariant parametric type as Array{<:Real} while Array{Real} is an invariant parametric type. Note also, that Array{<:Real} is abstract, while Array{Real} is concrete. But since Array{<:Real} is the more common case, it makes me wonder if it wouldn't be better for Array{Real} to be how you write the abstract, covariant parametric type and have a less convenient syntax for the concrete, invariant parametric type. Something like Array{=Real} or even Array[Real]. This wouldn't be backwards compatible, but I suspect that switching to covariant parametric types would be surprisingly non-disruptive.

[toivoh]

function foo(x::Vector{Real}) end works, it just requires an argument of type Vector{Real} (which is a concrete type, you can create one with e.g. Real[1, 2.5]). I think that the question is more about what you commonly want (in this case, most likely the covariant type).

[lindahua]

@sunetos Int is a subtype of Real, so your first foo works as expected. However, both Vector{Int} and Vector{Real} are concrete types, and neither is a subtype of the other, so the second foo doesn't work as you expect. I don't see any inconsistency here. I agree that this behavior may surprise some people though.

When parametric types are involved, things are more complicated. Making parametric types covariant by default may introduce other subtle problems.

[johnmyleswhite]

@sunetos, I find it frustrating when you speak on behalf of all "newcomers". Could you please stick to claims about your own beliefs rather than making assertions about the beliefs of all people? You don't represent me and I find it quite upsetting when you assert that you do.

[johnmyleswhite]

Please don't bow out. Your opinion is really valuable. I spoke up because I think it's important to keep in mind that none of us actually know how the modal newcomer will behave since we've never run any experiments. Right now, we're all just speaking from strong personal beliefs.

[lindahua]

@sunetos I am sympathetic to the proposal of having parametric types covariant by default, and believe that it may substantially improve the experience of many users.

However, changing the default behavior from invariant to covariant is a major change to the language, which may potentially complicate type inference and method resolution. This needs extensive discussion.

[quinnj]

FWIW, I remember bumping into the "Array{Real} is a concrete type" issue at some point and having to take a while to realize what was going on (I may have even posted in julia-users about it). So, like @sunetos, this was something I didn't understand at first. I think making Array{Real} covariant by default would be sensible and probably not too disruptive.

-Jacob

[nalimilan]

I also found quite unintuitive the current Array{T} behavior at first, though now I understand why it works that way. I think defaulting to covariant behavior may well reduce entry costs and the questions from newcomers on the mailing list (even if as @johnmyleswhite said it's always pretty hard to know this population in advance), without creating real problems in practice. Cases where you do not want this behavior are probably quite rare and would only affect people with advanced understanding of Julia.

[JeffBezanson]

I see the arguments in favor of covariance, but you do trade one surprise for another:

function f(x::Vector{Real})
    x[1] = 1.5
    ...

That code does not work for all arguments.

Another "new surprise" is that Array(Any, n) has to give an Array{=Any,1}, and you'd have to learn to insert the = when reasoning about the result type of the Array constructor.

[lindahua]

@JeffBezanson's argument is spot on.

When you want to input an array, you probably feel that covariance makes things convenient. However, when you want to supply a collection to receive output results, covariance is probably not what you want (you may like contravariance here)

[JeffBezanson]

I also find I have a psychological bias regarding numeric arrays --- it is very tempting to think of a Vector{Int} as a kind of "vector of real numbers". However in other domains you might commonly have a Vector{AbstractGraph}, where subtypes like Vector{EmptyGraph} are mostly useless.

[sunetos]

I didn't understand that example. In languages with concrete type inheritance, polymorphism, etc., you would specify the type that has something akin to the "least common denominator" of required behaviors. So if your function tried to do something that would only work on floats (like the example of assigning 1.5), then you would specify the argument as ::Vector{FloatingPoint}, not ::Vector{Real}, because clearly the function requires floats. If the function is generic enough to never require floats, but would work with any numeric type, then you would use ::Vector{Real} or ::Vector{Number}.

[lindahua]

Let's consider an example outside numerical computation:

# an action can operate on any instance of type T
type Action{T}  ... end
apply_action{T}(act::Action{T}, x::T) = ...

function apply_action(A::Vector{Float64}, act::Action{Float64})
    for x in A
        apply_action(act, x)
    end
end

In this case, we do wish to have contravariant behavior, which allows that we supply instances of Action{Real} or Action{Any}, which can also operate on float64 numbers.

It is true when we consider arrays, covariance might feel convenient. However, there are plenty of cases where the opposite behavior, namely contravariance, is preferred.

C# is a language that puts a lot of thoughts in this issues, which allows to specify whether each type parameter is covariant, invariant, or contravariant.

(see http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science))

[JeffBezanson]

The point of the example is that writing to arrays asks for contravariance, in which case you need to explain to people why you have to write Vector{FloatingPoint} instead of Vector{Real}. No one choice is "obviously intuitive to all beginners".

[lindahua]

In spite of the debate about default behaviors, I think it is useful to provide syntactic sugar for people to express covariance when they need it.

My feeling is that Array{<:Real} is a good way to go, where <: indicates covariance, and the part <:Real should not be considered as a standalone type. The type Array{<:Real} should be considered as abstract, and we have Array{T} <: Array{<:Real} whenever T <: Real.

[toivoh]

Ok, then I see what you mean.

[JeffBezanson]

Yes, I think what @lindahua described would be a good way forward.

[JeffBezanson]

Also extends to Array{>:Float64} for contravariance of course.

[JeffBezanson]

The bad news is that this is closer to being incompatible with the idea of default type parameters. But the good news is that #1470, adding a construct function for constructors, will allow defining constructors for partial types, so you could define a constructor for Dict{K,V} that inserts a third type parameter. I think this will resolve the issue satisfactorily.

[SimonDanisch]

I got to this topic, as I need things like this nearly everywhere in my code.

It might not be very constructive what I've to say, but this is one of the most important features in Julia, so I think it's extremely important that there are several iterations for the syntax to make all people feel comfortable with it.

As much as I like JeffBezanson's proposal, I didn't grasp the syntax right away.
It reminded me of my first horrors with Scala, as they make it incredibly easy to disguise the type of an argument and make things nearly unreadable. (Horrors I never had with Julia)
I must admit, that I don't have a killer proposal, as JeffBezanson's proposal is already pretty damn fine.
But I'll try to verbalize my unconscious rejection of the proposed syntax.

• First problem:
  • I think one parses a type top down, meaning, one would like to start with MyType, and then get to know the parameters, and parameters of parameters.
• Second:
  • To many Curly Braces and other symbols in one line.
• Third:
  • It's not really perceived as one item, but rather as a chain of items.
    This is confusing, as you're defining only one item, namely the type.

Some proposals I quickly came up with:

# As a reference, the original proposal
::{T<:Real}->{A<:AbstractVector{T}} -> MyType{T,A}

# Leaving away curly braces and wrapping everything in brackets, to make it feel more like a type
::(T<:Real -> A<:AbstractVector{T} -> MyType{T,A})

# Introducing new parameters on the fly. (Maybe not easy to parse, or ambiguous?)
# Also you could define ambiguous parameters, with more than one type.
::MyType{T<:Real, A <: AbstractVector{T}}, ::SecondType{T, F <: FloatingPoint}

# That's already it (Maybe I can come up with more) 
# To compare them better visually, here are all of them side by side:
::{T<:Real} -> {A <: AbstractVector{T}} -> MyType{T,A}
::(T<:Real -> A <: AbstractVector{T} -> MyType{T,A})
::MyType{T <: Real, A <: AbstractVector{T}}

The first thing that I notice is, that putting MyType in the first place is a lot easier on the eye, as you immediately know the type everything is about, which helps to put things into context....

[JeffBezanson]

I hear you on the excessive amount of punctuation. However one problem we
really need to solve is clarifying what parts of a type parameters are
bound in. I agree starting with the type name is easier to read, but as far
as I can tell this makes it impossible to solve this problem. We could have
some rule about how far "out" type variables apply, but in more complex
cases this would be even harder to understand.

[oxinabox]

~2 years later, what are the thoughts on this now?
(Given as @IainNZ points out, I just made a duplicate proposal: #16086)

[StefanKarpinski]

Still wanted. Part of the type revamp issue: #8974

[stevengj]

+1 for just supporting f(x::Vector{<:Real}) and similar simple non-nested cases and punting on everything else. All of the -> proposals seem like a cure worse than the disease here.

We don't need a sugar that covers all possible cases, since in more complicated cases you can always fall back onto the current syntax f{T<:Real}(x::Vector{T}) or define a typealias.

[stevengj]

Should this be added to the 1.0 milestone?

[stevengj]

With the new where syntax, Array{<:Number, 3} can just be sugar for Array{T,3} where T<:Number.

[yuyichao]

Someone might have already mentioned this but I think an issue for this syntax is that it is unclear where the where should be. Array{Array{T where T<:Number,3},3}, Array{Array{T,3} where T<:Number,3}, Array{Array{T,3},3} where T<:Number all have different meanings.

[stevengj]

It seems pretty clear to me that the where should go with the immediately enclosing type. e.g. Array{Array{<:Number,3}} should be Array{Array{T,3} where T<:Number}, surely? Anything else would be a messy context-dependent meaning, no?

You can always use where explicitly if you want something else.

[stevengj]

Just pushed a PR. This is pretty simple to implement given the new where machinery.