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 >> <swift-evolution@swift.org> 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. >> 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 ;-) >> 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. >>> On Thu, Jun 30, 2016 at 12:26 Dave Abrahams via swift-evolution < >>> swift-evolution@swift.org> 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 < >>>> swift-evolution@swift.org> 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 >>>> swift-evolution@swift.org >>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>> >> >> -- >> Dave >> _______________________________________________ >> swift-evolution mailing list >> swift-evolution@swift.org <mailto:swift-evolution@swift.org> >> https://lists.swift.org/mailman/listinfo/swift-evolution >> <https://lists.swift.org/mailman/listinfo/swift-evolution> -- Dave _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution