Protocol Witness Matching Roadmap

Evolution Discussion
, ,
1

Hello Swift community,

Back in 2020, I started a thread Protocol Witness Matching Mini-Manifesto to discuss the different kinds of witness matching ideas that the community has proposed, some design principles and which of those ideas we could potentially include in the language in the future.

It kicked off a really interesting (although limited) discussion, but it's been a long time since that thread was created, and I am really keen on getting the document into a state where it is comprehensive enough that it can be officially merged to the Swift repo.

So, I am looking for additional feedback and ideas from community members that we could incorporate into the roadmap - it could be new or existing ideas (for example: formalizing @_implements) for witness matching, feedback on the document structure or anything else that you think is useful.

Below is the current state of the roadmap, but I will be revising it based on the discussion here.

Thank you!

Protocol Witness Matching Roadmap

Author: Suyash Srijan
Last updated: April 24, 2020

Jargon

Before we dive into the document, let's clarify some jargon:

  • A protocol requirement (or just requirement) is a declaration inside a protocol that all conforming types must satisfy.
  • A protocol witness (or just witness) is a value or a type that satisfies a protocol requirement.

For example:

protocol P {
  func foo() // This is a protocol requirement
}

struct S: P {
  func foo() { // This is a protocol witness
    ...
  }
}

Introduction

In Swift (at the time of this writing), protocol witnesses have to pretty much match exactly with a protocol requirement. For example:

protocol P {
  func foo()
}

struct S: P {
  func foo() { ... }
}

protocol P {
  func getView() -> UIView
}

struct S: P {
  func getView() -> UIView { ... }
}

A few specific differences are allowed:

  1. A non-throwing function can witness a throwing function requirement:
protocol P {
  func foo() throws
}

struct S: P {
  // Even though 'foo' here is not marked 'throws', it is
  // still able to satisfy the protocol requirement. The
  // caller has to handle the possibility that it might 
  // throw, but the witness is ofcourse free to throw or 
  // not to, depending on whether it makes sense in the
  // implementation.
  func foo() { ... }
}
  1. A non-failable initializer can witness a failable initializer requirement:
protocol P {
  init?()
}

struct S: P {
  // Similarly, the initializer here is free to return
  // a newly created value or just return 'nil' instead.
  init() {}
}
  1. A non-escaping closure can witness one that is marked @escaping:
protocol P {
  func foo(completion: @escaping() -> ()) 
}

struct S: P {
  // Similar to above, you can use a non-escaping closure here
  // if you want.
  func foo(completion: () -> ()) { ... }
}
  1. A non-generic function requirement can be witnessed by a generic one:
struct Some {}

protocol P {
  func foo(arg: Some)
}

struct S: P {
  // This is okay, since 'foo' can accept any T, including 'Some'.
  // If T was constrained in a way that it couldn't accept 'Some',
  // then this (obviously) won't be a valid witness.
  func foo<T>(arg: T) {}
}

However, almost any other kind of mismatch is forbidden. For example:

protocol P {
  func getView() -> UIView
}

struct S: P {
  func getView() -> MyCustomUIViewSubclass { ... } // Not allowed
}

protocol P {
  init()
}

struct S: P {
  init(arg: Int = 0) { ... } // Not allowed
}

Many people have argued that the existing model is too restrictive and that more forms of mismatching should be allowed. It's also been suggested that the existing model feels inconsistent with other parts of the language; for example, the code example above where the witness's return type is a subclass of the requirement's return type is allowed with class method overrides. In order to figure out how respond to these statements, we first have to address a very basic question: what should the model be for how we expect witnesses to match with requirements?

This manifesto starts by listing some possible changes we could make that would allow more mismatches. It then sets out some design principles and describes some of the constraints on how the language can reasonably behave. Finally, it proposes a basic model for how witness matching should work in the language. The ultimate goal of this document is to provide a foundation for discussing witness matching in Swift and to spur a series of evolution proposals to bring the language into alignment with its proposed design.

Likely

These are mismatches that aren't unreasonable to be allowed. Allowing this is mostly a matter of doing the implementation work and does not require any changes to the current syntax.

These forms of mismatching has also been requested from time to time and can help improve the expressivity of the language, without fundamentally changing it.

Desugaring

We can enable certain forms of "desugaring", such as allowing enum cases to satisfy static requirements:

Note: This has now been implemented in Swift 5.3. See SE-0280 for more details.

For example:

protocol P {
  static var foo: Self { get }
  static func bar(_ value: String) -> Self
}

enum E: P {
  case foo
  case bar(_ value: String)
}

let e: some E = E.foo

Enum cases already behave like static properties/functions in the language, both syntactically and semantically, so it's not unreasonable to think of a case as "sugar" for a static var or static func.

Default arguments

We can allow functions with default arguments to witness function requirements:

protocol P {
  func bar(arg: Int)
}

struct S: P {
  func bar(arg: Int, anotherArg: Bool = true) { ... }
}

As a special case, we can also allow a function with all default arguments to witness a function requirement with no arguments:

protocol P {
  init()
}

struct S: P {
  init(arg1: Int = 0, arg2: Bool = false) { ... }
}

This seems reasonable, because the protocol really just requires the ability to call init() on the conforming type, which you can in this case since all arguments have default values.

Related bugs:

  • None

Subtyping

We can allow protocol witnesses to be covariant (i.e. have subtypes of the requirement):

protocol P {
  func getView() -> UIView
}

struct S: P {
  func getView() -> MySubclassOfUIView { ... }
}

We already allow this in classes, so it probably makes sense for protocols witnesses to follow the same rules that exist for classes, for example, optional subtyping:

class A {
  func bar() -> Int? { ... }
}

class B: A {
  override func bar() -> Int { ... }
}

As we loosen the rules around subtyping and other kinds of matching, it is possible that associated type inference could degrade, so it is important to keep that in mind when working on this feature. There have been some ideas around how to improve it though, such as ones mentioned in this post.

Related bugs:

Old PR with possible implementation: https://github.com/apple/swift/pull/8718

Maybe/Unlikely

These are mismatches where either it's not clear whether it belongs to the language, whether it provides any concrete benefits, or it just complicates the existing design and/or introduces other implementation/runtime complexity.

Properties with function type

We could allow a function to match a property protocol requirement with a function type. For example:

protocol P {
  var bar: () -> Int
}

struct S: P {
  func bar() -> Int { ... }
}

or vice versa - letting a function requirement be witnessed by a property with function type:

protocol P {
  func bar() -> Int
}

struct S: P {
  var bar: () -> Int { ... }
}

Syntactic matching

We could allow anything that meets the syntactic needs of the requirement to witness that requirement. For example:

protocol P {
  static func bar(_ instance: Self) -> (Int) -> Bool
}

struct S: P {
  func bar(_ arg: Int) -> Bool { ... }
}

We could go to the extreme and allow other kinds of matching, such as allowing @dynamicMemberLookup to satisfy arbitrary protocol requirements.

Design Principles

The basic design principle is that matching shouldn't be entirely based on how the requirement is written (or spelled), but rather it should be based on what the protocol requirement semantically requires. We probably do not want to take this principle to its extreme though and instead use it to provide a balance between language expressivity and complexity.

Here's a really simple example (which is allowed today):

protocol P {
  func foo(_ arg1: Int)
}

struct S: P {
  func foo(_ arg2: Int) { ... }
}

Here, the requirement is that a caller should be able to invoke a method T.foo (where T is a concrete type conforming to P) which takes a single argument of type Int which can be passed without the need to specify an argument name. One can argue that the parameter label should match too, however the name of that label is irrelevant because it does not change the semantics of the requirement, which is that "I should be able to call foo without an argument name".

However, this shouldn't be allowed (and isn't currently allowed):

protocol P {
  func foo(arg1: Int)
}

struct S: P {
  func foo(arg2: Int) { ... }
}

because the semantics of the function now have a fundamental difference i.e. you can no longer invoke T.foo(arg1:). In this case, if we subsitute T with S, then S.foo(arg1: 123) is not a valid invocation.

Of course, we can allow people to work around it, by introducing a new language feature or re-using an existing one:

struct S: P {
  // Not currently allowed, but could be
  @_implements(P, foo(arg1:))
  func foo(arg2: Int) { ... }
}

However, that adds a lot of extra complexity for very little benefit; in fact, you now have to write more code to work around it, whereas it's just simpler to rename the label.

Another example is a "subtype"-like semantic behavior:

protocol P {
  func foo() throws
}

struct S: P {
  func foo() { ... }
}

Even though S.foo is not marked throws (and throws is not really a type), a type T -> U can be thought of as a "subtype" of T -> U throws. Here, the requirement is that "I can call a function foo with no arguments and it might throw". Now, whether S.foo throws or not depends on whether it makes sense to do so in the implementation. So, the semantics stay intact.

However, such "subtyping" should not be allowed in places where this is some sort of deeper guarantee. For example:

// Strawman annotation based on https://forums.swift.org/t/pitch-genericizing-over-annotations-like-throws
protocol P {
  func foo() alwaysthrows
}

struct S: P {
  func foo() throws { print("I didn't throw!") }
}

Here, alwaysthrows is a semantic guarantee; it says that the method will always throw when it is called. However, S.foo may or may not throw. So, T -> U throws is not a "subtype" of T -> U alwaysthrows.

A Basic Model

The basic model for witness matching would embrace the above design principles. Luckily, the current model already does that to some extent and by allowing the proposed changes we can align the model to be more in sync with what is reasonable to do.

In practice, this means:

  • Exact matches are allowed
  • Mismatches are allowed, as long as the semantic requirements are satisfied (for examples, a throws mismatch)
  • Everything else is disallowed
12 Likes
2

I think this would be really cool if we could support it (well actually, the reverse case - witnessing a function requirement using a closure - is what I think would be useful).

It's a niche case, but... why not? If we're talking about members that are semantically equivalent (rather than syntactically identical), I think this would make sense.

9 Likes
3

One thing I've been thinking about is that if we had a formalized version of @_implements then I think we could get most of the way towards the syntactic model for protocol witness matching without having a mess of complex implicit witness matching rules.

The idea would be that annotating some declaration with @implements(P, foo) would synthesize the P.foo witness stub with a body that (syntactically) forwards to the annotated member. So rules like subtyping, closure/function equivalence, and maybe even things like dynamic member witnesses or default argument allowances. Concretely:

protocol P {
  func foo(x: Int) -> String?
}

struct S: P {
  @implements(P, foo)
  var bar: (Int) -> String
}

would implicitly synthesize something like:

func _S_P_foo(x: Int) -> String? {
  self.bar(x)
}

and all the expected conversions fall out naturally from existing language rules.

2 Likes
4

I think the full generality of @_implements would have to be strongly motivated on its own though.

I agree with the general problem statement that there already are witness matching rules, which as they exist currently are not fully rationalized and are limiting: some of the complexity actually lies in the fact that some intuitive rules surrounding mismatches are supported and others are not, and the distinction isn’t teachable.

I don’t think that merely allowing us to dispense with the (difficult) task of rationalizing these rules and filling in the missing bits is a good reason per se to jump to @_implements. And for my part, even if @_implements were a formally specified feature, I wouldn’t consider it an answer to the question of why mismatches in throws are allowed for protocol witnesses but not mismatches in optionality, other than the case of failability for initializers.

Instead, I would agree with the premise of the roadmap that we do need to reckon with this directly, if we decide that this is an area worthy of tackling for the next language version.

5 Likes
5

Definitely agree here—we still ought to consider what we want the overarching principle of witness matching to be and how to get there. But I also think that the potential of formalizing @implements gives good reason to err on the more restrictive rules when considering such a principle.

The most restrictive version of such a principle is, of course, “exact signature matches only, everything else must use @implements,” and there’s a good amount of ground between that and the state of affairs today. IMO the process of rationalizing these rules reasonably results in us deciding to remove bits where we may have gone too far with implicit matching rather than just “filling in.” This would come with the usual concerns about source compatibility and what we’re willing to break, but there too @implements would give a clear migration path.

Anyway, I’m not opposed to a hypothetical more-inclusive rule that ties all our implicit witness matching allowances together nicely. But I’m also very interested in ways that we can ergonomically minimize our implicit matching surface by making it very easy to explicitly invoke witness matching (with the end goal still being explainability).

2 Likes
6

Not just that; the stricter these rules are, the more difficult it becomes to evolve protocols in a source-compatible way.

For example, I mentioned in a recent thread that I wanted a function returning a concrete type to be able to witness a requirement returning an existential. The idea was to write something like this:

protocol MyProto {
  #if swift(>=5.7)
    func doSomething() -> any Collection<UInt8>
  #else
    func doSomething() -> AnyCollection<UInt8>
  #endif
}

I've benchmarked algorithms using language-integrated existentials as being up to 80x faster than the same algorithm using the stdlib's versions, so I would really like to use them, but I still want this API to be available in some form to people building with older compilers.

The idea is that those pre-5.7 users could write conformances like this:

struct MyStruct: MyProto {
  func doSomething() -> AnyCollection<UInt8> { ... }
}

And that when they eventually upgrade to 5.7, it would still match as a witness to the same requirement. Yes, the result would be an stdlib "existential" wrapped in a language existential, which is suboptimal for performance, but it would at least be a source-compatible change.

Since witness matching is too strict to allow for this kind of evolution, I'm having to limit this entire API to Swift 5.7+ with no compatibility fallback. It's the only part of the library that is limited in this way.

So yeah - while I understand the desire to make everything very strict, it can be impractical. We should be mindful of the benefits of being more relaxed, as long as everything still obeys some kind of comprehensible principles.

4 Likes
7

I also second that this should be possible, especially after we finally resurrect and actually get 'compound names' in Swift.

9 Likes
8

Many ideas worthy of consideration here.

There are of course always hidden type-soundness pitfalls in ventures like this. I wonder: has anybody out there ever modeled Swift’s type system, or even just Swift’s protocol conformance rules, in Alloy or TLA+ or some such? That would be a wonderful way to test out the soundness of these proposals. Well beyond my expertise, I’m afraid…but I’ll bet somebody out there with the right skills could give us some surprising insights.

9

Very interesting initiative.

I feel the likely part mostly comes down to covariance between the witness and the requirement (not sure in which direction).

Wouldn’t alwaysthrows be expressible today as ˋthrows -> Never? In which case, the covariance rule would tell us the witness would need to be the same or just -> Never`.

2 Likes
10

I guess you mean: we can allow them to be covariant in their return types, and possibly contravariant in their argument types, right? That’s how subtyping seems to work.