Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

[Resending to list with original message removed for length.]

This is fantastic. Glad to see it take shape. Very neat and insightful to
have trailingZeros on BinaryInteger but leadingZeros on FixedWidthInteger.
A couple of questions on smart shifts: What is the performance penalty as
compared to the existing operators? Beyond performance, what are the
implications for migrating existing bit twiddling algorithms written in
Swift 3?
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Max Moiseev via swift-evolution]

Hi Xiaodi,

>  What is the performance penalty as compared to the existing operators?

First of all, I don’t have the concrete numbers unfortunately. But…
If we are talking about concrete types, there should be very little difference 
between the two smart and masking shifts.
For example, the following functions:

public func foo(x: UInt) -> UInt {
  return x >> 32
}

public func bar(x: UInt) -> UInt {
  return x &>> 32
}

Produce equivalent SIL and LLVM IR when compiled with optimizations. Moreover, 
if you change 32 to 100, then foo will become something like:

foo(x: UInt) { return 0 }

whereas bar will still call the llvm.shl.

> Beyond performance, what are the implications for migrating existing bit 
> twiddling algorithms written in Swift 3?
Let’s take for example the ‘&>>” operator. There are 2 overloads: &>>(Self, 
Self) and &>>(Self, Other)
(In Swift 3 there is only one version of >>, that takes both arguments of the 
same type.)

So, in an expression `x &>> 32`, compiler assumes 32 to have type Int (which is 
the default type for the integer literals) and prefer the heterogeneous 
overload. It might not be too bad, as I showed in examples above, but in order 
to increase chances of success you might want to specify an explicit type 
context, as in `x &>> (32 as TypeOfX)`.

As always, only concrete benchmarks will tell. We spent many hours optimizing 
the implementation for our existing benchmark suite.

Max

> On Jan 13, 2017, at 2:14 PM, Xiaodi Wu  wrote:
> 
> [Resending to list with original message removed for length.]
> 
> This is fantastic. Glad to see it take shape. Very neat and insightful to 
> have trailingZeros on BinaryInteger but leadingZeros on FixedWidthInteger. A 
> couple of questions on smart shifts: What is the performance penalty as 
> compared to the existing operators? Beyond performance, what are the 
> implications for migrating existing bit twiddling algorithms written in Swift 
> 3?
> 

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Stephen Canon via swift-evolution]

> On Jan 13, 2017, at 5:14 PM, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> [Resending to list with original message removed for length.]
> 
> This is fantastic. Glad to see it take shape. Very neat and insightful to 
> have trailingZeros on BinaryInteger but leadingZeros on FixedWidthInteger. A 
> couple of questions on smart shifts: What is the performance penalty as 
> compared to the existing operators? Beyond performance, what are the 
> implications for migrating existing bit twiddling algorithms written in Swift 
> 3?

Hi Xiaodi —

I don’t want to speak for Max and Dave, but I think I can provide some insight 
for your questions about shifts.

First, the overwhelming majority of shifts have a compile-time-constant RHS. 
For these cases, there’s no performance change (except that the smart shifts 
may be able to optimize away the entire expression if the shift is overlarge).

For smart shifts with non-constant right-hand sides, the compiler will 
frequently still be able to prove that the shift count is always positive or 
negative and less than word size (this handles a lot of the most common cases 
like normalizing an integer, reading from a bitstream, or shifting words of a 
bignum); again there’s no performance penalty.

In the remaining cases where the compiler cannot bound the right-hand side, 
there will be some branches present; there may be a few regressions from these 
cases, but I expect most to be small (and the code simplifications are well 
worth it).  Users can always use the masking shifts, which lower to single 
instructions for 32b and 64b integers types on Intel and arm64, and which are 
at worst an and and a shift (two very cheap instructions) on other 
architectures.

Basically, I expect there to be no perf impact for almost all code, and that 
the perf impact is relatively easily mitigated when it does occur. This is an 
easy tradeoff for fully-defined and sensible operator behavior.

– Steve
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

Thanks, that's very helpful. Yes, my question was more directed to those
situations that can't be optimized away. It's good to know that the maximum
total cost is an and and a shift, which is what it sounded like but wasn't
made explicit.
On Fri, Jan 13, 2017 at 17:25 Stephen Canon  wrote:

> > On Jan 13, 2017, at 5:14 PM, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
> >
> > [Resending to list with original message removed for length.]
> >
> > This is fantastic. Glad to see it take shape. Very neat and insightful
> to have trailingZeros on BinaryInteger but leadingZeros on
> FixedWidthInteger. A couple of questions on smart shifts: What is the
> performance penalty as compared to the existing operators? Beyond
> performance, what are the implications for migrating existing bit twiddling
> algorithms written in Swift 3?
>
> Hi Xiaodi —
>
> I don’t want to speak for Max and Dave, but I think I can provide some
> insight for your questions about shifts.
>
> First, the overwhelming majority of shifts have a compile-time-constant
> RHS. For these cases, there’s no performance change (except that the smart
> shifts may be able to optimize away the entire expression if the shift is
> overlarge).
>
> For smart shifts with non-constant right-hand sides, the compiler will
> frequently still be able to prove that the shift count is always positive
> or negative and less than word size (this handles a lot of the most common
> cases like normalizing an integer, reading from a bitstream, or shifting
> words of a bignum); again there’s no performance penalty.
>
> In the remaining cases where the compiler cannot bound the right-hand
> side, there will be some branches present; there may be a few regressions
> from these cases, but I expect most to be small (and the code
> simplifications are well worth it).  Users can always use the masking
> shifts, which lower to single instructions for 32b and 64b integers types
> on Intel and arm64, and which are at worst an and and a shift (two very
> cheap instructions) on other architectures.
>
> Basically, I expect there to be no perf impact for almost all code, and
> that the perf impact is relatively easily mitigated when it does occur.
> This is an easy tradeoff for fully-defined and sensible operator behavior.
>
> – Steve
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Jacob Bandes-Storch via swift-evolution]

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?(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(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
. I explored this a bit here:
https://gist.github.com/jtbandes/93eeb7d5eee8e1a7245387c660d
53b03#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...


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

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.

*... 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? Why should 11 get masked to 3 before the shift? (Also, it
might be a good idea to choose examples with numbers whose base-ten
representations don't look like valid binary. 😉) 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.

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

*... init(_ 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(_
source: T). Given the source of type T, how do you access its bits? Is
repeated use of word(at:) the recommended way? 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.size),
which is pretty ugly.


*## FixedWidthInteger*

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


*## Heterogenous shifts, equality, and comparison*

These look great. How will the default implementations be provided?
(Equivalent question: how would a user define their own heterogeneous
operators?) I suppose this works:

static func &>> (lhs: Self, rhs: Other) -> Self {
// delegate to the protocol requirement &>>(Self, Self)
return self &>> Self(extendingOrTruncating: rhs)
}

But for operations you can't delegate so easily... I'm imagining trying to
implement heterogeneous comparison (i.e. < ) and the best I can come up
with uses signum() and word(at:)...

Also, should these be protocol requirements so user-defined types can
specialize them?


*## Masking arithmetic*

Do &* and &+ and &- need their operands to have the same type, or could

Re: [swift-evolution] protocol-oriented integers (take 2)

[Rien via swift-evolution]

+1

Any change of including “ranged integers”?
I.e. an integer with a value that must fit in a predefined range?

Regards,
Rien

Site: http://balancingrock.nl
Blog: http://swiftrien.blogspot.com
Github: http://github.com/Swiftrien
Project: http://swiftfire.nl




> On 13 Jan 2017, at 21:47, Max Moiseev via swift-evolution 
>  wrote:
> 
> Hi everyone,
> 
> Back in June 2016 we discussed the new design of the integer types for the 
> standard library. It even resulted in acceptance of SE-0104 for Swift 3. 
> Unfortunately we were not able to implement it in time for the release.
> 
> But it was not forgotten, although, as time went by, a few changes needed to 
> be made in order to reflect the current state of the language.
> Without further introduction, please welcome the refined proposal to make 
> integers in Swift more suitable for generic programming.
> 
> Available in this gist 
> https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c and also 
> inlined below.
> 
> Max
> 
> Protocol-oriented integers (take 2)
> 
>   • Proposal: SE-
>   • Authors: Dave Abrahams, Maxim Moiseev
>   • Review Manager: TBD
>   • Status: Awaiting review
>   • Bug: SR-3196
>   • Previous Proposal: SE-0104
> Introduction
> 
> This proposal is an evolution of SE-0104. The goal is still to clean up 
> Swifts integer APIs and make them more useful for generic programming.
> 
> The language has evolved in ways that affect integers APIs since the time the 
> original proposal was approved for Swift 3. We also attempted to implement 
> the proposed model in the standard library and found that some essential APIs 
> were missing, whereas others could be safely removed.
> 
> Major changes to the APIs introduced by this proposal (as compared to 
> SE-0104) are listed in a dedicated section.
> 
> Motivation
> 
> Swift's integer protocols don't currently provide a suitable basis for 
> generic programming. See this blog post for an example of an attempt to 
> implement a generic algorithm over integers.
> 
> The way the Arithmetic protocol is defined, it does not generalize to 
> floating point numbers and also slows down compilation by requiring every 
> concrete type to provide an implementation of arithmetic operators, thus 
> polluting the overload set.
> 
> Converting from one integer type to another is performed using the concept of 
> the 'maximum width integer' (see MaxInt), which is an artificial limitation. 
> The very existence of MaxInt makes it unclear what to do should someone 
> implement Int256, for example.
> 
> Another annoying problem is the inability to use integers of different types 
> in comparison and bit-shift operations. For example, the following snippets 
> won't compile:
> 
> var x: Int8 = 42
> let y = 1
> let z = 0
> 
> 
> x 
> <<= y   // error: binary operator '<<=' cannot be applied to operands of type 
> 'Int8' and 'Int'
> if x > z { ... }  // error: binary operator '>' cannot be applied to operands 
> of type 'Int8' and 'Int'
> Currently, bit-shifting a negative number of (or too many) bits causes a trap 
> on some platforms, which makes low-level bit manipulations needlessly 
> dangerous and unpredictable.
> 
> Finally, the current design predates many of the improvements that came since 
> Swift 1, and hasn't been revised since then.
> 
> Proposed solution
> 
> We propose a new model that does not have above mentioned problems and is 
> more easily extensible.
> 
> +--+  +-+
> +-->+  Arithmetic  |  | Comparable  |
> |   |   (+,-,*,/)  |  | (==,<,>,...)|
> |   +-++  +---+-+
> | ^   ^
> +---++|   |
> |  SignedArithmetic  |  +-+---+---+
> | (unary -)  |  |BinaryInteger|
> +--+-+  |(words,%,bitwise,...)|
>^++---+-+--+
>| +---^   ^ ^---+
>| |   | |
> +--+-+++-+---+  +--++
> |  SignedInteger  ||  FixedWidthInteger  |  |  UnsignedInteger  |
> | ||(endianness,overflow,...)|  |   |
> +---+-++-++--+  +-+-+
> ^^^   ^
> |||   |
> |||   |
>+++-++-+---+-+
>|Int family |-+  |UInt family|-+
>+---+ |  +---+ |
>  +---++---+
> 
> There are several benefits provided by this model over the old one:
> 
>   • It allows mixing integer types in generic functions.
> 
> The possibility to initialize instan

Re: [swift-evolution] protocol-oriented integers (take 2)

[Benjamin Spratling via swift-evolution]

I notice the BinaryInteger's func word(at n: Int) -> UInt  function expects a 
2's complement representation.  Do you expect that "BigInt" will be implemented 
with 2's complement?  As a nonmutating function, I would think any 
implementation from a 1's complement big int would result in O(n^2) unless the 
BigInt were designed with scratch space where it could store the intermediate 
values of that representation.  I only ask because just last week I was 
designing an arbitrary-width float type in 1's complement, well, really I kept 
the sign bit in a separate Bool.  Of course, I recognize the value of being 
able to write integer init code from a 2's complement representation, I'm just 
curious if there's a way to allow this function to be more efficient for 
alternate representations.

I love that there's a DoubleWidth type, having coded some arbitrary precision 
arithmetic, that's always a downer going from generic code to having to pick a 
specific "big enough" result type.  

I'm glad the % operator got moved.  It really did stand out as not part of 
floating points.

Trailing zeros looks like a sensible optimization.

I agree with moving the shift operators, I like that you've called out the 
notion of an infinite shift.  I can't say I fully understood the use of the 
separate mask vs. smart shift operators, but I'll take another read in the next 
few days and see if I understand why they exist.

I know this PR does not address the BitInt implementation, but do you have one?

I'm glad to see this moving forward.

-Ben Spratling
Sent from my iPad

> On Jan 14, 2017, at 2:00 AM, Rien via swift-evolution 
>  wrote:
> 
> +1
> 
> Any change of including “ranged integers”?
> I.e. an integer with a value that must fit in a predefined range?
> 
> Regards,
> Rien
> 
> Site: http://balancingrock.nl
> Blog: http://swiftrien.blogspot.com
> Github: http://github.com/Swiftrien
> Project: http://swiftfire.nl
> 
> 
> 
> 
>> On 13 Jan 2017, at 21:47, Max Moiseev via swift-evolution 
>>  wrote:
>> 
>> Hi everyone,
>> 
>> Back in June 2016 we discussed the new design of the integer types for the 
>> standard library. It even resulted in acceptance of SE-0104 for Swift 3. 
>> Unfortunately we were not able to implement it in time for the release.
>> 
>> But it was not forgotten, although, as time went by, a few changes needed to 
>> be made in order to reflect the current state of the language.
>> Without further introduction, please welcome the refined proposal to make 
>> integers in Swift more suitable for generic programming.
>> 
>> Available in this gist 
>> https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c and also 
>> inlined below.
>> 
>> Max
>> 
>> Protocol-oriented integers (take 2)
>> 
>>• Proposal: SE-
>>• Authors: Dave Abrahams, Maxim Moiseev
>>• Review Manager: TBD
>>• Status: Awaiting review
>>• Bug: SR-3196
>>• Previous Proposal: SE-0104
>> Introduction
>> 
>> This proposal is an evolution of SE-0104. The goal is still to clean up 
>> Swifts integer APIs and make them more useful for generic programming.
>> 
>> The language has evolved in ways that affect integers APIs since the time 
>> the original proposal was approved for Swift 3. We also attempted to 
>> implement the proposed model in the standard library and found that some 
>> essential APIs were missing, whereas others could be safely removed.
>> 
>> Major changes to the APIs introduced by this proposal (as compared to 
>> SE-0104) are listed in a dedicated section.
>> 
>> Motivation
>> 
>> Swift's integer protocols don't currently provide a suitable basis for 
>> generic programming. See this blog post for an example of an attempt to 
>> implement a generic algorithm over integers.
>> 
>> The way the Arithmetic protocol is defined, it does not generalize to 
>> floating point numbers and also slows down compilation by requiring every 
>> concrete type to provide an implementation of arithmetic operators, thus 
>> polluting the overload set.
>> 
>> Converting from one integer type to another is performed using the concept 
>> of the 'maximum width integer' (see MaxInt), which is an artificial 
>> limitation. The very existence of MaxInt makes it unclear what to do should 
>> someone implement Int256, for example.
>> 
>> Another annoying problem is the inability to use integers of different types 
>> in comparison and bit-shift operations. For example, the following snippets 
>> won't compile:
>> 
>> var x: Int8 = 42
>> let y = 1
>> let z = 0
>> 
>> 
>> x 
>> <<= y   // error: binary operator '<<=' cannot be applied to operands of 
>> type 'Int8' and 'Int'
>> if x > z { ... }  // error: binary operator '>' cannot be applied to 
>> operands of type 'Int8' and 'Int'
>> Currently, bit-shifting a negative number of (or too many) bits causes a 
>> trap on some platforms, which makes low-level bit manipulations needlessly 
>> dangerous and unpredictable.
>> 
>> Finally, the current design predates many of the 

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

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

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


> *## 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)`.

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()`).

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Fri, Jan 13, 2017 at 7:51 PM, Xiaodi Wu  wrote:

> Thanks, that's very helpful. Yes, my question was more directed to those
> situations that can't be optimized away. It's good to know that the maximum
> total cost is an and and a shift, which is what it sounded like but wasn't
> made explicit.


Oy, I misread your reply; the maximum total cost for a _masking_ shift is
two very cheap instructions; the maximum total cost for a _smart_ shift is
potentially higher. I know it's unrealistic, but what will we be looking at
when it comes to this:

```
func foo() -> UInt32 {
return arc4random() >> arc4random()
}
```


On Fri, Jan 13, 2017 at 17:25 Stephen Canon  wrote:
>
>> > On Jan 13, 2017, at 5:14 PM, Xiaodi Wu via swift-evolution <
>> swift-evolution@swift.org> wrote:
>> >
>> > [Resending to list with original message removed for length.]
>> >
>> > This is fantastic. Glad to see it take shape. Very neat and insightful
>> to have trailingZeros on BinaryInteger but leadingZeros on
>> FixedWidthInteger. A couple of questions on smart shifts: What is the
>> performance penalty as compared to the existing operators? Beyond
>> performance, what are the implications for migrating existing bit twiddling
>> algorithms written in Swift 3?
>>
>> Hi Xiaodi —
>>
>> I don’t want to speak for Max and Dave, but I think I can provide some
>> insight for your questions about shifts.
>>
>> First, the overwhelming majority of shifts have a compile-time-constant
>> RHS. For these cases, there’s no performance change (except that the smart
>> shifts may be able to optimize away the entire expression if the shift is
>> overlarge).
>>
>> For smart shifts with non-constant right-hand sides, the compiler will
>> frequently still be able to prove that the shift count is always positive
>> or negative and less than word size (this handles a lot of the most common
>> cases like normalizing an integer, reading from a bitstream, or shifting
>> words of a bignum); again there’s no performance penalty.
>>
>> In the remaining cases where the compiler cannot bound the right-hand
>> side, there will be some branches present; there may be a few regressions
>> from these cases, but I expect most to be small (and the code
>> simplifications are well worth it).  Users can always use the masking
>> shifts, which lower to single instructions for 32b and 64b integers types
>> on Intel and arm64, and which are at worst an and and a shift (two very
>> cheap instructions) on other architectures.
>>
>> Basically, I expect there to be no perf impact for almost all code, and
>> that the perf impact is relatively easily mitigated when it does occur.
>> This is an easy tradeoff for fully-defined and sensible operator behavior.
>>
>> – Steve
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Stephen Canon via swift-evolution]

> On Jan 14, 2017, at 11:18 AM, Xiaodi Wu  wrote:
> 
> On Fri, Jan 13, 2017 at 7:51 PM, Xiaodi Wu  > wrote:
> Thanks, that's very helpful. Yes, my question was more directed to those 
> situations that can't be optimized away. It's good to know that the maximum 
> total cost is an and and a shift, which is what it sounded like but wasn't 
> made explicit.
> 
> Oy, I misread your reply; the maximum total cost for a _masking_ shift is two 
> very cheap instructions; the maximum total cost for a _smart_ shift is 
> potentially higher. I know it's unrealistic, but what will we be looking at 
> when it comes to this:
> 
> ```
> func foo() -> UInt32 {
> return arc4random() >> arc4random()
> }
> ```

This specific example generates a compare, shift, and conditional move of zero. 
Still very cheap (a branch would arguably be even better, since the result is 
almost always zero in this particular case).

If the RHS is not unsigned, so that it might also be negative, the very rare 
absolute worst case codegen for basic integer types should be something like 
[add, compare, negate, 2xshift, 2xselect].

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sat Jan 14 2017, Xiaodi Wu  wrote:

> On Fri, Jan 13, 2017 at 7:51 PM, Xiaodi Wu 
> wrote:
>
>> Thanks, that's very helpful. Yes, my question was more directed to those
>> situations that can't be optimized away. It's good to know that the maximum
>> total cost is an and and a shift, which is what it sounded like but wasn't
>> made explicit.
>
> Oy, I misread your reply; the maximum total cost for a _masking_ shift is
> two very cheap instructions; the maximum total cost for a _smart_ shift is
> potentially higher. I know it's unrealistic, but what will we be looking at
> when it comes to this:
>
> ```
> func foo() -> UInt32 {
> return arc4random() >> arc4random()
> }
> ```

This is a shift by an unsigned quantity, so we know it's positive.  It
should optimize down to something like this:

 let _lhs = arc4random(), _rhs = arc4random()
 return _rhs > 31 ? 0 : Builtin.shiftRight(_lhs, _rhs)

> On Fri, Jan 13, 2017 at 17:25 Stephen Canon  wrote:
>>
>>> > On Jan 13, 2017, at 5:14 PM, Xiaodi Wu via swift-evolution <
>>> swift-evolution@swift.org> wrote:
>>> >
>>> > [Resending to list with original message removed for length.]
>>> >
>>> > This is fantastic. Glad to see it take shape. Very neat and insightful
>>> to have trailingZeros on BinaryInteger but leadingZeros on
>>> FixedWidthInteger. A couple of questions on smart shifts: What is the
>>> performance penalty as compared to the existing operators? Beyond
>>> performance, what are the implications for migrating existing bit twiddling
>>> algorithms written in Swift 3?
>>>
>>> Hi Xiaodi —
>>>
>>> I don’t want to speak for Max and Dave, but I think I can provide some
>>> insight for your questions about shifts.
>>>
>>> First, the overwhelming majority of shifts have a compile-time-constant
>>> RHS. For these cases, there’s no performance change (except that the smart
>>> shifts may be able to optimize away the entire expression if the shift is
>>> overlarge).
>>>
>>> For smart shifts with non-constant right-hand sides, the compiler will
>>> frequently still be able to prove that the shift count is always positive
>>> or negative and less than word size (this handles a lot of the most common
>>> cases like normalizing an integer, reading from a bitstream, or shifting
>>> words of a bignum); again there’s no performance penalty.
>>>
>>> In the remaining cases where the compiler cannot bound the right-hand
>>> side, there will be some branches present; there may be a few regressions
>>> from these cases, but I expect most to be small (and the code
>>> simplifications are well worth it).  Users can always use the masking
>>> shifts, which lower to single instructions for 32b and 64b integers types
>>> on Intel and arm64, and which are at worst an and and a shift (two very
>>> cheap instructions) on other architectures.
>>>
>>> Basically, I expect there to be no perf impact for almost all code, and
>>> that the perf impact is relatively easily mitigated when it does occur.
>>> This is an easy tradeoff for fully-defined and sensible operator behavior.
>>>
>>> – Steve
>>
>>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Fri Jan 13 2017, Max Moiseev  wrote:

> So, in an expression `x &>> 32`, compiler assumes 32 to have type Int
> (which is the default type for the integer literals) and prefer the
> heterogeneous overload. It might not be too bad, as I showed in
> examples above, but in order to increase chances of success you might
> want to specify an explicit type context, as in `x &>> (32 as
> TypeOfX)`.

It's easy to prove that the heterogeneous overload can't have different
semantics from the homogeneous one, so there is absolutely nothing to
worry about—other than, arguably, that it could take slightly more
time to type-check.

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

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

on Sat Jan 14 2017, Xiaodi Wu  wrote:

> On Sat, Jan 14, 2017 at 1:32 AM, Jacob Bandes-Storch via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>> 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?(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(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
>> . 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?

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.  

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
https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15d5709eb2be069286c1
and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
BinaryInteger.

>> *## 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(extending:T) where T.isNarrowerThan(Self)
  init(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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sat Jan 14 2017, Benjamin Spratling  wrote:

> I notice the BinaryInteger's func word(at n: Int) -> UInt function
> expects a 2's complement representation.  Do you expect that "BigInt"
> will be implemented with 2's complement?  

Ah, this is an excellent question, excellently phrased!

We designed it so BigInt could use 2's complement (see
DoubleWidth, which works that way), which should be faster than
sign-magnitude...

BUT: I hadn't really considered that if existing bignum libraries use
sign-magnitude, we'll want to be able to efficiently use their
representations, so we need to make sure the protocols don't force those
representations to be inefficient.

> As a nonmutating function, I would think any implementation from a 1's
> complement big int would result in O(n^2) unless the BigInt were
> designed with scratch space where it could store the intermediate
> values of that representation.  

Oh... you mean that word(at:) itself would be linear, and thus
algorithms that iterate the words linearly would be O(N^2)...  yuck.

So far, the only algorithm we have using word(at:) is this one, and
https://github.com/apple/swift/blob/new-integer-protocols/stdlib/public/core/Integers.swift.gyb#L2191
presumably we could adapt it to sign-magnitude by expanding the
BinaryInteger protocol with a static var that indicates which
representation is used.

  enum Representation { 
twosComplement, signMagnitude, /*onesComplement?*/ 
  }
  static var representation: Representation { get }

Now, the other algorithms that I can anticipate would use word(at:) are
basically... the ones you'd have to implement to build BigInt, so I
guess this change would be OK.

Supporting sign-magnitude complicates generic programming with these
protocols, though, so I want to be really sure we need to do this before
we take the plunge.

> I only ask because just last week I was designing an arbitrary-width
> float type in 1's complement, well, really I kept the sign bit in a
> separate Bool.  

Sounds like sign-magnitude rather than 1's complement if I remember my
complements correctly.

> Of course, I recognize the value of being able to write integer init
> code from a 2's complement representation, I'm just curious if there's
> a way to allow this function to be more efficient for alternate
> representations.
>
> I love that there's a DoubleWidth type, having coded some arbitrary
> precision arithmetic, that's always a downer going from generic code
> to having to pick a specific "big enough" result type.
>
> I'm glad the % operator got moved.  It really did stand out as not
> part of floating points.
>
> Trailing zeros looks like a sensible optimization.
>
> I agree with moving the shift operators, I like that you've called out
> the notion of an infinite shift.  

I don't think we ever meant to say anything about infinite shifts!

> I can't say I fully understood the use of the separate mask vs. smart
> shift operators, but I'll take another read in the next few days and
> see if I understand why they exist.

You're not alone it appears.  We need to clarify that in the text,
obviously.  The smart shift operators are there to give you sensible
semantics without undefined behavior or traps in the cases that have
logically computable answers.  The masking shifts are there for
performance in the rare cases where smart shifting with a non-literal
shift amount introduces non-negligible overheads (testing and branching
to handle overshifts and negative shift amounts).  

Obviously you have to know that the masking behavior is benign in your
use case when using masking shifts in an operation.  I made the mistake
of using a masking shift to optimize some code the other day where the
shift amount could be equal to the full width of the value being
shifted.  I ended up widening the LHS before doing the shift and then
truncating back to the width, but that's only because I was writing
performance-critical code.  The smart shift would have “just worked.”

> I know this PR does not address the BitInt implementation, but do you
> have one?

I know someone that implemented one... using sign-magnitude, actually,
and his word(at:) implementation has the linear cost problem.  I'll ask
him to post a link.

>
>
> I'm glad to see this moving forward.
>
> -Ben Spratling
>
>> On Jan 14, 2017, at 2:00 AM, Rien via swift-evolution 
>>  wrote:
>> 
>> +1
>> 
>> Any change of including “ranged integers”?
>> I.e. an integer with a value that must fit in a predefined range?
>> 
>> Regards,
>> Rien
>> 
>> Site: http://balancingrock.nl
>> Blog: http://swiftrien.blogspot.com
>> Github: http://github.com/Swiftrien
>> Project: http://swiftfire.nl
>> 
>> 
>> 
>> 
>>> On 13 Jan 2017, at 21:47, Max Moiseev via swift-evolution 
>>>  wrote:
>>> 
>>> Hi everyone,
>>> 
>>> Back in June 2016 we discussed the new design of the integer types for the 
>>> standard library. It even resulted in acceptance of SE-0104 for Swift 3. 
>>> Unfortunately we were not able to implem

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Sun, Jan 15, 2017 at 2:00 AM, Nate Cook via swift-evolution <
swift-evolution@swift.org> wrote:

>
> Link: https://github.com/natecook1000/swift/blob/nc-
> bigint/test/Prototypes/BigInt.swift
>
> This is just a proof of concept BigInt implementation—there's not much in
> the way of optimization going on, and it's a little out of date. It does
> use sign-magnitude, so the word(at:) implementation is O(n) on each call
> due to this bit:
>
> https://github.com/natecook1000/swift/blob/nc-
> bigint/test/Prototypes/BigInt.swift#L571-L576
>
>
> The only other question I have from looking at this again is whether
> perhaps BinaryInteger should have a toString(radix:uppercase:) method,
> since arbitrary precision types may be able to optimize significantly for
> different bases. The prototype at the link doesn't do this, but a hex
> string (or any factor of 2 base?) should be far cheaper to generate than
> the general case that uses repeated division. Without that, a BigInt type
> doesn't have any way to customize the generic String(_:radix:uppercase:)
> initializer.
>

Oh yes, +1 to this idea. (Though for consistency it might be more aptly
named `description(radix:uppercase:)`.)

-Nate
>
>
> I'm glad to see this moving forward.
>
> -Ben Spratling
>
> On Jan 14, 2017, at 2:00 AM, Rien via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> +1
>
> Any change of including “ranged integers”?
> I.e. an integer with a value that must fit in a predefined range?
>
> Regards,
> Rien
>
> Site: http://balancingrock.nl
> Blog: http://swiftrien.blogspot.com
> Github: http://github.com/Swiftrien
> Project: http://swiftfire.nl
>
>
>
>
> On 13 Jan 2017, at 21:47, Max Moiseev via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Hi everyone,
>
> Back in June 2016 we discussed the new design of the integer types for the
> standard library. It even resulted in acceptance of SE-0104 for Swift 3.
> Unfortunately we were not able to implement it in time for the release.
>
> But it was not forgotten, although, as time went by, a few changes needed
> to be made in order to reflect the current state of the language.
> Without further introduction, please welcome the refined proposal to make
> integers in Swift more suitable for generic programming.
>
> Available in this gist https://gist.github.com/moiseev/
> 62ffe3c91b66866fdebf6f3fcc7cad8c and also inlined below.
>
> Max
>
> Protocol-oriented integers (take 2)
>
>   • Proposal: SE-
>   • Authors: Dave Abrahams, Maxim Moiseev
>   • Review Manager: TBD
>   • Status: Awaiting review
>   • Bug: SR-3196
>   • Previous Proposal: SE-0104
> Introduction
>
> This proposal is an evolution of SE-0104. The goal is still to clean up
> Swifts integer APIs and make them more useful for generic programming.
>
> The language has evolved in ways that affect integers APIs since the time
> the original proposal was approved for Swift 3. We also attempted to
> implement the proposed model in the standard library and found that some
> essential APIs were missing, whereas others could be safely removed.
>
> Major changes to the APIs introduced by this proposal (as compared to
> SE-0104) are listed in a dedicated section.
>
> Motivation
>
> Swift's integer protocols don't currently provide a suitable basis for
> generic programming. See this blog post for an example of an attempt to
> implement a generic algorithm over integers.
>
> The way the Arithmetic protocol is defined, it does not generalize to
> floating point numbers and also slows down compilation by requiring every
> concrete type to provide an implementation of arithmetic operators, thus
> polluting the overload set.
>
> Converting from one integer type to another is performed using the concept
> of the 'maximum width integer' (see MaxInt), which is an artificial
> limitation. The very existence of MaxInt makes it unclear what to do should
> someone implement Int256, for example.
>
> Another annoying problem is the inability to use integers of different
> types in comparison and bit-shift operations. For example, the following
> snippets won't compile:
>
> var x: Int8 = 42
> let y = 1
> let z = 0
>
>
> x
> <<= y   // error: binary operator '<<=' cannot be applied to operands of
> type 'Int8' and 'Int'
> if x > z { ... }  // error: binary operator '>' cannot be applied to
> operands of type 'Int8' and 'Int'
> Currently, bit-shifting a negative number of (or too many) bits causes a
> trap on some platforms, which makes low-level bit manipulations needlessly
> dangerous and unpredictable.
>
> Finally, the current design predates many of the improvements that came
> since Swift 1, and hasn't been revised since then.
>
> Proposed solution
>
> We propose a new model that does not have above mentioned problems and is
> more easily extensible.
>
>   +--+  +-+
>   +-->+  Arithmetic  |  | Comparable  |
>   |   |   (+,-,*,/)  |  | (==,<,>,...)|
>   |   +-++  +---+

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 15, 2017, at 03:20, Xiaodi Wu via swift-evolution 
>  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 
>>  wrote:
>> 
>> on Sat Jan 14 2017, Dave Abrahams  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
>> > https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15d5709eb2be069286c1
>> > 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 }

+1

- Dave Sweeris ___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 14, 2017, at 18:55, Dave Abrahams via swift-evolution 
>  wrote:
> 
> 
> Responding to both Jacob and Xiaodi here; thanks very much for your
> feedback!
> 
>> on Sat Jan 14 2017, Xiaodi Wu  wrote:
>> 
>> On Sat, Jan 14, 2017 at 1:32 AM, Jacob Bandes-Storch via swift-evolution <
>> swift-evolution@swift.org> wrote:
>> 
>>> 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?(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(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
>>> . 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... 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?


>>> *## 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
>> in

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sat Jan 14 2017, Dave Abrahams  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
> https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15d5709eb2be069286c1
> 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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Anton Zhilin via swift-evolution]

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 : Group {
// ...
}

extension Field {
var multiplicativeGroup: MultiplicativeGroupAdapter
}

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Nate Cook  wrote:

> Excited to see this getting closer!
>
>> On Jan 14, 2017, at 7:41 PM, Dave Abrahams via swift-evolution 
>>  wrote:
>> 
>> on Sat Jan 14 2017, Benjamin Spratling > > wrote:
>> 
>>> I notice the BinaryInteger's func word(at n: Int) -> UInt function
>>> expects a 2's complement representation.  Do you expect that "BigInt"
>>> will be implemented with 2's complement?  
>> 
>> Ah, this is an excellent question, excellently phrased!
>> 
>> We designed it so BigInt could use 2's complement (see
>> DoubleWidth, which works that way), which should be faster than
>> sign-magnitude...
>> 
>> BUT: I hadn't really considered that if existing bignum libraries use
>> sign-magnitude, we'll want to be able to efficiently use their
>> representations, so we need to make sure the protocols don't force those
>> representations to be inefficient.
>> 
>>> As a nonmutating function, I would think any implementation from a 1's
>>> complement big int would result in O(n^2) unless the BigInt were
>>> designed with scratch space where it could store the intermediate
>>> values of that representation.  
>> 
>> Oh... you mean that word(at:) itself would be linear, and thus
>> algorithms that iterate the words linearly would be O(N^2)...  yuck.
>> 
>> So far, the only algorithm we have using word(at:) is this one, and
>> https://github.com/apple/swift/blob/new-integer-protocols/stdlib/public/core/Integers.swift.gyb#L2191
>>  
>> 
>> presumably we could adapt it to sign-magnitude by expanding the
>> BinaryInteger protocol with a static var that indicates which
>> representation is used.
>> 
>>  enum Representation { 
>>twosComplement, signMagnitude, /*onesComplement?*/ 
>>  }
>>  static var representation: Representation { get }
>> 
>> Now, the other algorithms that I can anticipate would use word(at:) are
>> basically... the ones you'd have to implement to build BigInt, so I
>> guess this change would be OK.
>> 
>> Supporting sign-magnitude complicates generic programming with these
>> protocols, though, so I want to be really sure we need to do this before
>> we take the plunge.
>>
>>> I only ask because just last week I was designing an arbitrary-width
>>> float type in 1's complement, well, really I kept the sign bit in a
>>> separate Bool.  
>> 
>> Sounds like sign-magnitude rather than 1's complement if I remember my
>> complements correctly.
>> 
>>> Of course, I recognize the value of being able to write integer init
>>> code from a 2's complement representation, I'm just curious if there's
>>> a way to allow this function to be more efficient for alternate
>>> representations.
>>> 
>>> I love that there's a DoubleWidth type, having coded some arbitrary
>>> precision arithmetic, that's always a downer going from generic code
>>> to having to pick a specific "big enough" result type.
>>> 
>>> I'm glad the % operator got moved.  It really did stand out as not
>>> part of floating points.
>>> 
>>> Trailing zeros looks like a sensible optimization.
>>> 
>>> I agree with moving the shift operators, I like that you've called out
>>> the notion of an infinite shift.  
>> 
>> I don't think we ever meant to say anything about infinite shifts!
>> 
>>> I can't say I fully understood the use of the separate mask vs. smart
>>> shift operators, but I'll take another read in the next few days and
>>> see if I understand why they exist.
>> 
>> You're not alone it appears.  We need to clarify that in the text,
>> obviously.  The smart shift operators are there to give you sensible
>> semantics without undefined behavior or traps in the cases that have
>> logically computable answers.  The masking shifts are there for
>> performance in the rare cases where smart shifting with a non-literal
>> shift amount introduces non-negligible overheads (testing and branching
>> to handle overshifts and negative shift amounts).  
>> 
>> Obviously you have to know that the masking behavior is benign in your
>> use case when using masking shifts in an operation.  I made the mistake
>> of using a masking shift to optimize some code the other day where the
>> shift amount could be equal to the full width of the value being
>> shifted.  I ended up widening the LHS before doing the shift and then
>> truncating back to the width, but that's only because I was writing
>> performance-critical code.  The smart shift would have “just worked.”
>> 
>>> I know this PR does not address the BitInt implementation, but do you
>>> have one?
>> 
>> I know someone that implemented one... using sign-magnitude, actually,
>> and his word(at:) implementation has the linear cost problem.  I'll ask
>> him to post a link.
>
> Link: 
> https://github.com/natecook1000/swift/blob/nc-bigint/test/Prototypes/BigInt.swift
>
> This is just a proof of concept BigInt implementation—there's not much
> in the way of op

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Xiaodi Wu  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  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
>> >
>> https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15d5709eb2be069286c1
>> > 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
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, David Sweeris  wrote:

>> On Jan 14, 2017, at 18:55, Dave Abrahams via swift-evolution 
>>  wrote:
>> 
>> 
>> Responding to both Jacob and Xiaodi here; thanks very much for your
>> feedback!
>
>> 
>>> on Sat Jan 14 2017, Xiaodi Wu  wrote:
>>> 
>>> On Sat, Jan 14, 2017 at 1:32 AM, Jacob Bandes-Storch via swift-evolution <
>>> swift-evolution@swift.org> wrote:
>>> 
 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?(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(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
 . 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 one

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Anton Zhilin  wrote:

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

The first test for the inclusion of any protocol in the standard library
is: “what generic algorithm that uses this protocol as a constraint
would be appropriate for inclusion in the standard library?”

I don't think we have a use for any of the above directly in the
standard library.  All the generic algorithms I know of that would be
appropriate to those protocols are part of some specialized domain that
should have its own library built on top of the Swift standard lib.

> 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 : Group {
> // ...
> }
>
> extension Field {
> var multiplicativeGroup: MultiplicativeGroupAdapter
> }
>
> ​
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Rob Mayoff via swift-evolution]

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

> Oh... you mean that word(at:) itself would be linear, and thus
> algorithms that iterate the words linearly would be O(N^2)...  yuck.
>

Couldn't you fix this by replacing `func word(at n: Int) -> UInt` with `var
words: Sequence`, producing the words from least to most significant?
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Rob Mayoff  wrote:

> On Sat, Jan 14, 2017 at 7:41 PM, Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>> Oh... you mean that word(at:) itself would be linear, and thus
>> algorithms that iterate the words linearly would be O(N^2)...  yuck.
>>
>
> Couldn't you fix this by replacing `func word(at n: Int) -> UInt` with `var
> words: Sequence`, producing the words from least to most significant?


Yeah... I thought about that...

Since Sequence isn't actually a valid type and the words are
multipass, it would actually be either

  // probably too inefficient
  var words: AnyCollection {get} 

or 

  // a bit more complexity than I'd like to have for this purpose
  associatedtype Words : Collection /*where Iterator.Element == UInt*/
  var words: Words {get}

The one algorithm we currently have that uses words generically is
iterating them in reverse order, but I think that's easily
solvable.

Slightly more concerning is that word(at:) was designed so that
algorithms could index beyond countRepresentedWords and get a
mathematically correct answer.  So we'd need to either:

  1. give that up - not a bad choice considering that it currently
 forces a branch into word(at:) that will (probably?) never be used
 if the algorithm is written in the most efficient possible way

  2. keep countRepresentedWords and make words an infinite collection

I guess I'm leaning towards #1.  Exchanging
countRepresentedWords/word(at:) for Words/words is almost an even trade
in overall complexity.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

There _may_ be value in recognizing the distinction between rings and
fields, perhaps? Just as the FP protocols make room for people to implement
their own decimal FP types, and just as you're trying to make Arithmetic
accommodate complex numbers, the distinction would allow someone to write
algorithms generic over rationals and reals (i.e. fields). Being able to
represent exact fractions isn't so terribly niche, and I think the design
wouldn't be terribly complicated by its accommodation:

```
// rename Arithmetic to Ring
// it's acceptable to omit `.one` from Ring, though some may call that a
Pseudoring
// consider omitting division from Ring and pushing it down to
BinaryInteger and Field

protocol BinaryInteger : Ring { ... }

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

protocol FloatingPoint : Field { ... }
// rational number types and complex number types
// would also conform to Field
```


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



on Sun Jan 15 2017, Anton Zhilin  wrote:



> 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

> }



The first test for the inclusion of any protocol in the standard library

is: “what generic algorithm that uses this protocol as a constraint

would be appropriate for inclusion in the standard library?”



I don't think we have a use for any of the above directly in the

standard library.  All the generic algorithms I know of that would be

appropriate to those protocols are part of some specialized domain that

should have its own library built on top of the Swift standard lib.



> 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 : Group {

> // ...

> }

>

> extension Field {

> var multiplicativeGroup: MultiplicativeGroupAdapter

> }

>

> ​

> ___

> swift-evolution mailing list

> swift-evolution@swift.org

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

>



--

-Dave



___

swift-evolution mailing list

swift-evolution@swift.org

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

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

>
>
> on Sun Jan 15 2017, Xiaodi Wu  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  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
>
> >> >
>
> >>
> https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15d5709eb2be069286c1
>
> >> > 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
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Jacob Bandes-Storch via swift-evolution]

[ proposal link: https://gist.github.com/moiseev/
62ffe3c91b66866fdebf6f3fcc7cad8c ]


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

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
> https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15
> 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(extending:T) where T.isNarrowerThan(Self)
>   init(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 de

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Xiaodi Wu  wrote:

> There _may_ be value in recognizing the distinction between rings and
> fields, perhaps? Just as the FP protocols make room for people to implement
> their own decimal FP types, and just as you're trying to make Arithmetic
> accommodate complex numbers, the distinction would allow someone to write
> algorithms generic over rationals and reals (i.e. fields). Being able to
> represent exact fractions isn't so terribly niche, and I think the design
> wouldn't be terribly complicated by its accommodation:
>
> ```
> // rename Arithmetic to Ring
> // it's acceptable to omit `.one` from Ring, though some may call that a
> Pseudoring
> // consider omitting division from Ring and pushing it down to
> BinaryInteger and Field
>
> protocol BinaryInteger : Ring { ... }
>
> protocol Field : Ring {
>   static var one { get }
>   static func / (Self, Self) -> Self
>   static func /= (inout Self, Self)
>   var inverted: Self { get } // default impl: .one / self
> }
>
> protocol FloatingPoint : Field { ... }
> // rational number types and complex number types
> // would also conform to Field
> ```

What generic algorithms would this enable?  Would they be appropriate
for the standard library (as opposed to some more specialized numerics
library)?

> On Sun, Jan 15, 2017 at 09:14 Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> on Sun Jan 15 2017, Anton Zhilin  wrote:
>
>> 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
>
>> }
>
> The first test for the inclusion of any protocol in the standard library
>
> is: “what generic algorithm that uses this protocol as a constraint
>
> would be appropriate for inclusion in the standard library?”
>
> I don't think we have a use for any of the above directly in the
>
> standard library.  All the generic algorithms I know of that would be
>
> appropriate to those protocols are part of some specialized domain that
>
> should have its own library built on top of the Swift standard lib.
>
>> 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 : Group {
>
>> // ...
>
>> }
>
>>
>
>> extension Field {
>
>> var multiplicativeGroup: MultiplicativeGroupAdapter
>
>> }
>
>>
>
>> ​
>
>> ___
>
>> swift-evolution mailing list
>
>> swift-evolution@swift.org
>
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>>
>
> --
>
> -Dave
>
> ___
>
> swift-evolution mailing list
>
> swift-evolution@swift.org
>
> https://lists.swift.org/mailman/listinfo/swift-evolution
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

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

>
> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>
> > There _may_ be value in recognizing the distinction between rings and
> > fields, perhaps? Just as the FP protocols make room for people to
> implement
> > their own decimal FP types, and just as you're trying to make Arithmetic
> > accommodate complex numbers, the distinction would allow someone to write
> > algorithms generic over rationals and reals (i.e. fields). Being able to
> > represent exact fractions isn't so terribly niche, and I think the design
> > wouldn't be terribly complicated by its accommodation:
> >
> > ```
> > // rename Arithmetic to Ring
> > // it's acceptable to omit `.one` from Ring, though some may call that a
> > Pseudoring
> > // consider omitting division from Ring and pushing it down to
> > BinaryInteger and Field
> >
> > protocol BinaryInteger : Ring { ... }
> >
> > protocol Field : Ring {
> >   static var one { get }
> >   static func / (Self, Self) -> Self
> >   static func /= (inout Self, Self)
> >   var inverted: Self { get } // default impl: .one / self
> > }
> >
> > protocol FloatingPoint : Field { ... }
> > // rational number types and complex number types
> > // would also conform to Field
> > ```
>
> What generic algorithms would this enable?


For one, anything to do with dividing into equal parts could be generic
over floating point, rational, and even complex numbers, but you probably
wouldn't want to include integer types in such an algorithm.


> Would they be appropriate
> for the standard library (as opposed to some more specialized numerics
> library)?
>

The issue is that it's not terribly ergonomic to relegate `Field` to a
specialized library because one cannot retroactively conform
`FloatingPoint` to `Field`.

> On Sun, Jan 15, 2017 at 09:14 Dave Abrahams via swift-evolution <
> > swift-evolution@swift.org> wrote:
> >
> > on Sun Jan 15 2017, Anton Zhilin  wrote:
> >
> >> 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
> >
> >> }
> >
> > The first test for the inclusion of any protocol in the standard library
> >
> > is: “what generic algorithm that uses this protocol as a constraint
> >
> > would be appropriate for inclusion in the standard library?”
> >
> > I don't think we have a use for any of the above directly in the
> >
> > standard library.  All the generic algorithms I know of that would be
> >
> > appropriate to those protocols are part of some specialized domain that
> >
> > should have its own library built on top of the Swift standard lib.
> >
> >> 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 : Group {
> >
> >> // ...
> >
> >> }
> >
> >>
> >
> >> extension Field {
> >
> >> var multiplicativeGroup: MultiplicativeGroupAdapter
> >
> >> }
> >
> >>
> >
> >> ​
> >
> >> ___
> >
> >> swift-evolution mailing list
> >
> >> swift-evolution@swift.org
> >
> >> https://lists.swift.org/mailman/listinfo/swift-evolution
> >
> >>
> >
> > --
> >
> > -Dave
> >
> > ___
> >
> > swift-evolution mailing list
> >
> > swift-evolution@swift.org
> >

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

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


> 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
>> https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15
>> 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 ju

Re: [swift-evolution] protocol-oriented integers (take 2)

[Jacob Bandes-Storch via swift-evolution]

On Sun, Jan 15, 2017 at 2:42 PM, Xiaodi Wu  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  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?
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 15, 2017, at 17:19, Jacob Bandes-Storch via swift-evolution 
>  wrote:
> 
> 
>> On Sun, Jan 15, 2017 at 2:42 PM, Xiaodi Wu  wrote:
>>> On Sun, Jan 15, 2017 at 3:29 PM, Jacob Bandes-Storch via swift-evolution 
>>>  wrote:
>> 
>>> [ proposal link: 
>>> https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c ]
>>> 
>>> 
 On Sat, Jan 14, 2017 at 4:55 PM, Dave Abrahams via swift-evolution 
  wrote:
 
 Responding to both Jacob and Xiaodi here; thanks very much for your
 feedback!
 
 on Sat Jan 14 2017, Xiaodi Wu  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?

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

"Mathematically correct" integers behave just like Int in that there is not
a multiplicative inverse. What we're trying to do here is to determine how
much of what we know about mathematics is usefully modeled in the standard
library. The answer is not zero, because there is more than just counting
that people do with integers.


On Sun, Jan 15, 2017 at 17:54 David Sweeris  wrote:

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

Sent from my iPhone
> On Jan 15, 2017, at 18:02, Xiaodi Wu  wrote:
> 
> "Mathematically correct" integers behave just like Int in that there is not a 
> multiplicative inverse. What we're trying to do here is to determine how much 
> of what we know about mathematics is usefully modeled in the standard 
> library. The answer is not zero, because there is more than just counting 
> that people do with integers.

It's an interesting problem... When I was in school, "integer" division 
"returned" a "quotient and remainder", a "fraction" (which, occasionally, could 
be simplified to just an integer), or a "real". We never talked about division 
in the context of "(Int, Int) -> Int", though. OTOH, I never took any math 
classes past Differential Equations or Linear Algebra, either... I'm aware of 
areas of math where you formally restrict yourself to the kind of "(Int, Int) 
-> Int" operations we're doing here, but I don't really know much about it. Is 
division even well-defined in that context?

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Jacob Bandes-Storch  wrote:

> [ proposal link: https://gist.github.com/moiseev/
> 62ffe3c91b66866fdebf6f3fcc7cad8c ]
>
> 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  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. 

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
https://www2.clarku.edu/~djoyce/complex/mult.html 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  (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.)
>
> 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
>> https://github.com/apple/swift/commit/de5b03ddc41be9c5ca5e15
>> d5709eb2be069286c1
>> and moving ExpressibleByIntegerLiteral down the protocol hierarchy to
>> BinaryInteger.
>>
>
> +1
>
>>
>> >> *## BinaryInteger*
>> >>
>> >> I'm a little conf

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Sun, Jan 15, 2017 at 7:24 PM, Dave Abrahams  wrote:

>
> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>
> > On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris 
> wrote:
> >
> >>
> >>
> >>
> >>
> >> On Jan 15, 2017, at 18:02, Xiaodi Wu  wrote:
> >>
> >> "Mathematically correct" integers behave just like Int in that there is
> >> not a multiplicative inverse. What we're trying to do here is to
> determine
> >> how much of what we know about mathematics is usefully modeled in the
> >> standard library. The answer is not zero, because there is more than
> just
> >> counting that people do with integers.
> >>
> >>
> >> It's an interesting problem... When I was in school, "integer" division
> >> "returned" a "quotient and remainder", a "fraction" (which,
> occasionally,
> >> could be simplified to just an integer), or a "real". We never talked
> about
> >> division in the context of "(Int, Int) -> Int", though. OTOH, I never
> took
> >> any math classes past Differential Equations or Linear Algebra,
> either...
> >> I'm *aware* of areas of math where you formally restrict yourself to the
> >> kind of "(Int, Int) -> Int" operations we're doing here, but I don't
> >> really know much about it. Is division even well-defined in that
> context?
> >>
> >> - Dave Sweeris
> >>
> >
> > I'm no mathematician, and I'm not sure how to tackle the question of
> > "well-defined." Hopefully someone who is more knowledgable can chime in
> > here.
> >
> > But I'll have a go at replying to your point as it relates to the
> practical
> > issue here. Two Int values can be "divided" to produce another Int, and
> > that gives a predictable and well-understood result. It's an operation
> > that's always going to be there--first, because it'd be insane to remove
> it
> > since much working code relies on it, and second, because we're only
> > re-designing integer protocols and not the concrete types. However, it
> _is_
> > true that such an operation has very different semantics from division as
> > you learned it in math.
> >
> > This is why I'm advocating for perhaps another look at the top of this
> > integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
> > semantic guarantees for a lot of things, but `/` has different semantics
> > for integer types and floating point types
>
> Well, that really depends on how closely you look.  From one
> point-of-view, floating point division and integer division *both*
> produce approximate results.
>

Yes, from a certain point of view. I remember we did discuss this at one
point on the list; I asked whether FloatingPoint was meant to model only
the countable set of representable values or whether it was meant to model
the uncountable set of reals. The answer was that here in Swift-land we're
trying to model the latter, and the approximate result is an artifact of
the imperfect modeling. Integer division, however, is not such an artifact,
but fundamentally a different operation.


> > and is really closer to just syntax. Other mathematical types--which
> > certainly the stdlib doesn't have to offer, but the stdlib protocol
> > hierarchy shouldn't preclude their conformance to relevant protocols
> > if it's possible--such as fractions and complex numbers, share with
> > floating point types the semantics of `/` that qualify these types as
> > fields. Dave A's question as to practical uses can probably best be
> > answered in this way: to the extent that any generic algorithm relies
> > on `/` having semantics and can be applied to fractions and real
> > numbers, it would be useful to distinguish such an operation from
> > integer "division."
>
> That's not a bad answer.  Ruminating on this...
>
> --
> -Dave
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Xiaodi Wu  wrote:

> On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris  wrote:
>
>>
>>
>>
>> 
>> On Jan 15, 2017, at 18:02, Xiaodi Wu  wrote:
>>
>> "Mathematically correct" integers behave just like Int in that there is
>> not a multiplicative inverse. What we're trying to do here is to determine
>> how much of what we know about mathematics is usefully modeled in the
>> standard library. The answer is not zero, because there is more than just
>> counting that people do with integers.
>>
>>
>> It's an interesting problem... When I was in school, "integer" division
>> "returned" a "quotient and remainder", a "fraction" (which, occasionally,
>> could be simplified to just an integer), or a "real". We never talked about
>> division in the context of "(Int, Int) -> Int", though. OTOH, I never took
>> any math classes past Differential Equations or Linear Algebra, either...
>> I'm *aware* of areas of math where you formally restrict yourself to the
>> kind of "(Int, Int) -> Int" operations we're doing here, but I don't
>> really know much about it. Is division even well-defined in that context?
>>
>> - Dave Sweeris
>>
>
> I'm no mathematician, and I'm not sure how to tackle the question of
> "well-defined." Hopefully someone who is more knowledgable can chime in
> here.
>
> But I'll have a go at replying to your point as it relates to the practical
> issue here. Two Int values can be "divided" to produce another Int, and
> that gives a predictable and well-understood result. It's an operation
> that's always going to be there--first, because it'd be insane to remove it
> since much working code relies on it, and second, because we're only
> re-designing integer protocols and not the concrete types. However, it _is_
> true that such an operation has very different semantics from division as
> you learned it in math.
>
> This is why I'm advocating for perhaps another look at the top of this
> integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
> semantic guarantees for a lot of things, but `/` has different semantics
> for integer types and floating point types 

Well, that really depends on how closely you look.  From one
point-of-view, floating point division and integer division *both*
produce approximate results.

> and is really closer to just syntax. Other mathematical types--which
> certainly the stdlib doesn't have to offer, but the stdlib protocol
> hierarchy shouldn't preclude their conformance to relevant protocols
> if it's possible--such as fractions and complex numbers, share with
> floating point types the semantics of `/` that qualify these types as
> fields. Dave A's question as to practical uses can probably best be
> answered in this way: to the extent that any generic algorithm relies
> on `/` having semantics and can be applied to fractions and real
> numbers, it would be useful to distinguish such an operation from
> integer "division."

That's not a bad answer.  Ruminating on this...

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Jacob Bandes-Storch  wrote:

> On Sun, Jan 15, 2017 at 2:42 PM, Xiaodi Wu  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  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?

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

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris  wrote:

>
>
>
> Sent from my iPhone
> On Jan 15, 2017, at 18:02, Xiaodi Wu  wrote:
>
> "Mathematically correct" integers behave just like Int in that there is
> not a multiplicative inverse. What we're trying to do here is to determine
> how much of what we know about mathematics is usefully modeled in the
> standard library. The answer is not zero, because there is more than just
> counting that people do with integers.
>
>
> It's an interesting problem... When I was in school, "integer" division
> "returned" a "quotient and remainder", a "fraction" (which, occasionally,
> could be simplified to just an integer), or a "real". We never talked about
> division in the context of "(Int, Int) -> Int", though. OTOH, I never took
> any math classes past Differential Equations or Linear Algebra, either...
> I'm *aware* of areas of math where you formally restrict yourself to the
> kind of "(Int, Int) -> Int" operations we're doing here, but I don't
> really know much about it. Is division even well-defined in that context?
>
> - Dave Sweeris
>

I'm no mathematician, and I'm not sure how to tackle the question of
"well-defined." Hopefully someone who is more knowledgable can chime in
here.

But I'll have a go at replying to your point as it relates to the practical
issue here. Two Int values can be "divided" to produce another Int, and
that gives a predictable and well-understood result. It's an operation
that's always going to be there--first, because it'd be insane to remove it
since much working code relies on it, and second, because we're only
re-designing integer protocols and not the concrete types. However, it _is_
true that such an operation has very different semantics from division as
you learned it in math.

This is why I'm advocating for perhaps another look at the top of this
integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
semantic guarantees for a lot of things, but `/` has different semantics
for integer types and floating point types and is really closer to just
syntax. Other mathematical types--which certainly the stdlib doesn't have
to offer, but the stdlib protocol hierarchy shouldn't preclude their
conformance to relevant protocols if it's possible--such as fractions and
complex numbers, share with floating point types the semantics of `/` that
qualify these types as fields. Dave A's question as to practical uses can
probably best be answered in this way: to the extent that any generic
algorithm relies on `/` having semantics and can be applied to fractions
and real numbers, it would be useful to distinguish such an operation from
integer "division."
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Xiaodi Wu  wrote:

> On Sun, Jan 15, 2017 at 3:27 PM, Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>>
>> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>>
>> > There _may_ be value in recognizing the distinction between rings and
>> > fields, perhaps? Just as the FP protocols make room for people to
>> implement
>> > their own decimal FP types, and just as you're trying to make Arithmetic
>> > accommodate complex numbers, the distinction would allow someone to write
>> > algorithms generic over rationals and reals (i.e. fields). Being able to
>> > represent exact fractions isn't so terribly niche, and I think the design
>> > wouldn't be terribly complicated by its accommodation:
>> >
>> > ```
>> > // rename Arithmetic to Ring
>> > // it's acceptable to omit `.one` from Ring, though some may call that a
>> > Pseudoring
>> > // consider omitting division from Ring and pushing it down to
>> > BinaryInteger and Field
>> >
>> > protocol BinaryInteger : Ring { ... }
>> >
>> > protocol Field : Ring {
>> >   static var one { get }
>> >   static func / (Self, Self) -> Self
>> >   static func /= (inout Self, Self)
>> >   var inverted: Self { get } // default impl: .one / self
>> > }
>> >
>> > protocol FloatingPoint : Field { ... }
>> > // rational number types and complex number types
>> > // would also conform to Field
>> > ```
>>
>> What generic algorithms would this enable?
>
> For one, anything to do with dividing into equal parts 

For example...?

> could be generic over floating point, rational, and even complex
> numbers, but you probably wouldn't want to include integer types in
> such an algorithm.
>
>> Would they be appropriate
>> for the standard library (as opposed to some more specialized numerics
>> library)?
>>
>
> The issue is that it's not terribly ergonomic to relegate `Field` to a
> specialized library because one cannot retroactively conform
> `FloatingPoint` to `Field`.

I don't think this is an important enough concern to justify adding
protocols to the standard library.  The number of types one has to
individually make conform to Field is probably going to remain small.

Show-me-the-mone^Walgorithms-ly y'rs,

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

One example: earlier, it was demonstrated that a genetic lerp would not
accommodate vector types. However, it _does_ work fine for any scalar (i.e.
field) type; however, with the currently proposed integer protocols, one
would constrain it to Arithmetic types, yet the algorithm would be bogus
for integers.


On Sun, Jan 15, 2017 at 19:21 Dave Abrahams  wrote:

>
>
> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>
>
>
> > On Sun, Jan 15, 2017 at 3:27 PM, Dave Abrahams via swift-evolution <
>
> > swift-evolution@swift.org> wrote:
>
> >
>
> >>
>
> >> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>
> >>
>
> >> > There _may_ be value in recognizing the distinction between rings and
>
> >> > fields, perhaps? Just as the FP protocols make room for people to
>
> >> implement
>
> >> > their own decimal FP types, and just as you're trying to make
> Arithmetic
>
> >> > accommodate complex numbers, the distinction would allow someone to
> write
>
> >> > algorithms generic over rationals and reals (i.e. fields). Being able
> to
>
> >> > represent exact fractions isn't so terribly niche, and I think the
> design
>
> >> > wouldn't be terribly complicated by its accommodation:
>
> >> >
>
> >> > ```
>
> >> > // rename Arithmetic to Ring
>
> >> > // it's acceptable to omit `.one` from Ring, though some may call
> that a
>
> >> > Pseudoring
>
> >> > // consider omitting division from Ring and pushing it down to
>
> >> > BinaryInteger and Field
>
> >> >
>
> >> > protocol BinaryInteger : Ring { ... }
>
> >> >
>
> >> > protocol Field : Ring {
>
> >> >   static var one { get }
>
> >> >   static func / (Self, Self) -> Self
>
> >> >   static func /= (inout Self, Self)
>
> >> >   var inverted: Self { get } // default impl: .one / self
>
> >> > }
>
> >> >
>
> >> > protocol FloatingPoint : Field { ... }
>
> >> > // rational number types and complex number types
>
> >> > // would also conform to Field
>
> >> > ```
>
> >>
>
> >> What generic algorithms would this enable?
>
> >
>
> > For one, anything to do with dividing into equal parts
>
>
>
> For example...?
>
>
>
> > could be generic over floating point, rational, and even complex
>
> > numbers, but you probably wouldn't want to include integer types in
>
> > such an algorithm.
>
> >
>
> >> Would they be appropriate
>
> >> for the standard library (as opposed to some more specialized numerics
>
> >> library)?
>
> >>
>
> >
>
> > The issue is that it's not terribly ergonomic to relegate `Field` to a
>
> > specialized library because one cannot retroactively conform
>
> > `FloatingPoint` to `Field`.
>
>
>
> I don't think this is an important enough concern to justify adding
>
> protocols to the standard library.  The number of types one has to
>
> individually make conform to Field is probably going to remain small.
>
>
>
> Show-me-the-mone^Walgorithms-ly y'rs,
>
>
>
> --
>
> -Dave
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 15, 2017, at 19:24, Dave Abrahams  wrote:
> 
> 
>> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>> 
>>> On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris  wrote:
>>> 
>>> 
>>> 
>>> 
>>> 
>>> On Jan 15, 2017, at 18:02, Xiaodi Wu  wrote:
>>> 
>>> "Mathematically correct" integers behave just like Int in that there is
>>> not a multiplicative inverse. What we're trying to do here is to determine
>>> how much of what we know about mathematics is usefully modeled in the
>>> standard library. The answer is not zero, because there is more than just
>>> counting that people do with integers.
>>> 
>>> 
>>> It's an interesting problem... When I was in school, "integer" division
>>> "returned" a "quotient and remainder", a "fraction" (which, occasionally,
>>> could be simplified to just an integer), or a "real". We never talked about
>>> division in the context of "(Int, Int) -> Int", though. OTOH, I never took
>>> any math classes past Differential Equations or Linear Algebra, either...
>>> I'm *aware* of areas of math where you formally restrict yourself to the
>>> kind of "(Int, Int) -> Int" operations we're doing here, but I don't
>>> really know much about it. Is division even well-defined in that context?
>>> 
>>> - Dave Sweeris
>>> 
>> 
>> I'm no mathematician, and I'm not sure how to tackle the question of
>> "well-defined." Hopefully someone who is more knowledgable can chime in
>> here.
>> 
>> But I'll have a go at replying to your point as it relates to the practical
>> issue here. Two Int values can be "divided" to produce another Int, and
>> that gives a predictable and well-understood result. It's an operation
>> that's always going to be there--first, because it'd be insane to remove it
>> since much working code relies on it, and second, because we're only
>> re-designing integer protocols and not the concrete types. However, it _is_
>> true that such an operation has very different semantics from division as
>> you learned it in math.
>> 
>> This is why I'm advocating for perhaps another look at the top of this
>> integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
>> semantic guarantees for a lot of things, but `/` has different semantics
>> for integer types and floating point types 
> 
> Well, that really depends on how closely you look.  From one
> point-of-view, floating point division and integer division *both*
> produce approximate results.

Yeah, but integer division tends to be so "approximate" that the answer can 
easily be useless without also calculating x%y. Floating point division will 
generally give you at least a few correct digits, won't it?

- Dave Sweeris
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Stephen Canon via swift-evolution]

Responding to the thread in general here, not so much any specific email:

“Arithmetic” at present is not a mathematically-precise concept, and it may be 
a mistake to make it be one[1]; it’s a mathematically-slightly-fuzzy “number” 
protocol. FWIW, if I had to pick a mathematical object to pin it to, I would 
make it a [non-commutative] ring, which give it:

addition, subtraction, multiplication, IntegerLiteralConvertible, and 
an inverse: T? property.

Note that this would make division go out the window, but we would *preserve* 
int literal convertible (because there’s a unique map from Z to any ring — Z is 
the initial object in the category of rings). I think that it’s quite important 
to keep that for writing generic code.

Vectors and points are not “numbery” in this sense, so they should not conform 
to this protocol, which is why it’s OK that multiplication and int literals 
don’t make sense for them. They’re property a vector space or module built over 
a scalar type.

I would be OK with moving division out of the Arithmetic protocol, as the 
division operator is fundamentally different for integers and floating-point, 
and you want to have separate left- and right- division for quaternions and 
matrices. I would be pretty strongly opposed to removing integer literals; they 
rightfully belong here.

I think the name “Arithmetic” is sound. It is deliberately *not* one of the 
standard mathematical abstractions, reserving those names for folks who want to 
build a precise lattice of algebraic objects. Vectors don’t belong in this 
protocol, though.

– Steve

[1] We don’t want to make a semester course in modern algebra a prerequisite to 
using Swift, as much as I would enjoy building a tower of formalism as a 
mathematician.
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Jacob Bandes-Storch via swift-evolution]

On Sun, Jan 15, 2017 at 6:13 PM, Xiaodi Wu via swift-evolution <
swift-evolution@swift.org> wrote:

> One example: earlier, it was demonstrated that a genetic lerp would not
> accommodate vector types. However, it _does_ work fine for any scalar (i.e.
> field) type; however, with the currently proposed integer protocols, one
> would constrain it to Arithmetic types, yet the algorithm would be bogus
> for integers.
>

I wouldn't say lerp is bogus (the results aren't wrong), just much
less useful.

On the other hand:

extension Collection where Iterator.Element: Arithmetic {
func mean() -> Iterator.Element {
return self.reduce(Iterator.Element(), +) /
Iterator.Element(count)  // assuming these initializers exist
}
}

Now [6, 7].mean() returns 6, and *that* I would call bogus.

Of course, there are some alternative ways to implement this which avoid
the issue:

- Implement it only for Iterator.Element: FloatingPoint.
- Implement it as mean() -> T, reducing by { $0 + T($1) }
or whatever the appropriate conversion initializer is, or simply converting
to floating point once *after* taking the sum.


>
> On Sun, Jan 15, 2017 at 19:21 Dave Abrahams  wrote:
>
>>
>>
>> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>>
>>
>>
>> > On Sun, Jan 15, 2017 at 3:27 PM, Dave Abrahams via swift-evolution <
>>
>> > swift-evolution@swift.org> wrote:
>>
>> >
>>
>> >>
>>
>> >> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>>
>> >>
>>
>> >> > There _may_ be value in recognizing the distinction between rings and
>>
>> >> > fields, perhaps? Just as the FP protocols make room for people to
>>
>> >> implement
>>
>> >> > their own decimal FP types, and just as you're trying to make
>> Arithmetic
>>
>> >> > accommodate complex numbers, the distinction would allow someone to
>> write
>>
>> >> > algorithms generic over rationals and reals (i.e. fields). Being
>> able to
>>
>> >> > represent exact fractions isn't so terribly niche, and I think the
>> design
>>
>> >> > wouldn't be terribly complicated by its accommodation:
>>
>> >> >
>>
>> >> > ```
>>
>> >> > // rename Arithmetic to Ring
>>
>> >> > // it's acceptable to omit `.one` from Ring, though some may call
>> that a
>>
>> >> > Pseudoring
>>
>> >> > // consider omitting division from Ring and pushing it down to
>>
>> >> > BinaryInteger and Field
>>
>> >> >
>>
>> >> > protocol BinaryInteger : Ring { ... }
>>
>> >> >
>>
>> >> > protocol Field : Ring {
>>
>> >> >   static var one { get }
>>
>> >> >   static func / (Self, Self) -> Self
>>
>> >> >   static func /= (inout Self, Self)
>>
>> >> >   var inverted: Self { get } // default impl: .one / self
>>
>> >> > }
>>
>> >> >
>>
>> >> > protocol FloatingPoint : Field { ... }
>>
>> >> > // rational number types and complex number types
>>
>> >> > // would also conform to Field
>>
>> >> > ```
>>
>> >>
>>
>> >> What generic algorithms would this enable?
>>
>> >
>>
>> > For one, anything to do with dividing into equal parts
>>
>>
>>
>> For example...?
>>
>>
>>
>> > could be generic over floating point, rational, and even complex
>>
>> > numbers, but you probably wouldn't want to include integer types in
>>
>> > such an algorithm.
>>
>> >
>>
>> >> Would they be appropriate
>>
>> >> for the standard library (as opposed to some more specialized numerics
>>
>> >> library)?
>>
>> >>
>>
>> >
>>
>> > The issue is that it's not terribly ergonomic to relegate `Field` to a
>>
>> > specialized library because one cannot retroactively conform
>>
>> > `FloatingPoint` to `Field`.
>>
>>
>>
>> I don't think this is an important enough concern to justify adding
>>
>> protocols to the standard library.  The number of types one has to
>>
>> individually make conform to Field is probably going to remain small.
>>
>>
>>
>> Show-me-the-mone^Walgorithms-ly y'rs,
>>
>>
>>
>> --
>>
>> -Dave
>>
>>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

Sent from my moss-covered three-handled family gradunza

> On Jan 15, 2017, at 5:29 PM, Xiaodi Wu  wrote:
> 
>> On Sun, Jan 15, 2017 at 7:24 PM, Dave Abrahams  wrote:
>> 
>> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>> 
>> > On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris  wrote:
>> >
>> >>
>> >>
>> >>
>> >>
>> >> On Jan 15, 2017, at 18:02, Xiaodi Wu  wrote:
>> >>
>> >> "Mathematically correct" integers behave just like Int in that there is
>> >> not a multiplicative inverse. What we're trying to do here is to determine
>> >> how much of what we know about mathematics is usefully modeled in the
>> >> standard library. The answer is not zero, because there is more than just
>> >> counting that people do with integers.
>> >>
>> >>
>> >> It's an interesting problem... When I was in school, "integer" division
>> >> "returned" a "quotient and remainder", a "fraction" (which, occasionally,
>> >> could be simplified to just an integer), or a "real". We never talked 
>> >> about
>> >> division in the context of "(Int, Int) -> Int", though. OTOH, I never took
>> >> any math classes past Differential Equations or Linear Algebra, either...
>> >> I'm *aware* of areas of math where you formally restrict yourself to the
>> >> kind of "(Int, Int) -> Int" operations we're doing here, but I don't
>> >> really know much about it. Is division even well-defined in that context?
>> >>
>> >> - Dave Sweeris
>> >>
>> >
>> > I'm no mathematician, and I'm not sure how to tackle the question of
>> > "well-defined." Hopefully someone who is more knowledgable can chime in
>> > here.
>> >
>> > But I'll have a go at replying to your point as it relates to the practical
>> > issue here. Two Int values can be "divided" to produce another Int, and
>> > that gives a predictable and well-understood result. It's an operation
>> > that's always going to be there--first, because it'd be insane to remove it
>> > since much working code relies on it, and second, because we're only
>> > re-designing integer protocols and not the concrete types. However, it _is_
>> > true that such an operation has very different semantics from division as
>> > you learned it in math.
>> >
>> > This is why I'm advocating for perhaps another look at the top of this
>> > integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
>> > semantic guarantees for a lot of things, but `/` has different semantics
>> > for integer types and floating point types
>> 
>> Well, that really depends on how closely you look.  From one
>> point-of-view, floating point division and integer division *both*
>> produce approximate results.
> 
> Yes, from a certain point of view. I remember we did discuss this at one 
> point on the list; I asked whether FloatingPoint was meant to model only the 
> countable set of representable values or whether it was meant to model the 
> uncountable set of reals. The answer was that here in Swift-land we're trying 
> to model the latter, and the approximate result is an artifact of the 
> imperfect modeling. Integer division, however, is not such an artifact, but 
> fundamentally a different operation.

That's right.  Thanks for keeping us honest and reminding us of our guiding 
stars. 👌🏻


>> > and is really closer to just syntax. Other mathematical types--which
>> > certainly the stdlib doesn't have to offer, but the stdlib protocol
>> > hierarchy shouldn't preclude their conformance to relevant protocols
>> > if it's possible--such as fractions and complex numbers, share with
>> > floating point types the semantics of `/` that qualify these types as
>> > fields. Dave A's question as to practical uses can probably best be
>> > answered in this way: to the extent that any generic algorithm relies
>> > on `/` having semantics and can be applied to fractions and real
>> > numbers, it would be useful to distinguish such an operation from
>> > integer "division."
>> 
>> That's not a bad answer.  Ruminating on this...
>> 
>> --
>> -Dave
> 
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

Sent from my moss-covered three-handled family gradunza

> On Jan 15, 2017, at 6:46 PM, Jacob Bandes-Storch  wrote:
> 
>> On Sun, Jan 15, 2017 at 6:13 PM, Xiaodi Wu via swift-evolution 
>>  wrote:
> 
>> One example: earlier, it was demonstrated that a genetic lerp would not 
>> accommodate vector types. However, it _does_ work fine for any scalar (i.e. 
>> field) type; however, with the currently proposed integer protocols, one 
>> would constrain it to Arithmetic types, yet the algorithm would be bogus for 
>> integers.
> 
> I wouldn't say lerp is bogus (the results aren't wrong), just much less 
> useful.
> 
> On the other hand:
> 
> extension Collection where Iterator.Element: Arithmetic {
> func mean() -> Iterator.Element {
> return self.reduce(Iterator.Element(), +) / 
> Iterator.Element(count)  // assuming these initializers exist
> }
> }
>  
> Now [6, 7].mean() returns 6, and that I would call bogus.
> 
> Of course, there are some alternative ways to implement this which avoid the 
> issue:
> 
> - Implement it only for Iterator.Element: FloatingPoint.
> - Implement it as mean() -> T, reducing by { $0 + T($1) } 
> or whatever the appropriate conversion initializer is, or simply converting 
> to floating point once after taking the sum.

You really want this to work for any field, though. Rational numbers, for 
example, would be excluded by those constraints

>> 
>> 
>>> On Sun, Jan 15, 2017 at 19:21 Dave Abrahams  wrote:
>>> 
>>> 
>>> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>>> 
>>> 
>>> 
>>> > On Sun, Jan 15, 2017 at 3:27 PM, Dave Abrahams via swift-evolution <
>>> 
>>> > swift-evolution@swift.org> wrote:
>>> 
>>> >
>>> 
>>> >>
>>> 
>>> >> on Sun Jan 15 2017, Xiaodi Wu  wrote:
>>> 
>>> >>
>>> 
>>> >> > There _may_ be value in recognizing the distinction between rings and
>>> 
>>> >> > fields, perhaps? Just as the FP protocols make room for people to
>>> 
>>> >> implement
>>> 
>>> >> > their own decimal FP types, and just as you're trying to make 
>>> >> > Arithmetic
>>> 
>>> >> > accommodate complex numbers, the distinction would allow someone to 
>>> >> > write
>>> 
>>> >> > algorithms generic over rationals and reals (i.e. fields). Being able 
>>> >> > to
>>> 
>>> >> > represent exact fractions isn't so terribly niche, and I think the 
>>> >> > design
>>> 
>>> >> > wouldn't be terribly complicated by its accommodation:
>>> 
>>> >> >
>>> 
>>> >> > ```
>>> 
>>> >> > // rename Arithmetic to Ring
>>> 
>>> >> > // it's acceptable to omit `.one` from Ring, though some may call that 
>>> >> > a
>>> 
>>> >> > Pseudoring
>>> 
>>> >> > // consider omitting division from Ring and pushing it down to
>>> 
>>> >> > BinaryInteger and Field
>>> 
>>> >> >
>>> 
>>> >> > protocol BinaryInteger : Ring { ... }
>>> 
>>> >> >
>>> 
>>> >> > protocol Field : Ring {
>>> 
>>> >> >   static var one { get }
>>> 
>>> >> >   static func / (Self, Self) -> Self
>>> 
>>> >> >   static func /= (inout Self, Self)
>>> 
>>> >> >   var inverted: Self { get } // default impl: .one / self
>>> 
>>> >> > }
>>> 
>>> >> >
>>> 
>>> >> > protocol FloatingPoint : Field { ... }
>>> 
>>> >> > // rational number types and complex number types
>>> 
>>> >> > // would also conform to Field
>>> 
>>> >> > ```
>>> 
>>> >>
>>> 
>>> >> What generic algorithms would this enable?
>>> 
>>> >
>>> 
>>> > For one, anything to do with dividing into equal parts
>>> 
>>> 
>>> 
>>> For example...?
>>> 
>>> 
>>> 
>>> > could be generic over floating point, rational, and even complex
>>> 
>>> > numbers, but you probably wouldn't want to include integer types in
>>> 
>>> > such an algorithm.
>>> 
>>> >
>>> 
>>> >> Would they be appropriate
>>> 
>>> >> for the standard library (as opposed to some more specialized numerics
>>> 
>>> >> library)?
>>> 
>>> >>
>>> 
>>> >
>>> 
>>> > The issue is that it's not terribly ergonomic to relegate `Field` to a
>>> 
>>> > specialized library because one cannot retroactively conform
>>> 
>>> > `FloatingPoint` to `Field`.
>>> 
>>> 
>>> 
>>> I don't think this is an important enough concern to justify adding
>>> 
>>> protocols to the standard library.  The number of types one has to
>>> 
>>> individually make conform to Field is probably going to remain small.
>>> 
>>> 
>>> 
>>> Show-me-the-mone^Walgorithms-ly y'rs,
>>> 
>>> 
>>> 
>>> --
>>> 
>>> -Dave
>>> 
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
> 
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Stephen Canon  wrote:

> Responding to the thread in general here, not so much any specific email:
>
> “Arithmetic” at present is not a mathematically-precise concept, and
> it may be a mistake to make it be one[1]; it’s a
> mathematically-slightly-fuzzy “number” protocol. FWIW, if I had to
> pick a mathematical object to pin it to, I would make it a
> [non-commutative] ring, which give it:
>
>   addition, subtraction, multiplication, IntegerLiteralConvertible, and 
> an inverse: T?
>   property.
>
> Note that this would make division go out the window, but we would
> *preserve* int literal convertible (because there’s a unique map from
> Z to any ring — Z is the initial object in the category of rings). I
> think that it’s quite important to keep that for writing generic code.
>
> Vectors and points are not “numbery” in this sense, so they should not
> conform to this protocol, which is why it’s OK that multiplication and
> int literals don’t make sense for them. They’re property a vector
> space or module built over a scalar type.
>
> I would be OK with moving division out of the Arithmetic protocol, as
> the division operator is fundamentally different for integers and
> floating-point, and you want to have separate left- and right-
> division for quaternions and matrices. I would be pretty strongly
> opposed to removing integer literals; they rightfully belong here.
>
> I think the name “Arithmetic” is sound. It is deliberately *not* one
> of the standard mathematical abstractions, reserving those names for
> folks who want to build a precise lattice of algebraic
> objects. Vectors don’t belong in this protocol, though.

OK, suppose we move division, and state in the documentation that models
of Arithmetic should have the mathematical properties of a
(non-commutative) Ring?

> – Steve
>
> [1] We don’t want to make a semester course in modern algebra a
> prerequisite to using Swift, as much as I would enjoy building a tower
> of formalism as a mathematician.

Indeedy.

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Mon, Jan 16, 2017 at 12:44 AM, Dave Abrahams via swift-evolution <
swift-evolution@swift.org> wrote:

>
> on Sun Jan 15 2017, Stephen Canon  wrote:
>
> > Responding to the thread in general here, not so much any specific email:
> >
> > “Arithmetic” at present is not a mathematically-precise concept, and
> > it may be a mistake to make it be one[1]; it’s a
> > mathematically-slightly-fuzzy “number” protocol. FWIW, if I had to
> > pick a mathematical object to pin it to, I would make it a
> > [non-commutative] ring, which give it:
> >
> >   addition, subtraction, multiplication, IntegerLiteralConvertible,
> and an inverse: T?
> >   property.
> >
> > Note that this would make division go out the window, but we would
> > *preserve* int literal convertible (because there’s a unique map from
> > Z to any ring — Z is the initial object in the category of rings). I
> > think that it’s quite important to keep that for writing generic code.
> >
> > Vectors and points are not “numbery” in this sense, so they should not
> > conform to this protocol, which is why it’s OK that multiplication and
> > int literals don’t make sense for them. They’re property a vector
> > space or module built over a scalar type.
> >
> > I would be OK with moving division out of the Arithmetic protocol, as
> > the division operator is fundamentally different for integers and
> > floating-point, and you want to have separate left- and right-
> > division for quaternions and matrices. I would be pretty strongly
> > opposed to removing integer literals; they rightfully belong here.
> >
> > I think the name “Arithmetic” is sound. It is deliberately *not* one
> > of the standard mathematical abstractions, reserving those names for
> > folks who want to build a precise lattice of algebraic
> > objects. Vectors don’t belong in this protocol, though.
>
> OK, suppose we move division, and state in the documentation that models
> of Arithmetic should have the mathematical properties of a
> (non-commutative) Ring?
>

Unless I'm mistaken, after removing division, models of SignedArithmetic
would have the mathematical properties of a ring. For every element a in
ring R, there must exist an additive inverse -a in R such that a + (-a) =
0. Models of Arithmetic alone would not necessarily have that property.

> – Steve
> >
> > [1] We don’t want to make a semester course in modern algebra a
> > prerequisite to using Swift, as much as I would enjoy building a tower
> > of formalism as a mathematician.
>
> Indeedy.
>
> --
> -Dave
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Stephen Canon via swift-evolution]

> On Jan 16, 2017, at 3:25 AM, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> Unless I'm mistaken, after removing division, models of SignedArithmetic 
> would have the mathematical properties of a ring. For every element a in ring 
> R, there must exist an additive inverse -a in R such that a + (-a) = 0. 
> Models of Arithmetic alone would not necessarily have that property.

Closure under the arithmetic operations is a sticky point for all the finite 
integer models vs. the actual ring axioms.  No finite [non-modulo] integer type 
is closed, because of overflow. Similarly, additive inverses don’t exist for 
the most negative value of a signed type, or for any non-zero value of an 
unsigned type. The obvious way around this is to say that types conforming to 
Arithmetic model a subset of a ring that need not be closed under the 
operations.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Karl Wagner via swift-evolution]

Really glad to see this coming back :)

I have a couple of questions:

1) How does Strideable relate to Arithmetic?

My understanding is that Strideable allows non-numeric types to express 
different-type addition and subtraction, and that Arithmetic is for numeric 
types only (derives from ExpressibleByIntegerLiteral) and allows then to 
express same-type operations. Is that correct? If so, it would be nice to add 
it to the proposal so people know when they should conform (or set their 
generic constraints) to one or the other.

2) Can SignedNumber get some operators now?

Strideable.Stride is bound to this weird protocol ‘SignedNumber’. You can 
create instances of it out of thin air via an integer literal, but you can’t 
accumulate Strides to find the overall distance between some adjacent 
Strideables. 


Also, #1 is why I don’t like the Strideable operator deprecation being part of 
the proposal (and therefore part of the language specification). It doesn’t 
solve the underlying issue, which is that our integer literal protocols aren’t 
really good enough - they’re not useful enough outside the standard library 
(see: https://bugs.swift.org/browse/SR-920), and evidently the compiler isn’t 
able to use them to infer types correctly. Perhaps fixing it is a low priority, 
and that’s fine, but what about if somebody else defines this operator in their 
library? They start of break lots of valid code because the compiler can’t do 
the right thing. Improved literal protocols may be the better way to resolve 
that problem.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Mon, Jan 16, 2017 at 12:02 PM, Stephen Canon  wrote:

> On Jan 16, 2017, at 3:25 AM, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> Unless I'm mistaken, after removing division, models of SignedArithmetic
> would have the mathematical properties of a ring. For every element a in
> ring R, there must exist an additive inverse -a in R such that a + (-a) =
> 0. Models of Arithmetic alone would not necessarily have that property.
>
>
> Closure under the arithmetic operations is a sticky point for all the
> finite integer models vs. the actual ring axioms.  No finite [non-modulo]
> integer type is closed, because of overflow. Similarly, additive inverses
> don’t exist for the most negative value of a signed type,
>

I think this goes back to the distinct mentioned earlier: imperfection in
how we model something, or a difference in what we're modeling? Finite
memory will dictate that any model that attempts to represent integers will
face constraints. Signed integer types represent a best-effort attempt at
exactly representing the greatest possible number of integers within a
given amount of memory such that the greatest proportion of those have an
additive inverse that can be also be represented in the same amount of
memory.


> or for any non-zero value of an unsigned type.
>

This is not fundamentally attributable to a limitation of how we model
something. Non-zero values of unsigned type do not have additive inverses
in the same way that non-one values of unsigned type do not have
multiplicative inverses.

The obvious way around this is to say that types conforming to Arithmetic
> model a subset of a ring that need not be closed under the operations.
>

If we don't remove division, type conforming to Arithmetic would also model
a subset of a field that need not be closed under the operations. I'm not
sure it'd be wise to put such a mathematical definition on it with a "need
not" like that. Better, IMO, to give these protocols semantics based on a
positive description of the axioms that do hold--with the caveat that the
result of addition and multiplication will hold to these axioms only
insofar as the result does not overflow.

– Steve
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Mon Jan 16 2017, Xiaodi Wu  wrote:

> On Mon, Jan 16, 2017 at 12:02 PM, Stephen Canon  wrote:
>
>> On Jan 16, 2017, at 3:25 AM, Xiaodi Wu via swift-evolution <
>> swift-evolution@swift.org> wrote:
>>
>>
>> Unless I'm mistaken, after removing division, models of SignedArithmetic
>> would have the mathematical properties of a ring. For every element a in
>> ring R, there must exist an additive inverse -a in R such that a + (-a) =
>> 0. Models of Arithmetic alone would not necessarily have that property.
>>
>>
>> Closure under the arithmetic operations is a sticky point for all the
>> finite integer models vs. the actual ring axioms.  No finite [non-modulo]
>> integer type is closed, because of overflow. Similarly, additive inverses
>> don’t exist for the most negative value of a signed type,
>>
>
> I think this goes back to the distinct mentioned earlier: imperfection in
> how we model something, or a difference in what we're modeling? Finite
> memory will dictate that any model that attempts to represent integers will
> face constraints. Signed integer types represent a best-effort attempt at
> exactly representing the greatest possible number of integers within a
> given amount of memory such that the greatest proportion of those have an
> additive inverse that can be also be represented in the same amount of
> memory.
>
>> or for any non-zero value of an unsigned type.
>>
>
> This is not fundamentally attributable to a limitation of how we model
> something. Non-zero values of unsigned type do not have additive inverses
> in the same way that non-one values of unsigned type do not have
> multiplicative inverses.
>
> The obvious way around this is to say that types conforming to Arithmetic
>> model a subset of a ring that need not be closed under the operations.
>>
>
> If we don't remove division, type conforming to Arithmetic would also model
> a subset of a field that need not be closed under the operations. I'm not
> sure it'd be wise to put such a mathematical definition on it with a "need
> not" like that. Better, IMO, to give these protocols semantics based on a
> positive description of the axioms that do hold--with the caveat that the
> result of addition and multiplication will hold to these axioms only
> insofar as the result does not overflow.

I feel like I'm mostly watching from the sidelines as the math titans
duke it out, but, FWIW, that sounds pretty good to me.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Mon, Jan 16, 2017 at 11:57 AM, Karl Wagner via swift-evolution <
swift-evolution@swift.org> wrote:

> Really glad to see this coming back :)
>
> I have a couple of questions:
>
> 1) How does Strideable relate to Arithmetic?
>
> My understanding is that Strideable allows non-numeric types to express
> different-type addition and subtraction, and that Arithmetic is for numeric
> types only (derives from ExpressibleByIntegerLiteral) and allows then to
> express same-type operations. Is that correct?


My understanding was that heterogeneous addition and subtraction using
operators are not supported not merely due to compiler limitations but as a
fundamental philosophy, because the type of the intended result can be
unclear to human readers and unintentional promotion is to be avoided? In
that vein, my understanding was that having those operators available for
Strideable was inconsistent and overdue for removal, and `advanced(by:)` is
the intended spelling for advancing a value by a distance of a different
type.


> If so, it would be nice to add it to the proposal so people know when they
> should conform (or set their generic constraints) to one or the other.
>
> 2) Can SignedNumber get some operators now?
>
> Strideable.Stride is bound to this weird protocol ‘SignedNumber’. You can
> create instances of it out of thin air via an integer literal, but you
> can’t accumulate Strides to find the overall distance between some adjacent
> Strideables.
>

I understood these new protocols to mean that SignedNumber is headed for
deprecation?


> Also, #1 is why I don’t like the Strideable operator deprecation being
> part of the proposal (and therefore part of the language specification). It
> doesn’t solve the underlying issue, which is that our integer literal
> protocols aren’t really good enough - they’re not useful enough outside the
> standard library (see: https://bugs.swift.org/browse/SR-920), and
> evidently the compiler isn’t able to use them to infer types correctly.
> Perhaps fixing it is a low priority, and that’s fine, but what about if
> somebody else defines this operator in their library? They start of break
> lots of valid code because the compiler can’t do the right thing. Improved
> literal protocols may be the better way to resolve that problem.
>

I agree totally that literals are aching for improvements as outlined in
SR-920. Not sure how it relates to integer protocols though. What are some
examples of valid code that get broken today because of compiler
limitations?


> - Karl
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Mon Jan 16 2017, Xiaodi Wu  wrote:

> On Mon, Jan 16, 2017 at 11:57 AM, Karl Wagner via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>> Really glad to see this coming back :)
>>
>> I have a couple of questions:
>>
>> 1) How does Strideable relate to Arithmetic?
>>
>> My understanding is that Strideable allows non-numeric types to express
>> different-type addition and subtraction, and that Arithmetic is for numeric
>> types only (derives from ExpressibleByIntegerLiteral) and allows then to
>> express same-type operations. Is that correct?
>
> My understanding was that heterogeneous addition and subtraction using
> operators are not supported not merely due to compiler limitations but as a
> fundamental philosophy, because the type of the intended result can be
> unclear to human readers and unintentional promotion is to be avoided? 

No, not really.  We'd like to introduce a promotion model.

> In that vein, my understanding was that having those operators
> available for Strideable was inconsistent and overdue for removal, and
> `advanced(by:)` is the intended spelling for advancing a value by a
> distance of a different type.

The real reason to remove them from Strideable is that unsigned numbers
are strideable with a signed stride, which made preventing people from
adding signed and unsigned numbers unintentionally messy and unreliable.

>> If so, it would be nice to add it to the proposal so people know when they
>> should conform (or set their generic constraints) to one or the other.
>>
>> 2) Can SignedNumber get some operators now?
>>
>> Strideable.Stride is bound to this weird protocol ‘SignedNumber’. You can
>> create instances of it out of thin air via an integer literal, but you
>> can’t accumulate Strides to find the overall distance between some adjacent
>> Strideables.
>>
>
> I understood these new protocols to mean that SignedNumber is headed for
> deprecation?

That's the plan.

>> Also, #1 is why I don’t like the Strideable operator deprecation being
>> part of the proposal (and therefore part of the language specification). It
>> doesn’t solve the underlying issue, which is that our integer literal
>> protocols aren’t really good enough - they’re not useful enough outside the
>> standard library (see: https://bugs.swift.org/browse/SR-920), and
>> evidently the compiler isn’t able to use them to infer types correctly.
>> Perhaps fixing it is a low priority, and that’s fine, but what about if
>> somebody else defines this operator in their library? They start of break
>> lots of valid code because the compiler can’t do the right thing. Improved
>> literal protocols may be the better way to resolve that problem.
>>
>
> I agree totally that literals are aching for improvements as outlined in
> SR-920. 

Indeedy.

> Not sure how it relates to integer protocols though. What are some
> examples of valid code that get broken today because of compiler
> limitations?
>
>> - Karl
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Karl Wagner via swift-evolution]

> On 16 Jan 2017, at 20:53, Xiaodi Wu  wrote:
> 
> On Mon, Jan 16, 2017 at 11:57 AM, Karl Wagner via swift-evolution 
> mailto:swift-evolution@swift.org>> wrote:
> Really glad to see this coming back :)
> 
> I have a couple of questions:
> 
> 1) How does Strideable relate to Arithmetic?
> 
> My understanding is that Strideable allows non-numeric types to express 
> different-type addition and subtraction, and that Arithmetic is for numeric 
> types only (derives from ExpressibleByIntegerLiteral) and allows then to 
> express same-type operations. Is that correct?
> 
> My understanding was that heterogeneous addition and subtraction using 
> operators are not supported not merely due to compiler limitations but as a 
> fundamental philosophy, because the type of the intended result can be 
> unclear to human readers and unintentional promotion is to be avoided? In 
> that vein, my understanding was that having those operators available for 
> Strideable was inconsistent and overdue for removal, and `advanced(by:)` is 
> the intended spelling for advancing a value by a distance of a different type.
>  
> If so, it would be nice to add it to the proposal so people know when they 
> should conform (or set their generic constraints) to one or the other.
> 
> 2) Can SignedNumber get some operators now?
> 
> Strideable.Stride is bound to this weird protocol ‘SignedNumber’. You can 
> create instances of it out of thin air via an integer literal, but you can’t 
> accumulate Strides to find the overall distance between some adjacent 
> Strideables.
> 
> I understood these new protocols to mean that SignedNumber is headed for 
> deprecation?

It would be nice if the proposal said that, then (and mentioned the 
corresponding change to Strideable.Stride). I assume it will be replaced with 
SignedArithmetic, then.

>  
> Also, #1 is why I don’t like the Strideable operator deprecation being part 
> of the proposal (and therefore part of the language specification). It 
> doesn’t solve the underlying issue, which is that our integer literal 
> protocols aren’t really good enough - they’re not useful enough outside the 
> standard library (see: https://bugs.swift.org/browse/SR-920 
> ), and evidently the compiler isn’t 
> able to use them to infer types correctly. Perhaps fixing it is a low 
> priority, and that’s fine, but what about if somebody else defines this 
> operator in their library? They start of break lots of valid code because the 
> compiler can’t do the right thing. Improved literal protocols may be the 
> better way to resolve that problem.
> 
> I agree totally that literals are aching for improvements as outlined in 
> SR-920. Not sure how it relates to integer protocols though. What are some 
> examples of valid code that get broken today because of compiler limitations?

The PR that implemented this fixed a bug with integer literals - basically, the 
thrust of it (as I understand) is that the compiler can’t figure out which is 
the preferred overload. It doesn’t know to prefer same-type arithmetic when 
resolving literals involved in operators.

My problem with just fixing the problem by removing that operator is that 
anybody could add it back in their own code, and that should be perfectly 
allowable, but if they did so basic expressions would fail to compile. To me it 
sounds preferable to leave this as a implementation artefact until we get a 
chance to make the literal protocols better.

Strideable isn’t some esoteric protocol just for collection indexes, you know. 
It’s very useful for any quasi-numeric type whose absolute value is 
semantically different from a difference. For example, I have strongly-typed 
wrappers for a ByteOffset within a binary file and a LineNumber inside a text 
file. These wrappers allow me to write extensions (for example to clamp to the 
bounds of a particular file), and ensure that I don’t accidentally mix 
semantically different values. They are both Strideable by Int, which is a 
better semantic fit than Arithmetic (LineNumbers are absolute, should you be 
able to add them? What does LineNumber * LineNumber mean?).

So my point is basically that it’s an important protocol (maybe not so much in 
the standard library, but certainly beyond).

- Karl

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Mon, Jan 16, 2017 at 3:32 PM, Karl Wagner  wrote:

>
> On 16 Jan 2017, at 20:53, Xiaodi Wu  wrote:
>
> On Mon, Jan 16, 2017 at 11:57 AM, Karl Wagner via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>> Really glad to see this coming back :)
>>
>> I have a couple of questions:
>>
>> 1) How does Strideable relate to Arithmetic?
>>
>> My understanding is that Strideable allows non-numeric types to express
>> different-type addition and subtraction, and that Arithmetic is for numeric
>> types only (derives from ExpressibleByIntegerLiteral) and allows then to
>> express same-type operations. Is that correct?
>
>
> My understanding was that heterogeneous addition and subtraction using
> operators are not supported not merely due to compiler limitations but as a
> fundamental philosophy, because the type of the intended result can be
> unclear to human readers and unintentional promotion is to be avoided? In
> that vein, my understanding was that having those operators available for
> Strideable was inconsistent and overdue for removal, and `advanced(by:)` is
> the intended spelling for advancing a value by a distance of a different
> type.
>
>
>> If so, it would be nice to add it to the proposal so people know when
>> they should conform (or set their generic constraints) to one or the other.
>>
>> 2) Can SignedNumber get some operators now?
>>
>> Strideable.Stride is bound to this weird protocol ‘SignedNumber’. You can
>> create instances of it out of thin air via an integer literal, but you
>> can’t accumulate Strides to find the overall distance between some adjacent
>> Strideables.
>>
>
> I understood these new protocols to mean that SignedNumber is headed for
> deprecation?
>
>
> It would be nice if the proposal said that, then (and mentioned the
> corresponding change to Strideable.Stride). I assume it will be replaced
> with SignedArithmetic, then.
>
>
>
>> Also, #1 is why I don’t like the Strideable operator deprecation being
>> part of the proposal (and therefore part of the language specification). It
>> doesn’t solve the underlying issue, which is that our integer literal
>> protocols aren’t really good enough - they’re not useful enough outside the
>> standard library (see: https://bugs.swift.org/browse/SR-920), and
>> evidently the compiler isn’t able to use them to infer types correctly.
>> Perhaps fixing it is a low priority, and that’s fine, but what about if
>> somebody else defines this operator in their library? They start of break
>> lots of valid code because the compiler can’t do the right thing. Improved
>> literal protocols may be the better way to resolve that problem.
>>
>
> I agree totally that literals are aching for improvements as outlined in
> SR-920. Not sure how it relates to integer protocols though. What are some
> examples of valid code that get broken today because of compiler
> limitations?
>
>
> The PR that implemented this fixed a bug with integer literals -
> basically, the thrust of it (as I understand) is that the compiler can’t
> figure out which is the preferred overload. It doesn’t know to prefer
> same-type arithmetic when resolving literals involved in operators.
>

Yes, that's a compiler shortcoming and a practical reason to remove + for
the moment. However, there's also the other reason to remove +, which is
that Swift doesn't have a promotion model for integer types, and until it
does heterogeneous operations shouldn't be spelled using + whether the
compiler knows how to pick a preferred overload or not...

My problem with just fixing the problem by removing that operator is that
> anybody could add it back in their own code, and that should be perfectly
> allowable, but if they did so basic expressions would fail to compile.
>

This would only break their own code unless it's also exported in a
library. For the former, if we fix something because it's broken, the fact
that someone can put it back into their own code to break it isn't a reason
for us not to fix it :) As to the latter scenario, clashes between
libraries that export different implementations of the same operators and
the inability for end users to choose not the import them with the rest of
the library _is_ actually an annoying issue that needs improvement. This is
getting away from the topic of integers and distinct from the topic of
literal protocols, but tackling this topic is sorely needed IMO.


> To me it sounds preferable to leave this as a implementation artefact
> until we get a chance to make the literal protocols better.
>
> Strideable isn’t some esoteric protocol just for collection indexes, you
> know. It’s very useful for any quasi-numeric type whose absolute value is
> semantically different from a difference. For example, I have
> strongly-typed wrappers for a ByteOffset within a binary file and a
> LineNumber inside a text file. These wrappers allow me to write extensions
> (for example to clamp to the bounds of a particular file), and ensure that
> I don’t accidental

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Mon, Jan 16, 2017 at 2:04 PM, Dave Abrahams  wrote:

>
> on Mon Jan 16 2017, Xiaodi Wu  wrote:
>
> > On Mon, Jan 16, 2017 at 12:02 PM, Stephen Canon 
> wrote:
> >
> >> On Jan 16, 2017, at 3:25 AM, Xiaodi Wu via swift-evolution <
> >> swift-evolution@swift.org> wrote:
> >>
> >>
> >> Unless I'm mistaken, after removing division, models of SignedArithmetic
> >> would have the mathematical properties of a ring. For every element a in
> >> ring R, there must exist an additive inverse -a in R such that a + (-a)
> =
> >> 0. Models of Arithmetic alone would not necessarily have that property.
> >>
> >>
> >> Closure under the arithmetic operations is a sticky point for all the
> >> finite integer models vs. the actual ring axioms.  No finite
> [non-modulo]
> >> integer type is closed, because of overflow. Similarly, additive
> inverses
> >> don’t exist for the most negative value of a signed type,
> >>
> >
> > I think this goes back to the distinct mentioned earlier: imperfection in
> > how we model something, or a difference in what we're modeling? Finite
> > memory will dictate that any model that attempts to represent integers
> will
> > face constraints. Signed integer types represent a best-effort attempt at
> > exactly representing the greatest possible number of integers within a
> > given amount of memory such that the greatest proportion of those have an
> > additive inverse that can be also be represented in the same amount of
> > memory.
> >
> >> or for any non-zero value of an unsigned type.
> >>
> >
> > This is not fundamentally attributable to a limitation of how we model
> > something. Non-zero values of unsigned type do not have additive inverses
> > in the same way that non-one values of unsigned type do not have
> > multiplicative inverses.
> >
> > The obvious way around this is to say that types conforming to Arithmetic
> >> model a subset of a ring that need not be closed under the operations.
> >>
> >
> > If we don't remove division, type conforming to Arithmetic would also
> model
> > a subset of a field that need not be closed under the operations. I'm not
> > sure it'd be wise to put such a mathematical definition on it with a
> "need
> > not" like that. Better, IMO, to give these protocols semantics based on a
> > positive description of the axioms that do hold--with the caveat that the
> > result of addition and multiplication will hold to these axioms only
> > insofar as the result does not overflow.
>
> I feel like I'm mostly watching from the sidelines as the math titans
> duke it out, but, FWIW, that sounds pretty good to me.


Ha, Steve is the titan. I'm just some guy who's still trying to wrap his
head about this stuff. A few more comments though:

- Why is `signum` required on BinaryInteger? Should it not be required on
SignedArithmetic instead? For signed non-integers, a signum function can be
defined. It can even be generalized to complex numbers. I'm unsure, OTOH,
what one does with a signum function for an unsigned integer...

- Why is there a static `isSigned` on BinaryInteger? All types refine
either `SignedInteger` or `UnsignedInteger`, which would seem to give you
the desired answer either statically or dynamically.

- A rough sketch of what I understand the semantics to be of these
protocols so far:
https://gist.github.com/xwu/a4250536ff8e5d207682079b641e9408



> --
> -Dave
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 16, 2017, at 13:40, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> On Mon, Jan 16, 2017 at 12:02 PM, Stephen Canon  wrote:
>>> On Jan 16, 2017, at 3:25 AM, Xiaodi Wu via swift-evolution 
>>>  wrote:
>>> 
>>> Unless I'm mistaken, after removing division, models of SignedArithmetic 
>>> would have the mathematical properties of a ring. For every element a in 
>>> ring R, there must exist an additive inverse -a in R such that a + (-a) = 
>>> 0. Models of Arithmetic alone would not necessarily have that property.
>> 
>> Closure under the arithmetic operations is a sticky point for all the finite 
>> integer models vs. the actual ring axioms.  No finite [non-modulo] integer 
>> type is closed, because of overflow. Similarly, additive inverses don’t 
>> exist for the most negative value of a signed type,
> 
> I think this goes back to the distinct mentioned earlier: imperfection in how 
> we model something, or a difference in what we're modeling? Finite memory 
> will dictate that any model that attempts to represent integers will face 
> constraints. Signed integer types represent a best-effort attempt at exactly 
> representing the greatest possible number of integers within a given amount 
> of memory such that the greatest proportion of those have an additive inverse 
> that can be also be represented in the same amount of memory.
>  
>> or for any non-zero value of an unsigned type.
> 
> This is not fundamentally attributable to a limitation of how we model 
> something. Non-zero values of unsigned type do not have additive inverses in 
> the same way that non-one values of unsigned type do not have multiplicative 
> inverses.
> 
>> The obvious way around this is to say that types conforming to Arithmetic 
>> model a subset of a ring that need not be closed under the operations.
> 
> If we don't remove division, type conforming to Arithmetic would also model a 
> subset of a field that need not be closed under the operations. I'm not sure 
> it'd be wise to put such a mathematical definition on it with a "need not" 
> like that. Better, IMO, to give these protocols semantics based on a positive 
> description of the axioms that do hold--with the caveat that the result of 
> addition and multiplication will hold to these axioms only insofar as the 
> result does not overflow.

What about writing the division part of the protocol so that the return type 
isn't necessarily `Self`?
protocol Arithmetic {
associatedtype DivisionResult
// use a function instead of an operator to avoid making this the mother of 
all breaking changes
...
static func divide (_: Self, _: Self) -> Self.DivisionResult
...
}
extension FloatingPoint {
typealias DivisionResult = Self
}
extension Integer {
typealias DivisionResult = (quotient: Self, remainder: Self)
}
That way, Integer division returns the "correct" answer regardless of whether 
the numerator is a multiple of the denominator.
In generic algorithms, you could easily extract the "normal" value like this:
let tValue = T.divide(x, y).0
because the `.0` of a non-tuple value is just the original value, right?

One thing I'm not sure about (and can't check because I'm not in front of a 
computer) is how this would affect multiplication... Would we want `Self` and 
`Self.DivisionResult` to be mutually multipliable?
protocol Arithmetic {
associatedtype DivisionResult
...
static func divide (_: Self, _: Self) -> Self.DivisionResult
static func * (_: Self, _: Self) -> Self
static func * (_: Self, _: Self.DivisionResult) -> Self
static func * (_: Self.DivisionResult, _: Self) -> Self
}

Could the compiler figure out that, where Self.DivisionResult == Self, those 
three * functions are actually just one function, or, whenever you tried to 
actually multiply stuff, would it throw its hands in the air (like it just 
don't care) and complain about ambiguous references to "*"?

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

I don't think this is necessary for any generic algorithms. There is
already quotientAndRemainder for your use for integers, and floating point
division works differently. I don't think .0 works in any case.
Fundamentally, your idea would turn integers into ersatz rational numbers,
but one of the purposes of these protocols is to make it easy to make your
own rational type if the need arises. My understanding of the goal here is
to model what integers can already do, not to give them new functions.
On Mon, Jan 16, 2017 at 17:06 David Sweeris  wrote:

>
> On Jan 16, 2017, at 13:40, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> On Mon, Jan 16, 2017 at 12:02 PM, Stephen Canon  wrote:
>
> On Jan 16, 2017, at 3:25 AM, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> Unless I'm mistaken, after removing division, models of SignedArithmetic
> would have the mathematical properties of a ring. For every element a in
> ring R, there must exist an additive inverse -a in R such that a + (-a) =
> 0. Models of Arithmetic alone would not necessarily have that property.
>
>
> Closure under the arithmetic operations is a sticky point for all the
> finite integer models vs. the actual ring axioms.  No finite [non-modulo]
> integer type is closed, because of overflow. Similarly, additive inverses
> don’t exist for the most negative value of a signed type,
>
>
> I think this goes back to the distinct mentioned earlier: imperfection in
> how we model something, or a difference in what we're modeling? Finite
> memory will dictate that any model that attempts to represent integers will
> face constraints. Signed integer types represent a best-effort attempt at
> exactly representing the greatest possible number of integers within a
> given amount of memory such that the greatest proportion of those have an
> additive inverse that can be also be represented in the same amount of
> memory.
>
>
> or for any non-zero value of an unsigned type.
>
>
> This is not fundamentally attributable to a limitation of how we model
> something. Non-zero values of unsigned type do not have additive inverses
> in the same way that non-one values of unsigned type do not have
> multiplicative inverses.
>
> The obvious way around this is to say that types conforming to Arithmetic
> model a subset of a ring that need not be closed under the operations.
>
>
> If we don't remove division, type conforming to Arithmetic would also
> model a subset of a field that need not be closed under the operations. I'm
> not sure it'd be wise to put such a mathematical definition on it with a
> "need not" like that. Better, IMO, to give these protocols semantics based
> on a positive description of the axioms that do hold--with the caveat that
> the result of addition and multiplication will hold to these axioms only
> insofar as the result does not overflow.
>
>
> What about writing the division part of the protocol so that the return
> type isn't necessarily `Self`?
> protocol Arithmetic {
> associatedtype DivisionResult
> // use a function instead of an operator to avoid making this the
> mother of all breaking changes
> ...
> static func divide (_: Self, _: Self) -> Self.DivisionResult
> ...
> }
> extension FloatingPoint {
> typealias DivisionResult = Self
> }
> extension Integer {
> typealias DivisionResult = (quotient: Self, remainder: Self)
> }
> That way, Integer division returns the "correct" answer regardless of
> whether the numerator is a multiple of the denominator.
> In generic algorithms, you could easily extract the "normal" value like
> this:
> let tValue = T.divide(x, y).0
> because the `.0` of a non-tuple value is just the original value, right?
>
> One thing I'm not sure about (and can't check because I'm not in front of
> a computer) is how this would affect multiplication... Would we want `Self`
> and `Self.DivisionResult` to be mutually multipliable?
> protocol Arithmetic {
> associatedtype DivisionResult
> ...
> static func divide (_: Self, _: Self) -> Self.DivisionResult
> static func * (_: Self, _: Self) -> Self
> static func * (_: Self, _: Self.DivisionResult) -> Self
> static func * (_: Self.DivisionResult, _: Self) -> Self
> }
>
> Could the compiler figure out that, where Self.DivisionResult ==
> Self, those three * functions are actually just one function, or, whenever
> you tried to actually multiply stuff, would it throw its hands in the air
> (like it just don't care) and complain about ambiguous references to "*"?
>
> - Dave Sweeris
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 16, 2017, at 17:16, Xiaodi Wu  wrote:
> 
> My understanding of the goal here is to model what integers can already do, 
> not to give them new functions.

Ah, ok. Never mind then.

- Dave Sweeris
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Mon Jan 16 2017, Xiaodi Wu  wrote:

> Strideable? I didn't think Strideable itself was going away. I'd be sad if
> it did; for one, all the Unsafe*Pointers are Strideable and that has its
> uses.

Nobody's proposing to remove Strideable.

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Jay Abbott via swift-evolution]

I barely understand any of this thread, so these might be silly questions,
or based on a total misunderstanding the goals here, but it seems to be
about: a) clever/advanced mathsy things; b) naming things; and c) the
standard library... my questions are:

Do specialised clever advanced mathsy libraries all work exactly the same,
or do they have slightly different behaviours or conventions or semantics
in different fields of study?

Is the the goal here to define a common/shared sub-set of specialised maths
libraries, but in the standard library? Would that be useful by itself?

Could it be possible that "naming things" in the standard library would
trample all over possible uses in external libraries, making it harder
rather than easier for specialised maths libraries to construct their
interfaces in a non-confusing way?


On Tue, 17 Jan 2017 at 01:39 Dave Abrahams via swift-evolution <
swift-evolution@swift.org> wrote:

>
> on Mon Jan 16 2017, Xiaodi Wu  wrote:
>
> > Strideable? I didn't think Strideable itself was going away. I'd be sad
> if
> > it did; for one, all the Unsafe*Pointers are Strideable and that has its
> > uses.
>
> Nobody's proposing to remove Strideable.
>
> --
> -Dave
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Florent Vilmart via swift-evolution]

>From what I see, talking about Fields, Rings, vector spaces etc... we're 
>talking about modeling the standard library upon mathematic models / axioms 
>(particularly algebra) and using the same terminology.

Those constructions allow for a more flexible approach as one would be able to 
'code theorems' on the top of the std library based on their mathematical 
definitions, instead of their CS oriented definitions.

That's overly abstract, incredible low level and insanely powerful at the same 
time.

Still it's an interesting concept of modeling the 'algebra' based upon those 
abstract structures, even if I believe the real world examples of usage would 
be thin.

On Jan 16, 2017, 9:26 PM -0500, Jay Abbott via swift-evolution 
, wrote:
> I barely understand any of this thread, so these might be silly questions, or 
> based on a total misunderstanding the goals here, but it seems to be about: 
> a) clever/advanced mathsy things; b) naming things; and c) the standard 
> library... my questions are:
>
> Do specialised clever advanced mathsy libraries all work exactly the same, or 
> do they have slightly different behaviours or conventions or semantics in 
> different fields of study?
>
> Is the the goal here to define a common/shared sub-set of specialised maths 
> libraries, but in the standard library? Would that be useful by itself?
>
> Could it be possible that "naming things" in the standard library would 
> trample all over possible uses in external libraries, making it harder rather 
> than easier for specialised maths libraries to construct their interfaces in 
> a non-confusing way?
>
>
> On Tue, 17 Jan 2017 at 01:39 Dave Abrahams via swift-evolution 
> mailto:swift-evolution@swift.org)> wrote:
> >
> > on Mon Jan 16 2017, Xiaodi Wu  > (mailto:swift-evolution@swift.org)> wrote:
> >
> > > Strideable? I didn't think Strideable itself was going away. I'd be sad if
> > > it did; for one, all the Unsafe*Pointers are Strideable and that has its
> > > uses.
> >
> > Nobody's proposing to remove Strideable.
> >
> > --
> > -Dave
> >
> > ___
> > swift-evolution mailing list
> > swift-evolution@swift.org (mailto:swift-evolution@swift.org)
> > https://lists.swift.org/mailman/listinfo/swift-evolution
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

I can't speak to the core team's motivations, but what I'm hoping for
personally is a solution to this problem:

Currently, there are a bunch of protocols to which integer types conform.
However, they aren't very useful (not really usable) for generic
programming. One example: As an exercise, I tried to port a binary greatest
common denominator function to Swift, generic over SignedNumber. However, I
can't bit shift. I have to divide by two. Because << isn't required or
implemented for two SignedNumber values. This proposal arranges the cascade
of protocols to which integer types conform, and their requirements, so
that useful generic algorithms that use integers can be written without
retroactively conforming them to one's own made-up protocols every time.
Every so often one or two minor new facilities are thrown in that complete
the picture, but the biggest part of this proposal is the rearranging.

I don't read this proposal as having as a goal the implementation of
advanced math in the standard library. However, note that it is not
possible to retroactively use an existing protocol in the standard library
to refine your own protocol in another project. So, what's important is
that the protocols here don't gratuitously preclude (preclude for no
technically justifiable reason) the "plugging in" (conforming) of
third-party numeric types to standard library protocols, so that where
these types have the semantics required they too can be used with
algorithms written to be generic over types conforming to standard library
protocols.

I think the key question about "naming things" that's left over here is:
since our modeling of sets of infinitely many things (e.g. integers) is
necessarily imperfect on a machine with finite memory, is it wise to use
terms from mathematics that describe those infinitely many things for our
imperfect, finite models? For now, the proposal chooses deliberately less
"mathy" terms so that Swift doesn't (a) make these protocols impenetrable
to the average user; and (b) it doesn't overpromise and say that our
imperfect model of something is _the_ way to model that thing. Nonetheless,
these mathy terms describe some attributes of integers, real numbers, etc.,
that apply as much to the algorithms we may want to write in Swift as they
do to math. Therefore, I think we want to ensure that even as we don't
insist on "mathy" names, we absorb as avidly as we can the insights about
integer semantics that the mathematicians have worked out, in the hopes of
making our protocols maximally useful.

But you're precisely right that a laudable aim is to help, not hinder,
third-party library design.


On Mon, Jan 16, 2017 at 20:25 Jay Abbott via swift-evolution <
swift-evolution@swift.org> wrote:

> I barely understand any of this thread, so these might be silly questions,
> or based on a total misunderstanding the goals here, but it seems to be
> about: a) clever/advanced mathsy things; b) naming things; and c) the
> standard library... my questions are:
>
> Do specialised clever advanced mathsy libraries all work exactly the
>
> same, or do they have slightly different behaviours or conventions or
>
> semantics in different fields of study?
>
> Is the the goal here to define a common/shared
>
> sub-set of specialised maths libraries, but in the standard library? Would
> that be useful by itself?
>
> Could it be possible that "naming things" in the standard library would
> trample all over possible uses in external libraries, making it harder
> rather than easier for specialised maths libraries to construct their
> interfaces in a non-confusing way?
>
>
> On Tue, 17 Jan 2017 at 01:39 Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
>
>
> on Mon Jan 16 2017, Xiaodi Wu  wrote:
>
>
>
>
>
> > Strideable? I didn't think Strideable itself was going away. I'd be sad
> if
>
>
> > it did; for one, all the Unsafe*Pointers are Strideable and that has its
>
>
> > uses.
>
>
>
>
>
> Nobody's proposing to remove Strideable.
>
>
>
>
>
> --
>
>
> -Dave
>
>
>
>
>
> ___
>
>
> swift-evolution mailing list
>
>
> swift-evolution@swift.org
>
>
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
>
> ___
>
> swift-evolution mailing list
>
> swift-evolution@swift.org
>
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Ben Rimmington via swift-evolution]

public protocol Arithmetic {
  init?(exactly source: T)
}

public protocol BinaryInteger : Arithmetic {
  init?(exactly source: T)
}

Should the `init?(exactly:)` initializers belong to the same protocol?
Would this allow generic conversions between integer and floating-point types?
For example, a failable `numericCast` function.

-- Ben

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

Stephen Canon wrote that Arithmetic should refine
ExpressibleByIntegerLiteral because of certain mathematical properties of
rings. In that case, 0 and 1 would just be spelled in that way. Otherwise,
+1.
On Wed, Jan 25, 2017 at 11:38 Anton Mironov via swift-evolution <
swift-evolution@swift.org> wrote:

> Hi everyone,
>
> I want to suggest a tiny extension to an Arithmetic protocol. It would be
> nice to have an additive identity and a multiplicative identity constants.
> Basically zero and one.
>
> ```
> protocol Arithmetic {
>   /* ... */
>   static var zero: Self { get }  // additive identity: (value + .zero) ==
> value
>   static var one: Self { get }   // multiplicative identity: (value *
> .one) == value
> }
> ```
>
> These constants will ease implementation of math structures: vectors,
> matrices and etc.
> I’m sorry if I’m duplicating someone’s suggestion. It is really hard to
> search for something in a long thread.
>
> Thanks,
> Anton Mironov
>
>
> On Jan 13, 2017, at 10:47 PM, Max Moiseev via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Hi everyone,
>
> Back in June 2016 we discussed the new design of the integer types for the
> standard library. It even resulted in acceptance of SE-0104
> 
>  for
> Swift 3. Unfortunately we were not able to implement it in time for the
> release.
>
> But it was not forgotten, although, as time went by, a few changes needed
> to be made in order to reflect the current state of the language.
> Without further introduction, please welcome the refined proposal to make
> integers in Swift more suitable for generic programming.
>
> Available in this gist
> https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c and also
> inlined below.
>
> Max
>
> Protocol-oriented integers (take 2)
>
>- Proposal: SE-
>
>- Authors: Dave Abrahams , Maxim Moiseev
>
>- Review Manager: TBD
>- Status: Awaiting review
>- Bug: SR-3196 
>- Previous Proposal: SE-0104
>
>
>
> 
> Introduction
>
> This proposal is an evolution of SE-0104
> . The goal is
> still to clean up Swifts integer APIs and make them more useful for generic
> programming.
>
> The language has evolved in ways that affect integers APIs since the time
> the original proposal was approved for Swift 3. We also attempted to
> implement the proposed model in the standard library and found that some
> essential APIs were missing, whereas others could be safely removed.
>
> Major changes to the APIs introduced by this proposal (as compared to
> SE-0104 ) are
> listed in a dedicated section
> 
> .
>
> 
> Motivation
>
> Swift's integer protocols don't currently provide a suitable basis for
> generic programming. See this blog post
>  
> for
> an example of an attempt to implement a generic algorithm over integers.
>
> The way the Arithmetic protocol is defined, it does not generalize to
> floating point numbers and also slows down compilation by requiring every
> concrete type to provide an implementation of arithmetic operators, thus
> polluting the overload set.
>
> Converting from one integer type to another is performed using the concept
> of the 'maximum width integer' (see MaxInt), which is an artificial
> limitation. The very existence of MaxInt makes it unclear what to do
> should someone implement Int256, for example.
>
> Another annoying problem is the inability to use integers of different
> types in comparison and bit-shift operations. For example, the following
> snippets won't compile:
>
> var x: Int8 = 42let y = 1let z = 0
>
> x <<= y   // error: binary operator '<<=' cannot be applied to operands of 
> type 'Int8' and 'Int'if x > z { ... }  // error: binary operator '>' cannot 
> be applied to operands of type 'Int8' and 'Int'
>
> Currently, bit-shifting a negative number of (or too many) bits causes a
> trap on some platforms, which makes low-level bit manipulations needlessly
> dangerous and unpredictable.
>
> Finally, the current design predates many of the improvements that came
> since Swift 1, and hasn't been revised since then.
>
> Proposed
> solution
>
> We propose a new model that does not have above mentioned problems and is

Re: [swift-evolution] protocol-oriented integers (take 2)

[Tony Allevato via swift-evolution]

It should already be possible to handle special cases like that since you
can reässign self in an initializer. Here's a contrived example; would it
allay your performance concerns?

```
struct Foo: ExpressibleByIntegerLiteral {
private let value: String
private static let zero = Foo("a really big thing")

init(integerLiteral value: Int) {
if value == 0 {
self = .zero
} else {
self = Foo(String(value))
}
}

private init(_ value: String) {
self.value = value
}
}

let x: Foo = 5   // value = "5"
let y: Foo = 0   // value = "a really big thing"
```

Given that, I definitely prefer the more natural literal expressibility to
the words "zero" and "one".


On Wed, Jan 25, 2017 at 10:45 AM David Sweeris via swift-evolution <
swift-evolution@swift.org> wrote:

>
> On Jan 25, 2017, at 10:03, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Stephen Canon wrote that Arithmetic should refine
> ExpressibleByIntegerLiteral because of certain mathematical properties of
> rings. In that case, 0 and 1 would just be spelled in that way. Otherwise,
> +1.
> On Wed, Jan 25, 2017 at 11:38 Anton Mironov via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Hi everyone,
>
> I want to suggest a tiny extension to an Arithmetic protocol. It would be
> nice to have an additive identity and a multiplicative identity constants.
> Basically zero and one.
>
> ```
> protocol Arithmetic {
>   /* ... */
>   static var zero: Self { get }  // additive identity: (value + .zero) ==
> value
>   static var one: Self { get }   // multiplicative identity: (value *
> .one) == value
> }
> ```
>
> These constants will ease implementation of math structures: vectors,
> matrices and etc.
> I’m sorry if I’m duplicating someone’s suggestion. It is really hard to
> search for something in a long thread.
>
>
> There is some merit in having them be declared as static properties... If
> it's a non-trivial process to initialize a type, it might be worth it to
> have a static property that either provides the storage directly or just
> returns a fileprivate value declared outside the type.
>
> - Dave Sweeris
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 25, 2017, at 07:59, Anton Mironov via swift-evolution 
>  wrote:
> 
> Hi everyone,
> 
> I want to suggest a tiny extension to an Arithmetic protocol. It would be 
> nice to have an additive identity and a multiplicative identity constants. 
> Basically zero and one.
> 
> ```
> protocol Arithmetic {
>   /* ... */
>   static var zero: Self { get }  // additive identity: (value + .zero) == 
> value
>   static var one: Self { get }   // multiplicative identity: (value * .one) 
> == value
> }
> ```
> 
> These constants will ease implementation of math structures: vectors, 
> matrices and etc.
> I’m sorry if I’m duplicating someone’s suggestion. It is really hard to 
> search for something in a long thread.

Vectors, matrices, etc can't conform to this protocol anyway because of the * 
and / requirements. And while it is true that it's not uncommon to reference an 
all-zero matrix or vector as "0", that doesn't work for any other number... for 
them I think the spelling should be "additiveIdentity". It'll be easy enough to 
just say
protocol Addable {
static var additiveIdentity: Self {get}
...
}
extension Addable where Self: Arithmetic {
static var additiveIdentity: Self {return Self.zero}
}

IMHO, anyway.

- Dave Sweeris
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Steve Canon via swift-evolution]

Sent from my iPhone

> On Jan 25, 2017, at 1:45 PM, David Sweeris via swift-evolution 
>  wrote:
> 
> 
>> On Jan 25, 2017, at 10:03, Xiaodi Wu via swift-evolution 
>>  wrote:
>> 
>> Stephen Canon wrote that Arithmetic should refine 
>> ExpressibleByIntegerLiteral because of certain mathematical properties of 
>> rings. In that case, 0 and 1 would just be spelled in that way. Otherwise, 
>> +1.
>>> On Wed, Jan 25, 2017 at 11:38 Anton Mironov via swift-evolution 
>>>  wrote:
>>> Hi everyone,
>>> 
>>> I want to suggest a tiny extension to an Arithmetic protocol. It would be 
>>> nice to have an additive identity and a multiplicative identity constants. 
>>> Basically zero and one.
>>> 
>>> ```
>>> protocol Arithmetic {
>>>   /* ... */
>>>   static var zero: Self { get }  // additive identity: (value + .zero) == 
>>> value
>>>   static var one: Self { get }   // multiplicative identity: (value * .one) 
>>> == value
>>> }
>>> ```
>>> 
>>> These constants will ease implementation of math structures: vectors, 
>>> matrices and etc.
>>> I’m sorry if I’m duplicating someone’s suggestion. It is really hard to 
>>> search for something in a long thread.
> 
> There is some merit in having them be declared as static properties... If 
> it's a non-trivial process to initialize a type, it might be worth it to have 
> a static property that either provides the storage directly or just returns a 
> fileprivate value declared outside the type.

A type for which this was necessary can just special-case handling 0 and 1 
literals.___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Stephen Canon via swift-evolution]

> On Jan 25, 2017, at 1:58 PM, David Sweeris via swift-evolution 
>  wrote:
> 
> 
>> On Jan 25, 2017, at 07:59, Anton Mironov via swift-evolution 
>>  wrote:
>> 
>> Hi everyone,
>> 
>> I want to suggest a tiny extension to an Arithmetic protocol. It would be 
>> nice to have an additive identity and a multiplicative identity constants. 
>> Basically zero and one.
>> 
>> ```
>> protocol Arithmetic {
>>  /* ... */
>>  static var zero: Self { get }  // additive identity: (value + .zero) == 
>> value
>>  static var one: Self { get }   // multiplicative identity: (value * .one) 
>> == value
>> }
>> ```
>> 
>> These constants will ease implementation of math structures: vectors, 
>> matrices and etc.
>> I’m sorry if I’m duplicating someone’s suggestion. It is really hard to 
>> search for something in a long thread.
> 
> Vectors, matrices, etc can't conform to this protocol anyway because of the * 
> and / requirements. And while it is true that it's not uncommon to reference 
> an all-zero matrix or vector as "0", that doesn't work for any other 
> number... for them I think the spelling should be "additiveIdentity". It'll 
> be easy enough to just say
> protocol Addable {
>static var additiveIdentity: Self {get}
>...
> }
> extension Addable where Self: Arithmetic {
>static var additiveIdentity: Self {return Self.zero}
> }
> 
> IMHO, anyway.

1. Square matrices of fixed size can absolutely conform to this protocol 
(except for ‘/‘, as discussed earlier in the thread).

2. It’s pretty common to call the multiplicative identity matrix 1 (though “I” 
is more common). The rest of the integers map to square matrices in the obvious 
way n —> n*1 (i.e. the matrix with n on the main diagonal, and zeros elsewhere).

– Steve
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Anton Mironov via swift-evolution]

I wish I knew how to express those requirements in the type system.
This is a good way to implement additiveIdentity but I assume that Arithmetic 
protocol implies behavior of Addable.


> On Jan 25, 2017, at 20:58, David Sweeris  wrote:
> 
>> 
>> On Jan 25, 2017, at 07:59, Anton Mironov via swift-evolution 
>>  wrote:
>> 
>> Hi everyone,
>> 
>> I want to suggest a tiny extension to an Arithmetic protocol. It would be 
>> nice to have an additive identity and a multiplicative identity constants. 
>> Basically zero and one.
>> 
>> ```
>> protocol Arithmetic {
>>  /* ... */
>>  static var zero: Self { get }  // additive identity: (value + .zero) == 
>> value
>>  static var one: Self { get }   // multiplicative identity: (value * .one) 
>> == value
>> }
>> ```
>> 
>> These constants will ease implementation of math structures: vectors, 
>> matrices and etc.
>> I’m sorry if I’m duplicating someone’s suggestion. It is really hard to 
>> search for something in a long thread.
> 
> Vectors, matrices, etc can't conform to this protocol anyway because of the * 
> and / requirements. And while it is true that it's not uncommon to reference 
> an all-zero matrix or vector as "0", that doesn't work for any other 
> number... for them I think the spelling should be "additiveIdentity". It'll 
> be easy enough to just say
> protocol Addable {
>static var additiveIdentity: Self {get}
>...
> }
> extension Addable where Self: Arithmetic {
>static var additiveIdentity: Self {return Self.zero}
> }
> 
> IMHO, anyway.
> 
> - Dave Sweeris

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 25, 2017, at 10:03, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> Stephen Canon wrote that Arithmetic should refine ExpressibleByIntegerLiteral 
> because of certain mathematical properties of rings. In that case, 0 and 1 
> would just be spelled in that way. Otherwise, +1.
>> On Wed, Jan 25, 2017 at 11:38 Anton Mironov via swift-evolution 
>>  wrote:
>> Hi everyone,
>> 
>> I want to suggest a tiny extension to an Arithmetic protocol. It would be 
>> nice to have an additive identity and a multiplicative identity constants. 
>> Basically zero and one.
>> 
>> ```
>> protocol Arithmetic {
>>   /* ... */
>>   static var zero: Self { get }  // additive identity: (value + .zero) == 
>> value
>>   static var one: Self { get }   // multiplicative identity: (value * .one) 
>> == value
>> }
>> ```
>> 
>> These constants will ease implementation of math structures: vectors, 
>> matrices and etc.
>> I’m sorry if I’m duplicating someone’s suggestion. It is really hard to 
>> search for something in a long thread.

There is some merit in having them be declared as static properties... If it's 
a non-trivial process to initialize a type, it might be worth it to have a 
static property that either provides the storage directly or just returns a 
fileprivate value declared outside the type.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 15 2017, Stephen Canon  wrote:

> Responding to the thread in general here, not so much any specific email:
>
> “Arithmetic” at present is not a mathematically-precise concept, and
> it may be a mistake to make it be one[1]; it’s a
> mathematically-slightly-fuzzy “number” protocol. 


In that case, should we consider renaming it to “Numeric” or even
“Number?”  That would at least remove the question about how to
pronounce it.


-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[T.J. Usiyan via swift-evolution]

Regarding `Number` or `Numeric`: Does everything in Arithmetic apply to
complex numbers and do we want it to? The bitwise stuff is where I think
that there might be a mismatch.



On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution <
swift-evolution@swift.org> wrote:

>
> on Sun Jan 15 2017, Stephen Canon  wrote:
>
> > Responding to the thread in general here, not so much any specific email:
> >
> > “Arithmetic” at present is not a mathematically-precise concept, and
> > it may be a mistake to make it be one[1]; it’s a
> > mathematically-slightly-fuzzy “number” protocol.
>
>
> In that case, should we consider renaming it to “Numeric” or even
> “Number?”  That would at least remove the question about how to
> pronounce it.
>
>
> --
> -Dave
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Stephen Canon via swift-evolution]

The bitwise stuff isn't on ArithMETic | ARITHmetic | Number | whatever.

> On Jan 27, 2017, at 9:13 AM, T.J. Usiyan via swift-evolution 
>  wrote:
> 
> Regarding `Number` or `Numeric`: Does everything in Arithmetic apply to 
> complex numbers and do we want it to? The bitwise stuff is where I think that 
> there might be a mismatch.
> 
> On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution 
> mailto:swift-evolution@swift.org>> wrote:
> 
> on Sun Jan 15 2017, Stephen Canon  > wrote:
> 
> > Responding to the thread in general here, not so much any specific email:
> >
> > “Arithmetic” at present is not a mathematically-precise concept, and
> > it may be a mistake to make it be one[1]; it’s a
> > mathematically-slightly-fuzzy “number” protocol.
> 
> 
> In that case, should we consider renaming it to “Numeric” or even
> “Number?”  That would at least remove the question about how to
> pronounce it.
> 
> 
> --
> -Dave
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org 
> https://lists.swift.org/mailman/listinfo/swift-evolution 
> 
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[T.J. Usiyan via swift-evolution]

Oh, I misread the arrows in that diagram and this makes much more sense now.

Thanks.

On Fri, Jan 27, 2017 at 9:14 AM, Stephen Canon  wrote:

> The bitwise stuff isn't on ArithMETic | ARITHmetic | Number | whatever.
>
> On Jan 27, 2017, at 9:13 AM, T.J. Usiyan via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Regarding `Number` or `Numeric`: Does everything in Arithmetic apply to
> complex numbers and do we want it to? The bitwise stuff is where I think
> that there might be a mismatch.
>
> On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>>
>> on Sun Jan 15 2017, Stephen Canon  wrote:
>>
>> > Responding to the thread in general here, not so much any specific
>> email:
>> >
>> > “Arithmetic” at present is not a mathematically-precise concept, and
>> > it may be a mistake to make it be one[1]; it’s a
>> > mathematically-slightly-fuzzy “number” protocol.
>>
>>
>> In that case, should we consider renaming it to “Numeric” or even
>> “Number?”  That would at least remove the question about how to
>> pronounce it.
>>
>>
>> --
>> -Dave
>>
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

I'd always just assumed that Arithmetic was chosen so that SignedArithmetic
wouldn't clash with the old SignedNumber. If that's not an issue,
definitely agree that Number is the superior name.
On Fri, Jan 27, 2017 at 08:30 T.J. Usiyan via swift-evolution <
swift-evolution@swift.org> wrote:

> Oh, I misread the arrows in that diagram and this makes much more sense
> now.
>
> Thanks.
>
> On Fri, Jan 27, 2017 at 9:14 AM, Stephen Canon  wrote:
>
> The bitwise stuff isn't on ArithMETic | ARITHmetic | Number | whatever.
>
> On Jan 27, 2017, at 9:13 AM, T.J. Usiyan via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Regarding `Number` or `Numeric`: Does everything in Arithmetic apply to
> complex numbers and do we want it to? The bitwise stuff is where I think
> that there might be a mismatch.
>
> On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> on Sun Jan 15 2017, Stephen Canon  wrote:
>
> > Responding to the thread in general here, not so much any specific email:
> >
> > “Arithmetic” at present is not a mathematically-precise concept, and
> > it may be a mistake to make it be one[1]; it’s a
> > mathematically-slightly-fuzzy “number” protocol.
>
>
> In that case, should we consider renaming it to “Numeric” or even
> “Number?”  That would at least remove the question about how to
> pronounce it.
>
>
> --
> -Dave
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Max Moiseev via swift-evolution]

Renaming Arithmetic to Number (and having SignedNumber) might actually end up 
being a win, since we need to provide SignedNumber to maintain source code 
compatibility anyway.

> On Jan 27, 2017, at 8:34 AM, Xiaodi Wu via swift-evolution 
>  wrote:
> 
> I'd always just assumed that Arithmetic was chosen so that SignedArithmetic 
> wouldn't clash with the old SignedNumber. If that's not an issue, definitely 
> agree that Number is the superior name.
> On Fri, Jan 27, 2017 at 08:30 T.J. Usiyan via swift-evolution 
> mailto:swift-evolution@swift.org>> wrote:
> Oh, I misread the arrows in that diagram and this makes much more sense now.
> 
> Thanks.
> 
> On Fri, Jan 27, 2017 at 9:14 AM, Stephen Canon  > wrote:
> The bitwise stuff isn't on ArithMETic | ARITHmetic | Number | whatever.
> 
>> On Jan 27, 2017, at 9:13 AM, T.J. Usiyan via swift-evolution 
>> mailto:swift-evolution@swift.org>> wrote:
>> 
>> Regarding `Number` or `Numeric`: Does everything in Arithmetic apply to 
>> complex numbers and do we want it to? The bitwise stuff is where I think 
>> that there might be a mismatch.
>> 
>> On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution 
>> mailto:swift-evolution@swift.org>> wrote:
>> 
>> on Sun Jan 15 2017, Stephen Canon > > wrote:
>> 
>> > Responding to the thread in general here, not so much any specific email:
>> >
>> > “Arithmetic” at present is not a mathematically-precise concept, and
>> > it may be a mistake to make it be one[1]; it’s a
>> > mathematically-slightly-fuzzy “number” protocol.
>> 
>> 
>> In that case, should we consider renaming it to “Numeric” or even
>> “Number?”  That would at least remove the question about how to
>> pronounce it.
>> 
>> 
>> --
>> -Dave
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org 
>> https://lists.swift.org/mailman/listinfo/swift-evolution 
>> 
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org 
>> https://lists.swift.org/mailman/listinfo/swift-evolution 
>> 
> 
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org 
> https://lists.swift.org/mailman/listinfo/swift-evolution 
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Brent Royal-Gordon via swift-evolution]

> On Jan 13, 2017, at 12:47 PM, Max Moiseev via swift-evolution 
>  wrote:
> 
> Protocol-oriented integers (take 2)
> 
>   • Proposal: SE-
>   • Authors: Dave Abrahams, Maxim Moiseev
>   • Review Manager: TBD
>   • Status: Awaiting review
>   • Bug: SR-3196
>   • Previous Proposal: SE-0104

Definitely liking what I'm seeing here.

> public protocol Arithmetic : Equatable, ExpressibleByIntegerLiteral 
> {

Is there a reason `Arithmetic` is not `Hashable`? (I think `Comparable` isn't 
here because complex numbers can't be compared, but correct me if I'm wrong 
about that.)

> /// A type that can represent the absolute value of any possible value of the
>   /// conforming type.
>   associatedtype Magnitude : Equatable, ExpressibleByIntegerLiteral

Is there a reason not to have this be `Arithmetic`? Maybe just the circularity 
problem?

> /// Returns the n-th word, counting from the least significant to most
>   /// significant, of this value's binary representation.
>   ///
>   /// The `word(at:)` method returns negative values in two's complement
>   /// representation, regardless of a type's underlying implementation. If `n`
>   /// is greater than the number of words in this value's current
>   /// representation, the result is `0` for positive numbers and `~0` for
>   /// negative numbers.
>   ///
>   /// - Parameter n: The word to return, counting from the least significant 
> to
>   ///   most significant. `n` must be greater than or equal to zero.
>   /// - Returns: An word-sized, unsigned integer with the bit pattern of the
>   ///   n-th word of this value.
>   func word(at n: Int) -> UInt

How does the client know how many words there are? Are they supposed to 
calculate that from `bitWidth`?

Oh, I see:

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

That looks fine to me.

> /// The number of bits in the current binary representation of this value.
>   ///
>   /// This property is a constant for instances of fixed-width integer
>   /// types.
>   var bitWidth : Int { get }

So, um, I'm a little confused about this one. Is this the physical number of 
bits in the value, or is it the number of bits you need to get from `word(at:)` 
in order to get all bits representing the value?

For instance, when you call `UInt32.bitWidth`, does it return `32`, the 
physical number of bits in the value, or `33`, the number of bits including the 
(always zero) sign bit?

>   static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -> (high: Self, 
> low: Magnitude)
>   static func doubleWidthDivide(_ lhs: (high: Self, low: Magnitude), _ rhs: 
> Self) -> (quotient: Self, remainder: Self)

Could these take/return a single `DoubleWidth` value instead of two 
separate `Self` and `Magnitude` values? Or would that present circularity 
problems?

> /// The number of bits equal to 1 in this value's binary representation.
>   ///
>   /// For example, in a fixed-width integer type with a `bitWidth` value of 8,
>   /// the number 31 has five bits equal to 1.
>   ///
>   /// let x: Int8 = 0b0001_
>   /// // x == 31
>   /// // x.popcount == 5
>   var popcount: Int { get }

I'm not super-fond of this name; I assume it's a term of art, but it's a pretty 
obscure one. Maybe `numberOfOnes`? `onesWithin`?

> DoubleWidth
> 
> The DoubleWidth type allows to create wider fixed-width integer types from 
> the ones available in the standard library.

I'm glad you're planning to include `DoubleWidth` this time.

>   • Deprecation of the BitwiseOperations protocol. We find it hard to 
> imagine a type that conforms to this protocol, but is not a binary integer 
> type.

While I'm sure any such type *could* be a binary integer type, I'm not 
convinced they necessary *should* be. For instance, suppose I have a "bit 
vector"; I know I never want to perform arithmetic on it, but I *do* want to 
manipulate bits separately, so I make it look like a `RandomAccessCollection` 
of `Bool`s. It might make a great deal of sense to support bitwise operations 
on this type, even though I don't want to clutter it up with arithmetic.

-- 
Brent Royal-Gordon
Architechies

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Sun, Jan 29, 2017 at 6:02 AM, Brent Royal-Gordon via swift-evolution <
swift-evolution@swift.org> wrote:

>
> > On Jan 13, 2017, at 12:47 PM, Max Moiseev via swift-evolution <
> swift-evolution@swift.org> wrote:
> >
> > Protocol-oriented integers (take 2)
> >
> >   • Proposal: SE-
> >   • Authors: Dave Abrahams, Maxim Moiseev
> >   • Review Manager: TBD
> >   • Status: Awaiting review
> >   • Bug: SR-3196
> >   • Previous Proposal: SE-0104
>
> Definitely liking what I'm seeing here.
>
> > public protocol Arithmetic : Equatable, ExpressibleByIntegerLiteral
> > {
>
> Is there a reason `Arithmetic` is not `Hashable`? (I think `Comparable`
> isn't here because complex numbers can't be compared, but correct me if I'm
> wrong about that.)
>
> > /// A type that can represent the absolute value of any possible value
> of the
> >   /// conforming type.
> >   associatedtype Magnitude : Equatable, ExpressibleByIntegerLiteral
>
> Is there a reason not to have this be `Arithmetic`? Maybe just the
> circularity problem?
>
> > /// Returns the n-th word, counting from the least significant to most
> >   /// significant, of this value's binary representation.
> >   ///
> >   /// The `word(at:)` method returns negative values in two's complement
> >   /// representation, regardless of a type's underlying implementation.
> If `n`
> >   /// is greater than the number of words in this value's current
> >   /// representation, the result is `0` for positive numbers and `~0` for
> >   /// negative numbers.
> >   ///
> >   /// - Parameter n: The word to return, counting from the least
> significant to
> >   ///   most significant. `n` must be greater than or equal to zero.
> >   /// - Returns: An word-sized, unsigned integer with the bit pattern of
> the
> >   ///   n-th word of this value.
> >   func word(at n: Int) -> UInt
>
> How does the client know how many words there are? Are they supposed to
> calculate that from `bitWidth`?
>
> Oh, I see:
>
> > 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.
>
> That looks fine to me.
>
> > /// The number of bits in the current binary representation of this
> value.
> >   ///
> >   /// This property is a constant for instances of fixed-width integer
> >   /// types.
> >   var bitWidth : Int { get }
>
> So, um, I'm a little confused about this one. Is this the physical number
> of bits in the value, or is it the number of bits you need to get from
> `word(at:)` in order to get all bits representing the value?
>
> For instance, when you call `UInt32.bitWidth`, does it return `32`, the
> physical number of bits in the value, or `33`, the number of bits including
> the (always zero) sign bit?
>

Could you comment on what use cases would make `33` the relevant answer?
I'd always thought that "the number of bits in the current binary
representation" admits of no alternative interpretation than `32` in your
example.


> >   static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -> (high:
> Self, low: Magnitude)
> >   static func doubleWidthDivide(_ lhs: (high: Self, low: Magnitude), _
> rhs: Self) -> (quotient: Self, remainder: Self)
>
> Could these take/return a single `DoubleWidth` value instead of two
> separate `Self` and `Magnitude` values? Or would that present circularity
> problems?


Having mulled the idea of implementing an IEEE Decimal type, I'd be sad to
see these return DoubleWidth. Double-width multiply as it is here is
useful when you want to get the result and immediately discard either the
high or the low bits, for instance. If you'd want a result of type
`DoubleWidth` instead, you could always just write
`DoubleWidth(a) * DoubleWidth(b)`.


> > /// The number of bits equal to 1 in this value's binary representation.
> >   ///
> >   /// For example, in a fixed-width integer type with a `bitWidth` value
> of 8,
> >   /// the number 31 has five bits equal to 1.
> >   ///
> >   /// let x: Int8 = 0b0001_
> >   /// // x == 31
> >   /// // x.popcount == 5
> >   var popcount: Int { get }
>
> I'm not super-fond of this name; I assume it's a term of art, but it's a
> pretty obscure one. Maybe `numberOfOnes`? `onesWithin`?


Far less obscure than `ulp` in `FloatingPoint`!

I think `popcount` is by far the most appropriate name here. It uses
`count`, which is rather consistent with existing Swift APIs, and it is a
visually recognizable term of art (note the absence of capitalization on
"count"). I think a useful barometer for the appropriateness of a term of
art is three-pronged:

* People who know of this concept (the population count of a binary
integer) will almost invariably know it as `popcount`. (Really, if you're
working with binary integers as a collection of bits, you will likely
encounter the term if you look for useful algorithms).

* Those who do not can immediately get all 

Re: [swift-evolution] protocol-oriented integers (take 2)

[Jonathan Hull via swift-evolution]

Shouldn’t “Number” be reserved for a foundation type similar to NSNumber?  Or 
would this protocol actually serve that purpose?

I was planning to ask for a value type similar to NSNumber in phase 2.  I built 
one for my own code (a struct around an enum which can be Int, Decimal, 
Rational, or Rational * π) and it is super useful for handling things like user 
input where the value could be an Integer or Float/Decimal, and I always want 
the highest precision until I ask for it in a particular form.  If it came in 
as an integer, I know I can present it as an integer, and vice versa with 
decimal numbers.

Sometimes it is nice to be able to say: “The user gave me a number” and not 
really care about the underlying representation...

Thanks,
Jon



> On Jan 27, 2017, at 4:50 PM, Max Moiseev via swift-evolution 
>  wrote:
> 
> Renaming Arithmetic to Number (and having SignedNumber) might actually end up 
> being a win, since we need to provide SignedNumber to maintain source code 
> compatibility anyway.
> 
>> On Jan 27, 2017, at 8:34 AM, Xiaodi Wu via swift-evolution 
>> mailto:swift-evolution@swift.org>> wrote:
>> 
>> I'd always just assumed that Arithmetic was chosen so that SignedArithmetic 
>> wouldn't clash with the old SignedNumber. If that's not an issue, definitely 
>> agree that Number is the superior name.
>> On Fri, Jan 27, 2017 at 08:30 T.J. Usiyan via swift-evolution 
>> mailto:swift-evolution@swift.org>> wrote:
>> Oh, I misread the arrows in that diagram and this makes much more sense now.
>> 
>> Thanks.
>> 
>> On Fri, Jan 27, 2017 at 9:14 AM, Stephen Canon > > wrote:
>> The bitwise stuff isn't on ArithMETic | ARITHmetic | Number | whatever.
>> 
>>> On Jan 27, 2017, at 9:13 AM, T.J. Usiyan via swift-evolution 
>>> mailto:swift-evolution@swift.org>> wrote:
>>> 
>>> Regarding `Number` or `Numeric`: Does everything in Arithmetic apply to 
>>> complex numbers and do we want it to? The bitwise stuff is where I think 
>>> that there might be a mismatch.
>>> 
>>> On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution 
>>> mailto:swift-evolution@swift.org>> wrote:
>>> 
>>> on Sun Jan 15 2017, Stephen Canon >> > wrote:
>>> 
>>> > Responding to the thread in general here, not so much any specific email:
>>> >
>>> > “Arithmetic” at present is not a mathematically-precise concept, and
>>> > it may be a mistake to make it be one[1]; it’s a
>>> > mathematically-slightly-fuzzy “number” protocol.
>>> 
>>> 
>>> In that case, should we consider renaming it to “Numeric” or even
>>> “Number?”  That would at least remove the question about how to
>>> pronounce it.
>>> 
>>> 
>>> --
>>> -Dave
>>> 
>>> ___
>>> swift-evolution mailing list
>>> swift-evolution@swift.org 
>>> https://lists.swift.org/mailman/listinfo/swift-evolution 
>>> 
>>> 
>>> ___
>>> swift-evolution mailing list
>>> swift-evolution@swift.org 
>>> https://lists.swift.org/mailman/listinfo/swift-evolution 
>>> 
>> 
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org 
>> https://lists.swift.org/mailman/listinfo/swift-evolution 
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org 
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

I think these protocols + generics should cover most such use cases, no?


On Sun, Jan 29, 2017 at 06:57 Jonathan Hull  wrote:

> Shouldn’t “Number” be reserved for a foundation type similar to NSNumber?
> Or would this protocol actually serve that purpose?
>
> I was planning to ask for a value type similar to NSNumber in phase 2.  I
> built one for my own code (a struct around an enum which can be Int,
> Decimal, Rational, or Rational * π) and it is super useful for handling
> things like user input where the value could be an Integer or
> Float/Decimal, and I always want the highest precision until I ask for it
> in a particular form.  If it came in as an integer, I know I can present it
> as an integer, and vice versa with decimal numbers.
>
> Sometimes it is nice to be able to say: “The user gave me a number” and
> not really care about the underlying representation...
>
> Thanks,
> Jon
>
>
>
>
> On Jan 27, 2017, at 4:50 PM, Max Moiseev via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Renaming Arithmetic to Number (and having SignedNumber) might actually end
> up being a win, since we need to provide SignedNumber to maintain source
> code compatibility anyway.
>
> On Jan 27, 2017, at 8:34 AM, Xiaodi Wu via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> I'd always just assumed that Arithmetic was chosen so that
> SignedArithmetic wouldn't clash with the old SignedNumber. If that's not an
> issue, definitely agree that Number is the superior name.
> On Fri, Jan 27, 2017 at 08:30 T.J. Usiyan via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Oh, I misread the arrows in that diagram and this makes much more sense
> now.
>
> Thanks.
>
> On Fri, Jan 27, 2017 at 9:14 AM, Stephen Canon  wrote:
>
> The bitwise stuff isn't on ArithMETic | ARITHmetic | Number | whatever.
>
> On Jan 27, 2017, at 9:13 AM, T.J. Usiyan via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Regarding `Number` or `Numeric`: Does everything in Arithmetic apply to
> complex numbers and do we want it to? The bitwise stuff is where I think
> that there might be a mismatch.
>
> On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>
> on Sun Jan 15 2017, Stephen Canon  wrote:
>
> > Responding to the thread in general here, not so much any specific email:
> >
> > “Arithmetic” at present is not a mathematically-precise concept, and
> > it may be a mistake to make it be one[1]; it’s a
> > mathematically-slightly-fuzzy “number” protocol.
>
>
> In that case, should we consider renaming it to “Numeric” or even
> “Number?”  That would at least remove the question about how to
> pronounce it.
>
>
> --
> -Dave
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 13, 2017, at 12:47, Max Moiseev via swift-evolution 
>  wrote:

> DoubleWidth
> The DoubleWidth type allows to create wider fixed-width integer types from 
> the ones available in the standard library.
> 
> Standard library currently provides fixed-width integer types of up to 64 
> bits. A value of DoubleWidth will double the range of the underlying 
> type and implement all the FixedWidthInteger requirements. Please note though 
> that the implementation will not necessarily be the most efficient one, so it 
> would not be a good idea to use DoubleWidthinstead of a built-in Int64.
> 

What about having a "CompoundBinaryInteger" type, and then do "typealias 
DoubleWidth = CompoundBinaryInteger"? That would make it easier to 
have, say, 40-bit ints, "CompoundBinaryInteger", while still having 
the convenience of "DoubleWidth".

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

Hmm, interesting. I might be tempted to use a 40-bit type for large arrays,
but the performance hit for any useful computation over a large array would
probably tilt heavily in favor of plain 64-bit integers. What's your use
case for such a 40-bit type? And is it common enough to justify such a
facility in the stdlib vs. providing the tools to build it yourself?

On Sun, Jan 29, 2017 at 12:29 David Sweeris via swift-evolution <
swift-evolution@swift.org> wrote:

>
> On Jan 13, 2017, at 12:47, Max Moiseev via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> DoubleWidth
>
> The DoubleWidth type allows to create wider fixed-width integer types
> from the ones available in the standard library.
>
> Standard library currently provides fixed-width integer types of up to 64
> bits. A value of DoubleWidth will double the range of the
> underlying type and implement all the FixedWidthInteger requirements. *Please
> note* though that the implementation will not necessarily be the most
> efficient one, so it would not be a good idea to use DoubleWidthinstead
> of a built-in Int64.
>
>
> What about having a "CompoundBinaryInteger" type, and then do
> "typealias DoubleWidth = CompoundBinaryInteger"? That would make it
> easier to have, say, 40-bit ints, "CompoundBinaryInteger",
> while still having the convenience of "DoubleWidth".
>
> - Dave Sweeris
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 29 2017, Jonathan Hull  wrote:

> Shouldn’t “Number” be reserved for a foundation type similar to
> NSNumber?  Or would this protocol actually serve that purpose?

I don't think so.  What is the purpose of NSNumber?  I always viewed it
as being, approximately, a box that allows us to put numerical values
into NSArrays.

> I was planning to ask for a value type similar to NSNumber in phase 2.
> I built one for my own code (a struct around an enum which can be Int,
> Decimal, Rational, or Rational * π) and it is super useful for
> handling things like user input where the value could be an Integer or
> Float/Decimal, and I always want the highest precision until I ask for
> it in a particular form.  If it came in as an integer, I know I can
> present it as an integer, and vice versa with decimal numbers.

That sounds like exactly the right way to handle your scenario, and your
use case wouldn't be served by NSNumber.  If we invented an
NSNumber-like thing to serve your use case, it wouldn't serve someone
else's.

> Sometimes it is nice to be able to say: “The user gave me a number”
> and not really care about the underlying representation...

But it seems to me that you do care, very much, because you're trying to
avoid losing precision from one of several possible input formats.

I mean, if you wanted you could do this:

  struct AnyNumber {
public init(_ n: N) {
  self._value = n
}
public func unwwrapped(as: N.Type) -> N? {
   return self._value as? N
}
private let _value: Any
  }

but there's not all that much you can do with something like this.

> Thanks,
> Jon
>
>> On Jan 27, 2017, at 4:50 PM, Max Moiseev via swift-evolution 
>>  wrote:
>> 
>> Renaming Arithmetic to Number (and having SignedNumber) might
>> actually end up being a win, since we need to provide SignedNumber
>> to maintain source code compatibility anyway.
>> 
>>> On Jan 27, 2017, at 8:34 AM, Xiaodi Wu via swift-evolution
>>> mailto:swift-evolution@swift.org>>
>>> wrote:
>>> 
>>> I'd always just assumed that Arithmetic was chosen so that
>>> SignedArithmetic wouldn't clash with the old SignedNumber. If
>>> that's not an issue, definitely agree that Number is the superior
>>> name.
>>> On Fri, Jan 27, 2017 at 08:30 T.J. Usiyan via swift-evolution
>>> mailto:swift-evolution@swift.org>>
>>> wrote:
>>> Oh, I misread the arrows in that diagram and this makes much more sense now.
>>> 
>>> Thanks.
>>> 
>>> On Fri, Jan 27, 2017 at 9:14 AM, Stephen Canon >> > wrote:
>>> The bitwise stuff isn't on ArithMETic | ARITHmetic | Number | whatever.
>>> 
 On Jan 27, 2017, at 9:13 AM, T.J. Usiyan via swift-evolution
 mailto:swift-evolution@swift.org>>
 wrote:
 
 Regarding `Number` or `Numeric`: Does everything in Arithmetic
 apply to complex numbers and do we want it to? The bitwise stuff
 is where I think that there might be a mismatch.
 
 On Thu, Jan 26, 2017 at 2:26 PM, Dave Abrahams via swift-evolution
 mailto:swift-evolution@swift.org>>
 wrote:
 
 on Sun Jan 15 2017, Stephen Canon >>> > wrote:
 
 > Responding to the thread in general here, not so much any specific email:
 >
 > “Arithmetic” at present is not a mathematically-precise concept, and
 > it may be a mistake to make it be one[1]; it’s a
 > mathematically-slightly-fuzzy “number” protocol.
 
 
 In that case, should we consider renaming it to “Numeric” or even
 “Number?”  That would at least remove the question about how to
 pronounce it.
 
 
 --
 -Dave
 
 ___
 swift-evolution mailing list
 swift-evolution@swift.org 
 https://lists.swift.org/mailman/listinfo/swift-evolution 
 
 
 ___
 swift-evolution mailing list
 swift-evolution@swift.org 
 https://lists.swift.org/mailman/listinfo/swift-evolution 
 
>>> 
>>> 
>>> ___
>>> swift-evolution mailing list
>>> swift-evolution@swift.org 
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
>>> ___
>>> swift-evolution mailing list
>>> swift-evolution@swift.org 
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave
___
swift-evolution mailing list
swift-evolution@swift.org
http

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 29, 2017, at 10:36, Xiaodi Wu  wrote:
> 
> Hmm, interesting. I might be tempted to use a 40-bit type for large arrays, 
> but the performance hit for any useful computation over a large array would 
> probably tilt heavily in favor of plain 64-bit integers. What's your use case 
> for such a 40-bit type? And is it common enough to justify such a facility in 
> the stdlib vs. providing the tools to build it yourself?

I can think of two use-cases. One — saving memory for large #s of allocations — 
you already mentioned. The other is for easing interactions with on-disk data. 
For example, if you're working with some format that has 24-bit ints, you could 
use "CompoundWhateverItWasCalled". It doesn't make much difference 
when you're loading the data, but when you're writing it back out, you wouldn't 
have to worry about trimming that last byte or what to do if the value won't 
fit in 24 bits. I mean, obviously you'd still have to handle it, but the 
overflow would happen in the calculation that causes it rather then while 
you're busy doing something else.

In terms of justification, I think probably all I can offer is that I think it 
wouldn't be materially harder or less efficient to implement this than it would 
be to write a "DoubleWidth" type... It's extra functionality for free, at 
least in terms of effort. It would increase the API surface, but not by much. 
Assuming that "DoubleWidth" could just be a typealias, that is. If I'm wrong 
about it being "that easy", then I don't think it'd be worth it. As you noted, 
it is somewhat niche.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Sun, Jan 29, 2017 at 2:03 PM, David Sweeris  wrote:

>
> On Jan 29, 2017, at 10:36, Xiaodi Wu  wrote:
>
> Hmm, interesting. I might be tempted to use a 40-bit type for large
> arrays, but the performance hit for any useful computation over a large
> array would probably tilt heavily in favor of plain 64-bit integers. What's
> your use case for such a 40-bit type? And is it common enough to justify
> such a facility in the stdlib vs. providing the tools to build it yourself?
>
>>
> I can think of two use-cases. One — saving memory for large #s of
> allocations — you already mentioned. The other is for easing interactions
> with on-disk data. For example, if you're working with some format that has
> 24-bit ints, you could use "CompoundWhateverItWasCalled". It
> doesn't make much difference when you're loading the data, but when you're
> writing it back out, you wouldn't have to worry about trimming that last
> byte or what to do if the value won't fit in 24 bits. I mean, obviously
> you'd still have to handle it, but the overflow would happen in the
> calculation that causes it rather then while you're busy doing something
> else.
>
> In terms of justification, I think probably all I can offer is that I
> *think* it wouldn't be materially harder or less efficient to implement
> this than it would be to write a "DoubleWidth" type... It's extra
> functionality for free, at least in terms of effort. It would increase the
> API surface, but not by much. Assuming that "DoubleWidth" could just be a
> typealias, that is. If I'm wrong about it being "that easy", then I don't
> think it'd be worth it. As you noted, it is somewhat niche.
>

Unless I'm mistaken, DoubleWidth would be implemented using
doubleWidthMultiply and doubleWidthDivide facilities provided in these new
integer protocols. As the protocol documentation says, DoubleWidth is
really intended for wider types, not arbitrarily sized narrower
ones. There's no obvious way I can see to implement the same thing for two
types of unequal bit width, short of determining dynamically, at each
operation, which of your two types has the larger bit width and truncating
bits accordingly. So if you want a 24-bit Int, it's unclear to me why you'd
choose what's effectively DoubleWidth minus 8 bits rather than Int32
minus 8 bits.
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[David Sweeris via swift-evolution]

> On Jan 29, 2017, at 12:13, Xiaodi Wu  wrote:
> 
>> On Sun, Jan 29, 2017 at 2:03 PM, David Sweeris  wrote:
>> 
>>> On Jan 29, 2017, at 10:36, Xiaodi Wu  wrote:
>>> 
>>> Hmm, interesting. I might be tempted to use a 40-bit type for large arrays, 
>>> but the performance hit for any useful computation over a large array would 
>>> probably tilt heavily in favor of plain 64-bit integers. What's your use 
>>> case for such a 40-bit type? And is it common enough to justify such a 
>>> facility in the stdlib vs. providing the tools to build it yourself?
>> 
>> I can think of two use-cases. One — saving memory for large #s of 
>> allocations — you already mentioned. The other is for easing interactions 
>> with on-disk data. For example, if you're working with some format that has 
>> 24-bit ints, you could use "CompoundWhateverItWasCalled". It 
>> doesn't make much difference when you're loading the data, but when you're 
>> writing it back out, you wouldn't have to worry about trimming that last 
>> byte or what to do if the value won't fit in 24 bits. I mean, obviously 
>> you'd still have to handle it, but the overflow would happen in the 
>> calculation that causes it rather then while you're busy doing something 
>> else.
>> 
>> In terms of justification, I think probably all I can offer is that I think 
>> it wouldn't be materially harder or less efficient to implement this than it 
>> would be to write a "DoubleWidth" type... It's extra functionality for 
>> free, at least in terms of effort. It would increase the API surface, but 
>> not by much. Assuming that "DoubleWidth" could just be a typealias, that is. 
>> If I'm wrong about it being "that easy", then I don't think it'd be worth 
>> it. As you noted, it is somewhat niche.
> 
> Unless I'm mistaken, DoubleWidth would be implemented using 
> doubleWidthMultiply and doubleWidthDivide facilities provided in these new 
> integer protocols. As the protocol documentation says, DoubleWidth is really 
> intended for wider types, not arbitrarily sized narrower ones. There's no 
> obvious way I can see to implement the same thing for two types of unequal 
> bit width, short of determining dynamically, at each operation, which of your 
> two types has the larger bit width and truncating bits accordingly. So if you 
> want a 24-bit Int, it's unclear to me why you'd choose what's effectively 
> DoubleWidth minus 8 bits rather than Int32 minus 8 bits.

It's a trade-off between computationally efficiency and memory/storage 
efficiency. If you want your answer sooner, pick Int32, accept that you're 
"wasting" a byte, and manually trim the value later. If you'd rather have your 
24-bit int only actually take up 24 bits or not have to worry about its value 
taking more than 24 bits, pick the other one.

I'll have to look at the doubleWidthMultiply/Divide functions later when I get 
home. Don't know if they'd actually throw a wrench in my crazy scheme, or if 
it's all just in the name. If this causes any problems for DoubleWidth, I don't 
think it'd be worth doing this.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

On Sun, Jan 29, 2017 at 2:30 PM, David Sweeris  wrote:

>
> On Jan 29, 2017, at 12:13, Xiaodi Wu  wrote:
>
> On Sun, Jan 29, 2017 at 2:03 PM, David Sweeris 
> wrote:
>
>>
>> On Jan 29, 2017, at 10:36, Xiaodi Wu  wrote:
>>
>> Hmm, interesting. I might be tempted to use a 40-bit type for large
>> arrays, but the performance hit for any useful computation over a large
>> array would probably tilt heavily in favor of plain 64-bit integers. What's
>> your use case for such a 40-bit type? And is it common enough to justify
>> such a facility in the stdlib vs. providing the tools to build it yourself?
>>
>>>
>> I can think of two use-cases. One — saving memory for large #s of
>> allocations — you already mentioned. The other is for easing interactions
>> with on-disk data. For example, if you're working with some format that has
>> 24-bit ints, you could use "CompoundWhateverItWasCalled". It
>> doesn't make much difference when you're loading the data, but when you're
>> writing it back out, you wouldn't have to worry about trimming that last
>> byte or what to do if the value won't fit in 24 bits. I mean, obviously
>> you'd still have to handle it, but the overflow would happen in the
>> calculation that causes it rather then while you're busy doing something
>> else.
>>
>> In terms of justification, I think probably all I can offer is that I
>> *think* it wouldn't be materially harder or less efficient to implement
>> this than it would be to write a "DoubleWidth" type... It's extra
>> functionality for free, at least in terms of effort. It would increase the
>> API surface, but not by much. Assuming that "DoubleWidth" could just be a
>> typealias, that is. If I'm wrong about it being "that easy", then I don't
>> think it'd be worth it. As you noted, it is somewhat niche.
>>
>
> Unless I'm mistaken, DoubleWidth would be implemented using
> doubleWidthMultiply and doubleWidthDivide facilities provided in these new
> integer protocols. As the protocol documentation says, DoubleWidth is
> really intended for wider types, not arbitrarily sized narrower
> ones. There's no obvious way I can see to implement the same thing for two
> types of unequal bit width, short of determining dynamically, at each
> operation, which of your two types has the larger bit width and truncating
> bits accordingly. So if you want a 24-bit Int, it's unclear to me why you'd
> choose what's effectively DoubleWidth minus 8 bits rather than Int32
> minus 8 bits.
>
>
> It's a trade-off between computationally efficiency and memory/storage
> efficiency. If you want your answer sooner, pick Int32, accept that you're
> "wasting" a byte, and manually trim the value later. If you'd rather have
> your 24-bit int only actually take up 24 bits or not have to worry about
> its value taking more than 24 bits, pick the other one.
>

You shouldn't have to make any trade-off: these protocols should make it
easy for you to make your own Int24 that is both fast and exactly 24 bits!


> I'll have to look at the doubleWidthMultiply/Divide functions later when I
> get home. Don't know if they'd actually throw a wrench in my crazy scheme,
> or if it's all just in the name. If this causes any problems for
> DoubleWidth, I don't think it'd be worth doing this.
>

`doubleWidthMultiply` gives you the high and low halves of the result in a
tuple. Unless I'm mistaken, getting the high and low halves are machine
instructions. Put them together and you have a double-width value.


>
> - Dave Sweeris
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 29 2017, Brent Royal-Gordon  wrote:

>> On Jan 13, 2017, at 12:47 PM, Max Moiseev via swift-evolution 
>>  wrote:
>> 
>> Protocol-oriented integers (take 2)
>> 
>>  • Proposal: SE-
>>  • Authors: Dave Abrahams, Maxim Moiseev
>>  • Review Manager: TBD
>>  • Status: Awaiting review
>>  • Bug: SR-3196
>>  • Previous Proposal: SE-0104
>
> Definitely liking what I'm seeing here.
>
>> public protocol Arithmetic : Equatable, ExpressibleByIntegerLiteral 
>> {
>
> Is there a reason `Arithmetic` is not `Hashable`? 

Just that it's an orthogonal concern.  I think it would make a lot of
sense to make all BinaryIntegers hashable, since we can provide a
default implementation that simply hash-combines words.

> (I think `Comparable` isn't here because complex numbers can't be
> compared, but correct me if I'm wrong about that.)

That's right.

>> /// A type that can represent the absolute value of any possible value of the
>>   /// conforming type.
>>   associatedtype Magnitude : Equatable, ExpressibleByIntegerLiteral
>
> Is there a reason not to have this be `Arithmetic`? Maybe just the
> circularity problem?

Yes, that, at least.

>>   /// Returns the n-th word, counting from the least significant to most
>>   /// significant, of this value's binary representation.
>>   ///
>>   /// The `word(at:)` method returns negative values in two's complement
>>   /// representation, regardless of a type's underlying implementation. If 
>> `n`
>>   /// is greater than the number of words in this value's current
>>   /// representation, the result is `0` for positive numbers and `~0` for
>>   /// negative numbers.
>>   ///
>>   /// - Parameter n: The word to return, counting from the least significant 
>> to
>>   ///   most significant. `n` must be greater than or equal to zero.
>>   /// - Returns: An word-sized, unsigned integer with the bit pattern of the
>>   ///   n-th word of this value.
>>   func word(at n: Int) -> UInt
>
> How does the client know how many words there are? Are they supposed to 
> calculate that from
> `bitWidth`?
>
> Oh, I see:
>
>> 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.
>
> That looks fine to me.
>
>> /// The number of bits in the current binary representation of this value.
>>   ///
>>   /// This property is a constant for instances of fixed-width integer
>>   /// types.
>>   var bitWidth : Int { get }
>
> So, um, I'm a little confused about this one. Is this the physical
> number of bits in the value, or is it the number of bits you need to
> get from `word(at:)` in order to get all bits representing the value?
>
> For instance, when you call `UInt32.bitWidth`, does it return `32`,
> the physical number of bits in the value, or `33`, the number of bits
> including the (always zero) sign bit?

I think we recently sorted this out with Nate Cook, who was going to
write some new text for it.  If that's not the case, Nate, please
correct me.

>
>
>>   static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -> (high: Self, 
>> low: Magnitude)
>>   static func doubleWidthDivide(_ lhs: (high: Self, low: Magnitude),
>> _ rhs: Self) -> (quotient: Self, remainder: Self)
>
> Could these take/return a single `DoubleWidth` value instead of
> two separate `Self` and `Magnitude` values? Or would that present
> circularity problems?

It might work; we should investigate.  When this was originally
designed, we weren't proposing to include DoubleWidth.

>>   /// The number of bits equal to 1 in this value's binary representation.
>>   ///
>>   /// For example, in a fixed-width integer type with a `bitWidth` value of 
>> 8,
>>   /// the number 31 has five bits equal to 1.
>>   ///
>>   /// let x: Int8 = 0b0001_
>>   /// // x == 31
>>   /// // x.popcount == 5
>>   var popcount: Int { get }
>
> I'm not super-fond of this name; I assume it's a term of art, but it's
> a pretty obscure one. Maybe `numberOfOnes`? `onesWithin`?

Yes, the rationale is that it's a term of art.  I think if you were
going to call it something else, you'd need to mention "one _bits_" in
the name.  If we can come up with a name that's obviously better, that's
great, but lacking a clear winner we should go with the already-accepted
term.

>> DoubleWidth
>> 
>> The DoubleWidth type allows to create wider fixed-width integer
>> types from the ones available in the standard library.
>
> I'm glad you're planning to include `DoubleWidth` this time.
>
>>  • Deprecation of the BitwiseOperations protocol. We find it
>> hard to imagine a type that conforms to this protocol, but is not a
>> binary integer type.
>
> While I'm sure any such type *could* be a binary integer type, I'm not
> convinced they necessary *should* be. For instance, suppose I have a
> "bit vector"; I know I never want to perform arithmetic on it, but I
> *do* want to mani

Re: [swift-evolution] protocol-oriented integers (take 2)

[Brent Royal-Gordon via swift-evolution]

> On Jan 29, 2017, at 7:02 PM, Dave Abrahams via swift-evolution 
>  wrote:
> 
>>>  var popcount: Int { get }
>> 
>> I'm not super-fond of this name; I assume it's a term of art, but it's
>> a pretty obscure one. Maybe `numberOfOnes`? `onesWithin`?
> 
> Yes, the rationale is that it's a term of art.  I think if you were
> going to call it something else, you'd need to mention "one _bits_" in
> the name.  If we can come up with a name that's obviously better, that's
> great, but lacking a clear winner we should go with the already-accepted
> term.

Okay, but the same could be said for `trailingZeros`. Does that also need to be 
something like `trailingZerosInBinaryRepresentation` or what-have-you?

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

> Personally I don't think the strict separation of SetAlgebra and things
> that do bitwise operations makes sense, but I know some people feel
> strongly that it would be confusing for users to expose set operations
> with bitwise operator names.  IMO using | for union and & for
> intersection would be beautiful.  But that's a story for another day...


Honestly, if I were designing Swift from scratch, I might consider having a 
`BitView` type and `bits` member which acts as a collection of `Bool`s (or 
maybe a set of offsets of `1` bits?) and conforms to `SetAlgebra`; you could 
then perform bitwise operations through the `bits`, but not directly on the 
value itself. But that ship has clearly sailed.

-- 
Brent Royal-Gordon
Architechies

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Xiaodi Wu via swift-evolution]

I share your concern about trailingZeros and leadingZeros; those could
probably be improved as trailingZeroBits and leadingZeroBits. The terms of
art there, ctz ("count trailing zeros") and clz, are a bit cryptic but
perhaps also fine if ulp is acceptable for FloatingPoint.



On Sun, Jan 29, 2017 at 22:42 Brent Royal-Gordon via swift-evolution <
swift-evolution@swift.org> wrote:

> > On Jan 29, 2017, at 7:02 PM, Dave Abrahams via swift-evolution <
> swift-evolution@swift.org> wrote:
> >
> >>>  var popcount: Int { get }
> >>
> >> I'm not super-fond of this name; I assume it's a term of art, but it's
> >> a pretty obscure one. Maybe `numberOfOnes`? `onesWithin`?
> >
> > Yes, the rationale is that it's a term of art.  I think if you were
> > going to call it something else, you'd need to mention "one _bits_" in
> > the name.  If we can come up with a name that's obviously better, that's
> > great, but lacking a clear winner we should go with the already-accepted
> > term.
>
> Okay, but the same could be said for `trailingZeros`. Does that also need
> to be something like `trailingZerosInBinaryRepresentation` or what-have-you?
>
> >> 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.
>
> > Personally I don't think the strict separation of SetAlgebra and things
> > that do bitwise operations makes sense, but I know some people feel
> > strongly that it would be confusing for users to expose set operations
> > with bitwise operator names.  IMO using | for union and & for
> > intersection would be beautiful.  But that's a story for another day...
>
>
> Honestly, if I were designing Swift from scratch, I might consider having
> a `BitView` type and `bits` member which acts as a collection of `Bool`s
> (or maybe a set of offsets of `1` bits?) and conforms to `SetAlgebra`; you
> could then perform bitwise operations through the `bits`, but not directly
> on the value itself. But that ship has clearly sailed.
>
> --
> Brent Royal-Gordon
> Architechies
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Sun Jan 29 2017, Brent Royal-Gordon  wrote:

>> On Jan 29, 2017, at 7:02 PM, Dave Abrahams via swift-evolution 
>>  wrote:
>> 
  var popcount: Int { get }
>>> 
>>> I'm not super-fond of this name; I assume it's a term of art, but it's
>>> a pretty obscure one. Maybe `numberOfOnes`? `onesWithin`?
>> 
>> Yes, the rationale is that it's a term of art.  I think if you were
>> going to call it something else, you'd need to mention "one _bits_" in
>> the name.  If we can come up with a name that's obviously better, that's
>> great, but lacking a clear winner we should go with the already-accepted
>> term.
>
> Okay, but the same could be said for `trailingZeros`. Does that also
> need to be something like `trailingZerosInBinaryRepresentation` or
> what-have-you?

Fair enough.  trailingZeroBits would be fine.  “InBinaryRepresentation”
isn't accurate enough; it would have to be “InTwosComplement,” but I'd
rather leave that out of the name and let the documentation clarify that
it's all 2's complement, all the way down.

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


>> Personally I don't think the strict separation of SetAlgebra and things
>> that do bitwise operations makes sense, but I know some people feel
>> strongly that it would be confusing for users to expose set operations
>> with bitwise operator names.  IMO using | for union and & for
>> intersection would be beautiful.  But that's a story for another day...
>
> Honestly, if I were designing Swift from scratch, I might consider
> having a `BitView` type and `bits` member which acts as a collection
> of `Bool`s (or maybe a set of offsets of `1` bits?) and conforms to
> `SetAlgebra`; you could then perform bitwise operations through the
> `bits`, but not directly on the value itself. But that ship has
> clearly sailed.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Brent Royal-Gordon via swift-evolution]

> On Jan 29, 2017, at 10:07 PM, Dave Abrahams  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.

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

-- 
Brent Royal-Gordon
Architechies

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Dave Abrahams via swift-evolution]

on Mon Jan 30 2017, Brent Royal-Gordon  wrote:

>> On Jan 29, 2017, at 10:07 PM, Dave Abrahams  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.
>
> 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?

-- 
-Dave

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Max Moiseev via swift-evolution]

> On Jan 29, 2017, at 4:41 AM, Xiaodi Wu  wrote:
> 
>  
> >   static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -> (high: Self, 
> > low: Magnitude)
> >   static func doubleWidthDivide(_ lhs: (high: Self, low: Magnitude), _ rhs: 
> > Self) -> (quotient: Self, remainder: Self)
> 
> Could these take/return a single `DoubleWidth` value instead of two 
> separate `Self` and `Magnitude` values? Or would that present circularity 
> problems?
> 
> Having mulled the idea of implementing an IEEE Decimal type, I'd be sad to 
> see these return DoubleWidth. Double-width multiply as it is here is 
> useful when you want to get the result and immediately discard either the 
> high or the low bits, for instance. If you'd want a result of type 
> `DoubleWidth` instead, you could always just write `DoubleWidth(a) 
> * DoubleWidth(b)`.

doubleWidthDivide should not return a DoubleWidth 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 high is T and low is T.Magnitude, which is not the case 
for quotient and remainder.

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

enum DoubleWidth {
  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.

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Max Moiseev via swift-evolution]

> On Jan 30, 2017, at 12:21 AM, Brent Royal-Gordon via swift-evolution 
>  wrote:
> 
>> On Jan 29, 2017, at 10:07 PM, Dave Abrahams  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.
> 
> 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.

> 
> -- 
> Brent Royal-Gordon
> Architechies
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

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

Re: [swift-evolution] protocol-oriented integers (take 2)

[Brent Royal-Gordon via swift-evolution]

> On Jan 30, 2017, at 11:31 AM, Max Moiseev  wrote:
> 
> doubleWidthDivide should not return a DoubleWidth 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 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
static func doubleWidthDivide(_ lhs: DoubleWidth, _ 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
static func divide(_ lhs: DoubleWidth, 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: 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
f