[swift-evolution] Feature proposal: Range operator with step
Xiaodi Wu
xiaodi.wu at gmail.com
Thu Mar 31 12:45:43 CDT 2016
Thoughts on an edge case: so long as it's possible to use
`stride(from:to:by:)` with Double, we'll need to figure out what
happens when you have `stride(from: 0.0, to: DBL_MAX, by: DBL_MIN)`.
Bounds may be unknown at compile time, obviously.
Currently (this is by reasoning through the code, not actually
observing it run), `for i in stride(from: 0.0, to: DBL_MAX, by:
DBL_MIN) { }` degenerates into an infinite loop once you reach
sufficient large values such that `current + stride == current`, which
for a stride of DBL_MIN should happen pretty quickly.
In Erica's proposed floating point Stride, an Int is used to count
iterations (and iterations need to be counted in order to avoid
accumulating error). Thus, one must break from `for i in stride(from:
0.0, to: DBL_MAX, by: DBL_MIN) { }` before the iteration counter
overflows or it will trap. IMO, trapping at some point is fine, but I
think a limit of Int.max iterations might be rather arbitrary for a
StrideTo<Double> (or whatever it will be named) and I'm not sure how
one can justify why the behavior of StrideTo<Double> would change from
machine to machine based on the size of Int.
I've been waffling between using an Int counter as Erica does or a
counter of type Strideable.Stride in `StrideTo<Strideable where
Strideable.Stride : FloatingPoint>`. In the latter alternative, no
trapping occurs, but error begins to accumulate when the iteration
counter is too large to represent integers exactly (e.g., 2^53 for
Double). In that case, `for i in stride(from: 0.0, to: DBL_MAX, by:
DBL_MIN) { }` degenerates into an infinite loop eventually (once
`iterationCount + 1.0 == iterationCount`) and never traps, which I'm
not sure I like, but a limit of 2^53 iterations bears at least a
rational connection to Double and is known at compile time independent
of the supplied bounds. We could alternatively return nil on reaching
2^53 iterations, trap, etc.
Comments?
On Wed, Mar 30, 2016 at 1:42 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>
> on Tue Mar 29 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>
>> On Tue, Mar 29, 2016 at 7:48 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>>>
>>> on Tue Mar 29 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>>>
>>>> Relatedly, while you're tackling this big revision:
>>>>
>>
>>>> I've tried to play around with what it would take to write a generic
>>>> non-error-accumulating striding method, and afaict, it would be
>>>> enormously cleaner if Strideable types are guaranteed to have + and *
>>>> (well, Strideable.Stride needs *, to be more accurate),
>>>
>>> That should happen automatically, since it conforms to SignedNumber,
>>> when we get the Integer protocols updated (project currently on hold while
>>> we land this other revision).
>>>
>>>> since the iterator needs to be able to compute end = start + iteration
>>>> * stride.
>>>
>>> Don't you need division too if you're going to do this?
>>
>> I didn't seem to ever need division. See attached playground (which
>> borrows shamelessly from existing code and Erica's proposal, and which
>> is written in Swift 2.2 because that's what I had handy).
>
> I guess it depends what semantics you want. Maybe the semantics that
> need division are better suited to a different API:
>
> (a..<b).striding(stepCount: 10)
>
>>>> Is that going to be exposed somewhere in the cascade of numeric
>>>> protocols that culminate in Strideable?
>>>
>>> That's not in the plan. I'm pretty sure we want UnsafePointer to be
>>> Strideable and we don't want it to have multiplication or division.
>>
>> You're right. The type itself doesn't need to have multiplication or
>> division. In fact, writing this, I'm going back and changing my
>> playground a bit. It's sufficient that UnsafePointer.Stride can be
>> multiplied, and if SignedNumber conformance will guarantee
>> multiplication for all conforming types, we're all set for floating
>> point.
>>
>>>
>>> I was thinking the StrideSequence (or some such) should be exposed as an
>>> associated type of the Strideable, so it can be as efficient as possible
>>> when no FP error is possible. We don't want to spend divisions on
>>> striding over Ints.
>>
>> Right, multiplication or division best avoided here. Not sure what the
>> associated type StrideSequence would be for though?
>
> Well, the multiplications can likely be optimized away, so maybe it's a
> non-issue. It's really worth looking at the code you get at -O, to see
> if we can avoid complicating the API.
>
> The thinking was that a Strideable type could have a StrideSequence with
> a default of StrideByAdding<Self>, while FloatingPoint types would use
> StrideSequence = StrideByMultiplying<Self>.
>
>> Are you aiming for one StrideTo type and one StrideThrough type
>> instead of two apiece
>
> Either way would be reasonable, depending on how well it optimizes.
>
>> , one for floating point and one for integer?
>
> No, one for FP and one for most everything else.
>
>> I've been lazy and overloading `stride(from:to:by:)` instead, but
>> there's a lot of repeated code.
>>
>>>
>>>> On Mon, Mar 28, 2016 at 7:45 PM Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>>
>>>> on Mon Mar 28 2016, Dave Abrahams <swift-evolution at swift.org> wrote:
>>>>
>>>> > on Mon Mar 28 2016, Erica Sadun <swift-evolution at swift.org> wrote:
>>>> >
>>>> >>> On Mar 28, 2016, at 3:54 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>>> >>>
>>>> >>>
>>>> >>> on Mon Mar 28 2016, Erica Sadun <swift-evolution at swift.org> wrote:
>>>> >>>
>>>> >>
>>>> >>>>> On Mar 28, 2016, at 3:25 PM, Dave Abrahams via swift-evolution
>>>> >>>>> <swift-evolution at swift.org> wrote:
>>>> >>>>>
>>>> >>>>>
>>>> >>>>> on Mon Mar 28 2016, Xiaodi Wu
>>>> >>>>
>>>> >>>>> <swift-evolution at swift.org
>>>> >>>>> <mailto:swift-evolution at swift.org>>
>>>> >>>>> wrote:
>>>> >>>>>
>>>> >>>>>> Right, Countable could refine Strideable. I'm no expert on this, but
>>>> >>>>>> some cursory reading suggests that the analogous feature in C++ simply
>>>> >>>>>> requires the type to have operator++ defined. Obviously, that won't
>>>> >>>>>> work for Swift 3.0...
>>>> >>>>>
>>>> >>>>> Hmm, instead of defining a new protocol (Countable), what if we just use
>>>> >>>>> “Strideable where Stride : Integer” as a constraint?
>>>> >>>>
>>>> >>>> I like a differentiation between continuous and discrete things
>>>> >>>> although both can have ranges, membership, fences,
>>>> >>>> and a way to stride through them
>>>> >>>
>>>> >>> Strideable where Stride : Integer expresses just exactly that. Now if I
>>>> >>> could only get the type-checker to cooperate...
>>>> >>
>>>> >> I am ridiculously excited about what you're doing there.
>>>> >> Looking forward to beautiful floating point strides if for no
>>>> >> other reason than I can point out how well they work for math
>>>> >> in comparison to traditional for;;loops, so maybe people will
>>>> >> stop burning semicolons on my lawn.
>>>> >
>>>> > The basics:
>>>> > https://github.com/apple/swift/commit/a5c3c63c3d5d940f729c23aab342ea4d270d264a
>>>>
>>>> Hi Erica,
>>>>
>>>> After some consideration, while I want to see the smart
>>>> (x..<y).striding(by: z) stuff happen too, it's somewhat incidental to
>>>> the (already massive) project we're undertaking in this branch. Would
>>>> you like to take on the implementation and/or proposal? I'd be happy to
>>>> provide guidance.
>>>>
>>>> --
>>>> Dave
>>>>
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>
>>>
>>> --
>>> Dave
>>
>
> --
> Dave
More information about the swift-evolution
mailing list