There's a slight problem that we also need a way to specify BidirectionalCollection.Element, .Index, .Indices, .SubSequence or any combination thereof to be useful.
Yes, that’s why BidirectionalCollection can’t be used as a variable type: we first need existential types that can wrap up all those unspecified associated types into a “best knowledge possible” interface that, for example, returns Any from a subscript if Element is unknown.
But none of that should be a problem for the is operation. Sylvain’s problem is they're just trying to use BidirectionalCollection as a tag protocol — a type relationship that indicates implementation behavior without exposing any additional API. No peering into associated types necessary for that.
2 Likes
I know this doesn't answer your question of casting to a protocol with associated type constraints, but have you tried using the following?
let lastIndex = collection.indices.last
I believe this would still allow collections to provide more efficient implementations through their Indices. I'm unsure if this is O(1) for bidirectional collections out-of-the-box, but for Array<T> it certainly is.
I don't see it, this example works only because self is already a collection of some sort, and that Index is for Collection is the same as Bidirectional collection. It wouldn't work if we go from Sequence to BidirectionalCollection because we don't know if Index matches (Self as BidirectionalCollection).Index.
In order to do what you want, we’d need somethihg like dynamic dispatch for protocol extension methods (Dynamically-dispatched protocol extension members).
There are iffy workarounds, like creating a closure-based type eraser with overloads for initialisation, but then you’d still need to construct it with a concrete type (it wouldn’t work in generic code).
There simply is no way today to conditionally downcast to a refined protocol if that protocol contains associated types.
There is no way to cast, but if you’re willing to write a bunch of boilerplate there is a way to conditionally “open” an existential in a way that brings conformance back into the type system for the duration of a callback. Here’s an example areEquatablyEqual.swift · GitHub. This is super clunky and we should improve the language in this area, but it is possible as a workaround today.
3 Likes
It's also not supported by the language. I encouraged Sylvain to post this as an evolution pitch because the simple is test for non-existential protocols makes complete sense as a language extension and is almost impossible to mis-specify, even if we do want fancier existential-opening capabilities some day.
8 Likes
I believe we should rethink what we can do with values implementing protocols with associated types in general. Especially when we know that a value conforms to such a protocol, but not what these associated types are. @sgugger gave a great example above.
Another issue that I often run into is the following:
protocol P { // Protocol with Self or associated type requirement
func foo(_ x: Self) {}
func bar() {}
}
let array: [P] // protocol 'P' can only be used as generic constraint because it has Self or associated type requirements
Note that P might also inherit the Self or associatedtype requirements, e.g. if it refines Equatable.
Admittedly, such an array of P might not be what one might initially expect (we can't do things like array[0].foo(array[1]) or compare elements if P refines Equatable because the elements might be different concrete types), but we could still safely use all other methods, like array[0].bar()!
Today's workaround is splitting the protocols in two parts:
protocol P {
func bar() {}
}
protocol Q: P {
func foo(_ x: Self) {}
}
let array: [P]
That works, but isn't nice. Plus we can't use this workaround when we don't own the protocol hierarchy, such as in the example with BidirectionalCollection.
I guess we could also use Any*-style type erasers?
Either way, I think being able to use such protocols as standalone types and not only as generic constraints would open up lots of possibilities. Would it be possible to allow the definition of let array: [P] above and have array[0] be of type some P? What do you guys think?
Yeah, I'm all in favor of improving the language. I was just trying to make a point of fact that there is a workaround people can use if they really need to.
That's a somewhat controversial question that's been covered many times elsewhere in these forums (look for “generalized existentials”), and a whole other can of worms than what Sylvain is proposing.
It's O(1) for bidirectional collections, but doesn't compile for plain Collection, which is the problem.
Ah, I didn't realize last is only added to the collection hierarchy as a requirement on BidirectionalCollection. Thanks for pointing that out, @dabrahams.
My impression is that this should work as expected for is, but that would still not give that much as you might often want to know that it conforms to a PAT and has specific associatedtypes.
One way that I think would be pretty natural (once the language evolves in that part) is to have if let self = self as? some BidirectionalCollection<.Element = Int> { ..., which allows you to use the result in many more ways
Yes — and the obvious syntax now (is SomeProtocolWithAssociatedTypes) would almost certainly remain compatible with that bigger better existential world of the future.
It seems a sensible and straightforward proposal, and I would support it.
1 Like
You can also make lastIndex a requirement of a new protocol, and provide default implementations:
protocol LastIndex: Collection {
public func lastIndex() -> Index
}
extension LastIndex where Self: BidirectionalCollection {
public func lastIndex() -> Index {
print("BidirectionalCollection implementation")
return index(endIndex, offsetBy: -1)
}
}
extension LastIndex where Self: Collection {
public func lastIndex() -> Index {
print("Collection implementation")
return indices.max()!
}
}
It would be nice if we had a mechanism for extending protocols with additional dispatched requirements. I think that would be a more robust approach than using dynamic casting or existentials; finding a protocol conformance dynamically has performance and semantic issues that are hard to avoid.
2 Likes
Heh, there are at least two problems with this approach. The first is that you need to explicitly make every Collection conform to LastIndex. The second is that if your generic collection conditionally conforms to BidirectionalCollection, you'll get the O(N) implementation unconditionally from a generic context.
It would be nice if we had a mechanism for extending protocols with additional dispatched requirements.
+1; we had a pitch on these forums for such a feature recently but I can't find it.
The restriction with "is" not accepting protocols that have associated types is artificial. It could be lifted and it would work. However, as others have pointed out, this has limited utility because there is no way to operate on the value, or to cast its associated types.
3 Likes
Sure, but it is a real solution to a real problem, here or in any case where the protocol in question is (or at least for the purpose of the code in question functions as) a marker interface / tag interface that indicates a contract that adds no API surface. In that situation, there's no need to peer into associated types; the obvious solution is a good one.
Given that the problem is real albeit narrow, given how hairy the current workaround (per @anandabits) is, and given that the solution is straightforward and non-breaking, it does seem like a sensible proposal.
Keep in mind that is/as? Protocol is always an expensive dynamic check if the type is not statically known to conform to the protocol, because the compiler cannot know whether conformances are added to a type externally.
3 Likes
This is one reason why I think that a good rule of thumb with these algorithms is, if you need to do this check, the first assumption should be you have taken a wrong turn.
In this case, it seems like you just need to check and go down the O(n) path. And if it's a one-off, that might be worth doing. But the OP states that this is in pursuit of implementing quickselect, the implementation of which will probably need random access to select the pivot.
In many cases, probably including quickselect, the idea you can have one algorithm service both forward-only and random-access collections just by having specific customization points for things like advancing an index is an illusion. In practice, if you know up front you're operating on a non-random-access (or non-bidirectional) collection, you'd be better off taking a completely different approach. If you push this requirement far enough up the chain, you end up at a concrete type and the user can make that decision for you, or you can make it via overloading at the top level (like reversed does – it returns an array for forward-only collections, but a lazy view for bidirectional ones).
This isn't a universal rule – there are some algorithms that could benefit from extra customization points. But if we had the benefit of a feature that let us add arbitrary customization points to a protocol, I expect you'd want to use them to be algorithm-specific rather than algorithm-building-block-specific (i.e. use mergesort instead of quicksort to implement sort on non-random-access collections).
6 Likes