[swift-evolution] [Review] SE-0065 A New Model for Collections and Indices

plx plxswift at icloud.com
Wed Apr 13 19:56:57 CDT 2016


> 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; 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.

> 
> 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?

Are there any circumstances where a collection *can* be usefully-subscripted with its *own* `endIndex`?

> 
> 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).

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`.

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.

This proposal and the new design is a good design!

>> 
>> 
>>        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



More information about the swift-evolution mailing list