protocol-oriented integers (take 2)

dabrahams · January 15, 2017, 2:52pm

Responding to both Jacob and Xiaodi here; thanks very much for your
feedback!

Great work, all. I'm not sure I ever commented on SE-0104, so I've read
through this one more carefully. Here are some things that came to mind:

*## Arithmetic*

Why are ExpressibleByIntegerLiteral and init?<T:BinaryInteger>(exactly:)
required? I could understand needing access to 0, but this could be
provided by a static property or nullary initializer. It doesn't seem like
all types supporting arithmetic operations would necessarily be convertible
from an arbitrary binary integer.

I tried to evaluate the Arithmetic protocol by considering what it means
for higher-dimensional types such as CGPoint and CGVector. My use case was
a linear interpolation function:

   func lerp<T: Arithmetic>(from a: T, to b: T, by ratio: T) -> T {
       return a + (b - a) * ratio
   }

If I've read the proposal correctly, this definition works for integer and
floating-point values. But we can't make it work properly for CGVector (or,
perhaps less mathematically correct but more familiar, CGPoint). It's okay
to define +(CGVector, CGVector) and -(CGVector, CGVector), but *(CGVector,
CGVector) and /(CGVector, CGVector) don't make much sense. What we really
want is *(CGVector, *CGFloat*) and /(CGVector, *CGFloat*).

After consulting a mathematician, I believe what the lerp function really
wants is for its generic param to be an affine space
<https://en.wikipedia.org/wiki/Affine_space>\. I explored this a bit here:
https://gist.github.com/jtbandes/93eeb7d5eee8e1a7245387c660d53b
03#file-affine-swift-L16-L18

This approach is less restrictive and more composable than the proposed
Arithmetic protocol, which can be viewed as a special case with the
following definitions:

   extension Arithmetic: AffineSpace, VectorSpace { // not actually
allowed in Swift
       typealias Displacement = Self
       typealias Scalar = Self
   }

It'd be great to be able to define a lerp() which works for all
floating-point and integer numbers, as well as points and vectors (assuming
a glorious future where CGPoint and CGVector have built-in arithmetic
operations). But maybe the complexity of these extra protocols isn't worth
it for the stdlib...

I think, in the end, it's the _name_ that could use improvement here. As
the doc comments say, `Arithmetic` is supposed to provide a "suitable basis
for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
appropriate? It would make it clear that `CGVector` is not meant to be a
conforming type.

We want Arithmetic to be able to handle complex numbers. Whether Scalar
would be appropriate in that case sort of depends on what the implied
field is, right?

I was under the impression that complex numbers are scalar
numbers...

Well, you can view them as 2d vectors, so I'm not sure. We need more of
a numerics expert than I am to weigh in here.

although maybe not since once you get past, I think quaternions, you
start losing division and eventually multiplication, IIRC. (I hate it
when two of my recollections try to conflict with each other.)

It's true that CGPoint and CGVector have no obvious sensible
interpretation of "42", and that's unfortunate. The problem with
protocols for algebraic structures is that there's an incredibly
complicated lattice (see figures 3.1, 3.2 in
ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
shove all of those protocols into the standard library (especially not
prematurely) but each requirement you add to a more-coarsely aggregated
protocol like Arithmetic will make it ineligible for representing some
important type.

My only concern with this is that later on, if we do decide the stdlib
should have them, does it then become a breaking change to start
moving all that stuff around? Or would everything be fine as long as
the net requirements for the "Arithmetic" protocol stay the same
regardless of how things get redistributed under the hood?

As far as I know, we don't have a strategy for injecting protocols into
a refinement hierarchy without destablizing ABI.

*## FixedWidthInteger*

Why is popcount restricted to FixedWidthInteger? It seems like it could
theoretically apply to any UnsignedInteger.

You can perfectly legitimately get a popcount for a signed integer. It's
just looking at the binary representation and counting the ones. But then
with two's complement, it'd have to be restricted to FixedWidthInteger and
not BinaryInteger, because the same negative value would have a different
popcount depending on the type's bitwidth.

Right, or to put it differently, the popcount of a negative BigInt would
always be inifinite.

I'd disagree strongly with removing popcount from signed binary
integers. However, I suppose the same requirement could be applied to
both FixedWidthInteger and UnsignedInteger.

Given that there's little point in ever creating an unsigned BigInt
type, I think that wouldn't make much sense.

Why is that? I'd think they'd be useful anywhere it'd be a logical
error to have a negative value and UInt64 wasn't big enough.

You can always build that type around a signed BigInt implementation.
The point of fixed width unsigned integers is that you really need that
last bit for representation. With a BigInt, there is no last bit.

Note also that representing “it's a logical error to have a negative
value” in the type system clashes a bit with the Swift philosophy that
you're basically supposed to use Int everywhere.

Is that situation simply that rare?

I think it's pretty rare, but the question is really, in the situations
where this could come up, is it important to be able to write a generic
algorithm over UnsignedInteger that doesn't use any additional protocols
and needs to work with your unsigned BigInt and needs to call popcount.
At that point the use-case starts to seem pretty darned narrow.

Remember, you can always define protocol UnsignedPopCount and make all
the unsigned types conform to it.

···

on Sun Jan 15 2017, David Sweeris <davesweeris-AT-mac.com> wrote:

On Jan 14, 2017, at 18:55, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:
On Sat, Jan 14, 2017 at 1:32 AM, Jacob Bandes-Storch via swift-evolution < >>> swift-evolution@swift.org> wrote:

--
-Dave

xwu · January 15, 2017, 9:20am

Given that Arithmetic also provides for multiplication and division, might
it be wise then also to have .multiplicativeIdentity (or .one)?

···

On Sun, Jan 15, 2017 at 02:47 Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Sat Jan 14 2017, Dave Abrahams <swift-evolution@swift.org> wrote:

> That said, the ability to interpret integer literals as an arbitrary
> Arithmetic isn't used anywhere in the standard library, so I'd like to
> consider undoing
>
Getting rid of Arithmetic.init() in favor of 0 · apple/swift@de5b03d · GitHub
> and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
> BinaryInteger.

Oh, and I meant to add: maybe the right way for an arbitrary X modeling
Arithmetic to spell zero (which is needed for negation) is something
like

   X.additiveIdentity

or

   X.zero

in other words, via a requirement

   static var theNameWeChoose: Self { get }

--
-Dave

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

xwu · January 15, 2017, 10:42pm

[ proposal link: https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f
3fcc7cad8c ]

Responding to both Jacob and Xiaodi here; thanks very much for your
feedback!

> I think, in the end, it's the _name_ that could use improvement here. As
> the doc comments say, `Arithmetic` is supposed to provide a "suitable
basis
> for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
> appropriate? It would make it clear that `CGVector` is not meant to be a
> conforming type.

We want Arithmetic to be able to handle complex numbers. Whether Scalar
would be appropriate in that case sort of depends on what the implied
field is, right?

I think "scalar" is an appropriate term for any field. The scalar-ness
usually comes into play when it's used in a vector space, but using the
term alone doesn't bother me.

It's true that CGPoint and CGVector have no obvious sensible
interpretation of "42", and that's unfortunate. The problem with
protocols for algebraic structures is that there's an incredibly
complicated lattice (see figures 3.1, 3.2 in
ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
shove all of those protocols into the standard library (especially not
prematurely) but each requirement you add to a more-coarsely aggregated
protocol like Arithmetic will make it ineligible for representing some
important type.

Yep, it is quite complicated, and I understand not wanting to address all
that right now; calling it ScalarArithmetic seems appropriate to clarify
the limitations. FieldArithmetic might also be appropriate, but is less
clear (+ see below about quaternions).

Daves Sweeris and Abrahams wrote:

> > I was under the impression that complex numbers are scalar numbers...
although maybe not since once you get past, I think quaternions, you start
losing division and eventually multiplication, IIRC. (I hate it when two of
my recollections try to conflict with each other.)
>
> Well, you can view them as 2d vectors, so I'm not sure. We need more of
a numerics expert than I am to weigh in here.

But complex numbers have multiplication and division operations defined
(they form a field), unlike regular vectors in R². Meaning you can have a
vector space over the field of complex numbers.

You still have multiplication and division past quaternions, but the
quaternions are *not commutative*. This isn't really a problem in Swift,
since the compiler never allows you to write an expression where the order
of arguments to an operator is ambiguous. This means they are *not a
field*, just a division ring <https://en.wikipedia.org/wiki/Division_ring> (a
field is a commutative division ring). (I believe you can't technically
have a vector space over a non-commutative ring; the generalization would
be a module <https://en.wikipedia.org/wiki/Module_(mathematics)>\.
That's probably an argument for the name ScalarArithmetic over
FieldArithmetic.)

Hmm, the issue is that the integers are not a field. So, if we're going to
have it all modeled by one protocol, maybe neither is the best term.

Octonions are furthermore *not associative*, which is more of a problem
since the standard library arithmetic operators are given an associativity.
We can't give that up for regular numeric types, so someone working with
octonions would just have to define their own non-associative operators
(since there's no way for the protocol requirement to specify the operator
associativity).

That said, the ability to interpret integer literals as an arbitrary
Arithmetic isn't used anywhere in the standard library, so I'd like to
consider undoing
Getting rid of Arithmetic.init() in favor of 0 · apple/swift@de5b03d · GitHub
d5709eb2be069286c1
and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
BinaryInteger.

+1

>> *## BinaryInteger*
>>
>> I'm a little confused by the presence of init(extendingOrTruncating:)
for
>> *all* binary integers. Why does it make sense to be able to write
>> UInt16(extendingOrTruncating: (-21 as Int8)) ? In my mind,
sign-extension
>> only has meaning when the source and destination types are both signed.
>>
>
> Here (just IMHO), I disagree. Since any binary integer can be truncated
and
> any can be right-shifted, it makes sense for
`init(extendingOrTruncating:)`
> to be available for all of them. If I understand the proposal correctly,
> `Int(extendingOrTruncating: (-1 as Int8))` would give you a different
> result than `Int(extendingOrTruncating: (255 as UInt8)`.

Yes it would. But the real justification for this operation is generic
programming with integers. It isn't possible, today, to define:

init<T:BinaryInteger>(extending:T) where T.isNarrowerThan(Self)
init<T:BinaryInteger>(truncating:T) where T.isWiderThan(Self)

>> Although I would not be against a clamp() function in the standard
library,
>> "init(clamping:)" sounds strange to me. What about calling it
>> "init(nearestTo:)"? One could also define a FloatingPoint version of
>> init(nearestTo:), i.e. lround(). For maximum annoyance and
explicitness,
>> you could even rename the existing init(_:) to init(truncating:) to
make it
>> clear that truncation, not regular rounding, occurs when converting
from
>> floating-point.
>>
>
> I would disagree with that as well; the existing `init(_:)` truncates
the
> fractional part but errors if that value is outside the representable
> range, while the word "truncating" makes it sound like something is
done to
> make any possible source value give you a destination value (a la
> "extendingOrTruncating" for integers).
>
> Meanwhile, "nearest to" is problematic for me because either 127 and
129 is
> "nearest to" 128, and neither integer is "nearest to" 500, yet
> `Int8(clamping: 128)` and `Int8(clamping: 500)` both give you 127. This
> operation is very different from lround() for floating point, which in
> Swift is `rounded(.toNearestOrAwayFromZero)` (or just `rounded()`).

127 and 129 are both nearest to 128, but both of them are not Int8s. The
"Int8(nearestTo: 128)" would be 127.

Well, now we're splitting hairs, but I don't think this is among the more
plausible rationalizations of a hypothetical init(nearestTo:). Either you
look for the integer(s) nearest to (128 as Int) in the set of all Int
values. Then, the nearest integers are equally 127 and 129. You attempt to
convert both to Int8 and trap (unless you first _clamp_ your results to the
range [-128, 127] before attempting to convert). Or, you look for the Int8
value(s) nearest to 128 in the set of all possible Int8 values. However,
since the distance between (128 as Int) and any Int8 is undefined, (127 as
Int8) is strictly speaking no nearer to (128 as Int) than is (-128 as Int8)
or any other Int8 value.

By contrast, the word `clamping` tells you that something is first done to
(128 as Int)--namely, it is clamped to the range [-128, 127]--and then the
result is converted to an Int8; thus, this function never traps.

> In both these cases, I think it's important to use spellings that
> distinguish doing things to the fractional part of floating point values
> and doing things to the binary representation of integer values. I think
> there's great value in using the term "clamp", which is very different
from
> "nearest"; and in using an unlabeled `init(_:)` for initializing from FP
> values, which is most similar to the unlabeled `init(_:)` for
initializing
> from integer values, as opposed to your suggested `init(truncating:)`
which
> connotes some similarity to `init(extendingOrTruncating:)` for integer
> values.

+1

> *... masking shifts*
>>
>> The example claims that "(30 as UInt8) &>> 11" produces 3, because it
>> right-shifts 30 by 3. But isn't the bitWidth of UInt8 always 8 since
it's a
>> fixed-width type?

Yes.

>> Why should 11 get masked to 3 before the shift?

Because those are the semantics of masking shift?

Ah, I see why I was confused (the point is that 2³ = 8 = bitWidth). Does
this mean that masking shifts only work when the bitWidth is a power of
two? Otherwise, there'd be no way to reduce the shift range to exactly
0..<bitWidth using a mask.

You can think of masking shift as an optimization akin to using &+ to
add signed numbers when you know it can't overflow. It's an expert's
tool. If you want semantics that always make sense, use regular shift.

>> (Also, it might be a good idea to choose examples with numbers whose
>> base-ten representations don't look like valid binary. )

Good point.

>> What use cases are there for masking shifts? I was under the
>> impression that "smart shifts" were pretty much how the usual shift
>> instructions already behaved.

No, sadly not! The way the usual shift instructions behave is that if
you shift by a negative amount or you overshift, you get undefined
behavior, which gets expressed in various fun ways at runtime!

>> (Minor: were the smart shift operators supposed to be included as
>> BinaryInteger protocol requirements? I only see them in the
"heterogeneous
>> shifts" extension.)

They don't need to be requirements, as they're defined entirely in terms
of other (required) operations. I'd be interested in any arguments you
might have for making them requirements, though.

>> *... init<T: BinaryInteger>(_ source: T)*
>>
>> Now a thought experiment: suppose you wanted to write an
>> arbitrary-precision BigInt, or any binary integer such as Int256. The
>> BinaryInteger protocol requires you to provide init<T:BinaryInteger>(_
>> source: T). Given the source of type T, how do you access its bits? Is
>> repeated use of word(at:) the recommended way?

Yes.

>> If so, it might be nice to include a "wordCount" returning the number
>> of available words; otherwise I suppose the user has to use something
>> like bitWidth/(8*MemoryLayout<Int>.size), which is pretty ugly.

good catch; countRepresentedWords is in the prototype
(https://github.com/apple/swift/blob/new-integer-protocols/s
tdlib/public/core/Integers.swift.gyb#L1521),
and it should be in the proposal.

>> *## FixedWidthInteger*
>>
>> Why is popcount restricted to FixedWidthInteger? It seems like it could
>> theoretically apply to any UnsignedInteger.
>>
>
> You can perfectly legitimately get a popcount for a signed integer. It's
> just looking at the binary representation and counting the ones. But
then
> with two's complement, it'd have to be restricted to FixedWidthInteger
and
> not BinaryInteger, because the same negative value would have a
different
> popcount depending on the type's bitwidth.

Right, or to put it differently, the popcount of a negative BigInt would
always be inifinite.

Makes sense, but infinity has no representation in Int, so what would the
popcount be?

I think the point here is that not all BigInt values would have a
representable popcount, justifying the requirement being on
FixedWidthInteger as opposed to BinaryInteger.

···

On Sun, Jan 15, 2017 at 3:29 PM, Jacob Bandes-Storch via swift-evolution < swift-evolution@swift.org> wrote:

On Sat, Jan 14, 2017 at 4:55 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

>> *## Masking arithmetic*
>>
>> Do &* and &+ and &- need their operands to have the same type, or could
>> these be heterogeneous too (at least &+ and &-)?

I don't know what semantics you're imagining for heterogeneous &+. What
type would it return? What mask would it use?

I was thinking of these as overflow rather than masking operators; i.e.
the lhs type would be allowed to overflow if the rhs value were too large.

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

dabrahams · January 16, 2017, 1:14am

[ proposal link: moiseev’s gists · GitHub
62ffe3c91b66866fdebf6f3fcc7cad8c ]

Responding to both Jacob and Xiaodi here; thanks very much for your
feedback!

> I think, in the end, it's the _name_ that could use improvement here. As
> the doc comments say, `Arithmetic` is supposed to provide a "suitable
basis
> for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
> appropriate? It would make it clear that `CGVector` is not meant to be a
> conforming type.

We want Arithmetic to be able to handle complex numbers. Whether Scalar
would be appropriate in that case sort of depends on what the implied
field is, right?

I think "scalar" is an appropriate term for any field.

Yes, but IIUC complex numbers are not scalars in every field.

The scalar-ness usually comes into play when it's used in a vector
space, but using the term alone doesn't bother me.

It's true that CGPoint and CGVector have no obvious sensible
interpretation of "42", and that's unfortunate. The problem with
protocols for algebraic structures is that there's an incredibly
complicated lattice (see figures 3.1, 3.2 in
ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
shove all of those protocols into the standard library (especially not
prematurely) but each requirement you add to a more-coarsely aggregated
protocol like Arithmetic will make it ineligible for representing some
important type.

Yep, it is quite complicated, and I understand not wanting to address all
that right now; calling it ScalarArithmetic seems appropriate to clarify
the limitations.

I don't see why we should do that, as opposed to moving integer literal
convertibility down the refinement hierarchy and adding an additive
identity. The latter seems like it makes a sensible API for average
programmers while still accomodating vector types.

If we can define the semantics properly (not sure if that's possible),
it could even cover SIMD types.

FieldArithmetic might also be appropriate, but is less clear (+ see
below about quaternions).

Daves Sweeris and Abrahams wrote:

> I was under the impression that complex numbers are scalar numbers...

although maybe not since once you get past, I think quaternions, you start
losing division and eventually multiplication, IIRC. (I hate it when two of
my recollections try to conflict with each other.)

Well, you can view them as 2d vectors, so I'm not sure. We need more of
a numerics expert than I am to weigh in here.

But complex numbers have multiplication and division operations defined
(they form a field), unlike regular vectors in R². Meaning you can have a
vector space over the field of complex numbers.

Yes, I know. I'm just not clear enough on the meaning of “scalar” to
know whether it's appropriate to call complex numbers scalars
independent of knowing the field in which they are scalars. Does
Complex numbers: multiplication describe a field,
where the complex numbers are treated as 2d vectors? I haven't done the
analysis.

You still have multiplication and division past quaternions, but the
quaternions are *not commutative*. This isn't really a problem in Swift,
since the compiler never allows you to write an expression where the order
of arguments to an operator is ambiguous. This means they are *not a field*,
just a division ring <https://en.wikipedia.org/wiki/Division_ring> (a field
is a commutative division ring). (I believe you can't technically have a
vector space over a non-commutative ring; the generalization would be a
module <https://en.wikipedia.org/wiki/Module_(mathematics)>\. That's
probably an argument for the name ScalarArithmetic over FieldArithmetic.)

Octonions are furthermore *not associative*, which is more of a problem
since the standard library arithmetic operators are given an associativity.
We can't give that up for regular numeric types, so someone working with
octonions would just have to define their own non-associative operators
(since there's no way for the protocol requirement to specify the operator
associativity).

I think syntactic associativity of operators might be a totally
orthogonal thing to semantic associativity of binary functions, so I'm
not sure this is an issue.

That said, the ability to interpret integer literals as an arbitrary
Arithmetic isn't used anywhere in the standard library, so I'd like to
consider undoing
Getting rid of Arithmetic.init() in favor of 0 · apple/swift@de5b03d · GitHub
d5709eb2be069286c1
and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
BinaryInteger.

+1

>> *## BinaryInteger*
>>
>> I'm a little confused by the presence of init(extendingOrTruncating:)
for
>> *all* binary integers. Why does it make sense to be able to write
>> UInt16(extendingOrTruncating: (-21 as Int8)) ? In my mind,
sign-extension
>> only has meaning when the source and destination types are both signed.
>>
>
> Here (just IMHO), I disagree. Since any binary integer can be truncated
and
> any can be right-shifted, it makes sense for
`init(extendingOrTruncating:)`
> to be available for all of them. If I understand the proposal correctly,
> `Int(extendingOrTruncating: (-1 as Int8))` would give you a different
> result than `Int(extendingOrTruncating: (255 as UInt8)`.

Yes it would. But the real justification for this operation is generic
programming with integers. It isn't possible, today, to define:

init<T:BinaryInteger>(extending:T) where T.isNarrowerThan(Self)
init<T:BinaryInteger>(truncating:T) where T.isWiderThan(Self)

>> Although I would not be against a clamp() function in the standard
library,
>> "init(clamping:)" sounds strange to me. What about calling it
>> "init(nearestTo:)"? One could also define a FloatingPoint version
>> of init(nearestTo:), i.e. lround(). For maximum annoyance and
>> explicitness, you could even rename the existing init(_:) to
>> init(truncating:) to make it clear that truncation, not regular
>> rounding, occurs when converting from floating-point.
>>
>
> I would disagree with that as well; the existing `init(_:)`
> truncates the fractional part but errors if that value is outside
> the representable range, while the word "truncating" makes it sound
> like something is done to make any possible source value give you a
> destination value (a la "extendingOrTruncating" for integers).
>
> Meanwhile, "nearest to" is problematic for me because either 127
> and 129 is "nearest to" 128, and neither integer is "nearest to"
> 500, yet `Int8(clamping: 128)` and `Int8(clamping: 500)` both give
> you 127. This operation is very different from lround() for
> floating point, which in Swift is
> `rounded(.toNearestOrAwayFromZero)` (or just `rounded()`).

127 and 129 are both nearest to 128, but both of them are not Int8s. The
"Int8(nearestTo: 128)" would be 127.

Makes sense to me. I think "clamping:" is more term-of-art-y and
"nearestTo:" is more comprehensible to a wide audience. I prefer the
latter unless the numericists out there are going to howl in protest.
Steve Canon, what's your take?

> In both these cases, I think it's important to use spellings that
> distinguish doing things to the fractional part of floating point values
> and doing things to the binary representation of integer values. I think
> there's great value in using the term "clamp", which is very different
from
> "nearest"; and in using an unlabeled `init(_:)` for initializing from FP
> values, which is most similar to the unlabeled `init(_:)` for
initializing
> from integer values, as opposed to your suggested `init(truncating:)`
which
> connotes some similarity to `init(extendingOrTruncating:)` for integer
> values.

+1

> *... masking shifts*
>>
>> The example claims that "(30 as UInt8) &>> 11" produces 3, because it
>> right-shifts 30 by 3. But isn't the bitWidth of UInt8 always 8 since
it's a
>> fixed-width type?

Yes.

>> Why should 11 get masked to 3 before the shift?

Because those are the semantics of masking shift?

Ah, I see why I was confused (the point is that 2³ = 8 = bitWidth). Does
this mean that masking shifts only work when the bitWidth is a power of
two?

Yes; we think that's a safe assumption for all fixed-width integers. We
could always define the mask in terms of the smallest power of 2 > T.max
if we want to lift that restriction, but it seems likely to not be
worthwhile.

Otherwise, there'd be no way to reduce the shift range to exactly
0..<bitWidth using a mask.

You can think of masking shift as an optimization akin to using &+ to
add signed numbers when you know it can't overflow. It's an expert's
tool. If you want semantics that always make sense, use regular shift.

>> (Also, it might be a good idea to choose examples with numbers whose
>> base-ten representations don't look like valid binary. )

Good point.

>> What use cases are there for masking shifts? I was under the
>> impression that "smart shifts" were pretty much how the usual shift
>> instructions already behaved.

No, sadly not! The way the usual shift instructions behave is that if
you shift by a negative amount or you overshift, you get undefined
behavior, which gets expressed in various fun ways at runtime!

>> (Minor: were the smart shift operators supposed to be included as
>> BinaryInteger protocol requirements? I only see them in the
"heterogeneous
>> shifts" extension.)

They don't need to be requirements, as they're defined entirely in terms
of other (required) operations. I'd be interested in any arguments you
might have for making them requirements, though.

>> *... init<T: BinaryInteger>(_ source: T)*
>>
>> Now a thought experiment: suppose you wanted to write an
>> arbitrary-precision BigInt, or any binary integer such as Int256. The
>> BinaryInteger protocol requires you to provide init<T:BinaryInteger>(_
>> source: T). Given the source of type T, how do you access its bits? Is
>> repeated use of word(at:) the recommended way?

Yes.

>> If so, it might be nice to include a "wordCount" returning the number
>> of available words; otherwise I suppose the user has to use something
>> like bitWidth/(8*MemoryLayout<Int>.size), which is pretty ugly.

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.

>> *## FixedWidthInteger*
>>
>> Why is popcount restricted to FixedWidthInteger? It seems like it could
>> theoretically apply to any UnsignedInteger.
>>
>
> You can perfectly legitimately get a popcount for a signed
> integer. It's just looking at the binary representation and
> counting the ones. But then with two's complement, it'd have to be
> restricted to FixedWidthInteger and not BinaryInteger, because the
> same negative value would have a different popcount depending on
> the type's bitwidth.

Right, or to put it differently, the popcount of a negative BigInt would
always be inifinite.

Makes sense, but infinity has no representation in Int, so what would the
popcount be?

Exactly my point. You can't express the result, unless maybe you want
to do it relative to `countRepresentedWords`

>> *## Masking arithmetic*
>>
>> Do &* and &+ and &- need their operands to have the same type, or could
>> these be heterogeneous too (at least &+ and &-)?

I don't know what semantics you're imagining for heterogeneous &+. What
type would it return? What mask would it use?

I was thinking of these as overflow rather than masking operators; i.e. the
lhs type would be allowed to overflow if the rhs value were too large.

You didn't really answer the questions, AFAICT. Anyway, I think the
answer is that unless someone can define for heterogeous &+ et
al. simple and useful semantics that are implementable in the current
language, they should remain homogeneous.

···

on Sun Jan 15 2017, Jacob Bandes-Storch <jtbandes-AT-gmail.com> wrote:

On Sat, Jan 14, 2017 at 4:55 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

--
-Dave

Brent_Royal-Gordon · January 30, 2017, 8:21am

I mean that `OptionSet.RawValue` currently has to conform to `BitwiseOperations`, but would now need to conform to `BinaryInteger` (or a sub-protocol).

···

On Jan 29, 2017, at 10:07 PM, Dave Abrahams <dabrahams@apple.com> wrote:

It might make a great deal of sense to support bitwise operations on
this type,

I think that's a model of SetAlgebra, then, isn't it?

Hmm, arguably. It's a shame that we won't be able to use it with
things like `OptionSet`, though.

Why not? That conforms to SetAlgebra.

--
Brent Royal-Gordon
Architechies

Nevin · January 31, 2017, 11:59am

What, exactly, is the intended purpose of doubleWidthDivide?

I ask because, outside of degenerate cases, a quotient and remainder will
fit in the same size type as the operands.

So widthX / widthY will have quotient that fits in width X, and remainder
that fits in width Y.

In general, we cannot assume either one would be any smaller than that.

Nevin

···

On Monday, January 30, 2017, Brent Royal-Gordon via swift-evolution < swift-evolution@swift.org> wrote:

> On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev@apple.com > <javascript:;>> wrote:
>
> doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
> 1. The components of it’s return type are not high and low, but are
quotient and remainder instead.
> 2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the
case for quotient and remainder.

You're right about the return value; for `doubleWidthDivide(_:_:)`, I was
thinking about changing the dividend. Specifically, I'm thinking we should
change these to:

        static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) ->
DoubleWidth<Self>
        static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs:
Self) -> (quotient: Self, remainder: Self)

I'm also thinking a little bit about spelling of these operations. I'd
*love* to be able to call them `*` and `/` and let the type system sort
things out, but that would cause problems, especially for multiply (since
the return value is the only thing different from a normal `*`). We could
invent a new operator, but that would be a bit much. Could these be simply
`multiply` and `divide`, and we'll permit the `DoubleWidth`
parameter/return type to explain itself?

I'm also thinking the second parameter should be labeled `by`, since
that's the way people talk about these operations. Applying both of these
suggestions, we'd get:

        static func multiply(_ lhs: Self, by rhs: Self) ->
DoubleWidth<Self>
        static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) ->
(quotient: Self, remainder: Self)

        let x = Int.multiply(a, by: b)
        let (aʹ, r) = Int.divide(x, by: b)
        assert(a == aʹ)
        assert(r == 0)

Should the standard library provide extensions automatic definitions of
multiplication and division in terms of their double-width equivalents?

        extension FixedWidthInteger {
                func multipliedWithOverflow(by other: Self) ->
(partialValue: Self, overflow: ArithmeticOverflow) {
                        let doubledResult = Self.multiply(self, by: other)
                        let overflowed = doubledResult.high !=
(doubledResult < 0 ? -1 : 0)
                        return (Self(bitPattern:
doubledResult.lowerValue), overflowed ? .overflowed : .none)
                }

                func quotientAndRemainder(dividingBy other: Self) ->
(quotient: Self, remainder: Self) {
                        precondition(other != 0, "Divide by zero")
                        return Self.divide(DoubleWidth(self), by: other)
                }

                func dividedWithOverflow(by other: Self) -> (partialValue:
Self, overflow: ArithmeticOverflow) {
                        guard other != 0 else { return (self, .overflowed)
}

                        let result = Self.divide(self, by: other)
                        return (result.quotient, .none)
                }

                static func * (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.dividedWithOverflow(by: rhs)
                        precondition(result.overflow == .none,
"Multiplication overflowed")
                        return result.partialValue
                }

                static func / (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.quotientAndRemainder(dividingBy:
rhs)
                        return result.quotient
                }

                static func % (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.quotientAndRemainder(dividingBy:
rhs)
                        return result.remainder
                }
}

Hmm...having actually written this out, I now have a couple of concerns:

1. There's a lot of jumping back and forth between instance methods and
static methods. Can we standardize on just static methods? Or make sure
that the user-facing interfaces are all either operators or instance
methods?

2. There is no quotient-and-remainder-with-overflow, either regular or
double-width. Can we do that?

3. "Overflow" is not really a good description of what's happening in
division; the value is undefined, not overflowing. Is there a better way to
express this?

4. For that matter, even non-fixed-width division can "overflow"; should
that concept be hoisted higher up the protocol hierarchy?

5. For *that* matter, should we simply make these operations throw instead
of returning a flag?

        enum ArithmeticError<NumberType: Arithmetic>: Error {
                // Are generic errors permitted?
                case overflow(partialValue: NumberType)
                case undefined
        }

        // Should these throwing definitions be higher up so that, when
working with `Arithmetic`
        // or similar types, you have an opportunity to handle errors
instead of always trapping?
        protocol FixedWidthInteger: BinaryInteger {
                ...
                func adding(_ other: Self) throws -> Self
                func subtracting(_ other: Self) throws -> Self
                func multiplied(by other: Self) throws -> Self
                func divided(by other: Self) throws -> Self
                ...
        }

I'm *really* tempted to suggest adding throwing variants of the actual
operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be
too specialized to really justify that.

> Having said that, there is a solution for doubleWidthMultiply, that I
think is worth trying:
>
> enum DoubleWidth<T> {
> case .parts(high: T, low: T.Magnitude)
>
> var high: T { switch self { case .parts(let high, _): return high } }
> var low: T.Magnitude { switch self { case .parts(_, let low): return
low } }
> }
>
> This way it will be possible to both do pattern-matching on the result
of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low
when needed.

This sounds like a good idea to me. (Unless we want to create a protocol
for destructuring, but I assume that's out of scope.)

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <javascript:;>
https://lists.swift.org/mailman/listinfo/swift-evolution

moiseev · January 31, 2017, 8:53pm

Hi Brent,

Thanks a lot for your suggestions! After having discussed them with Dave, we came up with the following design that I personally like a lot.

enum Overflowing { case .withOverflow }
enum FullWidth { case .fullWidth }

protocol FixedWidthInteger {
  func adding(_ other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)
  func subtracting(_ other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)
  func multiplied(by other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)
  func divided(by other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)

func multiplied(by other: Self, _: FullWidth) -> DoubleWidth<Self>
func dividing(_ other: DoubleWidth<Self>, _: FullWidth) -> (quotient: Self, remainder: Self)
}

Call sites would look like:

x.multiplied(by: y, .withOverflow) and x.multiplied(by: y, .fullWidth)

a little different for the division:

x.divided(by: y, .withOverflow) and y.dividing(x, .fullWidth)

Note the inverse-ness of `dividing`, but the lack of the argument label makes it quite natural.

2. There is no quotient-and-remainder-with-overflow, either regular or double-width. Can we do that?

What will the partialValue equivalent be in case of overflow in overflowing quotient+remainder division?

3. "Overflow" is not really a good description of what's happening in division; the value is undefined, not overflowing. Is there a better way to express this?

Division by 0 is not overflowing, true, but Int.min / (-1) is.

4. For that matter, even non-fixed-width division can "overflow"; should that concept be hoisted higher up the protocol hierarchy?

In my head, overflow is a notion related to fixed sized types. You simply don’t have enough room to represent certain values. Following this line of thought, binary integer is not bounded, and can grow at will. So FixedWidthInteger looks like the right place for overflowing operations. And if we decide to not consider division by 0 an overflow, the model seems quite consistent.

···

On Jan 30, 2017, at 7:55 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev@apple.com> wrote:

doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
1. The components of it’s return type are not high and low, but are quotient and remainder instead.
2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the case for quotient and remainder.

You're right about the return value; for `doubleWidthDivide(_:_:)`, I was thinking about changing the dividend. Specifically, I'm thinking we should change these to:

  static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -> DoubleWidth<Self>
  static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs: Self) -> (quotient: Self, remainder: Self)

I'm also thinking a little bit about spelling of these operations. I'd *love* to be able to call them `*` and `/` and let the type system sort things out, but that would cause problems, especially for multiply (since the return value is the only thing different from a normal `*`). We could invent a new operator, but that would be a bit much. Could these be simply `multiply` and `divide`, and we'll permit the `DoubleWidth` parameter/return type to explain itself?

I'm also thinking the second parameter should be labeled `by`, since that's the way people talk about these operations. Applying both of these suggestions, we'd get:

  static func multiply(_ lhs: Self, by rhs: Self) -> DoubleWidth<Self>
  static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) -> (quotient: Self, remainder: Self)

  let x = Int.multiply(a, by: b)
  let (aʹ, r) = Int.divide(x, by: b)
  assert(a == aʹ)
  assert(r == 0)

Should the standard library provide extensions automatic definitions of multiplication and division in terms of their double-width equivalents?

  extension FixedWidthInteger {
    func multipliedWithOverflow(by other: Self) -> (partialValue: Self, overflow: ArithmeticOverflow) {
      let doubledResult = Self.multiply(self, by: other)
      let overflowed = doubledResult.high != (doubledResult < 0 ? -1 : 0)
      return (Self(bitPattern: doubledResult.lowerValue), overflowed ? .overflowed : .none)
    }

    func quotientAndRemainder(dividingBy other: Self) -> (quotient: Self, remainder: Self) {
      precondition(other != 0, "Divide by zero")
      return Self.divide(DoubleWidth(self), by: other)
    }

    func dividedWithOverflow(by other: Self) -> (partialValue: Self, overflow: ArithmeticOverflow) {
      guard other != 0 else { return (self, .overflowed) }

      let result = Self.divide(self, by: other)
      return (result.quotient, .none)
    }

    static func * (lhs: Self, rhs: Self) -> Self {
      let result = lhs.dividedWithOverflow(by: rhs)
      precondition(result.overflow == .none, "Multiplication overflowed")
      return result.partialValue
    }

    static func / (lhs: Self, rhs: Self) -> Self {
      let result = lhs.quotientAndRemainder(dividingBy: rhs)
      return result.quotient
    }

    static func % (lhs: Self, rhs: Self) -> Self {
      let result = lhs.quotientAndRemainder(dividingBy: rhs)
      return result.remainder
    }
}

Hmm...having actually written this out, I now have a couple of concerns:

1. There's a lot of jumping back and forth between instance methods and static methods. Can we standardize on just static methods? Or make sure that the user-facing interfaces are all either operators or instance methods?

2. There is no quotient-and-remainder-with-overflow, either regular or double-width. Can we do that?

3. "Overflow" is not really a good description of what's happening in division; the value is undefined, not overflowing. Is there a better way to express this?

4. For that matter, even non-fixed-width division can "overflow"; should that concept be hoisted higher up the protocol hierarchy?

5. For *that* matter, should we simply make these operations throw instead of returning a flag?

  enum ArithmeticError<NumberType: Arithmetic>: Error {
    // Are generic errors permitted?
    case overflow(partialValue: NumberType)
    case undefined
  }

  // Should these throwing definitions be higher up so that, when working with `Arithmetic`
  // or similar types, you have an opportunity to handle errors instead of always trapping?
  protocol FixedWidthInteger: BinaryInteger {
    ...
    func adding(_ other: Self) throws -> Self
    func subtracting(_ other: Self) throws -> Self
    func multiplied(by other: Self) throws -> Self
    func divided(by other: Self) throws -> Self
    ...
  }

I'm *really* tempted to suggest adding throwing variants of the actual operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be too specialized to really justify that.

Having said that, there is a solution for doubleWidthMultiply, that I think is worth trying:

enum DoubleWidth<T> {
case .parts(high: T, low: T.Magnitude)

var high: T { switch self { case .parts(let high, _): return high } }
var low: T.Magnitude { switch self { case .parts(_, let low): return low } }
}

This way it will be possible to both do pattern-matching on the result of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low when needed.

This sounds like a good idea to me. (Unless we want to create a protocol for destructuring, but I assume that's out of scope.)

--
Brent Royal-Gordon
Architechies

David_Sweeris · January 15, 2017, 9:36am

+1

- Dave Sweeris

···

On Jan 15, 2017, at 03:20, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Given that Arithmetic also provides for multiplication and division, might it be wise then also to have .multiplicativeIdentity (or .one)?

On Sun, Jan 15, 2017 at 02:47 Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Sat Jan 14 2017, Dave Abrahams <swift-evolution@swift.org> wrote:

> That said, the ability to interpret integer literals as an arbitrary
> Arithmetic isn't used anywhere in the standard library, so I'd like to
> consider undoing
> Getting rid of Arithmetic.init() in favor of 0 · apple/swift@de5b03d · GitHub
> and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
> BinaryInteger.

Oh, and I meant to add: maybe the right way for an arbitrary X modeling
Arithmetic to spell zero (which is needed for negation) is something
like

   X.additiveIdentity

or

   X.zero

in other words, via a requirement

   static var theNameWeChoose: Self { get }

dabrahams · January 15, 2017, 2:41pm

Given that Arithmetic also provides for multiplication and division, might
it be wise then also to have .multiplicativeIdentity (or .one)?

I'm always wary of adding requirements that don't have a demonstrated
use-case in a generic algorithm. What generic algorithm can use this
value?

···

on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

On Sun, Jan 15, 2017 at 02:47 Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sat Jan 14 2017, Dave Abrahams <swift-evolution@swift.org> wrote:

> That said, the ability to interpret integer literals as an arbitrary
> Arithmetic isn't used anywhere in the standard library, so I'd like to
> consider undoing
>
Getting rid of Arithmetic.init() in favor of 0 · apple/swift@de5b03d · GitHub
> and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
> BinaryInteger.

Oh, and I meant to add: maybe the right way for an arbitrary X modeling
Arithmetic to spell zero (which is needed for negation) is something
like

   X.additiveIdentity

or

   X.zero

in other words, via a requirement

   static var theNameWeChoose: Self { get }

--
-Dave

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

--
-Dave

jtbandes · January 15, 2017, 11:19pm

Eurgh. That's true. Appropriate mathematical terms go out the window when
"division" doesn't actually produce a multiplicative inverse.

BasicArithmetic?

···

On Sun, Jan 15, 2017 at 2:42 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Jan 15, 2017 at 3:29 PM, Jacob Bandes-Storch via swift-evolution < > swift-evolution@swift.org> wrote:

[ proposal link: https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f
3fcc7cad8c ]

On Sat, Jan 14, 2017 at 4:55 PM, Dave Abrahams via swift-evolution < >> swift-evolution@swift.org> wrote:

Responding to both Jacob and Xiaodi here; thanks very much for your
feedback!

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:
> I think, in the end, it's the _name_ that could use improvement here.
As
> the doc comments say, `Arithmetic` is supposed to provide a "suitable
basis
> for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
> appropriate? It would make it clear that `CGVector` is not meant to be
a
> conforming type.

We want Arithmetic to be able to handle complex numbers. Whether Scalar
would be appropriate in that case sort of depends on what the implied
field is, right?

I think "scalar" is an appropriate term for any field. The scalar-ness
usually comes into play when it's used in a vector space, but using the
term alone doesn't bother me.

It's true that CGPoint and CGVector have no obvious sensible
interpretation of "42", and that's unfortunate. The problem with
protocols for algebraic structures is that there's an incredibly
complicated lattice (see figures 3.1, 3.2 in
ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
shove all of those protocols into the standard library (especially not
prematurely) but each requirement you add to a more-coarsely aggregated
protocol like Arithmetic will make it ineligible for representing some
important type.

Yep, it is quite complicated, and I understand not wanting to address all
that right now; calling it ScalarArithmetic seems appropriate to clarify
the limitations. FieldArithmetic might also be appropriate, but is less
clear (+ see below about quaternions).

Daves Sweeris and Abrahams wrote:

> > I was under the impression that complex numbers are scalar numbers...
although maybe not since once you get past, I think quaternions, you start
losing division and eventually multiplication, IIRC. (I hate it when two of
my recollections try to conflict with each other.)
>
> Well, you can view them as 2d vectors, so I'm not sure. We need more
of a numerics expert than I am to weigh in here.

But complex numbers have multiplication and division operations defined
(they form a field), unlike regular vectors in R². Meaning you can have a
vector space over the field of complex numbers.

You still have multiplication and division past quaternions, but the
quaternions are *not commutative*. This isn't really a problem in Swift,
since the compiler never allows you to write an expression where the order
of arguments to an operator is ambiguous. This means they are *not a
field*, just a division ring
<https://en.wikipedia.org/wiki/Division_ring> (a field is a commutative
division ring). (I believe you can't technically have a vector space over a
non-commutative ring; the generalization would be a module
<https://en.wikipedia.org/wiki/Module_(mathematics)>\. That's
probably an argument for the name ScalarArithmetic over FieldArithmetic.)

Hmm, the issue is that the integers are not a field. So, if we're going to
have it all modeled by one protocol, maybe neither is the best term.

Anton_Zhilin · January 15, 2017, 12:37pm

What about taking a mathematical approach to numbers?

protocol Group : Equatable {
    static var zero: Self { get }
    static func + (Self, Self) -> Self
    static func += (inout Self, Self)
    static func - (Self, Self) -> Self
    static func -= (inout Self, Self)
    static prefix func - (Self) -> Self
}

protocol Ring : Group {
    static var one: Self { get }
    static func * (Self, Self) -> Self
    static func *= (inout Self, Self)
    func tryDivide(by: Self) -> Self?
    func tryInvert() -> Self?
}

protocol Field : Ring {
    static func / (Self, Self) -> Self
    static func /= (inout Self, Self)
    var inverted: Self { get }
}

protocol VectorSpace : Group {
    associatedtype Scalar : Field
    static func * (Self, Scalar) -> Self
    static func *= (inout Self, Scalar) -> Self
    static func / (Self, Scalar) -> Self
    static func /= (inout Self, Scalar) -> Self
    static func * (Scalar, Self) -> Self
}

Detalization of mathematical terminology will be determined by what kind of
types we have in the standard library. Integer types are rings (except for
overflow), floating-point types are fields (except for precision), point
types are linear spaces, so I thought the abstractions above are the bare
minimum.

Unfortunately, Swift doesn’t have rename operations for protocol
requirements, so we can’t express groups that use operations other than +
and -. What we can do is to include an adapter to wrap current instance in
an additive group interface:

struct MultiplicativeGroupAdapter<T: Field> : Group {
// ...
}

extension Field {
var multiplicativeGroup: MultiplicativeGroupAdapter<Self>
}

dabrahams · January 16, 2017, 1:16am

“Basic” adds nothing AFAICT, which is why the proposed name is
“Arithmetic”

···

on Sun Jan 15 2017, Jacob Bandes-Storch <jtbandes-AT-gmail.com> wrote:

On Sun, Jan 15, 2017 at 2:42 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Jan 15, 2017 at 3:29 PM, Jacob Bandes-Storch via swift-evolution < >> swift-evolution@swift.org> wrote:

[ proposal link: https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f
3fcc7cad8c ]

On Sat, Jan 14, 2017 at 4:55 PM, Dave Abrahams via swift-evolution < >>> swift-evolution@swift.org> wrote:

Responding to both Jacob and Xiaodi here; thanks very much for your
feedback!

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:
> I think, in the end, it's the _name_ that could use improvement here.
As
> the doc comments say, `Arithmetic` is supposed to provide a "suitable
basis
> for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
> appropriate? It would make it clear that `CGVector` is not meant to be
a
> conforming type.

We want Arithmetic to be able to handle complex numbers. Whether Scalar
would be appropriate in that case sort of depends on what the implied
field is, right?

I think "scalar" is an appropriate term for any field. The scalar-ness
usually comes into play when it's used in a vector space, but using the
term alone doesn't bother me.

It's true that CGPoint and CGVector have no obvious sensible
interpretation of "42", and that's unfortunate. The problem with
protocols for algebraic structures is that there's an incredibly
complicated lattice (see figures 3.1, 3.2 in
ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
shove all of those protocols into the standard library (especially not
prematurely) but each requirement you add to a more-coarsely aggregated
protocol like Arithmetic will make it ineligible for representing some
important type.

Yep, it is quite complicated, and I understand not wanting to address all
that right now; calling it ScalarArithmetic seems appropriate to clarify
the limitations. FieldArithmetic might also be appropriate, but is less
clear (+ see below about quaternions).

Daves Sweeris and Abrahams wrote:

> > I was under the impression that complex numbers are scalar numbers...
although maybe not since once you get past, I think quaternions, you start
losing division and eventually multiplication, IIRC. (I hate it when two of
my recollections try to conflict with each other.)
>
> Well, you can view them as 2d vectors, so I'm not sure. We need more
of a numerics expert than I am to weigh in here.

But complex numbers have multiplication and division operations defined
(they form a field), unlike regular vectors in R². Meaning you can have a
vector space over the field of complex numbers.

You still have multiplication and division past quaternions, but the
quaternions are *not commutative*. This isn't really a problem in Swift,
since the compiler never allows you to write an expression where the order
of arguments to an operator is ambiguous. This means they are *not a
field*, just a division ring
<https://en.wikipedia.org/wiki/Division_ring> (a field is a commutative
division ring). (I believe you can't technically have a vector space over a
non-commutative ring; the generalization would be a module
<https://en.wikipedia.org/wiki/Module_(mathematics)>\. That's
probably an argument for the name ScalarArithmetic over FieldArithmetic.)

Hmm, the issue is that the integers are not a field. So, if we're going to
have it all modeled by one protocol, maybe neither is the best term.

Eurgh. That's true. Appropriate mathematical terms go out the window when
"division" doesn't actually produce a multiplicative inverse.

BasicArithmetic?

--
-Dave

David_Sweeris · January 15, 2017, 11:54pm

I was thinking something similar... Could we just rename Int/UInt to Counter/UnsignedCounter, and leave all these "mathematically correct" protocols and types to mathematically correct numeric libraries?

- Dave Sweeris

···

On Jan 15, 2017, at 17:19, Jacob Bandes-Storch via swift-evolution <swift-evolution@swift.org> wrote:

On Sun, Jan 15, 2017 at 2:42 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Jan 15, 2017 at 3:29 PM, Jacob Bandes-Storch via swift-evolution <swift-evolution@swift.org> wrote:

[ proposal link: Protocol-oriented integers (take 2) · GitHub ]

On Sat, Jan 14, 2017 at 4:55 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

Responding to both Jacob and Xiaodi here; thanks very much for your
feedback!

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:
> I think, in the end, it's the _name_ that could use improvement here. As
> the doc comments say, `Arithmetic` is supposed to provide a "suitable basis
> for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
> appropriate? It would make it clear that `CGVector` is not meant to be a
> conforming type.

We want Arithmetic to be able to handle complex numbers. Whether Scalar
would be appropriate in that case sort of depends on what the implied
field is, right?

I think "scalar" is an appropriate term for any field. The scalar-ness usually comes into play when it's used in a vector space, but using the term alone doesn't bother me.

It's true that CGPoint and CGVector have no obvious sensible
interpretation of "42", and that's unfortunate. The problem with
protocols for algebraic structures is that there's an incredibly
complicated lattice (see figures 3.1, 3.2 in
ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
shove all of those protocols into the standard library (especially not
prematurely) but each requirement you add to a more-coarsely aggregated
protocol like Arithmetic will make it ineligible for representing some
important type.

Yep, it is quite complicated, and I understand not wanting to address all that right now; calling it ScalarArithmetic seems appropriate to clarify the limitations. FieldArithmetic might also be appropriate, but is less clear (+ see below about quaternions).

Daves Sweeris and Abrahams wrote:

> > I was under the impression that complex numbers are scalar numbers... although maybe not since once you get past, I think quaternions, you start losing division and eventually multiplication, IIRC. (I hate it when two of my recollections try to conflict with each other.)
>
> Well, you can view them as 2d vectors, so I'm not sure. We need more of a numerics expert than I am to weigh in here.

But complex numbers have multiplication and division operations defined (they form a field), unlike regular vectors in R². Meaning you can have a vector space over the field of complex numbers.

You still have multiplication and division past quaternions, but the quaternions are not commutative. This isn't really a problem in Swift, since the compiler never allows you to write an expression where the order of arguments to an operator is ambiguous. This means they are not a field, just a division ring (a field is a commutative division ring). (I believe you can't technically have a vector space over a non-commutative ring; the generalization would be a module. That's probably an argument for the name ScalarArithmetic over FieldArithmetic.)

Hmm, the issue is that the integers are not a field. So, if we're going to have it all modeled by one protocol, maybe neither is the best term.

Eurgh. That's true. Appropriate mathematical terms go out the window when "division" doesn't actually produce a multiplicative inverse.

BasicArithmetic?

xwu · January 15, 2017, 6:29pm

You're quite right. Since the multiplicative inverse of any integer other
than 1 and -1 is not itself an integer, there isn't much one can do...

···

On Sun, Jan 15, 2017 at 08:41 Dave Abrahams <dabrahams@apple.com> wrote:

on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

> Given that Arithmetic also provides for multiplication and division,
might

> it be wise then also to have .multiplicativeIdentity (or .one)?

I'm always wary of adding requirements that don't have a demonstrated

use-case in a generic algorithm. What generic algorithm can use this

value?

>

> On Sun, Jan 15, 2017 at 02:47 Dave Abrahams via swift-evolution < > > > swift-evolution@swift.org> wrote:

>

>>

>> on Sat Jan 14 2017, Dave Abrahams <swift-evolution@swift.org> wrote:

>>

>> > That said, the ability to interpret integer literals as an arbitrary

>> > Arithmetic isn't used anywhere in the standard library, so I'd like to

>> > consider undoing

>> >

>>
Getting rid of Arithmetic.init() in favor of 0 · apple/swift@de5b03d · GitHub

>> > and moving ExpressibleByIntegerLiteral down the protocol hierarchy to

>> > BinaryInteger.

>>

>> Oh, and I meant to add: maybe the right way for an arbitrary X modeling

>> Arithmetic to spell zero (which is needed for negation) is something

>> like

>>

>> X.additiveIdentity

>>

>> or

>>

>> X.zero

>>

>> in other words, via a requirement

>>

>> static var theNameWeChoose: Self { get }

>>

>> --

>> -Dave

>>

>> _______________________________________________

>> swift-evolution mailing list

>> swift-evolution@swift.org

>> https://lists.swift.org/mailman/listinfo/swift-evolution

>>

--

-Dave

dabrahams · January 30, 2017, 7:25pm

It might make a great deal of sense to support bitwise operations on
this type,

I think that's a model of SetAlgebra, then, isn't it?

Hmm, arguably. It's a shame that we won't be able to use it with
things like `OptionSet`, though.

Why not? That conforms to SetAlgebra.

I mean that `OptionSet.RawValue` currently has to conform to
`BitwiseOperations`,

Actually it doesn't. You just have to implement these yourself in that
case:

  extension OptionSet where Self.RawValue : BitwiseOperations {
    convenience init()
    mutating func formUnion(_ other: Self)
    mutating func formIntersection(_ other: Self)
    mutating func formSymmetricDifference(_ other: Self)
  }

but would now need to conform to `BinaryInteger` (or a sub-protocol).

Does that limit you in some useful way?

···

on Mon Jan 30 2017, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

On Jan 29, 2017, at 10:07 PM, Dave Abrahams <dabrahams@apple.com> wrote:

--
-Dave

moiseev · January 30, 2017, 7:39pm

It might make a great deal of sense to support bitwise operations on
this type,

I think that's a model of SetAlgebra, then, isn't it?

Hmm, arguably. It's a shame that we won't be able to use it with
things like `OptionSet`, though.

Why not? That conforms to SetAlgebra.

I mean that `OptionSet.RawValue` currently has to conform to `BitwiseOperations`, but would now need to conform to `BinaryInteger` (or a sub-protocol).

It is not a protocol requirement, just a way for the standard library to provide a default implementation.
BitwiseOperations was replaced by the FixedWidthInteger in the prototype for this case.

···

On Jan 30, 2017, at 12:21 AM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

On Jan 29, 2017, at 10:07 PM, Dave Abrahams <dabrahams@apple.com> wrote:

--
Brent Royal-Gordon
Architechies

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

Nevin · January 31, 2017, 12:16pm

…rather, the remainder will fit in width min(X, Y)

Nevin

···

On Tuesday, January 31, 2017, Nevin Brackett-Rozinsky < nevin.brackettrozinsky@gmail.com> wrote:

What, exactly, is the intended purpose of doubleWidthDivide?

I ask because, outside of degenerate cases, a quotient and remainder will
fit in the same size type as the operands.

So widthX / widthY will have quotient that fits in width X, and remainder
that fits in width Y.

In general, we cannot assume either one would be any smaller than that.

Nevin

On Monday, January 30, 2017, Brent Royal-Gordon via swift-evolution < > swift-evolution@swift.org > <javascript:_e(%7B%7D,'cvml','swift-evolution@swift.org');>> wrote:

> On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev@apple.com> wrote:
>
> doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
> 1. The components of it’s return type are not high and low, but are
quotient and remainder instead.
> 2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the
case for quotient and remainder.

You're right about the return value; for `doubleWidthDivide(_:_:)`, I was
thinking about changing the dividend. Specifically, I'm thinking we should
change these to:

        static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) ->
DoubleWidth<Self>
        static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs:
Self) -> (quotient: Self, remainder: Self)

I'm also thinking a little bit about spelling of these operations. I'd
*love* to be able to call them `*` and `/` and let the type system sort
things out, but that would cause problems, especially for multiply (since
the return value is the only thing different from a normal `*`). We could
invent a new operator, but that would be a bit much. Could these be simply
`multiply` and `divide`, and we'll permit the `DoubleWidth`
parameter/return type to explain itself?

I'm also thinking the second parameter should be labeled `by`, since
that's the way people talk about these operations. Applying both of these
suggestions, we'd get:

        static func multiply(_ lhs: Self, by rhs: Self) ->
DoubleWidth<Self>
        static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) ->
(quotient: Self, remainder: Self)

        let x = Int.multiply(a, by: b)
        let (aʹ, r) = Int.divide(x, by: b)
        assert(a == aʹ)
        assert(r == 0)

Should the standard library provide extensions automatic definitions of
multiplication and division in terms of their double-width equivalents?

        extension FixedWidthInteger {
                func multipliedWithOverflow(by other: Self) ->
(partialValue: Self, overflow: ArithmeticOverflow) {
                        let doubledResult = Self.multiply(self, by: other)
                        let overflowed = doubledResult.high !=
(doubledResult < 0 ? -1 : 0)
                        return (Self(bitPattern:
doubledResult.lowerValue), overflowed ? .overflowed : .none)
                }

                func quotientAndRemainder(dividingBy other: Self) ->
(quotient: Self, remainder: Self) {
                        precondition(other != 0, "Divide by zero")
                        return Self.divide(DoubleWidth(self), by: other)
                }

                func dividedWithOverflow(by other: Self) ->
(partialValue: Self, overflow: ArithmeticOverflow) {
                        guard other != 0 else { return (self,
.overflowed) }

                        let result = Self.divide(self, by: other)
                        return (result.quotient, .none)
                }

                static func * (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.dividedWithOverflow(by: rhs)
                        precondition(result.overflow == .none,
"Multiplication overflowed")
                        return result.partialValue
                }

                static func / (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.quotientAndRemainder(dividingBy:
rhs)
                        return result.quotient
                }

                static func % (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.quotientAndRemainder(dividingBy:
rhs)
                        return result.remainder
                }
}

Hmm...having actually written this out, I now have a couple of concerns:

1. There's a lot of jumping back and forth between instance methods and
static methods. Can we standardize on just static methods? Or make sure
that the user-facing interfaces are all either operators or instance
methods?

2. There is no quotient-and-remainder-with-overflow, either regular or
double-width. Can we do that?

3. "Overflow" is not really a good description of what's happening in
division; the value is undefined, not overflowing. Is there a better way to
express this?

4. For that matter, even non-fixed-width division can "overflow"; should
that concept be hoisted higher up the protocol hierarchy?

5. For *that* matter, should we simply make these operations throw
instead of returning a flag?

        enum ArithmeticError<NumberType: Arithmetic>: Error {
                // Are generic errors permitted?
                case overflow(partialValue: NumberType)
                case undefined
        }

        // Should these throwing definitions be higher up so that, when
working with `Arithmetic`
        // or similar types, you have an opportunity to handle errors
instead of always trapping?
        protocol FixedWidthInteger: BinaryInteger {
                ...
                func adding(_ other: Self) throws -> Self
                func subtracting(_ other: Self) throws -> Self
                func multiplied(by other: Self) throws -> Self
                func divided(by other: Self) throws -> Self
                ...
        }

I'm *really* tempted to suggest adding throwing variants of the actual
operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be
too specialized to really justify that.

> Having said that, there is a solution for doubleWidthMultiply, that I
think is worth trying:
>
> enum DoubleWidth<T> {
> case .parts(high: T, low: T.Magnitude)
>
> var high: T { switch self { case .parts(let high, _): return high } }
> var low: T.Magnitude { switch self { case .parts(_, let low): return
low } }
> }
>
> This way it will be possible to both do pattern-matching on the result
of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low
when needed.

This sounds like a good idea to me. (Unless we want to create a protocol
for destructuring, but I assume that's out of scope.)

--
Brent Royal-Gordon
Architechies

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

Stephen_Canon · January 31, 2017, 4:16pm

It’s

(a) the inverse operation of doubleWidthMultiply.
(b) an important building block for fast “small bignum arithmetic” (2-16 ish words). If you have this operation, it’s easy to build the divide that does DoubleWidth<T> / DoubleWidth<T>.
(c) the widest divide operation that maps reasonably cleanly to common hardware when T = Word.

– Steve

···

On Jan 31, 2017, at 6:59 AM, Nevin Brackett-Rozinsky via swift-evolution <swift-evolution@swift.org> wrote:

What, exactly, is the intended purpose of doubleWidthDivide?

I ask because, outside of degenerate cases, a quotient and remainder will fit in the same size type as the operands.

So widthX / widthY will have quotient that fits in width X, and remainder that fits in width Y.

In general, we cannot assume either one would be any smaller than that.

Nevin

On Monday, January 30, 2017, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
> On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev@apple.com <javascript:;>> wrote:
>
> doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
> 1. The components of it’s return type are not high and low, but are quotient and remainder instead.
> 2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the case for quotient and remainder.

You're right about the return value; for `doubleWidthDivide(_:_:)`, I was thinking about changing the dividend. Specifically, I'm thinking we should change these to:

        static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -> DoubleWidth<Self>
        static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs: Self) -> (quotient: Self, remainder: Self)

I'm also thinking a little bit about spelling of these operations. I'd *love* to be able to call them `*` and `/` and let the type system sort things out, but that would cause problems, especially for multiply (since the return value is the only thing different from a normal `*`). We could invent a new operator, but that would be a bit much. Could these be simply `multiply` and `divide`, and we'll permit the `DoubleWidth` parameter/return type to explain itself?

I'm also thinking the second parameter should be labeled `by`, since that's the way people talk about these operations. Applying both of these suggestions, we'd get:

        static func multiply(_ lhs: Self, by rhs: Self) -> DoubleWidth<Self>
        static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) -> (quotient: Self, remainder: Self)

        let x = Int.multiply(a, by: b)
        let (aʹ, r) = Int.divide(x, by: b)
        assert(a == aʹ)
        assert(r == 0)

Should the standard library provide extensions automatic definitions of multiplication and division in terms of their double-width equivalents?

        extension FixedWidthInteger {
                func multipliedWithOverflow(by other: Self) -> (partialValue: Self, overflow: ArithmeticOverflow) {
                        let doubledResult = Self.multiply(self, by: other)
                        let overflowed = doubledResult.high != (doubledResult < 0 ? -1 : 0)
                        return (Self(bitPattern: doubledResult.lowerValue), overflowed ? .overflowed : .none)
                }

                func quotientAndRemainder(dividingBy other: Self) -> (quotient: Self, remainder: Self) {
                        precondition(other != 0, "Divide by zero")
                        return Self.divide(DoubleWidth(self), by: other)
                }

                func dividedWithOverflow(by other: Self) -> (partialValue: Self, overflow: ArithmeticOverflow) {
                        guard other != 0 else { return (self, .overflowed) }

                        let result = Self.divide(self, by: other)
                        return (result.quotient, .none)
                }

                static func * (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.dividedWithOverflow(by: rhs)
                        precondition(result.overflow == .none, "Multiplication overflowed")
                        return result.partialValue
                }

                static func / (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.quotientAndRemainder(dividingBy: rhs)
                        return result.quotient
                }

                static func % (lhs: Self, rhs: Self) -> Self {
                        let result = lhs.quotientAndRemainder(dividingBy: rhs)
                        return result.remainder
                }
}

Hmm...having actually written this out, I now have a couple of concerns:

1. There's a lot of jumping back and forth between instance methods and static methods. Can we standardize on just static methods? Or make sure that the user-facing interfaces are all either operators or instance methods?

2. There is no quotient-and-remainder-with-overflow, either regular or double-width. Can we do that?

3. "Overflow" is not really a good description of what's happening in division; the value is undefined, not overflowing. Is there a better way to express this?

4. For that matter, even non-fixed-width division can "overflow"; should that concept be hoisted higher up the protocol hierarchy?

5. For *that* matter, should we simply make these operations throw instead of returning a flag?

        enum ArithmeticError<NumberType: Arithmetic>: Error {
                // Are generic errors permitted?
                case overflow(partialValue: NumberType)
                case undefined
        }

        // Should these throwing definitions be higher up so that, when working with `Arithmetic`
        // or similar types, you have an opportunity to handle errors instead of always trapping?
        protocol FixedWidthInteger: BinaryInteger {
                ...
                func adding(_ other: Self) throws -> Self
                func subtracting(_ other: Self) throws -> Self
                func multiplied(by other: Self) throws -> Self
                func divided(by other: Self) throws -> Self
                ...
        }

I'm *really* tempted to suggest adding throwing variants of the actual operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be too specialized to really justify that.

> Having said that, there is a solution for doubleWidthMultiply, that I think is worth trying:
>
> enum DoubleWidth<T> {
> case .parts(high: T, low: T.Magnitude)
>
> var high: T { switch self { case .parts(let high, _): return high } }
> var low: T.Magnitude { switch self { case .parts(_, let low): return low } }
> }
>
> This way it will be possible to both do pattern-matching on the result of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low when needed.

This sounds like a good idea to me. (Unless we want to create a protocol for destructuring, but I assume that's out of scope.)

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <javascript:;>
https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

jtbandes · January 31, 2017, 9:32pm

Cute. Reminds me of C++ STL's struct tags: http://en.cppreference.
com/w/cpp/utility/piecewise_construct_t
std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag, std::contiguous_iterator_tag - cppreference.com

···

On Tue, Jan 31, 2017 at 12:53 PM, Max Moiseev via swift-evolution < swift-evolution@swift.org> wrote:

Hi Brent,

Thanks a lot for your suggestions! After having discussed them with Dave,
we came up with the following design that I personally like a lot.

enum Overflowing { case .withOverflow }
enum FullWidth { case .fullWidth }

protocol FixedWidthInteger {
  func adding(_ other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func subtracting(_ other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func multiplied(by other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func divided(by other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)

  func multiplied(by other: Self, _: FullWidth) -> DoubleWidth<Self>
  func dividing(_ other: DoubleWidth<Self>, _: FullWidth) -> (quotient:
Self, remainder: Self)
}

Call sites would look like:

x.multiplied(by: y, .withOverflow) and x.multiplied(by: y, .fullWidth)

a little different for the division:

x.divided(by: y, .withOverflow) and y.dividing(x, .fullWidth)

Note the inverse-ness of `dividing`, but the lack of the argument label
makes it quite natural.

> 2. There is no quotient-and-remainder-with-overflow, either regular or
double-width. Can we do that?
What will the partialValue equivalent be in case of overflow in
overflowing quotient+remainder division?
>
> 3. "Overflow" is not really a good description of what's happening in
division; the value is undefined, not overflowing. Is there a better way to
express this?
Division by 0 is not overflowing, true, but Int.min / (-1) is.
>
> 4. For that matter, even non-fixed-width division can "overflow"; should
that concept be hoisted higher up the protocol hierarchy?
In my head, overflow is a notion related to fixed sized types. You simply
don’t have enough room to represent certain values. Following this line of
thought, binary integer is not bounded, and can grow at will. So
FixedWidthInteger looks like the right place for overflowing operations.
And if we decide to not consider division by 0 an overflow, the model seems
quite consistent.

> On Jan 30, 2017, at 7:55 PM, Brent Royal-Gordon <brent@architechies.com> > wrote:
>
>> On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev@apple.com> wrote:
>>
>> doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
>> 1. The components of it’s return type are not high and low, but are
quotient and remainder instead.
>> 2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the
case for quotient and remainder.
>
> You're right about the return value; for `doubleWidthDivide(_:_:)`, I
was thinking about changing the dividend. Specifically, I'm thinking we
should change these to:
>
> static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) ->
DoubleWidth<Self>
> static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs:
Self) -> (quotient: Self, remainder: Self)
>
> I'm also thinking a little bit about spelling of these operations. I'd
*love* to be able to call them `*` and `/` and let the type system sort
things out, but that would cause problems, especially for multiply (since
the return value is the only thing different from a normal `*`). We could
invent a new operator, but that would be a bit much. Could these be simply
`multiply` and `divide`, and we'll permit the `DoubleWidth`
parameter/return type to explain itself?
>
> I'm also thinking the second parameter should be labeled `by`, since
that's the way people talk about these operations. Applying both of these
suggestions, we'd get:
>
> static func multiply(_ lhs: Self, by rhs: Self) ->
DoubleWidth<Self>
> static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) ->
(quotient: Self, remainder: Self)
>
> let x = Int.multiply(a, by: b)
> let (aʹ, r) = Int.divide(x, by: b)
> assert(a == aʹ)
> assert(r == 0)
>
> Should the standard library provide extensions automatic definitions of
multiplication and division in terms of their double-width equivalents?
>
> extension FixedWidthInteger {
> func multipliedWithOverflow(by other: Self) ->
(partialValue: Self, overflow: ArithmeticOverflow) {
> let doubledResult = Self.multiply(self, by: other)
> let overflowed = doubledResult.high !=
(doubledResult < 0 ? -1 : 0)
> return (Self(bitPattern:
doubledResult.lowerValue), overflowed ? .overflowed : .none)
> }
>
> func quotientAndRemainder(dividingBy other: Self) ->
(quotient: Self, remainder: Self) {
> precondition(other != 0, "Divide by zero")
> return Self.divide(DoubleWidth(self), by: other)
> }
>
> func dividedWithOverflow(by other: Self) -> (partialValue:
Self, overflow: ArithmeticOverflow) {
> guard other != 0 else { return (self, .overflowed)
}
>
> let result = Self.divide(self, by: other)
> return (result.quotient, .none)
> }
>
> static func * (lhs: Self, rhs: Self) -> Self {
> let result = lhs.dividedWithOverflow(by: rhs)
> precondition(result.overflow == .none,
"Multiplication overflowed")
> return result.partialValue
> }
>
> static func / (lhs: Self, rhs: Self) -> Self {
> let result = lhs.quotientAndRemainder(dividingBy:
rhs)
> return result.quotient
> }
>
> static func % (lhs: Self, rhs: Self) -> Self {
> let result = lhs.quotientAndRemainder(dividingBy:
rhs)
> return result.remainder
> }
> }
>
> Hmm...having actually written this out, I now have a couple of concerns:
>
> 1. There's a lot of jumping back and forth between instance methods and
static methods. Can we standardize on just static methods? Or make sure
that the user-facing interfaces are all either operators or instance
methods?
>
> 2. There is no quotient-and-remainder-with-overflow, either regular or
double-width. Can we do that?
>
> 3. "Overflow" is not really a good description of what's happening in
division; the value is undefined, not overflowing. Is there a better way to
express this?
>
> 4. For that matter, even non-fixed-width division can "overflow"; should
that concept be hoisted higher up the protocol hierarchy?
>
> 5. For *that* matter, should we simply make these operations throw
instead of returning a flag?
>
> enum ArithmeticError<NumberType: Arithmetic>: Error {
> // Are generic errors permitted?
> case overflow(partialValue: NumberType)
> case undefined
> }
>
> // Should these throwing definitions be higher up so that, when
working with `Arithmetic`
> // or similar types, you have an opportunity to handle errors
instead of always trapping?
> protocol FixedWidthInteger: BinaryInteger {
> ...
> func adding(_ other: Self) throws -> Self
> func subtracting(_ other: Self) throws -> Self
> func multiplied(by other: Self) throws -> Self
> func divided(by other: Self) throws -> Self
> ...
> }
>
> I'm *really* tempted to suggest adding throwing variants of the actual
operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be
too specialized to really justify that.
>
>> Having said that, there is a solution for doubleWidthMultiply, that I
think is worth trying:
>>
>> enum DoubleWidth<T> {
>> case .parts(high: T, low: T.Magnitude)
>>
>> var high: T { switch self { case .parts(let high, _): return high } }
>> var low: T.Magnitude { switch self { case .parts(_, let low): return
low } }
>> }
>>
>> This way it will be possible to both do pattern-matching on the result
of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low
when needed.
>
> This sounds like a good idea to me. (Unless we want to create a protocol
for destructuring, but I assume that's out of scope.)
>
> --
> Brent Royal-Gordon
> Architechies
>

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

xwu · January 31, 2017, 10:26pm

Hi Brent,

Thanks a lot for your suggestions! After having discussed them with Dave,
we came up with the following design that I personally like a lot.

enum Overflowing { case .withOverflow }
enum FullWidth { case .fullWidth }

protocol FixedWidthInteger {
  func adding(_ other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func subtracting(_ other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func multiplied(by other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func divided(by other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)

  func multiplied(by other: Self, _: FullWidth) -> DoubleWidth<Self>
  func dividing(_ other: DoubleWidth<Self>, _: FullWidth) -> (quotient:
Self, remainder: Self)
}

Call sites would look like:

x.multiplied(by: y, .withOverflow) and x.multiplied(by: y, .fullWidth)

a little different for the division:

x.divided(by: y, .withOverflow) and y.dividing(x, .fullWidth)

Note the inverse-ness of `dividing`, but the lack of the argument label
makes it quite natural.

This is an improvement in many ways, I think. However `.fullWidth` vs.
`DoubleWidth` seems less than ideal. I get that you can't reuse
`DoubleWidth` for the single-case enum, but still.

Now that * and &* no longer used the `multiplied(by:)` spelling, is there a
reason not to take advantage of overloading on the return value for these
very specialized methods?

protocol FixedWidthInteger {
  typealias OverflowFlagging = (partialValue: Self, overflow:
ArithmeticOverflow)
  func multiplied(by other: Self) -> OverflowFlagging
  func multiplied(by other: Self) -> DoubleWidth<Self>
}

You'd then write `x.multiplied(by: y) as OverflowFlagging` and
`x.multiplied(by: y) as DoubleWidth`

With respect to `dividing` vs `divided`, IMO it'd be a tricky name,
especially for non-English speakers. The "ed/ing" rule has these suffixes
used pretty interchangeably to indicate a non-mutating operation, depending
on the vagaries of the English language, but we've never had an "ed" and an
"ing" used for completely different things on the same type, as far as I'm
aware. Why not move the `dividing` version to DoubleWidth, where it can be
a proper `divided(by:)`?

···

On Tue, Jan 31, 2017 at 2:53 PM, Max Moiseev <moiseev@apple.com> wrote:

2. There is no quotient-and-remainder-with-overflow, either regular or
double-width. Can we do that?
What will the partialValue equivalent be in case of overflow in
overflowing quotient+remainder division?
>
> 3. "Overflow" is not really a good description of what's happening in
division; the value is undefined, not overflowing. Is there a better way to
express this?
Division by 0 is not overflowing, true, but Int.min / (-1) is.
>
> 4. For that matter, even non-fixed-width division can "overflow"; should
that concept be hoisted higher up the protocol hierarchy?
In my head, overflow is a notion related to fixed sized types. You simply
don’t have enough room to represent certain values. Following this line of
thought, binary integer is not bounded, and can grow at will. So
FixedWidthInteger looks like the right place for overflowing operations.
And if we decide to not consider division by 0 an overflow, the model seems
quite consistent.

> On Jan 30, 2017, at 7:55 PM, Brent Royal-Gordon <brent@architechies.com> > wrote:
>
>> On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev@apple.com> wrote:
>>
>> doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
>> 1. The components of it’s return type are not high and low, but are
quotient and remainder instead.
>> 2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the
case for quotient and remainder.
>
> You're right about the return value; for `doubleWidthDivide(_:_:)`, I
was thinking about changing the dividend. Specifically, I'm thinking we
should change these to:
>
> static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) ->
DoubleWidth<Self>
> static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs:
Self) -> (quotient: Self, remainder: Self)
>
> I'm also thinking a little bit about spelling of these operations. I'd
*love* to be able to call them `*` and `/` and let the type system sort
things out, but that would cause problems, especially for multiply (since
the return value is the only thing different from a normal `*`). We could
invent a new operator, but that would be a bit much. Could these be simply
`multiply` and `divide`, and we'll permit the `DoubleWidth`
parameter/return type to explain itself?
>
> I'm also thinking the second parameter should be labeled `by`, since
that's the way people talk about these operations. Applying both of these
suggestions, we'd get:
>
> static func multiply(_ lhs: Self, by rhs: Self) ->
DoubleWidth<Self>
> static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) ->
(quotient: Self, remainder: Self)
>
> let x = Int.multiply(a, by: b)
> let (aʹ, r) = Int.divide(x, by: b)
> assert(a == aʹ)
> assert(r == 0)
>
> Should the standard library provide extensions automatic definitions of
multiplication and division in terms of their double-width equivalents?
>
> extension FixedWidthInteger {
> func multipliedWithOverflow(by other: Self) ->
(partialValue: Self, overflow: ArithmeticOverflow) {
> let doubledResult = Self.multiply(self, by: other)
> let overflowed = doubledResult.high !=
(doubledResult < 0 ? -1 : 0)
> return (Self(bitPattern:
doubledResult.lowerValue), overflowed ? .overflowed : .none)
> }
>
> func quotientAndRemainder(dividingBy other: Self) ->
(quotient: Self, remainder: Self) {
> precondition(other != 0, "Divide by zero")
> return Self.divide(DoubleWidth(self), by: other)
> }
>
> func dividedWithOverflow(by other: Self) -> (partialValue:
Self, overflow: ArithmeticOverflow) {
> guard other != 0 else { return (self, .overflowed)
}
>
> let result = Self.divide(self, by: other)
> return (result.quotient, .none)
> }
>
> static func * (lhs: Self, rhs: Self) -> Self {
> let result = lhs.dividedWithOverflow(by: rhs)
> precondition(result.overflow == .none,
"Multiplication overflowed")
> return result.partialValue
> }
>
> static func / (lhs: Self, rhs: Self) -> Self {
> let result = lhs.quotientAndRemainder(dividingBy:
rhs)
> return result.quotient
> }
>
> static func % (lhs: Self, rhs: Self) -> Self {
> let result = lhs.quotientAndRemainder(dividingBy:
rhs)
> return result.remainder
> }
> }
>
> Hmm...having actually written this out, I now have a couple of concerns:
>
> 1. There's a lot of jumping back and forth between instance methods and
static methods. Can we standardize on just static methods? Or make sure
that the user-facing interfaces are all either operators or instance
methods?
>
> 2. There is no quotient-and-remainder-with-overflow, either regular or
double-width. Can we do that?
>
> 3. "Overflow" is not really a good description of what's happening in
division; the value is undefined, not overflowing. Is there a better way to
express this?
>
> 4. For that matter, even non-fixed-width division can "overflow"; should
that concept be hoisted higher up the protocol hierarchy?
>
> 5. For *that* matter, should we simply make these operations throw
instead of returning a flag?
>
> enum ArithmeticError<NumberType: Arithmetic>: Error {
> // Are generic errors permitted?
> case overflow(partialValue: NumberType)
> case undefined
> }
>
> // Should these throwing definitions be higher up so that, when
working with `Arithmetic`
> // or similar types, you have an opportunity to handle errors
instead of always trapping?
> protocol FixedWidthInteger: BinaryInteger {
> ...
> func adding(_ other: Self) throws -> Self
> func subtracting(_ other: Self) throws -> Self
> func multiplied(by other: Self) throws -> Self
> func divided(by other: Self) throws -> Self
> ...
> }
>
> I'm *really* tempted to suggest adding throwing variants of the actual
operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be
too specialized to really justify that.
>
>> Having said that, there is a solution for doubleWidthMultiply, that I
think is worth trying:
>>
>> enum DoubleWidth<T> {
>> case .parts(high: T, low: T.Magnitude)
>>
>> var high: T { switch self { case .parts(let high, _): return high } }
>> var low: T.Magnitude { switch self { case .parts(_, let low): return
low } }
>> }
>>
>> This way it will be possible to both do pattern-matching on the result
of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low
when needed.
>
> This sounds like a good idea to me. (Unless we want to create a protocol
for destructuring, but I assume that's out of scope.)
>
> --
> Brent Royal-Gordon
> Architechies
>