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

[Matthew Johnson]

> On Jun 27, 2016, at 11:46 AM, Dave Abrahams <dabrahams at apple.com> wrote:
> 
> 
> on Mon Jun 27 2016, Matthew Johnson <matthew-AT-anandabits.com <http://matthew-at-anandabits.com/>> wrote:
> 
>>> On Jun 26, 2016, at 10:56 PM, Jonathan Hull via swift-evolution
>>> <swift-evolution at swift.org> wrote:
>>> 
>>> Can’t a Sequence be potentially infinite, whereas a collection has a
>>> defined count/endIndex?  Other than that, I agree with your
>> 
>>> statement.
>>> 
>>> Here is what I see as the appropriate structure:
>>> 
>>> Iterator: Single destructive pass, potentially infinite, (should be for-in able)
>>> Sequence: Guaranteed non-destructive multi-pass (vends Iterators),
>>> potentially infinite, (should be subscript-able, gain most of
>>> collection, but lose anything that relies on it ending)
>>> Collection: Multi-pass, guaranteed finite, (no changes from current
>>> form, except extra inits from Iterator/Sequence with end conditions)
>>> 
>>> Right now we are allowed to have an infinite sequence, but calling
>>> dropLast or non-lazy map will cause an infinite loop.  These cases
>>> could be made much safer by considering the potentially infinite and
>>> finite cases separately…
>> 
>> I think this is pointing in the right general direction.  It would
>> make working with `Sequence` much more straightforward and allow us to
>> depend on the multi-pass property that is true in practice of the most
>> common models of `Sequence`.
>> 
>> But I agree that we should give much more careful consideration to
>> finite / infinite generally and for..in specifically.
>> 
>> Now that I have been thinking about the finite / infinite distinction
>> more closely I have begun to notice a lot of code that is written
>> generically using `Sequence` where a for..in loop is really what is
>> required, however the “finite sequence” precondition is not explicitly
>> stated.  Interestingly, this is the case with the standard library’s
>> eager `map` (but not the case with `dropLast` which explicitly notes
>> the precondition).  I have been somewhat surprised to realize how
>> common this “bug” is (i.e. not stating a precondition).  I think we
>> have gotten away with it thus far because the sequences most people
>> use most of the time in practice are finite.  But that doesn’t mean we
>> should accept this as good enough - IMO it is way to easy to forget to
>> document this precondition (and obviously easier for users to overlook
>> than preconditions that are actually encoded in the type system,
>> violations of which are caught at compile time).
>> 
>> The fact that this pattern is so pervasive is what I meant when I said
>> for..in “naturally” requires a finite sequence.
>> 
>> IMO it’s better to encode preconditions in the type system when that
>> is practical, and especially when the precondition is shared by a vast
>> majority of code written using a particular construct (in this case a
>> for..in loop written using the most generic for..in-able protocol).
>> 
>> I think the safest solution is to take the position that writing an
>> infinite loop is relatively uncommon and is a more “advanced”
>> technique, and thus should be done explicitly.  Do people really write
>> infinite loops often enough that the convenience of using for..in when
>> writing infinite loops outweighs the safety benefit of preventing
>> accidental infinite loops?  I haven’t seen a compelling argument for
>> this.
> 
> Good questions.  I'd also add: “do infinite sequences come up often
> enough that accidentally looping on them forever is a problem?”

That’s a good question as well.  In practice the frequency of infinite sequences likely depends on the domain.

IMO this falls into the same category as “do single pass sequences come up often enough that attempting to iterate over them twice is a problem.  To paraphrase your previous post:

> Today, people see a beautiful, simple protocol (Sequence) to which many
> things conform. They don't recognize that there's a semantic restriction
> (you can’t assume it is finite!) on it, so they write libraries
> of functions that may iterate a Sequence to termination.  They test
> their libraries with the most commonly-available Sequences, e.g. Arrays
> and Ranges, which happen to be finite.  Their tests pass!  But their
> constraints are wrong, their whole model of how to write generic code
> over sequences is wrong, and some of their code is wrong.
> 
> IMO this is a problematic programming model.


I definitely don’t mean to put words in your mouth here, but the logical structure of the argument appears identical to me regardless of which issue it is applied to.  I am only trying to make that point.

> 
>> If we adopt that position then for..in would need to be built on top
>> of a guaranteed finite construct.  This would allow programmers to
>> continue writing generic code agains the most generic for..in-able
>> construct while eliminating a precondition that is often (usually?)
>> unstated and likely unconsidered.
>> 
>> If we do decide to move forward with infinite for..in loops I think we
>> need to establish strong guidance around how to properly write generic
>> code with these protocols.  Should such code really be constrained to
>> `Collection` rather than `Sequence` (i.e. should a potentially
>> infinite `Sequence` have an eager map)?  If this is the guidance,
>> should it be paired with guidance that all finite sequences should
>> conform to `Collection`?  Or is it sufficient to just educate
>> developers about this issue and expect people to document the “finite
>> Sequence” precondition when the constraint is `Sequence` rather than
>> `Collection`?
>> 
>> I hope we will give serious consideration to these questions while
>> this topic is open for discussion.
>> 
>> -Matthew
>> 
>>> 
>>> Thanks,
>>> Jon
>>> 
>>>> on Wed Jun 22 2016, David Waite <david-AT-alkaline-solutions.com
>>>> <http://david-at-alkaline-solutions.com/ <http://david-at-alkaline-solutions.com/>>> wrote:
>>>> 
>>>>>> On Jun 22, 2016, at 2:57 PM, Dave Abrahams via swift-evolution
>>>>>> <swift-evolution at swift.org <http://swift.org/>
>>>>>> <https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>>>
>>>>>> wrote:
>>>>>> 
>>>>>> <Ahem> “Iterators,” please.
>>>>> 
>>>>> That makes me happy - for some reason I thought it was still GeneratorProtocol
>>>>> 
>>>>>>> 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?”
>>>>> No, I would just remove the allowance in the documentation and API
>>>>> design for a destructive/consuming iteration. Sequence would be the
>>>>> interface to getting access to repeatable iteration, without the need
>>>>> for meeting the other requirements for Collection.
>>>> 
>>>> That would be wrong unless there exist substantial examples of a
>>>> multipass Sequence that *can't* meet the other requirements of
>>>> Collection without loss of efficiency.  And since I can write an adaptor
>>>> that turns any multipass sequence into a Collection, I think it's
>>>> trivial to prove that no such examples exist.
>>>> 
>>>> -- 
>>>> -Dave
>>> 
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
> 
> -- 
> -Dave

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160627/a2c4c655/attachment.html>