CSC/ECE 517 Fall 2011/ch6 6c sj

Generic Programming

Generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters. This enables writing common set of functions which differ only in the types on which they operate. This reduces duplication. Software entities created using generic programming are known as generics in Ada, Eiffel, Java, C#, F#, and Visual Basic .NET; parametric polymorphism in ML, Scala and Haskell, templates in C++.

For example, given various data structures and several algorithms, the brute force way would be implement them for each data structure which would mean that various combinations of implementations will be necessary. Generic programming reduces this effort.

Generics in Java

What are Generics?

Generics were added to Java programming language as a part of J2SE 5.0 release in 2004. They allow programmers to develop generic and compile safe applications which enables a type or method to operate on objects of various type. This feature is well utilized while implementing Java Collections. The reason why people went into generic programming can be well explained using the below example:

  List list = new ArrayList();
  list.add("name");
  Integer num = (Integer)list.get(0);

In this example, we insert a String into an ArrayList and retrieve element by typecasting with Integer wrapper class. This throws a runtime exception because of Illegal class cast. But if we use generics, runtime exceptions can be avoided and the compiler will be able to catch such issues which in turn help a programmer to build a bug free code. So if we convert the above code to use generic then it would look like this:

  List<String> list = new ArrayList<String>();
  list.add("name");
  Integer num = list.get(0); //line 1 

Here at line 1 the compiler throws an error because the compiler on seeing the declaration of ArrayList will be expecting the list to have just String and thereby the return type of get to be String.

Implementing Generics:

Java provides a feature which helps one to implement your own generic types and this will help to build more sophisticated and runtime error free applications. Consider the below example:

  interface List<N> {
                        void add(N i);
                        Iterator<N> iterator();
                     }
  interface Iterator<N> {
                           N next();
                           boolean hasNext();
                        }
  class LinkedList<N> implements List<N> {
                         //Business Logic   
                }

So here, N can be replaced with any primitive data types or wrapper classes in the business logic. But we need to make sure that placeholders to be replaced with valid subtypes of Object. Generics implementation is not restricted for classes or interfaces, we can have for static/non static methods and constructors.

Example for generic methods:

<T> void fromArrayToCollection(T[] a, Collection<T> c) {
    for (T o : a) {
        c.add(o); // Correct
    }
}

Pros and Cons

Pros:

1. Reduces the number of casts in the program, which in turn reduces the number of potential bugs in the program.
2. Improves code clarity and maintenance.

Cons:

1. Parameter type information is not available at run time.
2. The automatically generated casts may fail when interoperating with ill-behaved legacy code.

Templates in C++

What are templates?

Templates are functions that can operate with generic types which means that the functionality can be adapted for more than one type of data without repeating the entire code for each type.

Overview

Templates can be either function templates or class templates.

Function Templates

These are just like regular functions except that they can have arguments of different types. A single function definition works with different kinds of data types. During compile time, the actual functions are generated once the compiler knows the data type being used. This kind of template does not save any memory.

Example

template <typename Type>
Type max(Type a, Type b) {
    return a > b ? a : b;
}

#include <iostream>
 
int main()
{
  // This will call max <int> (by argument deduction)
  std::cout << max(3, 7) << std::endl;
  // This will call max<double> (by argument deduction)
  std::cout << max(3.0, 7.0) << std::endl;
  // This type is ambiguous, so explicitly instantiate max<double>
  std::cout << max<double>(3, 7.0) << std::endl;
  return 0;
}

Class Templates

A class template provides a specification for generating classes based on parameters. A class template is instantiated by passing a given set of types to it as template arguments.

Example

template <class T>
class mypair {
    T values [2];
  public:
    mypair (T first, T second)
    {
      values[0]=first; values[1]=second;
    }
};

Features of C++ Templates

Some of the features of C++ templates are:

1. Implemented in the compiler.
   No runtime overhead
   Requires template source to be in headers
   Latent typing means template instantiator does no type checking
2. Glorified macro facility
   “Macros done right”/“Macros that look like classes”
3. Can use template arguments for both classes and straight function
4. Template specialization
   Specific implementation of a templated type or method
5. Pattern matching and text replacement
   Declarative model (like Prolog)

Pros and Cons

Usage of templates have both advantages and disadvantages.

Pros

1. Reduction in code size.
2. They are type-safe, that is, type-checking is done at compile time.

Cons

1. Since all compilers are not good at their support for templates, they may not be very portable.
2. Compilers generate additional code for each template type, this could lead to huge code if usage of templates is not checked.
3. Information hiding is not achieved as the code is all exposed in the header.

Templates (C++) versus Generics (Java)

We can compare templates in C++ versus generics in Java based on the following models of comparison, 1. Translation model - discussion based on the way generic code is translated. 2. Type model - discussion based on implementations in type interference, type aliasing and associated types. 3. Security model - discussion based on security loopholes, if any. Let's look at these with some examples.

Translation Model

Java

One of the design reasons behind Java's generics was to provide backward compatibility of legacy Java code. To achieve this, Java implementation has adopted the same representation policy for the raw type and the parametric type. The parametric type Collection<T> can be passed safely where the corresponding raw type Collection is expected. Hence the translation model of Java Generics is based on the “type erasure” model, where the translation erases the generic type parameter, replaces them by the bounding type (Object) and inserts casts to the actual places of usage. In order for method overriding to work correctly, the translation process also adds “bridge methods”, as illustrated in the following example.

class C<A> { abstract A id(A x); } 
class D extends C<String> { String id(String x) { return x; } } 
This will be translated to: 
class C { abstract Object id(Object x); } 
class D extends C { 
    String id(String x) { return x; } 
    // bridge method introduced by the translator to make  
    // overriding work correctly 
    Object id(Object x) { return id((String)x); }  
} 

Evolution of Generics

Here we take Java programming language as an example to explain evolution of generics. Generics were introduced with Java 1.5. However, before that, the codes were bulky and messy but the results were same. Rather than simply using a List<Integer> or Comparable<String>, developers had to deal with a significant amount of inheritance, casting, and instanceof testing. For example, an ArrayList to store only Integers pre-generics might look like the below snippet:

public class IntegerList extends ArrayList{
     public boolean add(Object o){
            if(o instanceof Integer)
                return super.add(o);
             return false;
      }

      public Integer get(int index){
           return (Integer)super.get(index);
      }
}

Generics allows to write more modular and reusable code that is adaptable to various datatypes, yet logically restrictive as well. Currently, generics are implemented using erasure, which means that the generic type information is not available at runtime, which makes some kind of code hard to write. Generics were implemented this way to support backwards compatibility with older non-generic code. Reified generics would make the generic type information available at runtime, which would break legacy non-generic code. Generics are implemented using erasure, in which generic type parameters are simply removed at runtime. That doesn't render generics useless, because you get typechecking at compile-time based on the generic type parameters, and also because the compiler inserts casts in the code based on the type parameters.

Erasure v/s Reification

Consider the below example, it won't work because of erasure.

public class Test<Key, Val> {
  public void test(Key key) {
  }
 
  public void test(Val value) {
  }
}

This would give a name clash error for having same erasure and one way to avoid the error is by renaming the method name but this will not the serve the purpose of overloading. Similarly, the below example would give errors because the JVM is not aware of the type T instead views it just as an Object.

public class Test {
  public <T> void f() {
    T t = new T();
  }
}

So reified generics have support in the compiler for preserving type information whereas type erased generics don't have and that "remember" the class they were created with during runtime. Below are some of the reasons why Java should have reified generics:

1. Type argument erasure cripples frameworks that works with generic types and this results in horrid workarounds
2. Reified generics allows Typesafe narrowing. Currently in Java, we first test the type of the object using the instanceof operator, and then attempt to downcast it using a C-style typecast
3. Interoperability between statically-typed is difficult since few support reified generics.

But at the same time reified generics have issues and one of the main concern is incompatible with the current collections. So a test on instanceof List<String> would now test that the object is an instance of List but also that its elements are of type String. This requires a lot of work around since we need to distinguish between collections making used of reified types from their older types.

Reference

1. http://en.wikipedia.org/wiki/Generic_programming
2. http://en.wikipedia.org/wiki/Generics_in_Java
3. http://www.oracle.com/technetwork/articles/javase/generics-136597.html
4. http://download.oracle.com/javase/tutorial/extra/generics/methods.html
5. http://www.cplusplus.com/doc/tutorial/templates/
6. http://en.wikipedia.org/wiki/Template_(programming)
7. http://www.cs.binghamton.edu/~mike/presentations/java-generics-cs580c-fall-2007.pdf
8. http://jnb.ociweb.com/jnb/jnbJul2003.html
9. http://tech.puredanger.com/java7/#reified
10. http://gafter.blogspot.com/2006/11/reified-generics-for-java.html
11. http://relation.to/21406.lace
12. http://beust.com/weblog/2011/07/29/erasure-vs-reification
13. http://aszt.inf.elte.hu/~gsd/s/cikkek/java/p40-ghosh.pdf