[swift-evolution] “Integer” protocol?

[Daryle Walker]

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. 

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


> 
> 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/57ae61fd/attachment.html>