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?
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 >
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
