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

[Dave Abrahams]

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