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.
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.
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).
I wonder if that's an argument for:
protocol Collection {
var isBidirectional: Bool { get } // on the protocol itself, so virtual dispatch
}
extension Collection {
var isBidirectional: Bool { false }
}
extension BidirectionalCollection {
var isBidirectional: Bool { true } // would be nice if Swift supported `final` here
}
�
Yeah, or maybe some other way of opting into keeping cheap "dynamic cast" information inside a protocol hierarchy. This sort of reminds me of the problem @dabrahams discussed in this thread, where in order to be able to specialize a protocol requirement in a conditional conformance without resorting to global dynamic searches for the conformances, we might need some way to explicitly mark optional conformance requirements.
Yeah, this is a really sticky area of the language, one where my reasoning often fails. The root of it all, I think, is that Swift extensions can express two very different things:
- properties of values themselves, but also
- properties values acquire from local assumptions in the context where theyāre used.
Itās confusing that extension
means both of these things.
In Daveās example in that second link, this dynamically dispatched code:
extension P {
static var isEquatable: Bool { false }
}
ā¦is something that the value itself knows ā āI am not equatableā ā whereas this statically dispatched code (which if I understand correctly is a shadow, not an override):
extension P where Self : Equatable {
static var isEquatable: Bool { true }
}
ā¦is tied to something the calling context knows ā āif you think I implement the Equatable
protocol, then I guess Iām equatable!ā Daveās example goes haywire because the local assumptions (the static types) that could expose this isEquatable
implementation donāt travel around with the value itself.
This all makes sense in terms of the language specification and implementation, but itās hard to reason intuitively about. It feels like the Liskov Substitution Principleās bohemian cousin.
Back to the problem at hand: I donāt think you can get things to make sense again here without doing some kind of runtime test based on metadata that lives with the value itself. Whether thatās an expensive type metadata search with is
or the vtable lookup I sketched, it has to be dynamic.
It's all very well to say that, and of course we would rather not do any ugly type-switching, but the language's current limitations on generic dispatching leaves us few options today. Rather than asking for the feature we'd really want, which is hard to implement and specify, we thought we should ask for the obvious, conservative, easy-to-implement language extension that makes sense.
No, it doesn't, as you can easily see by inspecting the pseudocode: immediately after selecting the pivot from a range of elements, the algorithm does an O(N) traversal of that same range to partition it. Therefore, if choosing a pivot devolves to O(N) traversal of that range in the non-random-access case, it doesn't change the algorithm's complexity at all.
(Also, choosing a pivot other than the first element isn't necessarily important if you're going on to implement introselect, because you handle the pathological cases with a fallback algorithm. But that's neither here nor there; I just added it because I like to talk about algorithms ;-}).
Incidentally, Matthew/@anandabits, I don't see any way to use _openExistential
to solve the problem Sylvain posted about, do you? The challenge is to implement this property:
extension Collection {
/// Returns `true` if `self` conforms to `BidirectionalCollection`.
var isBidirectional: Bool { /* your code here */ }
}
Thanks,
Dave
Ah you're right, my bad.
The challenge is to implement this property:
extension Collection { /// Returns `true` if `self` conforms to `BidirectionalCollection`. var isBidirectional: Bool { /* your code here */ } }
It there's a strong case here to add this particular customization point, it's easily done via an evolution proposal. I'm pretty sure we have the ability to add customization points ABI-stably (though not back deploy them).
You're right that _openExistential
does not help. I discovered a (admittedly rather clunky) pattern that does support opening arbitrary constraints and therefore allows this property to be implemented. You can find my implementation of isBidrectional
using this pattern here: isBidirectional.swift Ā· GitHub.
If you're able to clean up the implementation at all please let me know! And if you're able to push language improvements that let me toss this pattern into the dustbin even better.
Wow, thanks! I'm going to have to spend some time studying this code⦠and I will accept your invitation to try to simplify it.
Absolutely, I'm not giving up on those.
Thanks for the invitation, but wouldn't it be a lot more useful to have a generalized is
test than a one-off addition to the standard library? Either one is (I think) easily done via an evolution proposal, after all. Of course, if the language feature turns out to be unexpectedly hard to implement, I'll gratefully take you up on it.
If we literally just want the Bool
result for isBidirectional
, thatās actually pretty easy. Hereās a quick demo for all 5 of the standard Collection
subprotocols.
First some empty enums:
enum BidirectionalCollectionMarker<T> {}
enum LazyCollectionMarker<T> {}
enum MutableCollectionMarker<T> {}
enum RandomAccessCollectionMarker<T> {}
enum RangeReplaceableCollectionMarker<T> {}
Then some empty conformances:
protocol ConformanceMarker {}
extension BidirectionalCollectionMarker : ConformanceMarker where T: BidirectionalCollection {}
extension LazyCollectionMarker : ConformanceMarker where T: LazyCollectionProtocol {}
extension MutableCollectionMarker : ConformanceMarker where T: MutableCollection {}
extension RandomAccessCollectionMarker : ConformanceMarker where T: RandomAccessCollection {}
extension RangeReplaceableCollectionMarker: ConformanceMarker where T: RangeReplaceableCollection {}
And finally the Collection
properties:
extension Collection {
var isBidirectional : Bool { BidirectionalCollectionMarker<Self>.self is ConformanceMarker.Type }
var isLazy : Bool { LazyCollectionMarker<Self>.self is ConformanceMarker.Type }
var isMutable : Bool { MutableCollectionMarker<Self>.self is ConformanceMarker.Type }
var isRandomAccess : Bool { RandomAccessCollectionMarker<Self>.self is ConformanceMarker.Type }
var isRangeReplaceable: Bool { RangeReplaceableCollectionMarker<Self>.self is ConformanceMarker.Type }
}
For actual use, it probably makes sense to have static Collection.isX
properties as well, in which case the instance properties could just call Self.isX
.
In any event, hereās a helper for checking all the capabilities of a Collection
instance:
CollectionCapabilities
struct CollectionCapabilities {
var isBidirectional : Bool
var isLazy : Bool
var isMutable : Bool
var isRandomAccess : Bool
var isRangeReplaceable: Bool
}
extension Collection {
var capabilities: CollectionCapabilities {
CollectionCapabilities(
isBidirectional : isBidirectional,
isLazy : isLazy,
isMutable : isMutable,
isRandomAccess : isRandomAccess,
isRangeReplaceable: isRangeReplaceable
)
}
}
⢠⢠ā¢
Edit: Hereās a slight variation that adds a 2nd empty protocol in order to shorten the line length of the Collection
properties, and make things read a little better:
Version 2
extension Collection {
var isBidirectional : Bool { BidirectionalCollectionMarker<Self>.conforms }
var isLazy : Bool { LazyCollectionMarker<Self>.conforms }
var isMutable : Bool { MutableCollectionMarker<Self>.conforms }
var isRandomAccess : Bool { RandomAccessCollectionMarker<Self>.conforms }
var isRangeReplaceable: Bool { RangeReplaceableCollectionMarker<Self>.conforms }
}
protocol ConformanceMarker {}
extension ConformanceMarker {
static var conforms: Bool { Self.self is Conforming.Type }
}
enum BidirectionalCollectionMarker<T> : ConformanceMarker {}
enum LazyCollectionMarker<T> : ConformanceMarker {}
enum MutableCollectionMarker<T> : ConformanceMarker {}
enum RandomAccessCollectionMarker<T> : ConformanceMarker {}
enum RangeReplaceableCollectionMarker<T>: ConformanceMarker {}
protocol Conforming {}
extension BidirectionalCollectionMarker : Conforming where T: BidirectionalCollection {}
extension LazyCollectionMarker : Conforming where T: LazyCollectionProtocol {}
extension MutableCollectionMarker : Conforming where T: MutableCollection {}
extension RandomAccessCollectionMarker : Conforming where T: RandomAccessCollection {}
extension RangeReplaceableCollectionMarker: Conforming where T: RangeReplaceableCollection {}
Well, I never did understand what you were up to there, after reading about 10 lines I had an idea and solved it a bit more simply:
And now I see that Nevin posted another simple solution that uses basically the same technique.
The technique I posted was developed to be able to open value(s) and actually use the conformance (if it exists). I didnāt think about whether a simpler approach exists when only need to detect the conformance without actually using it. Good to know that there is one.
All right, Iāve wrapped my head around your protocol opening system @anandabits, thatās pretty clever!
When I first tried to build a protocol opener following your pattern, I thought I was doing something wrong because it kept crashing. However, it turns out I just discovered a rough edge.
Specifically, if you take your struct that conforms to the opener protocol, and constrain its generic type (the proxy) to have non-trivial conformances on the associated types of its associated type (and provide corresponding constraints on the top-level call site), then the program compiles but the receive
method crashes at runtime. Even attempting to print(self)
crashes!
In my case, I was writing a struct to open collections as BidirectionalCollection
, and the algorithm I chose to implement for my testing was āFind the longest suffix that 2 collections share, and return a tuple of the indices of the first element in that suffix from each collection.ā
So I made my top-level call site have the constraint T: Collection where T.Element: Equatable
, I set up my openers to test for BidirectionalCollection
conformance, and I made my struct constrain its proxy with where Proxy.Proxied: Collection, Proxy.Proxied.Element: Equatable
.
The whole thing compiled, and traversed through the trampoline, and reached the receive
method, then crashed.
I actually had changed all the names of protocols and types and functions to help myself better comprehend what they did, so I was worried I might have inadvertently made a mistake.
But eventually I discovered that if I removed the Equatable
constraint, added an equalBy
predicate to the struct, and made the top-level call site pass in (==)
for it, then it ran without crashing and successfully executed the algorithm on BidirectionalCollections
, while returning nil for other collections.
I could also make it dynamically check for BidirectionalCollection where Element: Equatable
, but I was hoping to make use of an existing known conformance to Equatable
while dynamically checking for the other. Unfortunately that crashed.
@dabrahams, if youāre interested in how Mattās dynamic opener works, Iāve distilled it down to something hopefully easier to explain. I actually eliminated his ātrampolineā type entirely, though I will explain at the end why itās useful to include.
For this exercise, letās say we want to take a Numeric
value, and if it actually conforms to SignedNumeric
then negate it. So weāre dynamically dispatching based on a conformance we donāt know statically.
⢠⢠ā¢
Part 1: Two short protocols
To start off, hereās the primary protocol:
protocol AttemptIfSigned {
associatedtype Wrapped
associatedtype Result
func action<T: SignedNumeric>(_ t: T.Type) -> Result where T == Wrapped
}
Wrapped
is the type we start with and want to dynamically dispatch, and Result
is the result type of whatever we do with it. In our example they will be the same types, but Iāve left them both for completeness.
The action
function signature represents the bulk of the cleverness, so letās break it down. In order to call that function, we need to pass in a type which both conforms to SignedNumeric
, and also equals Wrapped
.
That means within the body of the action
function, we are guaranteed that Wrapped
conforms to SignedNumeric
, hence we can do things like negate values of type Wrapped
. Now we just need to find a way to call it.
That brings us to our second protocol:
protocol KnownSignedNumeric {
static func performAction<T: AttemptIfSigned>(_ t: T) -> T.Result
}
The trick is that we will only ever conform to this protocol conditionally, when Wrapped
conforms to SignedNumeric
, and we will only ever call performAction
with T
matching the action weāre using.
Hereās how we call it:
extension AttemptIfSigned {
func attemptAction() -> Result? {
(Self.self as? KnownSignedNumeric.Type)?.performAction(self)
}
}
The attemptAction
function is our main entry-point. Itās what weāll actually call when we want to dynamically attempt an action. And all it does is check whether we are KnownSignedNumeric
, and if so pass our action to performAction
.
Note that performAction
is generic specifically to avoid an associated type on KnownSignedNumeric
, so that we can cast to that protocol inside attemptAction
.
Part 2: A little prep work
Thatās it for the high-level setup, now we need to write a conforming type to represent the action we want. Weāll call it NegateIfSigned
, but before we get to the type itself, letās see how it conforms to KnownSignedNumeric
:
extension NegateIfSigned: KnownSignedNumeric where Wrapped: SignedNumeric {
static func performAction<T: AttemptIfSigned>(_ t: T) -> T.Result {
(t as! Self).action(Wrapped.self) as! T.Result
}
}
The constraint on this extension is where we establish that Wrapped
conforms to SignedNumeric
, which allows us to call action
by passing in Wrapped
.
To do so, we need to convert back and forth between T
and Self
, but that will always succeed because performAction
is only ever called by passing in self
.
(Matt uses as?
here, but I switched to as!
because itās a programmer error if the types donāt match. Note that thereās only one call-site, and the types do match.)
So we see whatās happening now. First attemptAction
tries to cast our action type to KnownSignedNumeric
, and if that succeeds then it calls performAction
, which uses our holistic knowledge that T
and Self
are the same type, in order to call through to the action.
Got all that?
Great!
Now weāre almost ready to write the actual action type we want. Unfortunately, if we write it the obvious way as NegateIfSigned<Wrapped>
, then when we implement our action
function the compiler will raise an error at the same-type constraint T == Wrapped
.
So we have to use a little indirection, which is where our third and most trivial protocol comes into play, along with its one empty conforming type:
protocol ProxyProtocol { associatedType Wrapped }
enum Proxy<Wrapped>: ProxyProtocol {}
We literally only use that to appease the compiler.
Part 3: The action itself
At last we are prepared to write our action type, and itās pretty simple as generic types go:
struct NegateIfSigned<P: ProxyProtocol>: AttemptIfSigned {
typealias Wrapped = P.Wrapped
typealias Result = Wrapped
var x: Wrapped
init<T>(_ x: T) where P == Proxy<T> {
self.x = x
}
func action<T: SignedNumeric>(_ t: T.Type) -> Result where T == Wrapped {
return -x
}
}
The action method is straightforward, it just implements the protocol requirement and does whatever calculations we want under the condition that Wrapped
conforms to SignedNumeric
.
The initializer is a little sneaky though. We could make it just take a parameter of type Wrapped
, but then thereās no way to infer the type of P
and weād always have to specify it. We donāt want to have to write NegateIfSigned<Proxy<Foo>>(x)
, after all.
ā¦of course, if the compiler would have let us use Wrapped
directly as the generic type parameter, then we wouldnāt need Proxy
at all, and type inference would work with a non-generic initializer. Oh well.
Part 4: Usage example
At this point weāre done, and it works. We can make a convenience method if we want:
extension Numeric {
func negatedIfSigned() -> Self {
NegateIfSigned(self).attemptAction() ?? self
}
}
That lets us take any Numeric
value, and if its type conforms to SignedNumeric
weāll get its negation:
(1 as Int).negatedIfSigned() // -1
(1 as UInt).negatedIfSigned() // 1
(1 as Float).negatedIfSigned() // -1.0
In other words, we can dynamically dispatch to SignedNumeric
.
⢠⢠ā¢
The strategy is broadly applicable:
- We could put anything we want inside
action
, within the constraints we put onT
. - We could put whatever constraints we want on T.
- We could make our top-level entry point do whatever we want if
attemptAction()
returnsnil
.
For example, if we constrain T
to BidirectionalCollection
instead of (or in addition to!) SignedNumeric
, then we can write a double-ended algorithm in action
. And we can make our entry point on Collection
use a slower single-ended fallback algorithm if the attemptAction()
call returns nil.
We can also compose actions. We could make one that dynamically dispatches to BidirectionalCollection
, and another that dynamically dispatches to SignedNumeric
, and we can make use of the latter within our action
for the former.
And of course, we can make as many different action types as we want with the same constraints. As in, we can write as many dynamically-dispatched BidirectionalCollection
algorithms as we wish.
⢠⢠ā¢
Part 5: Trampolines
That last point brings us to the ātrampolineā that I removed.
In our SignedNumeric
example, we checked the constraints by using a conditional conformance on our action type. But if we have many action types with the same constraints, do they all need their own conditional conformances?
Heck no!
We can make an empty helper type whose only purpose is to check a specific set of constraints:
enum SignedMarker<A: AttemptIfSigned> {}
extension SignedMarker: KnownSignedNumeric where A.Wrapped: SignedNumeric {
static func performAction<T: AttemptIfSigned>(_ t: T) -> T.Result {
(t as! A).action(A.Wrapped.self) as! T.Result
}
}
This will let us remove the conditional extension on our action type, just by changing Self.self
to SignedMarker<Self>.self
in the attemptAction()
method.
However, I like to go a small step further and put the constraint check on the marker type as well:
extension SignedMarker {
static func attempt(_ a: A) -> A.Result? {
(self as? KnownSignedNumeric.Type)?.performAction(a)
}
}
That lets us simplify the implementation of attemptAction()
, which after all āshouldnātā need to know the details of how the conformance is checked:
extension AttemptIfSigned {
func attemptAction() -> Result? {
SignedMarker.attempt(self)
}
}
Essentially, the trampoline (what Iāve called SignedMarker
) makes it easier to implement action types, because they only need the main declaration now, not the conditional conformance.
⢠⢠ā¢
So thatās the, uh, āquickā overview of how it works.
I will note that Mattās implementation actually has one even higher level, where it starts from Any
. That becomes important when the action being implemented takes multiple inputs of the same type but the call-site doesnāt have that information.
On the other hand, if your call-site will be generic and can thus guarantee the inputs are all of the same type T
(whatever it may be), and you just need to check for certain constraints, then it isnāt necessary to start from Any
.
Is that a compiler bug?
Thanks for your explanation, Nevin! I'm looking forward to digging into it, but I have another dissertation to read and respond to firstā¦