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 <br...@architechies.com>
> wrote:
>
>> On Jan 30, 2017, at 11:31 AM, Max Moiseev <mois...@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
