[swift-evolution] “Integer” protocol?

Wed Nov 1 12:15:02 CDT 2017

On Wed, Nov 1, 2017 at 07:24 Daryle Walker <darylew at mac.com> wrote:

>
>
> Sent from my iPad
>
> On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>
> Right, these issues were discussed when the proposal was introduced and
> reviewed three times. In brief, what was once proposed as `Integer` was
> renamed `BinaryInteger` to avoid confusion in name between `Integer` and
> `Int`. It was also found to better reflect the semantics of the protocol,
> as certain functions treated the value not merely as an integer but
> operated specifically on its binary representation (for instance, the
> bitwise operators).
>
> Do not confuse integers from their representation. Integers have no
> intrinsic radix and all integers have a binary representation. This is
> distinct from floating-point protocols, because many real values
> representable exactly as a decimal floating-point value cannot be
> represented exactly as a binary floating-point value.
>
>
> Abstractly, integers have representations in nearly all real radixes. But
> mandating base-2 properties for a numeric type that uses something else
> (ternary, negadecimal, non-radix, etc.) in its storage is definitely
> non-trivial. Hence the request for intermediate protocols that peel off the
> binary requirements.
>

Not only binary properties, but specifically two’s-complement binary
properties. You are correct that some operations require thought for
implementation if your type uses ternary storage, or for any type that does
not specifically use two’s-complement representation internally, but having
actually implemented them I can assure you it is not difficult to do
correctly without even a CS degree.

Again, one must distinguish between the actual representation in storage
and semantics, which is what Swift protocols guarantee. The protocols are
totally agnostic to the internal storage representation. The trade-off for
supporting ternary _semantics_ is an additional set of protocols which
complicates understanding and use in generic algorithms. I am not aware of
tritwise operations being sufficiently in demand.

> To your specific question about bitwise operators: their semantics are
> with respect to the two's-complement binary representation of the integer
> regardless of the actual internal representation. `~` returns the one's
> complement of the two's-complement binary representation of the integer.
> FWIW, this is exactly what `mpn_com()` does in GNU MP for
> arbitrary-precision integers.
>
>
> To continue your own analogy, integers by themselves don’t have radix (or
> reduced-radix) complements. The complements depend on a fixed width, since
> they’re based on Radix ** Width modulo arithmetic (or Radix ** Width - 1
> for the reduced-radix complement).
>
> 15 has a two’s complement under a binary representation with N bits (where
> N is at least 4). It has a ones’ complement too. Doing any complement of 15
> without an N is non-sensical; the result effectively would have an infinite
> number of ones at its beginning. I guess GNU-MP is stopping at the width of
> the original number’s storage, but that doesn’t make it right (although
> it’s more practical).  That’s why complements should be under the
> fixed-width protocols, not the general integer ones.
>

The two’s-complement representation of a negative number contains an
infinite number of leading zeros when the bit width is infinite. Bitwise
operators have consistent semantics with this definition. Neither GNU MP,
nor a conformant sign-magnitude arbitrary-width type in Swift, performs
actual bitwise operations on the internal storage, but returns the result
that would be obtained by performing those operations on the notionally
infinite two’s-complement binary representation of the integer, which is
not the internal storage representation.

The binary representation of 15 is 0b1111. For an infinite-width type, the
one’s complement is 0b1...10000. That is the binary representation of -16.
So, `~15 as BigInt == -16`.

Again, one must distinguish semantics from representation. The bitwise
operators have two’s-complement semantics independent of internal
representation.

The very existence of BinaryInteger is proof of allowing protocols for
> types that don’t exist in the Standard Library (yet). (In other words, if
> protocols had to be justified with a current algorithm or type to be in the
> SL, then BinaryInteger should be purged since there’s no current type that
> uses it without using FixedWidthInteger too.) I just think the hierarchy
> needs a little more tweaking.
>

Yes, it’s meant to allow for an arbitrary-width integer type, a prototype
of which exists in the Swift repository. It is very much possible to write
such a type that conforms to all the requirements of BinaryInteger.

> On Tue, Oct 31, 2017 at 7:23 PM, Max Moiseev via swift-evolution <
> swift-evolution at swift.org> wrote:
>
>> Just for the reference. There was a lengthy discussion here in the
>> mailing list back when the proposal was introduced:
>>
>> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20170109/thread.html#30191
>>
>> Max
>>
>> On Oct 31, 2017, at 5:15 PM, Daryle Walker via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>> Looking at Apple’s Swift (4) docs at their SDK site, shouldn’t there be
>> an “Integer” protocol between Numeric and BinaryInteger? Without that,
>> there’s no solution for Integer types that are either a non-binary radix or
>> a non-radix system (besides being over-broad with Numeric).
>>
>> What would move there are: isSigned, quotientAndRemainder, signum, %, %=,
>> /, and /=.
>>
>> Also, how is ~ supposed to work in a BinaryInteger that is not a
>> FixedWidthInteger? Extend the high bits to infinity? Maybe that operator
>> should move to the derived protocol.
>>
>> Oh, why can’t a non-binary Integer type be fixed-width? FixedWidthInteger
>> should be renamed “FixedWidthBinaryInteger,” which derives from
>> BinaryInteger and a new version of FixedWidthInteger. The new version peels
>> off: max, min, addingReportingOverflow, dividedReportingOverflow,
>> dividingFullWidth, multipliedFullWidth, multipliedReportingOverflow,
>> remainderReportingOverflow, and subtractingReportingOverflow. There’s also
>> a “digitWidth” type property, analogous to “bitWidth”.
>>
>> Sent from my iPad
>> _______________________________________________
>> 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
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171101/21c46a21/attachment.html>