Data Structures & Algorithms Lecture Notes

24 September 2010 • Generics in Practice

---

Outline

• Polymorphism
• Generics
• 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.
  • Eliminate code duplication.
  • Amortize work over more clients.

Generics

• Generic types (or just generics) is one way to provide type variables.
  • Generics were bolted on to Java 1.5.
• 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.
  • Usually 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() { ... }
  

Implementing Generics via 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 t }
  
  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 t }

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 t }

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 t }

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.

Generics vs new

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

  $ cat MailBox.java
  class MailBox<T> {
    private T mailBox = new T();
    }
  
  $ javac -Xlint MailBox.java
  MailBox.java:2: unexpected type
  found   : type parameter T
  required: class
    private T mailBox = new T();
                            ^
  1 error
  
  $ 

• Creating a most-general class instance usually isn’t what’s wanted.

Generics vs Primitives

• Type variables cannot be associated with primitive types.

  $ cat MailBox.java
  class MailBox<T> { /* blah blah blah */ }
  
  class test { private MailBox<int> mailBox = new MailBox<int>(); }
  
  $ javac -Xlint MailBox.java
  MailBox.java:6: unexpected type
  found   : int
  required: reference
    private MailBox<int> mailBox = new MailBox<int>();
                    ^
  MailBox.java:6: unexpected type
  found   : int
  required: reference
    private MailBox<int> mailBox = new MailBox<int>();
                                               ^
  2 errors
  
  $ 

• Primitive types have no most general reference-type ancestor.

Generics vs static

• Type parameters can’t be used in static fields.

  $ cat MailBox.java
  import java.util.ArrayList;
  
  class MailBox<T> {
    static private T mailBoxs = new ArrayList<T>();
    }
  
  $ javac -Xlint MailBox.java
  MailBox.java:4: non-static class T cannot be referenced from a static context
    static private T mailBoxs = new ArrayList<T>();
                   ^
  MailBox.java:4: non-static class T cannot be referenced from a static context
    static private T mailBoxs = new ArrayList<T>();
                                              ^
  2 errors
  
  $ 

• Type parameters are a per-instance feature, not per class.

Curious Beasts

• Here’s a class:

  public class
  MailBox<T extends Number> {
  
    public void 
    copy(MailBox<T extends Integer> v) { 
      // blah blah blah 
      }
  
    // blah blah blah
    }
  

• What’s going on? What does this stuff mean?

Among Generic Classes

• 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  // ???
  

• Is this legal?

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 compatibility.

Type (In)Compatibility

• 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 accepting 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.

---

This page last modified on 22 September 2010.