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

[Dave Abrahams]

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?

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.  

That said, the ability to interpret integer literals as an arbitrary
Arithmetic isn't used anywhere in the standard library, so I'd like to
consider undoing
https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15d5709eb2be069286c1
and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
BinaryInteger.

>> *## BinaryInteger*
>>
>> I'm a little confused by the presence of init(extendingOrTruncating:) for
>> *all* binary integers. Why does it make sense to be able to write
>> UInt16(extendingOrTruncating: (-21 as Int8)) ? In my mind, sign-extension
>> only has meaning when the source and destination types are both signed.
>>
>
> Here (just IMHO), I disagree. Since any binary integer can be truncated and
> any can be right-shifted, it makes sense for `init(extendingOrTruncating:)`
> to be available for all of them. If I understand the proposal correctly,
> `Int(extendingOrTruncating: (-1 as Int8))` would give you a different
> result than `Int(extendingOrTruncating: (255 as UInt8)`.

Yes it would.  But the real justification for this operation is generic
programming with integers.  It isn't possible, today, to define:

  init<T:BinaryInteger>(extending:T) where T.isNarrowerThan(Self)
  init<T:BinaryInteger>(truncating:T) where T.isWiderThan(Self)

>> Although I would not be against a clamp() function in the standard library,
>> "init(clamping:)" sounds strange to me. What about calling it
>> "init(nearestTo:)"?  One could also define a FloatingPoint version of
>> init(nearestTo:), i.e. lround(). For maximum annoyance and explicitness,
>> you could even rename the existing init(_:) to init(truncating:) to make it
>> clear that truncation, not regular rounding, occurs when converting from
>> floating-point.
>>
>
> I would disagree with that as well; the existing `init(_:)` truncates the
> fractional part but errors if that value is outside the representable
> range, while the word "truncating" makes it sound like something is done to
> make any possible source value give you a destination value (a la
> "extendingOrTruncating" for integers).
>
> Meanwhile, "nearest to" is problematic for me because either 127 and 129 is
> "nearest to" 128, and neither integer is "nearest to" 500, yet
> `Int8(clamping: 128)` and `Int8(clamping: 500)` both give you 127. This
> operation is very different from lround() for floating point, which in
> Swift is `rounded(.toNearestOrAwayFromZero)` (or just `rounded()`).
>
> In both these cases, I think it's important to use spellings that
> distinguish doing things to the fractional part of floating point values
> and doing things to the binary representation of integer values. I think
> there's great value in using the term "clamp", which is very different from
> "nearest"; and in using an unlabeled `init(_:)` for initializing from FP
> values, which is most similar to the unlabeled `init(_:)` for initializing
> from integer values, as opposed to your suggested `init(truncating:)` which
> connotes some similarity to `init(extendingOrTruncating:)` for integer
> values.

+1

> *... masking shifts*
>>
>> The example claims that "(30 as UInt8) &>> 11" produces 3, because it
>> right-shifts 30 by 3. But isn't the bitWidth of UInt8 always 8 since it's a
>> fixed-width type? 

Yes.

>> Why should 11 get masked to 3 before the shift?

Because those are the semantics of masking shift?

You can think of masking shift as an optimization akin to using &+ to
add signed numbers when you know it can't overflow.  It's an expert's
tool.  If you want semantics that always make sense, use regular shift.

>> (Also, it might be a good idea to choose examples with numbers whose
>> base-ten representations don't look like valid binary. 😉) 

Good point.

>> What use cases are there for masking shifts? I was under the
>> impression that "smart shifts" were pretty much how the usual shift
>> instructions already behaved.

No, sadly not!  The way the usual shift instructions behave is that if
you shift by a negative amount or you overshift, you get undefined
behavior, which gets expressed in various fun ways at runtime!

>> (Minor: were the smart shift operators supposed to be included as
>> BinaryInteger protocol requirements? I only see them in the "heterogeneous
>> shifts" extension.)

They don't need to be requirements, as they're defined entirely in terms
of other (required) operations.  I'd be interested in any arguments you
might have for making them requirements, though.

>> *... init<T: BinaryInteger>(_ source: T)*
>>
>> Now a thought experiment: suppose you wanted to write an
>> arbitrary-precision BigInt, or any binary integer such as Int256. The
>> BinaryInteger protocol requires you to provide init<T:BinaryInteger>(_
>> source: T). Given the source of type T, how do you access its bits? Is
>> repeated use of word(at:) the recommended way? 

Yes.

>> If so, it might be nice to include a "wordCount" returning the number
>> of available words; otherwise I suppose the user has to use something
>> like bitWidth/(8*MemoryLayout<Int>.size), which is pretty ugly.

good catch; countRepresentedWords is in the prototype
(https://github.com/apple/swift/blob/new-integer-protocols/stdlib/public/core/Integers.swift.gyb#L1521),
and it should be in the proposal.

>> *## 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.

> *## Heterogenous shifts, equality, and comparison*
>>
>> These look great. How will the default implementations be provided?

You can look at the prototype to see how it's done:
https://github.com/apple/swift/blob/new-integer-protocols/stdlib/public/core/Integers.swift.gyb

>> (Equivalent question: how would a user define their own heterogeneous
>> operators?) I suppose this works:
>>
>>     static func &>> <Other : BinaryInteger>(lhs: Self, rhs: Other) -> Self
>> {
>>         // delegate to the protocol requirement &>>(Self, Self)
>>         return self &>> Self(extendingOrTruncating: rhs)
>>     }
>>
>> But for operations you can't delegate so easily... I'm imagining trying to
>> implement heterogeneous comparison (i.e. < ) and the best I can come up
>> with uses signum() and word(at:)...

It's already implemented; you don't need to do anything.
https://github.com/apple/swift/blob/new-integer-protocols/stdlib/public/core/Integers.swift.gyb#L1687

>> Also, should these be protocol requirements so user-defined types can
>> specialize them?

That's a good question; I don't have an opinion yet.  Anyone else?

>> *## Masking arithmetic*
>>
>> Do &* and &+ and &- need their operands to have the same type, or could
>> these be heterogeneous too (at least &+ and &-)?

I don't know what semantics you're imagining for heterogeneous &+.  What
type would it return?  What mask would it use?

Note that the language doesn't let us express a generic heterogeneous
operation where the result type is the wider of the two argument types.

>> 
>>
>>
>> Jacob
>>
>> On Fri, Jan 13, 2017 at 12:47 PM, Max Moiseev via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>>> Hi everyone,
>>>
>>> Back in June 2016 we discussed the new design of the integer types for
>>> the standard library. It even resulted in acceptance of SE-0104
>>> <https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md> for
>>> Swift 3. Unfortunately we were not able to implement it in time for the
>>> release.
>>>
>>> But it was not forgotten, although, as time went by, a few changes needed
>>> to be made in order to reflect the current state of the language.
>>> Without further introduction, please welcome the refined proposal to make
>>> integers in Swift more suitable for generic programming.
>>>
>>> Available in this gist https://gist.github.com/m
>>> oiseev/62ffe3c91b66866fdebf6f3fcc7cad8c and also inlined below.
>>>
>>> Max
>>>
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave