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

Sun Jan 29 06:41:38 CST 2017

On Sun, Jan 29, 2017 at 6:02 AM, Brent Royal-Gordon via swift-evolution <
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`? (I think `Comparable`
> isn't here because complex numbers can't be compared, but correct me if I'm
> wrong about that.)
>
> > /// 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?
>
> > /// 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?
>

Could you comment on what use cases would make `33` the relevant answer?
I'd always thought that "the number of bits in the current binary
representation" admits of no alternative interpretation than `32` in your
example.

> >   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?

Having mulled the idea of implementing an IEEE Decimal type, I'd be sad to
see these return DoubleWidth<Self>. Double-width multiply as it is here is
useful when you want to get the result and immediately discard either the
high or the low bits, for instance. If you'd want a result of type
`DoubleWidth<Foo>` instead, you could always just write
`DoubleWidth<Foo>(a) * DoubleWidth<Foo>(b)`.

> > /// 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`?

Far less obscure than `ulp` in `FloatingPoint`!

I think `popcount` is by far the most appropriate name here. It uses
`count`, which is rather consistent with existing Swift APIs, and it is a
visually recognizable term of art (note the absence of capitalization on
"count"). I think a useful barometer for the appropriateness of a term of
art is three-pronged:

* People who know of this concept (the population count of a binary
integer) will almost invariably know it as `popcount`. (Really, if you're
working with binary integers as a collection of bits, you will likely
encounter the term if you look for useful algorithms).

* Those who do not can immediately get all the information they need by
typing this term into Google or Wikipedia, because it needs no
disambiguation.

* It is hard to express the concept more accurately using an alternative
name. `hammingWeight`, `populationCount` are move verbose; `hammingWeight`
would be the more general term, but loses the word "count" and doesn't
_specifically_ communicate the fact that property has to do with the
integer's _binary_ representation. `populationCount` is needlessly wordy
and still a term of art. `countOfOnes` is unfamiliar to people who know
what a popcount is, and no more enlightening to someone who doesn't know
what a popcount is, as it fails to communicate the binary
representation-ness directly.

> > 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. It might make a great deal of sense to
> support bitwise operations on this type, even though I don't want to
> clutter it up with arithmetic.
>
> --
> Brent Royal-Gordon
> Architechies
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170129/7e0349f1/attachment.html>