[swift-evolution] [Pitch] Remove destructive consumption from Sequence

[Dave Abrahams]

on Thu Jun 30 2016, Xiaodi Wu <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.  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.

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.

> 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
>>

-- 
Dave