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

[Patrick Pijnappel]

>
> 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.


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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160305/4ec29c07/attachment.html>