Proposal for type conversions

[tomerarnon]

This proposal is related to #1182 #965, and maybe other issues that have to do with conversion (and promotion).

Currently, a number of convenient conversions are missing. Defining every possible conversion seems infeasible, but I think with a few steps, you can get almost all conversions you could reasonably want without having to deal with any of the combinatorial conversion problem. As concrete examples, I would love it if conversions like the following were possible.

julia> hr = rand(Hyperrectangle, dim = 2);

julia> convert(HPolytope{Float32, Vector{Float32}}, hr) # currently an error

The proposal to allow this, and other such conversions, is the following:

1. Each type must implement all the convert methods necessary to change its stored types. Basically L{N} -> L{M} must be defined for each type. I think this requires as many functions as parameters. While this is still a lot of conversions, it is independently convenient to have. (For someone cleverer than me, maybe this can be done with fewer methods, like with a fancy inner constructor, or even with a macro...)

For HalfSpaces, consider

function Base.convert(::Type{HalfSpace{N, VN}}, hs::HalfSpace) where {N, VN}
    HalfSpace(convert(VN, hs.a), N(hs.b))
end
# Note that conversion to `AbstractVector` is type stable, because it is a no-op
# in case N == M, and an eltype conversion in case M != N
# as an example, consider convert(AbstractVector{Float64}, [1])
function Base.convert(::Type{HalfSpace{N}}, hs::HalfSpace) where {N}
    HalfSpace(convert(AbstractVector{N}, hs.a), N(hs.b))
end

These two methods allow conversions like the following:

julia> hs = HalfSpace([1], 1)
HalfSpace{Int64,Array{Int64,1}}([1], 1)

julia> convert(HalfSpace{Float32}, hs)
HalfSpace{Float32,Array{Float32,1}}(Float32[1.0], 1.0f0)

1a. Once lower level conversions exist, higher level ones can be built on top of them. Consider HPolytope, which relies on HalfSpace

function Base.convert(T::Type{HPolytope{N, VN}}, hp::HPolytope) where {N, VN}
    HPolytope(convert.(HalfSpace{N, VN}, constraints_list(hp)))
end
function Base.convert(T::Type{HPolytope{N}}, hp::HPolytope) where {N}
    HPolytope(convert.(HalfSpace{N}, constraints_list(hp)))
end

Now we can also do things like

julia> hp = HPolytope([hs, hs])
HPolytope{Int64,Array{Int64,1}}(HalfSpace{Int64,Array{Int64,1}}[HalfSpace{Int64,Array{Int64,1}}([1], 1), HalfSpace{Int64,Array{Int64,1}}([1], 1)])

julia> convert(HPolytope{Float32}, hp)
HPolytope{Float32,Array{Float32,1}}(HalfSpace{Float32,Array{Float32,1}}[HalfSpace{Float32,Array{Float32,1}}(Float32[1.0], 1.0f0), HalfSpace{Float32,Array{Float32,1}}(Float32[1.0], 1.0f0)])

2. So far, we only have L{N} -> L{M}. However, L{N} -> S{N} already exists in a lot of cases, as in convert(HPolytope, hr), and we can and should take advantage of these! The last step is to break the conversion into L{N} -> S{N} -> S{M}, wherever both conversions are individually possible.

   
   # in general, convert S{M} -> L{N} whereever the conversions S{M} -> L{M} and L{M} -> L{N} already exist
   Base.convert(::Type{L}, s::L) where L <: LazySet = s
   function Base.convert(::Type{L}, s::LazySet) where L <: LazySet
   T = _stripparameters(L)
   # LazySets seems to implement major conversions using the UnionAll names
   # e.g. convert(HPolytope, hr), rather than convert(HPolytope{N, VN}, hr)
   # If we ended up in this function with a pure UnionAll or a pure DataType, 
   # (such that L == T), it means no other conversion for this type exists.
   # if T == _stripparameters(typeof(s)), then the conversion attempted is
   # to another leaf type of the same UnionAll type, such as:
   # convert(HPolytope{N, NV}, h::HPolytope). If we're in this method for
   # such a conversion, then no such conversion is defined.
   if L == T || T == _stripparameters(typeof(s))
       throw(MethodError(convert, (L, s)))
   end
   return convert(L, convert(T, s))
   end

get the "UnionAll name" from a type. E.g. _stripparameters(Vector{Int}) -> Vector

@inline _stripparameters(T::UnionAll) = _stripparameters(T.body) @inline _stripparameters(T::DataType) = T.name.wrapper

\* The above assumes inter-set conversions "always" take the form `convert(UnionAllName, set)`. I'm not sure if this is true, but it's a trend I've noticed, but maybe I'm too entrenched in AbstractPolytope land...

2a. Sometimes, lower level conversions may also be needed. For example, to get `convert(HPolytope{Float32, Vector{Float32}}, hr)` the following is also needed due to the conversion from `Hyperrectangle` resulting in `SingleEntryVector`s
```julia
Base.convert(T::Type{<:Arrays.SingleEntryVector}, v::Arrays.SingleEntryVector) = T(v.i, v.n, v.v)
Base.convert(::Type{AbstractVector{T}}, v::Arrays.SingleEntryVector{T}) where T = v
Base.convert(::Type{AbstractVector{T}}, v::Arrays.SingleEntryVector{A}) where {T, A} = convert(Arrays.SingleEntryVector{T}, v)
# other conversions seem to already exist from the <:AbstractArray interface.

But these should exist anyway, so I don't consider this its own obstacle 😁

3. As a cherry on top, it is sometimes convenient to call convert operations with a constructor-like function (for style usually). E.g. HPolytope(hr). I'm not sure if this contradicts the ethos behind convert for some types in LazySets, but if not, it can be achieved in general with

   # make conversions callable
   (Q::Type{<:LazySet})(P::LazySet) = convert(Q, P)

   This part isn't really crucial for the rest of the proposal, but could be nice to have.

---

With all of the above combined, you could do basically anything:

julia> using StaticArrays

julia> hr = rand(Hyperrectangle, dim = 4);

julia> HPolytope{Float16, SVector{4, Float16}}(hr)
HPolytope{Float16,SArray{Tuple{4},Float16,1,4}}(HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}[HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[1.0, 0.0, 0.0, 0.0], Float16(1.804)), HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[0.0, 1.0, 0.0, 0.0], Float16(-0.588)), HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[0.0, 0.0, 1.0, 0.0], Float16(0.3286)), HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[0.0, 0.0, 0.0, 1.0], Float16(0.663)), HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[-1.0, 0.0, 0.0, 0.0], Float16(-0.2954)), HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[0.0, -1.0, 0.0, 0.0], Float16(2.053)), HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[0.0, 0.0, -1.0, 0.0], Float16(-0.1383)), HalfSpace{Float16,SArray{Tuple{4},Float16,1,4}}(Float16[0.0, 0.0, 0.0, -1.0], Float16(0.1492))])

[mforets]

Thanks for the write-up! Food for thought. I'd love to have such conversions working as well.

More examples

julia> P = convert(HPolytope, BallInf(zeros(2), 1.0))
HPolytope{Float64,LazySets.Arrays.SingleEntryVector{Float64}}(HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}[HalfSpace{Float64,LazySets.Arrays.
SingleEntryVector{Float64}}([1.0, 0.0], 1.0), HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([0.0, 1.0], 1.0), HalfSpace{Float64,LazySets.Array
s.SingleEntryVector{Float64}}([-1.0, 0.0], 1.0), HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([0.0, -1.0], 1.0)])

julia> P = convert(HPolytope{Float64, Vector{Float64}}, BallInf(zeros(2), 1.0))
ERROR: MethodError: Cannot `convert` an object of type BallInf{Float64,Array{Float64,1}} to an object of type HPolytope{Float64,Array{Float64,1}}
Closest candidates are:
  convert(::Type{T}, ::T) where T at essentials.jl:171
Stacktrace:

[tomerarnon]

I didn't mention this, but I don't know whether performing the conversion in two steps like proposed is less efficient than defining a direct conversion method, and if so, whether inlining could help or not. That's something probably worth knowing though in case this is a desirable direction.