Value Representation, Hashing, and Generics

CS2112

 2019/09/30 

From Lecture:

Download my notes in OneNote here

Subtyping

Like other implements declarations, the declaration above that LList<T> implements Collection<T> generates a subtype relationship: in fact, a family of subtype relationships, because the subtype relationship holds regardless of what actual type T is chosen. The compiler therefore understands that the relationship LList<String> <: Collection<String> holds. What about these other possible relationships?

LList<String> <: LList<Object> ?
LList<String> <: Collection<Object> ?

Both of these look reasonable at first glance. But they are actually unsound, leading to possible run-time type errors. The following example shows the problem:

LList<String> ls = new LList<String>();
LList<Object> lo = ls;
lo.add(2112);
String s = ls.head(); // extract data from head of list

The head element of the list, which is assigned to a variable of type String, is actually an Integer! This is erroneous, so the Java compiler will not allow it. A similar situation arises with arrays, although in that case the error is unfortunately only caught at run time.

String[] a = new String[1];
Object[] b = a;
b[0] = 2112;
System.out.println(a[0]);

The idea that there can be a subtyping relationship between different instantiations of the same generic type is called variance. Variance is tricky to support in a sound way, so Java does not support variance. Other languages such as Scala do have variance.

Wildcards

To make up for the lack of variance, Java has a feature called wildcards, in which question marks are used as type arguments. The type LList<?> represents an object that is an LList<T> for some type T, though precisely which type T is not known at compile time (or for that matter, even at run time).

A value of type LList<T> (for any T) can be used as if it had type LList<?>, so there is a family of subtyping relationships LList<T> <: LList<?>. This means that a method can provide a caller with a list of any type without the client knowing what is really stored in the list; the client can get elements from the list but cannot change the list:

LList<?> f() {
    LList<Integer> i = new LList();
    i.add(2);
    i.add(3);
    i.add(5);
    return i;
}

// in caller
LList<?> lst = f();
lst.add(7); // illegal: type ? not known
for (Object o : lst) {
    println(o);
}

Note that the type of the elements iterated over is not really known either, but at least we know that the type hidden by ? is a subtype of Object. So it is type-safe to declare the variable o as an Object.

If we need to know more about the type hidden by the question mark, it is possible to add an extends clause. For example, suppose we have an interface Animal with two implementing classes Elephant and Rhino. Then the type Collection<? extends Animal> is a supertype of both Collection<Elephant> and Collection<Rhino>, and we can iterate over the collection and extract Animals rather than just Objects.

Collection<? extends Animal> c = new LList<Rhino>();
for (Animal a : c) { 
    // use a as Animal here
}

Limitations

The way generics are actually implemented in Java is that all actual type parameters are erased at run time. This implementation choice leads to a number of limitations of the generics mechanism in Java when in a generic context where T is a formal parameter:

Constructors of T cannot be used; we cannot write new T(). The workaround for this limitation is to have an object with a factory method for creating T objects.
Arrays with T as elements cannot be created, either. We cannot write new T[n] , because the type T is not known at run time and so the type T[] cannot be installed into the object’s header. The workaround for this limitation is to use an array of type Object[] instead: T[] a = (T[]) new Object[n];

This of course creates an array that could in principle be used to store things other than T’s, but as long as we use that array through the variable a, we won’t. The compiler gives us an alarming warning when we use this trick because of the unsafe cast, but this programming idiom is fairly safe. Note that if we need to create an array of T in a context where T is known to be a subtype of some type, then the array that should be created is an array of that type, rather than of Object.

Similarly, we can’t create an array whose type includes a parameter type:
1
HashSet<String>[] sets = new HashSet<String>[n]; // error: generic array creation
The workaround is to use a wildcard type to create the array, and dynamically cast it to the desired type:
1
HashSet<String>[] sets = new HashSet<?>[n];

We can’t use instanceof to find out what type parameters are, because the object does not contain that information. If, for example, we create an LList<String> object, the object’s header word only records that it is an LList. So an LList<String> object that is statically typed as an Object can be tested to see if it is some kind of LList, but not whether the actual type parameter is String:

Object co = new LList<String>();

if (co instanceof LList<String>) ... // illegal
if (co instanceof LList<?>)      ... // legal
if (co instanceof LList)         ... // legal but discouraged

LList<String> ls = (LList<String>) co; // legal but only partly checked
LList<?>      ls = (LList<?>) co;      // legal
LList<String> ls = (LList<?>) co;      // illegal
LList<String> ls = (LList)co;          // legal but discouraged

The last four lines above illustrate how downcasts interoperate with generics. Code can cast to a type with an actual type parameter, but the type parameter is not actually checked at run time; Java takes the programmer’s word that the type parameter is correct. We can cast to a wildcard instantiation, but such a cast is not very useful if we need to use the elements at their actual type. Finally, we can cast to the raw type LList; casting to raw types is unsafe. It is essentially the same as casting to LList<?> except that Java allows a raw type to be used as if it were any particular instantiation. Raw types should be avoided when possible.

Accessing type operations

What if we want to use methods of T in a generic context where T is a formal parameter? There is more than one way to do this, but in Java the most powerful approach is to provide a separate model object that knows how to perform the operations that are needed. For example, suppose we want to compare objects of type T using the compareTo method. We declare a generic interface Comparator<T>:

interface Comparator<T> {
    /** Compares x and y. Return 0 if x and y are equal, a negative number if x < y, 
     *  and a positive number if x > y.
     */
    int compareTo(T x, T y);
}

Now, a generic method for sorting an array takes an extra comparator parameter:

/** Sort the array a in ascending order using cmp to define the ordering on the
 * elements. */
<T> sort(T[] a, Comparator<T> cmp) {
    ...
    if (cmp.compareTo(a[i], a[j]) > 0) {
        ...
    }
    ...
}

A class can then implement the comparator interface and be used to make the right comparator operation available to the generic code.

class SCmp implements Comparator<String> {
    @Override
    public int compareTo(String x, String y) {
        return x.compareTo(y);
    }
}

String[] a = {"z", "Y", "x"};
sort(a, new SCmp());

Notice that here we are using String‘s own compareTo operation as a model for the comparator, but we don’t have to. For example, we could have used the compareToIgnoreCase method to sort strings while ignoring the difference between upper and lower case. It turns out that we can also use Java 8’s new lambda expressions to implement the interface even more compactly. Here is how we would sort the array using a lambda expression while also ignoring case:

1	sort(a, (x,y) -> x.compareToIgnoreCase(y));

The lambda expression (x,y) -> x.compareToIgnoreCase(y) is actually just a very convenient syntactic sugar for declaring a class like the one above and instantiating it with new.

Generic classes may need to access parameter type operations too. The typical approach is to accept the model object in constructors, then to store it in an instance variable for later use by other methods:

class SortedList<T> implements Collection<T> {
    Comparator<T> comparator;

    SortedList(Comparator<T> cmp) {
        comparator = cmp; // save model object
        ...
    }

    boolean add(T x) {
        ...
        if (comparator.compareTo(x, y)) { // use model object
            ...
        }
        ...
    }
}