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

Jacob Bandes-Storch jtbandes at gmail.com
Tue Jan 31 15:32:04 CST 2017


Cute. Reminds me of C++ STL's struct tags: http://en.cppreference.
com/w/cpp/utility/piecewise_construct_t
http://en.cppreference.com/w/cpp/iterator/iterator_tags

On Tue, Jan 31, 2017 at 12:53 PM, Max Moiseev via swift-evolution <
swift-evolution at swift.org> 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.
>
>
> > 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
> >
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170131/b4584470/attachment.html>


More information about the swift-evolution mailing list