Hi, everybody, I'm Ben. I work on the Swift standard library. And together with my colleague Doug, from the compiler team. We're going to talk to you about Swift generics. So the recent releases of Swift have added some important new features. Including conditional conformance and recursive protocol constraints. And, in fact, with every release of Swift, we've been refining the generic system, making it more expressive. And we feel that the 4.2 release marks an important point. It's the point where we can finally fully implement a number of designs that have always been envisioned for the standard library. Something that's critical for us in achieving our goal of API stability for Swift.

So, we've given a lot of talks about generics in the past, but we haven't taken a step back. And talked about generics as a whole for a while. So today, we're going to take you through a few different features of the generics system. Both new and old, to help understand how they fit together. I'm going to briefly recap the motivation for generics.

We're going to talk about designing protocols, given a number of concrete types, using examples taken from the standard library. We're going to review protocol inheritance, and talk about the new feature of conditional conformance. And how it interacts with protocol inheritance. And finally, we're going to wrap up with a discussion of classes and generics.

So why are generics such an important part of Swift? Well one way of seeing their impact is by designing a simple collection, like type. We'll call it buffer, and it's going to be similar to the standard library's array type. Now, the simplest possible API for the reading part of a buffer might include a count of the number of elements. And a way to fetch each element to the given position in the index.

But, what do we make of that return type? Now, if we didn't have generics, we'd have to make it some kind of type that could represent anything that we'd want to put inside the buffer. You can call that type ID or object or void star. In Swift we call it Any, which is a type that can stand in for any different kind of type in Swift.

So if you wanted to handle anything in the buffer, you could have subscript return an Any. But, of course, you probably know that that leads to a really unpleasant user experience. At some point, you've got to get out that type from inside the box. In order to actually use it.

And this isn't just annoying, it's also error-prone. What if somewhere in your code, maybe by accident, you put an integer into what was supposed to be a buffer of strings? But it's not just about ease of use. We also want to solve some problems relating to how these values are represented in memory.

Now, the ideal representation for a buffer of strings, would be a contiguous block of memory. With every element held in line next to each other. But with an untyped approach, this doesn't work out quite so well. Because the buffer doesn't know in advance what kind of type it's going to contain. And so it has to use a type like Any that can account for any of the possibilities. And, there's a lot of overhead in tracking, boxing, and unboxing the types in that Any.

Here, I might have just wanted a buffer of integers, but I have no way of expressing that to the compiler. And so, I'm paying for flexibility, even though I'm not interested in it. What's more, because Any has to account for any different kind of type. Including types that are too large to fit inside its own internal storage, it has to sometimes use indirection.

It has to hold a pointer to the values, and that value could be located all over memory. And so we really want to solve these problems, not just for ease of use and correctness, but also for performance reasons. And, we do it using a technique called parametric polymorphism. Which is just another term for what we in Swift refer to as generics.

With a generic approach, we put more information on the buffer, to represent the type that the buffer is going to contain. We'll call that type Element. Element is a generic parameter of the type, hence the term of parametric polymorphism. You can think of it kind of like a compile-time argument that tells the buffer what it's going to contain. Now it has a way of referring to that element type. It can use it wherever it was previously using Any.

And, that means that there's no need to do conversions when you're getting a type out of the buffer. And if you make an accidental assignment of the wrong kind of type, or some issue similar to that. The compiler will catch you. Now, now there's no such type as buffer without an associated element type. If you try to declare a type like that, you'll get a compilation error.

You might find that slightly surprising. Because sometimes you'll see that you can declare types like buffer without any element type. But, that's just because the compiler is able to infer what the element type ought to be from the context. In this case, from the literals on the right-hand side here. The element is still there, it's just implicit.

This knowledge of exactly what type a buff-- a type like buffer contains is carried all the way through both compile and runtime. And this means that we can achieve our goal of holding all of the elements in a contiguous block of memory, with no overhead. Even if those types are arbitrarily large.

And because the compiler has direct knowledge at all times of exactly what element type the buffer contains. It has optimization opportunities available to it that it wouldn't otherwise have. So, in the case here, where I've declared a buffer of integers. A loop like this ought to be compiled down to just a handful of very efficient CPU instructions.

Now, if you were writing a loop like this, on a regular basis. To sum up a buffer of integers, it might make sense to extract it out into a method. An extension on buffer that's more unit-testable, and more readable when you actually call it. But, you probably know that if you've written code like this, you'll get a compilation issue, because not all element types can be summed up like this.

We need to tell the compiler more about the capabilities the element needs to have, in order to make this method available on a buffer. Now, the easiest way to do that is by constraining the element type to be a specific type like the Int from our original loop.

If you take this easy approach to get up and running with your extension, it's easy to generalize it later. When you find that you need to do something different. Like sum up a buffer of doubles, or floats. Just look at the type that you've constrained to. Look at the protocols it conforms to.

And follow them up until you get the most general protocol that gives you everything that you need to do your work. In this case, the numeric protocol, which gives us the two things we're relying on here. The ability to create a new element with a value of zero, and the ability to add elements to it. Which come as part of the numeric protocol.

Now, let's talk about that process of factoring out protocols from various types. So we've been talking about this buffer type, and we can make it generic across different elements. But what about writing generic code that's generic in a different direction? Or writing code that works on any different kind of collection? Such as an array that's very similar to our buffer type.

But also more varied types, like a dictionary that's a collection of key value pairs. Or maybe types that aren't generic or are the different element types, like data or string that returns specific element types. We want to create a protocol that captures all of their common capabilities. We're going to create a, a cut down, simplified version of the standard library's own collection protocol.

So notice that we considered a varied number of concrete types first. And now, we're thinking about a kind of protocol that could join them all together. And, it's important to think of things as this way around. To start with some concrete types, and then try and unify them with a protocol.

What do those types have in common? What don't they have in common? When you're designing a protocol like this, you can think of it kind of like a contract negotiation. There's a natural push and pull here, between conforming types on the one hand. That want as much flexibility as possible in fulfilling that contract.

And users of the protocol, that want a really nice, tight, simple protocol in order to do their extensions. That's why it's really important to have both a variety of different possible conforming types. And a number of different use cases in mind when you're designing your protocol. Because it's a balancing act.

So, let's start to flesh out the collection protocol. So, first we need to represent the element type. Now, in protocols, we use an associated type for that. Each conforming type needs to set element to be something appropriate. In the case of buffer, or array, as of Swift 4.2, this happens automatically. Because we also named their generic parameters to be element as well. This is a nice side benefit of giving your generic arguments meaningful names that follow common conventions like the word element.

Rather than giving them something arbitrary like T that you'd have to separately state was the element type. For other data types, you might need to do something slightly more specific. For example, a dictionary needs to set the element type to be the pair of its key and value type.

Next, let's talk about adding the subscript operation. Now, if we were talking about just a protocol for types like array, we might be tempted to have subscripts take an Int as its argument. But making subscript take an Int would imply a very strong contract. Every conforming type would have to supply the ability to fetch an element's given position that was represented by an integer. And, that works great for types like array. It's also definitely easy for users of the protocol to understand.

But is it flexible enough for a slightly more complicated type, like a dictionary? Now no matter how you model it, a dictionary's probably going to be backed by some fairly complicated internal data structure. That has specific logic for moving from one element to the next. For example, it could be backed by an internal buffer of some kind, and it could use an index type that stored an offset into that buffer. That it could then take as the argument to subscript in order to fetch an element to the position, using that offset.

But it would be critical that the dictionary's index type be an opaque type that only the dictionary can control. You wouldn't want somebody necessarily just adding one to your offset. That wouldn't necessarily move to the next element in the dictionary. It could move some arbitrary, maybe uninitialized part of the dictionary's internal storage. So instead we want the dictionary to control moving forward through the collection by advancing the index. And so to do that, we add another method. That given an index, gives you the index that marks the position after it.

Once you take this step, you need a couple more things. You need a start index property, and an end index property. Because a simple count isn't going to work anymore in order to tell us that we've reached the end. Now that we're not using Ints as our index type.

So let's bring those back to the collection protocol. So we've got a subscript that takes some index type to represent a position, and gives you an element there. And, we've got a way of moving that position forward. But we also need types to supply what kind of type they're going to use for their index. We do that with another associated type. Conforming types would supply the appropriate types. So an array or a data would give an Int as their index type. Whereas a dictionary would give its own custom implementation that handles its own internal logic.

So let's go back to count that we dropped a minute ago in order to generalize our indexing model. It's still a really useful property to have. So we probably want to add it back as an extension on collection. Something that walks over the collection, moving the index forward, incrementing a counter that it then returns.

Now, if we try and implement this, we hit another missing requirement. Since we moved off of Int to a general index type, we can no longer assume that the index type was equatable. Ints are, but arbitrary index types aren't necessarily. And, we need that in order to know that we've reached the end.

Now, we could solve this in the same way that we did earlier, of constraining our extension. Say that it only works when the index type is equatable. But, that doesn't feel right. We want a protocol to be easy to use. And it's going to get really irritating, if we have to always, on every extension we write, put this constraint on there. Because we're nearly always going to need to be able to compare two indexes.

Instead, it's probably better expressed as a requirement of the protocol. As a constraint on our index-associated type. Putting this constraint on the protocol means that all types that conform to the protocol need to supply an equatable type for their index. That way you don't have to specify it every time you write the extension.

This is another example of negotiating the protocol contract. Users of the protocol had a requirement that they really needed to be able to compare indexes. And, conforming types, they did a check that they can reasonably accommodate that without giving up too much flexibility. In this case, they definitely can. Ints, the data, and array are using are already equatable. And, with Swift 4.2's new automatic synthesis of equatable conformance. It's easy for dictionary to make its index type equatable as well.

Next, let's talk about optimizing this count operation with a customization point. So, we've written a version of count, that calculates the number of elements in the collection by walking over the entire collection. But, obviously a lot of collections can probably do that a lot faster. For example, supposing a dictionary kept internally a count of the number of elements it held, for its own purposes. If it has this information, it can just serve it up in its own implementation of count. That means that when people call count on a dictionary, they're getting fast constant time. Instead of the linear time that our original version that works with any collection takes.

But, when adding optimizations like this, there's something you need to be aware of. Which is the difference between fulfilling protocol requirements, and just adding lots of overloads onto specific types. Up until now, this new version of count on dictionary is just an overload. That means that when you have a dictionary, and you know it's a dictionary. You'll get the newer, better version of count.

But, what about calling it inside a generic algorithm? So supposing we wanted, for example, to write a version of the standard library's map? If you're not already familiar with it, it's a really useful operation that transforms each element in the collection. And gives it back to you as a new array.

The implementation's pretty simple. It just creates a new array, moves over the collection, transforms each element. And then appends it to the array. Now, as you append elements to an array like this, the array automatically grows. And, as it grows, it needs sometimes to re-allocate its internal storage. In order to make more room to accommodate the new elements.

In a loop like this, it might have to do that multiple times over, depending on how big it gets. And, doing that takes time. Allocating memory can be fairly expensive. There is a nice optimization trick we can do with this implementation. We already know exactly how big the final array is going to be. It's going to be exactly the same size as our original collection. So we could reserve exactly the right amount of space in the array up front, before we start appending to it, which is a nice speed-up. And to do this, we're calling count.

But, we're calling count here, in what's referred to as a generic context. That is, a context where the collection type is completely generic, not specific. It could be an array, or a dictionary, or a link list, or anything. So, we can't know that it necessarily has a better implementation of count available to it. When the compiler compiles this code.

And so, in this case, the version of count that's going to be called is actually the general version of count. That works on any collection and iterates over the entire collection. If you called map on a dictionary, it wouldn't call the better version of count that we've just written yet.

In order for customized method or property like this to be called in a gen-- in a generic context. It needs to be declared as a requirement on the protocol itself. We've established that there's definitely a way in which certain collections could provide an optimized version of count, so it makes sense to add it as a requirement on the protocol.

Now, even though we've made it a requirement to implement it, all collections don't have to provide their own implementation. Because we've already provided one via our extension that will work on any collection. Adding a requirement to the protocol, and alongside it adding a default implementation via an extension is what we refer to as a customization point.

With a customization point, the compiler can know that there's potentially a better implementation of a method or property available to it. And so, in a generic context, it dynamically dispatches to that implementation through the protocol. So now, if you call map on a dictionary, even though it's a completely generic function.

You will get the better implementation of count. Adding customization points like this, alongside default implementations through extensions. Is a really powerful way of getting the same kind of benefit that you can also get with classes, implementation inheritance, and method overwriting. But, this technique works on structs and enums, as well as classes.

Now, not every method can be optimized like this. And, customization points have a small but non-zero impact on your binary size, your compiler runtime performance. So, it only makes sense to add customization points when there's definitely an opportunity for customization. For example, in the map operation that we just wrote. There's no reasonable way in which any different kind of collection could actually provide a better implementation. And so, it doesn't make sense to add it as a customization point. It can just stay as an extension.

So, we've created this collection type, and it's actually pretty fully-featured now. It has lots of different conforming types possible. And various different useful algorithms you can write for it. But, sometimes you need more than just a single protocol in order to categorize your family of types. You need protocol inheritance. And, to talk to you more about that, here's Doug.

Thank you, Ben. So, protocol inheritance has been around since the beginning of Swift. And, to think about where we need protocol inheritance. Let's go look at this collection protocol that we've been building. It's a nice protocol. It's well-designed. It describes a set of conforming types, and gives you the ability to write interesting generic algorithms on them.

But, we don't have to reach very far to find other collection-like algorithms that we cannot implement in terms of the collection protocol thus far. For example, if we want to find the index of the last element in a collection, that matches some predicate. The best way to do that would be to start at the end, and walk backwards. Collection protocol doesn't let us do that. Or say we want to build a shuffle operation to randomly shuffle around the elements in a collection. Well, that requires mutation, and collection doesn't do that. Now it's not that the collection protocol is wrong.

But it's that we need something more to describe these additional generic algorithms, and that is the point of protocol inheritance. So, here the bidirectionalCollection protocol inherits from, or is a collection. What that means is that any type that conforms to the bidirectionalCollection protocol also conforms to collection, and you can use those collection algorithms. But bidirectionalCollection adds this additional requirement, of being able to step backwards in the collection.

An important thing to note is not every collection can actually implement this particular requirement. Think of a singlyLinkedList, where you only have these pointers hopping from one location to the next. There's no efficient way to walk backward through this sequence, so it cannot be a bidirectionalCollection. So, once we've introduced inheritance, you've restricted the set of conforming types. But you've allowed yourself to implement more interesting algorithms. So, here's the code behind this last index where operation. It's fairly simple. We're just walking backwards through the collection, using this new requirement from the bidirectionalCollection protocol.

Let's look at a more interesting algorithm. So here's a shuffle operation. So, it was introduced for, for collections in Swift 4.2. You don't have to implement it yourself, but we're going to look at the algorithm itself to see what kinds of requirements it introduces to figure out how to categorize those into protocols meaningfully. So the Fisher-Yates shuffle algorithm's a pretty old algorithm. It's also fairly simple. You start with an index to the first element in the collection. And then, you select randomly some other element in the collection, and swap those two.

In the next iteration, you move the left index forward one. Randomly select between there and the end, swap those elements. And so, the algorithm is pretty simple. It's just this linear march through the collection, randomly selecting another element to swap with. And, at the end of this, you end up with a nicely shuffled collection.

So, we can actually look at the code here. It's a little bit involved. Don't worry about that. And, we're going to implement it on some kind of collection. So, we'll look at the core operations in here. So, first we need to be able to grab a random number between where we are in the collection and the end of the collection, using this, this random facility. But, that's an integer. And what we need is an index into the collection. We know those are different. So we need some operation. Let's call it index offsetBy.

To jump from the start index quickly over to whatever position we've selected. The other operation we need is the ability to swap two elements. Great. We have two operations that we need to add to the notion of a collection to be able to implement shuffle. Therefore, we have a new shuffleCollection protocol.

Please don't do this. So this is an anti-pattern that we see. And the anti-pattern here is we had one algorithm. We found its requirements, and then we packaged it up into a protocol that is just that one-- just describes that one algorithm. If you do this, you have lots and lots and lots of protocols around that don't have any interesting meaning. You're not learning anything from those protocols.

So what you should do is notice that we actually have distinct capabilities here. So shuffle is using random access, and it's using mutation. But, these are, these are separate, and we can categorize them in separate protocols. So, for example, the randomAccessCollection protocol is something where it allows us to jump around the collection, moving indices quickly.

And there are types like unsafeBufferPointer that can give you random access. But, do not allow any mutation. That's a separate capability. So, we also have the mutableCollection protocol here. And, we can think of types here that allow mutation, but not random access, like the singlyLinkedList that we talked about earlier. Now, you notice that we've essentially split the inheritance hierarchy here.

We've got the access side for random access, bidirectional, and so on. And then, we've got this mutation side. That's perfectly fine, because clients themselves can compose multiple protocols to implement whatever generic algorithm they're doing. So, we go back to our shuffle algorithm. And it can be written as an extension on randomAccessCollection, with a self-type. So this is the type that conforms to randomAccessCollection also conforms to the mutableCollection protocol. And now, we've pulled together the capabilities of both of these.

Now, when you have a bunch of conforming types, and a bunch of generic algorithms, you tend to get protocol hierarchies forming. Now, these hierarchies, they shouldn't be too big. They should not be too fine-grained. Because you really want a small number of protocols that really describe the kinds of types that show up in the domain, right? And now, there's things, things that you notice when you do build these protocol hierarchies.

So, as you go from the bottom of the hierarchy to the top, you're going to protocols that have fewer requirements. And therefore, there are more conforming types that can implement those requirements. Now, on the other hand, as you're moving down the hierarchy, and combining different protocols from the hierarchy. You get to implement more intricate, more specialized algorithms that require more advanced capabilities. But naturally work with fewer conforming types.

Okay. So let's talk about conditional conformance. This is, of course, a newer feature in, in Swift. And, let's start by looking at slices again. So for any collection that you have, you can form a slice of that collection by subscripting with a particular range of indices. And, that slice is essentially a view into some part of the collection.

Now these are default type that you get from slicing a collection, is called slice. And slice is a generic adaptor type. So it is parameterized on a base collection type, and it is itself a collection. So our expectation on a slice is that you can do anything to a slice that you can do to the underlying collection. It's a reasonable thing to want.

And so, certainly we can go and use the forward search operations like indexwhere, to go find something matching a predicate. And that works on the collection and any slice of that collection. So, we'd like to do the same thing with backwards search, but here we're going to run into a problem. So even if the buffer is a bidirectionalCollection, nothing has said that the slice is a bidirectionalCollection.

We can fix that. Let's extend slice to make it conform to the bidirectionalCollection protocol. We need to implement this index before operation, which we can implement in terms of the underlying base collection. Except the compiler's going to complain here. The only thing we knew about that base collection is that it's a collection. It doesn't have an index before operation on it.

We know how to fix this. All we need to do is introduce a requirement into this extension to say that well, base needs to be a bidirectionalCollection. This is conditional conformance. All it is, is extensions that declare conformance to a protocol. And then the constraints under which that conformance actually makes sense. And the wonderful thing about conditional conformance, is it stacks nicely when you have these protocol hierarchies. So we can also state that slice is a randomAccessCollection. When its underlying base type is a randomAccessCollection.

Now, notice that I've written two different extensions here. Now, it's generally good Swift style. Write an extension, have it conform to one protocol, so you know what that extension is for, you know its meaning. It's particularly important with conditional requirements, conformances, because you have different requirements on these extensions. And, this allows for composability. Whatever the underlying base collection can do, the slice type can also do.

So let's look at another application of conditional conformance, also in the standard library, and these are ranges. So, ranges have been around forever in Swift. And, you can form a range with, for example, these dot-dot less than operations. And so you can form ranges of doubles, you can form ranges of integers. But some ranges are more powerful than others. So, you can iterate over the elements in a range of integers. Well, why can you do that? It was because an intRange conforms to collection.

Now, if you're actually look at the type, it's reduced by that dot-dot less-than operator. It is aptly named the range type. Again, it's generic over the underlying bound type. So in this case, we have a range of doubles, and it merely stores the lower and upper bounds. That's fairly simple. But, prior to Swift 4.2, you would get from an integer range, an actually different type. This is the countableRange type.

Now, notice it's structurally the same as the range type. It has one type parameter. It has lower and upperBound. But it adds a couple additional requirements onto that bound type. That the bound be stridable, right? Meaning you can walk through and enumerate all the elements. Now that's the ability you need so that you can make countableRange conform to randomAccessCollection.

That enables the forEach, the forEach iteration loop, and other things. But with conditional conformance, of course, we can do better. So let's turn the basic range type into a collection, when the bound type conforms this-- has these extra stridable requirements on it. It's a simple application of conditional conformance. But it makes the range type more powerful when used with better type parameters.

Now, notice that I'm just conforming to randomAccessCollection. I have not actually mentioned collection or bidirectionalCollection. With unconditional performances, this is okay. Declaring conformance to randomAccessCollection implies conformances to any protocols that it inherits. In this case, bidirectionalCollection and collection. However, with conditional conformance, this is actually an error. Now, if you think back to the slice example, we needed to have different constraints for those, for those different levels of the hierarchy for collection. Versus bidirectionalCollection versus randomAccessCollection.

And so, compiler's enforcing that you've thought about this, and made sure that you have the right set of constraints for conditional conformance. In this case, the constraints across the entire hierarchy are the same. So, we can just write out explicitly collection and bidirectionalCollection. To assert that this is where all these conformances are. Or we can do the stylistically better thing, and split out the different conformances.

Now at this point, our range type is pretty powerful. It does everything the countableRange does. So what should we do with countableRange? We could throw it away. In this case we're talking about the standard library, and there's a lot of code that actually uses countableRange. So we can keep it around as a generic type alias. This is a really nice solution. So the generic type alias adds all of those extra requirements you need to make the range countable. The requirements you need to turn it into a collection, but it's just an alternate name for the underlying range type.

Again, this is great for source compatibility, because code can still use countableRange. On the other hand, it's also really nice to give a name to those ranges that have additional capabilities of being a randomAccessCollection. In fact, we can use this to clean up other code. To say, well, we know what a countableRange is.

It's a range with this extra striding capability, so we can go extend countableRanges. And that is a case in which we have randomAccessCollection conformance. So, we've introduced this in Swift 4.2 to help simplify the set of types that we're dealing with. And make the existing core types like range more composable and more flexible.

Recursive constraints describe relationships among protocols and their associated types. This is a topic that we didn't cover in the WWDC version of this talk. But it's an important part of the standard library's use of Swift's generic system. Let's jump right in. A recursive constraint is nothing more than a constraint within a protocol that mentions that same protocol. Here, collection has an associated type named subsequence. That is itself a collection. Why would you need this? Well, let's look at a generic algorithm that relies on it.

So here, given an already sorted collection. We want to find the index at which we should insert a new value. To maintain that sort order. We're going to compute the sorted insertion point for the value 11. When we go ahead and insert 11 at that index, the result is still a sorted array. The sorted insertion point of function is implemented in terms of a binary search.

Binary search is a classic divide-and-conquer algorithm. Meaning that at each step, it makes a decision that allows it to significantly reduce the problem size. For the next step to consider. For binary search, we first look at the middle element, 8. And compare it against the value that we want to insert. That's 11. And because 11 is greater than 8, we know that 11 needs to be inserted somewhere after the 8. In the latter half of the collection. So we restrict our search space by half.

In our next step, we find the new middle, 14, and compare it against the value we want to insert. Eleven is less than 14, so the insertion point has to come before the middle. Divide the remaining collection in half again. Continue dividing collection we're looking at in half. Until we're pointing at the proper insertion point. That's our solution.

Divide-and-conquer algorithms like this are fantastic. Because they're extremely fast. Binary search takes logarithmic time. Which means that doubling your input size doesn't make the algorithm run twice as slowly like it would for a linear algorithm. With a logarithmic algorithm like binary search, it only has to perform one additional step to cut the problem size in half again.

So let's turn that into code. The first thing we need to do is find the index of the middle element. Which we can do using randomAccessCollections index offset by a function. Next, we check whether our value comes before the middle element. So we know which half of the collection contains our insertion point.

Now in our example, the value to insert is greater than the middle element. So we take a slice of the collection from the index after the middle. All the way until the end. And recursively call sort and insertion point of on that slice. This is common of divide-and-conquer algorithms.

Where you reduce the problem space and then recurse. Now to make this work, we need that slicing syntax. Provide a suitable slice of a collection. We can do this for all collections by introducing a general operation that takes a range of indices and produces a slice. Like this.

Now remember that the slice adapter we discussed earlier works on any collection. Providing a view of the elements of the underlying collection that is itself a collection. This makes our divide-and-conquer algorithm work for any collection. As well as providing slicing syntax to all collections. That's great, but there's just one problem. Some collections don't want this particular slice type. They really want to provide their own slicing operations that produce a different type. String is the most common example. When you slice a string, you get back a substring.

And so if you apply our divide-and-conquer algorithms to the string collection. You really want those to be in terms of substring. Rather than some other type like the slice of a string. Range is another interesting example. Because its slicing operation returns an instance of the exact same range type just with the new bounds.

So to capture this variation among different types that conform to collection, we can introduce new requirements into the collection protocol. Specifically for slicing. So here we've pulled the slicing subscript into the collection protocol itself as a requirement. Now note that the result type of this subscript is described by a new associated type: subsequence.

Now both string and range meet these new requirements of collection. With string, the subsequence type is substring. For range, the subsequence type is going to be the range itself. Now this works well for, for string and range. But for all the other collection types that don't want to customize the actual subsequence type. We can provide default limitations of slicing. So the authors of these collection type don't actually have to do any extra work to conform to collection. They get all the slicing behavior for free.

So we're going to start with subsequence. Associated types themselves can have default values. Written after the equals sign. For subsequence, the slice adaptor type is a perfect default because it works for all collections. So this default will be used for any conforming type that doesn't provide its own subsequence type.

This pairs well with the implementation of the slicing subscript we started with earlier. Written in extension on the collection protocol. And it can act as a default implementation, providing the slicing subscript operation that returns a slice. We can even go one step further and limit the applicability of our default slicing subscript implementation to those cases where we picked the default subsequence type. So this pattern prevents the default implementation from showing up as an overload on collection types that have customized their subsequence. Like string and range. So this is all great for conforming types. They get slicing for free, or they can customize it if they want to.

But remember our goal here. We're trying to write our divide-and-conquer algorithms against the collection protocol. So we have to answer one really important question. What does subsequence do? All we know about subsequence right now is that it's the result type of the slicing subscript operation. But we need more to actually use it.

So to answer this question, we have to go back to the algorithms that we want to write in terms of subsequence. Our algorithm is recursive. It forms a slice which is now a value of the subsequence type. And then recursively calls sort insertion point of on that slice. Now this only makes sense if the subsequence type you get back is itself a collection.

Now when it performs that call, we're going to pass a value of the collection's element type. But the recursive call itself is going to expect a value of this subsequence's element type. The only way this can possibly make sense is if those element types are identical. Now the same issue comes up when returning an index from the recursive call. Which is going to be computed in terms of the subsequence.

But that index that's returned also needs to be a valid index for the current collection. So we can capture all of these requirements in the collection protocol itself. Now the first thing we want to do is say that the subsequence of a collection is itself a collection. This is a so-called recursive constraint. Because the associated type conforms to its own enclosing protocol.

We can then use associated type where clauses to further constrain our subsequence. As we talked about earlier, it has an element type. And that element type needs to be the same as that of the original collection. So we can express that here with the same type constraint. Subsequent element is the same as element. We can do exactly the same thing for the index type. Now, these cover all the properties that we discovered by looking at the implementation of the sorted insertion point of algorithm.

This leads us to an interesting question. Can you slice a subsequence? Well, every subsequence is a collection and every collection has a slice operation. So of course you can slice a subsequence. And the result is going to be a subsequence of the subsequence. Now you can do this again and get a subsequence of a subsequence of a subsequence. And keep on going on and on and on.

Now interestingly, at each point we could have a brand-new type. And so we have this potentially infinite tower of types. That's actually okay. Each recursive step in our generic algorithm could conceivably create a new type. Based on the current collection type. So long as the recursion eventually terminates at runtime, there's no problem with this. However, it's often the case divide-and-conquer algorithms can be implemented more efficiently by making them nonrecursive.

So here is the nonrecursive implementation of the sort and insertion point of algorithm. We're going to walk through it. Because the core algorithm is the same. But it's expressed iteratively with this while loop rather than recursively. So the first thing we're going to do is take a slice of the whole collection.

This slice variable is going to represent the part of the collection that we're looking at in each iteration. And now we see the familiar divide-and-conquer pattern. Find the middle of the slice. And then compare the value to insert against the middle element in the slice. We then narrow the search base by slicing the slice before we go in loop again.

However, here we have a problem. We're performing an assignment to the slice variable. Which is of the subsequence type. On the other hand, the right-hand side is a slice of a slice. And as we talked about before, this is a subsequence of the subsequence and could be a completely different type. So we're going to get a compiler error telling us that these two types are not necessarily the same.

That's really inconvenient here because it prevents us from writing this nonrecursive algorithm. And it doesn't really reflect how specific collection types behave. Think about string. If you slice a string, you get a substring. If you slice a substring, you don't get a sub-substring. You just get another instance of the substring type. So let's go back to how this slice adapter works to generalize this notion. We have a collection. We're going to call it Self, that we've sliced from I to J.

Now that's going to build something of the type slice of Self. Which is just a view on the underlying Self collection. If we then slice the slice, we get a slice of slice of self. Which is a view of a view on that same underlying Self collection. So this is our infinite tower of types in practice. However, it doesn't have to be this way. Remember that the slice types use the same indices as their underlying collection. And they also know about their underlying basic collection.

So when we slice the slice, we can take those new indices, I2 and J2. Bring them back to the original base collection and form the new slice from there. And what this does is it means that when you slice a slice, you get something back of the same slice type. Effectively tying off the recursion.

This is exactly the same behavior we saw with substring. And it's completely reasonable to expect that all subsequence types behave in this way. So let's model it as an explicit part of the collection's protocol requirements. So here we're saying that the subsequence of a subsequence is the same type as the subsequence. In other words, when you slice a slice, you get back the same slice.

This makes our nonrecursive divide-and-conquer algorithm work. And simplifies the use of the collection protocol. There's no more need to reason about infinite tower of types. Now there's one last issue here involving subsequence. We've said it's required to be a collection. But we need the subsequence type to be a random access collection to perform this index offset by operation.

To describe this, we can use protocol where clauses. So when bidirectionalCollection inherits from collection. It can add a new constraint on subsequence, requiring it to conform to that bidirectionalCollection protocol. This again is a recursive constraint but now it's expressed on the bidirectionalCollection protocol. We can do the exact same thing for randomAccessCollections. Such as the subsequence of a random access collection, itself conforms to randomAccessCollection. Note how the constraints on subsequence follow the enclosing protocol.

This might sound a little bit familiar. Both recursive constraints and conditional conformance tend to track the protocol hierarchy like this. And the features support each other. This is particularly important because we want the default associated type for subsequence, the slice of Self, to work at every level of the collection hierarchy. Slice is always a collection. When we go ahead and create the bidirectionalCollection protocol. It now requires that the subsequence type also conform to bidirectionalCollection.

The slice adapter's conditional conformance to bidirectionalCollection which kicks in anytime itself is known to be a bidirectionalCollection. Satisfies that requirement. RandomAccessCollection works the same way. Subsequence gains a randomAccessCollection requirement. And slices conditional conformance to randomAccessCollection satisfies that requirement. Now itself is known to be a randomAccessCollection. This behavior where an associated type default works for every protocol within the hierarchy is a good indicator of a cohesive design.

If you find yourself needing different associated type defaults at different points in the collection hierarchy. You might have a problem with your design. Recursive restraints are a powerful tool. Used with associated type and protocol where clauses, they help us write the protocol requirements we need to express divide-and-conquer algorithms naturally in generic code. And now we return to the final portion of the WWDC talk.

So, Swift is a multi-paradigm language. We've been talking exclusively about generics right now. But of course, Swift also supports object-oriented programming. And so, I'd like to take a few moments to talk about the interaction between those two features. How they work together in the Swift language. So with class inheritance, we know how class inheritance works. It's fairly simple. You can declare a superclass, like Vehicle. You can declare some subclasses, like Taxi and PoliceCar that both inherit from Vehicle.

And, once you do this, you have this object-oriented hierarchy. You have some expectations about where you can use those subclasses. So if I were to extend Vehicle with a new method, to go let it drive, I fully expect that I can call that method on one of my subclasses, Taxi.

So, this is a fundamental aspect of object-oriented programming. And, Barbara Liskov, actually described this really well in a lecture back in the '80s. Since then, we've referred to this as the Liskov substitution principle. And, the idea's actually fairly simple. So, if you have someplace in your program that refers to a supertype, or superclass, like Vehicle.

You should be able to take an instance of any of its subtypes, or subclasses, like Taxi or PoliceCar, and use that instead. And the program should still continue to type check and run correctly. So, the substitution here is an instance of a subclass should be able to go in anywhere that the superclass was expected and tested. And, this is a really simple principle. We've all internalized it, but it's also really powerful. If you think about it. And at any point in your program think well, what happens if I get a different subclass, maybe a subclass I haven't thought about here.

So, getting back to generics, what are our expectations when applying Liskov substitution principle to the generic system? Well, maybe we add a new protocol, Drivable. Whatever. And extend Vehicle to make it Drivable. What do we expect to happen? Well, we expect that you can use that protocol, conformance of Vehicle to Drivable, for some of its subclasses as well. Say, you add a simple generic algorithm to the Drivable protocol to go for a sundayDrive. Well, now you should be able to use that API on a PoliceCar, even if that might not be the best idea.

So, the protocol conformance here is effectively being inherited by subclasses. And this puts a constraint on the conformance. The one conformance that you write, the thing that makes Vehicle Drivable. Has to work for all of the subclasses of Vehicle now and anyone that comes up with it later. Most of the time, that just works.

However, there are some cases where this actually adds new requirements on the subclasses. The most common one is when dealing with initializer requirements. So, if you've looked at the decodable protocol, it has one interesting requirement. Which is the initializer requirement to create a new instance of the conforming type from a decoder.

How do we use this? Well, let's go add a convenience method to the decodable protocol. It's a static method decode that creates a new instance from a decoder, essentially a wrapper for the initializer, making it easier to use. And, there's two interesting things to notice about this particular method.

First, is it returns Self with a capital S. Remember this is the conforming type. It's the same type that you're calling the static method on. Now, the second interesting thing is, how are we implementing this? Well, we're calling to that initializer above to create a brand-new instance of whatever decodable type we have, and then return it.

Fair enough. We can go ahead and make our Vehicle type Decodable. And then, what we expect, when applying the Liskov substitution principle, is we can use any subclass of Vehicle. With these new API's that we've built through the protocol conformance. So, we can call Decode on a Taxi. And what we get back is not a Vehicle not some arbitrary Vehicle instance, but the Taxi, an instance of Taxi.

This is great, but how does it work? So let's take a look at what Taxi might have. Maybe there's an hourly rate here, and when we call Taxi.decode from, we're going through the protocol, going through the protocol initializer requirement. There's only one initializer this can actually call, and that's the initializer that's declared inside the Vehicle class, in the superclass here.

So that initializer, it knows how to decode all of the state of a Vehicle. But it knows nothing about the Taxi subclass. And so, if we were to use this initializer directly, we would actually have a problem that the hourly rate would be completely uninitialized, which could lead to some rather unfortunate misunderstandings when you get your bill at the end.

So, how do we address this? Well, it turns out Swift doesn't let you get into this problem. It's going to diagnose at the point where you try to make Vehicle conform to the decodable protocol that there's actually a problem with this initializer. It needs to be marked required.

Now, a required initializer has to be implemented in all subclasses. Not just the direct subclasses, but any subclasses of those, any future subclasses you don't know about now. Now by adding that requirement, it means that when Taxi inherits from Vehicle, it also needs to introduce an initializer with the same name. Now, this is important because this initializer's responsible for decoding the hourly rate. And then chaining up to the superclass initializer to decode the rest of the Vehicle type.

Okay. Now, if you're reading those red boxes really quickly, you may have noticed the subphrase non-final. So, by definition, final classes have no subclasses. So, it essentially exempts them from being substituted later on. That means that there's no sense in having a required initializer because you know there are no subclasses. And so final classes are in a sense a little easier to work with when dealing with things like decodable or other initializer requirements. Because they're exempt from these rules of having required initializers.

So when you're using classes, for reference semantics, consider using final when you no longer need to customize your class through the inheritance mechanism. Now, this doesn't mean that you can't customize your class later. You can still write an extension on it. The same way you can extend a struct or an enum. You can also add conformances to it, to get more dynamic dispatch. But final can simplify the interaction with the generic system, and also unlock optimization opportunities for the compiler in runtime.

So we've talked a bit about Swift generics today. The idea behind Swift generics is to provide the ability to reuse code while maintaining static type information. To make it easier to write correct programs, and compile those down into efficient, efficiently executing programs. When you're designing protocols, let this push and pull between the generic algorithms you want to write against a protocol. And the conforming types that need to implement that protocol guide your design to meaningful extractions. Introduce protocol inheritance when you need some more specialized capabilities to implement new generic algorithms that are only supportable on a subset of the conforming types.

And, conditional conformance when you're writing generic types, so that they can compose nicely, especially when working with protocol hierarchies. And finally, when you're reasoning about the tricky interaction between class inheritance and the generic system. Go back to the Liskov substitution principle, and think about what happens here if I introduce a subclass rather than a superclass at which I wrote the conformance. Well, thank you very much. There's a couple of related sessions on embracing algorithms and understanding how they can help you build better code. As well as using Swift collections effectively in your everyday programming. Thank you.