# Make `Numeric` Refine a new `AdditiveArithmetic` Protocol

## Introduction

This proposal introduces a weakening of the existing `Numeric` protocol named `AdditiveArithmetic` , which defines additive arithmetic operators and a zero, making conforming types roughly correspond to the mathematic notion of an additive group. This makes it possible for vector types to share additive arithmetic operators with scalar types, which enables generic algorithms over `AdditiveArithmetic` to apply to both scalars and vectors.

Discussion thread: Should Numeric not refine ExpressibleByIntegerLiteral

## Motivation

The `Numeric` protocol today refines `ExpressibleByIntegerLiteral` and defines all arithmetic operators. The design makes it easy for scalar types to adopt arithmetic operators, but makes it hard for vector types to adopt arithmetic operators by conforming to this protocol.

What's wrong with `Numeric`? Assuming that we need to conform to `Numeric` to get basic arithmetic operators and generic algorithms, we have three problems.

### 1. Vectors conforming to `Numeric` would be mathematically incorrect.

`Numeric` roughly corresponds to a ring. Vector spaces are not rings. Multiplication is not defined between vectors. Requirements `*` and `*=` below would make vector types inconsistent with the mathematical definition.

``````static func * (lhs: Self, rhs: Self) -> Self
static func *= (lhs: inout Self, rhs: Self)
``````

### 2. Literal conversion is undefined for dynamically shaped vectors.

Vectors can be dynamically shaped, in which case the the shape needs to be provided when we initialize a vector from a scalar. Dynamically shaped vector types often have an initializer `init(repeating:shape:)`.

Conforming to `Numeric` requires a conformance to `ExpressibleByIntegerLiteral`, which requires `init(integerLiteral:)`. However, the conversion from a scalar to a dynamically shaped vector is not defined when there is no given shape.

``````struct Vector<Scalar: Numeric>: Numeric {
// Okay!
init(repeating: Scalar, shape: [Int]) { ... }

// What's the shape?
init(integerLiteral: Int)
}
``````

Vector types mathematically represent vector spaces. Vectors by definition do not have multiplication between each other, but they come with scalar multiplication.

``````static func * (lhs: Vector, rhs: Scalar) -> Vector { ... }
``````

By established convention in numerical computing communities such as machine learning, many libraries define a multiplication operator `*` between vectors as element-wise multiplication. Given that scalar multiplication has to exist by definition, element-wise multiplication and scalar multiplication would overload the `*` operator.

``````static func * (lhs: Vector, rhs: Vector) -> Vector { ... }
static func * (lhs: Vector, rhs: Scalar) -> Vector { ... }
``````

This compiles, but does not work in practice. The following trivial use case would fail to compile, because literal `1` can be implicitly converted to both a `Scalar` and a `Vector` , and `*` is overloaded for both `Vector` and `Scalar` .

``````let x = Vector<Int>(...)
x * 1 // Ambiguous! Can be both `x * Vector(integerLiteral: 1)` and `x * (1 as Int)`.
``````

## Proposed solution

We keep `Numeric` 's behavior and requirements intact, and introduce a new protocol that

• does not require `ExpressibleByIntegerLiteral` conformance, and
• shares common properties and operators between vectors and scalars.

To achieve these, we can try to find a mathematical concept that is close enough to makes practical sense without depending on unnecessary algebraic abstractions. This concept is additive group, containing a zero and all additive operators that are defined on `Numeric` today. `Numeric` will refine this new protocol, and vector types/protocols will conform to/refine the new protocol as well.

## Detailed design

We define a new protocol called `AdditiveArithmetic` . This protocol requires all additive arithmetic operators that today's `Numeric` requires, and a zero. Zero is a fundamental property of an additive group.

``````public protocol AdditiveArithmetic: Equatable {
/// A zero value.
static var zero: Self { get }

/// Adds two values and produces their sum.
///
/// The addition operator (`+`) calculates the sum of its two arguments. For
/// example:
///
///     1 + 2                   // 3
///     -10 + 15                // 5
///     -15 + -5                // -20
///     21.5 + 3.25             // 24.75
///
/// You cannot use `+` with arguments of different types. To add values of
/// different types, convert one of the values to the other value's type.
///
///     let x: Int8 = 21
///     let y: Int = 1000000
///     Int(x) + y              // 1000021
///
/// - Parameters:
///   - lhs: The first value to add.
///   - rhs: The second value to add.
static func + (lhs: Self, rhs: Self) -> Self

/// Adds two values and stores the result in the left-hand-side variable.
///
/// - Parameters:
///   - lhs: The first value to add.
///   - rhs: The second value to add.
static func += (lhs: inout Self, rhs: Self) -> Self

/// Subtracts one value from another and produces their difference.
///
/// The subtraction operator (`-`) calculates the difference of its two
/// arguments. For example:
///
///     8 - 3                   // 5
///     -10 - 5                 // -15
///     100 - -5                // 105
///     10.5 - 100.0            // -89.5
///
/// You cannot use `-` with arguments of different types. To subtract values
/// of different types, convert one of the values to the other value's type.
///
///     let x: UInt8 = 21
///     let y: UInt = 1000000
///     y - UInt(x)             // 999979
///
/// - Parameters:
///   - lhs: A numeric value.
///   - rhs: The value to subtract from `lhs`.
static func - (lhs: Self, rhs: Self) -> Self

/// Subtracts the second value from the first and stores the difference in the
/// left-hand-side variable.
///
/// - Parameters:
///   - lhs: A numeric value.
///   - rhs: The value to subtract from `lhs`.
static func -= (lhs: inout Self, rhs: Self) -> Self
}
``````

Remove arithmetic operator requirements from `Numeric` , and make `Numeric` refine `AdditiveArithmetic` .

``````public protocol Numeric: AdditiveArithmetic, ExpressibleByIntegerLiteral  {
associatedtype Magnitude: Comparable, Numeric
init?<T>(exactly source: T) where T : BinaryInteger
var magnitude: Self.Magnitude { get }
static func * (lhs: Self, rhs: Self) -> Self
static func *= (lhs: inout Self, rhs: Self) -> Self
}
``````

To make sure today's `Numeric` -conforming types do not have to define a `zero` , we provide an extension to `AdditiveArithmetic` constrained on `Self: ExpressibleByIntegerLiteral` .

``````extension AdditiveArithmetic where Self: ExpressibleByIntegerLiteral {
public static var zero: Self {
return 0
}
}
``````

In the existing standard library, prefix `+` is provided by an extension to
`Numeric`. Since additive arithmetics are now defined on `AdditiveArithmetic`,
we change this extension to apply to `AdditiveArithmetic`.

``````extension AdditiveArithmetic {
/// Returns the given number unchanged.
///
/// You can use the unary plus operator (`+`) to provide symmetry in your
/// code for positive numbers when also using the unary minus operator.
///
///     let x = -21
///     let y = +21
///     // x == -21
///     // y == 21
///
/// - Returns: The given argument without any changes.
public static prefix func + (x: Self) -> Self {
return x
}
}
``````

## Source compatibility

The proposed change is fully source-compatible.

## Effect on ABI stability

The proposed change will affect the existing ABI of the standard library, because it changes the protocol hierarchy and protocol requirements. As such, this protocol must be considered before the Swift 5 branching date.

## Effect on API resilience

The proposed change will affect the existing ABI, and there is no way to make it not affect the ABI because it changes the protocol hierarchy and protocol requirements.

## Alternatives considered

1. Make `Numeric` no longer refine `ExpressibleByIntegerLiteral` and not introduce any new protocol. This can solve the type checking ambiguity problem in vector protocols, but will break existing code: Functions generic over `Numeric` may use integer literals for initialization. Plus, Steve Canon also pointed out that it is not mathematically accurate -- there's a canonical homomorphism from the integers to every ring with unity. Moreover, it makes sense for vector types to conform to `Numeric` to get arithmetic operators, but it is uncommon to make vectors, esp. fixed-rank vectors, be expressible by integer literal.

2. On top of `AdditiveArithmetic`, add a `MultiplicativeArithmetic` protocol that refines `AdditiveArithmetic`, and make `Numeric` refine `MultiplicativeArithmetic`. This would be a natural extension to `AdditiveArithmetic`, but the practical benefit of this is unclear.

3. Instead of a `zero` static computed property requirement, an `init()` could be used instead, and this would align well with Swift's preference for initializers. However, this would force conforming types to have an `init()`, which in some cases could be confusing or misleading. For example, it would be unclear whether `Matrix()` is creating a zero matrix or an identity matrix. Spelling it as `zero` eliminates that ambiguity.

13 Likes

@scanon Do you think `Arithmetic` should refine `Equatable`?

Yes.

1 Like

Maybe I don't understand the exact requirements well enough, but this seems mathematically weird to me. Vector spaces are not rings in any natural sort of way, and in general, no multiplication is defined on them (we could define component-wise multiplication for coordinate vectors, but there's lots of other vector spaces too). Also, why use the (somewhat obscure) ring without unity instead of a proper ring which is a very ubiquitous structure? If we're going to add proper algebraic structures to Swift (which I'm not sure we need to), I would start with Group and Ring first, then maybe Monoid.

Personally, I think that if component-wise multiplication is defined on a coordinate vector, it should use a different operator anyway, instead of overloading the `*` sign. But maybe that's standard practice in the ML community.

5 Likes

Looks like a nice proposal to have for more than just vectors. Iâ€™d love Swift to get more mathematical (e.g., via external math libraries) and a good stdlib protocol hierarchy is key here.

A small note about source compatibility. Since `Numeric` gets a new (defaulted) requirement `static var zero: Self`, there might be source breakage in conforming types of protocols where thereâ€™s a non-`Self` `zero`. Iâ€™m not aware of any implementations but it might be something to keep an eye on.

I'm with Fryie on this. If you're going to introduce a new protocol, it's not at all obvious to me that `*` should be in it.

2 Likes

Agreed.

<insert long rant about how we're all stuck in the 1980s WRT character sets because between the USB HID committee and the computer keyboard industry, nobody is trying to advance things>

1 Like

I totally get that, and agree it is weird! An assumption was made about `*` as being the element-wise multiplication operator so that it is consistent with the SIMD proposal and machine learning libraries. Ideally, we should not include `*` in such a protocol for mathematical correctness, but then the name `Arithmetic` would no longer fit. I'm interested in removing `*` from the protocol but I'll welcome ideas on what the protocol should be called.

I do not think names like "Group", "Ring" or "Monoid" are a good fit for the standard library. Also, it is important to recognize that this proposal needs to be refined and reviewed ASAP because it's breaking the ABI and is the only way to unblock vector libraries in the future.

Don't you think this is a tad dramatic? Surely, any kind of proposal should be carefully reviewed and discussed before it enters the language? Not everyone is working with ML or vector operations.

What exactly precludes powerful vector libraries from being added to Swift at this point in time? Maybe I'm missing something, but I'm not seeing exactly why there is such an urgent need (I do understand that the current situation is mathematically unsatisfying, but I haven't seen a language with a mathematically sound number hierarchy yet, and that includes Haskell).

If we remove the multiplication from your proposed `Arithmetic`, we're essentially left with a group, which I think is a very general structure and therefore good to have (vector spaces are naturally groups). Whether the name `Group` is picked, or some sort of name that is more instantly recognisable, can of course be debated (Swift has `SetAlgebra` and one thread over is considering `CountableSetAlgebra` or `ExtensionalSetAlgebra`, I'm not sure that's much better in terms of approachability than `Group`). Something like `Additive` might also work.*

*in theory, groups can be additive or multiplicative, which is just a notational issue and changes nothing about the mathematics, but I think it's probably useful to restrict groups in a programming language to always be additive.

5 Likes

IIRC groups can be â€śany* binary operationâ€ť-tive. Swift only allows conforming to a protocol once, though. Maybe if we had generic protocols, we could do something like `struct Double : Group<Additive>, Group<Multiplicative> {...}`, but Iâ€™m not sure thatâ€™s the best idea.

Going back to whether `*` should be in the protocol, I wonder if we need to get something like namespaces in before ABI stability lands? Itâ€™d let the ML camp and the math camp each define their operators without worrying so much about how the other group uses an operator.

* Not actually any, I think, but I donâ€™t recall the details off the top of my head.

Even if we needed to, itâ€™s pretty much impossible now unless we delay Swift 5.

IIRC, itâ€™s not that mathematical vector types canâ€™t be implemented now, they just canâ€™t be implemented generically. You either need to preface every `(Vector, Vector) -> Whatever` operation with a check to ensure that the two operands are dimensionally compatible, or create a separate type for every length of vector you want to work with (which is especially annoying when you change your mind about what lengths you want and have to go create yet another mostly copied/pasted type).

2 Likes

tbf thereâ€™s only 3 of them,,, once you get past N = 4 youâ€™re really in simd land, not vector math land

Sorry if I was pushing too hard. Such changes surely need to be carefully reviewed and considered. I just want to say it's an important issue to consider and, if it misses the ABI deadline, future vector space protocols will have to duplicate arithmetic operators, and generic algorithms won't be able to apply to both scalars and vectors.

@scanon also talked about proposing to remove `magnitude`, but I wonder if that's still possible after ABI is locked down.

I recently not too long ago sent a PR (under review) to an open source library to add matrix and vector support. What I did was also create a protocol called 'Arithmetic'

``````public protocol Arithmetic : SignedNumeric {
static var zero : Self { get }
static func /(lhs: Self, rhs: Self) -> Double
static func /(lhs: Self, scalar: Double) -> Double
static func /(lhs: Self, scalar: Float) -> Float
static func /(lhs: Self, rhs: Self) -> Float
static func /=(lhs: inout Self, rhs: Self)
func asDouble() -> Double
func asFloat() -> Float
func asInt() -> Int
``````

}

Curious to know what are your thoughts on this implementation. Mainly towards whether its smart to conform to SignedNumeric. Also your thoughts on the division operators since I hear its pretty taboo. The `as` such functions are there to do matrix math using just the methods defined with auto casting.

To see full PR. See https://github.com/CosmicMind/Algorithm/pull/13

Methods that conduct floating point operations return either Double or Float and its up to you to explicitly type which one you want.

This is a really key point to make. I would refer everyone to some of my favorite sequences: the number of semigroups that can be defined on a set of order n and the number of groups. Note that for any non-trivial set, the number of such structures is staggeringly huge. It doesn't suffice to have just "additive" and "multiplicative" groups; it doesn't suffice to have any finite named set of group operations. Even if we restrict ourselves to familiar operations, the integers are also a semigroup under `|`, `^`, `&`, `min`, `max`, ...

This is a big part of the reason why I personally haven't pursued adding protocols like `Semigroup`, `Group`, or `Ring` to the standard library. You really want to be able to say that a type together with operations conforms to these mathematical structures, rather than saying that the type does with a fixed operation. You should be able to say that `(Int, +, 0)` is a semi-group, but also that `(Int,`*`, 1)` is and `(Int, |, 0)` is. In order for these "protocols" to be useful for generic programming, you really need to be able to have a set conform repeatedly with distinct operations. We don't really have the machinery for that in Swift today, and I don't think we should try to add these structures to the standard library without it.

`Numeric` is a special case that made sense to add, in that "a ring with unity with the usual operators" is a common enough thing that it's useful to have on its own, rather than as a more abstract `Ring` structure, and it's deliberately not named `Ring` for the reasons sketched above.

`Arithmetic` or something like it, may or may not make sense to add, but the criteria according to which it should be considered are similar--is it a set of operations that is semantically useful separate from its meaning as an abstract mathematical structure.

All that said, I agree broadly with @Fryie: if you want to conform `VectorFoo` protocols to this protocol, then having multiplication is at least controversial, and probably doesn't belong. Every vector space can be endowed with a product that makes it into an algebra (the elementwise product works anytime you have "elements", and even in the most abstract settings you can always add the zero product that just maps `a*b` to zero for every `a`, `b`), but that is not a useful or meaningful operation in every setting that is a vector space, and which we would want to conform to such a protocol.

So, I think the API surface of this protocol, if it's going to be added, is:

``````public protocol Arithmetic : Equatable {
static var zero: Self { get }
prefix static func + (x: Self) -> Self
prefix static func - (x: Self) -> Self
static func + (lhs: Self, rhs: Self) -> Self
static func - (lhs: Self, rhs: Self) -> Self
static func += (lhs: inout Self, rhs: Self) -> Self
static func -= (lhs: inout Self, rhs: Self) -> Self
}
``````

I left the `Arithmetic` name here for clarity, but given the absence of `*`, another name will probably be a better fit. This is, mathematically, an additive group, but I think that we should avoid that name if we can, for reasons sketched above.

11 Likes

You're making very valid, and technically correct points. Sets (and therefore types) themselves are never algebraic structures, but only in conjunction with particular operations.

But there are also lots of cases where mathematicians commonly identify sets with their corresponding "natural" groups, e.g. Z is obviously a group w.r.t. `+`, not to `*`, R is a group with respect to `+`, whereas R\{0} is one with respect to `*`. I think there's lots of cases where there is such a "default" operation.

And in the worst case (where there's no good "default" operation, or you just need a different one), it's always possible to use wrapper types, even if that makes the code slightly more awkward to write (Haskell does it like that in a number of cases).

That said, I agree with your modified `Arithmetic` proposal, which I think would be a good fit; the question is only what it should be called.

Yes, but that's nothing that this proposal would be able to fix, is it? To be able to fix this properly, I think you'd need dependent types or something.

3 Likes

Weâ€™d need to be able to be able to write, say, `Vector<6, _>` to define them generically, and `Vector<A+B, _>` to concatenate them generically. Or something semantically equivalent, anyway.

Thanks for the feedback and ideas. I've updated the proposal to introduce an `AdditiveArithmetic` protocol! The name is completely up for bikeshedding, though.

I'm not sure about this one. This is defined on `SignedNumeric`, not `Numeric`.