10-8-04 Templates vs. Generics

Note: an earlier version of this article was posted briefly, then a reader pointed something out that required rewriting and which lead to other insights, so I took the article down and rewrote it. So you might have seen the earlier version before it disappeared. I have also removed comments that no longer apply to the rewritten version of this article.

This article will be part of my presentation at the Colorado Software Summit.

New Generics FAQ

But first, an announcement. If you still think Java Generics are trivial, a new resource has just been published that plumbs the depths of Java Generics, and may just convince you otherwise: Angelika Langer's Java Generics FAQ. You can find out more about Angelika on her web site, but she's been a long-time member of the C++ Standards Committee and has been writing and teaching the tricky parts of both C++ and Java for quite awhile, so she knows her stuff. And she's been researching Java Generics for at least 1.5 years, which is where this FAQ has come from.

Here's are some puzzles adapted from the FAQ. The first one is rather mindblowing:

import java.util.*;

public class Puzzles {
  public static <T> void fill(T[] array, T elem) {
    for(int i = 0; i < array.length; i++)
      array[i] = elem;
  }
  public static void main(String[] args) {
    fill(new String[5], "A string");
    fill(new String[5], 100); // What the ...???

    // Won't compile:
    // Class<String> cs = "abc".getClass();

    Object obj = new LinkedList<Long>();
    // Won't compile:
    // System.out.println(obj instanceof List<Long>);
  }
}

Yes, the calls to fill() compile and represent conformant generic code (an exception is generated at runtime, so it's an example of where generics do not produce static type safety). You'll have to look it up in the FAQ if you want to know the answer.

The example

The example that I will start with is adapted from something I wrote for Thinking in C++, Volume 2. In this article, I'll look at the C++ version of the example and then see what it looks like in Java. In this case, the Java version happens to be able to use an interface (Iterable) and so things work out pretty well. However, I will then look at a second example where no such interface happens to be used, and show how Java's lack of latent typing prevents you from writing truly "generic" code. Finally, I'll show a way around the lack of latent typing in Java by introducing more code in the form of the Adapter design pattern.

What I found in modifying the C++ example and translating it to Java was surprising. As far as generics go, it does in fact support my thesis that erasure limits the expressivity of generics. What is surprising is that I was expecting the usual result that C++ code is succinct (although arguably more complex, and certainly more difficult to get working right) while the Java code tends to be long and rambling. But in this case, the Java code is small and elegant, and far less verbose than the C++ code, so I found the Java result quite delightful. Alas, generics had nothing to do with this succinctness – it was actually reflection and varargs that were responsible. And so the power of reflection continues to be one of the most interesting features of Java, even though its runtime uncertainty is at odds with the Java Generics goal of static type safety.

The example is to create an apply() function that will apply any method to every object in a sequence. This is somewhat similar to the idea of closures (without the ability to implicitly capture context) that Martin Fowler recently explained in Ruby, and a number of other writers provided solutions in other languages (see links from Martin's entry).

The only constraint on the sequence is that it have (in the C++ case) a begin() method that produces an iterator. While this is the way that the C++ STL collections are defined to work, any class that produces an iterator this way will work with the apply() function. This is an important point – the C++ code defined here is truly "generic" because of latent typing. It can be applied to any sequence that satisfies the protocol, without requiring that the sequence be of any particular class or implement any particular interface. Because of this, one piece of code can be applied across more different types, which, I postulate, is the core intent of parameterized types.

Here is the C++ code, which is modified from the C05:ApplySequence.h example in Thinking in C++, Volume 2. It is presented as a single file to make it easier to compile and experiment with (you can download the file here):

// This part represents the "apply" library:

// const, 0 arguments, any type of return value. The only
// "bound" is that Seq must produce an iterator via a
// begin() method, that produces pointers to objects:
template<class Seq, class T, class R>
void apply(Seq& sq, R (T::*f)() const) {
  typename Seq::iterator it = sq.begin();
  while(it != sq.end())
    ((*it++)->*f)();
}

// const, 1 argument, any type of return value:
template<class Seq, class T, class R, class A>
void apply(Seq& sq, R(T::*f)(A) const, A a) {
  typename Seq::iterator it = sq.begin();
  while(it != sq.end())
    ((*it++)->*f)(a);
}

// const, 2 arguments, any type of return value:
template<class Seq, class T, class R,
         class A1, class A2>
void apply(Seq& sq, R(T::*f)(A1, A2) const,
    A1 a1, A2 a2) {
  typename Seq::iterator it = sq.begin();
  while(it != sq.end())
    ((*it++)->*f)(a1, a2);
}

// Non-const, 0 arguments, any type of return value:
template<class Seq, class T, class R>
void apply(Seq& sq, R (T::*f)()) {
  typename Seq::iterator it = sq.begin();
  while(it != sq.end())
    ((*it++)->*f)();
}

// Non-const, 1 argument, any type of return value:
template<class Seq, class T, class R, class A>
void apply(Seq& sq, R(T::*f)(A), A a) {
  typename Seq::iterator it = sq.begin();
  while(it != sq.end())
    ((*it++)->*f)(a);
}

// Non-const, 2 arguments, any type of return value:
template<class Seq, class T, class R,
         class A1, class A2>
void apply(Seq& sq, R(T::*f)(A1, A2),
    A1 a1, A2 a2) {
  typename Seq::iterator it = sq.begin();
  while(it != sq.end())
    ((*it++)->*f)(a1, a2);
}
// Etc., to handle maximum likely arguments

// The rest of the code uses the "apply" library:

#include<iostream>
using namespace std;

class Shape {
public:
  void rotate() { cout << (int)this << " rotate" << endl; }
  void resize(int newSize) {
    cout << (int)this << " resize " << newSize << endl;
  }
};

class Square : public Shape {};

#include <vector>

// A vector that fills itself:
template<class T> class FilledList : public vector<T*> {
public:
  FilledList(int size) {
    for(int i = 0; i < size; i++)
      // The existence of the default constructor
      // is checked at compile time:
      push_back(new T());
  }
};

int main() {
  vector<Shape*> shapes;
  for(int i = 0; i < 10; i++)
    shapes.push_back(new Shape());
  apply(shapes, &Shape::rotate);
  apply(shapes, &Shape::resize, 5);
  vector<Square*> squares;
  for(int i = 0; i < 10; i++)
    squares.push_back(new Square());
  apply(squares, &Shape::rotate);
  apply(squares, &Shape::resize, 5);

  FilledList<Shape> shapes2(10);
  FilledList<Square> squares2(10);
  apply(shapes2, &Shape::rotate);
  apply(squares2, &Shape::rotate);
  // (I'm using the "end-of-program-garbage-collection"
  // idiom here :-)
}

The first section of the code represents the reusable template library. You can see that it is a series of overloaded versions of the apply() function. The reason this is necessary is because there are variations in the use of apply() that I could not figure out how to encapsulate in a single template. I asked Andrei Alexandrescu whether there's a way to do this, and he replied:

The trick is to have apply() take a functor with zero parameters (which makes apply() become really for_each()), and then construct the functor outside of apply with the desired number of parameters.

Writing a functor that accomodates pointers to member functions and multiple parameters is tricky, but feasible in less-than ideal ways. (Multiple parameters kill you). See the Functors chapters in Modern C++ Design for considerations about doing that.

Perhaps one of my readers with their brain currently more in C++ and less in Java (where mine has been) can rewrite the example in this way.

In the above code, there's an overloaded apply() for each case of the member function being called having zero, one and two arguments, and const and non-const member functions. To be complete, you'd probably want to keep going to at least six or eight arguments.

So the C++ version is verbose, which you can justify if you're creating it as a library – you solve the problem once, and in the future all you have to do is include the header file and call apply(). It's also very efficient at runtime. However, the verbosity reduces the likelihood that you'll just dash off this code, whereas we'll see that the Java solution (again to my surprise) encourages such coding.

The apply() functions also require C++ pointer-to-member syntax, which is the way that you pass around the identity of a member function within a class that you'd like to call. In the apply() function, pointer to member is passed as R (T::*f)(), where f is the identifier and R is the parameterized return value. The call looks like this: ((*it++)->*f)(), which dereferences the iterator, then dereferences the pointer to member function in order to call it with the resulting object pointer. At the call site, you specify the address of the member function you wish to call using the relatively straightforward (for C++, anyway) &Shape::rotate.

Once the apply() library has been created, it can be used with a typical list of objects. Here, I create Shape classes, and to further the example, a generic collection called FilledList that can fill itself with a specified quantity of any type you desire. The constraint for FilledList is that the type parameter must have a default (no- arg) constructor, but this is checked at compile time so you get type safety without erasure.

In main(), various collections are created and filled, and the apply() function is applied to them. The resulting syntax is reasonably direct, and all operations are checked at compile time so the results are very efficient.

One important issue to notice: C++ templates do not need wildcards. Because of latent typing you don't need to care whether a vector<Square> behaves as if it subclasses a vector<Shape>. The only thing the compiler cares about is whether the operations can be performed successfully.

The Java Version

The first thing I discovered when translating the example to Java is that this is a situation where interfaces don't seem to fit. I want to be able to apply any method to a collection of objects, and interfaces constrain you too much to be able to describe "any method." C# has delgates which can be used for this purpose. C++ has pointers to members, shown above. How do you do this in Java? The solution seems to be reflection ^[1] (see the Wiki feedback page for one alternative).

As I mentioned at the beginning of this article, the syntax using reflection is far more elegant than I imagined, and with varargs all of the overloaded apply() functions that we saw in C++ collapse into a single method (you can download the file here):

//: cY:Apply.java
import java.util.*;
import java.lang.reflect.*;

public class Apply {
  public static <T, S extends Iterable<? extends T>>
  void apply(S seq, Method f, Object... args) {
    try {
      for(T t: seq)
        f.invoke(t, args);
    } catch(Exception e) {
      // Failures are programmer errors
      throw new RuntimeException(e);
    }
  }
}

class Shape {
  public void rotate() {
    System.out.println(this + " rotate");
  }
  public void resize(int newSize) {
    System.out.println(this + " resize " + newSize);
  }
}

class Square extends Shape {}

class FilledList<T> extends ArrayList<T> {
  public FilledList(Class<? extends T> klass, int size) {
    try {
      for(int i = 0; i < size; i++)
        add(klass.newInstance()); // Assumes default constructor
    } catch(Exception e) {
      // Failures are programmer errors
      throw new RuntimeException(e);
    }
  }
}

// A different kind of container that is Iterable
class SimpleQueue<T> implements Iterable<T> {
  private LinkedList<T> storage = new LinkedList<T>();
  public void add(T t) { storage.offer(t); }
  public T get() { return storage.poll(); }
  public Iterator<T> iterator() { return storage.iterator(); }
}

class ApplyTest {
  public static void main(String[] args) throws Exception {
    List<Shape> shapes = new ArrayList<Shape>();
    for(int i = 0; i < 10; i++)
      shapes.add(new Shape());
    Apply.apply(shapes, Shape.class.getMethod("rotate"));
    Apply.apply(shapes,
      Shape.class.getMethod("resize", int.class), 5);
    List<Square> squares = new ArrayList<Square>();
    for(int i = 0; i < 10; i++)
      squares.add(new Square());
    Apply.apply(squares, Shape.class.getMethod("rotate"));
    Apply.apply(squares,
      Shape.class.getMethod("resize", int.class), 5);

    Apply.apply(new FilledList<Shape>(Shape.class, 10),
      Shape.class.getMethod("rotate"));
    Apply.apply(new FilledList<Shape>(Square.class, 10),
      Shape.class.getMethod("rotate"));

    SimpleQueue<Shape> shapeQueue = new SimpleQueue<Shape>();
    for(int i = 0; i < 5; i++) {
      shapeQueue.add(new Shape());
      shapeQueue.add(new Square());
    }
    Apply.apply(shapeQueue, Shape.class.getMethod("rotate"));
  }
}

In Apply, we get lucky because there happens to be an Iterable interface built into Java and the Java collections library. Because of this, the apply() method can accept anything that implements the Iterable interface, which includes all the Collection classes such as List, but it can also accept anything else as long as you make it Iterable – for example, the SimpleQueue class defined above and used in main().

Exceptions are converted to RuntimeExceptions because there's not much of a way to recover from exceptions – they really do represent programmer errors in this case. However, the equivalent C++ code detects the problems at compile time.

Those who read my writings know that I do not fear dynamic behavior, and in fact believe it to be one of Java's greater strengths, so this aspect of things does not bother me. In Java, some tests do happen at runtime, and that's a good thing. Choose your battles – sometimes discovering problems at runtime is not so bad. It's a lot better than not finding them at all, or trying to track down a C++ memory leak.

Note that I had to put in bounds and wilcards in order for Apply and FilledList to be used in all desired situations. You can experiment by taking these out and you'll discover that some applications of Apply and FilledList will not work.

FilledList presents a bit of a quandary. In order for a type to be used, it must have a default (no-arg) constructor. In C++ this is checked at compile time, but Java has no way to assert such a thing at compile time, so it becomes a runtime issue. A common suggestion to ensure compile-time checking is to define a factory interface that has a method that generates objects, then FilledList would accept that interface rather than the "raw factory" of the class token. The problem with this is that all the classes you use in FilledList must then implement your factory interface. Alas, most classes are created without knowledge of your interface, and therefore do not implement it. Later, I'll show one solution using Adapters.

But the approach shown, of using a class token, is perhaps a reasonable tradeoff (at least as a first-cut solution) since it makes the use of something like FilledList just easy enough that it may be used rather than ignored. Of course, you need confidence that errors will appear early in the development process.

Note that the class token technique is recommended in the Java literature, such as Gilad Bracha's Generics in the Java Programming Language, where he notes: "It's an idiom that's used extensively in the new APIs for manipulating annotations, for example." However, I've discovered some inconsistency in people's comfort level with this technique; some people strongly prefer the factory approach, which we'll look at later.

Also, as elegant as the Java solution turns out to be, we must observe that the use of reflection (as much as it has been improved in recent versions of Java) is likely to be distinctly slower than the C++ implementation, since so much is happening at runtime. Not that this should stop you from using the solution (at least as a first cut, lest you fall sway to premature optimization) but it's certainly a distinction between the two approaches.

When you don't happen to have the right interface...

The above example benefitted because the Iterable interface was already built in, and was exactly what we needed. But what about the general case, when there isn't an interface that just happens to fit your needs, already in place?

For example, let's generalize the idea in FilledList and create a parameterized fill() method that will take a sequence and fill it using a Generator. Here's the C++ version:

#include <vector>
#include <iostream>
#include <cassert>
using namespace std;

// Because of latent typing, doesn't need an interface for A:

template<class A, class T> void fill(A& addable, int size) {
  for(int i = 0; i < size; i++)
    // Checks for default constructor at compile-time:
    addable.push_back(new T());
}

class Contract {
public:
  virtual void print() {
    cout << "Contract " << (int)this << endl;
  }
};

class TitleTransfer : public Contract {
public:
  virtual void print() {
    cout << "TitleTransfer " << (int)this << endl;
  }
};

// A different container that also has a push_back:
template<class T> class Stack {
  enum { ssize = 100 };
  T* stack[ssize];
  int top;
public:
  Stack() : top(0) {}
  void push_back(T* t) {
    assert(top < ssize);
    stack[top++] = t;
  }
  T* pop() {
    assert(top > 0);
    return stack[--top];
  }
  int size() { return top; }
};

int main() {
  typedef vector<Contract*> Contracts;
  Contracts contracts;
  fill<Contracts, Contract>(contracts, 3);
  fill<Contracts, TitleTransfer>(contracts, 2);
  Contracts::iterator it = contracts.begin();
  while(it != contracts.end())
    (*it++)->print();
  cout << "--------------" << endl;
  // Works because of latent typing:
  Stack<Contract> contractStack;
  fill<Stack<Contract>, TitleTransfer>(contractStack, 7);
  while(contractStack.size())
    contractStack.pop()->print();
}

When we convert it to Java, we run into a problem, because there is no convenient Addable interface. So instead of saying "anything that you can call add() on," you have to say "subtype of Collection." The resulting code is not particularly generic, since it must be constrained to work with Collection implementations. When I did the same thing in C++ by adding the Stack class the new class still worked with my existing template, without requiring changes to the template code (since all the template required is a push_back() method, not an interface). In Java, if I create a new class that doesn't implement Collection, my generic code won't work. Here's the translation:

//: cY:Fill.java
// Generalizing the FilledList idea
import java.util.*;
import java.lang.reflect.*;

// Doesn't work with "anything that has an add()."
// There is no "Addable" interface so we are narrowed
// to using a Collection.
// We cannot generalize using generics in this case.

public class Fill {
  public static <T> void
  fill(Collection<T> collection, Class<? extends T> classToken, int size) {
    for(int i = 0; i < size; i++)
      // Assumes default constructor:
      try {
        collection.add(classToken.newInstance());
      } catch(Exception e) {
        throw new RuntimeException(e);
      }
  }
}

class Contract {}
class TitleTransfer extends Contract {}

class FillTest {
  public static void main(String[] args) {
    List<Contract> contracts = new ArrayList<Contract>();
    Fill.fill(contracts, Contract.class, 3);
    Fill.fill(contracts, TitleTransfer.class, 2);
    for(Contract c: contracts)
      System.out.println(c);
    SimpleQueue<Contract> contractQueue = new SimpleQueue<Contract>();
    // Won't work. fill() is not generic enough:
    // Fill.fill(contractQueue, Contract.class, 3);
  }
}

This is where a parameterized type mechanism with latent typing is valuable, because you are not at the mercy of the past design decisions of any particular library creator, so you do not have to rewrite your code every time you encounter a new library that didn't take your situation into account (thus the code is truly "generic"). In the above case, since the Java designers (understandably) did not see the need for an "Addable" interface, we are constrained within the Collection hierarchy, and SimpleQueue, even though it has an add() method, will not work. Because it is thus constrained to working with Collection, the code is not particularly "generic." With latent typing, this would not be the case.

Working around the lack of latent typing

So Java Generics doesn't have latent typing, and we need something like latent typing in order to write code that can be applied across class boundaries (that is, "generic" code). Is there some way to get around this limitation?

To figure this out, I asked myself "what is latent typing accomplishing here?" It means that you are able to write code saying "I don't care what type I'm using here as long as it has these methods." In effect, latent typing creates an implicit interface containing the desired methods. So it follows that if we write the necessary interface by hand (since Java doesn't do it for us), that should solve the problem.

Writing code to produce an interface that we want from an interface that we have is an example of the Adapter design pattern. We can use adapters to adapt existing classes to produce the desired interface, with a relatively small amount of code. The solution demonstrates different ways of writing adapters, including one that is quite surprising:

//: cY:Fill2.java
// Using adapters to compensate for lack of latent typing.
import java.util.*;
import java.lang.reflect.*;

interface Generator<T> { T next(); }

interface Addable<T> { void add(T t); }

public class Fill2 {
  // Classtoken version:
  public static <T> void fill(Addable<T> addable,
    Class<? extends T> classToken, int size) {
    for(int i = 0; i < size; i++)
      try {
        addable.add(classToken.newInstance());
      } catch(Exception e) {
        throw new RuntimeException(e);
      }
  }
  // Generator version:
  public static <T> void
  fill(Addable<T> addable, Generator<T> generator, int size) {
    for(int i = 0; i < size; i++)
      addable.add(generator.next());
  }
}

// If you're adapting a base type, you must use composition.
// Make any Collection Addable using composition:
class AddableCollectionAdapter<T> implements Addable<T> {
  private Collection<T> c;
  public AddableCollectionAdapter(Collection<T> c) {
    this.c = c;
  }
  public void add(T item) { c.add(item); }
}

// Helper method for above, captures the type automatically:
class Adapter {
  public static <T>
  Addable<T> collectionAdapter(Collection<T> c) {
    return new AddableCollectionAdapter<T>(c);
  }
}

// If you're adapting a specific type, you can use inheritance:
// Make a SimpleQueue Addable using inheritance:
class AddableSimpleQueue<T>
extends SimpleQueue<T> implements Addable<T> {
  public void add(T item) { super.add(item); }
}

// Another type of container created by someone else:
class RandomList<T> {
  private ArrayList<T> storage = new ArrayList<T>();
  private Random rand = new Random();
  public void insert(T item) { storage.add(item); }
  public T select() {
    return storage.get(rand.nextInt(storage.size()));
  }
}

// Abstract composition adapter:
abstract class AddableAdapter<S, T> implements Addable<T> {
  protected S seq;
  public AddableAdapter(S sequence) { seq = sequence; }
  public abstract void add(T item);
}

class Coffee {}
class Latte extends Coffee {}
class Mocha extends Coffee {}
class Cappucino extends Coffee {}
class Americano extends Coffee {}
class Breve extends Coffee {}

// Generate different types of Coffee:
class CoffeeGenerator implements Generator<Coffee> {
  private Class[] types = { Latte.class, Mocha.class,
    Cappucino.class, Americano.class, Breve.class, };
  private Random rand = new Random();
  public Coffee next() {
    try {
      return (Coffee)types[rand.nextInt(types.length)].newInstance();
      // Report programmer errors at runtime:
    } catch(Exception e) {
      throw new RuntimeException(e);
    }
  }
}

class Fill2Test {
  public static void main(String[] args) {
    // Adapt a Collection:
    List<Coffee> coffeeCarrier = new ArrayList<Coffee>();
    Fill2.fill(new AddableCollectionAdapter<Coffee>(coffeeCarrier),
      Coffee.class, 3);
    // Helper method captures the type:
    Fill2.fill(Adapter.collectionAdapter(coffeeCarrier),
      Latte.class, 2);
    for(Coffee c: coffeeCarrier)
      System.out.println(c);

    System.out.println("----------------------");

    // Use an adapted class:
    AddableSimpleQueue<Coffee> coffeeQueue =
      new AddableSimpleQueue<Coffee>();
    Fill2.fill(coffeeQueue, Mocha.class, 4);
    Fill2.fill(coffeeQueue, Latte.class, 1);
    for(Coffee c: coffeeQueue)
      System.out.println(c);

    System.out.println("++++++++++++++++++++++");

    RandomList<Coffee> rl = new RandomList<Coffee>();
    // An on-the-fly adapter via an anonymous class:
    Addable<Coffee> ac =
      new AddableAdapter<RandomList<Coffee>, Coffee>(rl) {
        public void add(Coffee item) { seq.insert(item); }
      };
    Fill2.fill(ac, new CoffeeGenerator(), 7);
    for(int i = 0; i < 10; i++)
      System.out.println(rl.select());
  }
}

Fill2 doesn't require a Collection like Fill did. Instead, it only need something that implements Addable, and Addable has been written just for Fill – it is a manifestation of the latent type that I had wished the compiler would make for me.

In this version, I've also added an overloaded version of fill() that takes a Generator rather than a class token. A Generator is simply a class that produces a new object when you call next(), but notice that it's type-safe at compile time: the compiler ensures that you pass it a proper Generator, so no exceptions can be thrown.

The first adapter, AddableCollectionAdapter, works with the base type Collection, which means that any implementation of Collection can be used. This version simply stores the Collection reference and uses it to implement add().

If you have a specific type rather than the base class of a hierarchy, you can write somewhat less code when creating your adapter by using inheritance as you can see in AddableSimpleQueue.

To see the most interesting result of this code, I make a new kind of container called RandomList that doesn't implement any interfaces and is not part of any hierarchy. Let's assume it was created by someone else as a library and the could not anticipate any of our needs.

Now I create something very interesting: AddableAdapter, which I call an Abstract composition adapter. This is a general-purpose adapter that works with some type S which has a way to add items to itself. Notice two things about this code: S has no bounds, which ordinarily means that we couldn't call anything except Object methods on S. And what I do in the constructor for AddableAdapter is in fact very safe and generic – I simply store the reference to the sequence.

The second thing to notice is that the add() method, which satisfies the Addable<T> interface, is abstract, and there's no definition. Remember that when we put it to use later.

In order to produce an interesting set of types to work with, I created a Coffee hierarchy, and a CoffeeGenerator that produces random types of Coffee when you call next().

In Fill2Test.main(), you can see the various types of adapters at work. First, a Collection type is adapted with AddableCollectionAdapter. A second version of this uses a generic helper method, and you can see how the generic method is able to capture the type without the programmer having to explicitly write it out – this is a convenient trick that produces more elegant code.

Next, the pre-adapted AddableSimpleQueue is used. Note that in both cases the adapters allow the classes that previously didn't implement Addable to be used with Fill2.fill()

Finally, a RandomList is created and adapted using an anonymous class to produce an Addable<Coffee> that can then be used with Fill2.fill().

Why is it surprising that this works? Look closely at the definition of the inner class:

new AddableAdapter<RandomList<Coffee>, Coffee>(rl) {
  public void add(Coffee item) { seq.insert(item); }
};

The overridden add() method is calling insert(), a specific, non Object method on seq, but seq has no bound which says that insert() exists! We can only assume that when the inner class is created, the compiler analyzes and/or generates something (perhaps some kind of implicit bound) that allows it to make the call to insert() without requiring explicit bounds. In any event, this feature seems like it might allow some other interesting coding.

Using adapters like this would seem to compensate for the lack of latent typing, and thus allow you to write genuinely generic code. However, it's an extra step and something that must be understood both by the library creator and the library consumer, and the concept may not be grasped as readily by less experienced library consumers. By removing the extra step, latent typing makes generic code easier to apply, and this is its value.

Coincidentally, Rüdiger Klaehn wrote me and pointed out that .NET also has limitations because of the lack of latent typing. Even though C# does retain type information, it loses C++'s straightforward latent typing – it has to forget some things about the code because .NET generics must be language- neutral. Rüdiger has written a tool that automatically generates proxy classes to produce the effect of latent typing. You can find details in the following articles:

• generics
• generics2
• Autocaster

Daniel Bonniot (creator of the Nice language) gave another insight into the difference between C++ templates and Java Generics:

Nice generics are closer to Java than to C++. To me, C++ templates serve two purposes: enable generic types, and allow some kind of compile-time code generation. I believe they should be handled separately (using templates to do generics is inferior, because it leads to some errors to be detected later than they could be). The second aspect is also useful, but I think that rather calls for (hygenic) macros, in the spirit of Scheme. This is definitely something that will be investigated for Nice at a later point.

This is particularly intriguing, because using the "code generation" aspect of C++ templates, while powerful, is often confusing. If these really are two different issues, then separating them – and using a Scheme/Lisp style of macros – may add a great deal to the potential of programming with these tools by making it much simpler. Although generics are already part of Nice, macros will not be introduced until after version 1.0 (which should appear within the next 6 months).

For those who argue that Java Generics are only about Collection<T> and that using these is all the average programmer needs to know, I put forward that even small tools similar to Apply, FilledList, and Fill2 are useful tools to generify – if you go to the trouble to write them, why not write them reusably?

My point in these articles has been to show that there are limits to Java Generics, and if you understand the limits well enough, you can either figure out how to work around them (as I did here, with adapters) or at least know when to stop trying (and save yourself a lot of time and effort).

Feedback Wiki Page

^[1] Java could have a syntax to support a compile-time equivalent of pointers to members, based on the syntax that now produces class references at compile time. So you could not only say Shape.class to produce the class reference, you could also say Shape.class.rotate to produce the method reference at compile time. Of course, there would also need to be a compile-time syntax to apply the method reference.