[swift-evolution] [Proposal] Change guarantee for GeneratorType.next() to always return nil past end

[Dave Abrahams]

on Sat Mar 05 2016, Kevin Ballard <swift-evolution at swift.org> wrote:

> On Thu, Mar 3, 2016, at 03:24 AM, Patrick Pijnappel via swift-evolution wrote:
>> Hmm I see.
>>
>> Do we have any example cases where returning nil repeatedly would
>> require extra branches or state?
>
> Yes. My proposed .takeWhile() and .dropWhile() sequence adaptors
> (https://github.com/apple/swift-evolution/pull/95) would hit this case.
> Both of those adaptors would need to keep around extra state and in
> order to keep returning nil.

Are there realistic cases where this state and check would produce
measurable overhead?

Do you have an implementation somewhere I could look at?

> My preferred solution for this case is to add a new Generator adaptor
> called a FuseGenerator, with a convenience method .fuse(). All this
> adaptor does is include the extra state in order to ensure it keeps
> returning nil forever. This way Generators don't have to keep the state
> for that guarantee, and the majority case where client codes doesn't
> rely on this guarantee doesn't need the check either, and in the rare
> case where this guarantee is important all the user has to do is call
> .fuse() on the generator and use the result of that instead.

Between the lack of predictability being addressed here and the addition
of a rarely-used additional component, that's a lot of complexity in the
library; is there a clear benefit?

> All that said, I would be strongly in favor of dropping the language
> about triggering a precondition failure. I'd prefer to leave it as implementation-
> defined behavior, which an encouragement to keep returning nil if it's
> easy to do so. A benefit of this is Generators could opt to explicitly
> define their post-nil behavior, e.g. TakeWhileGenerator could explicitly
> document that after it has returned nil, subsequent calls to .next()
> will continue to consume the underlying generator and return another
> stream of elements terminating in `nil` (with the caveat that if the
> underlying generator is exhausted then behavior depends on the
> underlying generator's post-nil behavior). Granted, this probably isn't
> useful in most cases, but it could be useful upon occasion as a way to
> lazily split a sequence without building intermediate data structures
> (assuming that the underlying generator is fused or defines its post-nil
> behavior as returning nil forever).

TakeWhileGenerator could also provide a method that returns the
TakeWhileGenerator for the next segment.  Since you have to know that
you've got a TakeWhileGenerator to take advantage of this special
behavior, a different interface is just as useful and probably results
in clearer code.  

> FWIW, Rust uses precisely the solution I've described here (and in fact
> I'm responsible for its std::iter::Fuse iterator). It defines
> Iterator::next() such that calling .next() after it has returned None
> may or may not return more elements (but Iterators are not supposed to
> assert in this case, they should always return something). And it has
> the .fuse() convenience method that returns a std::iter::Fuse iterator
> that provides the always-returns-None guarantee. And in practice, almost
> nobody ever has to actually use .fuse(), since almost nobody writes
> algorithms that cares about the behavior after next() returns None (and
> in the rare case where they do, they're typically using some concrete
> Iterator that has defined behavior, as opposed to working on arbitrary
> Iterators).

This is about balancing performance, flexibility, simplicity of
specification, and predictability.  Rust has a very C++-like approach to
zero-overhead abstractions, in the sense that it's willing to introduce
many small wrinkles to avoid even the theoretical possibility of a
performance penalty.  Having cut my language/library-design teeth in the
C++ world, I understand that approach really well, but I have also seen
it do some damage (some of which I was personally responsible for!) and
I want to be more conservative with Swift.  In short, I'm still leaning
towards specifying post-nil behavior, and I'd want to have more evidence of
the value of leaving it unspecified before doing so.

-- 
-Dave