much better return type for Iterable.sequence()

[gavinking]

Today, @jvasileff figured out the solution to a problem that has bugged us for years — how to assign the correct return type to Iterable.sequence() for known-nonempty streams.

The return type is:

[Element+] | []&Iterable<Element,Absent>

There would be one big problem with making this change, and one much smaller problem:

1. It would involve a binary-incompatible change to the return type of Iterable.sequence(), which at the Java level would widen from Sequential<? extends Element> to Object.
2. For the case of an empty stream, that is not something special like [], "", or {}, calling sequence() would result in a reified check of the type argument Absent.

Problem (1) is rather easy to fix with a little hack to the compiler backend to preserve the previous return type Sequential<? extends Element>.

Problem (2) is not so easy to fix, but may not be a big deal.

[jvasileff]

Should the implementation of Iterable.sequence() should be just => [*this];?

That is, for spread arguments that are subtypes of Iterable where Absent involves a type parameter, should the sequential type be [X+] | []&Iterable<Anything,Absent>?

[gavinking]

That is, for spread arguments that are subtypes of Iterable where Absent involves a type parameter, should the sequential type be [X+] | []&Iterable<Anything,Absent>?

Yeah, I suppose we could make that work.

It's a good idea.

[gavinking]

Problem (2) is not so easy to fix, but may not be a big deal.

It appears that the reified type check costs about 1.5 μs in a tight loop.

[gavinking]

It appears that the reified type check costs about 1.5 μs in a tight loop.

Which is about 7 times slower than calling sequence() on a stream of length 3.

[gavinking]

So to even make a start on this issue, I need some nice person like @tombentley or @FroMage to do this bit for me:

a little hack to the compiler backend to preserve the previous return type Sequential<? extends Element>

Which means:

1. nailing down the return type of Iterable.sequence() to be exactly Sequential<? extends Element>, and
2. adding a typecast to the real type produced by the typechecker at every place where Iterable.sequence() is invoked.

The "real" type in (2) is always going to be either [], []|[Element+], or [Element+].

[tombentley]

Er, if I have

Iterable<Element,Nothing> defNonempty = nothing;
[Element+] x2 = defNonempty.sequence();

then I get error "specified expression must be assignable to declared type of 'x2': '[Element+]|[]&{Element+}' is not assignable to '[Element+]'"

What am I doing wrong?

[gavinking]

@tombentley what is your definition of Iterable.sequence()?

[gavinking]

We were using this function:

[Element+] | []&Iterable<Element,Absent>
sequence<Element,Absent>
    (Iterable<Element,Absent> elements)
    given Absent satisfies Null {
    if (nonempty sequence = elements.sequence()) {
        return sequence;
    }
    else {
        assert (is Iterable<Element,Absent> empty = []);
        return empty;
    }
}

I don't think the signature should stop working if you turned it into a method.

[gavinking]

Oh, I see, this problem only occurs if Element is a type parameter. That looks to me like a limitation of the type checker. I will look into it. But don't worry about it @tombentley, it definitely works for anything that is not a type parameter.

[tombentley]

Ah, OK, let me see then...

[gavinking]

It is a limitation of the code at ModelUtil:1673 and ModelUtil:1661, which give up if one of the intersected types involves type parameters.

I think we could improve that code by replacing type parameters with in Nothing.

[jvasileff]

As a workaround, @tombentley can use the return type [Element+] | []&Iterable<Anything,Absent>.

[gavinking]

@jvasileff OK, I have removed that limitation, but in fact the return type [Element+] | []&Iterable<Anything,Absent> is much better because it doesn't involve a reified type check, right!?

[gavinking]

it doesn't involve a reified type check, right!?

Oh no, not right, it's Absent that was being checked.

[gavinking]

Actually I like writing the function this way:

alias Empty<Absent> => [] & Iterable<Anything,Absent>;

[Element+]|Empty<Absent> sequence<Element,Absent>
    (Iterable<Element,Absent> elements)
        given Absent satisfies Null {
    if (nonempty sequence = elements.sequence()) {
        return sequence;
    }
    else {
        assert (is Iterable<Anything,Absent> e = []);
        return e;
    }
}

[jvasileff]

alias Empty<Absent> => [] & Iterable<Anything,Absent>;

That's really nice! (Although, Empty already exists)

[gavinking]

That's really nice!

Type functions FTW.

[gavinking]

@tombentley where are we at on this one?

[tombentley]

You want to do this for both Iterable.sequence() and the top-level sequence() and nothing else, right @gavinking?

[gavinking]

I was going to leave the toplevel sequence() alone, actually. In fact we should probably deprecate it now, no?

[tombentley]

It appears this change would be source incompatible, in that subclasses of Iterable which had refined sequence() would need an of, as evidenced by Sequential.sequence():

[ceylon-compile] /home/tom/ceylon/ceylon/language/src/ceylon/language/Sequential.ceylon:28: error: type of member must be assignable to type of refined member 'sequence' in 'Iterable': the assigned type 'Element[]' is covered by, but not assignable to, the type '[Element+]|[]' (explicitly narrow assigned expression using 'of [Element+]|[]')
[ceylon-compile]     shared actual default Element[] sequence() => this;
[ceylon-compile]                           ^

Funnily enough, if I add the suggested of I get essentially the same error:

[ceylon-compile] /home/tom/ceylon/ceylon/language/src/ceylon/language/Sequential.ceylon:28: error: type of member must be assignable to type of refined member 'sequence' in 'Iterable': the assigned type 'Element[]' is covered by, but not assignable to, the type '[Element+]|[]' (explicitly narrow assigned expression using 'of [Element+]|[]')
[ceylon-compile]     shared actual default Element[] sequence() => this of [Element+]|[];
[ceylon-compile]                           ^

[tombentley]

@gavinking I'd like your feedback about this problem ^^ before proceeding further.

[jvasileff]

It looks like the (confusingly worded) error is complaining about the signature. Try this?

shared actual default [Element+]|[] sequence() => this of [Element+]|[];

[tombentley]

@gavinking I pushed some changes to the issue-6804 branch. Due to the problem I mentioned this change doesn't seem to be source compatible: The compiler won't allow existing refiners of sequence() continue to return Element[], they must use [Element+]|[].

At the java level though we will use raw Sequence or Sequential, where previously it was Sequence<? extends Element> or Sequentail<? extends Element>. The use of raw types should be OK.

Anyway, have an experiment on the branch and let me know if you need anything else doing.

[gavinking]

@tombentley Yes, I agree that it's not perfectly source-compatible, but that it is binary compatible.

If we think the loss of source-compatibility is a real problem, then I can certainly do something to hack that in the typechecker (replacing the error with a warning in this special case). But my sense is that there's not much code out there that refines Iterable.sequence(), and the cases which do exist can be easily fixed.

[gavinking]

OK, this change is now source- and binary- backward compatible. I have merged the branch!

Thanks @tombentley!

[xkr47]

Amazing, great!