[Accepted with Revision] SE-0094: Add sequence(initial:next:) and sequence(state:next:) to the stdlib


(Chris Lattner) #1

Proposal Link: https://github.com/apple/swift-evolution/blob/master/proposals/0094-sequence-function.md

The review of "SE-0094: Add sequence(initial:next:) and sequence(state:next:) to the stdlib" ran from May 19…23, 2016. The proposal has been *accepted* with one minor naming-related change:

- Feedback from the community & core team is positive.
- Core team discussed whether it made sense to add just the first form, or whether it made sense to add both. They agree that although the form using an explicit state is much more infrequently used, when it is necessary, it is extremely helpful to have. It is also useful to consider both as a pair.
- On naming, the core team agrees with the community that “sequence(first:next:)” is a better name than "sequence(initial:next:)”. "sequence(state:next:)” is approved as-is.

Thank you to Kevin Ballard and Erica Sadun for proposing this both in SE-0045 and in SE-0094, an implementation of these functions would be welcome!

-Chris Lattner
Review Manager


(Jacob Bandes-Storch) #2

Great news!

I've filed a bug for this in JIRA: https://bugs.swift.org/browse/SR-1622

···

On Wed, May 25, 2016 at 7:44 PM, Chris Lattner via swift-evolution < swift-evolution@swift.org> wrote:

Proposal Link:
https://github.com/apple/swift-evolution/blob/master/proposals/0094-sequence-function.md

The review of "SE-0094: Add sequence(initial:next:) and
sequence(state:next:) to the stdlib" ran from May 19…23, 2016. The proposal
has been *accepted* with one minor naming-related change:

- Feedback from the community & core team is positive.
- Core team discussed whether it made sense to add just the first form, or
whether it made sense to add both. They agree that although the form using
an explicit state is much more infrequently used, when it is necessary, it
is extremely helpful to have. It is also useful to consider both as a pair.
- On naming, the core team agrees with the community that
“sequence(first:next:)” is a better name than "sequence(initial:next:)”.
"sequence(state:next:)” is approved as-is.

Thank you to Kevin Ballard and Erica Sadun for proposing this both in
SE-0045 and in SE-0094, an implementation of these functions would be
welcome!

-Chris Lattner
Review Manager

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


(Lily Ballard) #3

On Thu, May 19, 2016, at 05:52 PM, Kevin Ballard wrote (on a
different thread):

After having given this some thought, it seems apparent that
`sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where
the closure captures a single mutable variable. The microbenchmark
performance may differ slightly, as the AnyIterator version will
allocate a box on the heap to hold the captured variable (assuming it
can't get inlined entirely), whereas UnfoldSequence won't. But the
functionality is the same.

For the record, I just realized that the type signature of
UnfoldSequence<T> actually requires that we do heap allocation as well,
because this type can only be used for the stateful version if we erase
the state type by capturing it in a closure.

As part of implementing this, I'm going to go ahead and modify the type
signature to UnfoldSequence<T, State>, with `state(first:next:)`
returning the type UnfoldSequence<T, T?>. I think it's better to diverge
slightly from the proposal than it is to introduce unnecessary (albeit
small) performance cost. I hope there are no objections.

-Kevin Ballard


Troubling `Sequence`
(Lily Ballard) #4

And I've just grabbed that bug, and will whip up an initial
implementation shortly :smiley:

I'm also going to update the proposal with the name change in a minute.

-Kevin Ballard

···

On Wed, May 25, 2016, at 07:54 PM, Jacob Bandes-Storch via swift-evolution wrote:

Great news!

I've filed a bug for this in JIRA:
https://bugs.swift.org/browse/SR-1622

On Wed, May 25, 2016 at 7:44 PM, Chris Lattner via swift-evolution <swift- > evolution@swift.org> wrote:

Proposal Link:
https://github.com/apple/swift-evolution/blob/master/proposals/0094-sequence-function.md

The review of "SE-0094: Add sequence(initial:next:) and
sequence(state:next:) to the stdlib" ran from May 19…23, 2016. The
proposal has been *accepted* with one minor naming-related change:

- Feedback from the community & core team is positive.
- Core team discussed whether it made sense to add just the first
   form, or whether it made sense to add both. They agree that
   although the form using an explicit state is much more
   infrequently used, when it is necessary, it is extremely helpful
   to have. It is also useful to consider both as a pair.
- On naming, the core team agrees with the community that
   “sequence(first:next:)” is a better name than
   "sequence(initial:next:)”. "sequence(state:next:)” is approved
   as-is.

Thank you to Kevin Ballard and Erica Sadun for proposing this both
in SE-0045 and in SE-0094, an implementation of these functions
would be welcome!

-Chris Lattner
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


(Chris Lattner) #5

That makes sense to me - the core team review discussion did not specifically discuss the return type in question, nor its naming. In my opinion, these implementation concerns can be handled by patch review process.

-Chris

···

On May 25, 2016, at 8:39 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

On Thu, May 19, 2016, at 05:52 PM, Kevin Ballard wrote (on a different thread):

After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.

For the record, I just realized that the type signature of UnfoldSequence<T> actually requires that we do heap allocation as well, because this type can only be used for the stateful version if we erase the state type by capturing it in a closure.

As part of implementing this, I'm going to go ahead and modify the type signature to UnfoldSequence<T, State>, with `state(first:next:)` returning the type UnfoldSequence<T, T?>. I think it's better to diverge slightly from the proposal than it is to introduce unnecessary (albeit small) performance cost. I hope there are no objections.


(Lily Ballard) #6

>
> On Thu, May 19, 2016, at 05:52 PM, Kevin Ballard wrote (on a different thread):
>> After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.
>
> For the record, I just realized that the type signature of UnfoldSequence<T> actually requires that we do heap allocation as well, because this type can only be used for the stateful version if we erase the state type by capturing it in a closure.
>
> As part of implementing this, I'm going to go ahead and modify the type signature to UnfoldSequence<T, State>, with `state(first:next:)` returning the type UnfoldSequence<T, T?>. I think it's better to diverge slightly from the proposal than it is to introduce unnecessary (albeit small) performance cost. I hope there are no objections.

And of course I spoke too soon, because T? isn't the right state to handle this. It looks like I'll end up going with UnfoldSequence<T, (T?, Bool)>. Slightly ugly, but most people won't be typing it that often, and we've had worse (such as LazyMapSequence<LazyFilterSequence<LazyMapSequence<Self.Elements, ElementOfResult?>>, ElementOfResult>, which is quite a mouthful).

That makes sense to me - the core team review discussion did not specifically discuss the return type in question, nor its naming. In my opinion, these implementation concerns can be handled by patch review process.

Glad to hear it.

-Kevin Ballard

···

On Wed, May 25, 2016, at 08:49 PM, Chris Lattner wrote:

> On May 25, 2016, at 8:39 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:


Troubling `Sequence`
(Patrick Smith) #7

Just a dumb question, can you have two different types? UnfoldSequence and UnfoldStateSequence? Then they can have more focused generic parameters.

···

On 26 May 2016, at 1:51 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

On Wed, May 25, 2016, at 08:49 PM, Chris Lattner wrote:

On May 25, 2016, at 8:39 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

On Thu, May 19, 2016, at 05:52 PM, Kevin Ballard wrote (on a different thread):

After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.

For the record, I just realized that the type signature of UnfoldSequence<T> actually requires that we do heap allocation as well, because this type can only be used for the stateful version if we erase the state type by capturing it in a closure.

As part of implementing this, I'm going to go ahead and modify the type signature to UnfoldSequence<T, State>, with `state(first:next:)` returning the type UnfoldSequence<T, T?>. I think it's better to diverge slightly from the proposal than it is to introduce unnecessary (albeit small) performance cost. I hope there are no objections.

And of course I spoke too soon, because T? isn't the right state to handle this. It looks like I'll end up going with UnfoldSequence<T, (T?, Bool)>. Slightly ugly, but most people won't be typing it that often, and we've had worse (such as LazyMapSequence<LazyFilterSequence<LazyMapSequence<Self.Elements, ElementOfResult?>>, ElementOfResult>, which is quite a mouthful).

That makes sense to me - the core team review discussion did not specifically discuss the return type in question, nor its naming. In my opinion, these implementation concerns can be handled by patch review process.

Glad to hear it.

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


(Lily Ballard) #8

We could, but my plan was to implement sequence(first:next:) as a call to sequence(state:next:). I could of course implement it twice, but that would presumably result in slightly larger code size and a larger API surface (because there's a whole extra type there). I think this sort of thing can be hashed out in patch review if anyone feels strongly about it.

-Kevin Ballard

···

On Wed, May 25, 2016, at 08:56 PM, Patrick Smith wrote:

Just a dumb question, can you have two different types? UnfoldSequence and UnfoldStateSequence? Then they can have more focused generic parameters.

> On 26 May 2016, at 1:51 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:
>
> On Wed, May 25, 2016, at 08:49 PM, Chris Lattner wrote:
>>
>>> On May 25, 2016, at 8:39 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:
>>>
>>> On Thu, May 19, 2016, at 05:52 PM, Kevin Ballard wrote (on a different thread):
>>>> After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.
>>>
>>> For the record, I just realized that the type signature of UnfoldSequence<T> actually requires that we do heap allocation as well, because this type can only be used for the stateful version if we erase the state type by capturing it in a closure.
>>>
>>> As part of implementing this, I'm going to go ahead and modify the type signature to UnfoldSequence<T, State>, with `state(first:next:)` returning the type UnfoldSequence<T, T?>. I think it's better to diverge slightly from the proposal than it is to introduce unnecessary (albeit small) performance cost. I hope there are no objections.
>
> And of course I spoke too soon, because T? isn't the right state to handle this. It looks like I'll end up going with UnfoldSequence<T, (T?, Bool)>. Slightly ugly, but most people won't be typing it that often, and we've had worse (such as LazyMapSequence<LazyFilterSequence<LazyMapSequence<Self.Elements, ElementOfResult?>>, ElementOfResult>, which is quite a mouthful).
>
>> That makes sense to me - the core team review discussion did not specifically discuss the return type in question, nor its naming. In my opinion, these implementation concerns can be handled by patch review process.
>
> Glad to hear it.
>
> -Kevin Ballard
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #9

That being said, since we now have generic typealiases, I could presumably just have something like

public typealias UnfoldFirstSequence<T> = UnfoldSequence<T, (T?, Bool)>

-Kevin Ballard

···

On Wed, May 25, 2016, at 09:01 PM, Kevin Ballard wrote:

We could, but my plan was to implement sequence(first:next:) as a call to sequence(state:next:). I could of course implement it twice, but that would presumably result in slightly larger code size and a larger API surface (because there's a whole extra type there). I think this sort of thing can be hashed out in patch review if anyone feels strongly about it.

-Kevin Ballard

On Wed, May 25, 2016, at 08:56 PM, Patrick Smith wrote:
> Just a dumb question, can you have two different types? UnfoldSequence and UnfoldStateSequence? Then they can have more focused generic parameters.
>
>
> > On 26 May 2016, at 1:51 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:
> >
> > On Wed, May 25, 2016, at 08:49 PM, Chris Lattner wrote:
> >>
> >>> On May 25, 2016, at 8:39 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:
> >>>
> >>> On Thu, May 19, 2016, at 05:52 PM, Kevin Ballard wrote (on a different thread):
> >>>> After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.
> >>>
> >>> For the record, I just realized that the type signature of UnfoldSequence<T> actually requires that we do heap allocation as well, because this type can only be used for the stateful version if we erase the state type by capturing it in a closure.
> >>>
> >>> As part of implementing this, I'm going to go ahead and modify the type signature to UnfoldSequence<T, State>, with `state(first:next:)` returning the type UnfoldSequence<T, T?>. I think it's better to diverge slightly from the proposal than it is to introduce unnecessary (albeit small) performance cost. I hope there are no objections.
> >
> > And of course I spoke too soon, because T? isn't the right state to handle this. It looks like I'll end up going with UnfoldSequence<T, (T?, Bool)>. Slightly ugly, but most people won't be typing it that often, and we've had worse (such as LazyMapSequence<LazyFilterSequence<LazyMapSequence<Self.Elements, ElementOfResult?>>, ElementOfResult>, which is quite a mouthful).
> >
> >> That makes sense to me - the core team review discussion did not specifically discuss the return type in question, nor its naming. In my opinion, these implementation concerns can be handled by patch review process.
> >
> > Glad to hear it.
> >
> > -Kevin Ballard
> > _______________________________________________
> > swift-evolution mailing list
> > swift-evolution@swift.org
> > https://lists.swift.org/mailman/listinfo/swift-evolution
>