That’s in the Arithmetic Protocol in the proposal:
/// Initializes to the value of `source` if it is representable exactly,
/// returns `nil` otherwise.
init?<T : Integer>(exactly source: T)
On Jun 23, 2016, at 2:23 AM, Félix Cloutier via swift-evolution <swift-evolution@swift.org> wrote:
Is there a way to get an optional initializer that returns `nil` if the operand can't be represented?
Oh, one more comment: I suggest naming the primary protocol something other than "Integer", which IMHO is a little close to "Int" for a beginner. "Integral" is a bit too ambiguous, but maybe "IntegerArithmetic" or "ArithmeticInteger"? Or to go with the representation thing, "BinaryInteger"? (Some of the requirements are at odds with a decimal-based implementation.)
Jordan
On Jun 23, 2016, at 13:50, Jordan Rose <jordan_rose@apple.com> wrote:
Hey, standard library folks. Glad we're doing this one. :-)
- I remain unconvinced that defining an Arithmetic that includes both exact and floating-point numbers is a good idea. All of the arguments from Swift 1 and 2 about why we didn't include this still seem relevant. To phrase it in generic programming terms, what algorithm would be generic over Arithmetic?
- What is Integer.init<T: FloatingPoint>(_:) supposed to do if the floating-point value is larger than the maximum representable integer? Smaller than the minimum? (As a special case, negative, when the integer type is unsigned?) Infinity? NaN?
- Integer.init<T: Integer>(_:) currently says "if it is representable". It should say something like "trapping if it is not representable".
- I find it odd that Integer.init(clamping:) privileges the bounds of fixed-width integers. I was going to suggest it should take a range to clamp to that defaults to the min and max, but that's not implementable for a BigInt.
- nthWord should count "from least-significant to most-significant" rather than "from the right".
- As mentioned before, it sounds like Integer requires a two's complement representation (if only so the result of nthWord can be interpreted correctly). That should probably be in the doc comment for the protocol.
- Why is bitWidth in bits but nthWord in words? (I know there's a good answer to this, but using them together seems like it will be common.)
- It's also probably worth calling out even more explicitly that bitWidth is a representation property, not a value property. That is, a BigInt with the value "1" could have a bitWidth of 1, 8, or 128.
- What does signBitIndex return if self is positive? I ask because it's just not in the doc comment, but thinking about the answer made it obvious that the correct return value for 0 is 0.
- For signed integers, does remainder(dividingBy:) have specified behavior for the sign of the result? See https://en.wikipedia.org/wiki/Modulo_operation\.
- I do think having Swift.abs(_:) and Integer.absoluteValue is confusing, but I don't know what to do about it.
- Why are bitwise operations limited to fixed-width integers? I see "The only difference is that because shifting left truncates the high bits of fixed-width integers, it is hard to define what a left shift would mean to an arbitrary-precision integer" further down, but I would just assume it wouldn't truncate (i.e. it would be a pure multiplication by two).
- Is there a requirement about left-shifting into the sign bit, for '<<' and for '&<<'?
- What is the ArithmeticOverflow type?
- When does the remainder operation overflow? (I just can't remember.)
- I feel a little weird having "someValue.and(mask)". Maybe bitwiseAnd or bitwiseAND to be more explicit?
- maskingShiftLeft/Right seem underspecified in their doc comments. Why can't the protocol requirement just assume the shift amount has already been masked, instead of performing the masking themselves? Is it because we won't be able to optimize that away?
I think that's about it. Great work, all!
Jordan
Hi Jordan,
Hey, standard library folks. Glad we're doing this one. :-)
- I remain unconvinced that defining an Arithmetic that includes both exact and floating-point numbers is a good idea. All of the arguments from Swift 1 and 2 about why we didn't include this still seem relevant. To phrase it in generic programming terms, what algorithm would be generic over Arithmetic?
Steve, I don’t remember exactly why we chose to do it this time. Can you answer?
- What is Integer.init<T: FloatingPoint>(_:) supposed to do if the floating-point value is larger than the maximum representable integer? Smaller than the minimum? (As a special case, negative, when the integer type is unsigned?) Infinity? NaN?
The same thing it does now — trap.
- Integer.init<T: Integer>(_:) currently says "if it is representable". It should say something like "trapping if it is not representable”.
There is a comment saying that this is the precondition that must be checked by the caller. The initializer will trap but this is the implementation detail, isn’t it?
- I find it odd that Integer.init(clamping:) privileges the bounds of fixed-width integers. I was going to suggest it should take a range to clamp to that defaults to the min and max, but that's not implementable for a BigInt.
It is always possible to pass bounds as an optional value and default to min…max in .none case.
So you are suggesting something like `init<T : Integer>(clamping: T, within bounds: Optional<ClosedRange<Self>> = nil)` then?
I don’t disagree. Looks useful, but I cannot imagine a good real world use for it, except for:
extension Integer {
public func findClosest(to: Self, within bounds: ClosedRange<Self>) {
return Self(clamping: to, within: bounds)
}
}
- nthWord should count "from least-significant to most-significant" rather than "from the right”.
Will this definition work fine with different endiannesses? It needs some thinking, but I see your point.
- As mentioned before, it sounds like Integer requires a two's complement representation (if only so the result of nthWord can be interpreted correctly). That should probably be in the doc comment for the protocol.
I’ll add it. Thanks.
- Why is bitWidth in bits but nthWord in words? (I know there's a good answer to this, but using them together seems like it will be common.)
There is a derived property that will return the width in words based on bitWidth and word size.
- It's also probably worth calling out even more explicitly that bitWidth is a representation property, not a value property. That is, a BigInt with the value "1" could have a bitWidth of 1, 8, or 128.
Noted. Thanks.
- What does signBitIndex return if self is positive? I ask because it's just not in the doc comment, but thinking about the answer made it obvious that the correct return value for 0 is 0.
The doc comment right now describes the actual behavior from the prototype implementation. I plan to document this particular property better after cleaning up the prototype.
- For signed integers, does remainder(dividingBy:) have specified behavior for the sign of the result? See https://en.wikipedia.org/wiki/Modulo_operation\.
The behavior should remain the same as it is now (the sign is preserved). I guess this just should be explicitly mentioned somewhere. Will do.
- I do think having Swift.abs(_:) and Integer.absoluteValue is confusing, but I don't know what to do about it.
- Why are bitwise operations limited to fixed-width integers? I see "The only difference is that because shifting left truncates the high bits of fixed-width integers, it is hard to define what a left shift would mean to an arbitrary-precision integer" further down, but I would just assume it wouldn't truncate (i.e. it would be a pure multiplication by two).
Exactly. It won’t truncate and we considered it to be a sufficient difference in behavior to not allow it to be used in the context over all integers.
- Is there a requirement about left-shifting into the sign bit, for '<<' and for '&<<‘?
The current behavior is to not do anything special about the sign bit. So that (64 as Int8) << 1 would result in a -128.
I should probably add a general note somewhere in the proposal that “unless specifically mentioned, the behavior will remain consistent with the existing implementation”.
- What is the ArithmeticOverflow type?
It is an enum with 2 cases, just like Optional<()>, but with more specific case name. If not for the explicitness, a simple Bool value could have been used.
- When does the remainder operation overflow? (I just can't remember.)
Discussed in a separate email. The only case where it should trap is ‘division by zero’, so this part is subjected to changes.
- I feel a little weird having "someValue.and(mask)". Maybe bitwiseAnd or bitwiseAND to be more explicit?
Doesn’t return type hint at the ‘bitwise' and not logical nature of these operations? Besides, I would expect operators to be used instead of actual protocol functions.
- maskingShiftLeft/Right seem underspecified in their doc comments. Why can't the protocol requirement just assume the shift amount has already been masked, instead of performing the masking themselves? Is it because we won't be able to optimize that away?
There is a section about shifts: https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md#a-note-on-bit-shifts
Let me know if you think it is insufficient.
I think that's about it. Great work, all!
Jordan
Thank you for a thoughtful review!
Max
On Jun 23, 2016, at 1:50 PM, Jordan Rose <jordan_rose@apple.com> wrote:
I don't have anything else to add to the concerns that have already been discussed, but I would like to reiterate on the fact that having the ,absoluteValue, property but without substituting 'abs' will induce a lot of programers to use it anyway and make mistakes.
`FloatingPoint` seems to have a similar concept to `absoluteValue` that's called "magnitude", although there's no actual `magnitude` property. Would that be a better name for this concept?
And if so, should it be on `Arithmetic`? I don't think the `FloatingPoint` spec actually specifies how absolute values should be handled (for that matter, I don't think this one does either), and currently it seems to come out of an `AbsoluteValuable` protocol that I haven't seen mentioned in either the Integer or FloatingPoint proposals.
--
Brent Royal-Gordon
Architechies
Double-width isn't needed for these as it's impossible for an integer to become larger when dividing (the smallest value you can divide by and get a result is 2, which will halve the value), and the remainder can't be larger than the original value.
Anyway, I'm hugely in favour of this proposal, it's desperately needed!
On 24 Jun 2016, at 18:17, Károly Lőrentey via swift-evolution <swift-evolution@swift.org> wrote:
I’m especially stoked about `FixedWidthInteger.doubleWidthMultiply`, which will likely lead to a measurable speedup. Why is there no `doubleWidthQuotientAndRemainder` or `doubleWidthDivide`, though?
The first comment I have to make is that, as has already been noted by plx,
the Arithmetic protocol looks like a "bag of syntax" with loose semantics
attached. It will be used by signed integers, unsigned integers (naturals),
floating point numbers; and is an obvious conformance for a Rational type as
well.
In the proposal, there is no indication of the expected semantics of the
four basic operations.
- Are addition and multiplication commutative?
- Is multiplication distributive over addition?
- Is 'rhs != 0' a precondition for division?
- Presumably associativity must match the associativity of the operators.
- What is (a / b) * b?
- Is T(exactly: n) * x guaranteed to be == (x + ... + x) n times?
I’m not sure if this has been mentioned yet, but the semantics of Integer operations also needs to be tied down. In particular, the expected behavior of the remainder operation (in all forms) when given a negative numerator and/or denumerator should be explicitly spelled out.
Now about the AbsoluteValue associatedtype, which several other people have
already shown doubts about.
I found it useful, precisely for the reason stated in the proposal
(generating the description of a Rational). However, it seems to be mostly
an implementation detail, used to:
1) work around the fact that -Int.min isn't representable in two's complement;
2) provide a way to get the unsigned version of an integer type, to be used
by the doubleWidthMultiply() return type.These uses suggest that the Integer protocol might not be the best place for
this associatedtype: both of the use cases above would not apply to a
BigInt. It seems more appropriate for it to be part of FixedWidthInteger.
It might even make sense to rename it UnsignedSelf, to make it clear that
it's intended to be the unsigned equivalent of Self.
I think absoluteValue would be a better fit in SignedInteger or SignedArithmetic. But if implementation experience suggests it should be in Integer, I don’t mind including AbsoluteValue as an alias to Self (or BigUInt) in the BigInt case.
I’m also a bit suspicious of Integer's static isSigned property. What is its intended usecase? Why do we need it, given that we also have SignedInteger/UnsignedInteger protocols? (Does it ever make sense to implement Integer without also implementing SignedInteger or UnsignedInteger?)
I also join Karoly's request for double-width division operations. In
particular I would suggest:static func doubleWidthDivideWithOverflow(_ lhs: (high: Self, low:
AbsoluteValue), by rhs: Self) -> (partialValue: Self, overflow:
ArithmeticOverflow)static func doubleWidthRemainder(_ lhs: (high: Self, low: AbsoluteValue), by
rhs: Self) -> SelfNote that I needed to use static members here, because the first argument of
the division is not Self. Alternatively, the result of doubleWidthMultiply()
could be a struct, so that double-width division operations could be members
of that struct.
I suggest to combine generation of the quotient and remainder into a single division operation. (The implementations I know of provide both, so it makes sense to combine them.)
static func doubleWidthDivide(_ numerator: (high: Self, low: AbsoluteValue), by denumerator: Self) -> (partialQuotient: Self, remainder: Self, overflow: ArithmeticOverflow)
A more spoon-feeding name would be “doubleWidthQuotientAndRemainderWithOverflow(dividing:, by:)”, but yuck.
(I’d personally also be fine with simplifying this by requiring that the division not overflow, i.e., that lhs.high < rhs (assuming rhs > 0), and treating overflow as a precondition failure. I know Rational's addition needs to handle overflow, but perhaps it would be OK to move this check outside the function? I imagine the code is already full of branches like that.)
static func doubleWidthDivide(_ numerator: (high: Self, low: AbsoluteValue), by denumerator: Self) -> (quotient: Self, remainder: Self)
These operations are difficult to implement, and are very useful.
The difficulty of their implementation might be a problem for people who want to implement FixedWidthInteger outside stdlib, but don’t care about supporting bignums or rationals. (Is that usecase desirable?) I think it would be possible to provide a divide-n-conquer default implementation for double-width division and multiplication, like the code I linked to earlier. However, without support for splitting a FixedWidthInteger into two narrower halves, the code for this would have to use nthWord, which would essentially involve implementing half of a bigint library. :-/
On 2016-06-25, at 14:23, Nicola Salmoria via swift-evolution <swift-evolution@swift.org> wrote:
--
Karoly
@lorentey
I don't have anything else to add to the concerns that have already
been discussed, but I would like to reiterate on the fact that having
the ,absoluteValue, property but without substituting 'abs' will
induce a lot of programers to use it anyway and make mistakes.`FloatingPoint` seems to have a similar concept to `absoluteValue`
that's called "magnitude", although there's no actual `magnitude`
property. Would that be a better name for this concept?
That's not a terrible idea. :-)
And if so, should it be on `Arithmetic`? I don't think the
`FloatingPoint` spec actually specifies how absolute values should be
handled (for that matter, I don't think this one does either), and
currently it seems to come out of an `AbsoluteValuable` protocol that
I haven't seen mentioned in either the Integer or FloatingPoint
proposals.
Yes, that protocol should die as part of this.
on Fri Jun 24 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:
--
Dave
Well, this is a special case for two reasons:
1. Floating point is weird. Technically, it doesn't obey any
mathematical laws understandable by people whose name is not Steve
Canon. However, approximately nobody programs as though that's the
case, because it would be impossible. We program as though floating
point types are idealized real numbers and then we deal with the fact
that they're only a pretty good approximation as an afterthought at
best. Within the limits of that approximation, floating point fits
into a set of laws governing Arithmetic... that we admittedly have
not written down, but should.
2. The proper semantic breakdown of protocols in this area is too
complex for most people to handle (you can find some figures in
http://www.cs.indiana.edu/pub/techreports/TR638.pdf\), and we're not
sure yet which subset of these belongs in the standard library.
on Fri Jun 24 2016, plx <swift-evolution@swift.org> wrote:
+1 but with a few reservations.
# Arithmetic
What *are* the expected semantics of the operators? It seems like you
can’t assume much about a generic `Arithmetic` type, e.g. in a generic
context I can’t reliably assume even things like these:- `(x / y) * y == x` (or even “is close to" x)
- `(x + x + … + x) / n == x` (for `x` added together `n` times)
- `((x + y) + z) == (x + (y + z))` (etc.)
- `(x + y) - y == x`(? I think...)…and so on; am I missing something?
If `Arithmetic` is as lacking in semantics as it seems, then it feels
like one of those “bag of syntax” protocols that keep getting
mentioned as against the stdlib philosophy.
--
Dave
https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md
Minor omission I noticed: `Integer` doesn't formally model the `init?(_: String, radix: Int)` initializer. If it did, we could provide an `init?(_: String)` initializer that called through to it. We might even be able to take the existing string-to-integer logic, which I believe is duplicated for each type through GYB, and share it in an extension so no Integer needs to write its own conversion. Is that something that should be added?
--
Brent Royal-Gordon
Architechies
Hi Remy,
I would also like to know why bit shifting and bit-wise and, or and xor operations are limited to FixedWidthInteger. I would think that a variable-length integer would be able to handle these operations in a predictable way consistent with the protocol. Wouldn't it?
The problem is that with fixed-width, the values will eventually "fall off the cliff” when shifted left, but with the arbitrary-precision integers we can simply grow the underlying storage so that “the cliff” is never reached.
Which means that in generic context, when all you have is some T that conforms to Integer, you won’t be able to tell what will happen exactly.
Pretty much the same argument applies to the bitwise operations: since 2 bignums might have different widths of the underlying storage, the semantics of those operations is not exactly the same as for the fixed width types. Does it make sense?
Max
On Jun 23, 2016, at 9:08 AM, Remy Demarest via swift-evolution <swift-evolution@swift.org> wrote:
I would also like to know why bit shifting and bit-wise and, or and xor operations are limited to FixedWidthInteger. I would think that a variable-length integer would be able to handle these operations in a predictable way consistent with the protocol. Wouldn't it?
Le 22 juin 2016 à 23:23, Félix Cloutier via swift-evolution <swift-evolution@swift.org> a écrit :
Do we lose the ability to create a signed integer from an unsigned bit pattern?
Is there a way to get an optional initializer that returns `nil` if the operand can't be represented?
What is the cost of heterogeneous comparison?
Félix
Le 22 juin 2016 à 22:42:00, David Waite via swift-evolution <swift-evolution@swift.org> a écrit :
In addition to the technical review, I would like to point out that the definition of Arithmetic appears to be missing some underscores in add/adding/subtract/subtracting
https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md
* What is your evaluation of the proposal?
I’m so glad this work is being done!
For Integer, does the presence of signBit indicate an expectation that signed Integers will have a two's complement representation?
For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under what situations would you have an overflow? I could only come up with something like Int.min.dividedWithOverflow(-1).
* Is the problem being addressed significant enough to warrant a change to Swift?
Yes, oh yes.
* Does this proposal fit well with the feel and direction of Swift?
It looks like a significant improvement.
* How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
I combed the proposal for questions, although most were answered by the time I hit the end.
-DW
_______________________________________________
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
Hi Jordan,
Hey, standard library folks. Glad we're doing this one. :-)
- I remain unconvinced that defining an Arithmetic that includes both exact and floating-point numbers is a good idea. All of the arguments from Swift 1 and 2 about why we didn't include this still seem relevant. To phrase it in generic programming terms, what algorithm would be generic over Arithmetic?
Steve, I don’t remember exactly why we chose to do it this time. Can you answer?
- What is Integer.init<T: FloatingPoint>(_:) supposed to do if the floating-point value is larger than the maximum representable integer? Smaller than the minimum? (As a special case, negative, when the integer type is unsigned?) Infinity? NaN?
The same thing it does now — trap.
I think this is worth calling out as a precondition: the value must be within the bounds of the integer type. (The implementation may not trap for some values slightly outside the integer type, like 0.1 being converted to UInt, but it's still not defined.)
- Integer.init<T: Integer>(_:) currently says "if it is representable". It should say something like "trapping if it is not representable”.
There is a comment saying that this is the precondition that must be checked by the caller. The initializer will trap but this is the implementation detail, isn’t it?
Ah, of course. My bad.
- I find it odd that Integer.init(clamping:) privileges the bounds of fixed-width integers. I was going to suggest it should take a range to clamp to that defaults to the min and max, but that's not implementable for a BigInt.
It is always possible to pass bounds as an optional value and default to min…max in .none case.
So you are suggesting something like `init<T : Integer>(clamping: T, within bounds: Optional<ClosedRange<Self>> = nil)` then?
I don’t disagree. Looks useful, but I cannot imagine a good real world use for it, except for:extension Integer {
public func findClosest(to: Self, within bounds: ClosedRange<Self>) {
return Self(clamping: to, within: bounds)
}
}
I don't find it any different from the existing requirement. If I'm going from a potentially large (absolute) value to a smaller one, it's possible I only care about representation, but it's also possible I have a smaller type here because of context.
englishPluralIndex = items.count.clamped(to: 0...2)
Maybe I'd go the other way, and say that this isn't a useful requirement. Are there algorithms that need this that are generic over Integer? (rather than FixedWidthInteger)
- nthWord should count "from least-significant to most-significant" rather than "from the right”.
Will this definition work fine with different endiannesses? It needs some thinking, but I see your point.
Yes, "significant" always refers to place values, not to the representation in memory/registers.
- Why is bitWidth in bits but nthWord in words? (I know there's a good answer to this, but using them together seems like it will be common.)
There is a derived property that will return the width in words based on bitWidth and word size.
Got it. May be deserving of a SeeAlso.
- Why are bitwise operations limited to fixed-width integers? I see "The only difference is that because shifting left truncates the high bits of fixed-width integers, it is hard to define what a left shift would mean to an arbitrary-precision integer" further down, but I would just assume it wouldn't truncate (i.e. it would be a pure multiplication by two).
Exactly. It won’t truncate and we considered it to be a sufficient difference in behavior to not allow it to be used in the context over all integers.
Hm. I guess that makes sense. My interpretation: the behavior on fixed-width integers is well-understood, the behavior on arbitrary-precision integers is easy to understand, but the behavior in an algorithm generic over both might be problematic. Thanks for the explanation.
- Is there a requirement about left-shifting into the sign bit, for '<<' and for '&<<‘?
The current behavior is to not do anything special about the sign bit. So that (64 as Int8) << 1 would result in a -128.
I should probably add a general note somewhere in the proposal that “unless specifically mentioned, the behavior will remain consistent with the existing implementation”.
Sure. In this case I was asking about the requirement, though. If I use something like llvm::APSInt, which has an arbitrary-but-fixed-at-creation number of words, does shifting into the sign bit of a signed integer always result in a negative number? It never traps or is assumed not to happen?
- What is the ArithmeticOverflow type?
It is an enum with 2 cases, just like Optional<()>, but with more specific case name. If not for the explicitness, a simple Bool value could have been used.
Please do include this in the proposal. :-)
- When does the remainder operation overflow? (I just can't remember.)
Discussed in a separate email. The only case where it should trap is ‘division by zero’, so this part is subjected to changes.
- I feel a little weird having "someValue.and(mask)". Maybe bitwiseAnd or bitwiseAND to be more explicit?
Doesn’t return type hint at the ‘bitwise' and not logical nature of these operations? Besides, I would expect operators to be used instead of actual protocol functions.
I guess so. It just reads oddly to me.
- maskingShiftLeft/Right seem underspecified in their doc comments. Why can't the protocol requirement just assume the shift amount has already been masked, instead of performing the masking themselves? Is it because we won't be able to optimize that away?
There is a section about shifts: https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md#a-note-on-bit-shifts
Let me know if you think it is insufficient.
I did see this section, but that's about the operator-based interface, not the requirements on a model type. I'd like to hear a little more about what the expected input range of maskingShiftLeft is and why.
Jordan
On Jun 23, 2016, at 15:35, Max Moiseev <moiseev@apple.com> wrote:
On Jun 23, 2016, at 1:50 PM, Jordan Rose <jordan_rose@apple.com <mailto:jordan_rose@apple.com>> wrote:
Hi Xiaodi,
Q2: I do not understand the comment explaining signBitIndex. I thought I
understood what it does from the name, but the comment says it's not the
right name. So what is signBitIndex?The name is good but the way it is implemented in the prototype currently
is NOT what the name suggests. This is the point of the comment. I plan to
revisit the prototype and either make it behave the way it’s called, or
find a better name for what it currently does.Ask: You've got bitWidth and nthWord. Any way you could expose
__builtin_popcount()? Pretty please?I don’t mind adding it to the concrete types, similar to
`countLeadingZeros` (see
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb#L855\).
Do you think it should be a protocol requirement instead?
You're right, probably best belongs on concrete types.
On Thu, Jun 23, 2016 at 1:56 PM, Max Moiseev <moiseev@apple.com> wrote:
Max
On Jun 22, 2016, at 6:13 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:
On Wed, Jun 22, 2016 at 7:52 PM, Chris Lattner via swift-evolution < > swift-evolution@swift.org> wrote:
Hello Swift community,
The review of "SE-0104: Protocol-oriented integers" begins now and runs
through June 27. The proposal is available here:https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md
Reviews are an important part of the Swift evolution process. All reviews
should be sent to the swift-evolution mailing list athttps://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the
review manager.What goes into a review?
The goal of the review process is to improve the proposal under review
through constructive criticism and contribute to the direction of Swift.
When writing your review, here are some questions you might want to answer
in your review:* What is your evaluation of the proposal?
This is excellent, and a huge improvement. Two questions and one ask:
Q1: With the adoption of this proposal, will FloatingPoint conform to
Arithmetic?
Q2: I do not understand the comment explaining signBitIndex. I thought I
understood what it does from the name, but the comment says it's not the
right name. So what is signBitIndex?
Ask: You've got bitWidth and nthWord. Any way you could expose
__builtin_popcount()? Pretty please?* Is the problem being addressed significant enough to warrant a
change to Swift?Yes, the current tangle of protocols is not exactly fun to work with for
generics.* Does this proposal fit well with the feel and direction of
Swift?Yes.
* If you have used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?Not applicable, I think.
* How much effort did you put into your review? A glance, a
quick reading, or an in-depth study?Read the proposal, worked with the existing protocols, thought carefully
about numbers in the context of the FloatingPoint discussion.More information about the Swift evolution process is available at
https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,
-Chris Lattner
Review Manager_______________________________________________
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
Big step forward, no longer have to do this :
*___________________________________*
*James⎥Head of Trolls*
*james@supmenow.com <james@supmenow.com>⎥supmenow.com <http://supmenow.com>*
*Sup*
*Runway East *
*10 Finsbury Square*
*London*
* EC2A 1AF *
On 23 June 2016 at 17:08, Remy Demarest via swift-evolution < swift-evolution@swift.org> wrote:
I would also like to know why bit shifting and bit-wise and, or and xor
operations are limited to FixedWidthInteger. I would think that a
variable-length integer would be able to handle these operations in a
predictable way consistent with the protocol. Wouldn't it?> Le 22 juin 2016 à 23:23, Félix Cloutier via swift-evolution < > swift-evolution@swift.org> a écrit :
>
> Do we lose the ability to create a signed integer from an unsigned bit
pattern?
>
> Is there a way to get an optional initializer that returns `nil` if the
operand can't be represented?
>
> What is the cost of heterogeneous comparison?
>
> Félix
>
>> Le 22 juin 2016 à 22:42:00, David Waite via swift-evolution < > swift-evolution@swift.org> a écrit :
>>
>> In addition to the technical review, I would like to point out that the
definition of Arithmetic appears to be missing some underscores in
add/adding/subtract/subtracting
>>>
>>>
https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md
>>>
>>> * What is your evaluation of the proposal?
>>
>> I’m so glad this work is being done!
>>
>> For Integer, does the presence of signBit indicate an expectation that
signed Integers will have a two's complement representation?
>>
>> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
what situations would you have an overflow? I could only come up with
something like Int.min.dividedWithOverflow(-1).
>>
>>> * Is the problem being addressed significant enough to warrant a
change to Swift?
>>
>> Yes, oh yes.
>>
>>> * Does this proposal fit well with the feel and direction of Swift?
>>
>> It looks like a significant improvement.
>>
>>>
>>> * How much effort did you put into your review? A glance, a quick
reading, or an in-depth study?
>>
>> I combed the proposal for questions, although most were answered by the
time I hit the end.
>>
>> -DW
>>
>> _______________________________________________
>> 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
Max Moiseev via swift-evolution <swift-evolution@...> writes:
> For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow, under
what situations would
you have an overflow? I could only come up with something like
Int.min.dividedWithOverflow(-1).
If you look at the prototype here:
/Integers.swift.gyb#L789
there is
exactly the check that you’ve mentioned, but for all signed integers.
Besides, it is very convenient to
have all the arithmetic operations be implemented the same way, even if
there were no real overflows for division.
I agree with this for the four basic operations, but not for the remainder
operation.
By definition, the remainder is always strictly smaller (in absolute value)
than the divisor, so even if the division itself overflows, the remainder
must be representable, so technically it never overflow.
In the only actual case where the division overflow, that is Int.min / -1,
the remainder is simply 0.
For these reasons, I think it would make sense to explicitly request that
the remainder operation never traps, and remove the overflow variants.
Nicola
- I remain unconvinced that defining an Arithmetic that includes both
exact and floating-point numbers is a good idea. All of the arguments from
Swift 1 and 2 about why we didn't include this still seem relevant. To
phrase it in generic programming terms, what algorithm would be generic
over Arithmetic?
E.g. generic point/size/rect types.
For Integer, does the presence of signBit indicate an expectation that
signed Integers will have a two's complement representation?
Yes. That is correct.
So would this require a BigInt implementation to be in two's complement
also? Most BigInt implementations use a separate sign I think, not sure if
that's for performance reasons or merely convenience though.
On Fri, Jun 24, 2016 at 7:40 AM, Jordan Rose via swift-evolution < swift-evolution@swift.org> wrote:
Oh, one more comment: I suggest naming the primary protocol something
other than "Integer", which IMHO is a little close to "Int" for a beginner.
"Integral" is a bit too ambiguous, but maybe "IntegerArithmetic" or
"ArithmeticInteger"? Or to go with the representation thing,
"BinaryInteger"? (Some of the requirements are at odds with a decimal-based
implementation.)Jordan
On Jun 23, 2016, at 13:50, Jordan Rose <jordan_rose@apple.com> wrote:
Hey, standard library folks. Glad we're doing this one. :-)
- I remain unconvinced that defining an Arithmetic that includes both
exact and floating-point numbers is a good idea. All of the arguments from
Swift 1 and 2 about why we didn't include this still seem relevant. To
phrase it in generic programming terms, what algorithm would be generic
over Arithmetic?- What is Integer.init<T: FloatingPoint>(_:) supposed to do if the
floating-point value is larger than the maximum representable integer?
Smaller than the minimum? (As a special case, negative, when the integer
type is unsigned?) Infinity? NaN?- Integer.init<T: Integer>(_:) currently says "if it is representable". It
should say something like "trapping if it is not representable".- I find it odd that Integer.init(clamping:) privileges the bounds of
fixed-width integers. I was going to suggest it should take a range to
clamp to that *defaults* to the min and max, but that's not implementable
for a BigInt.- nthWord should count "from least-significant to most-significant" rather
than "from the right".- As mentioned before, it sounds like Integer requires a two's complement
representation (if only so the result of nthWord can be interpreted
correctly). That should probably be in the doc comment for the protocol.- Why is bitWidth in bits but nthWord in words? (I know there's a good
answer to this, but using them together seems like it will be common.)- It's also probably worth calling out *even more explicitly* that
bitWidth is a *representation* property, not a *value* property. That is,
a BigInt with the value "1" could have a bitWidth of 1, 8, or 128.- What does signBitIndex return if self is positive? I ask because it's
just not in the doc comment, but thinking about the answer made it obvious
that the correct return value for 0 is 0.- For signed integers, does remainder(dividingBy:) have specified behavior
for the sign of the result? See
https://en.wikipedia.org/wiki/Modulo_operation\.- I do think having Swift.abs(_:) and Integer.absoluteValue is confusing,
but I don't know what to do about it.- Why are bitwise operations limited to fixed-width integers? I see "The
only difference is that because shifting left truncates the high bits of
fixed-width integers, it is hard to define what a left shift would mean to
an arbitrary-precision integer" further down, but I would just assume it
wouldn't truncate (i.e. it would be a pure multiplication by two).- Is there a requirement about left-shifting into the sign bit, for '<<'
and for '&<<'?- What is the ArithmeticOverflow type?
- When does the remainder operation overflow? (I just can't remember.)
- I feel a little weird having "someValue.and(mask)". Maybe bitwiseAnd or
bitwiseAND to be more explicit?- maskingShiftLeft/Right seem underspecified in their doc comments. Why
can't the protocol requirement just assume the shift amount has already
been masked, instead of performing the masking themselves? Is it because we
won't be able to optimize that away?I think that's about it. Great work, all!
Jordan_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
A double-width divide takes a double-width *numerator*, and is a useful building block for some approaches to bignum divides.
– Steve
On Jun 24, 2016, at 2:52 PM, Haravikk via swift-evolution <swift-evolution@swift.org> wrote:
On 24 Jun 2016, at 18:17, Károly Lőrentey via swift-evolution <swift-evolution@swift.org> wrote:
I’m especially stoked about `FixedWidthInteger.doubleWidthMultiply`, which will likely lead to a measurable speedup. Why is there no `doubleWidthQuotientAndRemainder` or `doubleWidthDivide`, though?Double-width isn't needed for these as it's impossible for an integer to become larger when dividing (the smallest value you can divide by and get a result is 2, which will halve the value), and the remainder can't be larger than the original value.
The operation I want is the inverse of doubleWidthMultiply, where you have a (high, low) word pair and you want to divide it by a single word, getting a quotient and remainder. This is an important building block for implementing arbitrary precision division. Intel’s DIV can do this in a single instruction, while doing it in code requires a lot of work:
https://github.com/lorentey/BigInt/blob/swift3/Sources/BigDigit.swift#L119-L176
On 2016-06-24, at 20:52, Haravikk <swift-evolution@haravikk.me> wrote:
On 24 Jun 2016, at 18:17, Károly Lőrentey via swift-evolution <swift-evolution@swift.org> wrote:
I’m especially stoked about `FixedWidthInteger.doubleWidthMultiply`, which will likely lead to a measurable speedup. Why is there no `doubleWidthQuotientAndRemainder` or `doubleWidthDivide`, though?Double-width isn't needed for these as it's impossible for an integer to become larger when dividing (the smallest value you can divide by and get a result is 2, which will halve the value), and the remainder can't be larger than the original value.
Anyway, I'm hugely in favour of this proposal, it's desperately needed!
It may not be clearly documented in the stdlib (I haven’t checked), but it definitely *is* tied down. Swift using truncating division, and remainder is defined to satisfy the usual definition of division:
a = (a/b)*b + (a%b)
In particular, this means that if r = a%b, sign(r) == sign(a), and abs(r) < abs(b).
– Steve
On Jun 26, 2016, at 6:38 PM, Károly Lőrentey via swift-evolution <swift-evolution@swift.org> wrote:
I’m not sure if this has been mentioned yet, but the semantics of Integer operations also needs to be tied down. In particular, the expected behavior of the remainder operation (in all forms) when given a negative numerator and/or denumerator should be explicitly spelled out.
I would also like to know why bit shifting and bit-wise and, or and
xor operations are limited to FixedWidthInteger. I would think that a
variable-length integer would be able to handle these operations in a
predictable way consistent with the protocol. Wouldn't it?
The semantics of left shift on fixed width integers is that high bits
are discarded. How do you define that operation for variable-width
integers? Can you write a meaningful generic algorithm that uses a left
shift on both variable- and fixed-width integers? Similar arguments
apply to the bit-inverse operation.
It's possible that variable-width integers can implement some subset of
the bitwise operations in a sensible way, but until someone works out
exactly what that subset is, how it behaves, and why it's useful, I
don't think we want to lock that into any other protocols than
FixedWidthInteger.
Remember, variable-width integers can still support all the operations
you care to implement. It's just that their semantics will in some
cases be subtly different from those of fixed-width integers.
on Thu Jun 23 2016, Remy Demarest <swift-evolution@swift.org> wrote:
Le 22 juin 2016 à 23:23, Félix Cloutier via swift-evolution <swift-evolution@swift.org> a écrit :
Do we lose the ability to create a signed integer from an unsigned bit pattern?
Is there a way to get an optional initializer that returns `nil` if the operand can't be represented?
What is the cost of heterogeneous comparison?
Félix
Le 22 juin 2016 à 22:42:00, David Waite via swift-evolution <swift-evolution@swift.org> a écrit :
In addition to the technical review, I would like to point out that
the definition of Arithmetic appears to be missing some underscores
in add/adding/subtract/subtractinghttps://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md
* What is your evaluation of the proposal?
I’m so glad this work is being done!
For Integer, does the presence of signBit indicate an expectation
that signed Integers will have a two's complement representation?For FixedWidthInteger#dividedWithOverflow/remainderWithOverflow,
under what situations would you have an overflow? I could only come
up with something like Int.min.dividedWithOverflow(-1).* Is the problem being addressed significant enough to warrant a change to Swift?
Yes, oh yes.
* Does this proposal fit well with the feel and direction of Swift?
It looks like a significant improvement.
* How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
I combed the proposal for questions, although most were answered by the time I hit the end.
-DW
_______________________________________________
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
> The first comment I have to make is that, as has already been noted by
plx,
> the Arithmetic protocol looks like a "bag of syntax" with loose semantics
> attached. It will be used by signed integers, unsigned integers
(naturals),
> floating point numbers; and is an obvious conformance for a Rational
type as
> well.
> In the proposal, there is no indication of the expected semantics of the
> four basic operations.
> - Are addition and multiplication commutative?
> - Is multiplication distributive over addition?
> - Is 'rhs != 0' a precondition for division?
> - Presumably associativity must match the associativity of the operators.
> - What is (a / b) * b?
> - Is T(exactly: n) * x guaranteed to be == (x + ... + x) n times?I’m not sure if this has been mentioned yet, but the semantics of Integer
operations also needs to be tied down. In particular, the expected behavior
of the remainder operation (in all forms) when given a negative numerator
and/or denumerator should be explicitly spelled out.> Now about the AbsoluteValue associatedtype, which several other people
have
> already shown doubts about.
> I found it useful, precisely for the reason stated in the proposal
> (generating the description of a Rational). However, it seems to be
mostly
> an implementation detail, used to:
> 1) work around the fact that -Int.min isn't representable in two's
complement;
> 2) provide a way to get the unsigned version of an integer type, to be
used
> by the doubleWidthMultiply() return type.
>
> These uses suggest that the Integer protocol might not be the best place
for
> this associatedtype: both of the use cases above would not apply to a
> BigInt. It seems more appropriate for it to be part of FixedWidthInteger.
> It might even make sense to rename it UnsignedSelf, to make it clear that
> it's intended to be the unsigned equivalent of Self.I think absoluteValue would be a better fit in SignedInteger or
SignedArithmetic. But if implementation experience suggests it should be in
Integer, I don’t mind including AbsoluteValue as an alias to Self (or
BigUInt) in the BigInt case.
AbsoluteValue is currently part of the signature of doubleWidthMultiply()
in FixedWidthInteger. I suppose that moving it to SignedInteger would
require having FixedWithSignedInteger and FixedWidthUnsignedInteger, with
different signatures for the function.
I’m also a bit suspicious of Integer's static isSigned property. What is
its intended usecase? Why do we need it, given that we also have
SignedInteger/UnsignedInteger protocols? (Does it ever make sense to
implement Integer without also implementing SignedInteger or
UnsignedInteger?)> I also join Karoly's request for double-width division operations. In
> particular I would suggest:
>
> static func doubleWidthDivideWithOverflow(_ lhs: (high: Self, low:
> AbsoluteValue), by rhs: Self) -> (partialValue: Self, overflow:
> ArithmeticOverflow)
>
> static func doubleWidthRemainder(_ lhs: (high: Self, low:
AbsoluteValue), by
> rhs: Self) -> Self
>
> Note that I needed to use static members here, because the first
argument of
> the division is not Self. Alternatively, the result of
doubleWidthMultiply()
> could be a struct, so that double-width division operations could be
members
> of that struct.I suggest to combine generation of the quotient and remainder into a
single division operation. (The implementations I know of provide both, so
it makes sense to combine them.)static func doubleWidthDivide(_ numerator: (high: Self, low:
AbsoluteValue), by denumerator: Self) -> (partialQuotient: Self, remainder:
Self, overflow: ArithmeticOverflow)A more spoon-feeding name would be
“doubleWidthQuotientAndRemainderWithOverflow(dividing:, by:)”, but yuck.
If it's guaranteed to be free, no objections. I separated them because in
one case I need the quotient and not the remainder, and in another case the
opposite.
(I’d personally also be fine with simplifying this by requiring that the
division not overflow, i.e., that lhs.high < rhs (assuming rhs > 0), and
treating overflow as a precondition failure. I know Rational's addition
needs to handle overflow, but perhaps it would be OK to move this check
outside the function? I imagine the code is already full of branches like
that.)
When the divisor is positive the check is simple, but as we have seen with
the edge case Int.min / -1, when the divisor is negative things get a lot
more complicated. So I think it's better to leave the check in the library,
allowing it to take advantage of hardware support.
static func doubleWidthDivide(_ numerator: (high: Self, low:
AbsoluteValue), by denumerator: Self) -> (quotient: Self, remainder: Self)> These operations are difficult to implement, and are very useful.
The difficulty of their implementation might be a problem for people who
want to implement FixedWidthInteger outside stdlib, but don’t care about
supporting bignums or rationals. (Is that usecase desirable?) I think it
would be possible to provide a divide-n-conquer default implementation for
double-width division and multiplication, like the code I linked to
earlier. However, without support for splitting a FixedWidthInteger into
two narrower halves, the code for this would have to use nthWord, which
would essentially involve implementing half of a bigint library. :-/--
Karoly
@lorentey
Nicola
On Mon, Jun 27, 2016 at 12:38 AM, Károly Lőrentey <karoly@lorentey.hu> wrote:
> On 2016-06-25, at 14:23, Nicola Salmoria via swift-evolution < > swift-evolution@swift.org> wrote: