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

[David Sweeris]

> On Jan 16, 2017, at 13:40, Xiaodi Wu via swift-evolution <swift-evolution at swift.org> wrote:
> 
> On Mon, Jan 16, 2017 at 12:02 PM, Stephen Canon <scanon at apple.com> wrote:
>>> On Jan 16, 2017, at 3:25 AM, Xiaodi Wu via swift-evolution <swift-evolution at swift.org> wrote:
>>> 
>>> Unless I'm mistaken, after removing division, models of SignedArithmetic would have the mathematical properties of a ring. For every element a in ring R, there must exist an additive inverse -a in R such that a + (-a) = 0. Models of Arithmetic alone would not necessarily have that property.
>> 
>> Closure under the arithmetic operations is a sticky point for all the finite integer models vs. the actual ring axioms.  No finite [non-modulo] integer type is closed, because of overflow. Similarly, additive inverses don’t exist for the most negative value of a signed type,
> 
> I think this goes back to the distinct mentioned earlier: imperfection in how we model something, or a difference in what we're modeling? Finite memory will dictate that any model that attempts to represent integers will face constraints. Signed integer types represent a best-effort attempt at exactly representing the greatest possible number of integers within a given amount of memory such that the greatest proportion of those have an additive inverse that can be also be represented in the same amount of memory.
>  
>> or for any non-zero value of an unsigned type.
> 
> This is not fundamentally attributable to a limitation of how we model something. Non-zero values of unsigned type do not have additive inverses in the same way that non-one values of unsigned type do not have multiplicative inverses.
> 
>> The obvious way around this is to say that types conforming to Arithmetic model a subset of a ring that need not be closed under the operations.
> 
> If we don't remove division, type conforming to Arithmetic would also model a subset of a field that need not be closed under the operations. I'm not sure it'd be wise to put such a mathematical definition on it with a "need not" like that. Better, IMO, to give these protocols semantics based on a positive description of the axioms that do hold--with the caveat that the result of addition and multiplication will hold to these axioms only insofar as the result does not overflow.

What about writing the division part of the protocol so that the return type isn't necessarily `Self`?
protocol Arithmetic {
    associatedtype DivisionResult
    // use a function instead of an operator to avoid making this the mother of all breaking changes
    ...
    static func divide (_: Self, _: Self) -> Self.DivisionResult
    ...
}
extension FloatingPoint {
    typealias DivisionResult = Self
}
extension Integer {
    typealias DivisionResult = (quotient: Self, remainder: Self)
}
That way, Integer division returns the "correct" answer regardless of whether the numerator is a multiple of the denominator.
In generic algorithms, you could easily extract the "normal" value like this:
    let tValue = T.divide(x, y).0
because the `.0` of a non-tuple value is just the original value, right?

One thing I'm not sure about (and can't check because I'm not in front of a computer) is how this would affect multiplication... Would we want `Self` and `Self.DivisionResult` to be mutually multipliable?
protocol Arithmetic {
    associatedtype DivisionResult
    ...
    static func divide (_: Self, _: Self) -> Self.DivisionResult
    static func * (_: Self, _: Self) -> Self
    static func * (_: Self, _: Self.DivisionResult) -> Self
    static func * (_: Self.DivisionResult, _: Self) -> Self
}

Could the compiler figure out that, where Self.DivisionResult == Self, those three * functions are actually just one function, or, whenever you tried to actually multiply stuff, would it throw its hands in the air (like it just don't care) and complain about ambiguous references to "*"?

- Dave Sweeris
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170116/443613f7/attachment.html>