Thoughts on expanding AdditiveArithmetic

numerics

(Daryle Walker) #1

Gee, accidentally take a couple-month hiatus, and new versions of Xcode, macOS, and iOS show up. Plus 15 mostly-approved proposals.

The current one I'm catching up on is SE-0233: "Make Numeric Refine a new AdditiveArithmetic Protocol."

Looking at Wikipedia pages connected from the proposal, should we add repeated addition via multiplication with a natural number:

public protocol AdditiveArithmetic: Equatable {
    //...

    static func * <T: BinaryInteger>(lhs: T, rhs: Self) -> Self
}

extension AdditiveArithmetic {

    public static func * <T: BinaryInteger>(lhs: Self, rhs: T) -> Self {
        return rhs * lhs
    }

}

// Should a default implementation be added that preconditions on
// lhs == zero || rhs >= 0 and then has a for-loop brute-force implementation?

If the conforming type doesn't support "negative" values, then using a negative value for the integer scalar is a precondition error.

Then we can add a mostly marker protocol:

public protocol NegatableAdditiveArithmetic: AdditiveArithmetic { }

extension NegatableAdditiveArithmetic {

    public static func -(x: Self) -> Self {
        return 0 - x
    }

}

Where this new protocol indicates that "negative" values are supported, lifting the precondition I mentioned earlier. (This is like RandomAccessCollection is a quasi-marker refinement of BidirectionalCollection, and allows count to always be O(1).)

Maybe "SignedAdditiveArithmetic" could be a better name. I suppose SignedNumeric would refine this protocol.


(Xiaodi Wu) #2

What is your use case for such a design?


(Steve Canon) #3

This starts to go down the path of building up the full tower of algebraic abstractions. That's an interesting (and likely valuable) project, but the Swift language probably hasn't reached the point of maturity for such a project to live in the stdlib. As the language-level tools of abstraction are fleshed out, the "best" design of such a system will change, so we probably don't want to lock ourselves into choices today that close off better options down the road.

Peter Gottschling's "Fundamental Algebraic Concepts in Concept-Enabled C++"(pdf) gives some idea of what a fully-abstracted-out algebraic system might look like, and it's worth noting that more than a decade later, you still can't build it with the C++ language that we actually have (I think? @Douglas_Gregor would know).

We have [Signed]Numeric and AdditiveArithmetic because they are probably the two most useful abstractions both for writing generic code and for capturing the most-used operators in one place, but the bar for building a more refined algebraic system into the stdlib before the language matures further is pretty high.

With the language and compiler that we have today, you start to run into issues with introducing more ambiguity with changes like these; is 2 * 4 an integer (ring) product, or repeated addition on the additive group structure? If the latter, is it 2 + 2 + 2 + 2 or 4 + 4? These are all semantically equivalent, but correspond to different overloads of the * operator and different protocol witnesses.

A change like this would also allow heterogeneous integer arithmetic that isn't currently allowed by the stdlib, but only for *, which would be pretty confusing for a lot of people.

let x: Int8 = 3
let y: Int = 2
let z = x * y // ok, interpreted as 2 + 2 + 2
let w = x + y // error, mixed-type arithmetic

TL;DR: absolutely people should build these sorts of abstractions. They are useful, and are a wonderful way to explore ways in which the language and tools could be improved in the long-run. Until the language matures further, they probably shouldn't go into the stdlib; the existing AdditiveArithmetic and Numeric are about as far down that road as we want to go, unless a very compelling use case comes forward.


(Daryle Walker) #4

I saw unary + move to this new protocol, and wondered if unary - should move to a similar protocol, like we have with Numeric and SignedNumeric.

The other part of SignedAdditiveArithmetic is a marker protocol that lets the user know that s/he can subtract arbitrary values without checking if the first operand is not "smaller" than the second in advance. I'm not sure if that's really needed, but it wouldn't be safe to put unary - into AdditiveArithmetic (as an alternative) without mandating arbitrary subtraction support.