If Iterators become reference types that model single-pass sequences and becomes for-in-able, as the write-up suggests, couldn&#39;t Sequence be stipulated to be multipass and retain its refinement relationship with Collection?<br><br><div class="gmail_quote"><div dir="ltr">On Thu, Jun 30, 2016 at 12:26 Dave Abrahams via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
on Wed Jun 29 2016, Haravikk &lt;swift-evolution-AT-haravikk.me&gt; wrote:<br>
<br>
&gt;&gt; On 29 Jun 2016, at 00:10, Matthew Johnson via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
&gt;&gt;<br>
&gt;&gt; Swift is a language that embraces value semantics.  Many common<br>
&gt;&gt; iterators *can* be implemented with value semantics.  Just because we<br>
&gt;&gt; can’t implement *all* iterators with value semantics doesn’t mean we<br>
&gt;&gt; should require them to have reference semantics.  It just means you<br>
&gt;&gt; can’t *assume* value semantics when working with iterators in generic<br>
&gt;&gt; code unless / until we have a way to specify a value semantics<br>
&gt;&gt; constraint.  That’s not necessarily a bad thing especially when it<br>
&gt;&gt; leaves the door open to interesting future possibilities.<br>
&gt;&gt;<br>
&gt;&gt; -Matthew<br>
&gt;<br>
&gt; I&#39;m kind of undecided about this personally. I think one of the<br>
&gt; problems with Swift is that the only indication that you have a<br>
&gt; reference type is that you can declare it as a constant, yet still<br>
&gt; call mutating methods upon it, this isn&#39;t a very positive way of<br>
&gt; identifying it however. This may be more of a GUI/IDE issue though, in<br>
&gt; that something being a class isn&#39;t always that obvious at a glance.<br>
&gt;<br>
&gt; I wonder, could we somehow force iterators stored in variables to be<br>
&gt; passed via inout? This would make it pretty clear that you&#39;re using<br>
&gt; the same iterator and not a copy in all cases, encouraging you to<br>
&gt; obtain another if you really do need to perform multiple passes.<br>
<br>
I&#39;m going to push single-pass iteration on the stack briefly and talk<br>
about the topic that&#39;s been under discussion here: infinite multipass<br>
sequences.<br>
<br>
## Fitting “Infinite Multipass” Into the Model<br>
<br>
It remains to be decided whether it&#39;s worth doing, but if it&#39;s to<br>
happen, the standard library team thinks the right design is roughly<br>
this:<br>
<br>
  /// A multipass sequence that may be infinite<br>
  protocol Collection {<br>
<br>
    // Only eager algorithms that can terminate available here<br>
    func index(where predicate: (Element)-&gt;Bool) -&gt; Index<br>
<br>
    // all lazy algorithms available here<br>
    var lazy: ...<br>
<br>
    var startIndex: Index<br>
    var endIndex: Index // possibly not reachable from startIndex<br>
<br>
    associatedtype SubSequence : Collection<br>
    // do we need an associated FiniteSubsequence, e.g. for prefixes?<br>
  }<br>
<br>
  protocol FiniteCollection : Collection {<br>
<br>
    // All eager algorithms available here<br>
    func map(...) -&gt;<br>
    var count: ...<br>
  }<br>
<br>
  protocol BidirectionalCollection : Collection { ... }<br>
<br>
  protocol RandomAccessCollection : BidirectionalCollection { ... }<br>
<br>
Q: Why should there be indices on an infinite multipass sequence?<br>
A: Because the operations on indices apply equally well whether the<br>
   sequence is finite or not.  Find the index of a value in the<br>
   sequence, slice the sequence, find again, etc.<br>
<br>
Q: Why is there an endIndex on an infinite seque?<br>
A: So you can write algorithms such as index(where:) once.<br>
<br>
Q: Why not allow endIndex to have a different type from startIndex?<br>
A: It appears to offer insufficient benefit for the associated<br>
   complexity in typical usage.  A classic use case that argues for a<br>
   different endIndex type is the null-terminated C string.  But you<br>
   can&#39;t index one of those safely without actually counting the length,<br>
   and once you&#39;ve done that you can make the endIndex an Int.<br>
<br>
## Single Pass Iteration<br>
<br>
The refinement relationship between Sequence and Collection is<br>
problematic, because it means either:<br>
<br>
a) algorithms such as map on single-pass sequences claim to be<br>
   nonmutating even though it&#39;s a lie (status quo)<br>
<br>
b) those algorithms can&#39;t be used on immutable (“let bound”) multipass<br>
   sequences. IMO that would be totally unacceptable.<br>
<br>
If we drop the refinement, we can have a saner world.  We also don&#39;t<br>
need to separate Sequence and Iterator anymore.  We can simply drop<br>
Sequence altogether, and the protocol for single-pass iteration becomes<br>
Iterator.<br>
<br>
### Mutation and Reference Semantics<br>
<br>
Everything in Swift is copiable via `let copy = thing` (let&#39;s please not<br>
argue over the definition of copy for classes; this is the one built<br>
into the lowest level of the language—I refer to the other one, that<br>
requires allocation, as “clone”).<br>
<br>
Anything you do with a sequence that&#39;s truly single-pass mutates the<br>
sequence *and of its copies*.  Therefore, such a type *fundamentally*<br>
has reference semantics. One day we may be able to model single-pass<br>
sequences with “move-only” value types, which cannot be copied. You can<br>
find move-only types in languages like Rust and C++, but they are not<br>
supported by Swift today.  So it seems reasonable that all Iterators in<br>
Swift today should be modeled as classes.<br>
<br>
The fact that Swift doesn&#39;t have a mutation model for classes, though,<br>
means that mutating methods on a class constrained protocol can&#39;t be<br>
labeled as such.  So consuming operations on a class-constrained<br>
Iterator protocol would not be labeled as mutating.<br>
<br>
The standard library team is currently trying to evaluate the tradeoffs<br>
in this area.  One possibility under consideration is simply dropping<br>
support for single-pass sequences until Swift can support move-only<br>
value types and/or gets a mutation model for class instances.  It would<br>
be very interesting to know about any real-world models of single-pass<br>
sequences that people are using in Swift, since we don&#39;t supply any in<br>
the standard library.<br>
<br>
--<br>
Dave<br>
_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org" target="_blank">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>
</blockquote></div>