yieldAll and recursive generators

[ilya-g]

Investigate whether it's possible to implement efficient tail-recursive generators with yieldAll suspension function and the nested iterators technique, described here: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/specsharp-iterators.pdf

fun fromTo(from: Int, to: Int) = generate {
    if (from > to) return
    yield(from)
    yieldAll(fromTo(from + 1, to))
}

[h0tk3y]

I'm currently investigating this. As to the tail-recursive generators, seems like we can only achieve that using handleResult(), which requires a coroutine to return the tail sequence:

fun fromTo(from: Int, to: Int) = generateWithTail f@{
    if (from > to) return@f emptySequence()
    yield(from)
    return@f fromTo(from + 1, to)
}

As far as I understand, there's no other way to learn whether a nested iterator yield is the last suspension in the block and the continuation is actually a NOP that will immediately finish the coroutine block. I guess it would require some continuation metadata (though not much). Or is there already a way to learn that?

[elizarov]

buildSequence is not a part of stdlib with both yield and yieldAll support provided out-of-the-box.

[ilya-g]

Note that the mentioned nested iterator optimization is not implemented.

[elizarov]

It actually is conceptually available with suspending functions in even nicer way:

suspend tailrec fun SequenceBuilder<Int>.fromTo(from: Int, to: Int) {
    if (from > to) return
    yield(from)
    fromTo(from + 1, to)
}

then do buildSequence { fromTo(1, 1000) } (crashed backend right now, though)