[swift-evolution] [Review] SE-0104: Protocol-oriented integers

[Nicola Salmoria]

> * What is your evaluation of the proposal?

This is a great proposal which was sorely needed, so I strongly support it
in general. I have a few comments and suggestions to make.


First of all, a bit of background to explain where I'm coming from: in the
past weeks I have been working for educational purposes on a Rational<T:
SignedInteger> type. This is one of those things that seem trivial at first
sight, but are surprisingly difficult to do right. Thoroughly testing and
avoiding traps or incorrect results in edge cases was a lot of work.
I have now updated my code to use the new interfaces described in the
proposal, and I was able to remove a lot of custom protocols and
boilerplate. So it was a net improvement.


The first comment I have to make is that, as has already been noted by plx,
the Arithmetic protocol looks like a "bag of syntax" with loose semantics
attached. It will be used by signed integers, unsigned integers (naturals),
floating point numbers; and is an obvious conformance for a Rational type as
well.
In the proposal, there is no indication of the expected semantics of the
four basic operations.
- Are addition and multiplication commutative?
- Is multiplication distributive over addition?
- Is 'rhs != 0' a precondition for division?
- Presumably associativity must match the associativity of the operators.
- What is (a / b) * b?
- Is T(exactly: n) * x guaranteed to be == (x + ... + x) n times?

While this protocol is useful to simplify the implementation of operators,
it might be largely superseded by other improvements related to SE-0091.
Taken alone, I'm not sure it pulls its own weight.

For example say I wanted to write some generic code using values that
represent probabilities. I would need arithmetic to work on such values, but
since probabilities are strictly in the interval [0.0, 1.0], integers would
be useless. I could make the code generic over FloatingPoint, but a Rational
type would fit the bill as well, and guarantee accuracy. So to write
meaningful generic code I'd need a different protocol, one that made more
promises about the semantics of division.


Now about the AbsoluteValue associatedtype, which several other people have
already shown doubts about.
I found it useful, precisely for the reason stated in the proposal
(generating the description of a Rational). However, it seems to be mostly
an implementation detail, used to:
1) work around the fact that -Int.min isn't representable in two's complement;
2) provide a way to get the unsigned version of an integer type, to be used
by the doubleWidthMultiply() return type.

These uses suggest that the Integer protocol might not be the best place for
this associatedtype: both of the use cases above would not apply to a
BigInt. It seems more appropriate for it to be part of FixedWidthInteger.
It might even make sense to rename it UnsignedSelf, to make it clear that
it's intended to be the unsigned equivalent of Self.


I also join Karoly's request for double-width division operations. In
particular I would suggest:

static func doubleWidthDivideWithOverflow(_ lhs: (high: Self, low:
AbsoluteValue), by rhs: Self) -> (partialValue: Self, overflow:
ArithmeticOverflow)

static func doubleWidthRemainder(_ lhs: (high: Self, low: AbsoluteValue), by
rhs: Self) -> Self

Note that I needed to use static members here, because the first argument of
the division is not Self. Alternatively, the result of doubleWidthMultiply()
could be a struct, so that double-width division operations could be members
of that struct.

These operations are difficult to implement, and are very useful.

In my specific use case of Rational, addition is the trickiest operation to
implement because it can have transient overflows, which get simplified in
the final result. To handle them, I need to do two double-width multiplies,
followed by a double-width addition (which is easily implemented without
explicit support from the standard library). Then I need a double-width
remainder to compute the GCD, and finally an overflowing double-width
division to attempt fitting the result in a single-width numerator.

Without support for double-width division, the proposal falls short of being
really useful for this kind of operations.


Finally, I don't understand this example, which is also repeated twice in
the proposal. Is it perhaps a copy&paste error?

public struct Int8 {
  public func addingWithOverflow(_ rhs: DoubleWidth<T>)
    -> (partialValue: DoubleWidth<T>, overflow: ArithmeticOverflow) {
    // efficient implementation
  }
}


> * Is the problem being addressed significant enough to warrant a change to
Swift?

Absolutely. Working with integer types in generic code is currently one of
the most frustrating experiences in Swift. The proposal should address most
of the common issues.

> * Does this proposal fit well with the feel and direction of Swift?

Very well. The new protocols are much more consistent and cohesive than the
status quo.

> * If you have used other languages or libraries with a similar feature,
how do you feel that this proposal compares to those?

I haven't.

> * How much effort did you put into your review? A glance, a quick reading,
or an in-depth study?

Many hours of experience with the current IntegerArithmetic hierarchy,
carefully read all the discussion, and used the new semantics in real code
obtaining significant improvements.

Thanks,
Nicola