You should familiarize yourself with C++ and
templates to get the most out of this writeup.
Generic Java, or GJ, or JSR-014 is the proposed extension to Java
to include templates (parametric polymorphism, which I shorten to paramorphism) ala C++ with some
nifty new features. Generic Java is currently a prototype that
compiles Java bytecode compatible with Java 1.3 and up.
A Brief History
In 1997, a team of programmers from the University of Glasgow,
including Martin Odersky and Phil Wadler designed an extension
to Java for templates called Pizza (which itself was a spinoff
of the EspressoGrinder project). Pizza dabbled not only with
the idea of paramorphism, but also with the idea of
algebraic types, that is classes generated at compile time
using case statements to further refine the parent class. Think
of it as a class definition scattered about in different places
of your source code, an implicit class definition. Pizza was
also capable of producing plain Java code with all template
references removed to be compiled later with regular Java classes.
Out of this grew the programming language GJ (Generic Java),
which removed the concept of algebraic types and refined the
concept of f-bounded paramorphism.
Sun Microsystems selected this language as the candidate
for the new compiler that will hopefully become standard in
JDK 1.5.
An Example of GJ
import java.io.*;
public class Stack<A> {
public Node<A> top;
private class Node<A> extends Object {
public A value;
public Node<A> previous;
public Node (A value) {
this.value = value;
this.previous = null;
}
} // StackNode
public Stack () {
}
public boolean isEmpty () {
return (top == null);
}
public void push (A value) {
if (isEmpty()) {
top = new Node<A> (value);
}
else {
Node<A> newNode = new Node<A> (value);
newNode.previous = top;
top = newNode;
}
}
public A getTop () throws StackEmptyException {
if (isEmpty())
throw new StackEmptyException ();
return top.value;
}
public A pop () throws StackEmptyException {
A x;
if (isEmpty())
throw new StackEmptyException ();
x = top.value;
top = top.previous;
return x;
}
public Stack<A> reverse () {
Stack<A> newStack = new Stack<A> ();
if (isEmpty())
return newStack;
Node<A> currentNode = top;
while (currentNode != null) {
newStack.push (currentNode.value);
currentNode = currentNode.previous;
}
return newStack;
}
public void print (PrintStream ps) {
Stack<A> reverseStack = reverse ();
System.out.print ("Result(s): ");
if (reverseStack.isEmpty()) {
System.out.println ("");
return;
}
StackNode currentNode = reverseStack.top;
System.out.println (currentNode.value.toString());
while (currentNode.next != null) {
currentNode = currentNode.next;
System.out.println (" " + currentNode.value.toString());
}
}
public void println (PrintStream ps) {
print (ps);
}
} // Stack
Notice :
- The constructor signature does not refer to the type parameter "A".
It doesn't need to. But when one creates a new Stack, he must supply a
concrete parameter, unless that constructor call is itself contained
within a paramorphic class referring to A as a type parameter as well.
- At no point is an A constructor called. The type of A has to be
known in order to have its constructor called. All constructors have an A
passed to them externally.
Differences Between Generic Java and C++
The first notable difference between GJ and C++ is that all
parametric polymorphic classes are typesafe. Many programmers
opposing templates (as far as C++ is concerned) often state
that templates are nothing more than glorified macros that
can lead to runtime errors due to passing a value of the wrong
type to a template-clad class. This is largely true for C++,
yet not for Generic Java. Generic Java gets around this problem
in three ways.
- Template-clad classes cannot instantiate any objects
matching the parameter class, let's say "A", unless given an appropriate
constructor class, that is, a class with a static method
that returns a new object of type A.
- The GJ compiler checks that each object passed to the
template-clad class matches the type parameter at compile-time.
- And lastly, the GJ compiler, removes all type parameter references
from the bytecode, instead replacing them with either Object,
or an appropriate interface name. So the compiled version of a
parametric polymorphic class is identical to the version that uses
Object casts (or casts to an interface). Any violation of casting
rules is caught at runtime.
The second notable difference between GJ and C++ is that
one cannot use literals as parameters to a class, that is
one cannot create a Vector<ElementType,3> to specify
a 3 dimensional Vector.
Common Pitfalls and Shortcomings of GJ
One less visible pitfall or trap that I have fallen into
in the past is overlooking which classes are inheriting
type parameters. Multiple inheritance is not allowed in Java,
even when: a) the inherited class is inherited as a type parameter
and when b) there is a compelling reason to want to inherit two
or more type parameters via multiple inheritance.
public interface Ring <A,(+),(-),(*),(0)>
extends CommutativeGroup <A,(+),(-),(0)>,
SemiGroup <A,(*)> {
}
public interface CommutativeGroup <A,(+),(/),(1)>
extends CommutativeGroupoid <A,(+)>,
Group <A,(+),(-),(1)> {
}
public interface SemiGroup <A,(+)>
extends Groupoid <A,(+)> {
}
Look carefully at the definition for Ring, and it's easily deduced
that Ring extends both Groupoid <A,(+)> and Groupoid <A,(*)>.
Okay not so easy. The ()'s are just there to mimic "
big-o-plus",
meaning (+) and (*) may not be the normal + and * learned in grade school.
Neat Things That GJ Does
Type Erasure
Decompiling the class produced by GJ with JAD produces :
public class Stack {
private class Node {
public Object value;
public Node previous;
public Node(Object obj) {
value = obj;
previous = null;
}
}
public Node top;
public Stack() {
}
public boolean isEmpty() {
return top == null;
}
public void push(Object obj) {
if(isEmpty()) {
top = new Node(obj);
} else {
Node node = new Node(obj);
node.previous = top;
top = node;
}
}
public Object getTop() throws StackEmptyException {
if(isEmpty()) {
throw new StackEmptyException();
} else {
return top.value;
}
}
public Object pop() throws StackEmptyException {
if(isEmpty()) {
throw new StackEmptyException();
} else {
Object obj = top.value;
top = top.previous;
return obj;
}
}
public Stack reverse() {
Stack stack = new Stack();
if(isEmpty()) {
return stack;
}
for(Node node = top; node != null; node = node.previous) {
stack.push(node.value);
}
return stack;
}
}
Notice that all the A's have been replaced by Object's. If A had extended an
interface type like Comparable, then the Object's would be Comparable's.
This is equivalent to using Object casting as a means of genericity (a staple
in Java programming).
F-Bounded Paramorphism
Sometimes we want to restrict the resulting type returned by methods defined in a class to a specific hierarchy. Let's say we have a group of classes that are Number-like, that is classes like Real, Fraction, Complex, etc. If we define a class Number like so:
public interface Number {
Number add (Number x);
Number subtract (Number x);
Number multiply (Number x);
Number divide (Number x);
}
and then define Real, Fraction and Complex as extensions of Number, then the result of any arithmetic method between two objects of the same type will be Number. But it is not necessarily true that all extensions of Number are compatible with each other. What we want to do in this case is define Number like so:
public interface Number<T> {
T add (T x);
T subtract (T x);
T multiply (T x);
T divide (T x);
}
and then define say Complex as:
public class Complex implements Number<Complex> {
public Complex add (Complex x) { ... }
public Complex subtract (Complex x) { ... }
public Complex multiply (Complex x) { ... }
public Complex divide (Complex x) { ... }
}
Note that Complex is defined as an extension of Number<Complex>. What we've done here is ensure that any result of any arithmetic method defined by Complex will also result in a Complex number as well.
Type Signatures In Bytecode
Just because GJ removes type information from the compiled class does not
mean this information is lost permanently. If JAD were designed differently,
it could regenerate all the type references within Stack by using the type
signature included in the bytecode.
The standard Java type signatures use L to adorn typenames, and T to adorn
type parameters. All the type parameters are in class signature. A standard
Java class loader would ignore everything after Stack within the <>'s.