Subtyping with generic classes

Start off with our typical example: B <: A. Then you have this:

class Collection <T> {
    void add(x : T) {
        //...
    }
}

Is Collection<B> a subtype of Collection<A>?

Let’s look at some examples.

void printAll(Collection<A> c) {
    for (A a : c) {
        System.out.print(a);
    }
}

Collection<A> ca = new Collection<A>();
ca.add(new A());

Collection<B> cb = new Collection<B>();
cb.add(new B());

// Can you do this, add a B to a collection of As?
ca.add(new B());
// Yep, because a B is an A.

// Can you do this, add an A to a collection of Bs?
//cb.add(new A());
// Nope. An A is not a B.

// Is this OK though?
printAll(ca);
// Of course, since ca is a Collection<A>.

But what about the B object in ca? Assuming that A and B have separate ToString functions, how will it print? Well, remember dynamic dispatch: it’ll print with A’s ToString for the A objects, and B’s ToString for its B objects. Other than that, it’s fine though.

Back to the example, is this ok?

printAll(cb);

Seems ok, doesn’t it? It’ll just print out all the Bs. But what if you had this function instead?

void insertA(Collection<A> c) {
    A a = new A();
    c.add(a);
}

// This is ok.
insertA(ca);
// THIS IS NOT!
insertA(cb);

You’d be inserting an A object into a Collection<B>! That’s bad! So Collection<B> cannot be a subtype of Collection<A>.

In Java in particular, there is never any subtyping in between two instances of a generic class. No matter what the relationship is between B and A, C<B> is not a subtype of C<A>.

Java takes a very conservative approach. Scala takes a more flexible approach.

Obviously in the case of printAll it’s ok to treat the generic classes as subclasses. But in insertA it’s not. Why? Because insertA modifies its argument.

If you had a way to guarantee that the function doesn’t modify its argument (meaning the argument was immutable), you could allow for subtyping in a covariant direction.

What about in the mutable function? If you had this:

void insertB(Collection<B> c) {
    B b = new B();
    c.add(b);
}

Collection<A> ca = new Collection<A>();
insertB(ca); // Is this ok?

In this case, it is. So when adding objects to that class, the subtyping is ok in a contravariant direction.

But this, however, is not ok:

retrieveSomeBSpecificData(ca);

So, in short, if you’re reading or accessing the elements, it’s covariant. If you’re modifying the collection, it’s contravariant. Java eschews this complication and just disallows all of it.

But what if you wanted a function that prints all objects, regardless of type? You could do this:

void printAll(Collection<Object> c) {
    for (Object o : c) {
        System.out.print(o);
    }
}

But you can’t cast between Collection<Something> and Collection<Object>, so that doesn’t work. So Java allows for this:

void printAll(Collection<?> c) {
    for (Object o : c) {
        System.out.print(o);
    }
}

The ? is called a “wildcard”, and it matches any type. In the for loop, you know that whatever is in there is at least an Object, so that’s what you use to get objects from the collection.

What about inserting things?

void insert(Collection<?> c) {
    Object o = new Object();
    c.add(o); // Is this ok?
}

Uh, no. No it’s not. You can’t just stick an Object into a Collection<Something>.

So objects passed in with a wildcard for the generic parameter must be immutable. The compiler will reject this code.

But what if you want to create a function for a restricted set of generic types, as opposed to all generic types? For example, if you had these classes:

class Vehicle {
    int speed;
    int position;
}

class Airplane extends Vehicle {
    int altitude;
}

Let’s say you wanted to make a function that can take in a Collection<Vehicle> and prints out the speed of each. Obviously you can’t just use a universal wildcard the way we did before, since Object doesn’t have a speed member. You can do this:

void printSpeed(Collection<Vehicle> c) {
    for (Vehicle v : c) {
        System.out.println("Speed is " + v.speed);
    }
}

This would allow you to pass in any Collection<Vehicle>. But what if you wanted to pass in a Collection<Airplane>, or any collection of any Vehicle subtypes?

void printSpeed(Collection<? extends Vehicle> c) {
    for (Vehicle v : c) {
        System.out.println("Speed is " + v.speed);
    }
}

Yep, that works. This gives us bounded polymorphism, allowing you to take many different types as long as those types are a subtype of Vehicle. In this case, they’re bounded from above, because you’re specifying the superclass.

But what about our insert example? Can we make an insert procedure for every instance of a generic?

void insertVehicle(Collection<? super Vehicle> c) {
    c.add(new Vehicle());
}

It’s ok to insert Vehicles into a collection of Vehicles, or a collection of anything above Vehicle. So we use polymorphism that’s bounded from below, meaning that this function can accept Vehicles or any of its superclasses.

There are other ways of doing this too, by making parametric functions, where you can actually name the wildcard type. The syntax looks something like this:

static <T extends A> List<T> doNothing(List<T> l) {
    return l;
}

Unlike C++, though, there’s no way to declare a new variable of type T, because of type erasure.

There are a lot more examples of this on the code on the course website. The examples are verbose and numerous, so I’m not reproducing them here.

That’s all for Java. Next assignment will be a combination of Java and Scala, and focused around generic types.

Scala

A relatively new language, around 10 years old, that combines features of an object-oriented language like Java with a functional style. So you get functional polymorphism and pattern-matching, like you do in ML.

And it runs on the Java Virtual Machine, which really helped it get adopted, because it could interoperate with Java code. It’s compiled by the Scala compiler directly into Java bytecode.

Scala provides a REPL as well, similar to ML, that runs the compiler after each line. But the REPL doesn’t 100% support every feature in the language, so watch out.

Info’s in the resources folder on NYU Classes for how to install it.

Features and syntax

Scala has a special type of class called a “singleton class”, accessed by the object keyword (used in place of class). It’s a class that allows only one instantiation, and all methods are static. This is where Scala looks for the main procedure. It also doesn’t have to be in a file with the same name.

All methods begin with the word def, followed by a name, and then either {...} for a procedure or = for a function.

Anyway, that was a bit of jumping ahead. Here’s how you define classes and subclasses.

class A

class B extends A

That’s all you need to define empty classes. Here’s a function that takes in an A:

def foo(x: A) = 6

Unlike ML you have to define the types of your parameters. But in this case, the return type is inferred as Int. And as usual, you can pass in either an A or B into this function.

But you can pass functions as parameters as well:

def bar(g:A => Int) = g(new A)

bar(foo) // returns 6

Here’s a practical example of our contravariance in function parameter type inheritance from last week:

def bif(y: B) = 18

//bar(bif) // Error!

def baz(g: B => Int) = g(new B)

baz(bif) // This works though.
baz(foo) // This works too!

Briefly revisiting the subset interpretation of subtyping

Obviously baz is of type (B => Int) => Int, and bar is of type (A => Int) => Int. We know type B is a subset of type A, is A => Int a subset of type B => Int? Yes. B => Int is clearly the bigger set, because it consists of not only al functions that take a B but also all functions that take an A.

That’s all for today. Last homework out soon.