Associated Types Considered Weird

In my first post on Swift I expressed mild bewilderment at Apple’s decision to make protocols generic not by giving them generic type arguments, like C# does, but via what they call “associated types”. To reiterate the example, the Sequence protocol in Swift is defined as

protocol Sequence {
    typealias GeneratorType : Generator
    func generate() -> GeneratorType
}

whereas if Swift had generic type arguments in protocols (as it does in classes), the definition would look more like

protocol Sequence<T> {
    func generate() -> Generator<T>
}

When playing around with a set implementation that Alexis Gallagher posted, I came across a problem with associated types: it exposes more type information than the user of a class needs, and worse, more than the user of a class should have.

Here’s how Alexis implemented the generate method on his set type:

func generate() -> SetGeneratorType<KeyType> {
    let dictGenerator = self.dictionaryOfItems.generate()
    return SetGeneratorType<KeyType>(dictGenerator)
}

The type that generate is actually required to return (to adhere to the Sequence interface) is Generator. It’s not possible, however, (as far as I can tell) to declare generate as such:

func generate() -> Generator

The reason being that Generator here is under-specified—it must be a Generator whose associated type Element is KeyType, but that can’t be specified. If Swift had generic type arguments for protocols, it would simply be Generator<KeyType>.

The problem here is that the set type needs to publicly expose an implementation detail, namely the concrete type by which it implements its Generator. If that implementation detail changes, the method’s type changes, and code might break.

This problem is exacerbated by the fact that users of the generator might have to depend on its type. As an example, look at my simplification of Alexis’ code:

typealias GeneratorType = MapSequenceGenerator<Dictionary<KeyType,
                                                          Bool>.GeneratorType,
                                               KeyType>

func generate() -> GeneratorType {
    return dictionaryOfItems.keys.generate()
}

The body of the function explains the weird GeneratorType: The dictionary has a keys property that is exactly what I need—a sequence of all the elements in the set. The type that I’m returning now is the generator type of that sequence, instead of my own, and I must specify the concrete return type. The only way to get the concrete type, however, is to look up the type that keys returns, which means that I now depend on an implementation detail of Dictionary, and, making matters worse, I’m surfacing it to my users.

For comparison, let’s look at how this would work it Swift had generic type arguments for protocols. Sequence and Generator would be defined as

protocol Sequence<T> {
    func generate() -> Generator<T>
}

protocol Generator<T> {
    func next() -> T?
}

Dictionary’s keys property would be

var keys: Sequence<KeyType> { get }

And this would be our set’s generate method:

func generate() -> Generator<KeyType> {
    return dictionaryOfItems.keys.generate()
}

No leaked implementation details and no unneeded dependencies.

9 thoughts on “Associated Types Considered Weird

  1. How dare you criticize my work? Just kidding. This is awesome! Thanks for posting it. I’m not experienced in thinking about how generics creates unwanted dependencies between types, or how to manage type definitions for good modularity, so it’s very helpful to hear your thinking.

    I’m surprised that Swift does not provide a low level Generator type that is basic enough that a Set implementation can offer that to its users, without leaking information about its own implementation. I think we must be missing something.

    Also, is it possible to prevent this leak of implementation details by using a type alias? Maybe the Set implementation knows “internally” what generator type its using and defines it internally, but it only exposes a type alias for that, and so the users of Set only see the alias without ever “knowing” what the underlying type is. AFAIK, the only leakage now with my custom generator type is that it you can see its initializer, so there you can see its dependency on the Dictionary type. This is ringing some bells in my head connected with ML’s module system, but it’s been a while.

    • There are two issue here: The leakage on the one hand, and the dependency on the other. I can see how the dependency could be avoided if Dictionary had a typealias for the generator of its “keys” property, but it hasn’t, and I don’t think it can be extended to have one. If it had, we could get the proper type without depending on what it actually is. The leakage would still be there, but I don’t consider that a big issue.

  2. This puzzled me as well: http://stackoverflow.com/q/24137062/458193

    Is there any discussion where we can read why Apple engineers decided to go with associated types instead of generics for generators and sequences? It’s not like they don’t know C# or F#, so I presume there should be a good reason.

  3. I thought something like this might work:

    func generate() -> G {
    return dictionaryOfItems.keys.generate()
    }

    But nope. It fails with “‘MapSequenceGenerator’ is not convertible to ‘G’ return dictionaryOfItems.keys.generate()”. The generator can be assigned to a var:Generator as shown below, but trying to return the variable doesn’t seem to work regardless of the function signature.

    var gen: Generator = dictionaryOfItems.keys.generate()

    It’s too bad that, at least as things stand, Swift really seems to downplay the importance of interfaces/protocols.

  4. Trying again – parameters are hidden above:

    fund generate<G: Generator where G.Element == KeyType>() -> G {
    return dictionaryOfItems.keys.generate()
    }

  5. There are existing well-known arguments for the approach Swift is using [1]; however, those arguments require validity of the code John Vasileff is writing [2].

    [1] From Apple’s Joe Groff on the thread mentioned above (https://devforums.apple.com/message/983492#983492): “Associated types also scale much better to represent more intricate relationships among types than parameterized interfaces can. A Container in Swift has several interesting associated types—not only its Element type, but its IndexType and GeneratorType. Using associated types allows for all of these type relationships to be preserved in generic code, while not bloating the interface of code that only cares about one or two of them. To get the same level of expressivity in a parameterized interfaces system, the interface has to be parameterized by every associated type, so you’d end up with Container.”

    [2] Somebody with more experience is saying it: https://twitter.com/jonsterling/status/476868714789224449

  6. I feel like the solution here is to have something like:

    typealias GeneratorType: Generator = …
    where GeneratorType.Element == T

    By specifying it with this form, the public interface of your type would only specify that GeneratorType implements Generator and has an Element type of T. Whatever you put in the … is not part of the public interface of your type. You’d then return GeneratorType from generate.

    The advantage this would have over Generator is that you still return a concrete type from generate rather than having to wrap it in a value that can hold any Generator type that happens to generate Ts, permitting certain optimizations. Also, it fits better with the use case where you have a function with a `(g: G) -> G.Element`-like signature, since you’re actually able to pass it the concrete generator as it’s expecting rather than a wrapped type.

    It would be useful to be able to create a protocol as well, for use cases such as storing in a heterogeneous array, but I think the primary intended use of protocols is as constraints, and they should be used that way wherever possible.

    • Those are supposed to be `<G: Generator>(g: g) -> G.Element` and `protocol<Generator where Element==T>`.

Comments are closed.