“Integer” protocol?

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

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@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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.

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.

···

On Tue, Oct 31, 2017 at 7:23 PM, Max Moiseev via swift-evolution < swift-evolution@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@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

1 Like

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.

···

Sent from my iPad

On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Tue, Oct 31, 2017 at 7:23 PM, Max Moiseev via swift-evolution <swift-evolution@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@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Sent from my iPad

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 Wed, Nov 1, 2017 at 07:24 Daryle Walker <darylew@mac.com> wrote:

On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Tue, Oct 31, 2017 at 7:23 PM, Max Moiseev via swift-evolution < > swift-evolution@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@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Before everyone gets carried away with these protocols, can I ask what the
real use case for ternary integers is? Also I’m not a fan of bikeshedding
protocols for things that don’t exist (yet).

···

On Wed, Nov 1, 2017 at 12:15 PM, Xiaodi Wu via swift-evolution < swift-evolution@swift.org> wrote:

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

Sent from my iPad

On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <xiaodi.wu@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.

I can’t imagine it’d ever get far enough for me to care about Swift’s stance on the issue, but I want to build a 9-“trit” breadboard computer some day, just for my own edification/amusement.

(FWIW, while I’m not 100% on how the integer protocols ended up, this isn’t the part that I’d change)

- Dave Sweeris

···

On Nov 1, 2017, at 14:54, Kelvin Ma via swift-evolution <swift-evolution@swift.org> wrote:

On Wed, Nov 1, 2017 at 12:15 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

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

Sent from my iPad

On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <xiaodi.wu@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.

Before everyone gets carried away with these protocols, can I ask what the real use case for ternary integers is? Also I’m not a fan of bikeshedding protocols for things that don’t exist (yet).

To clarify slightly, it may be tedious to do, but the only real obstacle to implementing these properties for any integer representation should be efficiency. All you have to do is implement a pair of conversions to and from some twos complement integer representation, and the operations can be implemented by forwarding. I imagine that might conceivably be a challenge for an unbounded integer type, but for anything fixed-width, the cost of operations will be bounded by a constant.