Rename protocols that use Self or associated types to “constraints”, and declare them as such

Evolution Pitches
1

“They’re protocols, Jim, but not as we know it.” -Spock, on associatedtype

Proposal draft here.

There are two different types of protocols in Swift and they behave completely differently. Normal protocols are like any other type, use dynamic dispatch and allow for heterogenous mixtures of different implementations (similar to objects that inherit from the same base class). On the other hand, constraint protocols (distinguished only by having an associatedtype, or even more subtle, just using Self) use static dispatch, can never be used like a type, and can only be used to restrict which real types can be used for a generic function or new concrete type. This causes endless confusion:

LINKS

ios - Protocol can only be used as a generic constraint because it has Self or associatedType requirements - Stack Overflow

swift - What does "Protocol ... can only be used as a generic constraint because it has Self or associated type requirements" mean? - Stack Overflow

swift - Can you explain/solve these 'generic constraint' compiler errors? - Stack Overflow

ios - How to use associated type protocol as argument's type to a function? - Stack Overflow

swift - Protocol can only be used as a generic constraint - Stack Overflow

swift - Protocol 'BaseListPresenter' can only be used as a generic constraint because it has Self or associated type requirements - Stack Overflow

ios - Protocol can only be used as a generic constraint because it has Self or associated type requirements - Stack Overflow

swift - No associated type, and yet: Protocol can only be used as a generic constraint because it has Self or associated type requirements - Stack Overflow

swift - Protocol <NAME> can only be used as a generic constraint because it has Self or associated type requirements - Stack Overflow

generics - When to use Type Constraints in Swift? - Stack Overflow

ios - Protocol 'someProtocol' can only be used as generic constraint because it has Self or associated type requirements - Stack Overflow

swift - Why can we not cast to protocol types with associated types but achieve the same effect using generics? - Stack Overflow

swift - Getting around "Protocol X can only be used as a generic constraint" - Stack Overflow

swift - Using associatedtype in a delegate protocol for a generic type - Stack Overflow

swift - Can you explain/solve these 'generic constraint' compiler errors? - Stack Overflow

ios - How to use generic protocol as a variable type - Stack Overflow

Almost all of these links are caused by people either creating a protocol that inherits from Equitable or Hashable without realizing that it dramatically limits how they can use it, trying to use Equitable or Hashable as a type, or adding associated types to their protocol without understanding how they work (almost certainly because the compiler told them to, when they really just wanted a higher-kinded protocol).

Their confusion is understandable; indeed, as one poster points out:

Swift documentation says that protocols are treated like any other types, but looking at some examples, I see that 'type constraint' construct is being used instead of protocol.

And they’re right! The Swift Programming Language Guide version 4.1, section Protocols, heading Protocols as Types, contains a plain lie:

Protocols don’t actually implement any functionality themselves. Nonetheless, any protocol you create will become a fully-fledged type for use in your code.

I propose we change the above lie to a truth by renaming all protocols that cannot be used as types to “constraints”, and have them declared as such:

constraint Equatable {
    static func ==(lhs: Self, rhs: Self) -> Bool
}

All of their semantics stay exactly the same. Obviously anything that inherits from a constraint is also a constraint.

This would make it immediately obvious that constraints are a different animal than protocols, dramatically reducing confusion. (Protocols, of course, can be used as constraints, but that’s hardly a reason to call them the same thing; so can any class!) It would also improve two error messages:

X can only be used as a generic constraint because it has Self or associated type requirements

could be changed to:

Constraints such as X can only be used to narrow generic type variables

and we can marginally improve the terrible message:

Protocols do not allow generic parameters; use associated types instead

to:

Protocols do not allow generic parameters; you may be able to create a constraint with an associated type instead

(“May”, here, because there are some things Swift cannot do until if/when higher kinded types are added to the language. Constraints are usually a sufficient, if kludgy, alternative.)

The horrible confusion of constraint protocols has been with Swift from the very beginning. Swift 2.2 helped replacing “typealias” with “associatedtype,” but it doesn’t solve the fundamental problem that the keyword “protocol” is the declaration for two very different constructs. This change probably still won’t totally alleviate confusion, but it will go a long way towards helping people understand the distinction. Swift is the world’s first Protocol Oriented Programming language; it’s egregious for “protocol” to mean two different things.

5 Likes
2

Definitely agree that they way protocols currently are leaves a lot to be desired. However I think that making protocols generic, like classes and structs, giving them generalized existentials, or preferably both is a better solution than enshrining the current behaviour.

8 Likes
3

I agree the current situation is confusing, but I must nitpick this part. Even when using a protocol as a generic constraint, you still have dynamic dispatch:

func g<T : P>(_ t: T) {
  t.someMethod()
}

The compiler does not know which implementation of someMethod() will be called until runtime, therefore it must use dynamic dispatch.

This isn't quite true. Right now, this doesn't work, but it totally should:

protocol P {
  associatedtype T
}

protocol Q : P where T == Int {}

let q: Q = ... // this should work!

I think it is still useful to use a protocol without associated types as a generic constraint. For example, if you have a protocol for shapes and a function that takes a homogeneous array of shapes, you want to be able to write func foo<T : Shape>(_: [T]).

2 Likes
4

I would definitely support the addition of higher-kinded protocols, but I think there will still be a need to constrast them with constraint protocols. Equatable is anti-heterogenous. It would be very confusing to have two values of type Equatable that cannot be compared.

Hmm, maybe I'm confused. Surely which someMethod() is determined by whatever T is used at the call site?

Yes, it totally should! Though I would call that Q satisfying P, not Q inheriting from P.

Sure, there's no reason to remove that functionality, for either protocols or classes! All protocols are constraints, but not all constraints are protocols.

By letting protocols satisfy a constraint, I meant something like your example above:

constraint C {
    associatedtype T
    func flerg(_: T) -> T
}

protocol P {
    func flerg(_: Int) -> Int
}

extension P: C {
    associatedtype T = Int
}
5

For both generalized existential and generic protocols you would get a type error from the compiler.

6

Sure, but since we support separate compilation of generic functions, the compiler still emits a dynamic dispatch inside the body of g().

7

This can and should be expressed the way @Slava_Pestov mentioned: using a same-type constraint. Protocol extensions are not allowed to have inheritance clauses or requirements – they are quite different from protocols themselves.

8

You could compare them -- as long as our eventual generalized existential model could express performing an as? cast of the first value to the Self type of the second. If the cast succeeds, you've got two values with the same concrete type.

1 Like
9

What you're describing here would be an interesting feature in its own right, but it would be quite difficult to implement. If you could declare that all types conforming to P also conform to C, it vastly complicates subtype relation calculations at compile time, or dynamic casting at runtime. Right now, checking if a type conforms to a protocol is relatively straightforward. If protocols could conform to other protocols, we would have to search for all possible "paths" between the concrete type and the protocol.

10

That would be cool! But it would still be confusing to have

let x: Equatable = ...
let y: Equatable = ...
x == y // compiler error

I think that would be absolutely baffling to someone not yet up to speed on how existential types work. Is there a legitimate use case for generalized existentials (that isn't better filled by higher-kinded protocols)?

That does sound complicated. It's a distraction anyway so I'll edit the mention out of my post.

12

I think generic protocols would be better in most circumstances, e.g.:

let x: Equatable<Int> = ...
let y: Equatable<Double> = ...
x == y // compiler error

I find the above clearer.

There are some niche cases were existentials are better though. In the Java library you will find various Collectors. Collectors are reduce on steroids; in particular they can be parallel and use an intermediate container, the type of which you don't care about (an ideal candidate for existentials). EG in Java you have a counting collector, that counts the number of items (quickly), that has type Collector<T, ?, Int>, the ? is the intermediate type that you don't care about. If in Java they had both generic protocols and existentials then it could have type Collector<T, Int>.

As I said the usage is niche and the Java folks decided not worth it, however Scala has both, but as a counter example Kotlin has followed Java.

PS have Swiftified some of the Java.

13

What about collectors make them unable to be represented by a function with the type (T) -> Int?

14

Part of the "generalized existentials" work should include providing a mechanism for protocols with contravariant Self requirements to generalize their operations for the existential case. Equatable could implement its own == requirement by considering two values of different types to be unequal, or otherwise compare two values of the same dynamic type using their == operation, for instance.

2 Likes
15

I think you're confusing two concepts. A higher-kinded protocol would be one in which Self is generic, allowing you to express protocol Functor where Self<T> { func map<U>(_: (T) -> U) -> Self<U> } and other things of the sort. Protocols/interfaces with generic parameters are not higher-kinded, but rather an alternative syntax for expressing associated types. Being able to say Sequence<T> instead of Sequence where Element == T might be more convenient syntax but expresses the same idea.

7 Likes
16

It can also be said that current protocols are only existentially quantified types, when "higher-kinded" protocols would be universally quantified types (protocol P<T>) that can as well be existentially quantified (Self, associatedtype) over disjoint sets of generic parameters.

17

Actually what I'm doing is drawing a distinction between higher-kinded protocols and higher-kinded constraints, of which I think Swift should eventually have both. A higher-kinded protocol works like this:

protocol Stack<T> { // Stack is higher-kinded in that any type that adheres to it must be generic
    mutating func push(_:T)
    mutating func pop() -> T?
}

enum LinkedList<T> : Stack<T> { // okay because LinkedList is generic for T
    case cons(T, LinkedList<T>)
    case empty

    mutating func push(t: T) {
        let rest = self
        self = .cons(t,  rest)
    }

    mutating func pop() -> T? {
        switch self {
        case .cons(let first, let rest):
           self = rest
           return first
        case .empty:
           return nil
        }
    }
}

extension Array<T> : Stack<T> {  // okay because Array is generic for T {
    mutating func push(t: T) {
        self.insert(t, at: 0)
    }

    mutating func pop() -> T{
        return self.remove(at: 0)
    }
}

var array: Stack<Int> = [1, 2, 3]
var list: Stack<Int> = .cons(4, .cons(5, .cons(6, .empty)))

array.push(list.pop())
array // [4, 1, 2, 3]
list  // .cons(5, .cons(6, .empty))

list = array // okay because both have type Stack<Int>
list  // [4, 1, 2, 3]

I think this is usually it what people are going for when they try to add a generic parameter to a protocol and are told to use an associated type. This is somewhat ambitious to add, however, and it is not what I am proposing at present. All I am proposing is that we make explicit an existing distinction between normal protocols and constraints.

18

That's different syntax for an associated type. There's no fundamental reason the conforming entity has to be generic for it to conform to Stack; every individual type Array<Int>, Array<String>, etc. can conform to Stack with a different T binding, but so could a type that only supports pushing and popping Floats conform with T == Float. This is exactly what associated types express, just with a different syntax.

5 Likes
19

Not quite. There's no way to do list = array with associated type protocols, because list and array are forced to have different concrete types. With generic protocols, you can have:

let arrayOfStacks: [Stack<Int>]

Where each element in the array is a different concrete type, which you cannot do with associated type.

Now, it is equivalent to generalized existentials, but I'd still argue it's way better syntax, considering all of the confusion created by people trying to create generic protocols.

1 Like
20

Right, that's the "generalized existentials" feature. Instead of thinking of protocols with and without associated types as different things, I would say that all protocols in Swift are fundamentally what you're calling constraints, and the support for existential types is something that's currently restricted to protocols without associated types, but which is planned to be generalized. Stack<Int> is definitely nicer syntax for common cases, and we could add support for that syntax by treating protocol Stack<Element> as sugar for protocol Stack { associatedtype Element }, perhaps, but that doesn't require fundamentally changing the model.

7 Likes
21

I'm not actually proposing this generic protocol model, and I certainly wouldn't propose ditching associatedtype. All I am proposing is that there is a very meaningful distinction between protocols that can and cannot be used as ordinary types, and the fact that this distinction is not explicit is the source of enormous confusion.

You're right that associatedtype + generalized existentials would allow for a consistent model of protocols-as-constraints, but I think this would only be even more confusing for people learning the language. Why can I do x.toggle() when x: Toggleable but not e1 == e2 when e1: Equatable and e2: Equatable? Looking at the definition of Equatable will baffle me. It looks like we have defeated the entire purpose of protocols. It's especially bad when a protocol just inherits from one that uses associatedtype or Self, so the indication that it is a constraint is not even in its own body.