Allowable FSA subtype parameters and similar()

[c42f]

With #105 merged, similar() now plays a central role in deciding the FSA type which is returned from mapping operations. This means that some FSA subtypes which kind of worked before now really don't work without overloading similar(). For example, the Coordinates type in #104.

Looking at the implementations of similar() the problem is fairly obvious - it's assumed that the type parameters of FixedVector subtypes will always look like MyFSA{N,T, ...}. Personally I'm feeling like this is too constraining, and I think it's reasonable for users to want to

• Fix N for FixedVector (to 3 for three dimensions, say).
• Fix N for FixedVectorNoTuple, (ok, this is more or less inherently fixed :-) )
• Fix T to something specific for their problem domain.
• Add extra type parameters as an additional dimension along which to distinguish FSA subtypes (see datum discussion in map refactoring for different eltypes and different FSA subtypes. #105 for a possible use case)

Supporting all these needs automatically with the default implementation of similar() seems impossible, so I'd like to make similar() something users must overload in general, and discuss how we can have the most sensible default implementation.

If users are allowed to fix N and T for their subtype, they must have a way to produce an alternative container for the output of map when map produces incompatible N or T. Luckily overloading similar() seems a nice way to do this. Consider:

immutable Coordinates <: FixedVectorNoTuple{3, Float64}
    x::Float64
    y::Float64
    z::Float64
end

Base.similar(::Type{Coordinates}, ::Type{Float64}, sz::Tuple) = sz[1] == 3 ? Coordinates : Vec{sz[1],Float64}
Base.similar{T}(::Type{Coordinates}, ::Type{T}, sz::Tuple) = Vec{sz[1],T}

With the above definitions, we can get a sensible container of Bool out of .< even though Coordinates is fixed to Float64:

julia> Coordinates(1,2,3) .< Coordinates(2,2,2)
Vec(true,false,false)

Unfortunately the definitions of similar() above are a bit nasty with the branch on the size tuple meaning they are type unstable. To avoid this, I think we could do something with Val...

Base.similar(::Type{Coordinates}, ::Type{Float64}, ::Type{Val{(3,)}}) = Coordinates
Base.similar{T,SZ}(::Type{Coordinates}, ::Type{T}, ::Type{Val{SZ}}) = Vec{SZ[1],T} # Hmm, how do we  restrict SZ in the function signature?  Ugh!

Thoughts?

[SimonDanisch]

That seems pretty reasonable! :) We should rename it to similar_type at some point though!
That was me trying to mimic the way map is implemented in Base, while our similar really does a different thing.
We should also burden the user with defining base_name, and then have people overload similar_type only if it deviates as described above.
Val seems to be the only way of allowing to use similar_type outside of generated functions...

[SimonDanisch]

Althoooough, this seems to work on 0.5:

Base.@pure similar_type(::Type{Coordinates}, ::Type{Float64}, sz::Tuple{Int}) = sz[1] == 3 ? Coordinates : Vec{sz[1],Float64}
function test{N}(a, b::Vec{N, Int})
       map(identity, similar_type(Coordinates, Float64, (N,)))
end
@code_typed(test(a, Vec{3,Int}(2)))[1].rettype == Coordinates
@code_typed(test(a, Vec{4,Int}(2)))[1].rettype == FixedSizeArrays.Vec{4,Float64}
# this doesn't work though (but Val doesn't seem to help either)
function test(a, b)
       similar_type(Vec, length(b), Int)(a[1], b[2], a[3])
end

The last case could possibly work, but doesn't right now because something goes wrong somewhere else?! Not sure, needs investigation!

[c42f]

We should rename it to similar_type at some point though

Heh, I did think the pun on similar() was ok, but @andyferris was also advocating similar_type yesterday so I'm coming around to that.

Regarding downsides of Val, it's fairly ugly and nonintuitive to work with vs a plain tuple, and I'm not sure how to make function signatures which restrict the Vals which match (eg, suppose you only want Val{(N,)} but not Val{(N,M)} to match?). We also mostly use similar() inside @generated functions, which makes tuples non-disastrous, at least internally. So maybe it's worth trying for @pure instead, with the understanding that in 0.4 similar_type is only really useful inside a generated function.

Oh, one other thing. I did think that construct_similar in my map patch might be better off as similar, with the current similar renamed to similar_type. I'm not really sure that makes sense, but for immutable types, the only sensible value-returning similar you can have is one that actually constructs the output value fully initialized...

[andyferris]

Indeed, +1 for similar_type. Rather than construct_similar, maybe similar could take an extra argument as a Generator or similar to populate the array. (Maybe some kind of expression generator? I don't know... just speculating here).

I also agree sorting out these problems targeting Julia 0.5 is probably the smart move. @pure functions might help in alleviating the user-difficulty in using Val everywhere, but I'm still a little confused how to get that to work nicely (I mean - I can get it working for similar_type(::Type{Coordinates}, sz::Tuple{Int}) but maybe not for similar_type(::Coordinates, sz::Tuple{Int}), and certainly not for replacing TypedTable's getindex(::Table, ::Type{Val{fieldname}}) - any advice would be appreciated if you can get inference working on the last!).

Also, note that:

Base.similar{T,SZ}(::Type{Coordinates}, ::Type{T}, ::Type{Val{SZ}}) = Vec{SZ[1],T} # Hmm, how do we  restrict SZ in the function signature?  Ugh!

is not type-inferred. Inference bails whenever you try and do anything to a type parameter (and I really mean ANYTHING, like getting the first index of a tuple). You have to insert the value as a literal in a @generated function like this:

@generated function Base.similar{T,SZ}(::Type{Coordinates}, ::Type{T}, ::Type{Val{SZ}})
    :(Vec{$(SZ[1]),T})
end

This also opens up the possibility of capturing different dimensionalities of SZ and bailing appropriately.

Though, the real fix would be to investigate Julia's base/inference.jl and see if we can get @pure function constant propagation working in type parameters - that would both make this kind of package easier to write and remove a lot of generated functions.

The other thing that would be helpful is if Julia let you constrain the types of parametric values not just parametric types in method signatures.

[c42f]

Thanks for the thoughts guys. Considering @pure in 0.5 and the difficulty of working with Val, I think we should aim for similar_type to take a tuple parameter rather than a Val, so I'll put a PR together for that.

I've also spent far too much time worrying about what the default similar_type should look like. There's a few conflicting possibilities:

1. Always return "blessed" FSAs by default - I'd choose Vec and Mat for this. This is very simple to document and has a good analogy with Base where Array is returned by similar(::AbstractArray, ...) by default.
2. Return the same FSA if the eltype and size match exactly, otherwise behave as option 1. above.
3. Make assumptions about the type parameters, for example assume that if the user defines MyVec1, MyVec2 and MyMat, then the order of type parameters is MyVec1{N,T} <: FixedVector{N,T}, MyVec2{T} <: FixedVectorNoTuple{N,T}, MyMat{N,M,T} <: FixedMatrix{N,M,T}. This preserves the existing behavior, but is prone to failing in a confusing and poorly defined way if the user reorders type parameters, leaves some out, or whatever. If only we could programmatically guess the semantics of user defined type parameters, but I've no idea how to do this reliably.

At this stage I'm going to try for 2. and we can see how it looks.

[c42f]

I think #118 sorts this out to the extent it can be for now.