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...
>
