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