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

Matthew Johnson matthew at anandabits.com
Mon Jun 27 13:37:58 CDT 2016

> On Jun 27, 2016, at 11:39 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> 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.
> on Sun Jun 26 2016, Jonathan Hull <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.  

Exactly.  It is perfectly reasonable to have an infinite, dynamically generated mathematical sequence and make multiple passes over a portion of it (for example, by zipping it with finite sequences, taking a prefix, etc).

> [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.”]

Of course that is *possible* and not hard to do but it sounds like a degenerate case to me.  How often do such things arise *in practice*?  In reality I suspect we tend to have sequences that are either infinite or finite not just in a strict sense, but also in a practical sense.  

>> 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]
>> 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?
> 2. Presumably Collection refines Sequence.  Does Sequence refine
>   Iterator?  IMO that would create the same problematic programming
>   model we have today.
> 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.
>> 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?

I think the same question can apply to destructive consumption of sequences.  I know people write code that assumes multi-pass and people also write code that assumes finiteness.  Do you know of cases where people commonly get into trouble with single pass sequences today?

I don’t know of specific cases where either has caused problems in practice but both leave plenty of room for trouble.  Enough that they deserve fixing IMO as they are pretty fundamental constructs that most Swift code relies upon.


>> Thanks,
>> Jon
>>> on Wed Jun 22 2016, David Waite <david-AT-alkaline-solutions.com> wrote:
>>>>> On Jun 22, 2016, at 2:57 PM, Dave Abrahams via swift-evolution
>>>>> <swift-evolution at swift.org
>>>>> <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
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

More information about the swift-evolution mailing list