Thinking about it some more, the big problem with covariance is that it
forces the confusion of two distinct meanings of P{B} for abstract B:
1. The concrete instance of type P with actual parameter type B.
2. The abstract type including all instances P{A} where A <: B.
If P{B} meant the latter, then we would either need a new way to express
the former or we would be forced to identify the two. Unlike static
languages, the concrete interpretation is not just a hallucination of the
compiler – it exists at run-time – so we can't just have no name for it –
there needs to be some concrete answer when you write typeof(x).
Identifying the two meanings is very un-Julian as it would allow a concrete
type to have subtypes, which would be a massive and to my mind distasteful
change.
On Tue, Apr 29, 2014 at 11:51 AM, Stefan Karpinski <ste...@karpinski.org>wrote:
> The real root issue here is parametric
> variance<https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)>.
> Julia has opted for parametric invariance – i.e. that P{A} <: P{B} only if
> A = B – which is what James mentions in his StackOverflow answer. The
> wikipedia page does a decent job of summarizing the issue:
>
> A programming language designer will consider variance when devising
>> typing rules for e.g. arrays, inheritance, and generic datatypes. By making
>> type constructors covariant or contravariant instead of invariant, more
>> programs will be accepted as well-typed. On the other hand, programmers
>> often find contravariance unintuitive, and accurately tracking variance to
>> avoid runtime type errors can lead to complex typing rules. In order to
>> keep the type system simple and allow useful programs, a language may treat
>> a type constructor as invariant even if it would be safe to consider it
>> variant, or treat it as covariant even when that can violate type safety.
>
>
> Julia has chosen the simple approach of invariance everywhere. This
> simplifies the subtyping rules, but there is no free lunch – variance
> issues still do crop up. But at least Julia's rules are simple if
> occasionally a bit inconvenient. Basically, this is the situation:
>
> - *covariance:* *P{A} <: P{B} ⟺ A <: B* – correct for read, incorrect
> for write.
> - *contravariance:* *P{A} <: P{B} ⟺ B <: A* – correct for write,
> incorrect for read.
> - *invariance:* *P{A} <: P{B} ⟺ A = B* – correct for both read and
> write.
>
> The main purpose of variance in a programming language is to allow
> definitions to apply to more things. In particular, since the number of
> types that a parametric type may encompass is unbounded, you don't want to
> have to write an infinite number of method definitions to define some
> functionality for P{A} for all A <: B where B is some unbounded abstract
> type. Instead of accomplishing this with covariance or contravariance,
> Julia accomplishes it with more powerful dispatch – specifically, method
> signatures with quantified type parameters, such as:
>
> frob{A<:B}(x::P{A})
>
>
> This is effectively a covariant signature, applying to P{A} for any A <:
> B. It seems like you would be happier if parametric types were covariant
> and you were allowed to write this as:
>
> frob(x::P{B})
>
>
> where the method implicitly also applies to x::P{A} for every A <: B. This
> would certainly be less of an eyesore. There are a couple of important
> points to be made, however:
>
> 1. In the longer, more explicit form, it is clear that B may not be
> the actual parameter type of x; the parameter type of x is some A which is
> a subtype of B.
> 2. If the shorter form were shorthand for the longer form without
> explicit A, there would be no way to express that x has an
> exact parameter type of B.
>
> The explicit distinction between A – the actual parameter type of x – and
> B, which is simply an upper bound on A, becomes clearer in situations like
> this:
>
> frob{A<:B}(x::P{A}, y::A)
> frob{A<:B}(x::P{A}, y::B)
>
>
> The first definition only applies to x and y where y is of the actual
> parameter type of x and thus could be used as is by x. The second
> definition applies when y is of type B, regardless of x's actual parameter
> type, which means that it might not be usable as is by x.
>
> We could actually make parametric types covariant without losing the
> ability to express this distinction; it would just mean that the second
> definition could be written as:
>
> frob(x::P{B}, y::B)
>
>
> Currently, this means that x must have exact parameter type B; if types
> were covariant then it would mean that x's parameter type could be any A <:
> B. Although it may seem questionable that y not be of the true parameter
> type of x, allowing this wiggle room and then doing conversion at run-time
> as necessary is actually the standard way to do things in Julia. Conversion
> is often done implicitly by assignment to a type location such as a field
> of x or an array slot. The fact that this is quite common is why covariance
> might actually be ok. The main thing we would lose with parametric
> covariance is the ability to talk about arrays that are of *exactly*
> element type B where B is some abstract type. But I'm just not sure how
> useful that actually is. Those types are generally discouraged in any case
> and it's rare to want to give them special behaviors that wouldn't also
> apply to parametric types with concrete parameters. So perhaps we ought to
> consider making parametric types in Julia covariant.
>
> On Tue, Apr 29, 2014 at 5:38 AM, Oliver Woodford <
> oliver.woodf...@gmail.com> wrote:
>
>> A habitual MATLAB user, I've been trying out Julia over the last two
>> weeks to see if it might be a suitable replacement. I want something that
>> is as fast to develop using, but has much faster runtime. Perhaps I'll
>> write about my general thoughts in another post. However, in this thread I
>> want to address one linguistic thing I found confusing.
>>
>> Ignoring subarrays, dense/sparse arrays, there are two main types of
>> array in Julia. I will call them homogenous and heterogenous. Homogenous
>> arrays are declared as having all elements be the same type: e.g.
>> array{Float64}. They are efficient to store in memory, as the elements are
>> simply laid out consecutively in memory. Heterogenous arrays have an
>> abstract element type, e.g. array{Real}. The way Julia interprets this is
>> that every element must be a concrete subtype of Real, but that they don't
>> have to be the same type. Each element can therefore be a different type,
>> with different storage requirements, so these arrays contain a pointer to
>> each element, which is then stored somewhere else - this carries a massive
>> overhead. In MATLAB these arrays would be termed an array and a cell array
>> respectively, so there is a clear distinction. What I found confusing with
>> Julia is that the distinction is less clear.
>>
>> This confusion was highlighted in a stackoverflow
>> question<http://stackoverflow.com/questions/23326848/julia-arrays-with-abstract-parameters-cause-errors-but-variables-with-abstract>,
>> which I'll outline it again, now:
>>
>> f(x::Real) = x is equivalent to f{T<:Real}(x::T) = x, but f(x::Array{Real})
>> = x is different from f{T<:Real}(x::Array{T}) = x.
>>
>> The second form for input arrays, requiring static parameters, is needed
>> to declare that the array is homogenous, not heterogenous. This seems a
>> funny way of doing things to me because:
>> 1. The homogeneity/heterogeneity of the array is a characteristic of the
>> array only, and not of the function
>> 2. The static parameter T is not required anywhere else, and the Julia
>> style
>> guide<http://julia.readthedocs.org/en/latest/manual/style-guide/#don-t-use-unnecessary-static-parameters>
>> explicitly
>> counsels against the use of such parameters, where they are unnecessary.
>> 3. To declare a function which can take homogenous or heterogenous
>> arrays, I believe you'd have to do something like
>> f{T<:Real}(x::Union(Array{T},
>> Array{Real})) = x, which seems totally bizarre (due to point 1).
>>
>> What I would advocate instead is two types of array, one homogenous, one
>> heterogenous. Array for homogenous and Cell for heterogenous would work.
>> It would do away with the need for static parameters in this case, and
>> also, in my view, make people far more aware of when they are using the
>> different types of array. I suspect many beginners are oblivious to the
>> distinction, currently.
>>
>> In the stackoverflow question, someone suggested two points against this:
>> 1. Having an array whose elements are all guaranteed to be some subtype
>> of Real is not particularly useful without specifying which subtype since
>> without that information almost no structural information is being provided
>> to the compiler (e.g. about memory layout, etc.)
>> Well, firstly I disagree; there is a lot of structural information being
>> supplied - to read each element, the compiler knows that it just needs to
>> compute an offset, rather than compute an offset, read a pointer and then
>> read another memory location. However, I don't think this is exploited
>> (though it could be) because the function will be recompiled from scratch
>> for each element type. Secondly, this isn't about helping the compiler,
>> it's about making the language more consistent and sensible - helping the
>> *user*.
>> 2. You almost always pass homogenous arrays of a concrete type as
>> arguments anyway and the compiler is able to specialize on that.
>> Firstly, homogenous arrays that you pass in *always *have a concrete
>> type. Secondly, you don't always know what that type will be. It might be
>> Float64 or Unit8, etc.
>>
>> I haven't yet heard a convincing counterargument to it making more sense
>> to distinguish homogenous and heterogenous arrays by the array type rather
>> than by static function parameter.
>>
>> Let the discussion begin...
>>
>
>
