[swift-evolution] protocol-oriented integers (take 2)

Tue Jan 31 16:26:02 CST 2017

On Tue, Jan 31, 2017 at 2:53 PM, Max Moiseev <moiseev at apple.com> wrote:

> Hi Brent,
>
> Thanks a lot for your suggestions! After having discussed them with Dave,
> we came up with the following design that I personally like a lot.
>
> enum Overflowing { case .withOverflow }
> enum FullWidth { case .fullWidth }
>
> protocol FixedWidthInteger {
>   func adding(_ other: Self, _: Overflowing) -> (partialValue: Self,
> overflow: ArithmeticOverflow)
>   func subtracting(_ other: Self, _: Overflowing) -> (partialValue: Self,
> overflow: ArithmeticOverflow)
>   func multiplied(by other: Self, _: Overflowing) -> (partialValue: Self,
> overflow: ArithmeticOverflow)
>   func divided(by other: Self, _: Overflowing) -> (partialValue: Self,
> overflow: ArithmeticOverflow)
>
>   func multiplied(by other: Self, _: FullWidth) -> DoubleWidth<Self>
>   func dividing(_ other: DoubleWidth<Self>, _: FullWidth) -> (quotient:
> Self, remainder: Self)
> }
>
>
> Call sites would look like:
>
> x.multiplied(by: y, .withOverflow) and x.multiplied(by: y, .fullWidth)
>
> a little different for the division:
>
> x.divided(by: y, .withOverflow) and y.dividing(x, .fullWidth)
>
> Note the inverse-ness of `dividing`, but the lack of the argument label
> makes it quite natural.
>

This is an improvement in many ways, I think. However `.fullWidth` vs.
`DoubleWidth` seems less than ideal. I get that you can't reuse
`DoubleWidth` for the single-case enum, but still.

Now that * and &* no longer used the `multiplied(by:)` spelling, is there a
reason not to take advantage of overloading on the return value for these
very specialized methods?

```
protocol FixedWidthInteger {
  typealias OverflowFlagging = (partialValue: Self, overflow:
ArithmeticOverflow)
  func multiplied(by other: Self) -> OverflowFlagging
  func multiplied(by other: Self) -> DoubleWidth<Self>
}
```

You'd then write `x.multiplied(by: y) as OverflowFlagging` and
`x.multiplied(by: y) as DoubleWidth`

With respect to `dividing` vs `divided`, IMO it'd be a tricky name,
especially for non-English speakers. The "ed/ing" rule has these suffixes
used pretty interchangeably to indicate a non-mutating operation, depending
on the vagaries of the English language, but we've never had an "ed" and an
"ing" used for completely different things on the same type, as far as I'm
aware. Why not move the `dividing` version to DoubleWidth, where it can be
a proper `divided(by:)`?

> 2. There is no quotient-and-remainder-with-overflow, either regular or
> double-width. Can we do that?
> What will the partialValue equivalent be in case of overflow in
> overflowing quotient+remainder division?
> >
> > 3. "Overflow" is not really a good description of what's happening in
> division; the value is undefined, not overflowing. Is there a better way to
> express this?
> Division by 0 is not overflowing, true, but Int.min / (-1) is.
> >
> > 4. For that matter, even non-fixed-width division can "overflow"; should
> that concept be hoisted higher up the protocol hierarchy?
> In my head, overflow is a notion related to fixed sized types. You simply
> don’t have enough room to represent certain values. Following this line of
> thought, binary integer is not bounded, and can grow at will. So
> FixedWidthInteger looks like the right place for overflowing operations.
> And if we decide to not consider division by 0 an overflow, the model seems
> quite consistent.
>
>
> > On Jan 30, 2017, at 7:55 PM, Brent Royal-Gordon <brent at architechies.com>
> wrote:
> >
> >> On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev at apple.com> wrote:
> >>
> >> doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
> >> 1. The components of it’s return type are not high and low, but are
> quotient and remainder instead.
> >> 2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the
> case for quotient and remainder.
> >
> > You're right about the return value; for `doubleWidthDivide(_:_:)`, I
> was thinking about changing the dividend. Specifically, I'm thinking we
> should change these to:
> >
> >       static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) ->
> DoubleWidth<Self>
> >       static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs:
> Self) -> (quotient: Self, remainder: Self)
> >
> > I'm also thinking a little bit about spelling of these operations. I'd
> *love* to be able to call them `*` and `/` and let the type system sort
> things out, but that would cause problems, especially for multiply (since
> the return value is the only thing different from a normal `*`). We could
> invent a new operator, but that would be a bit much. Could these be simply
> `multiply` and `divide`, and we'll permit the `DoubleWidth`
> parameter/return type to explain itself?
> >
> > I'm also thinking the second parameter should be labeled `by`, since
> that's the way people talk about these operations. Applying both of these
> suggestions, we'd get:
> >
> >       static func multiply(_ lhs: Self, by rhs: Self) ->
> DoubleWidth<Self>
> >       static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) ->
> (quotient: Self, remainder: Self)
> >
> >       let x = Int.multiply(a, by: b)
> >       let (aʹ, r) = Int.divide(x, by: b)
> >       assert(a == aʹ)
> >       assert(r == 0)
> >
> > Should the standard library provide extensions automatic definitions of
> multiplication and division in terms of their double-width equivalents?
> >
> >       extension FixedWidthInteger {
> >               func multipliedWithOverflow(by other: Self) ->
> (partialValue: Self, overflow: ArithmeticOverflow) {
> >                       let doubledResult = Self.multiply(self, by: other)
> >                       let overflowed = doubledResult.high !=
> (doubledResult < 0 ? -1 : 0)
> >                       return (Self(bitPattern:
> doubledResult.lowerValue), overflowed ? .overflowed : .none)
> >               }
> >
> >               func quotientAndRemainder(dividingBy other: Self) ->
> (quotient: Self, remainder: Self) {
> >                       precondition(other != 0, "Divide by zero")
> >                       return Self.divide(DoubleWidth(self), by: other)
> >               }
> >
> >               func dividedWithOverflow(by other: Self) -> (partialValue:
> Self, overflow: ArithmeticOverflow) {
> >                       guard other != 0 else { return (self, .overflowed)
> }
> >
> >                       let result = Self.divide(self, by: other)
> >                       return (result.quotient, .none)
> >               }
> >
> >               static func * (lhs: Self, rhs: Self) -> Self {
> >                       let result = lhs.dividedWithOverflow(by: rhs)
> >                       precondition(result.overflow == .none,
> "Multiplication overflowed")
> >                       return result.partialValue
> >               }
> >
> >               static func / (lhs: Self, rhs: Self) -> Self {
> >                       let result = lhs.quotientAndRemainder(dividingBy:
> rhs)
> >                       return result.quotient
> >               }
> >
> >               static func % (lhs: Self, rhs: Self) -> Self {
> >                       let result = lhs.quotientAndRemainder(dividingBy:
> rhs)
> >                       return result.remainder
> >               }
> > }
> >
> > Hmm...having actually written this out, I now have a couple of concerns:
> >
> > 1. There's a lot of jumping back and forth between instance methods and
> static methods. Can we standardize on just static methods? Or make sure
> that the user-facing interfaces are all either operators or instance
> methods?
> >
> > 2. There is no quotient-and-remainder-with-overflow, either regular or
> double-width. Can we do that?
> >
> > 3. "Overflow" is not really a good description of what's happening in
> division; the value is undefined, not overflowing. Is there a better way to
> express this?
> >
> > 4. For that matter, even non-fixed-width division can "overflow"; should
> that concept be hoisted higher up the protocol hierarchy?
> >
> > 5. For *that* matter, should we simply make these operations throw
> instead of returning a flag?
> >
> >       enum ArithmeticError<NumberType: Arithmetic>: Error {
> >               // Are generic errors permitted?
> >               case overflow(partialValue: NumberType)
> >               case undefined
> >       }
> >
> >       // Should these throwing definitions be higher up so that, when
> working with `Arithmetic`
> >       // or similar types, you have an opportunity to handle errors
> instead of always trapping?
> >       protocol FixedWidthInteger: BinaryInteger {
> >               ...
> >               func adding(_ other: Self) throws -> Self
> >               func subtracting(_ other: Self) throws -> Self
> >               func multiplied(by other: Self) throws -> Self
> >               func divided(by other: Self) throws -> Self
> >               ...
> >       }
> >
> > I'm *really* tempted to suggest adding throwing variants of the actual
> operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be
> too specialized to really justify that.
> >
> >> Having said that, there is a solution for doubleWidthMultiply, that I
> think is worth trying:
> >>
> >> enum DoubleWidth<T> {
> >>  case .parts(high: T, low: T.Magnitude)
> >>
> >>  var high: T { switch self { case .parts(let high, _): return high } }
> >>  var low: T.Magnitude { switch self { case .parts(_, let low): return
> low } }
> >> }
> >>
> >> This way it will be possible to both do pattern-matching on the result
> of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low
> when needed.
> >
> > This sounds like a good idea to me. (Unless we want to create a protocol
> for destructuring, but I assume that's out of scope.)
> >
> > --
> > Brent Royal-Gordon
> > Architechies
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170131/42b77df8/attachment.html>