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


(Dmitri Gribenko) #1

Hi,

I'd like to continue the discussion of the issue raised by David Waite
inhttp://thread.gmane.org/gmane.comp.lang.swift.evolution/21295/:

My main motivation for proposing this is the potential for developer confusion. As stated during one of the previous threads on the naming of map, flatMap, filter, etc. methods on Sequence, Sequence has a naming requirement not typical of the rest of the Swift standard library in that many methods on Sequence may or may not be destructive. As such, naming methods for any extensions on Sequence is challenging as the names need to not imply immutability.

I'd like to focus on a particular point: methods on Sequence can
consume elements, but the APIs are not markedmutating.

Dave Abrahams, Max Moiseev, and I have discussed this issue and we
agree this problem is severe and worth solving, we also think that the
likely solutions would be source-breaking, so it is important that we
discuss it now.

We have discussed a few options.

- Rejected option: remove Sequence, let IteratorProtocol model
single-pass data streams

- Rejected option: use a syntactic marker, like sequence.consumedIn.map {}

- Rejected option: mutating APIs on Sequence, non-mutating APIs on Collection

Proposed: rename Sequence to IterableOnce or TraversableOnce. We think
that Sequence does not convey the single-pass restriction clearly. The
term "sequence" has been used in math (as in "integer sequence"), and
since the math domain does not have mutation, "sequence" can be
understood to mean "multi-pass", since you can traverse a sequence of
integers an arbitrary number of times.

We think that only the last option is viable in the Swift language as
it exists now, without creating an undue burden for API vendors and
users.

For more details about rejection options, please see the full writeup:
https://gist.github.com/gribozavr/47f4717f3afc762549383e94da7f748b

Dmitri

···

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(David Waite) #2

I was looking into implementing this as well (although a bit slowly, was on vacation and entertaining house guests). I don’t know if it is worth taking this to a proposal now with this conclusion stated, but I will give my evaluation below:

I took a slightly different approach in prototyping - I made IteratorProtocol require reference types, and made iterator methods lazy by default. I also made AnyIterator a base class for the Iterator objects returned by the default implementations in the IteratorProtocol extensions.

With underestimatedCount and dropFirst as distinct counterexamples, most of the methods did not make sense to include as potential overrides on the protocol. As examples, map() and filter() do not give opportunities for a subclass to optimize a default behavior.

It still made sense for Collection to have a makeIterator, and to act like such an iterator consumed a copy of the collection. As such, an algorithm written for an Iterator could be applied to Collections relatively simply.

Since Iterators were lazy, the duplication wasn’t so much with Collection as with LazyCollection. Methods which took an Iterator or a Collection just called makeIterator on the collection. I felt some of the algorithmic and method duplication was offset by the removal of Sequence and LazySequence, and the ability to internalize the types returned as results from the extension methods.

The last remark I’ll add was that I looked at splitting out certain methods into a FiniteIteratorProtocol; methods like dropLast, suffix, count, etc. I experimented with the API for IteratorProtocol using this in places as well, such as starts(with:) taking a finite iterator as its argument.

This seemed to definitely lead to an explosion of API complexity, and I decided that it was probably not worth differentiating the two in the class system, and that in fact it might be worth holding off on the finite-targetted methods until it is obvious they are needed, since adding a FiniteIteratorProtocol subclass could be considered additive.

-DW

···

On Jul 12, 2016, at 4:55 PM, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:

Hi,

I'd like to continue the discussion of the issue raised by David Waite
inhttp://thread.gmane.org/gmane.comp.lang.swift.evolution/21295/:

- Rejected option: remove Sequence, let IteratorProtocol model
single-pass data streams


(Xiaodi Wu) #3

This more limited approach makes sense in light of the documented
reasoning. However, as a renaming proposal, I feel like I should raise some
points about the proposed name.

First, a naive interpretation of IterableOnce may cause a user to think
that a for...in loop over an IterableOnce is guaranteed to execute at least
once. It is not that a sequence is "iterable once." It could be iterable
exactly zero times. Rather, after however many iterations, the iterating
cannot take place from the beginning again.

Second, the dictionary definition of "once" lists an ambiguity, where (at
least in one source) the first meaning is "one time only." (See: <
https://www.google.com/#q=define:once>.) This could lead to
misinterpretations of the relationship where Collection is IterableOnce.

I would propose that perhaps Iterable is sufficient to convey the meaning.
There is no a priori user expectation, I think, that something iterable
remains unchanged on traversal.

···

On Tue, Jul 12, 2016 at 5:55 PM, Dmitri Gribenko via swift-evolution < swift-evolution@swift.org> wrote:

Hi,

I'd like to continue the discussion of the issue raised by David Waite
inhttp://thread.gmane.org/gmane.comp.lang.swift.evolution/21295/:

> My main motivation for proposing this is the potential for developer
confusion. As stated during one of the previous threads on the naming of
map, flatMap, filter, etc. methods on Sequence, Sequence has a naming
requirement not typical of the rest of the Swift standard library in that
many methods on Sequence may or may not be destructive. As such, naming
methods for any extensions on Sequence is challenging as the names need to
not imply immutability.

I'd like to focus on a particular point: methods on Sequence can
consume elements, but the APIs are not markedmutating.

Dave Abrahams, Max Moiseev, and I have discussed this issue and we
agree this problem is severe and worth solving, we also think that the
likely solutions would be source-breaking, so it is important that we
discuss it now.

We have discussed a few options.

- Rejected option: remove Sequence, let IteratorProtocol model
single-pass data streams

- Rejected option: use a syntactic marker, like sequence.consumedIn.map {}

- Rejected option: mutating APIs on Sequence, non-mutating APIs on
Collection

Proposed: rename Sequence to IterableOnce or TraversableOnce. We think
that Sequence does not convey the single-pass restriction clearly. The
term "sequence" has been used in math (as in "integer sequence"), and
since the math domain does not have mutation, "sequence" can be
understood to mean "multi-pass", since you can traverse a sequence of
integers an arbitrary number of times.

We think that only the last option is viable in the Swift language as
it exists now, without creating an undue burden for API vendors and
users.

For more details about rejection options, please see the full writeup:
https://gist.github.com/gribozavr/47f4717f3afc762549383e94da7f748b

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Anton Zhilin) #4

I also thought on the problem, and I agree with your solution. It keeps
things simple.
I agree with this specific name -- IterableOnce (not IterableAtLeastOnce).
IterableOnce contains Iterable -- and that plays very nicely with
IteratorProtocol name.
IterableOnce is not a single word, but it's not too long, compared to some
other options.
Functions working with IterableOnce will always imply single-pass, and with
Collections -- multi-pass. It might seem odd that Collection conforms to
IterableOnce, but I consider that a minor drawback.

···

2016-07-13 1:55 GMT+03:00 Dmitri Gribenko via swift-evolution < swift-evolution@swift.org>:

Hi,

I'd like to continue the discussion of the issue raised by David Waite
inhttp://thread.gmane.org/gmane.comp.lang.swift.evolution/21295/:

> My main motivation for proposing this is the potential for developer
confusion. As stated during one of the previous threads on the naming of
map, flatMap, filter, etc. methods on Sequence, Sequence has a naming
requirement not typical of the rest of the Swift standard library in that
many methods on Sequence may or may not be destructive. As such, naming
methods for any extensions on Sequence is challenging as the names need to
not imply immutability.

I'd like to focus on a particular point: methods on Sequence can
consume elements, but the APIs are not markedmutating.

Dave Abrahams, Max Moiseev, and I have discussed this issue and we
agree this problem is severe and worth solving, we also think that the
likely solutions would be source-breaking, so it is important that we
discuss it now.

We have discussed a few options.

- Rejected option: remove Sequence, let IteratorProtocol model
single-pass data streams

- Rejected option: use a syntactic marker, like sequence.consumedIn.map {}

- Rejected option: mutating APIs on Sequence, non-mutating APIs on
Collection

Proposed: rename Sequence to IterableOnce or TraversableOnce. We think
that Sequence does not convey the single-pass restriction clearly. The
term "sequence" has been used in math (as in "integer sequence"), and
since the math domain does not have mutation, "sequence" can be
understood to mean "multi-pass", since you can traverse a sequence of
integers an arbitrary number of times.

We think that only the last option is viable in the Swift language as
it exists now, without creating an undue burden for API vendors and
users.

For more details about rejection options, please see the full writeup:
https://gist.github.com/gribozavr/47f4717f3afc762549383e94da7f748b

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution