stridethrough.md

Changing the Behavior of StrideThroughGenerator

• Proposal: TBD
• Author(s): Erica Sadun
• Status: TBD
• Review manager: TBD

Swift offers two stride functions, stride(to:, by:) and stride(through:, by:). I propose to introduce a third style that changes the way the through variation works and address inherent issues with floating point strides.

This proposal was discussed on-list in the "[Discussion] stride behavior and a little bit of a call-back to digital numbers" thread.

Motivation

This proposal is motivated by two issues with the current implementation of stride:

1. Strideable's existing through semantics do not pass through the end point. They stop at or before that fence. For example, 1.stride(through: 10, by: 8) returns the progress (1, 9), not (1, 9, 17).
   • The current Swift definition of to returns values in [start, end) and will never reach end. In other words, you will never get to end.
   • The current Swift definition of through returns values in [start, end]. It may never reach end and certainly never goes through that value.
   • To pass through a value, you should move beyond "the position or location of something beyond or at the far end of (an opening or an obstacle)". (New Oxford American Dictionary)
2. Strideable is genericized across both integer and floating point types. Genericizing arithmetic across integer types and floating types is inherently problematic. Floating point strides accumulate errors by repeatedly adding by intervals. Floating point types shouldn't conform to Strideable and deserve their own floating point-aware implementation, or at least one that minimizes errors.

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.

Strideable presents the following issues:

• The name of the calling function through suggests the progression will pass through the end point before stopping. It does not. The name to suggests a progression will attempt to arrive at an end point. It does not.
• While floating point calls present an extremely common use-case, they use integer-style math that accumulates errors during execution. 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" and have to use workarounds, such as adding some epsilon to the end of progressions to ensure, for example, that a final point is included in the progression.

Detail Design Part 1: Progressions

When striding to or through a number, the behavior does not match the meaning of the word. Swift should provide three stride styles not two.

• Style 1: [start, end) by interval
  This style is currently called to. I propose to rename it towards as each value works towards end. The final value in the progression is less than end

• Style 2: [start, end] by interval
  This style is currently called through. I propose to rename it to. The progression concludes with a value that is less than or equal to end. Swift provides no guarantee that end is an element of the sequence.

• Style 3: [start, >=end] by interval
  I propose to introduce a new style called through. The final value is guaranteed to pass through end, either by finishing on end or past end.

A Style 3 implementation works as follows:

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

    /// 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 {
            done = true
            return current
        }
        let result = current
        current = current.advancedBy(stride)
        return result
    }
}

This solution is minimally disruptive to developers, respectful to existing code bases, and introduces a more complete semantic set of progressions that better matches progression names to developer expectations. (For example, "this argument says it goes through a value but it never even reaches that value".)

Upon adopting this change, out-of-sync strides now pass through end values:

// Unit stride
print(Array(1.stride(through: 10, by: 1))) 
// prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], no change

// Old out-of-sync stride
print(Array(1.stride(through: 10, by: 8)))
// prints [1, 9]

// New out-of-sync stride
print(Array(1.stride(through: 10, by: 8)))
// prints[1, 9, 17]

There is no functional changes to a towards (formerly to) or to (formerly through) stride, which cuts off as expected:

print(Array(1.stride(towards: 10, by: 8)))
// prints [1, 9]

print(Array(1.stride(to: 10, by: 8)))
// prints [1, 9]

Although floating point arithmetic presents a separate and orthogonal challenge, its behavior changes under this proposal if implemented in the current generic system. For example, through now includes a value at (or at least close to) 2.0 instead of stopping at 1.9 due to accumulated floating point errors.

// Old
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]

// New
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]

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

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

Impact on Existing Code

Renaming two stride functions and adding a third does not change or break existing code. The Swift 3 migrator can easily update the names for the two existing styles. That said, the migrator could not easily find already in-place workarounds like a through: 2.01 epsilon adjustment. By adding FIXME: notes wherever through: is found and renamed to to:, the migrator could warn against continued use without a full inspection and could offer links to information about the semantic changes.

Detail Design Part 2: Floating Point Strides

Under the current implementation, each floating point addition in a generic stride accrues errors. The following 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]

This same issue occurs with traditional C-style for loops. This is an artifact of floating point math, and not the specific Swift statements:

var array: [Double] = []
for var i = 1.0; i <= 2.0; i += 0.1 {
    array.append(i)
}
print("Array", array) 
// Prints Array [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]

To force the floating point progression to include 2.0, you might add some 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]

Even if the epsilon trick "works", intermediate values reflect accumulated errors.

// Print the difference 
let ideal = [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
print(zip(Array(1.0.stride(through: 2.01, by: 0.1)), ideal).map(-))
// Prints [0.0, 0.0, 2.22044604925031e-16, 2.22044604925031e-16, 
   4.44089209850063e-16, 4.44089209850063e-16, 4.44089209850063e-16, 
   6.66133814775094e-16, 6.66133814775094e-16, 8.88178419700125e-16, 
   8.88178419700125e-16]

Floating point strides are inherently dissimilar to and should not be genericized with integer strides. I propose separate their implementation, freeing them to provide their own specialized progressions, using better numeric methods. In doing so, floating point values are no longer tied to implementations that unnecessarily accrue errors or otherwise provide less-than-ideal solutions.

The following example provides a rough pass at what this might look like for floating point math. I leave specific algorithm details to experts. A decimal number solution would be more appropriate. See: RandomAscii's write-ups on all things floating point.

/// A `GeneratorType` for `DoubleStrideThrough`.
public struct DoubleStrideThroughGenerator : GeneratorType {
    let start: Double
    let end: Double
    let stride: Double
    var iteration: Int = 0
    var done: Bool = false
    
    public init(start: Double, end: Double, stride: Double) {
        (self.start, self.end, self.stride) = (start, end, stride)
    }

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    public mutating func next() -> Double? {
        if done {
            return nil
        }
        let current = start + Double(iteration) * stride; iteration += 1
        if signbit(current - end) == signbit(stride) { // thanks Joe Groff
            if current >= end {
                done = true
                return current
            }
            return nil
        }
        return current
    }
}

public struct DoubleStrideThrough : SequenceType {
    let start: Double
    let end: Double
    let stride: Double

    /// Return a *generator* over the elements of this *sequence*.
    ///
    /// - Complexity: O(1).
    public func generate() -> DoubleStrideThroughGenerator {
        return DoubleStrideThroughGenerator(
            start: start, end: end, stride: stride)
    }
    
    init(start: Double, end: Double, stride: Double) {
        _precondition(stride != 0, "stride size must not be zero")
        (self.start, self.end, self.stride) = (start, end, stride)
    }
    
}

public extension Double {
    public func fstride(
        through end: Double, by stride: Double
        ) -> DoubleStrideThrough {
            return DoubleStrideThrough(
                start: self, end: end, stride: stride)
    }
}

This implementation reduces floating point error by limiting accumulated additions.

print(Array(1.0.fstride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1000000000000001, 1.2, 1.3, 1.3999999999999999,
//         1.5, 1.6000000000000001, 1.7000000000000002, 1.8, 
//         1.8999999999999999, 2.0]

// versus the old style
print(Array(1.0.stride(through: 2.0, by: 0.1)))
// prints [1.0, 1.1000000000000001, 1.2000000000000002, 1.3000000000000003, 
//         1.4000000000000004, 1.5000000000000004, 1.6000000000000005, 
//         1.7000000000000006, 1.8000000000000007, 1.9000000000000008]

print(zip(Array(1.0.stride(through: 2.0, by: 0.1)), 
          Array(1.0.fstride(through: 2.0, by: 0.1))).map(-))
// prints [0.0, 0.0, 2.2204460492503131e-16, 2.2204460492503131e-16, 
//         4.4408920985006262e-16, 4.4408920985006262e-16, 4.4408920985006262e-16, 
//         4.4408920985006262e-16, 6.6613381477509392e-16, 8.8817841970012523e-16]

let ideal = [1.0, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0]
print(zip(Array(1.0.fstride(through: 2.0, by: 0.1)), ideal).map(-))
print(zip(Array(1.0.stride(through: 2.0, by: 0.1)), ideal).map(-))

// prints
// [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 2.2204460492503131e-16, 0.0, 0.0, 0.0]
// [0.0, 0.0, 2.2204460492503131e-16, 2.2204460492503131e-16, 
//  4.4408920985006262e-16, 4.4408920985006262e-16, 4.4408920985006262e-16, 
//  6.6613381477509392e-16, 6.6613381477509392e-16, 8.8817841970012523e-16]

Alternatives Considered

While precision math for decimal numbers would be better addressed by introducing a decimal type and/or warnings for at-risk floating point numbers, those features lie outside the scope of this proposal.