[Pre-proposal] Forward/Reverse Only Indexing Methods


(Haravikk) #1

So for Swift 3 we’re going to have the great new indexing model that performs index manipulation through the collection to which an index belongs.

However, it retains one of the things I didn’t like about the old model, which is that the distinction between forward/backward only types is a bit fuzzy, since the single advancedBy() method, now the index(:offsetBy:) method, was used for both forward and backward movement, which seems contradictory compared to the forward/backward only single-step methods.

Anyway, I’m wondering what people’s thoughts would be on tweaking the formula slightly such that there are methods that only work in a particular direction, i.e- we’d have three main variations of the methods like so:

    public func index(_ index:Index, advancedBy:Index.Distance) -> Index { … } // Available on forward and bidirectional collections
    public func index(_ index:Index, reversedBy:Index.Distance) -> Index { … } // Available on reverse and bidirectional collections
    public func index(_ index:Index, offsetBy:Index.Distance) -> Index { … } // Available only on bidirectional collections

(note, the naming isn’t definite, as reversed may not be clear enough, it’s just an example for now)

There are three reasons I’d prefer this:

The first is that I can pass the same distance into either of the first two methods, and any negation etc. is handled internally. In essence I shouldn’t have to handle negative distances at all when working with the first two methods. So if I’m working with a step size of 5, I can just pass that into the appropriate method, I never have to do anything with it the value itself.

The second benefit is that there should be no uncertainty about the capabilities of the type you’re using; if it doesn’t have the index(:reversedBy:) method then you can’t go backwards, same as index(before:) and index(after:).

The third and main benefit is that the methods are just more explicit about what they do, and what direction you can go in; passing negatives into either of the first two would produce errors outright, allowing you to pick on mistakes in these cases.

The other main thing is that offsetBy doesn’t indicate whether a type supports forward-only offsets, you have to read the documentation to determine this either in the method itself or the type, whereas the presence or absence of the first two variants are pretty clear.

Currently the offsetBy, and the previous advancedBy(), methods require forward-only types to produce fatal errors if handed a negative distance, and vice versa for backward-only types, which can only produce errors at runtime, whereas the presence or absence of the first two methods can be handled during development. You could still pass a negative value and end up with a runtime error instead of course, but for the types of common uses they’re intended for you should be unlikely to produce one.

The offsetBy form would still exist for bidirectional collections, but would only really be used when you need to do more complex index/distance manipulation outside of the type where a calculation might produce either positive or negative values (e.g- if you're calculating the distance and don’t know where two indices are in relation to each other), the rest of the time you should try to use the more specific, single-direction forms as they clarify your intent and can help to catch mistakes if you’ve incorrectly generated a distance for example.

Just curious what other people’s thoughts are about this?

I intended to mention this a lot sooner (to change advancedBy), but then I find out about the new indexing model so thought I’d wait until afterwards, then completely forgot =)


(Thorsten Seitz) #2

I like this idea. The problem is that it would require that we have an Index.NonNegativeDistance as argument to really make it statically safe. And we would have to have methods producing these, probably as optional return values.
Otherwise we won't have achieved statically safety but effectively just better documentation about the capabilities of the respective collection.

-Thorsten

···

Am 31.05.2016 um 14:46 schrieb Haravikk via swift-evolution <swift-evolution@swift.org>:

So for Swift 3 we’re going to have the great new indexing model that performs index manipulation through the collection to which an index belongs.

However, it retains one of the things I didn’t like about the old model, which is that the distinction between forward/backward only types is a bit fuzzy, since the single advancedBy() method, now the index(:offsetBy:) method, was used for both forward and backward movement, which seems contradictory compared to the forward/backward only single-step methods.

Anyway, I’m wondering what people’s thoughts would be on tweaking the formula slightly such that there are methods that only work in a particular direction, i.e- we’d have three main variations of the methods like so:

    public func index(_ index:Index, advancedBy:Index.Distance) -> Index { … } // Available on forward and bidirectional collections
    public func index(_ index:Index, reversedBy:Index.Distance) -> Index { … } // Available on reverse and bidirectional collections
    public func index(_ index:Index, offsetBy:Index.Distance) -> Index { … } // Available only on bidirectional collections

(note, the naming isn’t definite, as reversed may not be clear enough, it’s just an example for now)

There are three reasons I’d prefer this:

The first is that I can pass the same distance into either of the first two methods, and any negation etc. is handled internally. In essence I shouldn’t have to handle negative distances at all when working with the first two methods. So if I’m working with a step size of 5, I can just pass that into the appropriate method, I never have to do anything with it the value itself.

The second benefit is that there should be no uncertainty about the capabilities of the type you’re using; if it doesn’t have the index(:reversedBy:) method then you can’t go backwards, same as index(before:) and index(after:).

The third and main benefit is that the methods are just more explicit about what they do, and what direction you can go in; passing negatives into either of the first two would produce errors outright, allowing you to pick on mistakes in these cases.

The other main thing is that offsetBy doesn’t indicate whether a type supports forward-only offsets, you have to read the documentation to determine this either in the method itself or the type, whereas the presence or absence of the first two variants are pretty clear.

Currently the offsetBy, and the previous advancedBy(), methods require forward-only types to produce fatal errors if handed a negative distance, and vice versa for backward-only types, which can only produce errors at runtime, whereas the presence or absence of the first two methods can be handled during development. You could still pass a negative value and end up with a runtime error instead of course, but for the types of common uses they’re intended for you should be unlikely to produce one.

The offsetBy form would still exist for bidirectional collections, but would only really be used when you need to do more complex index/distance manipulation outside of the type where a calculation might produce either positive or negative values (e.g- if you're calculating the distance and don’t know where two indices are in relation to each other), the rest of the time you should try to use the more specific, single-direction forms as they clarify your intent and can help to catch mistakes if you’ve incorrectly generated a distance for example.

Just curious what other people’s thoughts are about this?

I intended to mention this a lot sooner (to change advancedBy), but then I find out about the new indexing model so thought I’d wait until afterwards, then completely forgot =)
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Haravikk) #3

I like this idea. The problem is that it would require that we have an Index.NonNegativeDistance as argument to really make it statically safe. And we would have to have methods producing these, probably as optional return values.
Otherwise we won't have achieved statically safety but effectively just better documentation about the capabilities of the respective collection.

-Thorsten

So you’d see something like:

  public func distance(from start:Index, advancedTo end:Index) -> Index.NonNegativeDistance? { … }
  public func distance(from start:Index, reversedTo end:Index) -> Index.NonNegativeDistance? { … }

Or something to that effect anyway, with the single-direction index (and formIndex etc.) methods taking the same type?. That’s clever, eliminates the run-time error for distance in many cases with a type-check at compile time instead, neat!

This could actually present an interesting possibility by designing around the fixed direction methods first, e.g- the NonNegativeDistance could be a Uint, and regular Distance would be an enum with .Forward(UInt) and .Backward(UInt) cases. I’m currently porting some of my simpler collections to Swift 3 to get some more experience with the new indexing model and other changes, and this would be a nice way to do it for some of these, rather than relying on a regular Int.

···

On 1 Jun 2016, at 05:51, Thorsten Seitz <tseitz42@icloud.com> wrote:

Am 31.05.2016 um 14:46 schrieb Haravikk via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>>:

So for Swift 3 we’re going to have the great new indexing model that performs index manipulation through the collection to which an index belongs.

However, it retains one of the things I didn’t like about the old model, which is that the distinction between forward/backward only types is a bit fuzzy, since the single advancedBy() method, now the index(:offsetBy:) method, was used for both forward and backward movement, which seems contradictory compared to the forward/backward only single-step methods.

Anyway, I’m wondering what people’s thoughts would be on tweaking the formula slightly such that there are methods that only work in a particular direction, i.e- we’d have three main variations of the methods like so:

    public func index(_ index:Index, advancedBy:Index.Distance) -> Index { … } // Available on forward and bidirectional collections
    public func index(_ index:Index, reversedBy:Index.Distance) -> Index { … } // Available on reverse and bidirectional collections
    public func index(_ index:Index, offsetBy:Index.Distance) -> Index { … } // Available only on bidirectional collections

(note, the naming isn’t definite, as reversed may not be clear enough, it’s just an example for now)

There are three reasons I’d prefer this:

The first is that I can pass the same distance into either of the first two methods, and any negation etc. is handled internally. In essence I shouldn’t have to handle negative distances at all when working with the first two methods. So if I’m working with a step size of 5, I can just pass that into the appropriate method, I never have to do anything with it the value itself.

The second benefit is that there should be no uncertainty about the capabilities of the type you’re using; if it doesn’t have the index(:reversedBy:) method then you can’t go backwards, same as index(before:) and index(after:).

The third and main benefit is that the methods are just more explicit about what they do, and what direction you can go in; passing negatives into either of the first two would produce errors outright, allowing you to pick on mistakes in these cases.

The other main thing is that offsetBy doesn’t indicate whether a type supports forward-only offsets, you have to read the documentation to determine this either in the method itself or the type, whereas the presence or absence of the first two variants are pretty clear.

Currently the offsetBy, and the previous advancedBy(), methods require forward-only types to produce fatal errors if handed a negative distance, and vice versa for backward-only types, which can only produce errors at runtime, whereas the presence or absence of the first two methods can be handled during development. You could still pass a negative value and end up with a runtime error instead of course, but for the types of common uses they’re intended for you should be unlikely to produce one.

The offsetBy form would still exist for bidirectional collections, but would only really be used when you need to do more complex index/distance manipulation outside of the type where a calculation might produce either positive or negative values (e.g- if you're calculating the distance and don’t know where two indices are in relation to each other), the rest of the time you should try to use the more specific, single-direction forms as they clarify your intent and can help to catch mistakes if you’ve incorrectly generated a distance for example.

Just curious what other people’s thoughts are about this?

I intended to mention this a lot sooner (to change advancedBy), but then I find out about the new indexing model so thought I’d wait until afterwards, then completely forgot =)
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #4

Sorry, I can't seem to find the original message.

So for Swift 3 we’re going to have the great new indexing model that
performs index manipulation through the collection to which an index
belongs.

However, it retains one of the things I didn’t like about the old
model, which is that the distinction between forward/backward only
types is a bit fuzzy, since the single advancedBy() method, now the
index(:offsetBy:) method, was used for both forward and backward
movement, which seems contradictory compared to the forward/backward
only single-step methods.

Anyway, I’m wondering what people’s thoughts would be on tweaking
the formula slightly such that there are methods that only work in a
particular direction, i.e- we’d have three main variations of the
methods like so:

    public func index(_ index:Index, advancedBy:Index.Distance) ->
Index { … } // Available on forward and bidirectional collections
    public func index(_ index:Index, reversedBy:Index.Distance) ->
Index { … } // Available on reverse and bidirectional collections
    public func index(_ index:Index, offsetBy:Index.Distance) ->
Index { … } // Available only on bidirectional collections

(note, the naming isn’t definite, as reversed may not be clear
enough, it’s just an example for now)

There are three reasons I’d prefer this:

The first is that I can pass the same distance into either of the
first two methods, and any negation etc. is handled internally. In
essence I shouldn’t have to handle negative distances at all when
working with the first two methods. So if I’m working with a step
size of 5, I can just pass that into the appropriate method, I never
have to do anything with it the value itself.

I don't understand why that's an advantage. The Distance is required to
be a signed integer type, so you can always negate it.

The second benefit is that there should be no uncertainty about the
capabilities of the type you’re using; if it doesn’t have the
index(:reversedBy:) method then you can’t go backwards, same as
index(before:) and index(after:).

That's nice... but then you *don't* propose to handle negation
internally in that case?

The third and main benefit is that the methods are just more
explicit about what they do, and what direction you can go in;
passing negatives into either of the first two would produce errors
outright, allowing you to pick on mistakes in these cases.

The other main thing is that offsetBy doesn’t indicate whether a
type supports forward-only offsets, you have to read the
documentation to determine this either in the method itself or the
type, whereas the presence or absence of the first two variants are
pretty clear.

Yes, we are not entirely pleased with the fact that there is no
syntactic differentiation between BidirectionalCollection and
RandomAccessCollection. We think protocol refinements are easier to
understand when they introduce new requirements. On the other hand, it
is important to have a function, somewhere, that advances an index by N
steps, as efficiently as possible based on the collection's traversal
capability. The natural place for that function is in a protocol
requirement.

Currently the offsetBy, and the previous advancedBy(), methods
require forward-only types to produce fatal errors if handed a
negative distance,

[Nit: actually they don't; your conforming forward-only Collection can
legally produce any result it likes when asked to traverse backward.]

and vice versa for backward-only types,

There's no such thing as a backward-only collection. If you had one, you
might as well exchange the meaning of forward and backward.

which can only produce errors at runtime, whereas the presence or
absence of the first two methods can be handled during
development. You could still pass a negative value and end up with a
runtime error instead of course, but for the types of common uses
they’re intended for you should be unlikely to produce one.

The offsetBy form would still exist for bidirectional collections,
but would only really be used when you need to do more complex
index/distance manipulation outside of the type where a calculation
might produce either positive or negative values (e.g- if you're
calculating the distance and don’t know where two indices are in
relation to each other), the rest of the time you should try to use
the more specific, single-direction forms as they clarify your
intent and can help to catch mistakes if you’ve incorrectly
generated a distance for example.

Just curious what other people’s thoughts are about this?

In general, indexing is a fairly low-level means of access to a
collection, as it fundamentally exposes difficult semantics (distinct
index instances can refer to the same element, and indices can become
invalid). It is important to make indexing usable, but I'm not very
sure the changes you're proposing would help. To evaluate that, we
should see how your changes affect the writing of algorithms that do
indexing, like those in the standard library and in
https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift

I suggest you try your changes in the standard library and show us what
happens to the algorithms. Are they clearer? Would your changes be
likely to have prevented a bug?

I intended to mention this a lot sooner (to change advancedBy), but
then I find out about the new indexing model so thought I’d wait
until afterwards, then completely forgot =)
_______________________________________________
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

I like this idea. The problem is that it would require that we have an
Index.NonNegativeDistance as argument to really make it statically
safe. And we would have to have methods producing these, probably as
optional return values.
Otherwise we won't have achieved statically safety but effectively
just better documentation about the capabilities of the respective
collection.

As of today, negative index distances have meaning even in a forward
collection, since all indices are comparable. So you can measure the
distance between any two indices as long as they are valid in the same
collection. [I'm beginning to regret making all indices comparable a
little, but that's a separate discussion...]

···

on Tue May 31 2016, Thorsten Seitz <swift-evolution@swift.org> wrote:

Am 31.05.2016 um 14:46 schrieb Haravikk via swift-evolution >> <swift-evolution@swift.org>:

--
-Dave


(Thorsten Seitz) #5

I like this idea. The problem is that it would require that we have an Index.NonNegativeDistance as argument to really make it statically safe. And we would have to have methods producing these, probably as optional return values.
Otherwise we won't have achieved statically safety but effectively just better documentation about the capabilities of the respective collection.

-Thorsten

So you’d see something like:

  public func distance(from start:Index, advancedTo end:Index) -> Index.NonNegativeDistance? { … }
  public func distance(from start:Index, reversedTo end:Index) -> Index.NonNegativeDistance? { … }

Or something to that effect anyway, with the single-direction index (and formIndex etc.) methods taking the same type?. That’s clever, eliminates the run-time error for distance in many cases with a type-check at compile time instead, neat!

Yes, that's what I meant.

This could actually present an interesting possibility by designing around the fixed direction methods first, e.g- the NonNegativeDistance could be a Uint, and regular Distance would be an enum with .Forward(UInt) and .Backward(UInt) cases. I’m

That's a good idea! I'd like to see how some real algorithms would look like with that approach.

-Thorsten

···

Am 03.06.2016 um 21:20 schrieb Haravikk <swift-evolution@haravikk.me>:

On 1 Jun 2016, at 05:51, Thorsten Seitz <tseitz42@icloud.com> wrote:

currently porting some of my simpler collections to Swift 3 to get some more experience with the new indexing model and other changes, and this would be a nice way to do it for some of these, rather than relying on a regular Int.

Am 31.05.2016 um 14:46 schrieb Haravikk via swift-evolution <swift-evolution@swift.org>:

So for Swift 3 we’re going to have the great new indexing model that performs index manipulation through the collection to which an index belongs.

However, it retains one of the things I didn’t like about the old model, which is that the distinction between forward/backward only types is a bit fuzzy, since the single advancedBy() method, now the index(:offsetBy:) method, was used for both forward and backward movement, which seems contradictory compared to the forward/backward only single-step methods.

Anyway, I’m wondering what people’s thoughts would be on tweaking the formula slightly such that there are methods that only work in a particular direction, i.e- we’d have three main variations of the methods like so:

    public func index(_ index:Index, advancedBy:Index.Distance) -> Index { … } // Available on forward and bidirectional collections
    public func index(_ index:Index, reversedBy:Index.Distance) -> Index { … } // Available on reverse and bidirectional collections
    public func index(_ index:Index, offsetBy:Index.Distance) -> Index { … } // Available only on bidirectional collections

(note, the naming isn’t definite, as reversed may not be clear enough, it’s just an example for now)

There are three reasons I’d prefer this:

The first is that I can pass the same distance into either of the first two methods, and any negation etc. is handled internally. In essence I shouldn’t have to handle negative distances at all when working with the first two methods. So if I’m working with a step size of 5, I can just pass that into the appropriate method, I never have to do anything with it the value itself.

The second benefit is that there should be no uncertainty about the capabilities of the type you’re using; if it doesn’t have the index(:reversedBy:) method then you can’t go backwards, same as index(before:) and index(after:).

The third and main benefit is that the methods are just more explicit about what they do, and what direction you can go in; passing negatives into either of the first two would produce errors outright, allowing you to pick on mistakes in these cases.

The other main thing is that offsetBy doesn’t indicate whether a type supports forward-only offsets, you have to read the documentation to determine this either in the method itself or the type, whereas the presence or absence of the first two variants are pretty clear.

Currently the offsetBy, and the previous advancedBy(), methods require forward-only types to produce fatal errors if handed a negative distance, and vice versa for backward-only types, which can only produce errors at runtime, whereas the presence or absence of the first two methods can be handled during development. You could still pass a negative value and end up with a runtime error instead of course, but for the types of common uses they’re intended for you should be unlikely to produce one.

The offsetBy form would still exist for bidirectional collections, but would only really be used when you need to do more complex index/distance manipulation outside of the type where a calculation might produce either positive or negative values (e.g- if you're calculating the distance and don’t know where two indices are in relation to each other), the rest of the time you should try to use the more specific, single-direction forms as they clarify your intent and can help to catch mistakes if you’ve incorrectly generated a distance for example.

Just curious what other people’s thoughts are about this?

I intended to mention this a lot sooner (to change advancedBy), but then I find out about the new indexing model so thought I’d wait until afterwards, then completely forgot =)
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #6

Exactly.

···

on Sat Jun 04 2016, Thorsten Seitz <swift-evolution@swift.org> wrote:

That's a good idea! I'd like to see how some real algorithms would
look like with that approach.

--
-Dave