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


(Chris Lattner) #1

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md <https://github.com/apple/swift-evolution/blob/master/proposals/0055-optional-unsafe-pointers.md>

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager


(Chris Lattner) #2

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

The correct link is:

-Chris

···

On Apr 10, 2016, at 2:41 PM, Chris Lattner <clattner@apple.com> wrote:

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager


(Jens Alfke) #3

That link actually goes to an earlier proposal, 0055, although the visible text forms the correct URL. Try this link <https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md> instead. :slight_smile:

—Jens

···

On Apr 10, 2016, at 2:41 PM, Chris Lattner <clattner@apple.com> wrote:

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md <https://github.com/apple/swift-evolution/blob/master/proposals/0055-optional-unsafe-pointers.md>


(Brent Royal-Gordon) #4

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Some questions and comments:

    • Two for ranges that additionally conform to RandomAccessCollection (requiring bounds that are Strideablewith Stride conforming to Integer): CountableRange<T> and CountableClosedRange<T>. These types can be folded into Range and ClosedRange when Swift acquires conditional conformance capability.

Does this mean that once we have conditional conformances, HalfOpenRangeProtocol and ClosedRangeProtocol will most likely go away?

We also introduce three new protocols:

  • RangeProtocol
  • HalfOpenRangeProtocol
  • ClosedRangeProtocol

These protocols mostly exist facilitate implementation-sharing among the range types, and would seldom need to be implemented outside the standard library.

If these types are for implementation sharing, should they be underscored to discourage their use? Or is the position they occupy in the type hierarchy important because Range and ClosedRange will eventually occupy them?

It seems to me that RangeProtocol is unlike the other two in that it's a sensible thing to constrain a parameter to. Does the "implementation-sharing" comment not really apply to it? On the other hand, it's not like the SubSequence subscript now takes a RangeProtocol. Should it?

(Has any thought been given to allowing you to close protocols to outside conformances the way that resilience seems to suggest we'll eventually allow you to close classes?)

• Two for general ranges (whose bounds are Comparable): Range<T> and ClosedRange<T>. Having a separate ClosedRange type allows us to address the vexing inability of the old Range to represent a range containing the maximal value of its bound.

I notice that ClosedRange uses a ClosedRangeIndex to, essentially, add one extra value for "larger than all values of this type". Could this solution be applied to Range to allow us to unify Range and ClosedRange, or are there other obstacles to that?

(There likely are. I just wanted to make sure the idea wasn't left unexplored.)

func successor(of i: Index) -> Index

Two things:

1. I would really like a version of this which returns Optional and is guaranteed to go `nil` once it hits `endIndex`. There can be a non-optional version too, or it might even be a feature of the `index` family of methods instead of `successor` itself, but I think it would be valuable to let the collection worry about the bounds check. It seems silly to check the index before calling `successor(of:)` when `successor(of:)` is going to immediately perform the same check again as a precondition.

(Actually, in general, I'm a little bit dismayed that the collection API does so little to help you include bounds checks in your code. Especially when iterating through a collection, bounds checks are absolutely mandatory, and the collection API's solution to the problem is "eh, just use `<`, it's not like you might mess something like that up".)

2. There is a very strong parallel between this method and a generator's `next()` method—the generator's `next()` calls `successor(of:)` to get the index it should use—which makes me wonder if this method should also be called `next(_:)` instead of `successor(of:)`. On the other hand, I have no good suggestion for a

func index(n: IndexDistance, stepsFrom i: Index) -> Index

Oof, I am really not a fan of this name. `steps` is sort-of a label on the `n` parameter, but it's attached to `i`. Other collection APIs use `distance`, not `steps` (although "steps" does appear in the documentation of the `Distance` associated type). `index` puts it in a method family with `index(predicate:)` and `index(of:)`, but those two are user-facing while this one is part of the collection API. Even the word `index` itself is redundant with the method return type.

I do understand how this is kind of parallel to `index(of:)` and `index(predicate:)`, in that they all return an index calculated from the parameters, but I think these methods are more different than they are similar.

Compared to this:

  collection.index(5, stepsFrom: i)

I would prefer any of these (ordered from least favorite to most):

  collection.index(distance: 5, from: i)
  collection.index(5, from: i)
  collection.traveling(5, from: i)
  collection.striding(5, from: i)
  collection.advancing(i, by: 5)

A word on `striding(_:from:)` appearing in that list: Although redesigning Strideable is not directly in scope for this proposal, I've noticed that our discussions on modernizing Strideable seem to be trending towards the idea that it operates on collections (or rather, on an as-yet-unnamed supertype of `BidirectionalCollection` or `RandomAccessCollection`) and strides by repeatedly calling a method with the same semantics as this one. Thus, there seems to be an intimate connection between this operation and Strideable. I think we ought to choose a method name which suits that, and I don't think `index` is it.

func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index) -> Index

I have a few issues with this API.

1. As aforementioned, I'm not a big fan of using `index` as the base method name.

2. This method can move the index either forwards or backwards, but only one limit is specified. Would we be better off having the `limit` be a range?

3. What is the use case for returning the `limit` instead of returning the fact that we crossed it? I have a hard time thinking of a case where I would want to just bump up against the limit and use it rather than *detect* that I've hit the limit (which would probably call for a return type of `Index?`). Are there common needs that I'm just not thinking of? Should we offer both?

  * What is your evaluation of the proposal?

Despite my criticisms, this is fundamentally a very good design. It will not only improve the language, it will also open the door to further improvements.

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes. I believe this change is complicating in the short run but actually simplifying in the long run, eliminating concepts like the Index protocols which represented several overlapping semantics.

  * Does this proposal fit well with the feel and direction of Swift?

Yes.

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

Nothing with a collection design as rich as Swift's.

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

Somewhere between the latter two. I wouldn't call it in-depth when it's such a big change, but I feel like I have too much background to say it's a quick reading, either.

···

--
Brent Royal-Gordon
Architechies


(Joe Groff) #5

I love irregular plurals as much as the next grammar nerd, but I think it'd be better to use the more regular, but still correct, plural "indexes" rather than "indices".

-Joe

···

On Apr 10, 2016, at 2:41 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Joe Groff) #6

  • Because Swift is unable to express conditional protocol conformances, implementing this change has required us to create a great deal of complexity in the standard library API. Aside from the two excess “Countable” range types, there are new overloads for slicing and twelve distinct slice types that capture all the combinations of traversal, mutability, and range-replaceability. While these costs are probably temporary, they are very real in the meantime.

Is there a migration strategy possible for when we do support conditional conformances? Would typealiasing the existing names to refinements of a more general Slice<T> type be sufficient?

-Joe


(Tyler Cloutier) #7

I won’t do a full review because I don’t think I have spent enough time reading through the discussion, but just reading the proposal I’d say I’m an huge proponent of this change. Irrespective of the performance benefits, I think it’s a massive win for an easily understandable mental model.

Tyler

···

On Apr 10, 2016, at 2:41 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md <https://github.com/apple/swift-evolution/blob/master/proposals/0055-optional-unsafe-pointers.md>

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Taras Zakharko) #8

  * What is your evaluation of the proposal?

+1. I think it makes the collection model more simple and more flexible at the same time. By coupling index to a specific collection, rather then treating it as a separate, independent entity, we can more easily implement alternative collections. For instance, I have recently needed a collection that wraps around the end of a sequence, e.g.

[1, 2, 3, 4, 5].[wrappingFrom: 3, end: 2] == [4, 5, 1, 2]

With the current model, implementing indexes that do this kind of wrapping is quite messy, because a lot of collection-specific state needs to be stored within the index. With the new model, it becomes much simpler.

  * Is the problem being addressed significant enough to warrant a change to Swift?

I think so. The model where index has its own, independent properties is too rigid. It might be possible to work around the limitations of that model with using more advanced generics(e.g. where type information depends on values such as dimensionality etc.), but the proposed new model is much simpler and potentially allows better performing code.

  * Does this proposal fit well with the feel and direction of Swift?

Yes

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

Followed the thread, experimented with implementing various non-trivial collections myself (in Swift and outside Swift)

···

On 10 Apr 2016, at 23:41, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md <https://github.com/apple/swift-evolution/blob/master/proposals/0055-optional-unsafe-pointers.md>

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


#9

Hello,

I have a user question regarding the proposed range types that replace the old range/interval.

The old hierachy allowed me to turn ranges to SQL expressions through the following mapping (see https://github.com/groue/GRDB.swift/blob/v0.57.0/GRDB/FetchRequest/SQLOperator.swift#L335-L365)

  1. Range<BidirectionalIndexType>
  expr BETWEEN self.startIndex AND self.endIndex.predecessor()

  2. ClosedInterval
  expr BETWEEN self.start AND self.end

  3. HalfOpenInterval
  expr >= start AND x < end

This would let me generate SQL for 0..<18 and "A"..<"B", as below:

  // SELECT * FROM "persons" WHERE ("age" BETWEEN 0 AND 17)
  Person.filter((0..<18).contains(Col.age))

  // SELECT * FROM "persons" WHERE ("age" BETWEEN 0 AND 17)
  Person.filter((0...17).contains(Col.age))

  // SELECT * FROM "persons" WHERE ("name" BETWEEN 'A' AND 'z')
  Person.filter(("A"..."z").contains(Col.name))

  // SELECT * FROM "persons" WHERE (("name" >= 'A') AND ("name" < 'z'))
  Person.filter(("A"..<"z").contains(Col.name))

Will it still be possible with the new protocol and types? Especially, how to I generate "BETWEEN 0 AND 17" from 0..<18 without a supporting collection that gives me the predecessor of 18?

Gwendal Roué

···

Le 10 avr. 2016 à 23:41, Chris Lattner via swift-evolution <swift-evolution@swift.org> a écrit :

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?
  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Tony Parker) #10

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  * What is your evaluation of the proposal?

I agree with the general direction and scope of the proposal, but I think the names could use some changes. Specifically, I don’t think the fallback to ‘form’ is required. It would be a significant readability improvement to use a meaningful verb to describe the action of altering the argument. The methods that create new indices probably need a label on the first argument, because otherwise it looks as if the IndexDistance is what is described by ‘index’.

Proposed:

  func successor(of i: Index) -> Index
  func formSuccessor(i: inout Index)

Instead, I suggest:

  func successor(of i : Index) -> Index
  func advance(i: inout Index)

Proposed:

  func index(n: IndexDistance, stepsFrom i: Index) -> Index
  func index(n: IndexDistance, stepsFrom i: Index, limitedBy limit: Index) -> Index
  func formIndex(n: IndexDistance, stepsFrom i: inout Index)
  func formIndex(n: IndexDistance, stepsFrom i: inout Index, limitedBy limit: Index)

Suggested (taking into account Nate’s suggestion of reversing the order):

  func index(startingAt i: Index, movedBy n: IndexDistance) -> Index
  func index(startingAt i: Index, movedBy n: IndexDistance, limitedBy limit: Index) -> Index
  func move(i : inout Index, by n: IndexDistance)
  func move(i : inout Index, by n: IndexDistance, limitedBy limit: Index)

Proposed:

  func predecessor(of i: Index) -> Index
  func formPredecessor(i: inout Index)

Suggested:

  func predecessor(of i: Index) -> Index
  func reverse(i: inout Index)

I think reversing an index has some nice symmetry with reversing a sequence, but if it seems to confusing, then replace advance and reverse with ‘moveForward’ and ‘moveBackward’.

- Tony

···

On Apr 10, 2016, at 2:41 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

  * Is the problem being addressed significant enough to warrant a change to Swift?
  * Does this proposal fit well with the feel and direction of Swift?
  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(plx) #11

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.

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

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

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #12

We realized we neglected to propose this useful API:

    /// Conversion from one range to another.
    extension RangeProtocol where Bound : Strideable, Bound.Stride : Integer {
      /// Creates an instance equivalent to `other`.
      ///
      /// - Precondition: an equivalent range is representable as an
      /// instance of `Self`. For example, `Range(0...Int.max)`
      /// violates this precondition because an equivalent `Range<Int>`
      /// would need an `upperBound` equal to `Int.max + 1`, which
      /// is unrepresentable as an `Int`.
      public init<Other: RangeProtocol where Other.Bound == Bound>(_ other: Other)
    }

Please consider it added to the proposal, per
https://github.com/apple/swift-evolution/pull/255/.

···

--
Dave


(Howard Lovatt) #13

Review of:
https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

* What is your evaluation of the proposal?

I think it is a big improvement over the current collections API. However I
have a number of reservations, particularly:

   1. The motivation of improved performance smacks of "premature
   optimisation". For particularly high performance collections a fast unsafe
   form could be provided, like UnsafePointer, e.g. UnsafeArray. For the rest
   I think it is better to have a clean API rather than skew the API for
   performance.
   2. The proposed iterator, `collection.next(&iterator)`, is not as
   convenient to use as a classic external or internal iterator. It introduces
   the potential for errors where an iterator from one collection is used in
   another and where the collection and iterator are manipulated separately.
   What's the point of eliminating C for loops because of index problems and
   then introducing much the same? The new iterator cannot be type erased
   without also capturing the associated collection, defeating the point of
   the new iterators!
   3. The protocols are quite hierarchical; instead they could be a
   collection [sic] of small, top-level protocols that are plugged together. A
   useful division is one main method per protocol with 'good', default
   implementations provided for other methods. A 'good' implementation of
   count would not be iterating through the collection counting!
   4. The members, e.g. map, filter, return specific implementations like
   Array. I find this restrictive. Would it be possible to return a protocol
   to allow other implementations more flexibility.
   5. There is an advantage in splitting lazy into a separate hierarchy,
   there is precedence for this in that both Java, Stream, and C#, LINQ, do
   this. The main differences are that you would expect a collection to be
   multiple iterable, e.g. inside a nested loop, and mutable, e.g.
   subscriptable, whereas a lazy can only be guaranteed to be iterable once
   and is purely functional. This splitting of lazy into a separate API would
   also lay the groundwork for a parallel-lazy version.
   6. The naming of the protocols would be better if they were Xxxable and
   that xxx referred to the main method in the protocol. For example instead
   of Sequence, Iterable because its key feature is iterate.
   7. I think Range would be better if it has an Int index of 0 to count -
   1 and a value of start + index * stride, where start and stride are of type
   Arithmetic, i.e. range[index] = start + index * stride.

* Is the problem being addressed significant enough to warrant a change to
Swift?

Yes the current collections API could be improved and it is an important
part of any programming language.

* Does this proposal fit well with the feel and direction of Swift?

In some ways yes, it captures more of your intention in the type system.
But in other ways no, it introduces an iterative paradigm that is
potentially more error prone that the existing one and step back towards
using subscripts and index for everything, ie. C for loop style.

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

Obviously everyone uses collection API's in every language. I have used
collections in many diverse languages and also written custom collections,
e.g. a parallel collection API in Java before Java got a standard version.

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

Quite a bit, including fleshing out a minimal collection API that conforms
to the principles stated above and posted on swift-evolution under the new
iterator model discussions.

  -- Howard.

···

On 11 April 2016 at 07:41, Chris Lattner via swift-evolution < swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and
runs through April 18th. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md
<https://github.com/apple/swift-evolution/blob/master/proposals/0055-optional-unsafe-pointers.md>

Reviews are an important part of the Swift evolution process. All reviews
should be sent to the swift-evolution mailing list at:
https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the
review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:

* What is your evaluation of the proposal?
* Is the problem being addressed significant enough to warrant a change to
Swift?
* Does this proposal fit well with the feel and direction of Swift?
* If you have you used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?
* How much effort did you put into your review? A glance, a quick reading,
or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Patrick Gili) #14

  * What is your evaluation of the proposal?

1) I think eliminating intervals increases consistency and reduces confusion.

2) I really like the fact that this will make in-place index traversal methods public. It will reduce the amount of boilerplate for developers implementing new collections.

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes.

  * Does this proposal fit well with the feel and direction of Swift?

Yes.

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

Most modern languages provide a sophisticated library supporting collections. I think this proposal is moving the Swift Foundation in the direction of the C++ STL and Boost libraries.

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

In-depth.

···

(Chris Lattner) #15

A quick update: the core team met to discuss this. They agreed to accept it with some naming-related revisions to the proposal (in response to community feedback). Dave is organizing this feedback, and I’ll send out the formal announcement when that is ready.

-Chris

···

On Apr 10, 2016, at 2:41 PM, Chris Lattner <clattner@apple.com> wrote:

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md <https://github.com/apple/swift-evolution/blob/master/proposals/0055-optional-unsafe-pointers.md>

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
  https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.


(Karl) #16

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and runs through April 18th. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md<https://github.com/apple/swift-evolution/blob/master/proposals/0055-optional-unsafe-pointers.md>

Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at:
https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

* What is your evaluation of the proposal?
* Is the problem being addressed significant enough to warrant a change to Swift?
* Does this proposal fit well with the feel and direction of Swift?
* If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
* How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

So, just confirming that the following is going to change:

···

—————
var string = "test"
let origLen = 4
let indexOne = string.startIndex

string.appendContentsOf("ANOTHERTEST")

let indexTwo = indexOne.advancedBy(origLen, limit: string.endIndex)

assert(indexTwo<string.endIndex)
indexTwo.successor() //<--- fatal error: cannot increment endIndex
—————

Is this a consequence of the index needing to know its originating string for successor() purposes?
Once this is implemented, will String.Index be portable across string instances (presuming you bounds-check them, as I did above)?

Thanks

Karl


(Jacob Bandes-Storch) #17

Minor questions after initial read-through:

- Should the comment on {index,formIndex}(_:stepsFrom:) say what happens if
the resulting index would be out of bounds? Can these functions return
Optional values, or can they be `throws`?

- Can {index,formIndex}(_:stepsFrom:) be combined with the limitedBy:
versions, such that the limit is an *optional parameter* with default value
nil? For example:

    public func index(n: IndexDistance, stepsFrom i: Index, *limitedBy
limit: Index? = nil*)

Jacob

···

On Sun, Apr 10, 2016 at 2:45 PM, Chris Lattner via swift-evolution < swift-evolution@swift.org> wrote:

On Apr 10, 2016, at 2:41 PM, Chris Lattner <clattner@apple.com> wrote:

Hello Swift community,

The review of "A New Model for Collections and Indices" begins now and
runs through April 18th. The proposal is available here:

The correct link is:

https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md

-Chris

Reviews are an important part of the Swift evolution process. All reviews
should be sent to the swift-evolution mailing list at:
https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the
review manager.

What goes into a review?

The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:

* What is your evaluation of the proposal?
* Is the problem being addressed significant enough to warrant a change to
Swift?
* Does this proposal fit well with the feel and direction of Swift?
* If you have you used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?
* How much effort did you put into your review? A glance, a quick reading,
or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #18

Hi,

···

On Mon, Apr 11, 2016 at 9:16 AM, Gwendal Roué <swift-evolution@swift.org> wrote:

Will it still be possible with the new protocol and types? Especially, how to I generate "BETWEEN 0 AND 17" from 0..<18 without a supporting collection that gives me the predecessor of 18?

You would either design your API to accept a CountableRange, or a
Range where Bound conforms to Strideable.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Dmitri Gribenko) #19

You could also make your API generic over RangeProtocol where Bound
conforms to Strideable, check if the end point is contained in the
range (detecting closed ranges), and if it is not, perform the
adjustment.

Dmitri

···

On Mon, Apr 11, 2016 at 9:20 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

Hi,

On Mon, Apr 11, 2016 at 9:16 AM, Gwendal Roué <swift-evolution@swift.org> wrote:

Will it still be possible with the new protocol and types? Especially, how to I generate "BETWEEN 0 AND 17" from 0..<18 without a supporting collection that gives me the predecessor of 18?

You would either design your API to accept a CountableRange, or a
Range where Bound conforms to Strideable.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Trent Nadeau) #20

I disagree. According to both http://grammarist.com/usage/indexes-indices/
and http://www.worldwidewords.org/qa/qa-ind2.htm, "indices" is more common
in the English-speaking world (outside of parts of America and Canada) as
well as in technical contexts.

···

On Mon, Apr 11, 2016 at 12:29 PM, Joe Groff via swift-evolution < swift-evolution@swift.org> wrote:

I love irregular plurals as much as the next grammar nerd, but I think
it'd be better to use the more regular, but still correct, plural "indexes"
rather than "indices".

-Joe

> On Apr 10, 2016, at 2:41 PM, Chris Lattner via swift-evolution < > swift-evolution@swift.org> wrote:
>
> Hello Swift community,
>
> The review of "A New Model for Collections and Indices" begins now and
runs through April 18th. The proposal is available here:
>
>
https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md
>
> Reviews are an important part of the Swift evolution process. All
reviews should be sent to the swift-evolution mailing list at:
> https://lists.swift.org/mailman/listinfo/swift-evolution
> or, if you would like to keep your feedback private, directly to the
review manager.
>
>
> What goes into a review?
>
> The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:
>
> * What is your evaluation of the proposal?
> * Is the problem being addressed significant enough to warrant a
change to Swift?
> * Does this proposal fit well with the feel and direction of Swift?
> * If you have you used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?
> * How much effort did you put into your review? A glance, a quick
reading, or an in-depth study?
>
> More information about the Swift evolution process is available at
>
> https://github.com/apple/swift-evolution/blob/master/process.md
>
> Thank you,
>
> -Chris Lattner
> Review Manager
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Trent Nadeau