Julep: parametric abstract inference

[timholy]

A potential enhancement to inference would be to make it parametric:

julia> T = TypeVar(:T)
T

julia> Base.return_types(getindex, (Vector{T}, Int))
1-element Vector{Any}:
 Any

where this should return T (the identical T I defined with the TypeVar) instead of Any.

Let's begin with the downsides:

• this might be heroically difficult (or impossible) to implement
• keeping track of the extra information might make inference slower
• we might have to widen to Any at the slightest provocation to avoid blowing up inference, meaning that there would be precious few applications of this capability.

In the worst-case scenario, this adds up to a massive waste of time.

Now let's consider possible good things that might, if fate smiles on us, come to pass:

• inference might get faster: you only have to infer getindex(::Vector{T}, Int) once, and just plug in T for any concrete case.
• you can check abstract interfaces more precisely

The last might be a big enough win that this is worth considering. Let me give a (possibly broken) demo implementation, motivated by #49973 (comment):

function Test.required_interface(::Type{A}, ::Type{X}) where {A<:AbstractArray{T,N},X} where {T,N}
    Base._return_type(Tuple{typeof(size), X}) <: NTuple{N,Integer} || throw(InterfaceError(X, AbstractArray{T,N}, size))
    Base._return_type(Tuple{typeof(getindex), X, Vararg{Int,N}}) === T ||
        Base._return_type(Tuple{typeof(getindex), X, Int}) === T || throw(InterfaceError(X, AbstractArray{T,N}, getindex))
end

The caller could prepare this with

T, N = TypeVar(:T), TypeVar(:N)
Test.required_interface(AbstractArray{T,N}, MyNewArrayType{T,N})

[martinholters]

In many places throughout inference, the appearance of unbound (including plain) typevars is a sign that something is going wrong. So maybe a dedicated lattice element might be more appropriate, if just to clearly distinguish intentional vs. unintentional typevars (or their equivalent lattice elements).

Another even more radical idea: Could we, upon first inference of a method, synthesize a tfunc for it? That might take a moment, but executing the tfunc should be faster than doing abstract interpretation, so if the method is inferred for many different argument types, it might pay off eventually.