[SR-3196] Implement SE-0104: Protocol-oriented integers

[jtbandes]

Previous ID	SR-3196
Radar	rdar://27382334
Original Reporter	@jtbandes
Type	Task
Status	Resolved
Resolution	Done

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Task
Assignee	@moiseev
Priority	Medium

md5: 1858174fa1c4380083b951e198df12f7

Issue Description:

SE-0104 needs implementation:

https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md

[jtbandes]

Implementation work so far is at #3796

[moiseev]

The majority of work has been done and the PR merged. The few missing pieces are:

• More tests

• var words: WordsCollection implementation to replace func word(at: )

• DoubleWidth<T> implementation

• Using DoubleWidth in FixedWidthInteger.multipliedFullWidth(by: )

• Probably more Swift 3 compatibility APIs

[bob-wilson]

Is this done now?

[swift-ci]

Comment by Raphael (JIRA)

From the SE:

> Deprecation of the BitwiseOperations protocol. We find it hard to imagine a type that conforms to this protocol, but is not a binary integer type.

Has this been implemented? What about Data?

[moiseev]

Has this been implemented? What about Data?

Yes, it has. What about Data?

[swift-ci]

Comment by Raphael (JIRA)

The quoted piece suggests that bitwise operations only ever make sense for integers. I immediately thought of Data; imho, bitwise operations would make all the sense there. Arrays of Booleans come to mind. I don't know what else people can come up with, I don't think it's "hard to imagine" non-integer types with bitwise operations, at all.

[moiseev]

Ah... The phrasing... I don't disagree it is possible to find useful types that can conform to BitwiseOperations, the more important questions is whether these types should also provide all the other operations required by FixedWidthInteger or not. If the rest of the protocol makes sense on those types, then BitiwiseOperations is not a useful abstraction. Take array of booleans as an example. If it's a fixed-width bit set, it would probably need literal representation to make masking with a literal possible, addition and subtraction can also come handy. In fact, a fixed-width bit set is best represented as a fixed width integer.
Can you think of an algorithm that would only be generic over BitwiseOperations, and nothing else?

[swift-ci]

Comment by Raphael (JIRA)

Say I want to implement sets using bit vectors. A natural implementation would use a type conforming to BitwiseOperations (probably Data, at least if we want to support more than 64 elements). BitwiseOperations members would drive set operations (intersection = &, union = |, symmetric difference = ^). However, numeric operations like division, subtraction etc. would make no sense at all (in this context).

That said, one could of course base a BigInt implementation on Data.
Therefore, I find the question "can you think of an algorithm" irrelevant here: we have no way of knowing what people come up with. The question is whether there's a reasonable abstraction. And here, it's clear to me that bit-wise logical operators make sense (and, yes, have applications) outside of integer arithmetics (the two are disjoint, really; bitwise operations don't make much sense numerically).

[benrimmington]

SE-0104 Revision 4 was implemented by:

• apple/swift#11044

• apple/swift#11203