Invariant Tuples

[martinholters]

A radical idea that came up in #24166 and on slack: Make Tuple invariant in its parameters.

Pro:

• Makes Tuples less special/magical.
• (Hopefully) reduces special cases in subtyping code.
• Allows abandoning the "diagonal rule" that is useful is dispatch, but nasty in code working with (especially widening) types, ref bug in type widening #24582.
• Would allow for e.g. Tuple{Union{Int,Missing}, Union{Int,Missing}} to be concrete. (Added based on comment below.)
• ...

Con:

• Probably huge effort, needs to be well justified.
• ...

(Hoping to stir up a discussion that adds to these lists.)

Of course the current covariant behavior is useful more often than not, but the new InvariantTuple (for the sake of discussion) could be use to express it: Tuple{Number,Any} would become Tuple{<:Number, <:Any}. The diagonal rule would be trivial: Tuple{T,T} where T would become InvariantTuple{T,T} where T (but T would no longer be confined to concrete types), while Tuple{T,T,Ref{T}} where T (N.B. diagonal rule does not apply!) would become InvariantTuple{<:T,<:T,<:Ref{T}} where T.

Handling Varargs needs more thought: Tuple{Vararg{Any}} would need to be interpreted as InvariantTuple{<:Any,<:Any,...} while Tuple{Vararg{T}} where T would need to be interpreted as InvariantTuple{T,T,...} where T. Hence we would need two different syntaxes for InvariantTuple{Vararg} to distinguish these cases. Maybe InvariantTuple{Vararg{T} where T} for Tuple{Vararg{Any}} vs. InvariantTuple{Vararg{T}} where T for Tuple{Vararg{T}} where T?

I have no idea whether we actually want to go down this road eventually, but I feel like it at least deserves discussion. (CC @andyferris)

[JeffBezanson]

Another potential advantage is that Tuple{Union{Int,Missing}, Union{Int,Missing}}would be a concrete type, which is currently thought to make it easier to handle missing data.

[martinholters]

Hm, currently

julia> typeintersect(Tuple{T, Ref, T} where T, Tuple{T, Ref{T}, T} where T)
Tuple{T,Ref{T1},T} where T1 where T

which doesn't seem quite right. If I translate this to typeintersect(InvariantTuple{T, <:Ref, T} where T, InvariantTuple{<:T, <:Ref{T}, <:T} where T), I think the answer should be InvariantTuple{T, <:Ref{T}, T} where T *) which I don't think we can represent using our current Tuples. Is that so? That would be another good reason pro this change.

*) Incidentally, if I just define abstract type InvariantTuple{T1,T2,T3} end for this experiment, then

julia> typeintersect(InvariantTuple{T, <:Ref, T} where T, InvariantTuple{<:T, <:Ref{T}, <:T} where T)
InvariantTuple{T,#s11,T} where #s11<:Ref where T

which is also not quite correct...

[martinholters]

Tuple{Union{Int,Missing}, Union{Int,Missing}} would be a concrete type

It could be a concrete type. Or we still impose the restriction that only Tuples with all fields concrete types can have instances. No idea whether that has any advantages, but it would be possible.

[andyferris]

@JeffBezanson yes, missing was part of my thinking on this one.

[StefanKarpinski]

I guess part of this thinking would be that the type of a method signature, e.g. f(a::A, b::B) would become Tuple{<:A, <:B} rather than just Tuple{A, B} in order to compensate for the invariance of tuple types? Otherwise this would completely wreak havoc on dispatch in a way that seems totally beyond the pale. But it does seems nice that all parametric types by invariant rather than having this one special case in the system. This would also not be that hard to fix since you would mostly just translate Tuple{A, B} to Tuple{<:A, <:B}.

[martinholters]

I guess part of this thinking would be that the type of a method signature, e.g. f(a::A, b::B) would become Tuple{<:A, <:B}

Yes. Although some way of opting in to it actually becoming Tuple{A, B} might also be useful, if you e.g. want to restrict T to a concrete type in f(x::T, y::T, z::Ref{T}) (i.e. so that x and y are ensured to be of the same type).

[StefanKarpinski]

I would imagine that the diagonal rule would still apply (although not in that case). Whatever the diagonal rule is expressed in terms of could perhaps be used explicitly for that behavior in that case.

[andyferris]

Yes, the signature for f(x::T1, y::T2) would be Tuple{::A, ::B) where {A <: T1, B <: T2}. Diagonal dispatch f(x::T, y::T) where T would still be a Tuple{T, T} where T <: ....

Usage of tuple(a, b) and f(a, b) would require using the Julia bindings a and b, which each have a concrete type (all bindings have a concrete type). To construct a tuple of abstract types, we could maybe use the Tuple constructor (perhaps like Tuple{Integer}(1)) and to invoke a function using abstract argument types we already have invoke, which dovetails pretty nicely here.

To me, it's interesting to note that the new type system is powerful enough that we no longer need covariant tuples to describe how dispatch behaves! :) The question then becomes: what do we actually gain from covariance at all?

[andyferris]

Also - I hope I'm not wrong, but I vaguely remember a comment once discussing that ccall uses a signature which is more like a list of types such as (Integer, Integer) than an actual Julia Tuple. I think this may remove any distinction?

[andyferris]

Finally, at JuliaCon it seemed uncertain even if we thought that suitable algorithms things like accurate type intersection for a multiple inheritance type system even exist - I would guess that simplifying the type system might help with forward progress (I'm hardly an expert but it seems logical). I suspect this might be a pretty large simplification of the existing subtyping algorithm, and will be easier for users to grasp.

[StefanKarpinski]

The more I think about this idea, the more I like it. I would make a couple of observations:

• It would be more correctly described as "invariant tuple types" – nothing actually changes about tuple values, not their syntax or their type since they are already concrete.

• It doesn't change dispatch at all either. What it would change is how you write the signature type of methods with abstract argument types, but methods would continue to have the same type.

• It's strictly more expressive: every tuple type that can currently be written can still be written, but many types that cannot currently be written would be expressible.

• It makes "invariant position" versus "covariant position" for type vars completely explicit: if T appears as P{<:T} that's covariant position; if it appears as P{T} that's invariant position.

• It unifies the way all of Julia's parametric types work.

I also don't think the deprecation process would be too bad: people don't write tuple types all that much and we can deprecate abstract parameters without <: in front of them in Tuple. Then in 1.0 we can re-allow the <:-less syntax with invariant meaning.

[mauro3]

A wrinkle would be -- if @andyferris's observation is right:

Yes, the signature for f(x::T1, y::T2) would be Tuple{::A, ::B) where {A <: T1, B <: T2}. Diagonal dispatch f(x::T, y::T) where T would still be a Tuple{T, T} where T <: ....

-- that the (mental) translation of a type signature to a tuple type gets complicated. Now the translation is easy:
f(x::T1, y::T2, z::T2) where T2 -> Tuple{T1, T2, T2} where T2 versus with this change:
f(x::T1, y::T2, z::T2) where T2 -> Tuple{A, T2, T2} where {A<:T1, T2}.

[rfourquet]

I don't understand enough this topic to be sure that this is related (apologies for the noise if it's not), but I wanted to raise a point about the way tuples work just in case it could be addressed in a tuple overhaul. The problem is related to how types are handled as function arguments: to get type-stable code, we often write a type signature with ::Type{T}. For example you can have f(x) = ...; f(::Type{Int}) = .... But this doesn't work if the arguments of f are wrapped in a tuple: f(x::Tuple{Int}) = ... is fine but f(Tuple{Type{Int}}) fails when called as f((Int,)): ERROR: MethodError: no method matching f(::Tuple{DataType}). Now if the type of Int (resp. (Int,)) could be modified to Type{Int} (resp. Tuple{Type{Int}}), then then call f((Int,)) would work, and together with tuple covariance, the call g((Int,)) would also work where g(::Tuple{DataType}). I can give (if asked) a motivating example for why this behavior can be useful (it would help me a lot while I try to extend the rand API).