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

[Jonathan Hull]

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.


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

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