[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