Re: [swift-evolution] “Integer” protocol?

[David Sweeris via swift-evolution]

> On Nov 1, 2017, at 14:54, Kelvin Ma via swift-evolution 
>  wrote:
> 
> 
> 
>> On Wed, Nov 1, 2017 at 12:15 PM, Xiaodi Wu via swift-evolution 
>>  wrote:
>>> On Wed, Nov 1, 2017 at 07:24 Daryle Walker  wrote:
>> 
>>> 
>>> 
>>> Sent from my iPad
>>> 
 On Oct 31, 2017, at 10:55 PM, Xiaodi Wu  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).

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

Re: [swift-evolution] “Integer” protocol?

[Kelvin Ma via swift-evolution]

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  wrote:
>
>>
>>
>> Sent from my iPad
>>
>> On Oct 31, 2017, at 10:55 PM, Xiaodi Wu  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).
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] “Integer” protocol?

[Xiaodi Wu via swift-evolution]

On Wed, Nov 1, 2017 at 07:24 Daryle Walker  wrote:

>
>
> Sent from my iPad
>
> On Oct 31, 2017, at 10:55 PM, Xiaodi Wu  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 0b. For an infinite-width type, the
one’s complement is 0b1...1. 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@swift.org> wrote:
>
>> Just for the reference. There was a lengthy discussion here in the
>> mailing list back 

Re: [swift-evolution] “Integer” protocol?

[Daryle Walker via swift-evolution]

Sent from my iPad

> On Oct 31, 2017, at 10:55 PM, Xiaodi Wu  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 
>  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 
>>>  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
>> 
> 
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] “Integer” protocol?

[Xiaodi Wu via 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
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] “Integer” protocol?

[Max Moiseev via swift-evolution]

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

[swift-evolution] “Integer” protocol?

[Daryle Walker via swift-evolution]

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