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

[David Sweeris]

> On Jan 14, 2017, at 18:55, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> Responding to both Jacob and Xiaodi here; thanks very much for your
> feedback!
> 
>> on Sat Jan 14 2017, Xiaodi Wu <swift-evolution at swift.org> wrote:
>> 
>> On Sat, Jan 14, 2017 at 1:32 AM, Jacob Bandes-Storch via swift-evolution <
>> swift-evolution at swift.org> wrote:
>> 
>>> Great work, all. I'm not sure I ever commented on SE-0104, so I've read
>>> through this one more carefully. Here are some things that came to mind:
>>> 
>>> *## Arithmetic*
>>> 
>>> Why are ExpressibleByIntegerLiteral and init?<T:BinaryInteger>(exactly:)
>>> required? I could understand needing access to 0, but this could be
>>> provided by a static property or nullary initializer. It doesn't seem like
>>> all types supporting arithmetic operations would necessarily be convertible
>>> from an arbitrary binary integer.
>>> 
>>> 
>>> I tried to evaluate the Arithmetic protocol by considering what it means
>>> for higher-dimensional types such as CGPoint and CGVector. My use case was
>>> a linear interpolation function:
>>> 
>>>    func lerp<T: Arithmetic>(from a: T, to b: T, by ratio: T) -> T {
>>>        return a + (b - a) * ratio
>>>    }
>>> 
>>> If I've read the proposal correctly, this definition works for integer and
>>> floating-point values. But we can't make it work properly for CGVector (or,
>>> perhaps less mathematically correct but more familiar, CGPoint). It's okay
>>> to define +(CGVector, CGVector) and -(CGVector, CGVector), but *(CGVector,
>>> CGVector) and /(CGVector, CGVector) don't make much sense. What we really
>>> want is *(CGVector, *CGFloat*) and /(CGVector, *CGFloat*).
>>> 
>>> After consulting a mathematician, I believe what the lerp function really
>>> wants is for its generic param to be an affine space
>>> <https://en.wikipedia.org/wiki/Affine_space>. I explored this a bit here:
>>> https://gist.github.com/jtbandes/93eeb7d5eee8e1a7245387c660d53b
>>> 03#file-affine-swift-L16-L18
>>> 
>>> This approach is less restrictive and more composable than the proposed
>>> Arithmetic protocol, which can be viewed as a special case with the
>>> following definitions:
>>> 
>>>    extension Arithmetic: AffineSpace, VectorSpace {  // not actually
>>> allowed in Swift
>>>        typealias Displacement = Self
>>>        typealias Scalar = Self
>>>    }
>>> 
>>> It'd be great to be able to define a lerp() which works for all
>>> floating-point and integer numbers, as well as points and vectors (assuming
>>> a glorious future where CGPoint and CGVector have built-in arithmetic
>>> operations). But maybe the complexity of these extra protocols isn't worth
>>> it for the stdlib...
>>> 
>> 
>> I think, in the end, it's the _name_ that could use improvement here. As
>> the doc comments say, `Arithmetic` is supposed to provide a "suitable basis
>> for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
>> appropriate? It would make it clear that `CGVector` is not meant to be a
>> conforming type.
> 
> We want Arithmetic to be able to handle complex numbers.  Whether Scalar
> would be appropriate in that case sort of depends on what the implied
> field is, right?

I was under the impression that complex numbers are scalar numbers... although maybe not since once you get past, I think quaternions, you start losing division and eventually multiplication, IIRC. (I hate it when two of my recollections try to conflict with each other.)



> It's true that CGPoint and CGVector have no obvious sensible
> interpretation of "42", and that's unfortunate.  The problem with
> protocols for algebraic structures is that there's an incredibly
> complicated lattice (see figures 3.1, 3.2 in
> ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
> shove all of those protocols into the standard library (especially not
> prematurely) but each requirement you add to a more-coarsely aggregated
> protocol like Arithmetic will make it ineligible for representing some
> important type.

My only concern with this is that later on, if we do decide the stdlib should have them, does it then become a breaking change to start moving all that stuff around? Or would everything be fine as long as the net requirements for the "Arithmetic" protocol stay the same regardless of how things get redistributed under the hood?


>>> *## FixedWidthInteger*
>>> 
>>> Why is popcount restricted to FixedWidthInteger? It seems like it could
>>> theoretically apply to any UnsignedInteger.
>>> 
>> 
>> You can perfectly legitimately get a popcount for a signed integer. It's
>> just looking at the binary representation and counting the ones. But then
>> with two's complement, it'd have to be restricted to FixedWidthInteger and
>> not BinaryInteger, because the same negative value would have a different
>> popcount depending on the type's bitwidth. 
> 
> Right, or to put it differently, the popcount of a negative BigInt would
> always be inifinite.
> 
>> I'd disagree strongly with removing popcount from signed binary
>> integers. However, I suppose the same requirement could be applied to
>> both FixedWidthInteger and UnsignedInteger.
> 
> Given that there's little point in ever creating an unsigned BigInt
> type, I think that wouldn't make much sense.

Why is that? I'd think they'd be useful anywhere it'd be a logical error to have a negative value and UInt64 wasn't big enough. Is that situation simply that rare?

- Dave Sweeris