Subset interpretation of subtypes

In formal language, this means: The set denoted by the parent type is a superset of the set denoted by the child type. Equivalently, a subtype denotes a subset of the set denoted by the parent type.

Let’s pick back up with the mystery we had last week. How can Airplane be a subset of Vehicle, if it contains more internal variables and values?

This only makes sense when realizing that the set of objects denoted by a class A is the set of all objects that have at least the properties specified by A. You can think of the additional properties as additional constraints.

In Java, you declare subtypes like this:

class B extends A {
    // ...
}

This means that B is a subtype of A, and a B object is also an A object. This is consistent with the subset interpretation: if you drew the Venn diagram of these two values, B would be completely contained within A.

Subtyping of function types

In Java, subtyping is only possible between classes. But what about languages in which functions are values? If a language like that is object-oriented, can there be subtyping between function types?

For example, if B is a subtype of A, is a function B => B a subset of A => A?

Scala, the next language we’re covering, does have subtyping of function types.

Note that the prof’s Scala is a bit rusty, so don’t take the syntax here as correct.

def f(g: A => int) {...}
// ^ Takes a function as a parameter
def h(x: A) { return 6; }
// ^ Is a function of type A => int

It’s obvious you can pass h into f. But, can you pass this into f?

def j(y: B) { return 7; }
// ^ B is a subtype of A

Can you call f(j)? No. What if f passes an A that is not a B to its function parameter? j is always expecting a B object and wouldn’t know what to do with a non-B A object.

So in summary, if B is a subtype of A, B => int is not a subtype of A => int.

But could A => int be a subtype of B => int? Yes.

def f(g: B => int) {...}
// ^ Takes a function as a parameter
def h(x: A) { return 6; }
// ^ Is still a function of type A => int
f(h); // This is fine

Why? Because every B, even the ones you instantiate or create from within f, are also As, so passing them into an A => int function is fine.

What does this mean in general? Function subtyping works in the opposite direction of the inputs to the function. We say that function subtyping is contravariant with respect to the input type of the function.

Note that this doesn’t apply to the output type.

def f(g : int => A) { A a = g(3); }
def h(x : int) { return new A(); }
f(h); // This is fine.
def j(y : int) { return new B(); }
f(j); // This is fine too!

Why? Because every B is an A. The fact that the A that j returns is actually a B doesn’t matter. So function subtypes are not contravariant with respect to the return type. It’s covariant instead.

Putting it all together: if B is a subtype of A, and D is a subtype of C, then A => D is a subtype of B => C.

Prof uses a symbol to represent subtyping, kind of like a ⊆ but with a square open box above the line instead of a C shape. Here, I’ll use <: instead.

In notation: If B <: A and D <: C then (A => D) <: (B => C).

Let’s look at another example, assuming B <: A. Say we have the following functions:

• A => A
• A => B
• B => A
• B => B

What are the subtype relations? It goes a little like this (subtypes shown below their parents):

    B => A
   /      \
A => A  B => B
   \      /
    A => B

It’s sort of a lattice shape.

Bring in the subset interpretation

So how does this fit with the subset interpretation of subtyping? Let’s look at the input type first.

As usual, we’ll say B <: A. This implies A => int <: B => int. Thinking about this in the subset interpretation, this shows a different interpretation of B => int: it’s the set of all functions that can take a B and functions that can take any supertype of B, returning an int. Thinking of this in this way, it’s pretty clear that this set is a superset of A => int.

What about the covariant case, the return type?

With the same rules as above, int => B <: int => A. We can think of int => A as the set of all functions that return an A or any subtype of A. This makes it clear that it’s a superset of int => B.

Generic types in Java

Prof wants us to read a paper he’s posed on NYU classes, but will go over some of the material here.

Java used to have (and still has) collection types like List, etc. These were interfaces, meant to be implemented by things like LinkedList. But this just stores objects of type Object, which is the implied parent class of all other classes. To get values out, you need to cast the value.

List myIntList = new LinkedList();
myIntList.add(new Integer(6));
Iterator i = myIntList.iterator();
Integer x = (Integer) i.next(); // Casting

This looks like a cast in C or C++, but it’s not. Unlike C (which just does the cast without checking), Java does a runtime check to make sure that the cast you’re doing is valid. So (Integer) someObject will only run without exception if someObject is actually an Integer.

This also means you can mix types in an old-style Java linked list, but you can’t check these types at compile time, only at runtime. For example, this would work:

myIntList.add(new Object());

This defeats a lot of the purpose of static type checking. So later versions of Java introduced a feature for specifying what the type of the list is:

List<Integer> myIntList = new LinkedList<Integer>();
myIntList.add(new Integer(6));
// myIntList.add(new Object());
// ^ Produces a compile-time error
Iterator<Integer> i = myIntList.iterator();
Integer x = i.next(); // No cast needed

The type of the list is added within the angle brackets. The syntax for writing a generic class is similar:

class Entry<K, V> {
    private K key;
    private V value;
    
    public K getKey() {
        return key;
    }
    // ...and so on
}

You can also define generic interfaces:

interface I<T> {
    void foo (T x);
}

What’s the difference between this and C++ templates is that C++ is much more like textual substitution. They’re type-checked after expansion. Java performs type checking on the generic itself, giving you much stronger guarantees.

You can also have generic methods:

public static <T> Entry<T, T> twice(T value) {
    return new Entry<T, T>(value, value);
}

And you don’t even need to specify the type parameter when calling a method:

Entry<String, String> e1 = twice("Hello");
Entry<Integer, Integer> e2 = twice(7);

The implementers of Java had an interesting problem, though: they wanted to make this run on everybody’s machine, even people with older versions of Java. In other words, they needed to implement this within Java’s existing bytecode, to run on anyone’s JVM. Either that, or you can force everyone to update their JVM, which is a much less attractive option. They wanted it to run on old JVMs.

They did this through erasure. The type-checking for generics is all done at compile-time, so you don’t actually need that extra information at runtime. This information is erased. So effectively the newer, generic code effectively compiles into the same bytecode as the older, non-generic code. The only difference is the error messages the compiler generates. You can see this by using reflection at runtime:

ArrayList<Integer> li = new ArrayList<Integer>();
ArrayList<Float> lf = new ArrayList<Float>();

System.out.println(li.getClass().toString());
// ^ Prints just "class java.util.ArrayList"
System.out.println(lf.getClass().toString());
// ^ Also prints just "class java.util.ArrayList"
// These two classes are exactly the same and will
// compare as equal when compared with ==.

Subtyping with generics

Suppose you have this:

class <T> Collection<T> {
    void add(T x) {
        // ...add x to this collection...
    }
    //...
}

class A {...}
class B extends A {...}

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

The answer, surprisingly, is no. We’ll talk about why next class.