"Regression" in typeinf when concatenate two tuple types

[yuyichao]

I was under the impression that #10380 can make type inference easier for functions that use tuple types. However, when I want to get the type of the concatenation of two tuples, I couldn't get good type inference anymore. (It is also very likely that I'm just being stupid and don't know the correct way to do it in the new version.)

The code I am using can be simplified to

if isa((Int,), Type)
    function cat_tt(a, b)
        tuple(a..., b...)
    end
else
    function cat_tt(a, b)
        Tuple{a.parameters..., b.parameters...}
    end
end

println(cat_tt(typeof((1, 2)), typeof((1, 2))))
println(@code_typed cat_tt(typeof((1, 2)), typeof((1, 2))))

Before the change of the tuple type, the output is

(Int64,Int64,Int64,Int64)
Any[:($(Expr(:lambda, Any[:a,:b], Any[Any[],Any[Any[:a,Type{(Int64,Int64)},0],Any[:b,Type{(Int64,Int64)},0]],Any[],Any[]], :(begin  # /home/yuyichao/tmp/julia_cat_tt.jl, line 5:
        return (Int64,Int64,Int64,Int64)
    end::(Type{Int64},Type{Int64},Type{Int64},Type{Int64})))))]

After the change

Tuple{Int64,Int64,Int64,Int64}
Any[:($(Expr(:lambda, Any[:a,:b], Any[Any[],Any[Any[:a,Type{Tuple{Int64,Int64}},0],Any[:b,Type{Tuple{Int64,Int64}},0]],Any[],Any[]], :(begin  # /home/yuyichao/tmp/julia_cat_tt.jl, line 9:
        return (top(_apply))(call,top(apply_type),(top(tuple))(Tuple)::Tuple{DataType},(top(getfield))(a::Type{Tuple{Int64,Int64}},:parameters)::SimpleVector,(top(getfield))(b::Type{Tuple{Int64,Int64}},:parameters)::SimpleVector)::ANY
    end::ANY))))]

Maybe there's better ways to do this.

[yuyichao]

Actually, I guess I can use a staged function

stagedfunction cat_tt(a, b)
    Tuple{a.parameters[1].parameters..., b.parameters[1].parameters...}
end

Is there a better way to do this?....

[blakejohnson]

Isn't the problem just that (Int,) is now just a tuple, and not a type? If you change that first line to:

if isa(Tuple{Int}, Type)

wouldn't it work?

[yuyichao]

@blakejohnson No. that if is just to make the code works for both before and after the change and the difference I'm talking about is not the result, but the result of typeinf.

My point was that the typeinf cannot infer the result of concatenation of tuple types anymore. (But since I noticed that stagedfunction can be used to do this, I guess the point should be there's no easy way to do this (concatenate two tuple types while keep make sure the typeinf can infer the correct type).)

[JeffBezanson]

Yes, this was maybe the biggest advantage to using tuples of types as types: you got lots of operations on them for free. While working on #10380 I found I needed the following tuple type operations:

tuple_type_head
tuple_type_tail
tuple_type_nth
tuple_type_cons
tuple_type_cat

I used staged functions, but it feels like kind of a hack. I think I can improve type inference of splatting x.parameters at least.

[yuyichao]

And since it is still possible to do what I want, I guess it's not a "regression" anymore although it might still be helpful to teach typeinf about .parameters for types

[yuyichao]

Also, how bad/useful would it be to make the Tuple type itself iterable?

[vtjnash]

i think i've seen this before on the issues list; the primary source of the issue being due to the fact that type inference doesn't know that the .parameters field is constant

[JeffBezanson]

There used to be a hack in inference that handled this, but now .parameters is a SimpleVector so something slightly different is needed.

[yuyichao]

Would it be useful if the certain field of a type can be declared as constant (immutable) without making the whole type immutable?

I found this old issue but it seems to be merged with the implementation of immutable.

[StefanKarpinski]

@yuyichao, we decided against that.

[JeffBezanson]

It wouldn't help here, since SimpleVector hides the types of its elements, and the compiler already effectively assumes a type's parameters can't change. If they did, you'd have way bigger problems than this.

[andyferris]

Hi, sorry to bump, but I'd really like to see some of the functionality talked about here and many related threads.

In particular, I think solving the splatting of tuple-types into tuple-types as being type-stable would mean all the other problems can be solved by clever Julia programming (without generated functions). Is there any progress on this issue?

My interest was sparked in trying to remove generated functions from this attempt at strongly-typed dataframes/tables using metaprogramming along the lines of this attempt of a metaprogramming package. The goal of the latter is to manipulate meta-collections in a type-safe way where every function is a no-op. I'm surprised how far you can get with no generated code, but the big hang-up is in creating (and inspecting) Tuple-types.

Type-stable concatenation and splatting would be sufficient to implement the rest of the features (and to use Tuple as a meta-storage container, rather than hacks like I came up with) but @JeffBezanson's list above is even better. @mbauman has some code for concatenation, but it's only defined up to a certain fixed integer length, and I would really appreciate some general built-in functionality.

[vtjnash]

this has been largely "solved" by allowing marking type functions (like tuple_type_cat) as @pure. that lets inference know that it should evaluate these methods directly when it can constant fold them, without incurring the complexity and memory cost of a generated function.

[andyferris]

Hmm... the :pure tag didn't seem to work for me. E.g.:

function concatenate{T<:Tuple, S<:Tuple}(::Type{T}, ::Type{S})
    Base.@_pure_meta
    Tuple{T.parameters..., S.parameters...}
end

julia> concatenate(Tuple{Int},Tuple{Int})
Tuple{Int64,Int64}

julia> @code_warntype concatenate(Tuple{Int},Tuple{Int})
Variables:
  #self#::Metaprogramming.#concatenate

Body:
  begin  # /home/aferris/.julia/v0.5/Metaprogramming/src/Metaprogramming.jl, line 18:
      $(Expr(:meta)) # /home/aferris/.julia/v0.5/Metaprogramming/src/Metaprogramming.jl, line 19:
      return (top(_apply))(top(apply_type),(top(tuple))(Metaprogramming.Tuple)::Tuple{DataType},(top(getfield))(T,:parameters)::SimpleVector,(top(getfield))(S,:parameters)::SimpleVector)::Any
  end::Any

I have tried another couple of functions, but there seems to be no effect of the macro.

Perhaps this will resolve itself when more features and abilities are added to @pure?

[vtjnash]

you're looking at the code for the unspecialized function. unlike generated functions, it doesn't have to regenerate and compile the function for every combination of arguments in order to constant fold.

julia> f() = concatenate(Tuple{Int},Tuple{Int})
f (generic function with 1 method)

julia> @code_typed f()
1-element Array{Any,1}:
 :($(Expr(:lambda, Any[symbol("#self#")], Any[Any[Any[symbol("#self#"),#f,0]],Any[],Any[]], :(begin  # none, line 1:
        return $(QuoteNode(Tuple{Int64,Int64}))
    end::Type{Tuple{Int64,Int64}}))))

[andyferris]

OK great - thanks! I know this is a question for the forums, but how does this work exactly? More precisely, when will it always work? For instance, I see that the wrapping function can have non-trivial inputs:

julia> g{T}(::Type{T}) = concatenate(Tuple{T},Tuple{T})
g (generic function with 1 method)

julia> @code_warntype g(Int)
Variables:
  #self#::#g

Body:
  begin  # none, line 1:
      return $(QuoteNode(Tuple{Int64,Int64}))
  end::Type{Tuple{Int64,Int64}}

I also checked g(x::Type...) which works well too.

Has it got something to do with the REPL living in Main? Or are there other special constraints on the wrapping function?

[vtjnash]

there's no special constraints. you just need to be careful that your function really is const and pure

[andyferris]

OK... sorry for being completely stupid, and its likely the answer can be found elsewhere, but why is f() = concatenate(Tuple{T},Tuple{T}) const and pure but concatenate(Tuple{T},Tuple{T}) not?

I'm trying to get to the heart of the problem of when exactly a function like concatenate gets specialized? Do I need a second layer of const function to get the specialization?

And, what exactly do you mean by const function? That it doesn't depend on the values of the inputs? Is that another meta-tag automatically generated by the compiler? Or is it similar to const declarations, which from the REPL help:

Technically, you can even redefine const variables, although this will generate a 
warning from the compiler. The only strict requirement is that the type of the variable
does not change, which is why const variables are much faster than regular globals.

Does this mean in analogy that a const function just has to be type-stable??

[mbauman]

Ah, this is interesting. I, too, had been thrown off by the function not getting specialized at the REPL - SubArray's trait computation should be pure.

As I understand it, the pure optimization is only used while running inference on another function because it can be precomputed and inlined there. It only isn't specialized at global scope and with type-unstable inputs.

[carnaval]

in general can we please all be careful before putting @pure everywhere since inference will trust you that it also means guaranteed_to_terminate, or maybe even guaranteed_to_terminate_quite_quickly.

In any case, I agree it's a little better than a staged function since at least we can fallback on not doing anything special and everything should still work.

[vtjnash]

Agreed, I'm only proposing it as an alternative to generated, which has those same issues plus more. Usually dispatch can achieve the same result (with better correctness with respect to #265). Explicitly memorized runtime checks are usually better, imo.

[JeffBezanson]

Was this fixed?

[yuyichao]

The list of function above can all be implemented with @pure and it's generic enough. Or do you think any access of T.parameters should be inferred/constprop automatically? Ref https://groups.google.com/forum/?fromgroups=#!topic/julia-users/TxQ49oHMGMY

[JeffBezanson]

Yes I think it should be simple to handle this with the constant prop we have now.

[yuyichao]

ok, reopen then ...