120

I'm confused about the difference between the syntax used for associated types for protocols, on the one hand, and generic types on the other.

In Swift, for example, one can define a generic type using something like

struct Stack<T> { var items = [T]() mutating func push(item: T) { items.append(item) } mutating func pop() -> T { return items.removeLast() } } 

while one defines a protocol with associated types using something like

protocol Container { associatedtype T mutating func append(item: T) var count: Int { get } subscript(i: Int) -> T { get } } 

Why isn't the latter just:

protocol Container<T> { mutating func append(item: T) var count: Int { get } subscript(i: Int) -> T { get } } 

Is there some deep (or perhaps just obvious and lost on me) reason that the language hasn't adopted the latter syntax?

1
  • 8
    FWIW the 2nd approach will throw the following error: protocols do not allow generic parameters; use associated types instead. Understandably your question isn't about why the error is happening rather why the language hasn't took this approach? Commented Dec 3, 2018 at 19:34

3 Answers 3

68

This has been covered a few times on the devlist. The basic answer is that associated types are more flexible than type parameters. While you have a specific case here of one type parameter, it is quite possible to have several. For instance, Collections have an Element type, but also an Index type and a Generator type. If you specialized them entirely with type parameterization, you'd have to talk about things like Array<String, Int, Generator<String>> or the like. (This would allow me to create arrays that were subscripted by something other than Int, which could be considered a feature, but also adds a lot of complexity.)

It's possible to skip all that (Java does), but then you have fewer ways that you can constrain your types. Java in fact is pretty limited in how it can constrain types. You can't have an arbitrary indexing type on your collections in Java. Scala extends the Java type system with associated types just like Swift. Associated types have been incredibly powerful in Scala. They are also a regular source of confusion and hair-tearing.

Whether this extra power is worth it is a completely different question, and only time will tell. But associated types definitely are more powerful than simple type parameterization.

Sign up to request clarification or add additional context in comments.

19 Comments

Interesting. That makes sense as an argument for associated types as an additional (and more flexible) way of specializing, but why not allow type parameters for protocols for the same reason they are allowed for generic types: in simple cases they do the job?
Then you would also need to handle the interaction of protocols that included both type parameters and associated types. It's more complicated to implement a compiler for that (though Scala does as I recall, but then Scala implements many type features that Swift doesn't). I would not be shocked to see them add it at some point (just like I wouldn't be shocked to see them add default implementations or mixins or many other features). But Swift left out many things in its v1. They needed associated types for Sequence/Collection/etc. They didn't need type parameters.
They're different. Associated types are a relationship between two types, chosen by the implementation. Generics are chosen by the caller. So an Array always has an Int index. If we used generic indexes rather than associated types, you'd have to say Array<Element, Int> every time you used Array (to express the Int` Index), and it'd be incompatible with Array<Element, DictionaryIndex> (which would be legal), or else every Collection would have to use Int as its Index (which currently most don't).
@RobNapier Thank you for the explanation. I indeed was thinking about inheritance and locking in certain type parameters and leaving others free. But I missed the fact that collections are structs in Swift and inheritance is not an option. But what if Swift would allow generic type parameters for protocols (like in the original question)? Then we could have something like Array<Element>: SomeCollectionProto<Element, Int> instead of associated types in SomeCollectionProto. I still can't understand why this wouldn't eliminate the need of associated types.
Type-erasers are completely mechanical boxes around protocol. They are tedious to build by hand, but not difficult. In principle, the compiler should be able to invent such a box on the fly whenever it is needed. That feature is called "existential containers" and it's discussed somewhat non-stop within parts of the Swift team. It's hard because generics in Swift are very flexible, so inferring that you need a Collection<Element: Collection> where Element.Element: Collection<Comparable> (which isn't a complicated one; I just needed something that fit in a comment) has a lot of corner cases.
|
63

RobNapier's answer is (as usual) quite good, but just for an alternate perspective that might prove further enlightening...

On Associated Types

A protocol is an abstract set of requirements — a checklist that a concrete type must fulfill in order to say it conforms to the protocol. Traditionally one thinks of that checklist of being behaviors: methods or properties implemented by the concrete type. Associated types are a way of naming the things that are involved in such a checklist, and thereby expanding the definition while keeping it open-ended as to how a conforming type implements conformance.

When you see:

protocol SimpleSetType { associatedtype Element func insert(_ element: Element) func contains(_ element: Element) -> Bool // ... } 

What that means is that, for a type to claim conformance to SimpleSetType, not only must that type contain insert(_:) and contains(_:) functions, those two functions must take the same type of parameter as each other. But it doesn't matter what the type of that parameter is.

You can implement this protocol with a generic or non-generic type:

class BagOfBytes: SimpleSetType { func insert(_ byte: UInt8) { /*...*/ } func contains(_ byte: UInt8) -> Bool { /*...*/ } } struct SetOfEquatables<T: Equatable>: SimpleSetType { func insert(_ item: T) { /*...*/ } func contains(_ item: T) -> Bool { /*...*/ } } 

Notice that nowhere does BagOfBytes or SetOfEquatables define the connection between SimpleSetType.Element and the type used as the parameter for their two methods — the compiler automagically works out that those types are associated with the right methods, so they meet the protocol's requirement for an associated type.

On Generic Type Parameters

Where associated types expand your vocabulary for creating abstract checklists, generic type parameters restrict the implementation of a concrete type. When you have a generic class like this:

class ViewController<V: View> { var view: V } 

It doesn't say that there are lots of different ways to make a ViewController (as long as you have a view), it says a ViewController is a real, concrete thing, and it has a view. And furthermore, we don't know exactly what kind of view any given ViewController instance has, but we do know that it must be a View (either a subclass of the View class, or a type implementing the View protocol... we don't say).

Or to put it another way, writing a generic type or function is sort of a shortcut for writing actual code. Take this example:

func allEqual<T: Equatable>(a: T, b: T, c: T) { return a == b && b == c } 

This has the same effect as if you went through all the Equatable types and wrote:

func allEqual(a: Int, b: Int, c: Int) { return a == b && b == c } func allEqual(a: String, b: String, c: String) { return a == b && b == c } func allEqual(a: Samophlange, b: Samophlange, c: Samophlange) { return a == b && b == c } 

As you can see, we're creating code here, implementing new behavior — much unlike with protocol associated types where we're only describing the requirements for something else to fulfill.

TLDR

Associated types and generic type parameters are very different kinds of tools: associated types are a language of description, and generics are a language of implementation. They have very different purposes, even though their uses sometimes look similar (especially when it comes to subtle-at-first-glance differences like that between an abstract blueprint for collections of any element type, and an actual collection type that can still have any generic element). Because they're very different beasts, they have different syntax.

Further reading

The Swift team has a nice writeup on generics, protocols, and related features here.

5 Comments

Thanks for this. One question - you write "insert(-:) and contains(:-)". What do the parameters "-:" and ":-" imply? (And read underscore for minus sign, Stack Overflow gets confused when I write an underscore.)
A format like insert(_:) (use backticks for code and you can keep the underscores on SO) is the way Swift refers to functions by name/signature. The internal name of the first parameter (element, byte, etc in this post's examples) isn't part of the function's interface, so we use an underscore to say that there is a first, unlabeled parameter. Argument labels (e.g. the second and third in print(_:separator:terminator) are part of the interface, so they're included in the function "name". (And the reversed :_ in my original post was just a typo.)
(Also, I first posted this answer when Swift 2.x was current, so the syntax from the original version of the post resulted in parameters without argument labels. I've updated it to use Swift 3 syntax now.)
Thanks for updating your answer and for answering my question.
I absolutely don't get the argument about generic type parameters and associated types being different kind of tools. Both instruments make your type more generic when going from concrete types. It's basically the same thing. The only difference is in syntax and the way how you can constrain type parameters/associated type values.
5

To add to the already great answers, there's another big difference between generics and associated types: the direction of the type generic fulfilment.

In case of generic types, it's the client that dictates which type should be used for the generic, while in case of protocols with associated types that's totally in the control of the type itself. Which means that types that conform to associated types are in liberty to choose the associated type that suits them best, instead of being forced to work with some types they don't know about.

As others have said, the Collection protocol is a good example of why associated types are more fit in some cases. The protocol looks like this (note that I omitted some of the other associated types):

protocol Collection { associatedtype Element associatedtype Index ... } 

If the protocol would've been defined as Collection<Element, Index>, then this would've put a great burden on the type conforming to Collection, as it would've have to support any kind of indexing, many of them which don't even make sense (e.g. indexing by a UIApplication value).

So, choosing the associated types road for protocol generics it's also a matter of empowering the type that conforms to that protocol, since it's that type the one that dictates what happens with the generics. And yes, that might sound less flexible, but if you think about it all types that conform to Collection are generic types, however they only allow generics for the types that make sense (i.e. Element), while "hardcoding" the other associated types (e.g. Index) to types that make sense and are usable in their context.

3 Comments

you wrote about great burden and freedom to choose the associated type, but why wouldn't it be possible to do something like this "class MyCollection<Element> : Collection<Element, Int>"? MyCollection freely chose it's index type to be Int
@frangulyan they're called "associated types" for a reason :) Also what you wrote is semi-possible since the primary associated types landed into the language. Allowing the Index to be specified as part of the generic signature only when conforming to the protocol opens a new set of problems, and complicates even more the grammar of the language.
it works fine in kotlin :) but after playing around with chatgpt I realized that the biggest difference and advantage is being able to write "Collection.Index" as a type in various places. That's what you miss when you move it to the generic parameter. The rest is just syntax - you can have the word "associatedtype" written in capitals, or move the "Index" to angle brackets next to the protocol name, it doesn't matter.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.