[Discussion] stride behavior and a little bit of a call-back to digital numbers


(Erica Sadun) #1

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type? <http://article.gmane.org/gmane.comp.lang.swift.evolution/7130/match=decimal>) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica


(Erica Sadun) #2

Following up to myself. Thoughts and feedback are welcome. -- Erica

Changing the Behavior of StrideThroughGenerator

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to change the way the through variation works.

Current Art

A Strideable to sequence returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in
the progression that is less than end.

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + tride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”
Proposed Modifications

I recommend the following changes:

Change the documentation text from

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

to

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression greater than or equal to end. There is no guarantee that end is an element of the sequence.

Modify the implementation

Current:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            if current == end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
Proposed:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            // NOTE: `current >= end` and not `current == end`
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
}
Introduced Changes

Under these changes, the following progression ends at 2.0 not 1.9:

print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
Integer progressions are unchanged:

print(Array(1.stride(through2: 10, by: 1)))
/// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Floating point strides will extend up-to or past the through value:

// Old
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75]

// New
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75, 2.0]
Alternates Considered

Other changes could include:

Introducing a digitalStride function with a set precision that works in integer math, multiplying each value by 10n, converting to integers, and then working back to floating point after each change
Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.
Introducing a DecimalNumber type, with its own stride methods, e.g. DecimalNumber(1.0).stride(through:DecimalNumber(2.0), by: DecimalNumber(0.1)).

···

On Feb 26, 2016, at 5:12 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type? <http://article.gmane.org/gmane.comp.lang.swift.evolution/7130/match=decimal>) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica

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


(Sune Foldager) #3

The documentation is a bit weird. "It returns the sequence where last is less than or equal to `end`.” seems to tacitly assume that we’re talking about the longest possible sequence with that property. With your proposed "It returns the sequence where last is greater than or equal to `end`?” we’re now talking about the shortest possible sequence with that property.

But what do you mean “no change for integers”? What about 1.stride(through: 10, by: 8)? Wouldn’t that return [1, 9] now and [1, 9, 17] with your change?

—S

···

On 27 Feb 2016, at 01:12, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).


(William Dillon) #4

I like this proposal. Even the corrected integer case feels more correct to me. I think that the core of stride is (not surprisingly) the stride.

So, in the integer case as well as the floating case, I would expect through to stride past the terminus if it isn’t an integer multiple of the stride in the through case. Likewise, of course, it would stop before the end in the to case.

+1 from me.

- Will

···

On February 27, 2016 at 3:36:41 PM, Erica Sadun via swift-evolution (swift-evolution@swift.org) wrote:

The documentation is a bit weird. "It returns the sequence where last is less than or equal to `end`.” seems to tacitly assume that we’re talking about the longest possible sequence with that property. With your proposed "It returns the sequence where last is greater than or equal to `end`?” we’re now talking about the shortest possible sequence with that property.

But what do you mean “no change for integers”? What about 1.stride(through: 10, by: 8)? Wouldn’t that return [1, 9] now and [1, 9, 17] with your change?

It means, I'm wrong about that. Fixing here, both in code and in text: https://gist.github.com/erica/03c398c06f6c47824429

print(Array(1.stride(through: 10, by: 8)))
[1, 9]

print(Array(1.stride(through2: 10, by: 8))) // my test implementation
[1, 9, 17]

The second progress now goes *through* 10.

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


(Erica Sadun) #5

The documentation is a bit weird. "It returns the sequence where last is less than or equal to `end`.” seems to tacitly assume that we’re talking about the longest possible sequence with that property. With your proposed "It returns the sequence where last is greater than or equal to `end`?” we’re now talking about the shortest possible sequence with that property.

But what do you mean “no change for integers”? What about 1.stride(through: 10, by: 8)? Wouldn’t that return [1, 9] now and [1, 9, 17] with your change?

It means, I'm wrong about that. Fixing here, both in code and in text: https://gist.github.com/erica/03c398c06f6c47824429

print(Array(1.stride(through: 10, by: 8)))
[1, 9]

print(Array(1.stride(through2: 10, by: 8))) // my test implementation
[1, 9, 17]

The second progress now goes *through* 10.

-- E


(Joe Groff) #6

As implemented, `stride` is broken for floating-point numbers. Instead of repeatedly adding the `by` interval, it should multiply the interval by successive integral values and add that to the base to avoid accruing error. Your proposal only papers over the problem.

-Joe

···

On Feb 27, 2016, at 3:27 PM, Erica Sadun <erica@ericasadun.com> wrote:

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”


(Charles Kissinger) #7

Hi Erica,

With your suggested change, there would be no way to specify a precise upper bound for a sequence (except for integers in specific cases). The current pair of functions provide numbers in the intervals [a, b) and [a,b], which is what is needed to cover all use cases. With your change, the two functions would produce sequences that potentially lie either in the interval [a, b) for "stride to” or [a, infinity] for "stride through” since the size of the stride isn’t necessarily known at compile time or predictable.

In addition to breaking existing code, it would not cover every use case. Sometimes you won’t know the stride until runtime, but you know it has to be able to reach but not exceed a certain value.

—CK

···

On Feb 27, 2016, at 3:27 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

Following up to myself. Thoughts and feedback are welcome. -- Erica

Changing the Behavior of StrideThroughGenerator

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to change the way the through variation works.

Current Art

A Strideable to sequence returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in
the progression that is less than end.

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + tride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”
Proposed Modifications

I recommend the following changes:

Change the documentation text from

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

to

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression greater than or equal to end. There is no guarantee that end is an element of the sequence.

Modify the implementation

Current:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            if current == end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
Proposed:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            // NOTE: `current >= end` and not `current == end`
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
}
Introduced Changes

Under these changes, the following progression ends at 2.0 not 1.9:

print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
Integer progressions are unchanged:

print(Array(1.stride(through2: 10, by: 1)))
/// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Floating point strides will extend up-to or past the through value:

// Old
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75]

// New
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75, 2.0]
Alternates Considered

Other changes could include:

Introducing a digitalStride function with a set precision that works in integer math, multiplying each value by 10n, converting to integers, and then working back to floating point after each change
Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.
Introducing a DecimalNumber type, with its own stride methods, e.g. DecimalNumber(1.0).stride(through:DecimalNumber(2.0), by: DecimalNumber(0.1)).

On Feb 26, 2016, at 5:12 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type? <http://article.gmane.org/gmane.comp.lang.swift.evolution/7130/match=decimal>) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto: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


(Joseph Lord) #8

If this happened how would legacy code be handled and a migratory written. I'm really nervous about small changes to semantics causing bugs. Would be more comfortable if the 'through' argument was renamed to force people to reconsider and check their code. It shouldn't have a migratory and the error on calling the old through variant should produce a very informative warning describing the semantic change.

Whether the change is worthwhile at all I'm not entirely sure, I haven't floating point stride much.

Joseph

···

On Feb 27, 2016, at 11:27 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

Following up to myself. Thoughts and feedback are welcome. -- Erica

Changing the Behavior of StrideThroughGenerator

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to change the way the through variation works.

Current Art

A Strideable to sequence returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in
the progression that is less than end.

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + tride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”
Proposed Modifications

I recommend the following changes:

Change the documentation text from

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

to

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression greater than or equal to end. There is no guarantee that end is an element of the sequence.

Modify the implementation

Current:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            if current == end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
Proposed:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            // NOTE: `current >= end` and not `current == end`
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
}
Introduced Changes

Under these changes, the following progression ends at 2.0 not 1.9:

print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
Integer progressions are unchanged:

print(Array(1.stride(through2: 10, by: 1)))
/// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Floating point strides will extend up-to or past the through value:

// Old
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75]

// New
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75, 2.0]
Alternates Considered

Other changes could include:

Introducing a digitalStride function with a set precision that works in integer math, multiplying each value by 10n, converting to integers, and then working back to floating point after each change
Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.
Introducing a DecimalNumber type, with its own stride methods, e.g. DecimalNumber(1.0).stride(through:DecimalNumber(2.0), by: DecimalNumber(0.1)).

On Feb 26, 2016, at 5:12 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type?) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica

_______________________________________________
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


(Erica Sadun) #9

This is a really good point, and while I don't have a recommended direction, am adding to the write-up because it is so important.

-- E

···

On Feb 27, 2016, at 4:59 PM, Joseph Lord <joseph@human-friendly.com> wrote:

If this happened how would legacy code be handled and a migratory written. I'm really nervous about small changes to semantics causing bugs. Would be more comfortable if the 'through' argument was renamed to force people to reconsider and check their code. It shouldn't have a migratory and the error on calling the old through variant should produce a very informative warning describing the semantic change.

Whether the change is worthwhile at all I'm not entirely sure, I haven't floating point stride much.

Joseph

On Feb 27, 2016, at 11:27 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Following up to myself. Thoughts and feedback are welcome. -- Erica

Changing the Behavior of StrideThroughGenerator

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to change the way the through variation works.

Current Art

A Strideable to sequence returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in
the progression that is less than end.

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + tride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”
Proposed Modifications

I recommend the following changes:

Change the documentation text from

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

to

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression greater than or equal to end. There is no guarantee that end is an element of the sequence.

Modify the implementation

Current:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            if current == end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
Proposed:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            // NOTE: `current >= end` and not `current == end`
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
}
Introduced Changes

Under these changes, the following progression ends at 2.0 not 1.9:

print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
Integer progressions are unchanged:

print(Array(1.stride(through2: 10, by: 1)))
/// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Floating point strides will extend up-to or past the through value:

// Old
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75]

// New
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75, 2.0]
Alternates Considered

Other changes could include:

Introducing a digitalStride function with a set precision that works in integer math, multiplying each value by 10n, converting to integers, and then working back to floating point after each change
Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.
Introducing a DecimalNumber type, with its own stride methods, e.g. DecimalNumber(1.0).stride(through:DecimalNumber(2.0), by: DecimalNumber(0.1)).

On Feb 26, 2016, at 5:12 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type? <http://article.gmane.org/gmane.comp.lang.swift.evolution/7130/match=decimal>) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica

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

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


(Erica Sadun) #10

Impact on Existing Code

If this change were adopted, it could affect legacy code semantics written under current behaviors and assumptions. A migrator would not easily identify in-place workarounds like the through: 2.01 epsilon adjustment. I'd recommend adding "FIXME:" notes wherever through: is found to warn against continued use without a full inspection, offering links to information about the semantic changes.

Although renaming the through argument is another valid approach, renaming works against the proposed point that adapting through semantics better match what "through" actually means.

···

On Feb 27, 2016, at 4:59 PM, Joseph Lord <joseph@human-friendly.com> wrote:

If this happened how would legacy code be handled and a migratory written. I'm really nervous about small changes to semantics causing bugs. Would be more comfortable if the 'through' argument was renamed to force people to reconsider and check their code. It shouldn't have a migratory and the error on calling the old through variant should produce a very informative warning describing the semantic change.


(Erica Sadun) #11

As implemented, `stride` is broken for floating-point numbers. Instead of repeatedly adding the `by` interval, it should multiply the interval by successive integral values and add that to the base to avoid accruing error. Your proposal only papers over the problem.

-Joe

Agreed. This is "papering over the problem" of accumulated floating point error. There are two issues being addressed:

1. Semantics of `through` do not match their promise of going through the end point rather than stopping at it or before.
2. Floating point strides accumulate errors by repeatedly adding the `by` interval.

I mention issue 2 in the alternative implementations: https://gist.github.com/erica/03c398c06f6c47824429

Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.

If you were addressing issue 2, what approach would you suggest:

* Differentiating integer strides from floating point, and minimizing floating point errors?
* Leaving the tech as-is with minimal code change with a relatively high benefit?

In both cases, I'd still prefer the semantics to *go through* the end point, not just stop at it, which is issue 1.

-- E


(Erica Sadun) #12

Would you accept a third version then? towards (to, `[a, b)`), to (through, `[a, b]`), and through (new, `[a, >=b]` <-- not sure that even has a representation)?

-- E

···

On Feb 27, 2016, at 6:25 PM, Charles Kissinger <crk@akkyra.com> wrote:

Hi Erica,

With your suggested change, there would be no way to specify a precise upper bound for a sequence (except for integers in specific cases). The current pair of functions provide numbers in the intervals [a, b) and [a,b], which is what is needed to cover all use cases. With your change, the two functions would produce sequences that potentially lie either in the interval [a, b) for "stride to” or [a, infinity] for "stride through” since the size of the stride isn’t necessarily known at compile time or predictable.

In addition to breaking existing code, it would not cover every use case. Sometimes you won’t know the stride until runtime, but you know it has to be able to reach but not exceed a certain value.

—CK

On Feb 27, 2016, at 3:27 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Following up to myself. Thoughts and feedback are welcome. -- Erica

Changing the Behavior of StrideThroughGenerator

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to change the way the through variation works.

Current Art

A Strideable to sequence returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in
the progression that is less than end.

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + tride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”
Proposed Modifications

I recommend the following changes:

Change the documentation text from

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

to

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression greater than or equal to end. There is no guarantee that end is an element of the sequence.

Modify the implementation

Current:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            if current == end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
Proposed:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            // NOTE: `current >= end` and not `current == end`
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
}
Introduced Changes

Under these changes, the following progression ends at 2.0 not 1.9:

print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
Integer progressions are unchanged:

print(Array(1.stride(through2: 10, by: 1)))
/// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Floating point strides will extend up-to or past the through value:

// Old
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75]

// New
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75, 2.0]
Alternates Considered

Other changes could include:

Introducing a digitalStride function with a set precision that works in integer math, multiplying each value by 10n, converting to integers, and then working back to floating point after each change
Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.
Introducing a DecimalNumber type, with its own stride methods, e.g. DecimalNumber(1.0).stride(through:DecimalNumber(2.0), by: DecimalNumber(0.1)).

On Feb 26, 2016, at 5:12 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type? <http://article.gmane.org/gmane.comp.lang.swift.evolution/7130/match=decimal>) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica

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

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


(William Dillon) #13

I hope I’m not missing something, but I think Erica’s point on #1 is really important. When I originally learned about stride I assumed that the meaning of though was entirely different than what it really was. Erica’s idea brings it inline with my expectation based on its name.

Ignoring floating point entirely (which is still problematic):

print(Array(1.stride(through: 16, by: 7)))
// prints [1, 8, 15]
// I would expect [1, 8, 15, 22]
print(Array(1.stride(to: 16, by: 7)))
// prints [1, 8, 15]
The only cases where through behaves as I expect in the integer case is when the stride is a factor of through.

I do understand why someone would want to have a stride that ends on the terminal number if it equal, and not go over, but it feels like a label such as including, or something similar, would be more appropriate.

- Will

···

On February 27, 2016 at 5:06:36 PM, Erica Sadun via swift-evolution (swift-evolution@swift.org) wrote:

As implemented, `stride` is broken for floating-point numbers. Instead of repeatedly adding the `by` interval, it should multiply the interval by successive integral values and add that to the base to avoid accruing error. Your proposal only papers over the problem.

-Joe

Agreed. This is "papering over the problem" of accumulated floating point error. There are two issues being addressed:

1. Semantics of `through` do not match their promise of going through the end point rather than stopping at it or before.
2. Floating point strides accumulate errors by repeatedly adding the `by` interval.

I mention issue 2 in the alternative implementations: https://gist.github.com/erica/03c398c06f6c47824429

Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.

If you were addressing issue 2, what approach would you suggest:

* Differentiating integer strides from floating point, and minimizing floating point errors?
* Leaving the tech as-is with minimal code change with a relatively high benefit?

In both cases, I'd still prefer the semantics to *go through* the end point, not just stop at it, which is issue 1.

-- E

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


(Charles Kissinger) #14

Would you accept a third version then? towards (to, `[a, b)`), to (through, `[a, b]`), and through (new, `[a, >=b]` <-- not sure that even has a representation)?

No objection here. It’s a really interesting problem you’ve pointed out. I’m not sure yet the best way to minimize it.

—CK

···

On Feb 27, 2016, at 5:38 PM, Erica Sadun <erica@ericasadun.com> wrote:

-- E

On Feb 27, 2016, at 6:25 PM, Charles Kissinger <crk@akkyra.com <mailto:crk@akkyra.com>> wrote:

Hi Erica,

With your suggested change, there would be no way to specify a precise upper bound for a sequence (except for integers in specific cases). The current pair of functions provide numbers in the intervals [a, b) and [a,b], which is what is needed to cover all use cases. With your change, the two functions would produce sequences that potentially lie either in the interval [a, b) for "stride to” or [a, infinity] for "stride through” since the size of the stride isn’t necessarily known at compile time or predictable.

In addition to breaking existing code, it would not cover every use case. Sometimes you won’t know the stride until runtime, but you know it has to be able to reach but not exceed a certain value.

—CK

On Feb 27, 2016, at 3:27 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Following up to myself. Thoughts and feedback are welcome. -- Erica

Changing the Behavior of StrideThroughGenerator

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to change the way the through variation works.

Current Art

A Strideable to sequence returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in
the progression that is less than end.

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + tride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”
Proposed Modifications

I recommend the following changes:

Change the documentation text from

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

to

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression greater than or equal to end. There is no guarantee that end is an element of the sequence.

Modify the implementation

Current:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            if current == end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
Proposed:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            // NOTE: `current >= end` and not `current == end`
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
}
Introduced Changes

Under these changes, the following progression ends at 2.0 not 1.9:

print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
Integer progressions are unchanged:

print(Array(1.stride(through2: 10, by: 1)))
/// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Floating point strides will extend up-to or past the through value:

// Old
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75]

// New
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75, 2.0]
Alternates Considered

Other changes could include:

Introducing a digitalStride function with a set precision that works in integer math, multiplying each value by 10n, converting to integers, and then working back to floating point after each change
Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.
Introducing a DecimalNumber type, with its own stride methods, e.g. DecimalNumber(1.0).stride(through:DecimalNumber(2.0), by: DecimalNumber(0.1)).

On Feb 26, 2016, at 5:12 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type? <http://article.gmane.org/gmane.comp.lang.swift.evolution/7130/match=decimal>) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica

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

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


(Erica Sadun) #15

The English definition of through is "expressing the position or location of something beyond or at the far end of (an opening or an obstacle)".

-- E

···

On Feb 27, 2016, at 6:41 PM, William Dillon <william@housedillon.com> wrote:

I hope I’m not missing something, but I think Erica’s point on #1 is really important. When I originally learned about stride I assumed that the meaning of though was entirely different than what it really was. Erica’s idea brings it inline with my expectation based on its name.


(Joe Groff) #16

Erica Sadun via swift-evolution

As implemented, `stride` is broken for floating-point numbers. Instead
of repeatedly adding the `by` interval, it should multiply the interval
by successive integral values and add that to the base to avoid accruing
error. Your proposal only papers over the problem.

-Joe

Agreed. This is "papering over the problem" of accumulated floating point
error. There are two issues being addressed:

1. Semantics of `through` do not match their promise of going through the
end point rather than stopping at it or before.
2. Floating point strides accumulate errors by repeatedly adding the `by` interval.

I mention issue 2 in the alternative implementations:
https://gist.github.com/erica/03c398c06f6c47824429

Counting expected iterations by forming (max - min) / by, e.g. (2.0 -
1.0) / 0.1, which is 10, and performing each step as a pro-rated
progression along those steps, which would remove most of the accumulated
floating point errors along the way.

If you were addressing issue 2, what approach would you suggest:

* Differentiating integer strides from floating point, and minimizing
floating point errors?
* Leaving the tech as-is with minimal code
change with a relatively high benefit?

Arguably, floating point types shouldn't conform to Strideable at all, on
the general principle that genericizing arithmetic over ints and floats is
a trap. That would free floating point types to provide their own
specialized implementation of the stride methods.

In both cases, I'd still prefer the semantics to *go through* the end
point, not just stop at it, which is issue 1.

I'll have to defer to domain experts on this one. It seems superficially
appealing at least. If your only motivation is to get 1.0 through 2.0 by
0.1 to include 2.0, though, that feels like weak justification to me, since
that's a symptom of a different problem.

···

<swift-evolution@swift.org> wrote:

-- E


(Howard Lovatt) #17

I think you have raised a valid concern. But would suggest a simpler
solution, remove stride for floating point. You can always write:

100.stride(through: 200, by 25).map { $0 / 100.0 }

···

On Sunday, 28 February 2016, Erica Sadun via swift-evolution < swift-evolution@swift.org> wrote:

As implemented, `stride` is broken for floating-point numbers. Instead of
repeatedly adding the `by` interval, it should multiply the interval by
successive integral values and add that to the base to avoid accruing
error. Your proposal only papers over the problem.

-Joe

Agreed. This is "papering over the problem" of accumulated floating point
error. There are two issues being addressed:

1. Semantics of `through` do not match their promise of going through the
end point rather than stopping at it or before.
2. Floating point strides accumulate errors by repeatedly adding the `by`
interval.

I mention issue 2 in the alternative implementations:
https://gist.github.com/erica/03c398c06f6c47824429

   - Counting expected iterations by forming (max - min) / by, e.g. (2.0
   - 1.0) / 0.1, which is 10, and performing each step as a pro-rated
   progression along those steps, which would remove most of the accumulated
   floating point errors along the way.

If you were addressing issue 2, what approach would you suggest:

* Differentiating integer strides from floating point, and minimizing
floating point errors?
* Leaving the tech as-is with minimal code change with a relatively high
benefit?

In both cases, I'd still prefer the semantics to *go through* the end
point, not just stop at it, which is issue 1.

-- E

--
-- Howard.


(Erica Sadun) #18

I'd really dislike any solution that makes Swift programming worse than where it currently is.

-- E

···

On Feb 27, 2016, at 6:28 PM, Howard Lovatt <howard.lovatt@gmail.com> wrote:

I think you have raised a valid concern. But would suggest a simpler solution, remove stride for floating point. You can always write:

100.stride(through: 200, by 25).map { $0 / 100.0 }

On Sunday, 28 February 2016, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

As implemented, `stride` is broken for floating-point numbers. Instead of repeatedly adding the `by` interval, it should multiply the interval by successive integral values and add that to the base to avoid accruing error. Your proposal only papers over the problem.

-Joe

Agreed. This is "papering over the problem" of accumulated floating point error. There are two issues being addressed:

1. Semantics of `through` do not match their promise of going through the end point rather than stopping at it or before.
2. Floating point strides accumulate errors by repeatedly adding the `by` interval.

I mention issue 2 in the alternative implementations: https://gist.github.com/erica/03c398c06f6c47824429

Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.

If you were addressing issue 2, what approach would you suggest:

* Differentiating integer strides from floating point, and minimizing floating point errors?
* Leaving the tech as-is with minimal code change with a relatively high benefit?

In both cases, I'd still prefer the semantics to *go through* the end point, not just stop at it, which is issue 1.

-- E

--
-- Howard.


(Erica Sadun) #19

Erica Sadun via swift-evolution

If you were addressing issue 2, what approach would you suggest:

* Differentiating integer strides from floating point, and minimizing
floating point errors?
* Leaving the tech as-is with minimal code
change with a relatively high benefit?

Arguably, floating point types shouldn't conform to Strideable at all, on
the general principle that genericizing arithmetic over ints and floats is
a trap. That would free floating point types to provide their own
specialized implementation of the stride methods.

As if I don't already get enough grief from the C-for-loop people, now this? They'll be
burning semicolons on my front lawn at this rate. (And let me mention again that this
problem affects C-for-loop just as much as it does strides.)

In both cases, I'd still prefer the semantics to *go through* the end
point, not just stop at it, which is issue 1.

I'll have to defer to domain experts on this one. It seems superficially
appealing at least. If your only motivation is to get 1.0 through 2.0 by
0.1 to include 2.0, though, that feels like weak justification to me, since
that's a symptom of a different problem.

This sounds like it reduces to the following:

1. Leave as is, broken, requiring workarounds for nearly all floating point cases

2. Leave as is but remove floating point stride support, tick off forloopians. Introduce floating point stride-alike,
which isn't terribly difficult but will need a different something since `Stride` is built on `SignedNumberType`.

3. (This) Introduce a fix to make floating point less sucky and integers more semantically fitting, with
minimal code change. Issue FIXME warnings during migration to warn against changed semantics.

4. Do something else. Magic happens. Profit.

-- E

···

On Feb 27, 2016, at 6:28 PM, Joe Groff via swift-evolution <swift-evolution@swift.org> wrote:
<swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


(Erica Sadun) #20

I've updated the proposal to take this into account: https://gist.github.com/erica/03c398c06f6c47824429

It makes two core recommendations:

1. Adjust stride function semantics to expand from two to three functions, renaming them appropriately.
2. Break floating point strides away from Strideable to provide their own stride method implementations.

-- E

···

On Feb 27, 2016, at 8:07 PM, Charles Kissinger <crk@akkyra.com> wrote:

On Feb 27, 2016, at 5:38 PM, Erica Sadun <erica@ericasadun.com <mailto:erica@ericasadun.com>> wrote:

Would you accept a third version then? towards (to, `[a, b)`), to (through, `[a, b]`), and through (new, `[a, >=b]` <-- not sure that even has a representation)?

No objection here. It’s a really interesting problem you’ve pointed out. I’m not sure yet the best way to minimize it.

—CK

-- E

On Feb 27, 2016, at 6:25 PM, Charles Kissinger <crk@akkyra.com <mailto:crk@akkyra.com>> wrote:

Hi Erica,

With your suggested change, there would be no way to specify a precise upper bound for a sequence (except for integers in specific cases). The current pair of functions provide numbers in the intervals [a, b) and [a,b], which is what is needed to cover all use cases. With your change, the two functions would produce sequences that potentially lie either in the interval [a, b) for "stride to” or [a, infinity] for "stride through” since the size of the stride isn’t necessarily known at compile time or predictable.

In addition to breaking existing code, it would not cover every use case. Sometimes you won’t know the stride until runtime, but you know it has to be able to reach but not exceed a certain value.

—CK

On Feb 27, 2016, at 3:27 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Following up to myself. Thoughts and feedback are welcome. -- Erica

Changing the Behavior of StrideThroughGenerator

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to change the way the through variation works.

Current Art

A Strideable to sequence returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in
the progression that is less than end.

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + tride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

Under the current implementation, each floating point addition accrues errors. The progression never reaches 2.0.

print(Array(1.0.stride(through: 2.0, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
To force the progression to include 2.0, you must add an (ugly) epsilon, as in the following example:

print(Array(1.0.stride(through: 2.01, by: 0.1)))
/// Prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
This is problematic for the following reasons:

The name of the calling function “through” suggests the progression will pass through the end point before stopping
Floating point calls present an extremely common use-case
It’s unreasonable to expect developers to consider every case of “will floating point math prevent my progression from actually reaching the end point, which has already been differentiated by using through rather than to”
Proposed Modifications

I recommend the following changes:

Change the documentation text from

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression less than or equal to end. There is no guarantee that end is an element of the sequence.

to

A Strideable through sequence currently returns the sequence of values (self, self + stride, self + stride + stride, … last) where last is the last value in the progression greater than or equal to end. There is no guarantee that end is an element of the sequence.

Modify the implementation

Current:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            if current == end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
Proposed:

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Element? {
        if done {
            return nil
        }
        if stride > 0 ? current >= end : current <= end {
            // NOTE: `current >= end` and not `current == end`
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        let result = current
        current += stride
        return result
    }
}
Introduced Changes

Under these changes, the following progression ends at 2.0 not 1.9:

print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
Integer progressions are unchanged:

print(Array(1.stride(through2: 10, by: 1)))
/// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Floating point strides will extend up-to or past the through value:

// Old
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75]

// New
print(Array(1.0.stride(through: 1.9, by: 0.25)))
// prints [1.0, 1.25, 1.5, 1.75, 2.0]
Alternates Considered

Other changes could include:

Introducing a digitalStride function with a set precision that works in integer math, multiplying each value by 10n, converting to integers, and then working back to floating point after each change
Counting expected iterations by forming (max - min) / by, e.g. (2.0 - 1.0) / 0.1, which is 10, and performing each step as a pro-rated progression along those steps, which would remove most of the accumulated floating point errors along the way.
Introducing a DecimalNumber type, with its own stride methods, e.g. DecimalNumber(1.0).stride(through:DecimalNumber(2.0), by: DecimalNumber(0.1)).

On Feb 26, 2016, at 5:12 PM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I have a problem with the way floating point ranges work with striding:
1.0.stride(through: 2.0, by: 0.1) returns the sequence [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9].
Documentation: "It returns the sequence where last is less than or equal to `end`."
(And yes, the same issue exists with tradition C-style for loops).

Would it be really horrible if the implementation and definition was changed to:
"It returns the sequence where last is greater than or equal to `end`?"
This would offer no change for integers, and include 2.0 for floating point sequences.

Alternatively, could there be decimalStride? Using Double but a rounding system with a fixed number of decimal places (e.g. 1, 2, 3), to ensure at least the end point is hit? It might look like:
1.0.stride(through: 2.0, by: 0.1, places: 1)

I know there have been several discussions on-list about decimal number systems (Re: Is there a need for a Decimal type? <http://article.gmane.org/gmane.comp.lang.swift.evolution/7130/match=decimal>) as well, but this could fix an ongoing annoyance without a major change.

Thanks for your thoughts,

-- Erica

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

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