> On Jul 1, 2016, at 11:07 AM, Dave Abrahams <[email protected]> wrote: > > > on Fri Jul 01 2016, Matthew Johnson <matthew-AT-anandabits.com> wrote: > >>> 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). > > It does, but I am ever more strongly motivated to drop the comparability > requirement.
Dropping that would eliminate the questions that are still lingering in my mind about getting rid of `Sequence`. Are there any important algorithms that rely on the ability to compare indices? > >>> 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? > > Comparabile refines Equatable, so it's at *least* as hard ;-) Right. You only mentioned that index equality could have been exposed but didn’t mention comparability. I was wondering whether the potential additional difficulty is why they couldn’t 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. >> >> Can you elaborate on what designs / data structures you’re talking >> about here? > > Cocoa Dictionaries and Sets are examples. The enumeration interface > doesn't have any facility for copying or comparing enumeration state. What impact would that have on the bridged value types (which is how we should be using those in Swift). > >>>> 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> > > -- > Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
