[Pre-proposal] Standard Protocol for Bitwise Shifts and Binary-based Integers


(Haravikk) #1

So I recently discovered that the shift operators no longer appear to be defined anywhere, i.e- they seem to only be implemented by convention rather than being required by a protocol, which doesn’t seem ideal. The problem with this is that I wanted to implement some bitwise operations but there’s no longer an obvious place to do this, and I ended up having to implement my own concept of a BitwiseIntegerType, as you can see in the example below:

protocol BitwiseIntegerType : BitwiseOperationsType, IntegerType {
    init(_ value:Int)
    init(_ value:UInt)

    func << (lhs:Self, rhs:Self) -> Self
    func >> (lhs:Self, rhs:Self) -> Self
    func <<= (inout lhs:Self, rhs:Self)
    func >>= (inout lhs:Self, rhs:Self)
}

extension BitwiseIntegerType {
    static var allOnes:Self { return ~Self.allZeros }
    static var numberOfBits:UInt { return UInt(sizeof(Self) * 8) }

    static var mostSignificantBit:Self { return Self.allOnes << Self(Self.numberOfBits - 1) }

    var leadingZeros:UInt {
        if self == Self.allZeros { return Self.numberOfBits }

        var value = self
        var width = Self.numberOfBits
        var mask = Self.allOnes
        var zeros:UInt = 0

        while (value & Self.mostSignificantBit) == Self.allZeros {
            if (value & mask) == Self.allZeros {
                zeros += width
                value <<= Self(width)
            } else {
                width /= 2
                mask <<= Self(width)
            }
        }

        return zeros
    }
}

extension Int : BitwiseIntegerType {}
extension Int8 : BitwiseIntegerType {}
extension Int16 : BitwiseIntegerType {}
extension Int32 : BitwiseIntegerType {}
extension Int64 : BitwiseIntegerType {}

extension UInt : BitwiseIntegerType {}
extension UInt8 : BitwiseIntegerType {}
extension UInt16 : BitwiseIntegerType {}
extension UInt32 : BitwiseIntegerType {}
extension UInt64 : BitwiseIntegerType {}

Int64.mostSignificantBit // -9223372036854775808
1234567.leadingZeros // 43

I think that the best solution would be to add the shift operators to BitwiseOperationsType, while declaring a BitwiseIntegerType similar to what I’ve done above that groups BitwiseOperationsType with IntegerType to create a distinction between binary-based integers and integers that could be based on some other mechanism in future, as well as to declare the required initializers from Int and UInt types. This gives more flexibility in defining higher level protocol extensions that rely on the full range of bitwise operations, without having to move any of it further up (iirc some of these operators used to be in IntegerType).

Either way, the shift operators are currently declared by convention, which I don’t think is right, as they should surely be declared as a requirement somewhere.

Also, ignore the actual implementation of leadingZeros, it may not be the most efficient method, it’s just a useful illustration of something that can be done with the protocol declarations, I’ve also omitted warnings and such to keep things simple.

Just wondering what others think? One other issue I’m unsure about is that the required Int and Uint initialiizers should probably be of the truncatingBitPattern type for bitwise operations, but I wasn’t sure how to handle adding that to the types that don’t currently have these initializers (i.e- the 64-bit types that don’t need them since they can’t currently be initialized from anything bigger).


(Jacob Bandes-Storch) #2

I saw it mentioned somewhere that the standard library team wants to allow
smaller types to be used, like <<(lhs: UInt64, rhs: UInt8). I'm not sure
exactly how that would fit in here.

···

On Mon, Jan 18, 2016 at 4:45 AM, Haravikk via swift-evolution < swift-evolution@swift.org> wrote:

So I recently discovered that the shift operators no longer appear to be
defined anywhere, i.e- they seem to only be implemented by convention
rather than being required by a protocol, which doesn’t seem ideal. The
problem with this is that I wanted to implement some bitwise operations but
there’s no longer an obvious place to do this, and I ended up having to
implement my own concept of a BitwiseIntegerType, as you can see in the
example below:

protocol BitwiseIntegerType : BitwiseOperationsType, IntegerType {
    init(_ value:Int)
    init(_ value:UInt)

    func << (lhs:Self, rhs:Self) -> Self
    func >> (lhs:Self, rhs:Self) -> Self
    func <<= (inout lhs:Self, rhs:Self)
    func >>= (inout lhs:Self, rhs:Self)
}

extension BitwiseIntegerType {
    static var allOnes:Self { return ~Self.allZeros }
    static var numberOfBits:UInt { return UInt(sizeof(Self) * 8) }

    static var mostSignificantBit:Self { return Self.allOnes << Self(Self.numberOfBits
- 1) }

    var leadingZeros:UInt {
        if self == Self.allZeros { return Self.numberOfBits }

        var value = self
        var width = Self.numberOfBits
        var mask = Self.allOnes
        var zeros:UInt = 0

        while (value & Self.mostSignificantBit) == Self.allZeros {
            if (value & mask) == Self.allZeros {
                zeros += width
                value <<= Self(width)
            } else {
                width /= 2
                mask <<= Self(width)
            }
        }

        return zeros
    }
}

extension Int : BitwiseIntegerType {}
extension Int8 : BitwiseIntegerType {}
extension Int16 : BitwiseIntegerType {}
extension Int32 : BitwiseIntegerType {}
extension Int64 : BitwiseIntegerType {}

extension UInt : BitwiseIntegerType {}
extension UInt8 : BitwiseIntegerType {}
extension UInt16 : BitwiseIntegerType {}
extension UInt32 : BitwiseIntegerType {}
extension UInt64 : BitwiseIntegerType {}

Int64.mostSignificantBit // -9223372036854775808
1234567.leadingZeros // 43

I think that the best solution would be to add the shift operators to
BitwiseOperationsType, while declaring a BitwiseIntegerType similar to what
I’ve done above that groups BitwiseOperationsType with IntegerType to
create a distinction between binary-based integers and integers that could
be based on some other mechanism in future, as well as to declare the
required initializers from Int and UInt types. This gives more flexibility
in defining higher level protocol extensions that rely on the full range of
bitwise operations, without having to move any of it further up (iirc some
of these operators used to be in IntegerType).

Either way, the shift operators are currently declared by convention,
which I don’t think is right, as they should surely be declared as a
requirement somewhere.

Also, ignore the actual implementation of leadingZeros, it may not be the
most efficient method, it’s just a useful illustration of something that
can be done with the protocol declarations, I’ve also omitted warnings and
such to keep things simple.

Just wondering what others think? One other issue I’m unsure about is that
the required Int and Uint initialiizers should probably be of the
truncatingBitPattern type for bitwise operations, but I wasn’t sure how to
handle adding that to the types that don’t currently have these
initializers (i.e- the 64-bit types that don’t need them since they can’t
currently be initialized from anything bigger).

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


(Haravikk) #3

Hmm. Well, Int is fairly common, and encompasses more than we’re ever likely to need for shifts, so it may make sense to use Self << Int as the baseline for the shifts. As for supporting smaller types, I’m not sure how it could be done in the protocol as a specific requirement unless it was something like:

protocol BitwiseIntegerType : BitwiseOperationsType, IntegerType {
    ...
    func << (lhs:Self, rhs:SignedIntegerType) -> Self
    func << (lhs:Self, rhs:UnsignedIntegerType) -> Self
}

Since those types can be easily converted to the maximum supported size and then processed accordingly, but that seems much the same as requiring a right-hand-side of Self to me, except that it requires two variations per operator.

I posted another discussion around simplifying casting of integers, specifically allowing implicit casts of any integer type so long as the type you’re casting to has a larger range; in other words, anywhere you can put an Int32 you could put an Int16, Int8, UInt16 or UInt8, but not a UInt32 or anything larger, as these could potentially lose information so should have a warning as normal (forcing the developer to do something explicitly).

Handling of integers is definitely tricky!

···

On 18 Jan 2016, at 18:11, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

I saw it mentioned somewhere that the standard library team wants to allow smaller types to be used, like <<(lhs: UInt64, rhs: UInt8). I'm not sure exactly how that would fit in here.

On Mon, Jan 18, 2016 at 4:45 AM, Haravikk via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
So I recently discovered that the shift operators no longer appear to be defined anywhere, i.e- they seem to only be implemented by convention rather than being required by a protocol, which doesn’t seem ideal. The problem with this is that I wanted to implement some bitwise operations but there’s no longer an obvious place to do this, and I ended up having to implement my own concept of a BitwiseIntegerType, as you can see in the example below:

protocol BitwiseIntegerType : BitwiseOperationsType, IntegerType {
    init(_ value:Int)
    init(_ value:UInt)

    func << (lhs:Self, rhs:Self) -> Self
    func >> (lhs:Self, rhs:Self) -> Self
    func <<= (inout lhs:Self, rhs:Self)
    func >>= (inout lhs:Self, rhs:Self)
}

extension BitwiseIntegerType {
    static var allOnes:Self { return ~Self.allZeros }
    static var numberOfBits:UInt { return UInt(sizeof(Self) * 8) }

    static var mostSignificantBit:Self { return Self.allOnes << Self(Self.numberOfBits - 1) }

    var leadingZeros:UInt {
        if self == Self.allZeros { return Self.numberOfBits }

        var value = self
        var width = Self.numberOfBits
        var mask = Self.allOnes
        var zeros:UInt = 0

        while (value & Self.mostSignificantBit) == Self.allZeros {
            if (value & mask) == Self.allZeros {
                zeros += width
                value <<= Self(width)
            } else {
                width /= 2
                mask <<= Self(width)
            }
        }

        return zeros
    }
}

extension Int : BitwiseIntegerType {}
extension Int8 : BitwiseIntegerType {}
extension Int16 : BitwiseIntegerType {}
extension Int32 : BitwiseIntegerType {}
extension Int64 : BitwiseIntegerType {}

extension UInt : BitwiseIntegerType {}
extension UInt8 : BitwiseIntegerType {}
extension UInt16 : BitwiseIntegerType {}
extension UInt32 : BitwiseIntegerType {}
extension UInt64 : BitwiseIntegerType {}

Int64.mostSignificantBit // -9223372036854775808
1234567.leadingZeros // 43

I think that the best solution would be to add the shift operators to BitwiseOperationsType, while declaring a BitwiseIntegerType similar to what I’ve done above that groups BitwiseOperationsType with IntegerType to create a distinction between binary-based integers and integers that could be based on some other mechanism in future, as well as to declare the required initializers from Int and UInt types. This gives more flexibility in defining higher level protocol extensions that rely on the full range of bitwise operations, without having to move any of it further up (iirc some of these operators used to be in IntegerType).

Either way, the shift operators are currently declared by convention, which I don’t think is right, as they should surely be declared as a requirement somewhere.

Also, ignore the actual implementation of leadingZeros, it may not be the most efficient method, it’s just a useful illustration of something that can be done with the protocol declarations, I’ve also omitted warnings and such to keep things simple.

Just wondering what others think? One other issue I’m unsure about is that the required Int and Uint initialiizers should probably be of the truncatingBitPattern type for bitwise operations, but I wasn’t sure how to handle adding that to the types that don’t currently have these initializers (i.e- the 64-bit types that don’t need them since they can’t currently be initialized from anything bigger).

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


(Andrew Bennett) #4

I support this idea. Probably worth mentioning that Dave Abrahams has been
working on integers, specifically (
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002445.html
):

Related: I have been working for some time on a rewrite of all the integer types and protocols. (sic) Another important goal is to make the *integer protocols actually useful for writing generic code*, instead of what they are today: implementation artifacts used only for code sharing. As another *litmus test* of the usefulness of the resulting protocols, the plan is to implement BigInt in terms of the generic operations defined on integers, and make BigInt itself conform to those protocols.

I've come across this issue making a BigInt library myself, I found that I
wanted shift operations in the implementation of my library, but they
weren't on any protocols. I'm hoping it will be necessary to add it to the
protocols for the mentioned *litmus test*.

Also (
https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/003652.html
):

Again I'll mention that the prototype (sic) I'm already working on to *replace

the integer protocols* and types already supports any integer type
appearing on the RHS of a *shift operation.*

Looking at the code I can't find any shift operators in protocols, but I
may have missed it. Perhaps we need to check if it's still in the plan.

···

On Tue, Jan 19, 2016 at 6:47 AM, Haravikk via swift-evolution < swift-evolution@swift.org> wrote:

Hmm. Well, Int is fairly common, and encompasses more than we’re ever
likely to need for shifts, so it may make sense to use Self << Int as the
baseline for the shifts. As for supporting smaller types, I’m not sure how
it could be done in the protocol as a specific requirement unless it was
something like:

protocol BitwiseIntegerType : BitwiseOperationsType, IntegerType {
    ...
    func << (lhs:Self, rhs:SignedIntegerType) -> Self
    func << (lhs:Self, rhs:UnsignedIntegerType) -> Self
}

Since those types can be easily converted to the maximum supported size
and then processed accordingly, but that seems much the same as requiring a
right-hand-side of Self to me, except that it requires two variations per
operator.

I posted another discussion around simplifying casting of integers,
specifically allowing implicit casts of any integer type so long as the
type you’re casting to has a larger range; in other words, anywhere you can
put an Int32 you could put an Int16, Int8, UInt16 or UInt8, but not a
UInt32 or anything larger, as these could potentially lose information so
should have a warning as normal (forcing the developer to do something
explicitly).

Handling of integers is definitely tricky!

On 18 Jan 2016, at 18:11, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

I saw it mentioned somewhere that the standard library team wants to allow
smaller types to be used, like <<(lhs: UInt64, rhs: UInt8). I'm not sure
exactly how that would fit in here.

On Mon, Jan 18, 2016 at 4:45 AM, Haravikk via swift-evolution < > swift-evolution@swift.org> wrote:

So I recently discovered that the shift operators no longer appear to be
defined anywhere, i.e- they seem to only be implemented by convention
rather than being required by a protocol, which doesn’t seem ideal. The
problem with this is that I wanted to implement some bitwise operations but
there’s no longer an obvious place to do this, and I ended up having to
implement my own concept of a BitwiseIntegerType, as you can see in the
example below:

protocol BitwiseIntegerType : BitwiseOperationsType, IntegerType {
    init(_ value:Int)
    init(_ value:UInt)

    func << (lhs:Self, rhs:Self) -> Self
    func >> (lhs:Self, rhs:Self) -> Self
    func <<= (inout lhs:Self, rhs:Self)
    func >>= (inout lhs:Self, rhs:Self)
}

extension BitwiseIntegerType {
    static var allOnes:Self { return ~Self.allZeros }
    static var numberOfBits:UInt { return UInt(sizeof(Self) * 8) }

    static var mostSignificantBit:Self { return Self.allOnes << Self(Self.numberOfBits
- 1) }

    var leadingZeros:UInt {
        if self == Self.allZeros { return Self.numberOfBits }

        var value = self
        var width = Self.numberOfBits
        var mask = Self.allOnes
        var zeros:UInt = 0

        while (value & Self.mostSignificantBit) == Self.allZeros {
            if (value & mask) == Self.allZeros {
                zeros += width
                value <<= Self(width)
            } else {
                width /= 2
                mask <<= Self(width)
            }
        }

        return zeros
    }
}

extension Int : BitwiseIntegerType {}
extension Int8 : BitwiseIntegerType {}
extension Int16 : BitwiseIntegerType {}
extension Int32 : BitwiseIntegerType {}
extension Int64 : BitwiseIntegerType {}

extension UInt : BitwiseIntegerType {}
extension UInt8 : BitwiseIntegerType {}
extension UInt16 : BitwiseIntegerType {}
extension UInt32 : BitwiseIntegerType {}
extension UInt64 : BitwiseIntegerType {}

Int64.mostSignificantBit // -9223372036854775808
1234567.leadingZeros // 43

I think that the best solution would be to add the shift operators to
BitwiseOperationsType, while declaring a BitwiseIntegerType similar to what
I’ve done above that groups BitwiseOperationsType with IntegerType to
create a distinction between binary-based integers and integers that could
be based on some other mechanism in future, as well as to declare the
required initializers from Int and UInt types. This gives more flexibility
in defining higher level protocol extensions that rely on the full range of
bitwise operations, without having to move any of it further up (iirc some
of these operators used to be in IntegerType).

Either way, the shift operators are currently declared by convention,
which I don’t think is right, as they should surely be declared as a
requirement somewhere.

Also, ignore the actual implementation of leadingZeros, it may not be the
most efficient method, it’s just a useful illustration of something that
can be done with the protocol declarations, I’ve also omitted warnings and
such to keep things simple.

Just wondering what others think? One other issue I’m unsure about is
that the required Int and Uint initialiizers should probably be of the
truncatingBitPattern type for bitwise operations, but I wasn’t sure how to
handle adding that to the types that don’t currently have these
initializers (i.e- the 64-bit types that don’t need them since they can’t
currently be initialized from anything bigger).

_______________________________________________
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