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