Separating the finite-vs-infinite distinction from single-vs-multi-pass

Evolution Discussion
1

This post describes the standard library team's analysis of the
finite/infinite sequence issue raised by Matthew Johnson and others in
http://news.gmane.org/find-root.php?message_id=1976B8AE-FDD1-4257-A24F-2AFF84115445%40anandabits.com\.

[Dmitri is going to write a separate post detailing our proposed
direction with respect to the original topic raised by David Waite in
http://thread.gmane.org/gmane.comp.lang.swift.evolution/21295, the
confusion resulting from the refinement relationship between Sequence
and Collection that introduces non-destructive consumption. As you
will see below, the resolution of this post's issue will depend
somewhat on that].

It seems to us that there are four possible approaches here:

1. Do nothing. Infinite loops are not usually security problems and
   might not be worth complicating APIs for.

2. Formally lift the constraint on Collection that forces it to be
   finite. That would allow us to model multi-pass traversal over
   (portions of) infinite sequences.

3. #2, plus add to Collection an `isKnownToBeInfinite` property,
   defaulting to `false`, that can be used to trigger a trap when a call
   would otherwise loop infinitely.

4. Go all the way to separate protocols for finite and infinite
   Collections as detailed in
   http://article.gmane.org/gmane.comp.lang.swift.evolution/22471

As far as we can tell, the only real point in distinguishing finiteness
is to prevent infinite loops. Since inifinite loops are equally
(non-)problematic for both single- and multi-pass sequences, we can find
little justification for treating single-pass and multi-pass sequences
differently where finiteness is concerned. Therefore, whatever we end
up with for Collection should apply to single-pass sequences as well.

Lastly, it looks like nobody on the standard library team is going to
have the time to drive this forward for Swift 3. While the standard
library team can provide some guidance, if it is to happen, someone else
needs to take the reins. That's not supposed to be discouraging:
several smart and capable people have expressed their interest in this
topic. That said, if you care about it, you'll need to do as much work
as possible independently. That includes putting the proposal through
evolution and creating a pull request containing the implementation.

Thanks, everybody!

···

--
Dave

2

1. Do nothing with finiteness, because huge sequences are mostly like
infinite ones, plus because infinite loops are useful
2. Allow collections to be infinite
3. Do not add new fields to collections, because infinite loops are useful
4, Do not separate protocols
Current model of IteratorProtocol + Sequence is a very simple and clean way
to define one's own iterables. Let's not break it.

Now to single-pass-ness.
I would suggest the following model:
1. Iterable protocol is base of everything that can be used in for loop.
Contains all single-pass-able operations.
2. IteratorProtocol is what Iterable returns. IteratorProtocol conforms to
Iterable, returns itself. Single-pass sequences should conform to
IteratorProtocol.
3. Sequence protocol conforms to Iterable. Sequences are multi-pass.

Also, we should leave both Sequence and Collection trees, because correctly
conforming to Collection is a hard work, and correctly conforming to
Sequence must be easy as pie.

···

2016-07-06 4:56 GMT+03:00 Dave Abrahams via swift-evolution < swift-evolution@swift.org>:

This post describes the standard library team's analysis of the
finite/infinite sequence issue raised by Matthew Johnson and others in

http://news.gmane.org/find-root.php?message_id=1976B8AE-FDD1-4257-A24F-2AFF84115445%40anandabits.com
.

[Dmitri is going to write a separate post detailing our proposed
direction with respect to the original topic raised by David Waite in
http://thread.gmane.org/gmane.comp.lang.swift.evolution/21295, the
confusion resulting from the refinement relationship between Sequence
and Collection that introduces non-destructive consumption. As you
will see below, the resolution of this post's issue will depend
somewhat on that].

It seems to us that there are four possible approaches here:

1. Do nothing. Infinite loops are not usually security problems and
   might not be worth complicating APIs for.

2. Formally lift the constraint on Collection that forces it to be
   finite. That would allow us to model multi-pass traversal over
   (portions of) infinite sequences.

3. #2, plus add to Collection an `isKnownToBeInfinite` property,
   defaulting to `false`, that can be used to trigger a trap when a call
   would otherwise loop infinitely.

4. Go all the way to separate protocols for finite and infinite
   Collections as detailed in
   http://article.gmane.org/gmane.comp.lang.swift.evolution/22471

As far as we can tell, the only real point in distinguishing finiteness
is to prevent infinite loops. Since inifinite loops are equally
(non-)problematic for both single- and multi-pass sequences, we can find
little justification for treating single-pass and multi-pass sequences
differently where finiteness is concerned. Therefore, whatever we end
up with for Collection should apply to single-pass sequences as well.

Lastly, it looks like nobody on the standard library team is going to
have the time to drive this forward for Swift 3. While the standard
library team can provide some guidance, if it is to happen, someone else
needs to take the reins. That's not supposed to be discouraging:
several smart and capable people have expressed their interest in this
topic. That said, if you care about it, you'll need to do as much work
as possible independently. That includes putting the proposal through
evolution and creating a pull request containing the implementation.

Thanks, everybody!

--
Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

3

1. Do nothing with finiteness, because huge sequences are mostly like
infinite ones, plus because infinite loops are useful
2. Allow collections to be infinite
3. Do not add new fields to collections, because infinite loops are
useful

No argument so far, but...

4, Do not separate protocols
Current model of IteratorProtocol + Sequence is a very simple and clean way
to define one's own iterables. Let's not break it.

It's already broken. When you call non-mutating methods such as map,
filter, or reduce on a Sequence, the sequence can be modified. That
provblem was outlined very nicely by David Waite in
http://thread.gmane.org/gmane.comp.lang.swift.evolution/21295/focus=21872:

  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.

Now to single-pass-ness.
I would suggest the following model:
1. Iterable protocol is base of everything that can be used in for loop.
Contains all single-pass-able operations.
2. IteratorProtocol is what Iterable returns. IteratorProtocol conforms to
Iterable, returns itself. Single-pass sequences should conform to
IteratorProtocol.
3. Sequence protocol conforms to Iterable. Sequences are multi-pass.

That solves no problems AFAICT and introduces a new protocol. What's
the point?

Also, we should leave both Sequence and Collection trees, because
correctly conforming to Collection is a hard work, and correctly
conforming to Sequence must be easy as pie.

That goal should not take precedence over logical coherence and
simplicity of the standard library.

Also, conforming to collection isn't really hard.

Finally, as mentioned earlier we could easily supply a protocol that
makes it no harder than conforming to IteratorProtocol is. You don't
even need to make your iteration state equatable because we can compare
counters stored in the indices. I'll post a gist illustrating this
today.

···

on Wed Jul 06 2016, Anton Zhilin <antonyzhilin-AT-gmail.com> wrote:

--
Dave

4

Enjoy,

···

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

Finally, as mentioned earlier we could easily supply a protocol that
makes it no harder than conforming to IteratorProtocol is. You don't
even need to make your iteration state equatable because we can compare
counters stored in the indices. I'll post a gist illustrating this
today.

--
Dave

5

Finally, as mentioned earlier we could easily supply a protocol that
makes it no harder than conforming to IteratorProtocol is. You don't
even need to make your iteration state equatable because we can compare
counters stored in the indices. I'll post a gist illustrating this
today.

Make defining a collection as easy as pie · GitHub

Thanks for sharing! It's great to have a clear and concise example showing how easy it can be to support Collection.

We should keep the the Comparable requirement and probably drop Sequence.

I plan to comment on finite vs infinite but want to see the rest of the plans the library team is working before I do so.

Matthew

···

Sent from my iPad

On Jul 6, 2016, at 6:50 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

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

Enjoy,

--
Dave
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution