[swift-evolution] [Pitch] Remove destructive consumption from Sequence
Xiaodi Wu
xiaodi.wu at gmail.com
Thu Jun 30 12:36:10 CDT 2016
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 <
swift-evolution at 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 at 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 at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160630/c4ad842b/attachment.html>
More information about the swift-evolution
mailing list