[swift-evolution] Representation of natural numbers with a distinct type

James Froggatt conductator at ntlworld.com
Wed Feb 3 15:03:51 CST 2016


I specifically referred to the subscript of Array, not all CollectionTypes. The fact is Array's specific implementation of CollectionType implements a zero-based index, yet exposes its subscript as a signed integer.

As for .count, there is no way for it to be negative in CollectionType's default implementation, and don't see any realistic situation in which an implementing type would override it to allow negative values. If one did, I'm not sure it should conform to CollectionType to begin with. I expect there are many occurrences of 0 ..< collection.count being used in functions operating on collections without first checking count is not negative, because why would it be?

The problem is, currently any type implementing CollectionType could do this, so when creating generic functions, any cautious programmer would have to account for it. The only sensible thing to do in that situation, that I can see, is throw an error, which suggests count is in fact unsafe.

I am unfamiliar with size_t, but a type that could act as an equivalent of the CGFloat typealias for unsigned integers seems a good idea. However, given size_t goes against Swift type naming conventions (I assume it exists for C interop?), it seems like it would be preferable to create a separate typealias for this purpose.

From James F

> On 3 Feb 2016, at 20:35, davesweeris at mac.com wrote:
> 
> What about .count? Is it possible for that to be negative? If we change how count is represented, I think it should be switched to size_t, rather that UInt. I’m aware that they’re currently the same thing, but that might not always be the case, and, at least the way I understand things, the max value of a platform’s “pointer” type is more directly tied to the maximum possible element count than the max value of its native uint type. I know of at least one platform in development which uses 64 bits for pointers, but the address space is only 61 bits because the CPU & memory system use 3 bits for flags.
> 
> - Dave Sweeris
> 
> 
>> On Feb 3, 2016, at 11:58, David Turnbull via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> -1  CollectionType and it's ilk, contrary to what you believe, were designed to handle negative indexes just fine. Or even indexes that aren't numeric. And there's plenty of real use cases for this.
>> 
>> class GraphRow : MutableCollectionType {
>>     var values = [Int](count: 201, repeatedValue: 0)
>>     var startIndex: Int { return -100 }
>>     var endIndex: Int { return 100 }
>>     subscript(column: Int) -> Int {
>>         get {
>>             return values[column+100]
>>         }
>>         set {
>>             values[column+100] = newValue
>>         }
>>     }
>> }
>> var r = GraphRow()
>> r[-3] = 12
>> r[9] = 2
>> print(r[-3])
>> print(r.reduce(0, combine: +))
>> 
>> -david
>> 
>> 
>>> On Wed, Feb 3, 2016 at 9:31 AM, James Froggatt via swift-evolution <swift-evolution at swift.org> wrote:
>>> In the standard library, there are methods (notably array subscripts, CollectionType's .count and the dimensions of CGSize) which are designed to deal only with natural (non-negative) numbers. Functions either throw an error if a parameter is negative, or else ignore the possibility of a negative value finding its way into these functions.
>>> 
>>> By updating the standard library with a natural number type to represent these values (and potentially the Swift interfaces for Foundation and other frameworks), there is no way a negative number can be passed to these functions. This eliminates the need for many preconditions, allowing them to eliminate the possibility of a crash, and it would be clear that values such as count will never be negative.
>>> 
>>> If this change were accepted, the user would have to explicitly convert between the types at some points in their code. This could be seen as a burden, but requiring a cast encourages the programmer to check for negative values, keeping negatives out of natural number functions, and moving checks to the source of the data, similar to how Optionals eliminate nil values early on.
>>> 
>>> The parallel to Optionals is, in my opinion, the most appealing aspect of this idea. With Swift's focus on type safety, the lack of distinction between natural numbers and potentially negative ones seems like an omission, given how commonly both kinds of number are used. Enabling this level of integral safety would add additional clarity and reduce potential errors. Use cases include not just indexes, but in sizes such as collections' count and CG dimensions, for both clarity when getting values, and enforcing valid values at initialisation.
>>> 
>>> UInt is the obvious candidate to represent integer natural numbers, but is hazardous in edge cases: UInt allows an extra bit for magnitude, so has the possibility of overflow when converting back to Int. I assume this hazard is the primary reason UInt currently isn't used. If this a concern, a separate collection of types for natural integers (NInt?) could be created, which could be a strict subset of the correspondingly sized Int values (using n-1 bits).
>>> 
>>> This would mean adding a new collection of integer types in the standard library, which is undesirable. However, for high level applications which Swift is primarily used for, this would arguably be a more useful type than UInt, considering the near absence of UInt in current APIs, and its tiny increase (1 bit?) in precision compared to using an Int of a larger size. An unsigned Integer subset would allow safe conversion back to Int, and the conversion from Int is relatively simple, from the design perspective - ignore the sign bit, throw an error, or round up to 0, as appropriate.
>>> 
>>> Alternatives include:
>>> • A generic wrapper for Int which constrains its possible values. This would allow inherent support for use with existing operators, but would be rather clunky in cases where only natural numbers are being dealt with.
>>> • In a future version of Swift, the addition of type parameters constraining possible values may enable this to be added, but even if this does get added it may be too late to make such a major change.
>>> • Leaving the APIs as they are and require every function dealing with natural numbers to either throw a runtime error when a negative is passed. If the user forgets to follow this rule (or wont put in the extra effort to add the check), their functions will have unspecified behaviour.
>>> 
>>> This ended up longer than I would like, sorry about that. I don't think this issue has been covered here.
>>> I'd be interested to hear responses and opinions, and while I'm confident this change would be beneficial if done correctly, doing it correctly is easier said that done.
>>> 
>>> - James
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160203/545a0f7c/attachment.html>


More information about the swift-evolution mailing list