Data Structures & Algorithms Lecture Notes

17 September 2010 • Generics

---

Outline

A problem with types. Generics Basics Implementation via erasure. Properties Interfaces Polymorphism

Remember This?

class ArrayADT {

  ArrayADT(int n) { ... }
  void resize(int n) { ... }

  int get(int i) { ... }
  int size() { ... }

  void put(int i, int v) { ... }
  void swap(int i, int j) { ... }

  // and so on.
  }

• What's wrong with it?

Monotyped ADTs

• Arrays can (should be able to) store more than integer values.
  • String [], Point [], …
• Having an ADT that works in one case is nice, but having one that works in many cases is nicer.
  • The more cases, the nicer it is.
  • Assuming we’re not paying to much for the extra.
• How can we get a nicer, a more generally applicable, ADT?

Not This Way

class StringArrayADT {

  String get(int i) { ... }
  void put(int i, String v) { ... }

  }

class PointArrayADT {

  Point get(int i) { ... }
  void put(int i, Point v) { ... }

  }

• This works, but not well. Why?

Type Specialization

• This kind of type specialization is a particularly bad approach.
  • Implementation effort grows exponentially.
    • And no, inheritance doesn’t help.
  • Lots of redundant code and code bloat.
  • A complex software management and maintence problem.

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 TArrayADT
    void put(int i, T v) { ... }
    T get(int i) {...}
  
  TypeVariable T = String
  TArrayADT strings = new TArrayADT(10)
  strings.put(0, "hello")
  String str = strings.get(0)
  
  T = Point
  TArrayADT points = new TArrayADT(20)
  points.put(3, new Point())
  Point p = points.get(3)
  

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 ArrayADT<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).

  ArrayADT<String> strings = new ArrayADT<String>(10)
  

  • This can get verbose, as with C++.
  • And there’s no typedef in Java.
• Except when it doesn’t
  • “ArrayADT” with no type variables is a valid class name.

  import utils.ArrayADT;
  

Using Type Variables

• Inside a generic class, type variables may be used as types.
  • Except when they can’t.

  Class ArrayADT<T>
  
    void put(int i, T t) { ... }
  
    T get(int i) { ... }
  
    private ArrayList<T> elts = 
      new ArrayList<T>()
  

Type Variables vs new

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

  class ArrayADT<T>
    private int N = 10
    private T elements[] = new T[max]

• Inside a generic class, fall back to ugly casts to and from objects.

  class ArrayADT<T>
    private int N = 10
    private Object elements[] = new Object[N]
    T get(int i) { return (T) elements[i] }
    void put(int i, T v) { elements[i] = v }

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 }
  
  

Implementing Generics

• These restrictions are unfortunate. Why are they necessary?
  • And those aren't the only restrictions.
• 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.

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 Object (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()
  

• What about static? Why can’t type variables be used with static?

  class SharedMailbox<T>
    private static T slot = null

Interfaces

• What about interfaces? Do they get to play with generics too?
  • But does that even make sense?
  • What does a generic interface mean?

Generic Interfaces

• Interfaces follow the same rules (more or less) as classes.

  interface ArrayADT<T>{
  
    public T get(int i);
    public void put(int i, T v);
  
    // and so on.
    }

Implementing Generic Interfaces

• Implementing classes must match the interface's type variables one way or another.

  class CustomArrayADT<t>
  implements ArrayADT<t> { ... }
  
  class IntArrayADT
  implements ArrayADT<Integer> { ... }
  
  class BinaryArrayADT<t1, t2>
  implements ArrayADT<t1> { ... }
  

• It gets more complicated, particularly with erasure, but this is enough for us.

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.
• Generics is an example of parametric polymorphism.

Summary

• Generics implement parametric polymorphism.
• Generics allows ahierarchial relations in polymorphism.
  • As opposed to inheritance.
• Java generics provides run-time safe casting.
• Java implements generics with erasure.
  • Which causes subtle (and not so subtle) problems.

References

Credits

• national_generic_peas by rstinnett under a Creative Commons AT license.

---

This page last modified on 28 January 2010.