On Fri, Jul 1, 2016 at 11:51 AM, Dave Abrahams via swift-evolution < [email protected]> wrote:
> > on Fri Jul 01 2016, Matthew Johnson <matthew-AT-anandabits.com> wrote: > > >> On Jun 30, 2016, at 12:26 PM, Dave Abrahams <[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 > > > > I definitely think it’s worth doing. > > Opinions are nice, but rationales are better. How will we understand > *why* it's worth doing? > > > I really appreciate the attention that the library team has given to > > this. > > > >> , 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 { … } > > > > Does this design entirely break with the relationship between > > collections and iterators (dropping `makeIterator` as a protocol > > requirement)? If so, would for..in (over collections) be built on top > > of indices and use `formIndex(after:)`? Would it require a finite > > collection (unless we add `until` to the language and then allow > > `for..in..until` to work with infinite collections)? > > All of these points are up for discussion. John McCall pointed out to > me that an index-based for..in would make it possible to implement > > for inout x in y { mutate(&x) } > > > Would we still retain `IndexingIterator`even if we break the > > relationship in the protocol requirements? > > Yes: it should be possible to implement Collection algorithms in terms > of Iterator algorithms, and IndexingIterator provides the means. That > said, I think the makeIterator requirement does little harm, especially > when it can be defaulted for Collections. > > > Would it still be possible to do things like zip a multi-pass sequence > > with a single-pass sequence (assuming we keep single-pass sequences or > > add them back eventually)? This seems like a use case worth > > supporting in some way. > > Yes. If you can create an Iterator from a Collection, and you can zip > Iterators, you can do this. > > > One subtle change I think this implies is that things like > > `LazyFilterSequence` can implement `makeIterator` with constant > > complexity, deferring the O(N) complexity to the first call to `next`. > > I don't believe that's a difference, though I could be wrong. > > > `startIndex` for `LazyFilterCollection` currently has O(N) complexity. > > The complexity of a complete iteration doesn’t change and probably > > isn’t a big deal, but it’s worth noting. > > Filtered collection views always require a bit of hand-waving around > performance guarantees; I don't think that changes. > > > I’ve been looking at some code that wraps a sequence and considering > > how it would be impacted. With iterators it looks like this: > > > > guard let element = base.next() > > else { return nil } > > > > With collections and indices it would look something like this: > > > > base.formIndex(after: &index) > > guard index != baseEndIndex > > else { return endIndex } > > > > let element = base[index] > > > > That’s not too bad but it is more verbose. > > Sequence today is a single-pass thing. If you are wrapping Sequence > today presumably you'd wrap an Iterator tomorrow, and you wouldn't have > to deal with indices. > > > If we’re going to push people towards collections and indices we > > should try to make common patterns like “update the iteration state > > and return the next element if there is one" simpler. > > That's IndexingIterator. > > > This could be accomplished with an extension method along these lines: > > > > guard let element = base.formIndex(after: &index, > > .returningOptionalElement) > > else { return endIndex } > > > > With an implementation something like: > > > > enum FormIndexResult { > > .returningOptionalElement > > } > > extension Collection { > > func formIndex(after i: inout Self.Index, _ result: > > FormIndexResult) -> Self.Element? > > } > > > > This would provide similar functionality to `IndexingIterator` without > > coupling the storage of `elements` and `position` (which is important > > if you’re wrapping a collection and need to wrap the collection and > > its indices independently). > > I'm afraid I don't understand. Could you be more explicit about what > you have in mind? > > >> 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. > > > > It’s also worth nothing that we can use `Optional` with `nil` as the > > `endIndex` sentinel if necessary. > > True, that's a useful technique when there's no underlying storage in > the collection (e.g. a fibonacci sequence) > > >> > >> ## 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. > > > > Makes sense to me. > > > >> > >> ### 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. > > > > I think this makes a lot of sense in the model you are proposing. All > > multipass structures are collections. Any sequence that can only > > support a single pass is modeled as an iterator which inherently has > > identity. Making this distinction strong will prevent any confusion. > > > >> 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. > > > > I’m happy to see you mention a mutation model for class instances! (I > > don’t mean to sidetrack the discussion, but would love to see that > > someday) > > > > I don’t have any objection to dropping support for single-pass > > sequences temporarily. It’s possible that I would feel differently if > > I was making use of them in my own code but I’m not. > > On second thought, I believe it is important to have a way to support > existing “partially formed” multipass sequences that don't expose > copying or equality for their iteration states. Iterator is the right > way to do that. So I think we need to keep Iterator around. > > > In the meantime, people would be able to implement their own protocol > > for single pass sequences. What they would lose is for..in as well as > > the standard library algorithms. I’m not sure how many people this > > would impact or how big the impact would be for them. We have seen a > > couple of examples in this discussion, but probably not enough to > > asses the overall impact. > > > > One thing you don’t mention here is a distinction between finite and > > infinite single-pass sequences (iterators). I don’t know if the > > finite / infinite distinction is as important here, but wanted to > > point it out. Obviously if we remove support single-pass sequences > > now we could defer that discussion until we’re ready to bring back > > support for them. > > There are a few possible answers I can think of: > > 1. Do the “obvious” thing and create a separate protocol for finite > single-pass sequences > > 2. Decide that the combination of infinite and single-pass is rare > enough (/dev/urandom, temperature sensor) that it's better to just > ask people handling them to be careful and not, e.g., try to “count” > them. > Not really feeling sufficiently in my element (excuse the pun) to comment on most of this discussion, but here I thought I'd chime in. What's interesting about your two examples (/dev/urandom, temperature sensor) is that, though single-pass, they should be insensitive to destructive consumption, no? By which I mean, if some function returns 5 elements from the "sequence", in both scenarios it would be undetectable whether it consumes 5, 10 or 15 elements in the process, IIUC. Are there other examples of infinite, single-pass sequences where destructive consumption would make a difference? > > 3. Decide that everything on a single-pass sequence is lazy. Since you > can only take a single pass anyway, people won't observe their > closures being called more often than necessary, which was the main > motivator for making map, filter, et. al eager on collections without > an explicit .lazy. > > Implications of #3: > > * Any “partially-formed” multipass sequences (modeling only Iterator) > would be free to expose an accurate underestimatedCount, thereby > optimizing the process of copying into an array. The lazy filter > Iterator adaptor would have an underestimatedCount of 0. > > * All algorithms that require multiple passes, such as sorted(), would > be unavailable on Iterator. You'd have to construct an Array (or > other MutableCollection) and sort that in-place. Of course, > constructing an Array from an Iterator could still go on forever if > the Iterator turned out to be infinite, which means, at some level #3 > is just a refinement of #2 that makes it less error-prone. > > -- > Dave > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution >
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
