Outline
  
  | 
     A problem with types.
     Generics
      
       Basics 
       Implementation via erasure.
       Properties
       Interfaces
     Polymorphism
     |   | 
  
Remember This?
class ArrayClass {
  ArrayClass(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.
  }
  
Monotyped Classess
  
  -  Arrays can (should be able to) store more than integer values.
    
  
-  A class that works in one case is nice, but a class that works in many
  cases is nicer.
    
    -  The more cases, the nicer it is.
    
-  Assuming more cases don’t cost too much extra.
    
 
-  How can we get a nicer, a more generally applicable, class?
  
Not This Way
class StringArrayClass {
  String get(int i) { ... }
  void put(int i, String v) { ... }
  }
class PointArrayClass {
  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 Tis a type variable.class TArrayClass
  void put(int i, T v) { ... }
  T get(int i) {...}
TypeVariable T = String
TArrayClass strings = new TArrayClass(10)
strings.put(0, "hello")
String str = strings.get(0)
T = Point
TArrayClass points = new TArrayClass(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 ArrayClass<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).
ArrayClass<String> strings = 
  new ArrayClass<String>(10) 
 
     
    -  This can get verbose, as with C++. 
    
-  And there’s no typedef in Java.
    
 
-  Except when it doesn’t
    
    -  ArrayClasswithout the type parameter is a valid class name.
 import utils.ArrayClass; 
  
     
Using Type Variables
  
  -  Inside a generic class, type variables may be used as types.
Class ArrayClass<T>
  void put(int i, T t) { ... }
  T get(int i) { ... }
  private ArrayList<T> elts = 
    new ArrayList<T>()
 
   
-  Except when they can’t.
  
Type Variables vs new
  
  -  Type-variable instances 
can’t be created via new.class ArrayClass<T>
  private int N = 10
  private T elements[] = new T[N]
 
 
   
-  Inside a generic class, fall back to ugly casts to and from objects.
class ArrayClass<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
  
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:
    
    -  Remove the type-variable declarations (erasure).
    
-  Replace each type variable with its most general class.
    
-  Add casts as required to maintain type correctness
    
 
Erasure Example.
  
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....
  
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, Tis replaced byObject, 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 withstatic?class SharedMailbox<T>
  private static Tslot = 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 ArrayClass<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 CustomArrayClass<t>
implements ArrayClass<t> { ... }
class IntArrayClass
implements ArrayClass<Integer> { ... }
class BinaryArrayClass<t1, t2>
implements ArrayClass<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
  
  
  -  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.
  
- 
  A Comparative Study of Language Support for Generic Programming by
  Ronald Garcia, Jaakko Järvi, Andrew Lumsdaine, Jeremy
  Siek, and Jeremiah Willcock in Proceedings of the Conference on
  Object-Oriented Programming Languages, Systems, and Applications (OOPSLA),
  2003.
  
-  A Comparative Evaluation of Generic Programming in Java and C++ by
  Hossein Saiedian and Steve Hill in Software—Practice and
  Experience, February, 2003.
  
 
Credits
  
  
  | This page last modified on 2011 February 1. | 
      |