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

Matthew Johnson matthew at anandabits.com
Fri Jul 1 11:19:39 CDT 2016 

> On Jul 1, 2016, at 11:07 AM, Dave Abrahams <dabrahams at apple.com> wrote:
> 
> 
> on Fri Jul 01 2016, Matthew Johnson <matthew-AT-anandabits.com> wrote:
> 
>>> 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).
> 
> It does, but I am ever more strongly motivated to drop the comparability
> requirement.

Dropping that would eliminate the questions that are still lingering in my mind about getting rid of `Sequence`.

Are there any important algorithms that rely on the ability to compare indices?

> 
>>> 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?
> 
> Comparabile refines Equatable, so it's at *least* as hard ;-)

Right.  You only mentioned that index equality could have been exposed but didn’t mention comparability.  I was wondering whether the potential additional difficulty is why they couldn’t 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.
>> 
>> Can you elaborate on what designs / data structures you’re talking
>> about here?
> 
> Cocoa Dictionaries and Sets are examples.  The enumeration interface
> doesn't have any facility for copying or comparing enumeration state.

What impact would that have on the bridged value types (which is how we should be using those in Swift).

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

More information about the swift-evolution mailing list