Data Structures & Algorithms Lecture Notes

15 September 2009 • Generics

---

Outline

Polymorphism Generics Basics Implementation via erasure. Properties Wildcards Bounded type variables.

Polymorphism

• Polymorphism is abstraction over types.

  • When types don’t matter, they shouldn’t clog up the code.

• Systems exploiting polymorphism are smaller, simpler (mostly), and more flexible.

  • This assumes polymorphism is well-integrated into the language.

  • As opposed to being bolted on after the fact.

Object Polymorphism

• Object polymorphism is a variation on subtype polymorphism.

  • Every class is a descendant of Object.

  class stack
    void push(Object o) { ... }
    Object pop() { ... }
  

• Object polymorphism is the limit to “types don’t matter”.

  • Except that some times, in some places, types do matter.

Problems.

• Object polymorphism is cumbersome.

  • Casting’s required when types do matter.

  Stack stk = new Stack()
  stk.push("hello")
  String str = (String) stk.pop()
  

• Object polymorphism is run-time explody.

  stk.push(1)
  String str = (String) stk.pop()
  

Problems..

• Not to pick on Object polymorphism exclusively though.

  Stack stk = new Stack()
  stk.push(new Spot())
  Drip drip = (Drip) stk.pop()  // boom!
  

• Down-casting always has the potential to fail at run-time.

  • Unless precautions are taken to prevent it.

  • Generics help simplify the precautions.

Object-Polymorphism Fixes

• Specialization is one solution to the object-polymorphism problem.

  class StringStack
    void push(String str) { ... }
    String pop() { ... }
  
  class DripStack
    void push(Drip drip) { ... }
    Drip pop() { ... }
  
  // and so on.

• No more casting, and compile-time type checking.

Wishful Thinking

• Specialization doesn’t scale; it requires polynomially many implementations.

• Can specialization be simplified or automated?

  • How about using some weird thing like type variables?

• A type variable is a variable capable of holding a type instead of a value.

  • The type variable is an attempt to abstract the different but related types in specialized classes.

Type-Variable Example

• Suppose T is a type variable.

  class TStack
    void push(T t) { ... }
    T pop() {...}
  
  TypeVariable T = String
  TStack stringStk = new TStack()
  stringStk.push("hello")
  String str = stringStk.pop()
  
  T = Drip
  TStack dripStk = new TStack()
  dripStk.push(new Drip())
  Drip drip = dripStk.pop()
  

Generics

• Generic types (or just generics) is one way to provide type variables.

  • Generics were bolted on to Java 1.5.

  • And yes, there are compatibility problems with earlier Java code.

• Java generics is different from C++ and C# generics.

  • Different in both semantics and implementation.

Generic Type Variables

• Type variables (or type parameters) appear on the other side of the class name enclosed in angle brackets.

  class Stack<T> { ... }
  
  class Map<K, V> { ... }
  

  • Type variables are any legal Java variable identifier.

  • Convention dictates upper-case single letter mnemonic type-variable names.

Generic Class Names

• A generic class’s name includes the type-variable definitions (and angle brackets).

  Stack<Blob> blobStack = new Stack<Blob>()
  

  • This can get verbose, as with C++.

  • And there’s no typedef in Java.

• Except when it doesn’t

  • “Stack” with no type variables is a valid class name.

  import utils.Stack;
  

Using Type Variables

• Inside a generic class, type variables may be used as types.

  • Except when they can’t.

  Class Stack<T>
  
    private T top = null
    private ArrayList<T> elts = 
      new ArrayList<T>()
  
    void push(T t) { ... }
  
    T pop() { ... }
  

Type Variables vs new

• Type-variable instances can’t be created via new.

  class Stack<T>
  
    private final int max = 10
    private T elements[] = new T[max]

• Inside a generic class, fall back to object polymorphism.

  class Stack<T>
    private final int max = 10
    private Object stk[] = new Object[max]
    T pop() { return (T) stk[--top] }

Type Variables vs static

• Type variables can’t appear in class-feature (that is, static) declarations.

  class SharedMailbox<T>
  
    private static T slot = null
  
    public static T pickUp()
      { return slot }
  
    public static deliver(T t)
      { slot = t }
  
  

Type Variables vs Primitives

• Type variables cannot be associated with primitive types.

  Stack<int> intStack = new Stack<int>()
  

• Autoboxing does not apply to type-variable association.

  • You have to do it yourself; it works after that.

    Stack<Integer> integerStack = 
      new Stack<Integer>()
    integerStack.push(1)
    int i = integerStack.pop()
    

Implementing Generics

• These restrictions are unfortunate. Why are they necessary?

  • And there are more restrictions to come.

• Even obeying the restrictions, it’s easy to fall off the straight and narrow generics path.

  • Why is that? and How do you get back on the path?

• Answering these questions requires understanding how generics is implemented in Java.

History

• Adding generics to Java was hampered by

  • The late start.

    • Around 1999, but any design not available at the beginning is too late.

  • The need for backward JVM compatibility.

    • Which was eventually abandoned after it irrecoverably distorted the design.

Erasure

• Java generics is implemented by a technique called erasure.

• Erasure has three steps:

  1. Remove the type-variable declarations (erasure).

  2. Replace each type variable with its most general class.

  3. Add casts as required to maintain type correctness

Erasure Example.

• Given

  class Mailbox<T>
    private T slot
    void put(T t) { slot = t }
    T get() { return slot }
  
  Mailbox<Letter> mailBox = 
    new Mailbox<Letter>()
  mailBox.put(new Letter())
  Letter letter = mailBox.get()
  

  Step 1: erase type-variable declarations

Erasure Example..

class Mailbox<T>
  private T slot
  void put(T t) { slot = t }
  T get() { return slot }

Mailbox<Letter> mailBox = 
  new Mailbox<Letter>()
mailBox.put(new Letter())
Letter letter = mailBox.get()

Step 2: Replace type variables with their most general (most ancestral) type.

Erasure Example...

class Mailbox
  private T Object slot
  void put(T Object t) { slot = t }
  T Object get() { return slot }

Mailbox mailBox = 
  new Mailbox()
mailBox.put(new Letter())
Letter letter = mailBox.get()

Step 3: Cast to maintain type correctness.

Erasure Example....

class Mailbox
  private Object slot
  void put(Object t) { slot = t }
  Object get() { return slot }

Mailbox mailBox = 
  new Mailbox()
mailBox.put(new Letter())
Letter letter = (Letter) mailBox.get()

Ta da! No generics.

Observations

• The Step 3 casts will not to explode at run-time.

  • The compiler verifies correctly typed values coming in.

• The resulting bytecode is indistinguishable from similarly structured non-erased Java code.

  • In other words, the bytecode won’t run faster.

• Actual erasure is much more tricky.

Repercussions

• Understanding how generics are implemented via erasure helps explain the previous restrictions.

• Type-variable instances may not be created via new.

  class MailBox<T>
    // Start with a default letter.
    private T mailBox = new T()
  

• Why not?

Type Variables vs new

• By Step 2, T is replaced by Object, which isn’t useful.

  class MailBox
    // Start with a default letter.
    private Object mailBox = new Object()
  

• Type variables cannot be associated with primitive types.

  Stack<int> intStack = new Stack<int>()
  

  Why not?

Type Variables vs Primitives

• Again, Step 2 replaces T by it’s most distant ancestor.

  • But primitives aren’t part of the type hierarchy.

• What is the relation between generic classes with related type variables?

  class Blob { ... }
  class Spot extends Blob { ... }
  
  Mailbox<Spot> spotBox = new Mailbox<Spot>
  Mailbox<Blob> blobBox = spotBox  // ???
  

Generics vs. Inheritance

• Step 1 erases both mailbox generic classes to Mailbox.

  Mailbox<Spot> spotBox = new Mailbox<Spot>
  Mailbox<Blob> blobBox = spotBox  // ???
  

  So the assignment should be fine and dandy.

• True, it should be. But the compiler flags it as being illegal.

  • Why is that?

Violating Run-time Guarantees

• Consider

  class Blob { ... }
  class Spot extends Blob { ... }
  
  Mailbox<Spot> spotBox = new Mailbox<Spot>
  Mailbox<Blob> blobBox = spotBox
  
  blobBox.put(new Blob)
  Spot spot = spotBox.get()  // boom!
  

• Aliasing spotBox as blobBox can lead to run-time casting exceptions, violating the generic guarantee.

Example

Erasure Strikes Again

• Erasure makes all generic-class variants of class C be class C eventually. C is known as the raw type.

  

• Class files contain almost none of the extra information generic class definitions can provide.

  • All in service to backwards compatability.

Type (In)Compatability

• Erasure and run-time type safety combine to make

  any generic variant of class C type incompatible with every different generic variant of C.

• For example, write a method that accepts an arbitrary mailbox as a parameter.

  • Does

    void lock(Mailbox<Object> mb) { ... }
    

    do it?

Polymorphism Exiled

• The method

  void lock(Mailbox<Object> mb) { ... }
  

  only accepts mailboxes containing Object instances.

  • Using any other Mailbox variant causes a compile time error.

• We’ve moved from specialization to generics and back to specialization again.

  • Can nothing save us?

Wildcards

• The wildcard ? indicates that

  • The associated actual type is minimally knowable.

  • The associated generic reference is readable but not writeable.

• The method

  void lock(Mailbox<?> mb) { ... }
  

  does what we want, as long as lock() doesn’t try to write polymorphic references into mb.

Wildcard Properties

• Polymorphic references are Object instances.

  void lock(Mailbox<?> mb)
    Object o = mb.get() // Ok
  

• Read-only polymorphic references protect run-time type safety at compile time.

  void lock(Mailbox<?> mb)
    mb.put(new Blob()) // Compile-time error
    mb.setOwner("Trollope") // Ok
  

  • Non-polymorphic references are writeable.

Generics Hierarchy

When Types Matter

• Write a method acceptimg only blobish mailboxes.

  • This

    void lock(Mailbox<Blob> mb) { ... }
    

    doesn’t go far enough and this

    void lock(Mailbox<?> mb) { ... }
    

    goes too far.

• What can be done?

Bounded Wildcards

• A bounded wildcard is ranges over a subtree of the class hierarchy.

  • The root of the subhierarchy is the bound.

• The bounded-wildcard syntax abuses the extends keyword:

  void lock(Mailbox<? extends Blob> mb) {…}
  

  • The bound can be a class or an interface.

Bounded Wildcard Properties

• Bounding wildcards doesn’t change its properties much.

• Polymorphic references are bound-type instances.

  void lock(Mailbox<? extends Blob> mb)
    Blob blob = mb.get() // Ok
  

  • The bound represents minimal type knowledge.

• Polymorphic references are still read-only.

• Non-polymorphic references are still writeable.

Bounded Type Variables

• As with wildcards, so with type variables.

  class Mailbox<T extends Letter> { ... }
  

  • T’s most general (ancestral) type is Letter.

  

Multiple Bounds

• A bound can comprise several classes.

  class Mailbox<
    T extends Letter & Refundable> { ... }
  

  • T must satisfy (extend or implement) all bounds.

  

Summary

• Generics implement parametric polymorphism.

• Generics allows ahierarchial relations in polymorphism.

  • As opposed to subtype polymorphism.

  • Although generics can use bounds to exploit class hierarchy.

• Java implements generics with erasure.

References

• Generics in the Java Programming Language by Gilad Bracha, 2004 July 5.

• Chapter 5, Generics, Effective Java by Joshua Bloch, second edition, Prentice Hall, 2008.

• Angela Langer’s Java generics FAQ.

Credits

• national_generic_peas by rstinnett under an AT CC license.