Feature request: Type constructors as type parameters

[eschnett]

This would be cool to have:

immutable X{C}
       x::C{Int}
end

In this way, I can pass Vector or Set or NTuple{4} as type parameter to X.

[vtjnash]

this assumes that a type parameter is the eltype of that type, which is false.

[yuyichao]

FWIW, TypeConstructor as type parameter is allowed...

julia> immutable X{C}
       end

julia> X{Vector}()
X{Array{T,1}}()

The usage of the type parameter is the problem...

[JeffBezanson]

Yes, although it may seem surprising, I believe supporting this is nearly impossible. For example you could write

typealias Loop{X} X{X}

Loop{Loop}

which wouldn't terminate.

[eschnett]

@vtjnash I don't understand your comment. What does eltype have to do with what I'm trying to do? I'm not claiming that X is a collection, or that C is its element type.

[vtjnash]

based on your examples, it seemed you were assuming that in C{T}, T was the eltype of C, but you can't parameterize an unknown type that way, since the order and meaning of the type parameters isn't defined that way

for example, I could define a type IntSet <: Set{Int}. this IntSet should be valid for C, since it fits the pattern above, but clearly that is not valid in this case since IntSet doesn't accept parameters.

[eschnett]

@JeffBezanson Recursion could be addressed by disallowing recursion, or by imposing a recursion limit.

My goal is to define a collection where the actual container type used in the implementation is not fixed. If the above construct is not possible, then I cannot write

immutable X{C, T}
    x::C{T}
end

but I have to write

immutable X{CT}
    x::CT
end

instead. This means that I can't define a type where T is a parameter; instead, I will have to use eval to create a new type for each type parameter T.

[eschnett]

@vtjnash Yes, type type "won't work" for some values of C. That is nothing new; e.g. in NTuple{-1,Int}, the parameter -1 is also not allowed.

[yuyichao]

You don't need eval, You can define X{C,T,CT} and handle this in the constructor.

[vtjnash]

My goal is to define a collection where the actual container type used in the implementation is not fixed. If the above construct is not possible, then I cannot write

please reread my counter-example

[eschnett]

@vtjnash I understand your example -- it does not apply. C should be a TypeConstructor, whereas IntSet is not; it is a Type instead. So yes, passing IntSet for C will not work, and I don't expect it to. It's like passing a value when the caller expects a function. This is like writing Set{Int}{Int}.

[eschnett]

@yuyichao Wouldn't this be expensive -- constructing a type X{C,T,CT} each time an object is constructed? In the end, I expect the type to hold just a few Float64 values, and all overhead should be optimized away.

[yuyichao]

Constructing a type cost nothing if type inference can infer the type. This is what @pure and @generated are for.

[yuyichao]

julia> immutable X{C,T,CT}
           x::CT
           X() = new()
       end

julia> Base.@pure _apply_type(C, T) = C{T}
_apply_type (generic function with 1 method)

julia> (::Type{X{C,T}}){C,T}() = X{C,T,_apply_type(C, T)}()

julia> X{Set,Int}()
X{Set{T},Int64,Set{Int64}}(#undef)

julia> @code_warntype X{Set,Int}()
Variables:
  #self#::Type{X{Set{T},Int64,CT}}

Body:
  begin  # none, line 1:
      GenSym(1) = $(Expr(:static_parameter, 1))
      GenSym(0) = $(Expr(:static_parameter, 2))
      $(Expr(:static_parameter, 1))
      $(Expr(:static_parameter, 2))
      return $(Expr(:new, X{Set{T},Int64,Set{Int64}}))
  end::X{Set{T},Int64,Set{Int64}}

[rfourquet]

This is a dupe of #8322 (third example).

[yuyichao]

Actually type inference is smart enough without the @pure wrapper... (as it should....)

julia> immutable X{C,T,CT}
           x::CT
           X() = new()
       end

julia> (::Type{X{C,T}}){C,T}() = X{C,T,C{T}}()

julia> @code_warntype X{Set,Int}()
Variables:
  #self#::Type{X{Set{T},Int64,CT}}

Body:
  begin  # none, line 1:
      GenSym(1) = $(Expr(:static_parameter, 1))
      GenSym(0) = $(Expr(:static_parameter, 2))
      $(Expr(:static_parameter, 1))
      return $(Expr(:new, X{Set{T},Int64,Set{Int64}}))
  end::X{Set{T},Int64,Set{Int64}}

[eschnett]

Doesn't this require me to declare all functions @generated if they take such a type as input? I would also have to introduce such a hidden parameter for all other types that contain an element of type X{C,T} -- and I might not have control over these other types. Assume e.g. I want to create a Vector{X{C,T}}.

[vtjnash]

yeah, @pure is for marking expressions that aren't trivially pure (similar to how type assertions are for marking expressions that aren't trivially inferrable). i'm not sure what @generated is for :P. it would certain help make that example far more expensive (memory and speed).

[yuyichao]

Doesn't this require me to declare all functions @generated if they take such a type as input?

No, it can just use the type.

Assume e.g. I want to create a Vector{X{C,T}}

AFAICT this is mainly a matter of how to generate X{C,T,C{T}} conveniently. For now you can just define a pure function to compute that with C and T as input so that you can write Vector{x(C,T)}. Maybe we can allow overloading the behavior of apply_type assuming the overload is pure in order to get more syntactically consistent in this case but that sounds like a feature that can be misused a lot (especially given that not even @pure is currently exported)

[yuyichao]

i'm not sure what @generated is for :P

It's for non-trivial compile time code generation when the compile time and type unstable input are not concerns. Doesn't help with this example with @pure though.

[eschnett]

I still can't use this with Vector in all cases:

typealias MyVector Vector{X(Set,Int)}

doesn't work since I can't call a function in typealias (or in a type definition); thus, I'm back to having to use a function instead of typealias, and to doing special tricks for defining types that contain an element of type X, even if X is completely known at compile time.

[yuyichao]

I can't call a function in typealias

Not true. It's just a const assignment.

julia> typealias MyVector Vector{(()->Int)()}
Array{Int64,1}

I'm back to having to use a function instead of typealias

Mostly about using functions instead of TypeConstructor. (edit: which is exactly what I mentioned above...)

For dispatch, you don't need to specify all the type parameters, you can just assume the type is legal.

[eschnett]

@yuyichao D'oh, my bad. Thanks for the correction.

[JeffBezanson]

@yuyichao I like your solution; that's clever.

Currently we require field types to be, well, types. To represent C{T} as a type, we would need to have an "application" type kind. However then types could represent arbitrary lambda terms AFAICT. To avoid this, we require that type application be performed by executing code, which is obviously already turing-complete.

So, we could address this by instead lifting the requirement that field types be types. For example, field types could be thunks that get executed when type parameters are known. However this would make it difficult to get partial type information from field types. @yuyichao 's approach can be seen as implementing something like this manually via the constructor.