[swift-evolution] [Pitch] Remove destructive consumption from Sequence
Matthew Johnson
matthew at anandabits.com
Wed Jun 22 20:12:07 CDT 2016
> On Jun 22, 2016, at 6:41 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>
>
> on Wed Jun 22 2016, Matthew Johnson <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>
>>> On Jun 22, 2016, at 3:57 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>
>>>
>>> on Wed Jun 22 2016, David Waite <swift-evolution at swift.org> wrote:
>>>
>>
>>>> Today, a Sequence differs from a Collection in that:
>>>>
>>>> - A sequence can be infinitely or indefinitely sized, or could require
>>>> an O(n) operation to count the values in the sequence.
>>>
>>> The latter being no different from Collection.
>>>
>>>> A collection has a finite number of elements, and the fixed size is
>>>> exposed as an O(1) or O(n) operation via ‘count’
>>>
>>> I don't believe we've actually nailed down that Collection is finite.
>>>
>>> Oh, gee, Nate's documentation edits do
>>> that. (https://github.com/apple/swift/commit/6e274913)
>>> Nate, did we discuss this explicitly or did it slip in unnoticed?
>>>
>>> The one crucial distinction in Collection is that you can make multiple
>>> passes over the same elements.
>>>
>>>> - A collection is indexable, with those indices being usable for
>>>> various operations including forming subsets, comparisons, and manual
>>>> iteration
>>>>
>>>> - A sequence may or may not be destructive, where a destructive
>>>> sequence consumes elements during traversal, making them unavailable
>>>> on subsequent traversals. Collection operations are required to be
>>>> non-destructive
>>>>
>>>> I would like to Pitch removing this third differentiation, the option
>>>> for destructive sequences.
>>>
>>> I have been strongly considering this direction myself, and it's
>>> something we need to decide about for Swift 3.
>>
>> I believe this is a problem that should be solved.
>>
>> I also believe distinguishing between finite and infinite sequences is
>> a good idea (along with preventing for..in from being used with an
>> infinite sequence)
>
> for..in over an infinite sequence is not necessarily wrong. I'm not
> confident it should be prevented. It's certainly less dangerous than
> using `forEach`, from which there is no possibility of escape.
Sure, it’s not wrong in the sense that sometimes an infinite loop is valid. But I think it would almost always be wrong (an accident) in practice. If you really want to loop over an infinite sequence maybe it’s a good thing to require you to do that explicitly.
>
>>>> My main motivation for proposing this is the potential for developer
>>>> confusion. As stated during one of the previous threads on the naming
>>>> of map, flatMap, filter, etc. methods on Sequence, Sequence has a
>>>> naming requirement not typical of the rest of the Swift standard
>>>> library in that many methods on Sequence may or may not be
>>>> destructive. As such, naming methods for any extensions on Sequence is
>>>> challenging as the names need to not imply immutability.
>>>
>>> I don't think the names are really the worst potential cause of
>>> confusion here. There's also the fact that you can conform to Sequence
>>> with a destructively-traversed “value type” that has no mutating
>>> methods.
>>
>> I agree, names are not the primary issue.
>>
>> Another issue is that you cannot currently write generic code that
>> might need to iterate a sequence more than once. You currently have
>> to over-constrain types to `Collection` even if you don’t need to do
>> anything other than iterate the elements (the discussion about whether
>> `LazyFilterSequnce` has a bug in its `underestimateCount` is relevant
>> here).
>
> That's not an over-constraint. Multi-pass-ness *is* the fundamental
> distinction between Sequence and Collection. AFAIK there's no multipass
> sequence that cannot support indices.
If we do nail down that Collection has to be finite then this is not the case. There are infinite multipass sequences.
If we require Sequence to be multipass (that is the same as removing destructive consumption, isn’t it?) then what would be the distinction between Sequence and Collection? The fact that we are making Collection finite?
>
>>>> It would still be possible to have Generators which operate
>>>
>>> <Ahem> “Iterators,” please.
>>>
>>>> destructively, but such Generators would not conform to the needs of
>>>> Sequence. As such, the most significant impact would be the inability
>>>> to use such Generators in a for..in loop,
>>>
>>> Trying to evaluate this statement, it's clear we're missing lots of
>>> detail here:
>>>
>>> * Would you remove Sequence?
>>> * If so, what Protocol would embody “for...in-able?”
>>> * If not, would you remove Collection?
>>> * What role would Iterator play?
>>
>> If we’re going to consider alternative designs it is worth considering
>> the semantic space available. For the sake of discussion, here is a
>> model that captures the various semantics that exist (the names are
>> just strawmen):
>>
>> Iterable
>> / \
>> / \
>> / \
>> FiniteIterable MultipassIterable
>> \ /
>> \ /
>> \ /
>> Sequence
>> |
>> |
>> Collection
>>
>> `Iterable` corresponds to the current `Sequence` - no semantics beyond
>> iteration are required. Infinite, single-pass “sequences” may
>> conform.
>
> Just to keep things straight, let's please adjust one thing at a time.
> Adding new concepts should be separated from renaming existing ones. I
> don't want to have to qualify “Sequence” every time I use it in this
> thread to clarify whether I mean the existing one or what you're
> proposing.
>
I should have avoided using the name “Sequence” here just to keep things more clear. Sorry about that.
>> `for..in` naturally requires `FiniteIterable`,
>
> I'm less than confident.
See above.
>
> FWIW, I'm also not entirely confident that single-pass things should be
> part of *this* picture at all. It might be that single-pass things
> should be entirely separate and forced to be reference types where
> traversal mutates the instance.
This seems like a reasonable direction.
> E.g., the current Iterator could gain a
> class constraint and become the only representation of single-pass
> sequences.
Hmm. I would have to give this more thought. Do we really want to require all conformances of `Iterator` to be reference types? What would be the performance impact of that?
>
>> but does not require the `MultipassIterable`.
>>
>> There are many interesting infinite `MultipassIterable` types. These
>> include any dynamically generated sequence, such as a mathematical
>> sequence (even numbers, odd numbers, etc).
>
> These are all potential Collections, AFAICT. I see no reason they
> shouldn't be treated as such.
If we allow Collections to be infinite.
>
>> This is also what the existing `Sequence` would become if we drop
>> support for destructive sequences and do nothing else (note: it would
>> still be possible to accidentally write a `for..in` loop over an
>> infinite sequence).
>>
>> Under this model `Sequence` brings together `FiniteIterable` and
>> `MultipassIterable`. This describes the most common models of
>> `Sequence`, can safely be used in a `for..in` loop, and does support
>> “destructive” single pass sequences.
>>
>> `FiniteIterable` and `MultipassIterable` introduce independent and
>> important semantic requirements. If we’re going to consider changes
>> here, I think it is worth at least considering introducing the
>> distinction.
>>
>> This is obviously much more complex than than the current design.
>
> Another reason I'm reluctant. Whatever we do, IMO, should simplify things.
Sure. I’m not actually proposing we implement this model, I am just trying to explore the design space and think through how we can simplify by introducing desirable semantic requirements.
I think part of the complexity of the current model is due to the protocols not introducing semantic requirements that the most heavily used models actually support. Making it clear where multipass is valid and making a distinction between finite and infinite sequences will simplify things IMO. Figuring out the best way to organize them is the tricky part. I think Brent is heading in the right direction in his post.
>
>> The most obvious simplification would be to drop `Iterable` if we
>> don’t have any compelling use cases for infinite, single pass
>> sequences. One downside to doing this is that the syntactic
>> requirements would need to be repeated in both `FiniteIterable` and
>> `MultipassIterable`
>>
>> Another obvious simplification would be to also remove `Sequence`
>> (which becomes a “convenience” protocol under this model) and require
>> types that can conform to both `FiniteIterable` and
>> `MultipassIterable` to do so directly.
>>
>> If chose to make both simplifications we could also rename the
>> remaining `FiniteIterable` and `MultipassIterable` to something
>> simpler like `Iterable` and `Sequence`.
>>
>> (for..in) (the existing `Sequence` with an additional multipass semantic requirement)
>> Iterable Sequence
>> \ /
>> \ /
>> \ /
>> Collection
>>
>> I’m interested in hearing what others think about this way of thinking about the available design space.
>>
>> -Matthew
>>
>>>
>>>
>>> --
>>> Dave
>>>
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>> _______________________________________________
>> 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
>
> _______________________________________________
> 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/20160622/fb9cb75e/attachment-0001.html>
More information about the swift-evolution
mailing list