[Review] Constraining AnySequence.init

Hello Swift community,

The review of “Constraining AnySequence.init” begins now and runs through Monday, December 21st, 2015. The proposal is available here:

  swift-evolution/0014-constrained-AnySequence.md at master · apple/swift-evolution · GitHub <https://github.com/apple/swift-evolution/blob/master/proposals/0009-require-self-for-accessing-instance-members.md&gt;

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

  https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  swift-evolution/process.md at master · apple/swift-evolution · GitHub

  Cheers,
  Doug Gregor
  Review Manager

The URL is right (https://github.com/apple/swift-evolution/blob/master/proposals/0014-constrained-AnySequence.md\), but the link points to a different proposal (https://github.com/apple/swift-evolution/blob/master/proposals/0009-require-self-for-accessing-instance-members.md\). Copy-paste it to access the review.

···

Le 18 déc. 2015 à 12:51:57, Douglas Gregor via swift-evolution <swift-evolution@swift.org> a écrit :

Hello Swift community,

The review of “Constraining AnySequence.init” begins now and runs through Monday, December 21st, 2015. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0014-constrained-AnySequence.md <https://github.com/apple/swift-evolution/blob/master/proposals/0009-require-self-for-accessing-instance-members.md&gt;

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

  https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

  Cheers,
  Doug Gregor
  Review Manager

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

Yikes, thank you! I have no idea how I managed that. Will re-send...

  - Doug

···

On Dec 18, 2015, at 9:58 AM, Félix Cloutier <felixcca@yahoo.ca> wrote:

The URL is right (https://github.com/apple/swift-evolution/blob/master/proposals/0014-constrained-AnySequence.md\), but the link points to a different proposal (https://github.com/apple/swift-evolution/blob/master/proposals/0009-require-self-for-accessing-instance-members.md\). Copy-paste it to access the review.

Le 18 déc. 2015 à 12:51:57, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

Hello Swift community,

The review of “Constraining AnySequence.init” begins now and runs through Monday, December 21st, 2015. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0014-constrained-AnySequence.md <https://github.com/apple/swift-evolution/blob/master/proposals/0009-require-self-for-accessing-instance-members.md&gt;

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

  https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

  Cheers,
  Doug Gregor
  Review Manager

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

*# What is your evaluation of the proposal?*

Overall it looks good. I haven't looked at the implementation of
AnySequence before, but it sound fairly reasonable.

A couple of minor nits:

1. The proposal motivation says

At the moment AnyCollection does not delegate calls to SequenceType
protocol methods to the underlying base sequence

Presumably that should say AnySequence instead of AnyCollection, since
the rest of the proposal talks about AnySequence?

2. One of the added constraints looks like

S.SubSequence.SubSequence == S.SubSequence

with a comment saying that ideally the set of constraints would apply to
the SequenceType protocol but that's not currently possible. This makes
sense for the other constraints (that SubSequence conforms to
SequenceType and has the same element), but this particular constraint,
that the subsequence type must have itself as its own subsequence,
surprises me a little. I can see why it's needed here (because that's
the only way you can guarantee that recursing through SubSequences
always finds SequenceTypes with the right element), but ideally we
wouldn't actually require it to be the _same_ sequence, just that it is
some sequence with the same element type. If we ever change Swift such
that these constraints can be expressed on the SequenceType definition
itself, then presumably we'll be able to drop this == constraint
entirely as the SequenceType protocol itself will ensure that its
subsequence is a sequence of the same element type (which will satisfy
the need to have it be true after arbitrary levels of recursion).

Given that, I'm inclined to say that we should of course go ahead and
have this == constraint here because that's the only way to satisfy the
requirement today, but just to note that if SequenceType can learn to
express this requirement directly the == constraint will go away as it's
perfectly fine then for subsequences of subsequences to be different
sequence types.

*# Is the problem being addressed significant enough to warrant a change
to Swift?*

Yeah. It's a fairly minor change in the scheme of things (should affect
very little code, if any), and it fixes a surprising hole in
AnySequence.

*# Does this proposal fit well with the feel and direction of Swift?*

Yes.

*# If you have you used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?*

Not applicable.

*# How much effort did you put into your review? A glance, a quick
reading, or an in-depth study?*

A reasonably brief reading.

-Kevin Ballard

···

On Fri, Dec 18, 2015, at 09:59 AM, Douglas Gregor via swift-evolution wrote:

Yikes, thank you! I have no idea how I managed that. Will re-send...

- Doug

On Dec 18, 2015, at 9:58 AM, Félix Cloutier >> <felixcca@yahoo.ca> wrote:

The URL is right
(https://github.com/apple/swift-evolution/blob/master/proposals/0014-constrained-AnySequence.md\)
, but the link points to a different proposal
(https://github.com/apple/swift-evolution/blob/master/proposals/0009-require-self-for-accessing-instance-members.md\)
. Copy-paste it to access the review.

Le 18 déc. 2015 à 12:51:57, Douglas Gregor via swift-evolution <swift- >>> evolution@swift.org> a écrit :

Hello Swift community,

The review of “Constraining AnySequence.init” begins now and runs
through Monday, December 21st, 2015. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0014-constrained-AnySequence.md[1\]

Reviews are an important part of the Swift evolution process. All
reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the
review manager.

What goes into a review?

The goal of the review process is to improve the proposal under
review through constructive criticism and, eventually, determine the
direction of Swift. When writing your review, here are some
questions you might want to answer in your review:

* What is your evaluation of the proposal? * Is the problem being
addressed significant enough to warrant a change to Swift? * Does
this proposal fit well with the feel and direction of Swift? * If
you have you used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those? * How
much effort did you put into your review? A glance, a quick reading,
or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Cheers, Doug Gregor Review Manager

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

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

Links:

  1. https://github.com/apple/swift-evolution/blob/master/proposals/0009-require-self-for-accessing-instance-members.md

Thanks for a review Kevin!

At the moment AnyCollection does not delegate calls to SequenceType protocol methods to the underlying base sequence

Presumably that should say AnySequence instead of AnyCollection, since the rest of the proposal talks about AnySequence?

Good catch. Although applicable to AnyCollection as well, this should mention AnySequence in this case. :+1:

2. One of the added constraints looks like

S.SubSequence.SubSequence == S.SubSequence

with a comment saying that ideally the set of constraints would apply to the SequenceType protocol but that's not currently possible. This makes sense for the other constraints (that SubSequence conforms to SequenceType and has the same element), but this particular constraint, that the subsequence type must have itself as its own subsequence, surprises me a little. I can see why it's needed here (because that's the only way you can guarantee that recursing through SubSequences always finds SequenceTypes with the right element), but ideally we wouldn't actually require it to be the _same_ sequence, just that it is some sequence with the same element type. If we ever change Swift such that these constraints can be expressed on the SequenceType definition itself, then presumably we'll be able to drop this == constraint entirely as the SequenceType protocol itself will ensure that its subsequence is a sequence of the same element type (which will satisfy the need to have it be true after arbitrary levels of recursion).

You’re totally right again. I will make these changes to the proposal.

max

[a bunch of text removed]

Hi Kevin,

Thank you for your feedback!

2. One of the added constraints looks like

S.SubSequence.SubSequence == S.SubSequence

with a comment saying that ideally the set of constraints would apply to
the SequenceType protocol but that's not currently possible. This makes
sense for the other constraints (that SubSequence conforms to SequenceType
and has the same element), but this particular constraint, that the
subsequence type must have itself as its own subsequence, surprises me a
little. I can see why it's needed here (because that's the only way you can
guarantee that recursing through SubSequences always finds SequenceTypes
with the right element), but ideally we wouldn't actually require it to be
the _same_ sequence, just that it is some sequence with the same element
type. If we ever change Swift such that these constraints can be expressed
on the SequenceType definition itself, then presumably we'll be able to
drop this == constraint entirely as the SequenceType protocol itself will
ensure that its subsequence is a sequence of the same element type (which
will satisfy the need to have it be true after arbitrary levels of
recursion).

The idea behind putting this constraint into the protocol was to make it
possible to write code that repeatedly slices a collection without getting
a ton of different types along the way:

var myCollectionSlice = myCollection[myCollection.indices]
myCollectionSlice = myCollectionSlice.dropFirst()

Also, we couldn't come up with an example of a sequence or a collection
that needs to have different SubSequence types on different depth levels
for efficiency or type safety reasons. Given that we think we aren't
limiting expressivity with this constraint, having a simpler model (the
operation of slicing slices is closed in the set of types) is better.

I'd be happy to hear if you know some sequence or collection types that
would benefit from not having this constraint.

Dmitri

···

On Fri, Dec 18, 2015 at 3:13 PM, Kevin Ballard via swift-evolution < swift-evolution@swift.org> wrote:

--
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>*/

Fair enough. I was thinking that it's better to err on the side of
allowing flexibility, but there is something to be said for having
slices of slices still be slices. My vague thought was that there might
be some desire to have a slice be a type that wraps the thing being
sliced, but I admit that I can't think offhand of any reason why a
FooSlice<FooSlice<FooSlice<Foo>>> would be useful.

-Kevin

···

On Fri, Dec 18, 2015, at 08:51 PM, Dmitri Gribenko wrote:

Hi Kevin,

Thank you for your feedback!

On Fri, Dec 18, 2015 at 3:13 PM, Kevin Ballard via swift-evolution <swift- > evolution@swift.org> wrote:

2. One of the added constraints looks like

S.SubSequence.SubSequence == S.SubSequence

with a comment saying that ideally the set of constraints would apply
to the SequenceType protocol but that's not currently possible. This
makes sense for the other constraints (that SubSequence conforms to
SequenceType and has the same element), but this particular
constraint, that the subsequence type must have itself as its own
subsequence, surprises me a little. I can see why it's needed here
(because that's the only way you can guarantee that recursing through
SubSequences always finds SequenceTypes with the right element), but
ideally we wouldn't actually require it to be the _same_ sequence,
just that it is some sequence with the same element type. If we ever
change Swift such that these constraints can be expressed on the
SequenceType definition itself, then presumably we'll be able to drop
this == constraint entirely as the SequenceType protocol itself will
ensure that its subsequence is a sequence of the same element type
(which will satisfy the need to have it be true after arbitrary
levels of recursion).

The idea behind putting this constraint into the protocol was to make
it possible to write code that repeatedly slices a collection without
getting a ton of different types along the way:

var myCollectionSlice = myCollection[myCollection.indices]
myCollectionSlice = myCollectionSlice.dropFirst()

Also, we couldn't come up with an example of a sequence or a
collection that needs to have different SubSequence types on different
depth levels for efficiency or type safety reasons. Given that we
think we aren't limiting expressivity with this constraint, having a
simpler model (the operation of slicing slices is closed in the set of
types) is better.

I'd be happy to hear if you know some sequence or collection types
that would benefit from not having this constraint.

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>*/

Well actually...

LazyCollection right now has just this very behavior. The SubSequence of
a LazyCollection<T> is a LazyCollection<Slice<T>>. If you say
`[1,2,3].lazy.prefixUpTo(3).prefixUpTo(3)` you end up with a
LazyCollection<Slice<Slice<[Int]>>>. So the only way we can constrain
SubSequence this way is by also making it possible for LazyCollection to
"flatten" the slices.

-Kevin Ballard

···

On Fri, Dec 18, 2015, at 10:03 PM, Kevin Ballard wrote:

Fair enough. I was thinking that it's better to err on the side of
allowing flexibility, but there is something to be said for having
slices of slices still be slices. My vague thought was that there
might be some desire to have a slice be a type that wraps the thing
being sliced, but I admit that I can't think offhand of any reason why
a FooSlice<FooSlice<FooSlice<Foo>>> would be useful.

-Kevin

On Fri, Dec 18, 2015, at 08:51 PM, Dmitri Gribenko wrote:

Hi Kevin,

Thank you for your feedback!

On Fri, Dec 18, 2015 at 3:13 PM, Kevin Ballard via swift-evolution >> <swift-evolution@swift.org> wrote:

2. One of the added constraints looks like

S.SubSequence.SubSequence == S.SubSequence

with a comment saying that ideally the set of constraints would
apply to the SequenceType protocol but that's not currently
possible. This makes sense for the other constraints (that
SubSequence conforms to SequenceType and has the same element), but
this particular constraint, that the subsequence type must have
itself as its own subsequence, surprises me a little. I can see why
it's needed here (because that's the only way you can guarantee that
recursing through SubSequences always finds SequenceTypes with the
right element), but ideally we wouldn't actually require it to be
the _same_ sequence, just that it is some sequence with the same
element type. If we ever change Swift such that these constraints
can be expressed on the SequenceType definition itself, then
presumably we'll be able to drop this == constraint entirely as the
SequenceType protocol itself will ensure that its subsequence is a
sequence of the same element type (which will satisfy the need to
have it be true after arbitrary levels of recursion).

The idea behind putting this constraint into the protocol was to make
it possible to write code that repeatedly slices a collection without
getting a ton of different types along the way:

var myCollectionSlice = myCollection[myCollection.indices]
myCollectionSlice = myCollectionSlice.dropFirst()

Also, we couldn't come up with an example of a sequence or a
collection that needs to have different SubSequence types on
different depth levels for efficiency or type safety reasons. Given
that we think we aren't limiting expressivity with this constraint,
having a simpler model (the operation of slicing slices is closed in
the set of types) is better.

I'd be happy to hear if you know some sequence or collection types
that would benefit from not having this constraint.

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>*/

Well actually...

LazyCollection right now has just this very behavior. The SubSequence of a
LazyCollection<T> is a LazyCollection<Slice<T>>. If you say
`[1,2,3].lazy.prefixUpTo(3).prefixUpTo(3)` you end up with a
LazyCollection<Slice<Slice<[Int]>>>. So the only way we can constrain
SubSequence this way is by also making it possible for LazyCollection to
"flatten" the slices.

Indeed, thanks for noticing this! Multiple levels of Slice<T>
wrapping is bad not just because of the type, but because each Slice
has its own index bounds stored, and every access through a Slice
needs to perform a range check. So having multiple levels of wrapping
would affect performance in this case.

If we tested LazyCollection with `addForwardCollectionTests()` from
StdlibUnittest, we would have noticed.

The fix might be here:

// stdlib/public/core/LazyCollection.swift
public subscript(bounds: Range<Index>) -> LazyCollection<Slice<Base>>

public subscript(bounds: Range<Index>) -> LazyCollection<Base.SubSequence>

(Haven't compiled it.)

I opened [SR-318] LazyCollection.SubSequence.SubSequence introduces multiple levels of Slice wrapping · Issue #42940 · apple/swift · GitHub for this issue.

Dmitri

···

On Fri, Dec 18, 2015 at 10:08 PM, Kevin Ballard <kevin@sb.org> wrote:

--
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>*/