Use `StaticInteger`s instead of `Tuple{1,2,3}` in `StaticArray` type parameter?

[tkf]

StaticArray uses Tuple{1,2,3} to encode the size:

https://github.com/JuliaArrays/StaticArrays.jl/blob/cee335d3e7f08dcc72075ac5f18bb3a632e8b841/src/StaticArrays.jl#L73-L76

Arguably, the type parameters of Tuple should be types. Otherwise, such Tuple does not have an instance. It also confuses some users (including me when I first saw this): What does Tuple{3} mean in StaticArrays? - Usage / First steps - JuliaLang.

A better solution may be to use Tuple{StaticInteger{1},StaticInteger{2},StaticInteger{3}} instead of Tuple{1,2,3}. For example, a possible implementation of SArray would be

struct SArray{N, S <: NTuple{N,StaticInteger}, T, L} <: StaticArray{S, T, N}
    data::NTuple{L,T}
    size::S
end

const SVector{S, T} = SArray{1, Tuple{StaticInteger{S}}, T, S}
const SMatrix{S1, S2, T, L} = SArray{2, Tuple{StaticInteger{S1}, StaticInteger{S2}}, T, L}

(Early discussion in https://github.com/JuliaArrays/StaticArrays.jl/issues/806#issuecomment-655279036)

[c42f]

I'll just say: the prospect of removing this hack is extremely exciting, I think this might be just the right thing. It's 2.0 material though.

One difficulty is the syntax for the concrete SArray type which gets even worse than it currently is. Maybe we'll have to work around that with a function which constructs the concrete types. Moving away from concrete type names would also provide a way for libraries to be compatible with both StaticArrays 1.0 and 2.0, and to avoid the need for the user to know about the dimension and storage size parameters. So there's some compensation at least!

[c42f]

It's 2.0 material though.

Or at least, that's my initial reaction; not a foregone conclusion I guess! We haven't released 1.0 yet though, so if there's a smooth transition plan possible perhaps we could consider doing this as part of a big 1.0.

[tkf]

if there's a smooth transition plan

I can't think of an easy way to not break code like f(::SArray{Tuple{1,2,3},Int}) = ... (unless Core.apply_type is a generic function...).

The only idea I can think of ATM for maximally smoothing this out is to let v1 and v2 co-exist.

[c42f]

I can't think of an easy way to not break code like f(::SArray{Tuple{1,2,3},Int}) = ... (unless Core.apply_type is a generic function...).

The point would be to release a transitional version of StaticArrays which didn't change the type signature, but included some "type constructor" functions to work around the fact that apply_type can't be extended. Something like this demo:

julia> Base.@pure SArrayT(T, dims) = SArray{Tuple{dims...}, T, length(dims), prod(dims)}
SArrayT (generic function with 1 method)

julia> f(a::SArrayT(Int, (2,))) = a
f (generic function with 1 method)

Which acts as intended:

julia> f(SA[1,2])
2-element SArray{Tuple{2},Int64,1,2} with indices SOneTo(2):
 1
 2

julia> f(SA[1 2; 3 4])
ERROR: MethodError: no method matching f(::SArray{Tuple{2,2},Int64,2,4})
Closest candidates are:
  f(::SArray{Tuple{2},Int64,1,2}) at REPL[17]:1
Stacktrace:
 [1] top-level scope at REPL[19]:1

Unfortunately there's no way indicate deprecations of type parameters (is there?) The best I can think of would be new names and to deprecate the old bindings. But that seems horribly heavy handed.

[c42f]

Unfortunately there's no way to indicate deprecations of type parameters

Actually I guess in the inner constructors can be used to check the type parameters so there might be some way forward.

[tkf]

I actually thought about something like SArrayT but I thought it wouldn't be enough since you can't support expressions where the types appear in the middle of other types. Like

VectorOfStaticArrays{N} = Vector{<:SArray{S}} where {N, S <: NTuple{N,Any}}
StaticArray3{N1, N2, N3, T} = StaticArray{Tuple{N1, N2, N3}, T, 3}

But maybe those use-cases are not so common?

[c42f]

It's true... I guess once we start trying to work around the system with "type constructor" functions, we're going to be outside the world of normal type constructors and things which should be easy won't work.

Which is really too bad because this proposal does seem like the right thing semantically; it's just bad in surface syntax.

Welp, I guess being a matter of syntax, we're still left with a macro

@SArrayT {(2,2),Int}

But does the macro try to expand to the fully concrete type? That's often what you want, but not always.

[tkf]

Ah yes, macro sounds like a good solution!

By the way, why not just use the existing macro name and implement @SArray{(2,2),Int}?

But does the macro try to expand to the fully concrete type?

You mean when the dimensions are given as literals (or even constants)? Maybe we can provide @SArray{(2,2),Int} and, for computing prod(dims), @SArray{(2,2),Int,_...}?

[martinholters]

Could also decide based on the type of dims and compute prod(dims) if possible. E.g. like

make_sarray_type(dims::NTuple{N,Int}, T) where {N} = SArray{Tuple{dims...}, T, N, prod(dims)}
make_sarray_type(dims::NTuple{N}, T) where {N} = SArray{Tuple{dims...}, T, N}

struct Foo{L}
    x::make_sarray_type((2,2,2), Float64)
    y::make_sarray_type((L,), Float64)
end

Then

julia> fieldtypes(Foo{4})
(SArray{Tuple{2,2,2},Float64,3,8}, SArray{Tuple{4},Float64,1,L} where L)

(And this only sketches the idea, an actual implementation should probably be more careful that the types can not only be computed, but also inferred, and this is not propose an API in any way.)

But this might be too magical, although it feels a bit like constant propagation.

[tkf]

Wow, I didn't know that this "works"!

julia> VectorOfStaticArrays{N} = Vector{<:SArray{@show(S)}} where {S <: NTuple{@show(N),Any}}
N = N
S = S<:Tuple{Vararg{Any,N}}
Vector{var"#s21189"} where var"#s21189"<:(SArray{S<:Tuple{Vararg{Any,N}},T,N,L} where L where N where T) = Array{var"#s21189",1} where var"#s21189"<:(SArray{S,T,N,L} where L where N where T) where S<:Tuple{Vararg{Any,N}} where N

So, I guess it means that we can use functions in the middle of "type expressions" (like the RHS of VectorOfStaticArrays{N}) as long as they can handle TypeVar etc.?

[c42f]

By the way, why not just use the existing macro name and implement @SArray{(2,2),Int}?

Yes with the curly syntax it should be visually distinct enough to indicate that it's a type construction rather than a value.

Actually I didn't know @f{} syntax worked (without the space before the {). It was recently implemented in https://github.com/JuliaLang/julia/pull/34505 so will be in 1.5 I guess.

But this might be too magical, although it feels a bit like constant propagation.

Well SArray type parameters like N and L should ideally not exist, but have to due to practical limitations. So I think it's generally good if users don't need to know about them. It might be too magical if they generally don't need to know about them but there's some surprise cases where they do...

[stev47]

You can actually store the tuples directly as values in type parameters as in

abstract type MyAbstractSArray{T,N,Sz} <: AbstractArray{T,N} end
Base.size(::MyAbstractSArray{<:Any,<:Any,Sz}) where Sz = Sz

struct MySArray{T,N,Sz,L} <: MyAbstractSArray{T,N,Sz}
    data::NTuple{L,T}
    function MySArray{Sz}(a::NTuple{L,T}) where {Sz,L,T}
        L == prod(Sz) || throw(ArgumentError("size mismatch"))
        return new{T,length(Sz),Sz,L}(a)
    end
end
MySArray{Sz}(a::T...) where {Sz,T} = MySArray{Sz}(a)

Base.IndexStyle(::Type{<:MySArray}) = IndexLinear()
Base.getindex(a::MySArray, i::Int) = a.data[i]

you then have

julia> x = MySArray{(2,2)}(1, 2, 3, 4)
2×2 MySArray{Int64,2,(2, 2),4}:
 1  3
 2  4

The size information is still static and the type layout way simpler. Is there something I have overlooked?

[tkf]

Actually that's how current StaticArrays.Size works. But I don't think it's flexible enough to support the patterns discussed in the OP like const StaticVector{N, T} = StaticArray{Tuple{N}, T, 1} (note how N works)?

[stev47]

But I don't think it's flexible enough to support the patterns discussed in the OP like const StaticVector{N, T} = StaticArray{Tuple{N}, T, 1} (note how N works)?

I see, type-aliases are a problem. Constructors seem to work but I guess they don't help for convenient dispatch:

MySVector{N,T}(a::T...) where {N,T} = MySArray{(length(a),)}(a...)

For dispatch on vectors you could use the length typevar for a functionally equivalent typealias

const MySVector{N,T} = MySArray{T,1,<:Any,N}

but that doesn't work for matrices.

This language restriction is a bit disappointing, since nesting types in type parameters feels like a hack, especially if it is only done for the sake of having nice type aliases.

[c42f]

especially if it is only done for the sake of having nice type aliases.

Actually I feel this is somewhat deeper than the problem of type aliases.

To me, this is about traits as values vs types, and the natural handling of static and dynamic dimensions. For this, the current way that the Size trait is encoded is really not ideal. Encoding the size as a Tuple of StaticInteger and Int instead seems extremely promising. I said something about this in https://github.com/JuliaArrays/StaticArrays.jl/issues/806#issuecomment-655320510 as well:

One thing which has long bothered me is the inability to use Size quite the way I want to when mixing static and dynamic dimensions — I've ended up reimplementing things in the type and value domains separately which is really dissatisfying. The right way out of that is to use a mixed Tuple of StaticInteger and Int, not a Size parameterized on a Tuple of Int and Dynamic().

[stev47]

I'm sorry for maybe sounding somewhat oblivious to the larger picture, but I'm still trying to understand.

Since traits are implemented by functions, they can always be defined, as long as the information is carried within the type somehow. I was talking about the concrete array type, the Size trait might be a different topic. But even there I still don't see where Tuple{StaticInteger{N},Int} is more flexible than (N, Int) when traits are just functions. The big restrictions I see are in subtyping and type aliases where you can go one way but not the other with respect to type parameters.

I agree that stuff should not be reimplemented in the type and value domain, but isn't StaticNumbers doing exactly that by reimplementing Julias native numbers in the type domain (partly by delegating and partly but restricting operations to ease compiler load)? Constant propagation and inlining actually make StaticNumbers somewhat obsolete, since the compiler will always carry out the computation if the input was statically known (e.g. carried in a type parameter).

[c42f]

But even there I still don't see where Tuple{StaticInteger{N},Int} is more flexible than (N, Int) when traits are just functions.

It's true that trait functions are pretty flexible and that traits can be encoded in a variety of ways. Also true there's no need for the same representation to be used in the type parameters as is returned from a trait function.

Perhaps you're right that this is really about having sensible subtyping, with the consequence that type aliases are naturally expressible plus dispatch rules easy to write. I guess I've just got the strong feeling that having static numbers in the type signature would fix several expressivity problems I've observed while working on StaticArrays! Some of the internals seem much more awkward and difficult to work on than they really should be. Conversion and construction, for example.

Constant propagation and inlining actually make StaticNumbers somewhat obsolete, since the compiler will always carry out the computation if the input was statically known

I'd agree that it's much better to rely on constant propagation for a lot of cases where we previously used things like Val{N} to force certain optimizations. Encoding information in the type is still useful though if you want a semantic guarantee that the compiler won't throw that information out — that it will always be propagated through the program in a user-defined way, regardless of compiler inlining decisions, etc.

[cscherrer]

you then have

julia> x = MySArray{(2,2)}(1, 2, 3, 4)
2×2 MySArray{Int64,2,(2, 2),4}:
 1  3
 2  4

The size information is still static and the type layout way simpler. Is there something I have overlooked?

Hi @stev47 , I'm very late to this party, but I was trying to something similar and found one pain point with this approach if you try to match with a type-level tuple:

julia> numrows(::MySArray{(I,J)}) where {I,J} = I
ERROR: TypeError: in Type, in parameter, expected Type, got a value of type Tuple{TypeVar, TypeVar}
Stacktrace:
 [1] top-level scope
   @ REPL[31]:1

[stev47]

In many cases there is no need to dispatch on the tuple components, e.g in your case:

numrows(::MySArray{X}) where X = X[1]

You can confirm that it compiles down to a single constant using @code_typed.

[cscherrer]

I've been bitten a few times trying to do manipulations like this on type parameters, I guess the semantics aren't entirely clear to me yet. I wouldn't have expected this to work, but it's nice that it does!