This is a comparison of generics (a type of generic programming) as implemented in the Java programming language (and proposed for the C# programming language) to templates in C++ and D.

A quick note on terminology: the term "generics" can refer to a number of related generic programming techniques, but this article only deals with the specific type of generics that are implemented in Java.

The problem

Templates and generics are two solutions to a problem that arises in strongly-typed programming languages. Many of the most popular programming languages today are strongly typed, as this type of language can have significant benefits with regards to robustness. For example, if we have a function

int sum(int[] a)

that takes as its argument an array of integers and returns the sum, we would not want a programmer to accidentally pass the function an array of strings. Strongly-typed languages prevent this type of mistake from being made at compile-time, which means we don't need to chase down this type of error while debugging.

However, this facility, while helpful, introduces a problem. Many data structures and algorithms are very general in applicability. For example, the function

void sort(int[] a)

that takes an array of integers and sorts it could very easily be rewritten to sort strings. In a dynamically-typed language, we might even be able to reuse the code without any changes. To give another example, consider a complex data structure such as a hash table. This data structure could just as easily hold integers, strings, or billing records.

The problem with implementing algorithms or data structures in a strongly-typed language is that we must rewrite the code for each type of data that must be handled. Rewriting code is time-consuming and opens the door for errors to creep in. In addition, changes to one set of code must be manually echoed in all of the copies.

Templates

One solution to this problem is to not make programmers rewrite code manually, but instead let a tool do it for them. One such tool is the template metaprogramming facility in C++ (and the similar facility in D). Templates are a type of code generation, that is, they take a higher level description of code and use it to automatically produce code. Specifically, a template is generic code that takes one or more parameters, which at compile-time can take more specific values.

For example, instead of writing two classes, ListOfInts and ListOfStrings, we might write a single template class:

template <class T> class List

where the template parameter T can be replaced by any type when the code is compiled. This is accomplished by template instantiation:

List<int> l1;
List<string> h2;

Here we have created a hash table of integers and one of strings, but we only had to write the hash table class once.

Templates are actually more general than solving the problem identified here; see Template metaprogramming for more details.

How templates work

Let's look in more detail at a simple example of a template class and how it is handled by the compiler. We use the familiar C++ syntax.

template <class T> class Foo {
  T bar;
public:
  T getBar() {return bar;}
  void setBar(T baz) {bar = baz;}
};

We now create two instantiations of the template class, in this case using explicit instantiation:

template class Foo<int>;
template class Foo<char>;

The compiler will generate two class definitions, one for each instantiation:

class Foo<int> {
  int bar;
public:
  int getBar() {return bar;}
  void setBar(int baz) {bar = baz;}
};
class Foo<char> {
  char bar;
public:
  char getBar() {return bar;}
  void setBar(char baz) {bar = baz;}
};

In general, each instantiation of a template produces a copy of the template code.

Generics

Another solution that is specific to object-oriented programming languages is generics. First, let's look at how many languages partially solve the problem, and then we will see how generics is an improvement.

In some object-oriented languages that use inheritance, two factors facilitate a solution:

1. A unified type system; all classes inherit from a single base class, such as class Object in Java.
2. Reflection, which allows us to discover information about an object's type at run-time. We actually only need run-time type identification, a limited form of reflection. This means this solution could actually be used with C++, assuming we use a coding style that satisfies the first condition.

Examples of languages that include these features are Java and C#.

The Java collections framework gives an example of how these factors can be used to arrive at a partial solution to the problem. For example, the Java collections framework contains a class ArrayList that defines methods such as

boolean add(Object o)

and

Object get(int index)

which insert an object at the end of the list and return the object stored at a specified index, respectively. Since all classes inherit from class Object, we could just as easily add and retrieve strings, files, billing records, etc. Assume that the variable a is an array list and s is a string. We add the string to the list with

a.add(s);

and retrieve it with

s = (String) a.get(index);

Note that because the get method returns an object, not specifically a string, we must cast the return value to type String before trying to store it in s. Also note that the programming language must have run-time type identification, that is, some way to determine at run-time whether the object returned actually is a string.

This solution is useful, but it is not complete. It achieves the flexibility of templates by breaking the type system. Specifically, if we have an array list that we want to contain only strings, there is no way to enforce this restriction. An unwitting programmer might accidentally add an object of some type other than a string to the list. If the list contained a file for some reason, the line

s = (String) a.get(index);

would fail (throwing a ClassCastException) when we tried to cast the file object to a string. In addition, the required cast is somewhat cumbersome "boilerplate code ".

One solution to this problem is generics. Generics (at least as implemented in Java) look very similar in syntax to templates, and are inspired by templates, but they are in fact a very different solution. Let's look at the generified version of the ArrayList class, from Java 2 Version 5:

class ArrayList<E>

The parameter E refers to a class, specifically the class the array list should store. Note that because generic parameters are always classes (or interfaces), it is not necessary (as it is in C++) to specify that E is a class parameter.

Much as in the case of templates, we can instantiate array lists of different types:

ArrayList<String> a1;
ArrayList<Object> a2;
ArrayList<ArrayList> a3;

Now, if we write code that tries to insert an object of an inappropriate type into one of our array lists, such as:

ArrayList a = new ArrayList();
a1.add(a);

the code will not compile. This saves the programmer from finding such problems during debugging. In addition, to get a string out of the string array list, we need only write

s = a1.get(index);

Notice that the cast is no longer required, because the compiler can guarantee that only strings will be added to the list.

Generic classes and methods can specify "bounds" on their parameters. Let's look at an example of a generic method, defined in class Collections (a utility class with methods that operate on collections):

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)

This example may seem daunting, but we can look at it one part at a time. The part

<T extends Object & Comparable<? super T>>

specifies that this is a generic method, and states the bounds on the generic parameter T. T must extend class Object, which means it must be a class, not an interface, and it must implement the interface Comparable<? super T>, in other words, it must be comparable to some superclass of itself. The method takes as its only argument a collection, Collection<? extends T> coll, not necessarily a collection of T but at least a collection of some subclass of T. Why these particular bounds were chosen is a tricky issue, but use of the generic method generally does not require a complete understanding of the bounds.

How generics work

Despite the superficial similarity of syntax, these two solutions are quite different. The difference is largely in how they are handled by the compiler. With templates, the compiler generates code for each instantiation of the template. With generics, this is not the case. There only exists a single copy of the generic class. So in our example case of ArrayList, our three instantiations of the class all use the same code. This is very important, as the compiler has no way of knowing what types of array lists might be created when it compiles the ArrayList class.

What does happen when we instantiate a generic class is that the compiler introduces compile-time checks on calls to that class's methods. We have seen this above, when we accidentally tried to add an array list into the array list of strings. In addition, the compiler can suppress the cast that would usually be required on the return value of the get method.

What about the code in the generic class itself? In the code for a class such as ArrayList that does not specify bounds on its parameters, any objects of type E (the generic parameter) are treated as generic Objects. Only operations that are applicable to any Object can be applied to variables of type E. In generic classes and methods that specify bounds on parameters, the compiler checks if the operations on variables of type E can be performed on any class satisfying the bounds.

Comparison

Here is a summary of the differences between generics and templates:

Advantages of generics

• A generic class can be compiled without knowing how it will be instantiated. Consequently, a generic class can be distributed as bytecode, whereas a template class must be distributed as source code.
• Code that uses a generic class or method does not require the generic code to be recompiled. This can result in faster compilation.
• Generic code appears only once in the bytecode or executable code, resulting in a smaller executable.
• There exists a relationship between different instantiations of generic code, whereas different instantiations of a template are completely incompatible.
• Generics allow raw types, that is, generic classes that haven't been instantiated. This feature allows generic code to interoperate with legacy code that doesn't use generics. On the other hand, templates must be instantiated.
• Although both generics and templates can be tricky to write, having complex syntax rules, generics are usually easier to use.
• Generics allow the restrictions on parameters to be stated explicitly, allowing errors due to improper instantiation to be caught at an earlier stage of compilation. While this is possible with templates (and implemented in D templates), it is not implemented in the best known example of templates, namely C++.

Advantages of templates

• Templates need not be specific to object-oriented languages.
• Because templates generate code for each instantiation, each instantiation may be be optimized separately. Many optimizations that would not be possible with generics, such as loop unrolling , are possible with templates.
• C++ templates allow explicit instantiations to override template class methods, which provides some balance between the convenience of templates and the flexibility of writing code from scratch.
• Templates are more general than generics, allowing parameters other than types. In fact, although the practice is widely discouraged, template metaprogramming is Turing complete.

External links

• Generics tutorial (PDF)
• Templates in D