Function arguments are inferred to be of type Any despite annotation (v0.3.0-prerelease)

[yurivish]

In the definition of getindex() below, which is taken from a Treap implementation discussed in this julia-users thread, inspecting variable types using code_typed reveals that both t and index are inferred to be of type Any despite being annotated with specific types in the function declaration.

Here's a minimal piece of code that will reproduce the issue (load the Treap code first):

t = MinTreap{Int}()
add!(t, 50)
@code_typed t.root[1]

For convenience, here's the definition of getindex() that is being invoked above:

function Base.getindex{K}(t::TreapNode{K}, index::Int)
    @assert 1 <= index <= t.size "Invalid treap index: $index."
    while t.left.size != index - 1
        if index <= t.left.size
            t = t.left
        else
            index = index - t.left.size - 1
            t = t.right
        end
    end
    t.key
end

[JeffBezanson]

The types in the function signature only serve as a dispatch spec; they don't "declare" the variables to be of those types in a case like this where the arguments are assigned to. It has to be this way, to make dispatch and declaration orthogonal.

I was able to fix it by adding these declarations at the beginning of the function:

    t::TreapNode{K}
    index::Int

One could argue that this orthogonality is not so important, and you just have to expect arguments with types to have fixed types. But the current behavior is intentional and we'll probably keep it that way for now.

[yurivish]

Understood – thanks for the diagnosis. I had thought that type annotations in the signature had the effect as those in the two lines you added.

For my understanding, could you give an example of a case where the current behavior is beneficial?

[IainNZ]

So @JeffBezanson is then a failure in some sense of the type inference, and is thus fixable?

[JeffBezanson]

Sometimes people write code like

function foo(x::Int)
    x = float(x)
    ...
end

and expect the type of x to change. It would be a bit confusing if x were type-const by default.

[mlubin]

But that doesn't seem to be the case here?

[JeffBezanson]

In the new version of the code, the abstract Treap type has been removed, so the type of t.left is always known exactly. With that change, the extra declarations are not necessary.

[IainNZ]

Oh, yes, indeed. :+1:

[yurivish]

For what it's worth, I think that the code was prettier and more expressive when empty and nonempty nodes had different types. The change in the new version was made for performance reasons alone (and does improve the speed of treap operations significantly).

I wonder if there's any way to use the type system to encode the distinction while maintaining performance?

[JeffBezanson]

It would be nice to have a way to "seal" an abstract type so that its set of subtypes is fixed. Then you would get more of the benefits of tagged unions as in many functional languages.

[StefanKarpinski]

Isn't a sealed abstract type just a type union? The only difference is that an abstract type is declared before its constituent types, whereas a type union must be defined after. However, if we allowed referring to not-yet-declared types that are defined later in the same closed module (i.e. not Main), then we would get both for free and solve the mutually recursive types problem.

[JeffBezanson]

I'm not sure they're equivalent when parameters are involved. For example

abstract A{P}

type Sub1{T} <: A{T}
end

type Sub2 <: A{Int8}
end

[StefanKarpinski]

Can't you get around that with a typealias? Close abstract types seem kind of featurey.

[JeffBezanson]

I agree it feels featurey, but I don't see how to express my example with typealias.

[StefanKarpinski]

typealias Sub{T} Union(Sub1{T},Sub2)

[JeffBezanson]

In my example Sub2 is only a subtype of A{Int8}, not any other A{T}.

[StefanKarpinski]

What is the abstract type that you want to close here? A?

[JeffBezanson]

Yes, that's the only abstract type in the example.

[StefanKarpinski]

There are an unbounded number of abstract types in the example: Sub1, A, A{Int8}, A{Symbol}, A{A}, etc. I don't get how Sub2 being only a subtype of A{Int8} is relevant – Sub2 <: A{Int8} <: A. The concrete types that are subtypes of A at the end of your code snippet are Sub1{T} for any T and Sub2. Those are precisely the concrete types that are subtypes of the Sub typealias.

[JeffBezanson]

With the typealias, Sub2 is a subtype of A{Float64}, and in my example it's not. The behavior is not identical.