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

[Dave Abrahams]

on Sun Jan 29 2017, Brent Royal-Gordon <swift-evolution at swift.org> wrote:

>> On Jan 13, 2017, at 12:47 PM, Max Moiseev via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> Protocol-oriented integers (take 2)
>> 
>> 	• Proposal: SE-NNNN
>> 	• Authors: Dave Abrahams, Maxim Moiseev
>> 	• Review Manager: TBD
>> 	• Status: Awaiting review
>> 	• Bug: SR-3196
>> 	• Previous Proposal: SE-0104
>
> Definitely liking what I'm seeing here.
>
>> public protocol Arithmetic : Equatable, ExpressibleByIntegerLiteral 
>> {
>
> Is there a reason `Arithmetic` is not `Hashable`? 

Just that it's an orthogonal concern.  I think it would make a lot of
sense to make all BinaryIntegers hashable, since we can provide a
default implementation that simply hash-combines words.

> (I think `Comparable` isn't here because complex numbers can't be
> compared, but correct me if I'm wrong about that.)

That's right.

>> /// A type that can represent the absolute value of any possible value of the
>>   /// conforming type.
>>   associatedtype Magnitude : Equatable, ExpressibleByIntegerLiteral
>
> Is there a reason not to have this be `Arithmetic`? Maybe just the
> circularity problem?

Yes, that, at least.

>>   /// Returns the n-th word, counting from the least significant to most
>>   /// significant, of this value's binary representation.
>>   ///
>>   /// The `word(at:)` method returns negative values in two's complement
>>   /// representation, regardless of a type's underlying implementation. If `n`
>>   /// is greater than the number of words in this value's current
>>   /// representation, the result is `0` for positive numbers and `~0` for
>>   /// negative numbers.
>>   ///
>>   /// - Parameter n: The word to return, counting from the least significant to
>>   ///   most significant. `n` must be greater than or equal to zero.
>>   /// - Returns: An word-sized, unsigned integer with the bit pattern of the
>>   ///   n-th word of this value.
>>   func word(at n: Int) -> UInt
>
> How does the client know how many words there are? Are they supposed to calculate that from
> `bitWidth`?
>
> Oh, I see:
>
>> 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.
>
> That looks fine to me.
>
>> /// The number of bits in the current binary representation of this value.
>>   ///
>>   /// This property is a constant for instances of fixed-width integer
>>   /// types.
>>   var bitWidth : Int { get }
>
> So, um, I'm a little confused about this one. Is this the physical
> number of bits in the value, or is it the number of bits you need to
> get from `word(at:)` in order to get all bits representing the value?
>
> For instance, when you call `UInt32.bitWidth`, does it return `32`,
> the physical number of bits in the value, or `33`, the number of bits
> including the (always zero) sign bit?

I think we recently sorted this out with Nate Cook, who was going to
write some new text for it.  If that's not the case, Nate, please
correct me.

>
>
>>   static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -> (high: Self, low: Magnitude)
>>   static func doubleWidthDivide(_ lhs: (high: Self, low: Magnitude),
>> _ rhs: Self) -> (quotient: Self, remainder: Self)
>
> Could these take/return a single `DoubleWidth<Self>` value instead of
> two separate `Self` and `Magnitude` values? Or would that present
> circularity problems?

It might work; we should investigate.  When this was originally
designed, we weren't proposing to include DoubleWidth.

>>   /// The number of bits equal to 1 in this value's binary representation.
>>   ///
>>   /// For example, in a fixed-width integer type with a `bitWidth` value of 8,
>>   /// the number 31 has five bits equal to 1.
>>   ///
>>   ///     let x: Int8 = 0b0001_1111
>>   ///     // x == 31
>>   ///     // x.popcount == 5
>>   var popcount: Int { get }
>
> I'm not super-fond of this name; I assume it's a term of art, but it's
> a pretty obscure one. Maybe `numberOfOnes`? `onesWithin`?

Yes, the rationale is that it's a term of art.  I think if you were
going to call it something else, you'd need to mention "one _bits_" in
the name.  If we can come up with a name that's obviously better, that's
great, but lacking a clear winner we should go with the already-accepted
term.

>> DoubleWidth
>> 
>> The DoubleWidth<T> type allows to create wider fixed-width integer
>> types from the ones available in the standard library.
>
> I'm glad you're planning to include `DoubleWidth` this time.
>
>> 	• Deprecation of the BitwiseOperations protocol. We find it
>> hard to imagine a type that conforms to this protocol, but is not a
>> binary integer type.
>
> While I'm sure any such type *could* be a binary integer type, I'm not
> convinced they necessary *should* be. For instance, suppose I have a
> "bit vector"; I know I never want to perform arithmetic on it, but I
> *do* want to manipulate bits separately, so I make it look like a
> `RandomAccessCollection` of `Bool`s. 

OK, so that's a collection of Bools.  It doesn't matter that it's
*implemented* with one bit per Bool.

> It might make a great deal of sense to support bitwise operations on
> this type, 

I think that's a model of SetAlgebra, then, isn't it?

> even though I don't want to clutter it up with arithmetic.

The question is, what algorithm wants to operate generically on a model
of BitwiseOperations?  If we can't imagine one, it doesn't deserve its
own protocol.

Personally I don't think the strict separation of SetAlgebra and things
that do bitwise operations makes sense, but I know some people feel
strongly that it would be confusing for users to expose set operations
with bitwise operator names.  IMO using | for union and & for
intersection would be beautiful.  But that's a story for another day...

-- 
-Dave