[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.
Dan GrossmanProfessor
