> On Jun 30, 2016, at 5:32 PM, Dave Abrahams via swift-evolution > <[email protected]> wrote: > > > on Thu Jun 30 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com > <http://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.
It’s worth noting that indices require comparability, not just equality. I think comparability might cause more difficulty than equality (but haven’t thought too hard about it). > 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. Why can’t they be adapted to model Collection if equality could have been exposed? Is it because comparability would be difficult? > > 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. Can you elaborate on what designs / data structures you’re talking about here? > >> 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] <mailto:[email protected]> > https://lists.swift.org/mailman/listinfo/swift-evolution > <https://lists.swift.org/mailman/listinfo/swift-evolution>
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
