Fixing the confusion between non-mutating algorithms and single-pass sequences

Evolution Discussion
1

>>> Basically, I added back in a super-minimal protocol to fill the
>>> structural gap left by Sequence. I call it “IteratorProvider” and it
>>> only has a single function which vends an iterator. Collection
>>> adheres to this, and Iterator adheres to it by returning itself. All
>>> of the other methods from Sequence remain on Iterator. Thus anyone
>>> with API that only needs a single pass would take a IteratorProvider
>>> and then work on the iterator it provides.
>>
>> That leaves us back where we are now: people will see that
>> IteratorProvider is a simple, universal protocol for both single-and
>> multi-pass sequences, write algorithm libraries that depend on
>> multi-pass-ness, and test them with the most prevalent examples, which
>> happen to be multi pass.
>
> Let me make a quick counter-argument, because I thought about it a
> bit, and I don’t think it does have the same problem (especially with
> careful/better naming).
>
> The difference is that the ONLY method on IteratorProvider is the one
> to get an iterator. There is no map, filter, sort, first, count, etc…
> just a way to get a single-pass iterator. This changes the mindset
> when using it. You are aware that you are getting a single-pass
> iterator.

Maybe. What's to stop people from extending IteratorProvider?

Nothing. But that is true of any protocol. I am ok with individual's extensions. They would have to use that single method to build up from anyway, so presumably they would have to consider the single pass case in their extensions...

> True, people might try to get the iterator a second time, but we can
> make the iteratorProvider method optional (and trying to get an
> iterator from an iterator which is spent would return nil)
> and then they are forced to deal with the case where it was
> single-pass.

Now you can't loop over the same array multiple times.

I must be missing something. Isn’t that the point?

I mean, your version is called “IterableOnce”. Why do you want to iterate on IterableOnce more than once? The point (at least in my mind) is to provide a common interface for things that we want to iterate over a single time. If you want to iterate multiple times, use collection’s interface where you are guaranteed multi-pass.

That said, you actually can loop multiple times for collections by getting a new iterator from the provider (which could point to the same array storage). The optional just forces you to check for the single-pass case.

I have a feeling like I am missing your true meaning here though...

Thanks,
Jon

2

>>> Basically, I added back in a super-minimal protocol to fill the
>>> structural gap left by Sequence. I call it “IteratorProvider” and it
>>> only has a single function which vends an iterator. Collection
>>> adheres to this, and Iterator adheres to it by returning itself. All
>>> of the other methods from Sequence remain on Iterator. Thus anyone

>>> with API that only needs a single pass would take a IteratorProvider
>>> and then work on the iterator it provides.
>>
>> That leaves us back where we are now: people will see that
>> IteratorProvider is a simple, universal protocol for both single-and
>> multi-pass sequences, write algorithm libraries that depend on
>> multi-pass-ness, and test them with the most prevalent examples, which
>> happen to be multi pass.
>
> Let me make a quick counter-argument, because I thought about it a
> bit, and I don’t think it does have the same problem (especially with
> careful/better naming).
>
> The difference is that the ONLY method on IteratorProvider is the one
> to get an iterator. There is no map, filter, sort, first, count, etc…
> just a way to get a single-pass iterator. This changes the mindset
> when using it. You are aware that you are getting a single-pass
> iterator.

Maybe. What's to stop people from extending IteratorProvider?

Nothing. But that is true of any protocol. I am ok with individual's
extensions. They would have to use that single method to build up
from anyway, so presumably they would have to consider the single pass
case in their extensions...

> True, people might try to get the iterator a second time, but we can
> make the iteratorProvider method optional (and trying to get an
> iterator from an iterator which is spent would return nil)
> and then they are forced to deal with the case where it was
> single-pass.

Now you can't loop over the same array multiple times.

I must be missing something. Isn’t that the point?

No. Arrays are multipass.

I mean, your version is called “IterableOnce”. Why do you want to
iterate on IterableOnce more than once?

Because it happens to be multipass.

The point (at least in my mind) is to provide a common interface for
things that we want to iterate over a single time. If you want to
iterate multiple times, use collection’s interface where you are
guaranteed multi-pass.

for ... in uses Iterators.

That said, you actually can loop multiple times for collections by
getting a new iterator from the provider (which could point to the
same array storage). The optional just forces you to check for the
single-pass case.

Oh, I'm sorry; I didn't realize you were saying that only single-pass
IteratorProviders would ever return nil from their methods.

I have a feeling like I am missing your true meaning here though...

Probably a communication failure on my end.

···

on Wed Jul 20 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:

--
-Dave

3

Right - an iterator instance is single pass, but a method that returns an iterator may be able to make multiple iterators which iterate over the same sequence of values.

I still think ideally you can operate on iterators as streams of data directly, rather than requiring a base protocol. I understand how this could cause lots of duplication to have two ‘sequence’ implementations, however.

-DW

···

On Jul 20, 2016, at 2:57 PM, Jonathan Hull via swift-evolution <swift-evolution@swift.org> wrote:

> True, people might try to get the iterator a second time, but we can
> make the iteratorProvider method optional (and trying to get an
> iterator from an iterator which is spent would return nil)
> and then they are forced to deal with the case where it was
> single-pass.

Now you can't loop over the same array multiple times.

I must be missing something. Isn’t that the point?

I mean, your version is called “IterableOnce”. Why do you want to iterate on IterableOnce more than once? The point (at least in my mind) is to provide a common interface for things that we want to iterate over a single time. If you want to iterate multiple times, use collection’s interface where you are guaranteed multi-pass.

That said, you actually can loop multiple times for collections by getting a new iterator from the provider (which could point to the same array storage). The optional just forces you to check for the single-pass case.

I have a feeling like I am missing your true meaning here though...

Thanks,
Jon

4

>>> Basically, I added back in a super-minimal protocol to fill the
>>> structural gap left by Sequence. I call it “IteratorProvider” and it
>>> only has a single function which vends an iterator. Collection
>>> adheres to this, and Iterator adheres to it by returning itself. All
>>> of the other methods from Sequence remain on Iterator. Thus anyone

>>> with API that only needs a single pass would take a IteratorProvider
>>> and then work on the iterator it provides.
>>
>> That leaves us back where we are now: people will see that
>> IteratorProvider is a simple, universal protocol for both single-and
>> multi-pass sequences, write algorithm libraries that depend on
>> multi-pass-ness, and test them with the most prevalent examples, which
>> happen to be multi pass.
>
> Let me make a quick counter-argument, because I thought about it a
> bit, and I don’t think it does have the same problem (especially with
> careful/better naming).
>
> The difference is that the ONLY method on IteratorProvider is the one
> to get an iterator. There is no map, filter, sort, first, count, etc…
> just a way to get a single-pass iterator. This changes the mindset
> when using it. You are aware that you are getting a single-pass
> iterator.

Maybe. What's to stop people from extending IteratorProvider?

Nothing. But that is true of any protocol. I am ok with individual's
extensions. They would have to use that single method to build up
from anyway, so presumably they would have to consider the single pass
case in their extensions...

> True, people might try to get the iterator a second time, but we can
> make the iteratorProvider method optional (and trying to get an
> iterator from an iterator which is spent would return nil)
> and then they are forced to deal with the case where it was
> single-pass.

Now you can't loop over the same array multiple times.

I must be missing something. Isn’t that the point?

No. Arrays are multipass.

I mean, your version is called “IterableOnce”. Why do you want to
iterate on IterableOnce more than once?

Because it happens to be multipass.

The point (at least in my mind) is to provide a common interface for
things that we want to iterate over a single time. If you want to
iterate multiple times, use collection’s interface where you are
guaranteed multi-pass.

for ... in uses Iterators.

That said, you actually can loop multiple times for collections by
getting a new iterator from the provider (which could point to the
same array storage). The optional just forces you to check for the
single-pass case.

Oh, I'm sorry; I didn't realize you were saying that only single-pass
IteratorProviders would ever return nil from their methods.

Note: any IteratorProvider that could return nil would have to be a
class (or wrap a class) in order to bypass mutability restrictions,
since we can't allow the method that provides the iterator to be
mutating.

···

on Wed Jul 20 2016, Dave Abrahams <dabrahams-AT-apple.com> wrote:

on Wed Jul 20 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:

I have a feeling like I am missing your true meaning here though...

Probably a communication failure on my end.

--
-Dave

5

That is a good point. I think I am ok with it, since in my mind this is already true of non-clonable Iterators anyway. If you recall, in my original proposal I wanted to make iterators reference types. That was rejected for performance reasons, but I still think that non-clonable Iterators will at least need to wrap a reference type somewhere (or they will be subject to the issue you are talking about above).

Note: In the current system, it is common to create sequences, but under my proposal it would be rare to create an IteratorProvider that wasn’t also an Iterator or Collection, since Iterator and Collection would both have default implementations satisfying IteratorProvider, and IteratorProvider doesn’t have any useful methods besides the one providing an Iterator.

Thanks,
Jon

···

On Jul 20, 2016, at 3:30 PM, Dave Abrahams <dave@boostpro.com> wrote:

on Wed Jul 20 2016, Dave Abrahams <dabrahams-AT-apple.com> wrote:

on Wed Jul 20 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:

Basically, I added back in a super-minimal protocol to fill the
structural gap left by Sequence. I call it “IteratorProvider” and it
only has a single function which vends an iterator. Collection
adheres to this, and Iterator adheres to it by returning itself. All
of the other methods from Sequence remain on Iterator. Thus anyone

with API that only needs a single pass would take a IteratorProvider
and then work on the iterator it provides.

That leaves us back where we are now: people will see that
IteratorProvider is a simple, universal protocol for both single-and
multi-pass sequences, write algorithm libraries that depend on
multi-pass-ness, and test them with the most prevalent examples, which
happen to be multi pass.

Let me make a quick counter-argument, because I thought about it a
bit, and I don’t think it does have the same problem (especially with
careful/better naming).

The difference is that the ONLY method on IteratorProvider is the one
to get an iterator. There is no map, filter, sort, first, count, etc…
just a way to get a single-pass iterator. This changes the mindset
when using it. You are aware that you are getting a single-pass
iterator.

Maybe. What's to stop people from extending IteratorProvider?

Nothing. But that is true of any protocol. I am ok with individual's
extensions. They would have to use that single method to build up
from anyway, so presumably they would have to consider the single pass
case in their extensions...

True, people might try to get the iterator a second time, but we can
make the iteratorProvider method optional (and trying to get an
iterator from an iterator which is spent would return nil)
and then they are forced to deal with the case where it was
single-pass.

Now you can't loop over the same array multiple times.

I must be missing something. Isn’t that the point?

No. Arrays are multipass.

I mean, your version is called “IterableOnce”. Why do you want to
iterate on IterableOnce more than once?

Because it happens to be multipass.

The point (at least in my mind) is to provide a common interface for
things that we want to iterate over a single time. If you want to
iterate multiple times, use collection’s interface where you are
guaranteed multi-pass.

for ... in uses Iterators.

That said, you actually can loop multiple times for collections by
getting a new iterator from the provider (which could point to the
same array storage). The optional just forces you to check for the
single-pass case.

Oh, I'm sorry; I didn't realize you were saying that only single-pass
IteratorProviders would ever return nil from their methods.

Note: any IteratorProvider that could return nil would have to be a
class (or wrap a class) in order to bypass mutability restrictions,
since we can't allow the method that provides the iterator to be
mutating.

6

Suggestion: Realistically, I see no possibility that this idea can be
completely designed, reviewed, approved, and implemented in time for
Swift 3, so let's take this up after Swift 3 ships. Yes, it's a
breaking change, but there *will* be some of those going forward.
Obviously, if you disagree, feel free to pursue it now, but—even though
I'm very interested in this topic—I don't
think I have the time budget to participate at the moment.

Regardless, the best proof-of-concept would be to implement it and
create a pull request against Swift that demonstrates how it works and
passes tests, and that can be worked on by anybody at any time. That's
also the only thing I can imagine that would make it realistic for me to
spend time on it before Swift 3 ships.

···

on Wed Jul 20 2016, Jonathan Hull <swift-evolution@swift.org> wrote:

On Jul 20, 2016, at 3:30 PM, Dave Abrahams <dave@boostpro.com> wrote:

on Wed Jul 20 2016, Dave Abrahams <dabrahams-AT-apple.com> wrote:

on Wed Jul 20 2016, Jonathan Hull <jhull-AT-gbis.com> wrote:

Basically, I added back in a super-minimal protocol to fill the
structural gap left by Sequence. I call it “IteratorProvider” and it
only has a single function which vends an iterator. Collection
adheres to this, and Iterator adheres to it by returning itself. All
of the other methods from Sequence remain on Iterator. Thus anyone

with API that only needs a single pass would take a IteratorProvider
and then work on the iterator it provides.

That leaves us back where we are now: people will see that
IteratorProvider is a simple, universal protocol for both single-and
multi-pass sequences, write algorithm libraries that depend on
multi-pass-ness, and test them with the most prevalent examples, which
happen to be multi pass.

Let me make a quick counter-argument, because I thought about it a
bit, and I don’t think it does have the same problem (especially with
careful/better naming).

The difference is that the ONLY method on IteratorProvider is the one
to get an iterator. There is no map, filter, sort, first, count, etc…
just a way to get a single-pass iterator. This changes the mindset
when using it. You are aware that you are getting a single-pass
iterator.

Maybe. What's to stop people from extending IteratorProvider?

Nothing. But that is true of any protocol. I am ok with individual's
extensions. They would have to use that single method to build up
from anyway, so presumably they would have to consider the single pass
case in their extensions...

True, people might try to get the iterator a second time, but we can
make the iteratorProvider method optional (and trying to get an
iterator from an iterator which is spent would return nil)
and then they are forced to deal with the case where it was
single-pass.

Now you can't loop over the same array multiple times.

I must be missing something. Isn’t that the point?

No. Arrays are multipass.

I mean, your version is called “IterableOnce”. Why do you want to
iterate on IterableOnce more than once?

Because it happens to be multipass.

The point (at least in my mind) is to provide a common interface for
things that we want to iterate over a single time. If you want to
iterate multiple times, use collection’s interface where you are
guaranteed multi-pass.

for ... in uses Iterators.

That said, you actually can loop multiple times for collections by
getting a new iterator from the provider (which could point to the
same array storage). The optional just forces you to check for the
single-pass case.

Oh, I'm sorry; I didn't realize you were saying that only single-pass
IteratorProviders would ever return nil from their methods.

Note: any IteratorProvider that could return nil would have to be a
class (or wrap a class) in order to bypass mutability restrictions,
since we can't allow the method that provides the iterator to be
mutating.

That is a good point. I think I am ok with it, since in my mind this
is already true of non-clonable Iterators anyway. If you recall, in
my original proposal I wanted to make iterators reference types. That
was rejected for performance reasons, but I still think that
non-clonable Iterators will at least need to wrap a reference type
somewhere (or they will be subject to the issue you are talking about
above).

Note: In the current system, it is common to create sequences, but
under my proposal it would be rare to create an IteratorProvider that
wasn’t also an Iterator or Collection, since Iterator and Collection
would both have default implementations satisfying IteratorProvider,
and IteratorProvider doesn’t have any useful methods besides the one
providing an Iterator.

--
Dave