Test if a type conforms to a non-existential protocol

Evolution Pitches
40

@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 on T.
  • We could put whatever constraints we want on T.
  • We could make our top-level entry point do whatever we want if attemptAction() returns nil.

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.

8 Likes