[Returned for revision] SE-0050: Decoupling Floating Point Strides from Generic Implementations

Chris_Lattner · May 29, 2016, 8:04pm

Proposal link: swift-evolution/0050-floating-point-stride.md at master · apple/swift-evolution · GitHub

Hello Swift Community,

The review of SE-0050: "Decoupling Floating Point Strides from Generic Implementations" ran from May 17...23, 2016. The proposal is returned for revision:

There was very little feedback from the community - the feedback was positive about solving the floating point error accumulation problem indicated by the proposal, but wasn’t strongly positive about the solution. The core team also agrees that the problem needs to be solved, however they don't think this API change is the right approach.

The core team believes that the existing strideable API cannot efficiently and correctly handle all the real-world use cases one would want. However, a multiplication-based implementation similar to the one proposed in SE-0050 (but potentially extended) seems sufficiently general to solve the existing use cases as well as solve the floating point error accumulation issue. Once the design of this iterates on swift-evolution, it would be great to see a revised version of this proposal.

Many thanks to Erica Sadun and Xiaodi Wu for driving this discussion and writing a great proposal!

-Chris Lattner
Review Manager

Brent_Royal-Gordon · May 30, 2016, 10:10am

The core team believes that the existing strideable API cannot efficiently and correctly handle all the real-world use cases one would want. However, a multiplication-based implementation similar to the one proposed in SE-0050 (but potentially extended) seems sufficiently general to solve the existing use cases as well as solve the floating point error accumulation issue. Once the design of this iterates on swift-evolution, it would be great to see a revised version of this proposal.

Can you give any indication of what's wrong with the proposed API?

Personally, what bothered me about it is that it seems too float-specific. The way I would design it is to add multiplication to Strideable:

  public protocol Strideable: Comparable {
    typealias Stride: SignedNumber

    func distance(to other: Self) -> Stride
    func advanced(by stride: Stride) -> Self

    static func scale(_ stride: Stride, by multiplier: Stride) -> Stride
  }

And then have a refined protocol for types like Int which are safe to repeatedly advance:

  /// An AccumulatingStrideable is a Strideable which guarantees that:
  ///
  /// (0..<10).reduce(value) { val, _ in val.advanced(by: stride) } == value.advanced(by: T.scale(stride, by: 10))
  ///
  /// In other words, the result of repeatedly advancing any value by any stride *n* times is exactly equal to the
  /// result of advancing it once by that stride scaled up *n* times.
  public protocol AccumulatingStrideable: Strideable {}

Then you have two forms of `stride(from:to:by:)`:

public func stride<T: Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T>
public func stride<T: AccumulatingStrideable>(from start: T, to end: T, by stride: T.Stride) -> AccumulatingStrideTo<T>

Obviously there are many designs we could consider along these lines, and I don't want to get bogged down in the details of choosing one at this point. What I'm asking is, is this the general *kind* of design you're looking for compared to SE-0050, one which is not specific to FloatingPoint types? Or are you looking for a redesign which addresses different issues from these?

···

--
Brent Royal-Gordon
Architechies

Erica_Sadun · May 30, 2016, 3:55pm

Piling on because it would really help to get a sense of what direction the core team is looking for. Unless we can figure out in advance what the core team is actually looking for, it's hard to respond with the request for revision. The feedback says: "they don't think this API change is the right approach" and "The core team believes that the existing strideable API cannot efficiently and correctly handle all the real-world use cases one would want."

I'd like to iterate the design as requested, but it's hard to know where to start. So let me discuss things that can be strode along:

There are four types of bounded intervals (open and closed on each end) that can be traversed in either direction, four types of unbounded interval (open and closed starting points, heading positively and negatively), and both integer and floating point applications of strides along these:

Bounded Intervals: [A, B), (A, B], (A, B), [A, B]
Unbounded Intervals: (A, ∞), [A, ∞), ( -∞, A), (-∞, A]

(Technically, there's also the empty interval (), and the full number line (-∞, ∞), which really don't come into play for sequences but might play a role in pattern matching.)

The simplest API to handle all these cases would be:

`stride(from/off:, by:, towards/to/through:)` for sequences along bounded intervals and
`stride(from/off:, by:)` for sequences along unbounded intervals.

In these calls, `from` is inclusive and `off` is exclusive of the first value.

SE-0051 <https://github.com/apple/swift-evolution/blob/master/proposals/0051-stride-semantics.md> covers the details of what the semantics of `towards`/`to`/`through` mean:

towards meaning a..<b, a<..b, for example: 1 towards 5 by 1 is [1, 2, 3, 4]
to a...b, for example: 1 to 5 by 1 is [1, 2, 3, 4, 5], and 1 to 10 by 8 is [1, 9]
through a..>=b, a>=..b, for example: 1 through 5 by 1 is [1, 2, 3, 4, 5] and 1 through 10 by 8 is [1, 9, 17]

The acceptance of SE-0045 and SE-0099 and makes implementing each of these sequence types much easier. The state version can use the error-reducing iteration multiplier. The non-state version is perfect for integer math.

-- E

···

On May 30, 2016, at 4:10 AM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

The core team believes that the existing strideable API cannot efficiently and correctly handle all the real-world use cases one would want. However, a multiplication-based implementation similar to the one proposed in SE-0050 (but potentially extended) seems sufficiently general to solve the existing use cases as well as solve the floating point error accumulation issue. Once the design of this iterates on swift-evolution, it would be great to see a revised version of this proposal.

Can you give any indication of what's wrong with the proposed API?

dabrahams · May 31, 2016, 5:16pm

The core team believes that the existing strideable API cannot efficiently and correctly handle all the real-world use cases one would want. However, a multiplication-based implementation similar to the one proposed in SE-0050 (but potentially extended) seems sufficiently general to solve the existing use cases as well as solve the floating point error accumulation issue. Once the design of this iterates on swift-evolution, it would be great to see a revised version of this proposal.

Can you give any indication of what's wrong with the proposed API?

For example, a multiplication-based implementation like the one proposed
for floating point could be made to work for all the current models of
Strideable in the standard library, but it would not generalize
efficiently to handling arbitrary-precision integers or complex numbers
or even to efficiently striding over Float. We believe such a protocol
should be designed, and we fundamentally disagree with the proposal's
claim that abstracting over integers and floating point is wrong.

Until we have the right API design for Strideable, we believe the
accumulating problem can be fixed without changing Strideable's public
API, e.g. by adding underscored protocol requirements for which we can
provide specialized implementations using protocol extensions
constrained to Stride : FloatingPointType. We look forward to accepting
a pull request to make this change, which doesn't require an evolution
proposal, and we expect that change to usefully inform the question of
how to change Strideable.

···

on Mon May 30 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

Personally, what bothered me about it is that it seems too float-specific. The way I would design it is to add multiplication to Strideable:

  public protocol Strideable: Comparable {
    typealias Stride: SignedNumber

    func distance(to other: Self) -> Stride
    func advanced(by stride: Stride) -> Self

    static func scale(_ stride: Stride, by multiplier: Stride) -> Stride
  }

And then have a refined protocol for types like Int which are safe to repeatedly advance:

  /// An AccumulatingStrideable is a Strideable which guarantees that:
  ///
  /// (0..<10).reduce(value) { val, _ in val.advanced(by: stride) } == value.advanced(by: T.scale(stride, by: 10))
  ///
  /// In other words, the result of repeatedly advancing any value by any stride *n* times is exactly equal to the
  /// result of advancing it once by that stride scaled up *n* times.
  public protocol AccumulatingStrideable: Strideable {}

Then you have two forms of `stride(from:to:by:)`:

  public func stride<T: Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T>
  public func stride<T: AccumulatingStrideable>(from start: T, to end: T, by stride: T.Stride) -> AccumulatingStrideTo<T>

Obviously there are many designs we could consider along these lines, and I don't want to get bogged down in the details of choosing one at this point. What I'm asking is, is this the general *kind* of design you're looking for compared to SE-0050, one which is not specific to FloatingPoint types? Or are you looking for a redesign which addresses different issues from these?

--
Dave

trs · May 31, 2016, 3:15pm

Like it!

-Thorsten

···

Am 30.05.2016 um 12:10 schrieb Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org>:

The core team believes that the existing strideable API cannot efficiently and correctly handle all the real-world use cases one would want. However, a multiplication-based implementation similar to the one proposed in SE-0050 (but potentially extended) seems sufficiently general to solve the existing use cases as well as solve the floating point error accumulation issue. Once the design of this iterates on swift-evolution, it would be great to see a revised version of this proposal.

Can you give any indication of what's wrong with the proposed API?

Personally, what bothered me about it is that it seems too float-specific. The way I would design it is to add multiplication to Strideable:

   public protocol Strideable: Comparable {
       typealias Stride: SignedNumber

       func distance(to other: Self) -> Stride
       func advanced(by stride: Stride) -> Self

       static func scale(_ stride: Stride, by multiplier: Stride) -> Stride
   }

And then have a refined protocol for types like Int which are safe to repeatedly advance:

   /// An AccumulatingStrideable is a Strideable which guarantees that:
   ///
   /// (0..<10).reduce(value) { val, _ in val.advanced(by: stride) } == value.advanced(by: T.scale(stride, by: 10))
   ///
   /// In other words, the result of repeatedly advancing any value by any stride *n* times is exactly equal to the
   /// result of advancing it once by that stride scaled up *n* times.
   public protocol AccumulatingStrideable: Strideable {}

Then you have two forms of `stride(from:to:by:)`:

   public func stride<T: Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T>
   public func stride<T: AccumulatingStrideable>(from start: T, to end: T, by stride: T.Stride) -> AccumulatingStrideTo<T>

Obviously there are many designs we could consider along these lines, and I don't want to get bogged down in the details of choosing one at this point. What I'm asking is, is this the general *kind* of design you're looking for compared to SE-0050, one which is not specific to FloatingPoint types? Or are you looking for a redesign which addresses different issues from these?

--
Brent Royal-Gordon
Architechies

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