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

[Dave Abrahams]

on Fri Mar 04 2016, Patrick Pijnappel <swift-evolution at swift.org> wrote:

>>
>> What algorithms or components can be simplified by taking advantage of this
>> extra guarantee?
>
> Any generator that somehow buffers their underlying generator (as it can't
> tell whether it already tried to refill the buffer). For example UTF8 &
> UTF16's decode() both have 3 instead of 2 branches on ASCII input because
> of this.
>
>> Off the top of my head: a stream of random numbers that stops when it
>> encounters
>> a zero.
>
> You could generate the next random number in advance (you take a O(1) hit
> instead of O(n)). Of course consuming more than you need is not always
> allowed and the O(1) could outweigh the branch.
>
> Overall I'd say performance-wise both categories are small (though taking
> the standard library as sample case, we have some examples of the former
> but not the latter).
>
> We'd be left with the safety concern of code which fails in rare corner
> cases.

Thanks, this is helpful.  I'm leaning in favor of making the change.

> On Sat, Mar 5, 2016 at 11:30 AM, Dave Abrahams via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>>
>> on Thu Mar 03 2016, Patrick Pijnappel <swift-evolution at swift.org> wrote:
>>
>> > Hmm I see.
>> >
>> > Do we have any example cases where returning nil repeatedly would require
>> > extra branches or state?
>>
>> Off the top of my head: a stream of random numbers that stops when it
>> encounters a zero.
>>
>> >
>> > The generators in the standard library don't (*) – the usual pattern is
>> > either of the following:
>> > - 1) Check state if we're at end, if so return nil 2) get return value 3)
>> > advance state. Since the state is not mutated before returning nil,
>> > repeating nil is automatic.
>> > - 1) Call next() on one or more wrapped generators 2) return some
>> > transformation of that. If the wrapped generators repeat nil, repeating
>> nil
>> > is also automatic for the wrapper.
>> >
>> > If you would have a generator setup that doesn't automatically repeat
>> nil,
>> > omitting a nil-repeat check might be dangerous considering the risk other
>> > code hadn't considered the case.
>> >
>> > (*) StrideThroughGenerator & ZipGenerator have a done flag, but need
>> these
>> > even without repeating nil. JoinGenerator has an .End state but actually
>> > doesn't have to – even to repeat nil.
>>
>> What algorithms or components can be simplified by taking advantage of
>> this extra guarantee?  If the category of code that can use it is
>> broader than the category of generators that would suffer an overhead or
>> implementation complexity, it might be worth doing.
>>
>> My intuition is that both categories are small.
>>
>> >
>> >
>> > On Thu, Mar 3, 2016 at 8:12 PM, Dmitri Gribenko <gribozavr at gmail.com>
>> wrote:
>> >
>> >> On Wed, Mar 2, 2016 at 10:47 PM, Patrick Pijnappel via swift-evolution
>> >> <swift-evolution at swift.org> wrote:
>> >> > Situation
>> >> > Currently GeneratorType.next() requires callers to not call next()
>> after
>> >> it
>> >> > has returned nil once, even encouraging a preconditionFailure() if
>> this
>> >> is
>> >> > violated:
>> >> >
>> >> >   /// - Requires: `next()` has not been applied to a copy of `self`
>> >> >   ///   since the copy was made, and no preceding call to
>> `self.next()`
>> >> >   ///   has returned `nil`.  Specific implementations of this protocol
>> >> >   ///   are encouraged to respond to violations of this requirement by
>> >> >   ///   calling `preconditionFailure("...")`.
>> >>
>> >> I'd like to add more context to this discussion.  We added this
>> >> requirement a while ago.  [1]  The reason for introducing it was not
>> >> an attempt to flag bugs in client code.  Rather, we were not convinced
>> >> that all generators can return nil repeatedly without loss of
>> >> efficiency or extra storage burden.
>> >>
>> >> [1]
>> >>
>> https://github.com/apple/swift/commit/304b4f33ae74a5abd09da485bbc435dfa2ade522
>> >> and rdar://problem/17392226
>> >>
>> >> > Adds caller burden
>> >> > To avoid breaking the requirement, the caller will not uncommonly have
>> >> to track extra state and branch
>> >>
>> >> I would actually say the opposite -- running a non-trivial algorithm
>> >> on generators is a very uncommon thing to do.  The 99% use case for
>> >> generators is implicit usage from the for-in loop.  This is why
>> >> allowing generators to be as simple as possible and pushing the
>> >> requirement for extra branches into non-trivial algorithms made sense
>> >> for us when we introduced this requirement.
>> >>
>> >> > Silent corner case
>> >> > Because basically all generators keep returning nil, it's not unlikely
>> >> people will write their code based on the assumption it will always
>> return
>> >> nil
>> >>
>> >> This is what concerns me the most about the current rules.
>> >>
>> >> Dmitri
>> >>
>> >> --
>> >> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
>> >> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/
>> >>
>> > _______________________________________________
>> > swift-evolution mailing list
>> > swift-evolution at swift.org
>> > https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>> --
>> -Dave
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
-Dave