Comparison of generics to templates

This is a comparison of generics (a type of generic programming) as implemented in the Java programming language (and proposed for the C Sharp) to Template metaprogramming in C plus plus and D programming language.

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 programming language. External metaprogramming systems, such as those described in Generative Programming by Krzysztof Czarnecki and Ulrich W. Eisenecker, have more in common with templates than with generics.

=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 (programming) 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 compilation, 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 Sorting algorithm 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 List where the template parameter T can be replaced by any type when the code is compiled. This is accomplished by template instantiation : List l1; List h2; Here we have created a list of integers and one of strings, but we only had to write the list 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 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; template class Foo; The compiler will generate two class definitions, one for each instantiation: class Foo { int bar; public: int getBar() {return bar;} void setBar(int baz) {bar = baz;} }; class Foo { 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 (computer science), two factors facilitate a solution:

#A unified type system; all class (computer science) inherit from a single base class, such as class Object in Java. #Reflection (computer science), 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 method (computer science) 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 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 a1; ArrayList a2; 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