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

Tue Jun 28 13:28:25 CDT 2016

> On Jun 28, 2016, at 12:51 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> 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?  

That was my impression.  It’s an interesting idea.  It wouldn’t guarantee termination but would require developers to consider termination and therefore prevent accidents, which are the concerns I am raising.

> We could also do this with
> 
>    for i in allIntegers.until(isPrime)

Is `until` lazy or eager here?  I imagine you’re thinking it would be lazy because making it eager would introduce unnecessary allocation.  However, if it’s lazy it is an exception to the explicit laziness Swift has adopted.  

Wouldn’t it be better to require explicit laziness `allIntegers.lazy.until` if for..in is going to be require finite sequences and we’re going to use a library solution to support infinite sequences?  It’s more verbose but more consistent with how laziness is currently handled.  It also doesn’t privilege any specific operator (which isn’t necessary if we do this in the library).  

If we went with a language solution I imagine it would look something like this:

for i in allIntegers until i.isPrime && i > 1000 where i.isEven {
    // all even integers < the first prime > 1000
}

IIRC the `until` clause has already been discussed as syntactic sugar for early termination.  Its utility wouldn’t be limited to looping over infinite sequences, however it would be *required* when you loop over an infinite sequence.  

This sugar wouldn’t have to be introduced in Swift 3.  We could make for..in require finite sequences in Swift 3 and add it later if there is sufficient demand.  In the meantime people could iterate infinite sequences manually and / or we could add library support via lazy operators that select a prefix (if we are willing to live with the fact that in practice termination may depend on arguments to the operator).

> 
>>> 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
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution