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

[Dave Abrahams]

on Mon Jun 27 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:

> Comments inline
>
>> On Jun 27, 2016, at 9:39 AM, Dave Abrahams <dabrahams at apple.com> wrote:
>> 
>> 
>> I should be clear up-front about the main problem I'm trying to solve:
>> 
>> Today, people see a beautiful, simple protocol (Sequence) to which many
>> things conform. They don't recognize that there's a semantic restriction
>> (assume you can make only a single-pass!) on it, so they write libraries
>> of functions that may make multiple passes over Sequences.  They test
>> their libraries with the most commonly-available Sequences, e.g. Arrays
>> and Ranges, which happen to be multi-pass.  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.
> Agreed.
>
>> on Sun Jun 26 2016, Jonathan Hull <jhull-AT-gbis.com <http://jhull-at-gbis.com/>> wrote:
>> 
>>> Can’t a Sequence be potentially infinite, whereas a collection has a
>>> defined count/endIndex?  Other than that, I agree with your statement.
>> 
>> I agree that that is currently what the documentation allows and requires.
>> Maybe we do need to separate finiteness from multipass-ness.  There's
>> certainly no reason one can't make multiple passes over a portion of an
>> infinite sequence.
> I have a use-case for this below.  Graphical manipulation using a repeatable sequence of random numbers.
>
>>  [Just to complicate things... I wonder if finiteness is really
>> meaningful.  It's easy to create a finite sequence that's so long that
>> it's “effectively infinite.”]
>
> See below… I am definitely guilty of this.  That said, if we had
> explicit infinite sequences (with subscripts), I would use those
> instead of collections for these use-cases.
>
>> 
>>> Here is what I see as the appropriate structure:
>>> 
>>> Iterator: Single destructive pass, potentially infinite, (should be
>>> for-in able)
>> 
>> [Note: the best way to represent “single destructive pass” today is to
>> constrain Iterator to be a reference type.  Otherwise, it's both easy to
>> create an Iterator that can be used to make multiple passes (by
>> copying), and to create a truly single-pass Iterator that suggests it
>> has value semantics.  These are both potentially misleading situations]
>
> Hmm… This is a really good point.  I can see why you are thinking of making it a reference type.
>
> If a particular iterator can safely be cloned mid-stream, then it can
> provide its own interface to allow that.  The value type makes a
> promise which can’t always be kept.
>
>> 
>>> 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)
>> 
>> This is a reasonable structure, but there are important details missing.
>> 
>> 1. Presumably these are all for-in-able.  What makes something
>>   for-in-able?
>
> I would think the potentially infinite should require for-in-until
> (even if you explicitly set until to false to create an infinite
> loop), but collection would allow for-in (with optional until).  That
> way you have to acknowledge the possibility of an infinite
> sequence/iterator.

Are you proposing a new language feature?  We could also do this with

    for i in allIntegers.until(isPrime)

>> 2. Presumably Collection refines Sequence.  Does Sequence refine
>>   Iterator?  IMO that would create the same problematic programming
>>   model we have today.
>
> Sequence vends iterators. (a sequence is NOT a refinement of iterator,
> it just creates them as needed)
>
>> Perhaps the language should accept types conforming to either of two
>> unrelated protocols (your Sequence and Iterator, as you've described
>> them, with no refinement relationship) for for-in.
>
> Yes.
>
>>> 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...
>> 
>> The other thing I am concerned about here is that we're addressing real
>> use-cases with these distinctions.  For example, do people commonly get
>> in trouble with infinite sequences today?
>
> Probably not… because they avoid infinite sequences to avoid getting
> into trouble.  I was bitten a few times early on (I assumed map was
> lazy) and just avoided them until recently.
>
> I think they would be used more often if you could guarantee that
> their use was safe (i.e. being forced to consider the infinite
> possibility).  I would like to have a bunch of infinite sequences that
> could easily be refined to collections.  The ones I would use most
> often would be the natural numbers and random numbers.  Also imagine,
> an infinite sequence of random colors which look fairly good together.
> Markov chains, die rolls… there are a lot of potential uses that
> become interesting once the threat of accidental infinite loop has
> been removed...
>
> As a real world example of the "effectively infinite” sequence, this
> weekend I created a Swift 3 collection of repeatable random values (of
> any type conforming to a protocol). I would have used sequence if the
> subscript behavior was available on it, since I do intend it to be an
> infinite sequence in most cases (Apologies for the lack of comments,
> it is not yet prepared for public consumption):
> https://gist.github.com/jonhull/3655672529f8cf5b2eb248583d2cafb9
>
> The use case here is to create a hand-drawn look for a CGPath by
> breaking it up into pieces and then jiggling the pieces about (using
> random CGVectors). I quickly realized that I needed a repeatable
> source of randomness (otherwise the drawing would move each time it
> was redrawn), and thus a multi-pass sequence.
>
> I am a little bit nervous every time I use this, as it has the
> potential for an “effectively infinite” loop, but is proving useful
> throughout my project.

Thanks for the example; that helps.

> Thanks,
> Jon
>
>> 
>>> Thanks,
>>> Jon
>>> 
>>>> on Wed Jun 22 2016, David Waite <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
>>> 
>> 
>> -- 
>> -Dave
>

-- 
Dave