[swift-evolution] [Pitch] Remove destructive consumption from Sequence
Dave Abrahams
dabrahams at apple.com
Fri Jul 1 11:07:19 CDT 2016
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.
>> 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 ;-)
>> 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.
>>> 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