[swift-evolution] protocol-oriented integers (take 2)
Xiaodi Wu
xiaodi.wu at gmail.com
Wed Jan 25 12:03:08 CST 2017
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 at 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 at 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
> <https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md> 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-NNNN
> <https://gist.github.com/moiseev/0000-even-more-improved-integers.md>
> - Authors: Dave Abrahams <https://github.com/dabrahams>, Maxim Moiseev
> <https://github.com/moiseev>
> - Review Manager: TBD
> - Status: Awaiting review
> - Bug: SR-3196 <https://bugs.swift.org/browse/SR-3196>
> - Previous Proposal: SE-0104
> <https://gist.github.com/moiseev/0104-improved-integers.md>
>
>
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#introduction>
> Introduction
>
> This proposal is an evolution of SE-0104
> <https://gist.github.com/moiseev/0104-improved-integers.md>. 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 <https://gist.github.com/moiseev/0104-improved-integers.md>) are
> listed in a dedicated section
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#whats-new-since-se-0104>
> .
>
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#motivation>
> Motivation
>
> Swift's integer protocols don't currently provide a suitable basis for
> generic programming. See this blog post
> <http://blog.krzyzanowskim.com/2015/03/01/swift_madness_of_generic_integer/> 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.
>
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#proposed-solution>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 instances of any concrete integer type
> with values of any other concrete integer type enables writing functions
> that operate on more than one type conforming to BinaryInteger, such
> as heterogeneous comparisons or bit shifts, described later.
> -
>
> It removes the overload resolution overhead.
>
> Arithmetic and bitwise operations can now be defined as generic
> operators on protocols. This approach significantly reduces the number of
> overloads for those operations, which used to be defined for every single
> concrete integer type.
> -
>
> It enables protocol sharing between integer and floating point types.
>
> Note the exclusion of the % operation from Arithmetic. Its behavior
> for floating point numbers is sufficiently different from the one for
> integers that using it in generic context would lead to confusion. The
> FloatingPoint protocol introduced by SE-0067
> <https://gist.github.com/moiseev/0067-floating-point-protocols.md> should
> now refine SignedArithmetic.
> -
>
> It makes future extensions possible.
>
> The proposed model eliminates the 'largest integer type' concept
> previously used to interoperate between integer types (see toIntMax in
> the current model) and instead provides access to machine words. It also
> introduces thedoubleWidthMultiply, doubleWidthDivide, and
> quotientAndRemainder methods. Together these changes can be used to
> provide an efficient implementation of bignums that would be hard to
> achieve otherwise.
>
> The implementation of proposed model in the standard library is available in
> the new-integer-protocols branch
> <https://github.com/apple/swift/tree/new-integer-protocols>.
>
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#a-note-on-bit-shifts>A
> note on bit shifts
>
> This proposal introduces the concepts of *smart shifts* and *masking
> shifts*.
>
> The semantics of shift operations are often undefined
> <http://llvm.org/docs/LangRef.html#bitwise-binary-operations> in under-
> or over-shift cases. *Smart shifts*, implemented by >> and <<, are
> designed to address this problem and always behave in a well defined way,
> as shown in the examples below:
>
> -
>
> x << -2 is equivalent to x >> 2
> -
>
> (1 as UInt8) >> 42) will evaluate to 0
> -
>
> (-128 as Int8) >> 42) will evaluate to 0xff or -1
>
> In most scenarios, the right hand operand is a literal constant, and
> branches for handling under- and over-shift cases can be optimized away.
> For other cases, this proposal provides *masking shifts*, implemented by
> &>> and &<<. A masking shift logically preprocesses the right hand
> operand by masking its bits to produce a value in the range 0...(x-1)
> where x is the number of bits in the left hand operand. On most
> architectures this masking is already performed by the CPU's shift
> instructions and has no cost. Both kinds of shift avoid undefined behavior
> and produce uniform semantics across architectures.
>
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#detailed-design>Detailed
> design
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#whats-new-since-se-0104>What's
> new since SE-0104
>
> -
>
> SE-0091
> <https://gist.github.com/moiseev/0091-improving-operators-in-protocols.md> removed
> the necessity to dispatch generic operators through special methods.
>
> All operators are now declared by protocols as static funcs.
> -
>
> Standard Library no longer provides + and - operators for Strideable
> types.
>
> They were problematic, as one could have written mixed-type code like let
> x: Int64 = 42; x += (1 as Int), which would compile, but shouldn't.
> Besides, since the Stride of an unsigned type is signed, Standard
> Library had to implement a hack to make code like let x: UInt = 42; x
> += (1 as Int) ambiguous. These operators were only necessary because
> they made advancing collection indices convenient, which is no longer the
> case since the introduction of the new indexing model
> <https://gist.github.com/moiseev/0065-collections-move-indices.md> in
> Swift 3.
> -
>
> Shifts and other bitwise operations were moved from FixedWidthInteger
> to BinaryInteger.
>
> Left shift operation on an unbounded integer should infinitely extend
> the number, and never drop set bits when they reach the most significant
> position in the underlying representation.
> -
>
> BitwiseOperations protocol was deprecated.
>
> We believe there are no useful entities that support bitwise
> operations, but at the same time are not binary integers.
> -
>
> minimumSignedRepresentationBitWidth property was removed.
> -
>
> trailingZeros property was added to the BinaryInteger protocol.
>
> leadingZeros and popcount properties are still defined by the
> FixedWidthInteger protocol.
> -
>
> Endian-converting initializers and properties were added to the
> FixedWidthInteger protocol.
> -
>
> Standard library introduces the new type DoubleWidth<T>.
>
> See this section
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#doublewidth> for
> more details.
>
>
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#protocols>
> Protocols
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#arithmetic>
> Arithmetic
>
> The Arithmetic protocol declares binary arithmetic operators – such as +,
> -, and * — and their mutating counterparts.
>
> It provides a suitable basis for arithmetic on scalars such as integers
> and floating point numbers.
>
> Both mutating and non-mutating operations are declared in the protocol,
> however only the mutating ones are required, as default implementations of
> the non-mutating ones are provided by a protocol extension.
>
> The Magnitude associated type is able to hold the absolute value of any
> possible value of Self. Concrete types do not have to provide a type
> alias for it, as it can be inferred from the magnitude property. This
> property can be useful in operations that are simpler to implement in terms
> of unsigned values, for example, printing a value of an integer, which is
> just printing a '-' character in front of an absolute value.
>
> Please note that for ordinary work, the magnitude property should not be
> preferred to the abs(_) function, whose return value is of the same type
> as its argument.
>
> public protocol Arithmetic : Equatable, ExpressibleByIntegerLiteral {
> /// Creates a new instance from the given integer, if it can be represented /// exactly. /// /// If the value passed as `source` is not representable exactly, the result /// is `nil`. In the following example, the constant `x` is successfully /// created from a value of `100`, while the attempt to initialize the /// constant `y` from `1_000` fails because the `Int8` type can represent /// `127` at maximum: /// /// let x = Int8(exactly: 100) /// // x == Optional(100) /// let y = Int8(exactly: 1_000) /// // y == nil /// /// - Parameter source: A floating-point value to convert to an integer. init?<T : BinaryInteger>(exactly source: T)
>
> /// A type that can represent the absolute value of any possible value of the /// conforming type. associatedtype Magnitude : Equatable, ExpressibleByIntegerLiteral
>
> /// The magnitude of this value. /// /// For any numeric value `x`, `x.magnitude` is the absolute value of `x`. /// You can use the `magnitude` property in operations that are simpler to /// implement in terms of unsigned values, such as printing the value of an /// integer, which is just printing a '-' character in front of an absolute /// value. /// /// let x = -200 /// // x.magnitude == 200 /// /// The global `abs(_:)` function provides more familiar syntax when you need /// to find an absolute value. In addition, because `abs(_:)` always returns /// a value of the same type, even in a generic context, using the function /// instead of the `magnitude` property is encouraged. /// /// - SeeAlso: `abs(_:)` var magnitude: Magnitude { get }
>
> /// Returns the sum of the two given values. /// /// The sum of `lhs` and `rhs` must be representable in the same type. In the /// following example, the result of `100 + 200` is greater than the maximum /// representable `Int8` value: /// /// let x: Int8 = 10 + 21 /// // x == 31 /// let y: Int8 = 100 + 121 /// // Overflow error static func +(_ lhs: Self, _ rhs: Self) -> Self
>
> /// Adds the given value to this value in place. /// /// For example: /// /// var x = 15 /// y += 7 /// // y == 22 static func +=(_ lhs: inout Self, rhs: Self)
>
> /// Returns the difference of the two given values. /// /// The difference of `lhs` and `rhs` must be representable in the same type. /// In the following example, the result of `10 - 21` is less than zero, the /// minimum representable `UInt` value: /// /// let x: UInt = 21 - 10 /// // x == 11 /// let y: UInt = 10 - 21 /// // Overflow error static func -(_ lhs: Self, _ rhs: Self) -> Self
>
> /// Subtracts the given value from this value in place. /// /// For example: /// /// var x = 15 /// y -= 7 /// // y == 8 static func -=(_ lhs: inout Self, rhs: Self)
>
> /// Returns the product of the two given values. /// /// The product of `lhs` and `rhs` must be representable in the same type. In /// the following example, the result of `10 * 50` is greater than the /// maximum representable `Int8` value. /// /// let x: Int8 = 10 * 5 /// // x == 50 /// let y: Int8 = 10 * 50 /// // Overflow error static func *(_ lhs: Self, _ rhs: Self) -> Self
>
> /// Multiples this value by the given value in place. /// /// For example: /// /// var x = 15 /// y *= 7 /// // y == 105 static func *=(_ lhs: inout Self, rhs: Self)
>
> /// Returns the quotient of dividing the first value by the second. /// /// For integer types, any remainder of the division is discarded. /// /// let x = 21 / 5 /// // x == 4 static func /(_ lhs: Self, _ rhs: Self) -> Self
>
> /// Divides this value by the given value in place. /// /// For example: /// /// var x = 15 /// y /= 7 /// // y == 2 static func /=(_ lhs: inout Self, rhs: Self)
> }
> extension Arithmetic {
> public init() { self = 0 }
>
> public static prefix func + (x: Self) -> Self {
> return x
> }
> }
>
>
> <https://gist.github.com/moiseev/62ffe3c91b66866fdebf6f3fcc7cad8c#signedarithmetic>
> SignedArithmetic
>
> The SignedArithmetic protocol is for numbers that can be negated.
>
> public protocol SignedArithmetic : Arithmetic {
> /// Returns the additive inverse of this value. /// /// let x = 21 /// let y = -x /// // y == -21 /// /// - Returns: The additive inverse of this value. /// /// - SeeAlso: `negate()` static prefix func - (_ operand: Self
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170125/065562e0/attachment.html>
More information about the swift-evolution
mailing list