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

plx plxswift at icloud.com
Tue Apr 12 11:57:57 CDT 2016

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

Although Swift uses `Optional` to mitigate the hazards of `nil` pointers (etc.), you’re still left to your own devices for handling indices.

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.

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

  protocol SafeCollection {

    /// `Index` by another name
    associatedtype Position: Equatable // , Comparable too if you want
    /// Returns `nil` when empty. A non-strawman version
    /// would return something better than a labeled tuple, here.
    var bounds: (first: Position, last: Position)? { get }
    /// Returns the first position, or `nil` when empty. 
    /// Like `startIndex` but any non-nil value is safe to subscript.
    var firstPosition: Position? { get }

    /// Returns the last position, or `nil` when empty. 
    /// Like `endIndex` but any non-nil value is safe to subscript.
    var lastPosition: Position? { get }
    /// No risk of trying to subscript `endIndex` here.
    subscript(position: Position) -> Element
    /// Safe to call on any non-nil position from this collection;
    /// no risk of trying to advance the `endIndex` here.
    func successor(of p: Position) -> Position?

    /// Safe to call on any non-nil position from this collection;
    /// no risk of trying to retreat-from the `startIndex` here.
    func predecessor(of p: Position) -> Position?

    // and so on and so forth


…which, again, I include for purpose of *comparison* only. I *believe* this illustration has more of the “index-safety” Brent is getting at, but I can’t speak for him.

- safer, b/c there’s no `nil`-analog like `endIndex` that needs checking-for
- feels more Swift-like (safer, harder to mis-use)

- likely less-efficient than current proposal
- wants you to use closed index ranges, not half-open
- doesn’t address index-invalidation (discussed immediately below)

So, again, I’m not advocating that “safer” design be Swift's basic building-block, but I think it illustrates why it’s fair to call the index system relatively “unsafe”: as proposed, indices have semantics that are lower-level than they seem, with a safety profile *closer to* IOU/`!` than most of Swift’s standard library. 

# 2: Index Invalidation Unrepresented In Type System 

A related “un-Swift-y” aspect is that index-invalidation has no type-level representation whatsoever. Some operations on collections invalidate indices, but which operations? Which indices?

I don’t have a proposed *solution* I feel good about as to how to represent invalidation in the type system, but even so “values that become invalid for further use due to actions that happen elsewhere” is not very Swift-y.

# Remarks

Don’t get me wrong, I still like this proposal, and am *very* skeptical that something like the “safer index” sketched above would be a net win; I just think it’s very fair to say that indices are a corner of the standard library that isn’t all that Swifty due to the lack of statically-enforced safety as per usual in the rest of the library.

> 	* If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

This is a tricky question in this context b/c pretty much every non-toy language with a non-toy standard library will have its own take on collections-and-iteration; it also makes it very hard to be concise, as the same terms mean slightly different things from language to language.

I think it’s fair to say that although *many* languages have something analogous to Swift’s `Generator` (soon: `Iterator`), *very few* languages have based their fundamental collections hierarchy/API around Swift-style indices.

Additionally, most languages I’m familiar with have a hierarchy that, in Swift terms, would look something like this:

- Sequence
  - Collection
    - ArrayCollection // or `ForwardCollection` in Swift, probably
    - DictionaryCollection // or AssociativeCollection, or MapCollection, etc.
    - SetCollection 

…as opposed to Swift’s design (wherein `Collection` *is* essentially the nonexistent `ForwardCollection`, and all collections are thus `ForwardCollection`s).

I’m not sure Swift gains much from being this way; put differently, if Swift currently looked like this:

  protocol CloningIterator : Iterator {

    /// Returns a copy of `self` (at the current iteration state).
    func clone() -> Self


  protocol Collection : Sequence {
    // no `Index` here
    associatedtype Iterator: CloningIterator
    // minimal API here
    var isEmpty: Bool { get }
    var count: Int { get }

  protocol ForwardCollection : Collection {
    // exactly as-per proposal’s `Collection`:
    associatedtype Index 
    // all Index-related methods exactly as-per proposal’s `Collection`


  struct Array<T> : ForwardCollection {}
  struct Set<T> : Collection {}
  struct Dictionary<K,V> : Collection {}

…then I’d still want `ForwardCollection` to have an API like the proposal (wherein collections-move-indices), but I’d personally see no real value gained by “promoting" `Set` and `Dictionary` to be `ForwardCollection`.

But, I’ve made that case before.

I want to reiterate that I think this proposal is more-or-less the best possible design for what it is—collections *should* move indices, when they have them!

> 	* How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

I’ve groused unproductively about aspects of iteration-and-collection design in numerous previous discussions; I’ve written some custom collections and some collection-combinators and in so doing encountered many issues with the previous design.

> More information about the Swift evolution process is available at
> 	https://github.com/apple/swift-evolution/blob/master/process.md <https://github.com/apple/swift-evolution/blob/master/process.md>
> Thank you,
> -Chris Lattner
> Review Manager
> _______________________________________________
> 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/20160412/c80ca658/attachment.html>

More information about the swift-evolution mailing list