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

Sun Feb 28 01:17:02 CST 2016

I’d like to add a couple of thoughts to the discussion.

I agree that the current Strideable naming is surprising, and toward/to instead of to/through would have been more appropriate.

I’m not so sure that having a proper ‘through’ method that would pass through the endpoint would be useful, and that it would do anything to solve the floating point issues.

The specific example that started the discussion was 1.0 through 2.0 by 0.1. The expected result was to end exactly at 2.0, instead it ended at 1.9 because `by`+epsilon was added at every step. Changing the behavior of `through`to end past the endpoint would have solved this case.

However, I suspect that changing the stride values you could end in the opposite condition, where `by`-epsilon is added at every step, and so with a changed `through` behavior you would end at the equivalent of 2.1; which is equally wrong.

The root of the problem is that Strideable is clearly designed with exact (not necessarily integer, but exact) math in mind. Floating point values shouldn’t conform to it, as they need different semantics.

In my experience, when dealing with floating point values in loops it has always been one of two cases:

1) (most common) iterate from A to *exactly* B, doing steps *as close as possible* to S
2) (less common) iterate from A to *as close as possible* to B, doing steps of *exactly* S

1) would be implemented with integer math, computing the number of steps needed and then interpolating between A and B. This guarantees that the final iteration is exactly on B, however the difference between two steps would not be exactly S.

2) would be implemented by tweaking the end condition so that the final iteration can be either before or after B—whichever is closest.

—
Nicola

> 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 at akkyra.com(mailto:crk at akkyra.com)>wrote:
> > 
> > > On Feb 27, 2016, at 5:38 PM, Erica Sadun<erica at ericasadun.com(mailto:erica at 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 at akkyra.com(mailto:crk at 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 at swift.org(mailto:swift-evolution at 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:)andstride(through:, by:). I propose to change the way thethroughvariation works.
> > > > > 
> > > > > Current Art
> > > > > 
> > > > > AStrideable tosequence returns the sequence of values (self,self + stride,self + stride + stride, …last) wherelastis the last value in
> > > > > the progression that is less thanend.
> > > > > 
> > > > > 
> > > > > AStrideable throughsequence currently returns the sequence of values (self,self + stride,self + tride + stride, …last) wherelastis the last value in the progression less than or equal toend. There is no guarantee thatendis 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 passthroughthe 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 usingthroughrather thanto”
> > > > > 
> > > > > Proposed Modifications
> > > > > 
> > > > > I recommend the following changes:
> > > > > 
> > > > > Change the documentation text from
> > > > > > 
> > > > > > AStrideable throughsequence currently returns the sequence of values (self,self + stride,self + stride + stride, …last) wherelastis the last value in the progressionless than or equal toend. There is no guarantee thatendis an element of the sequence.
> > > > > > 
> > > > > 
> > > > > 
> > > > > to
> > > > > 
> > > > > > 
> > > > > > AStrideable throughsequence currently returns the sequence of values (self,self + stride,self + stride + stride, …last) wherelastis the last value in the progressiongreater than or equal toend. There is no guarantee thatendis an element of the sequence.
> > > > > > 
> > > > > 
> > > > > Modify the implementation
> > > > > 
> > > > > Current:
> > > > > 
> > > > > ///Advanceto thenextelementandreturnit,or`nil`ifnonext///element exists.   public mutating funcnext() ->Element? {ifdone {returnnil}ifstride>0? current>=end:current<=end{ifcurrent ==end{         done =truereturncurrent       }returnnil}     let result = current     current += stridereturnresult   }
> > > > > 
> > > > > Proposed:
> > > > > 
> > > > > ///Advanceto thenextelementandreturnit,or`nil`ifnonext///element exists.   public mutating funcnext() ->Element? {ifdone {returnnil}ifstride>0? current>=end:current<=end{//NOTE:`current>=end`andnot`current ==end`ifcurrent>=end{         done =truereturncurrent       }returnnil}     let result = current     current += stridereturnresult   } }
> > > > > 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 thethroughvalue:
> > > > > 
> > > > > // Oldprint(Array(1.0.stride(through:1.9,by:0.25)))// prints [1.0, 1.25, 1.5, 1.75]// Newprint(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 adigitalStridefunction 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 aDecimalNumbertype, with its ownstridemethods, 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 at swift.org(mailto:swift-evolution at 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 bedecimalStride? 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 at swift.org(mailto:swift-evolution at swift.org)
> > > > > > https://lists.swift.org/mailman/listinfo/swift-evolution
> > > > > 
> > > > > _______________________________________________
> > > > > swift-evolution mailing list
> > > > > swift-evolution at swift.org(mailto:swift-evolution at swift.org)
> > > > > https://lists.swift.org/mailman/listinfo/swift-evolution
> > > > 
> > > 
> > 
> 
> 
> 