<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&#39;t tell whether it already tried to refill the buffer). For example UTF8 &amp; UTF16&#39;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&#39;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&#39;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">&lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt;</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 &lt;<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>&gt; wrote:<br>
<br>
&gt; Hmm I see.<br>
&gt;<br>
&gt; Do we have any example cases where returning nil repeatedly would require<br>
&gt; 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>
&gt;<br>
&gt; The generators in the standard library don&#39;t (*) – the usual pattern is<br>
&gt; either of the following:<br>
&gt; - 1) Check state if we&#39;re at end, if so return nil 2) get return value 3)<br>
&gt; advance state. Since the state is not mutated before returning nil,<br>
&gt; repeating nil is automatic.<br>
&gt; - 1) Call next() on one or more wrapped generators 2) return some<br>
&gt; transformation of that. If the wrapped generators repeat nil, repeating nil<br>
&gt; is also automatic for the wrapper.<br>
&gt;<br>
&gt; If you would have a generator setup that doesn&#39;t automatically repeat nil,<br>
&gt; omitting a nil-repeat check might be dangerous considering the risk other<br>
&gt; code hadn&#39;t considered the case.<br>
&gt;<br>
&gt; (*) StrideThroughGenerator &amp; ZipGenerator have a done flag, but need these<br>
&gt; even without repeating nil. JoinGenerator has an .End state but actually<br>
&gt; doesn&#39;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>
&gt;<br>
&gt;<br>
&gt; On Thu, Mar 3, 2016 at 8:12 PM, Dmitri Gribenko &lt;<a href="mailto:gribozavr@gmail.com">gribozavr@gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt;&gt; On Wed, Mar 2, 2016 at 10:47 PM, Patrick Pijnappel via swift-evolution<br>
&gt;&gt; &lt;<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>&gt; wrote:<br>
&gt;&gt; &gt; Situation<br>
&gt;&gt; &gt; Currently GeneratorType.next() requires callers to not call next() after<br>
&gt;&gt; it<br>
&gt;&gt; &gt; has returned nil once, even encouraging a preconditionFailure() if this<br>
&gt;&gt; is<br>
&gt;&gt; &gt; violated:<br>
&gt;&gt; &gt;<br>
&gt;&gt; &gt;   /// - Requires: `next()` has not been applied to a copy of `self`<br>
&gt;&gt; &gt;   ///   since the copy was made, and no preceding call to `self.next()`<br>
&gt;&gt; &gt;   ///   has returned `nil`.  Specific implementations of this protocol<br>
&gt;&gt; &gt;   ///   are encouraged to respond to violations of this requirement by<br>
&gt;&gt; &gt;   ///   calling `preconditionFailure(&quot;...&quot;)`.<br>
&gt;&gt;<br>
&gt;&gt; I&#39;d like to add more context to this discussion.  We added this<br>
&gt;&gt; requirement a while ago.  [1]  The reason for introducing it was not<br>
&gt;&gt; an attempt to flag bugs in client code.  Rather, we were not convinced<br>
&gt;&gt; that all generators can return nil repeatedly without loss of<br>
&gt;&gt; efficiency or extra storage burden.<br>
&gt;&gt;<br>
&gt;&gt; [1]<br>
&gt;&gt; <a href="https://github.com/apple/swift/commit/304b4f33ae74a5abd09da485bbc435dfa2ade522" rel="noreferrer" target="_blank">https://github.com/apple/swift/commit/304b4f33ae74a5abd09da485bbc435dfa2ade522</a><br>
&gt;&gt; and rdar://problem/17392226<br>
&gt;&gt;<br>
&gt;&gt; &gt; Adds caller burden<br>
&gt;&gt; &gt; To avoid breaking the requirement, the caller will not uncommonly have<br>
&gt;&gt; to track extra state and branch<br>
&gt;&gt;<br>
&gt;&gt; I would actually say the opposite -- running a non-trivial algorithm<br>
&gt;&gt; on generators is a very uncommon thing to do.  The 99% use case for<br>
&gt;&gt; generators is implicit usage from the for-in loop.  This is why<br>
&gt;&gt; allowing generators to be as simple as possible and pushing the<br>
&gt;&gt; requirement for extra branches into non-trivial algorithms made sense<br>
&gt;&gt; for us when we introduced this requirement.<br>
&gt;&gt;<br>
&gt;&gt; &gt; Silent corner case<br>
&gt;&gt; &gt; Because basically all generators keep returning nil, it&#39;s not unlikely<br>
&gt;&gt; people will write their code based on the assumption it will always return<br>
&gt;&gt; nil<br>
&gt;&gt;<br>
&gt;&gt; This is what concerns me the most about the current rules.<br>
&gt;&gt;<br>
&gt;&gt; Dmitri<br>
&gt;&gt;<br>
&gt;&gt; --<br>
&gt;&gt; main(i,j){for(i=2;;i++){for(j=2;j&lt;i;j++){if(!(i%j)){j=0;break;}}if<br>
&gt;&gt; (j){printf(&quot;%d\n&quot;,i);}}} /*Dmitri Gribenko &lt;<a href="mailto:gribozavr@gmail.com">gribozavr@gmail.com</a>&gt;*/<br>
&gt;&gt;<br>
</div></div><span class="im HOEnZb">&gt; _______________________________________________<br>
&gt; swift-evolution mailing list<br>
&gt; <a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a><br>
&gt; <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>