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

Fri Jul 1 10:59:23 CDT 2016

> On Jun 30, 2016, at 5:32 PM, Dave Abrahams via swift-evolution <swift-evolution at 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).

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

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

> 
>> 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
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160701/3548e93d/attachment.html>