[swift-evolution] protocol-oriented integers (take 2)
Xiaodi Wu
xiaodi.wu at gmail.com
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>
More information about the swift-evolution
mailing list