[Pitch] BitPatternRepresentable


(Jens Persson) #1

I've found it practical/necessary to write my own BitPatternRepresentable
protocol and IMHO it feels like something that could have been added along
with the improved numeric protocols of Swift 4.

Would it make sense to add something like the following to the standard
library?

/// A type that can be converted to and from an associated BitPattern type.
protocol BitPatternRepresentable {
    associatedtype BitPattern
    var bitPattern: BitPattern { get }
    init(bitPattern: BitPattern)
}

I think it's preferable to keep the conforming type's BitPatterns to the
most basic (most "BitPattern-like" types) so eg
UInt8, UInt16, UInt32, UInt64
rather than
Int8, Int16, Int32, Int64
and, depending on platform
UInt64, UInt32
rather than
Int or UInt.

PS

// Double and Float already fulfill the requirements of
BitPatternRepresentable so:

extension Double : BitPatternRepresentable {}
extension Float : BitPatternRepresentable {}

// And here is the rest of the types that I've used:

extension UInt8 : BitPatternRepresentable {
    var bitPattern: UInt8 { return self }
    init(bitPattern: UInt8) { self = bitPattern }
}
extension UInt16 : BitPatternRepresentable {
    var bitPattern: UInt16 { return self }
    init(bitPattern: UInt16) { self = bitPattern }
}
extension UInt32 : BitPatternRepresentable {
    var bitPattern: UInt32 { return self }
    init(bitPattern: UInt32) { self = bitPattern }
}
extension UInt64 : BitPatternRepresentable {
    var bitPattern: UInt64 { return self }
    init(bitPattern: UInt64) { self = bitPattern }
}
#if arch(x86_64) || arch(arm64)
    extension Int : BitPatternRepresentable {
        var bitPattern: UInt64 { return UInt64(UInt.init(bitPattern: self))
}
        init(bitPattern: UInt64) { self = Int(Int64(bitPattern:
bitPattern)) }
    }
    extension UInt : BitPatternRepresentable {
        var bitPattern: UInt64 { return UInt64(self) }
        init(bitPattern: UInt64) { self = UInt(bitPattern) }
    }
#elseif arch(i386) || arch(arm)
    extension Int : BitPatternRepresentable {
        var bitPattern: UInt32 { return UInt32(UInt.init(bitPattern: self))
}
        init(bitPattern: UInt32) { self = Int(Int32(bitPattern:
bitPattern)) }
    }
    extension UInt : BitPatternRepresentable {
        var bitPattern: UInt32 { return UInt32(self) }
        init(bitPattern: UInt32) { self = UInt(bitPattern) }
    }
#endif

/Jens


(Jens Persson) #2

Oh, I forgot the signed IntN types:

extension Int8 : BitPatternRepresentable {
    var bitPattern: UInt8 { return UInt8(bitPattern: self) }
    init(bitPattern: UInt8) { self = Int8(bitPattern: bitPattern) }
}
extension Int16 : BitPatternRepresentable {
    var bitPattern: UInt16 { return UInt16(bitPattern: self) }
    init(bitPattern: UInt16) { self = Int16(bitPattern: bitPattern) }
}
extension Int32 : BitPatternRepresentable {
    var bitPattern: UInt32 { return UInt32(bitPattern: self) }
    init(bitPattern: UInt32) { self = Int32(bitPattern: bitPattern) }
}
extension Int64 : BitPatternRepresentable {
    var bitPattern: UInt64 { return UInt64(bitPattern: self) }
    init(bitPattern: UInt64) { self = Int64(bitPattern: bitPattern) }
}

···

On Tue, Jul 11, 2017 at 1:57 PM, Jens Persson <jens@bitcycle.com> wrote:

I've found it practical/necessary to write my own BitPatternRepresentable
protocol and IMHO it feels like something that could have been added along
with the improved numeric protocols of Swift 4.

Would it make sense to add something like the following to the standard
library?

/// A type that can be converted to and from an associated BitPattern type.
protocol BitPatternRepresentable {
    associatedtype BitPattern
    var bitPattern: BitPattern { get }
    init(bitPattern: BitPattern)
}

I think it's preferable to keep the conforming type's BitPatterns to the
most basic (most "BitPattern-like" types) so eg
UInt8, UInt16, UInt32, UInt64
rather than
Int8, Int16, Int32, Int64
and, depending on platform
UInt64, UInt32
rather than
Int or UInt.

PS

// Double and Float already fulfill the requirements of
BitPatternRepresentable so:

extension Double : BitPatternRepresentable {}
extension Float : BitPatternRepresentable {}

// And here is the rest of the types that I've used:

extension UInt8 : BitPatternRepresentable {
    var bitPattern: UInt8 { return self }
    init(bitPattern: UInt8) { self = bitPattern }
}
extension UInt16 : BitPatternRepresentable {
    var bitPattern: UInt16 { return self }
    init(bitPattern: UInt16) { self = bitPattern }
}
extension UInt32 : BitPatternRepresentable {
    var bitPattern: UInt32 { return self }
    init(bitPattern: UInt32) { self = bitPattern }
}
extension UInt64 : BitPatternRepresentable {
    var bitPattern: UInt64 { return self }
    init(bitPattern: UInt64) { self = bitPattern }
}
#if arch(x86_64) || arch(arm64)
    extension Int : BitPatternRepresentable {
        var bitPattern: UInt64 { return UInt64(UInt.init(bitPattern:
self)) }
        init(bitPattern: UInt64) { self = Int(Int64(bitPattern:
bitPattern)) }
    }
    extension UInt : BitPatternRepresentable {
        var bitPattern: UInt64 { return UInt64(self) }
        init(bitPattern: UInt64) { self = UInt(bitPattern) }
    }
#elseif arch(i386) || arch(arm)
    extension Int : BitPatternRepresentable {
        var bitPattern: UInt32 { return UInt32(UInt.init(bitPattern:
self)) }
        init(bitPattern: UInt32) { self = Int(Int32(bitPattern:
bitPattern)) }
    }
    extension UInt : BitPatternRepresentable {
        var bitPattern: UInt32 { return UInt32(self) }
        init(bitPattern: UInt32) { self = UInt(bitPattern) }
    }
#endif

/Jens


(Dave Abrahams) #3

As ever, my first question when a new protocol is proposed is, “what
generic algorithms rely on this protocol?”

inquiring-minds-wanna-know-ly y'rs,

···

on Tue Jul 11 2017, Jens Persson <swift-evolution@swift.org> wrote:

I've found it practical/necessary to write my own BitPatternRepresentable
protocol and IMHO it feels like something that could have been added along
with the improved numeric protocols of Swift 4.

Would it make sense to add something like the following to the standard
library?

/// A type that can be converted to and from an associated BitPattern type.
protocol BitPatternRepresentable {
    associatedtype BitPattern
    var bitPattern: BitPattern { get }
    init(bitPattern: BitPattern)
}

--
-Dave


(Jens Persson) #4

First, please note that I made some mistakes in the code earlier in this
conversation as I did not have a compiler at hand, a better version can be
found in the PS-section of this post:
https://lists.swift.org/pipermail/swift-users/Week-of-Mon-20170710/005921.html

It contains some more context also.

To answer your question: I'm using it as one of the basic building blocks
needed for implementing generic statically allocated Vector types with
type-level Element and Count/Index (despite the current limitations of
Swift's type system!) , more specifically:
...
protocol Vector {
    associatedtype Index: VectorIndex
    associatedtype Element
    init(elementForIndex: (Index) -> Element)
    subscript(index: Index) -> Element { get set }
}
...
protocol VectorIndex where
    VectorUInt32.Element == UInt32, VectorUInt32.Index == Self, // I guess
this should not work
    VectorUInt64.Element == UInt64, VectorUInt64.Index == Self // but it's
actually a workaround …
{
    associatedtype VectorUInt32 : Vector // … for some bug that makes it
necessary to add
    associatedtype VectorUInt64 : Vector // the constraints up there
instead of down here ...
    ...
}
...
enum Index1 : VectorIndex { // Yes, there are situations when we want a
1-element vector.
    typealias VectorUInt8 = Vector1<UInt8>
    typealias VectorUInt16 = Vector1<UInt16>
    typealias VectorUInt32 = Vector1<UInt32>
    typealias VectorUInt64 = Vector1<UInt64>
    case i0
}
enum Index2 : VectorIndex {
    typealias VectorUInt8 = Vector2<UInt8>
    typealias VectorUInt16 = Vector2<UInt16>
    typealias VectorUInt32 = Vector2<UInt32>
    typealias VectorUInt64 = Vector2<UInt64>
    case i0, i1
}
enum Index3 : VectorIndex {
    typealias VectorUInt8 = Vector3<UInt8>
    typealias VectorUInt16 = Vector3<UInt16>
    typealias VectorUInt32 = Vector3<UInt32>
    typealias VectorUInt64 = Vector3<UInt64>
    case i0, i1, i2
}
enum Index4 : VectorIndex {
    typealias VectorUInt8 = Vector4<UInt8>
    typealias VectorUInt16 = Vector4<UInt16>
    typealias VectorUInt32 = Vector4<UInt32>
    typealias VectorUInt64 = Vector4<UInt64>
    case i0, i1, i2. i3
}
// Add more if needed, I haven't yet needed more than 4.
...
...
// I leave Vector1, Vector3 and Vector4 out since they are obvious given
this:
struct Vector2<E> : Vector {
    typealias Index = Index2
    typealias Element = E
    var elements: (Element, Element)
    init(elementForIndex: (Index) -> Element) {
        elements = (elementForIndex(.i0), elementForIndex(.i1))
    }
    subscript(index: Index) -> Element {
        get {
            switch index {
            case .i0: return elements.0
            case .i1: return elements.1
            }
        }
        set {
            switch index {
            case .i0: elements.0 = newValue
            case .i1: elements.1 = newValue
            }
        }
    }
}
...
// This type of Vector is needed for the interesting and hard version of
map in the example below:
struct PrimaryBitPatternBasedVector<Base, E> : Vector where
    Base: Vector,
    E: PrimaryBitPatternRepresentable,
    E.PrimaryBitPattern == Base.Element
{
    typealias Index = Base.Index
    typealias Element = E
    var base: Base
    init(elementForIndex: (Index) -> Element) {
        base = Base.init { elementForIndex($0).bitPattern }
    }
    subscript(index: Index) -> Element {
        get { return Element(bitPattern: base[index]) }
        set { base[index] = newValue.bitPattern }
    }
}
...
extension Vector {
    ...
    // It's easy as long as the return type is just Self.
    func map(transform: (Element) -> Element) -> Self {
        return .init { transform(self[$0]) }
    }
    // But THIS MAP is an interesting example of something that is very
hard/impossible to accomplish given Swift's current type system, so we need
to special case it in some way, and one way that includes most of the
interesting element types is to do this, which will cover any type whose
values can be represented as a fixed width bit pattern:
    func map<ResultingElement>(transform: (Element) -> ResultingElement) ->
PrimaryBitPatternBasedVector<Index.VectorUInt8, ResultingElement> {
        return .init { transform(self[$0]) }
    }
    func map<ResultingElement>(transform: (Element) -> ResultingElement) ->
PrimaryBitPatternBasedVector<Index.VectorUInt16, ResultingElement> {
        return .init { transform(self[$0]) }
    }
    func map<ResultingElement>(transform: (Element) -> ResultingElement) ->
PrimaryBitPatternBasedVector<Index.VectorUInt32, ResultingElement> {
        return .init { transform(self[$0]) }
    }
    func map<ResultingElement>(transform: (Element) -> ResultingElement) ->
PrimaryBitPatternBasedVector<Index.VectorUInt64, ResultingElement> {
        return .init { transform(self[$0]) }
    }
    ...
}
...

Phew,
Don't know if that makes any sense when stripped down and edited like that
but I don't feel like posting the entire code because it needs better
naming, cleaning up, etc. first.

But more generally I think that this little protocol
(PrimaryBitPatternRepresentable (but better named)) would just tie together
/ systemize functionality that is already in the standard library,
similarly to how the Numeric protocol tied together things that were
(almost) already in the std lib, although this is of course much more
trivial and at a much lower level (bits/storage instead of numeric
computation).

I'm totally fine with just using my own implementation though and I'm just
putting it here as a naive suggestion to see if perhaps anyone else would
find it useful. Perhaps my attempts at naming it (BitPatternRepresentable,
PrimaryBitPatternRepresentable) is confusing things a little, but the idea
is just:
Every type whose values can be represented by a fixed number of bits (8,
16, 32 or 64) is "PrimaryBitPatternRepresentable" and has an associated
type "PrimaryBitPattern" that is one of the four
"PrimaryBitPatternProtocol"-conforming types: UInt8, UInt16, UInt32 or
UInt64.

/Jens

···

On Wed, Jul 12, 2017 at 12:23 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

/../
As ever, my first question when a new protocol is proposed is, “what
generic algorithms rely on this protocol?”


(Dave Abrahams) #5

/../
As ever, my first question when a new protocol is proposed is, “what
generic algorithms rely on this protocol?”

First, please note that I made some mistakes in the code earlier in this
conversation as I did not have a compiler at hand, a better version can be
found in the PS-section of this post:
https://lists.swift.org/pipermail/swift-users/Week-of-Mon-20170710/005921.html

Looking closer at your proposal, it appears to be representing in the
language the notion of a trivial type:

https://github.com/apple/swift/blob/2ee382efc37bc8ca2fc41495e76bd07846e6ca93/docs/ABIStabilityManifesto.md#layout-and-properties-of-types
https://github.com/apple/swift/blob/b6ce00a012acc3f16f9d1758320fe926a92f0dd3/docs/OwnershipManifesto.md#core-definitions

That's definitely something we should do in order to support low-level
programming.

It contains some more context also.

To answer your question: I'm using it as one of the basic building blocks
needed for implementing generic statically allocated Vector types with
type-level Element and Count/Index (despite the current limitations of
Swift's type system!) ,

Yes, Michael Ilseman and I have solved the same problem in several ways
ourselves. Of course the particular problem of fixed-sized arrays
should probably have native support, but a builtin way to identify
trivial types at compile-time would be helpful as well.

···

on Sun Jul 16 2017, Jens Persson <swift-evolution@swift.org> wrote:

On Wed, Jul 12, 2017 at 12:23 AM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

--
-Dave


(Karl) #6

+1 to that. @_specialized supports layout constraints. We should consider making them real generic parameter constraints in some later version of Swift, along with other loose constraints such as move-only objects, or objects with explicit value/reference semantics.

If anybody’s interested, see:

https://github.com/apple/swift/blob/ec6fc4d54db95f78ae72dab29734533f709ea2d7/include/swift/AST/KnownIdentifiers.def#L106 for the list of currently-supported layout constraints, and
https://github.com/apple/swift/blob/ff6747de77597afa055bb239b3d3b215640d30ea/test/attr/attr_specialize.swift#L212 for examples

- Karl

···

On 16. Jul 2017, at 16:26, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Sun Jul 16 2017, Jens Persson <swift-evolution@swift.org> wrote:

On Wed, Jul 12, 2017 at 12:23 AM, Dave Abrahams via swift-evolution < >> swift-evolution@swift.org> wrote:

/../
As ever, my first question when a new protocol is proposed is, “what
generic algorithms rely on this protocol?”

First, please note that I made some mistakes in the code earlier in this
conversation as I did not have a compiler at hand, a better version can be
found in the PS-section of this post:
https://lists.swift.org/pipermail/swift-users/Week-of-Mon-20170710/005921.html

Looking closer at your proposal, it appears to be representing in the
language the notion of a trivial type:

https://github.com/apple/swift/blob/2ee382efc37bc8ca2fc41495e76bd07846e6ca93/docs/ABIStabilityManifesto.md#layout-and-properties-of-types
https://github.com/apple/swift/blob/b6ce00a012acc3f16f9d1758320fe926a92f0dd3/docs/OwnershipManifesto.md#core-definitions

That's definitely something we should do in order to support low-level
programming.

It contains some more context also.

To answer your question: I'm using it as one of the basic building blocks
needed for implementing generic statically allocated Vector types with
type-level Element and Count/Index (despite the current limitations of
Swift's type system!) ,

Yes, Michael Ilseman and I have solved the same problem in several ways
ourselves. Of course the particular problem of fixed-sized arrays
should probably have native support, but a builtin way to identify
trivial types at compile-time would be helpful as well.

--
-Dave

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