[swift-evolution] [Pitch] BitPatternRepresentable

[Jens Persson]

On Wed, Jul 12, 2017 at 12:23 AM, Dave Abrahams via swift-evolution <
swift-evolution at 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

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170716/333c8671/attachment.html>