[music]. So now that I've shown you in the previous segment how generics and subtyping are good for different things. Let me show you an example of where they're good together and you actually need to combine them in order to get what you want. So to be clear, programming languages can have generics and subtyping. Java does, C# does, C++ with templates kind of does. So, sure you can have them. What's interesting is when you can use them together rather than sometimes use one and sometimes use the other. And the way we're going to combine them is called bounded polymorphism. And let us, it will let us write things like. Any type T1, that is a subtype of T2. So an ML quote a just says any type T1. In Java, we have subtype relationships, like, this is a subtype of that. It's only when we combine them, which we can do in Java and C#, that we say things, like any type T1, that is a subtype of T2. So, not any type, only those that meet that constraint. And I want to show you an example of where that's exactly the sort of thing you need to write, to write the code that you want to in a statically typed situation. So my example is a method that takes a list of points. A List is a collection just like List in ML or Racket. And it takes a circle. A circle is something that has a center and a radius. Okay? And what it returns is a new list of points, which is the subset of the points in the argument that lie within the circle, right? So you have a bunch of points, you have a circle, filter out all the ones that are outside the circle. That's all you want to do. And the nice method signature in Java, in case you're not familiar with Java, let me walk you through this, would look like this. It's a method called inCircle. Its return type is List of Points. The same thing we would write point list and is now list of points. Just use these angle brackets in this way. It takes three arguments. It takes the list of points that it's going to iterate through. Ut takes a point which is the center of the circle, and it takes basically, a real a double that is the radius, okay? And that's the signature we want. And, you know, just to be clear, at the bottom here, I have an implementation in Java. It's only a few lines long. You don't have to understand how it works. But it basically creates a new empty collection. Then has a little loop that goes through all the points in this argument pts. And if it's inside the circle, it adds it to the result. And I'm actually assuming that my points have certain methods that make this work, but the point is that it's a simple function, a simple method to write. I would like to use inCircle with this List of ColorPoints I have. That makes sense. I have a list of ColorPoints. I have some circle. I would like the output list, that's all the color points that are in the circle. Okay? Java and C# rightly disallow reusing the function, the method I've already defined. The reason is that List of ColorPoint is not a subtype of List of Point. And the reason is the same reason we studied when we learned about depth subtyping and how it's not sound, inCircle, as written here, would work just fine. If you passed it a List of ColorPoints, it would give back a List of ColorPoints, but we don't know that. The type checker doesn't know that. For all we know, the List of Points that inCircle returns includes some new point that it makes up, you know? It just makes up point you know, with an x-coordinate of two and a y-coordinate of four. And since that point that it makes up does not have a color field, it would be unsound to assume that everything in the output is a color point. Just, if everything in the input is a ColorPoint. And second, we have the same mutation problem we saw with dub sub-typing that we cannot trust inCircle not to add things to our input list that are points and not color points. And that would be the same problem. So, we cannot just use subtyping in this situation. So, if we can't use subtyping, can we use generics? So, suppose we replaced the method signature up here, which is what we have been using with the generic one. Now, if we said, well, inCircle takes a list of T for any type T, think of T as quote A, alright? Then it returns a list of T. Now, this would be great for colors. Because I could instantiate T with points and then have a list of points and get back a list of points. I could instantiate with color point, have a List of ColorPoint, get back List of ColorPoint. This is one problem, if this is the type, then I can instantiate T with anything, so I can instantiate with integer, or string, or foo, and that means that the body of this method cannot possibly to the right thing, right? What inCircle is supposed to be doing is treating the list as a List of Point things and, and checking if they're within some circle. If all it knows is that it has the elements are some unknown type T, then it won't be able to call any methods or access any of the state of points and then inCircle can't do anything useful. Okay? So we'll, the body of the inCircle method will not type check under this type. So, here is what we want. This is what we've been build, building up to is some sort of bound. We want to take that polymorphic version, that generic work at version and say, yeah, inCircle, given a list of T's will give back a list of T's but it assumes that T is a subtype of point. And at, and it assumes that, and under that assumption, it can write the body just like I showed you before. And now callers are going to have to meet that constraint. They're not going to be able to instantiate T with anything, but they can instantiate it with any subtype of Point. And so they can instantiate it with Point, they can instantiate it with ColorPoint, they could instantiate it with 3DPoint if that were a subtype of Point, but they can't instantiate it with non-subtypes of Points like String or Foo or Int or whatever. So we really are combining two great ideas here, we're using generics, we're using a list of T here and list of T here, and those can be any type. We're using subtyping to constrain the generics to make sure that the elements of this List are a subtype of Point. So that's the great idea of bounded polymorphism. Hopefully, this is a compelling example. There are plenty of other examples that come up. And that's all you need to know about it, just the high level idea that generics and subtyping can combine in this way. For those of you who have programmed in Java, I thought I would show you the actual syntax. That red on the previous slide, with the where, this is not Java. I just find it easier to explain that way. This is the actual syntax. You should be able to type this on and, and, and have it work. I need this extra thing over on the left to say that T is a subtype of Point. Use the keyword extends for that. You need these angle brackets to introduce that this is actually a generic method. And I should also admit one other thing about Java, is that all the nice things about generic, like it doesn't matter what T is, the method will behave the same way and all that sort of stuff. Doesn't actually hold in Java for backwards compatibility reasons, as well as making it easy to implement the way Java has typically implemented. There is always a way to use casts to get around the static checking with generics. That if you use generics, and you wish to put weird typecasts in weird places you'll be able to get strange results that you wouldn't get under a more conventional treatment of generics. That's okay. Java is under a lot of design constraints and used properly. You can use both generics and Java, as well as combining them with subtyping to get bounded polymorphism to enforce some pretty nice invariants. And use them for nice methods liked the inCircle method that you see here.
