[swift-evolution] [Review] SE-0065 A New Model for Collections and Indices
Dave Abrahams
dabrahams at apple.com
Thu Apr 14 12:12:26 CDT 2016
on Wed Apr 13 2016, plx <swift-evolution at swift.org> wrote:
>> On Apr 13, 2016, at 5:36 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>
>>
>> on Wed Apr 13 2016, plx <swift-evolution at swift.org> wrote:
>>
>
>>> On Apr 12, 2016, at 5:25 PM, Dave Abrahams via swift-evolution
>>> <swift-evolution at swift.org> wrote:
>>>
>>> on Tue Apr 12 2016, plx
>>> <swift-evolution at swift.org> wrote:
>>>
>>> Aside: `indices` being irregular can be a benefit in the context of
>>> auto-complete.
>>>
>>> * What is your evaluation of the proposal?
>>>
>>> +1, very much.
>>>
>>> As a change from the current model, it’s an across-the-board improvement
>>> for me,
>>> at least.
>>>
>>> In a bigger-picture sense I think Swift would be better off by going
>>> *further*
>>> on certain aspects, but have said all that before.
>>>
>>> * Is the problem being addressed significant enough to warrant a change
>>> to
>>> Swift?
>>>
>>> It is, again very much so.
>>>
>>> * Does this proposal fit well with the feel and direction of Swift?
>>>
>>> Depends on the framing of the question.
>>>
>>> Compared to the previous model, it’s an unqualified YES.
>>>
>>> As a general proposition, I think this design is a local optimum for
>>> overall
>>> Swift-ness, but even so it’s creating a little un-Swifty pocket. It’s
>>> “un-Swifty” in at least two ways:
>>>
>>> # 1: Relatively Unsafe, Pointer-Like Semantics
>>>
>>> Indices—unsurprisingly!—behave quite a bit like pointers, and similarly
>>> expose
>>> *numerous* crashing combinations of `(value,operation)`:
>>>
>>> - self[endIndex]
>>> - self[startIndex] // <- when empty
>>> - successor(of: endIndex)
>>> - predecessor(of: startIndex)
>>>
>>> …etc., which is *very much* reminiscent of the hazards of pointers.
>>> (Technically
>>> “undefined” not “crashing”, but being realistic “crashing" is usually
>>> accurate).
>>>
>>> No, these are unspecified in the general case, not undefined. Unless
>>> you're working with, e.g. `UnsafeMutableBufferPointer` (or you have a
>>> data race), there's no undefined behavior. The big problem with
>>> pointers isn't what happens when they crash; it's what happens when they
>>> *don't*.
>>>
>>> Although Swift uses `Optional` to mitigate the hazards of `nil` pointers
>>> (etc.),
>>> you’re still left to your own devices for handling indices.
>>>
>>> `Optional` is not “mitigating hazards;” it's encoding the possibility of
>>> null in the type system. It's non-optional things that mitigate hazards.
>>>
>>> This isn’t news to anyone here, I’m sure, and may even be unavoidable;
>>> I’m just
>>> pointing it out as an uncharacteristically-unsafe area in Swift’s
>>> standard APIs,
>>> and closer to how `!` and IOUs behave than otherwise typical.
>>>
>>> Any time there's a required relationship between two things, e.g. a
>>> receiver and an argument, you have a precondition. The existence of a
>>> precondition does not make something unsafe at all in the sense that
>>> Swift uses the term. Safety in swift is about type and memory safety in
>>> the absence of data races, not about having APIs that respond sensibly
>>> to every possible combination of arguments. Int.max + 1 will trap, but
>>> that doesn't make addition unsafe.
>>>
>>> Saying that it's close to how `!` behaves is not at all far from the
>>> truth, because `!` has a precondition that its argument is non-nil.
>>>
>>> I meant it as a much more exact analogy.
>>>
>>> In a collections-move-indices world, you *could* handle indices as pointers have
>>> been handled, bringing in support from the type-system:
>>>
>>> enum SaferIndex<T:Comparable> {
>>> case Position(T)
>>> case End
>>> }
>>>
>>> …(yes, this is more-or-less `Optional` by another name).
>>>
>>> The assumption above is `T` would be today’s “Index” types, w/o the value used
>>> for `endIndex` (e.g. 0..<self.count for an array, the non-`endIndex` values of
>>> `DictionaryIndex` and `SetIndex`, and so on).
>>
>> No, you can't, at least not usefully. An Index that's at the end of one
>> collection is in the middle of another, or with a suitably-modified version
>> of the same collection.
>
> Sure, in certain concrete scenarios it’s possible for one collection’s
> indices to have such relationships to some other collection.
>
> But, what of it?
>
> In a generic context you can’t assume this;
That's incorrect. A slice's indices are *documented* as having a
particular relationship to those of the thing it was sliced from. This
applies everywhere. A dictionary's keys and values use the same indices
as the dictionary itself, and have a correspondence.
> in a concrete context you naturally have more information.
>
> Slices would become problematic, I’ll grant.
>
>> var x = [1, 2]
>> let i = x.index(1, stepsFrom: x.startIndex)
>> x.removeLast()
>> x[i] // fatal error: Index out of range
>
> Indices can become invalid; this imposes preconditions. I don’t get
> it.
My point is that whether i is at the end or not cannot be encoded in i.
>> The converse is also true: subscripting on a collection's endIndex is
>> sometimes just fine, even with no mutation in sight.
>>
>> let a = (0..<10).reversed()
>> print(Array(a)) // “[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]”
>>
>> let b = a.prefix(9)
>> print(Array(b)) // “[9, 8, 7, 6, 5, 4, 3, 2, 1]”
>>
>> print(a[b.endIndex]) // “0” (correct, supported behavior)
>
> I believe we are back to “subscripting one collection with *another*
> collection's `endIndex`, no?
Totally legit, as mentioned above. a.prefix(9) returns a slice of a.
> Are there any circumstances where a collection *can* be
> usefully-subscripted with its *own* `endIndex`?
var a = [1]
let i = a.endIndex
a.append(2)
print(a[i]) // “2”
>>
>> Of course,
>>
>> b[b.endIndex] // As a matter of QOI: fatal error: out of bounds: index >= endIndex
>>
>>>
>>> It would’ve been awkward to do this under the previous status quo—e.g. even for
>>> arrays your indices would have to have a back-reference to get the count, and
>>> thus couldn’t be plain integers—but the collection will now always be present to
>>> provide such info.
>>>
>>> Cons:
>>>
>>> - more overhead than “bare” indices
>>> - doesn’t address invalidation (but what does, really?)
>>>
>>> Pros:
>>>
>>> - easier in some ways to handle things like e.g 0…Int.max
>>> - the endIndex equivalent *never* invalidates
>>> - compile-time help for end-index checking
>>>
>>> Overall this *would* bring the treatment of indices closer to that for `?`—e.g.,
>>> redefine the core type to omit the `nil`-like value,
>>
>> Sorry, but that's the opposite of what `?` is doing: it *adds* a nil
>> value.
>
> …I must have been unclear.
>
> Step 1: Define T* = { "all memory addresses” (nil included) }
> Step 2: Define T = T* \ { nil } (e.g. "non-null pointers")
>
> …is what I was trying to summarize via “redefine the core type to omit
> the `nil`-like value” (which is the important part here).
Sorry, that's still unclear to me. I just don't see what you're getting
at.
> Anyways, having `endIndex` directly inhabit the same type as the
> “good” indices has some pros and some cons; it’s not an IMHO one-sided
> situation as with `nil`.
Maybe, but my point is that many things in the current model are
incompatible with the other arrangement. If you wanted to change the
arrangement, you'd need to re-think the current model from the ground
up, including index invalidation, how algorithms interact, the
relationship of slices to the thing they're sliced from, etc...
So what you're suggesting is an interesting hypothesis, but to me it's
not by any means obviously workable.
> On the one hand, in my own experience so far, it’s definitely been the
> case that most custom collections I’d done have had indices that’re
> effectively the `SaferIndex` above; it’s been rather rare that there’s
> been a natural “1 past the rest” value to use of the same type as is
> used to describe the position of a “good” index.
>
>> Seriously, just because Swift has Optionals and they're useful for
>> safety in some scenarios (compared with allowing everything to be
>> nullable) does not mean that it's going to be “Swiftier” to apply a
>> similar pattern everywhere.
>>
>>> use an enum to reintroduce that value when necessary—than to `!`.
>>>
>>> I don’t think the above is an *improvement* over the proposal, but it’s a route
>>> that could have been taken.
>>
>> I believe it would be hard to make such a design work at all, and if you
>> could make it work I think you'd end up with exactly the problem this
>> proposal aims to solve: references inside indices. So, I don't think
>> it's even a possibility, really.
>
> I can’t say I see the impossibility. I definitely have experienced the
> clunkiness.
>
> This is getting too involved for a hypothetical I was explaining, but
> not advocating.
I will happily agree to drop this topic :-)
> This proposal and the new design is a good design!
Thanks!
>>>
>>>
>>> To help illustrate the claim, here’s a strawman “safe” API—for
>>> illustration
>>> only, not advocacy!—that would be safer and thus perhaps more “Swift-y”:
>>>
>>> I think there's a prevalent misunderstanding (IOW, I don't mean to
>>> single out this post or this poster) about what “safe” means in Swift
>>> and what the features of a Swifty API are and should be. This
>>> is a big topic worthy of much more time than I can devote here, but
>>> here's a thought to start with:
>>>
>>> A Swifty API helps you reason effectively about the correctness of your
>>> code, and in part that means we provide enough preconditions on
>>> arguments to avoid complicating result types, and code to handle
>>> results, with optional-ness.
>>>
>>> --
>>> Dave
>>>
>>> _______________________________________________
>>> 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
>>
>> --
>> Dave
>>
>> _______________________________________________
>> 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
--
Dave
More information about the swift-evolution
mailing list