Review

• Type inference = compiler infers types from usage
• Example:

  fun f1(x) = x + 2;
  val f = fn : int -> int

• Hindley-Milner algorithm
  • Build tree
  • Annotate with known types and unknown type variables
  • Read off equations
  • Solve through unification

ActiveLecture.org Warm-up exercise: What is the type of

fun f(g)(h)(x) = g(h(x))

Subtype Hierarchy

• Characteristic of OO languages
• If S extends or implements T, S is a direct subtype of T (S <₁ T)
• Ex: FileReader is a subtype of InputStreamReader, Reader is a subtype of Closeable
• Subtype relationship <: is the transitive closure of <₁ (See JLS Section 4.10)
• In plain English: S <: T if there is a chain of extends/implements leading from S to T.
• Ex. FileReader <: Reader, FileReader <: Closeable
• Automatic conversion from subtype to supertype, e.g.

  Reader reader = new FileReader("input.txt");

Array Types

• In Java, array types are covariant. If S <: T, then S[] <: T[]
• For example, FileReader[] <: Reader[]
• Normally, that's convenient. Can pass FileReader[] to method that expects Reader[].
• Array store problem:

  String[] strs = { "Mary", "had", "a", "little", "lamb" };
  Object[] objs = strs; // legal: String[] <: Object[]
  objs[0] = new Watermelon(); // legal: Watermelon <: Object

• Now strs[0] is a Watermelon, not a String!
• In Java, throws ArrayStoreException
• The price for covariant arrays is a runtime check for every store

Generic Types

• Generic type = type with type parameter
• Example: ArrayList<File>
• Compile-time safety

  ArrayList<File> files = new ArrayList<File>();
   . . .
  files.add("mydata.txt"); // Error message

• Old-style Java:

  ArrayList files = new ArrayList();
  files.add("mydata.txt"); // No error
   . . .
  File file = (File) files.get(0); // ClassCastException

Java Generics

• Basics are very simple: Add <T>, use type variables

  public class ArrayList<T> {
     private T[] values; // white lie
     public T get(int i) { return values[i]; }
     . . .
  }

• Type variables are erased in virtual machine, i.e. ArrayList<File>, ArrayList<String> turn into plain ArrayList (with Object[] values)
• API compatibility: Pre-Java 5 APIs can be used with generics

Generic Interfaces

• Can have generic interfaces: Comparable<T> can compare against object of type T

  public interface Comparable<T> {
     int compareTo(T other)
  }

• Example:

  public class Employee implements Comparable<...> {
     public int compareTo(Employee other) { return id - other.id; }
     . . .
  }

• What is the type parameter of Comparable? ActiveLecture.org

Generic Methods

• Generic method in a non-generic class

  public class Util {
     public static <T> T max(List<T> lst) { . . . }
  }

• Parameter is inferred in call

  List<String> strs = . . .;
  String s = Util.max(strs); // infers Util.max<String>

• How can we implement max? Need to know that the list values are comparable
• Use type bound:

  public static <T extends Comparable<T>> T max(List<T> lst) {
     T max = lst.get(0);
     for (T x : lst) if (x.compareTo(max) > 0) max = x;
     return max;
  }

Generics and Inheritance

• Challenge to combine generics and OO
• If S is a subclass of T, should ArrayList<S> be
  1. a subclass of ArrayList<T>?
  2. a superclass of ArrayList<T>?
  3. unrelated to ArrayList<T>?

  Hint: Think about a concrete example for S and T

  ActiveLecture.org

Variance Problem

• Suppose ArrayList<Manager> was a subclass of ArrayList<Employee>

  ArrayList<Manager> bosses = ...;
  Employee empl = bosses.get(0); // OK, a manager is an employee
  ArrayList<Employee> empls = bosses; // managers are employees 
  empls.add(0, new Employee("Dilbert")); // OK to add employee

• bosses and empl are references to the same collection
• Dilbert has become a manager!
• Can we solve this with an ArrayStoreException?
• No—because of erasure
• The VM uses an Object[] array to hold the ArrayList elements

Wildcards

• Java solves variance with wildcards

  ArrayList<? extends Employee>

• “? extends” is effectively read-only:

  ArrayList<? extends Employee> empls;
  Employee e = empls.get(0); // OK
  empls.put(new Employee("Dilbert")); // Compile-time error

• Use for utility methods that can process lists of subtypes

  public void readAll(List<? extends Reader> readers)
     // ok to pass ArrayList<FileReader>

• If S <: T, which of the following subtype relationships hold? ActiveLecture.org
  1. G[S] <: G[T]
  2. G[? extends T] <: G[T]
  3. G[? extends T] <: G[S]
  4. G[S] <: G[? extends T]
  5. None of the above

Contravariance

• ? super is the opposite of ? extends
• Most commonly used in parameters of callbacks
• Consider this call:

  ArrayList<Manager> bosses = . . .;
     // Manager <: Employee <: Comparable<Employee>
  Manager m = Util.max(bosses);
     // static <T extends Comparable<T>> T max(List<T> lst)

• Why won't it compile? ActiveLecture.org
• Remedy:

  static <T extends Comparable<? super T>> T max(List<T> lst)

Moral

• The designers of Java generics wanted
  • Safe collections
  • Variance (to support OO collections)
  • Erasure (to support legacy APIs)
  • Simplicity
• They got three out of four
• Language design means making tradeoffs
• They could have gotten a better set of three
• Short-term legacy doesn't pay in the long term

  “A moment of convenience; a lifetime of regret”