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

[Max Moiseev]

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
>