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); }  
} 

C++

The translation model of C++ is based on instantiation – no static type checking is done on the generic code. The compiler generates separate copies of the component (class or function) for each instantiation with a distinct type and the type checking is performed after instantiation at each call site. Type checking of the bound types can only succeed when the input types have satisfied the type requirements of the function template body. It is because of this, that misleading error messages are thrown in by the compiler when a generic component is instantiated with an improper type.

Comparison

The C++ model is loss-less in the sense that no type information is lost during runtime, though the implementation of the translation suffers from the drawbacks of the possibility of introducing code bloats and misleading error messages. On the other hand, the Java model emphasizes on retrofitting the raw types with the generic counterparts, but the type-erasure model delegates the generic types to “second class” status compared to the conventional types.

Type Model

Java

Type requirements can be defined on arguments as a set of formal abstractions – this feature is called constrained genericity. The generic types of the classes have to honor these requirements in order to participate in the valid instantiation. Java Generics use interfaces to represent a concept and employ the mechanism of subtyping to model a concept – any type T modeling a concept C will have to implement the corresponding interface.

public interface VertexListGraph<Vertex,  
                      VertexIterator extends Iterator<Vertex>> { 
    VertexIterator vertices(); 
    int num_vertices(); 
} 
public interface IncidenceGraph<Vertex, Edge, 
                      OutEdgeIterator extends Iterator<Edge>> { 
    OutEdgeIterator out_edges(Vertex v); 
    int out_degree(Vertex v); 
} 
public interface VertexListAndIncidenceGraph<…> 
        extends VertexListGraph<…>, IncidenceGraph<…> {} 
public class adjacency_list 
        implements VertexListAndIncidenceGraph<Integer, 
                      Simple_edge<Integer>, Iterator<Integer>, 
                      Integer, Iterator<simple_edge<Integer>>, 
                      Integer, Iterator<simple_edge<Integer>>> { 
…… 
} 

The implements clause makes the adjacency_list a model of Vertex List Graph and Incidence Graph concepts.

C++

C++ does not offer any means to constrain the template parameters. However, techniques for checking constraints in C++ have been implemented as a library using the notion of compile time assertions.

Comparison

Java Generics come without two of the very important features of generic programming – type aliasing and associated types. C++ templates offer both of them, type aliasing through typedefs and the associated types through the traits mechanism. Though typedef s are not part of the C++ templates per se, but without them writing generic code often becomes extremely verbose and error prone.

Java has no type aliasing as seen below:

dijkstra_visitor<VertexListAndIncidenceGraph<Vertex, 
   Edge, 
   VertexIterator, 
   OutEdgeIterator>,  
                 mutable_queue<Vertex, indirect_cmp<Vertex,  
                          Distance, DistanceMap, DistanceCompare>>,  
                 WeightMap,  
                 PredecessorMap,  
                 DistanceMap,  
                 DistanceCombine,  
                 DistanceCompare,  
                 Vertex,  
                 Edge,  
                 Distance> vis  
      = new dijkstra_visitor<VertexListAndIncidenceGraph<Vertex, 
                                                     Edge, 
                                                     VertexIterator, 
                                                     OutEdgeIterator>,  
                             mutable_queue<Vertex,  
                                 indirect_cmp<Vertex, Distance,  
                                      DistanceMap, DistanceCompare>>,  
                             WeightMap,  
                             PredecessorMap,  
                             DistanceMap,  
                             DistanceCombine,  
                             DistanceCompare,  
                             Vertex,  
                             Edge,  
                             Distance> (Q, weight, predecessor, 
distance, combine, compare, zero); 

Java has no support for associated types:

// breadth_first_search prototype in C++ 
template <class VertexListGraph, class Buffer, class BFSVisitor, 
          class ColorMap> 
  void breadth_first_search 
    (const VertexListGraph& g, 
     typename graph_traits<VertexListGraph>::vertex_descriptor s, 
     Buffer& Q, BFSVisitor vis, ColorMap color) 
// breadth_first_search prototype in Java 
public static <Vertex, 
               Edge extends GraphEdge<Vertex>, 
               VertexIterator extends java.util.Iterator<Vertex>, 
               OutEdgeIterator extends java.util.Iterator<Edge>, 
               Vis extends Visitor, 
               ColorMap extends 
                    ReadWritePropertyMap<Vertex,java.lang.Integer>, 
               QueueType extends Buffer<Vertex>> 
  void breadth_first_search(VertexListAndIncidenceGraph<Vertex, 
                               Edge,VertexIterator,OutEdgeIterator> g, 
                               Vertex s, Visitor vis, ColorMap color) 

Security Model

Java

Java Generics translation model replaces all generic types by the bound type, Object, thereby removing all type information from the runtime system. This is referred to as the homogeneous model of implementing Generics, since all generic types are mapped to a single supertype.

C++

C++ implements the heterogeneous model, where the compiler generates a separate copy of the type for each specific instantiation of the type parameter. Hence a generic container Stack<T> will generate separate concrete classes Stack<int> for integers, Stack<double> for double precision numbers, Stack<string> for string data type. While in Java, Stack<T> will be instantiated as Stack collection class.

Class BroadcastList<C extends Channel> { 
    C channels[]; 
    void add(C c) { … } 
    void broadcast(String s) { 
        int I; 
        for(I = 0; I < channels.length; i++) 
            channels[i].send(s); 
    } 
    …… 
} 
Class EncryptedChannel extends Channel; 
Class UnencryptedChannel extends Channel; 
BroadcastList<EncryptedChannel> list = ……; 
list.add(new EncryptedChannel()); 
(*) 
list.broadcast(“Hello”); 

Comparison

Because of the homogeneous implementation, during instantiation of the generic class BroadCastList, C will not contain the exact type, since the translation of Java Generics will erase C. Hence it becomes vulnerable to a malicious program who can add an unencrypted channel to the list (possibly at position marked by (*)) through hand-written byte codes, which will bypass all compile time checking and the compiler generated run-time checks guaranteeing JDK 1.5 (beta) includes a workaround to prevent this security hole; it has a means of constructing a dynamically typesafe view of a specified collection (Collections.checkedCollection()). This ensures that any attempt to insert an element of incorrect type will result in a ClassCastException. But this approach introduces a counterintuitive programming model specifically to address an existing loophole in the security of the JVM. 

In C++, this security loophole does not exist since strict type-checking is employed at the points of instantiation of templates. However, this heterogeneous translation model employed by C++ will not fit with the current security model of the Java virtual machine. The JVM offers two levels of visibility – global level (public) and package level. Hence in some cases it becomes impossible to find out the proper package where the instantiated class will be placed honoring the visibility model of the JVM.

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.

Conclusion

Despite their deceptively similar syntax, C++ and Java are two very different languages. Likewise, the original goals, programming models, and under-currents shaping their continued evolution are very different. Not surprisingly, their approaches to support generic programming are very different—"simple and comprehensible" in Java and meticulous and comprehensive in C++.

Java Generics substantially improves type safety, encourages software reuse, and adds some basic support for generic programming. For Java, it is a serious step forward in the area of commercial software development. However, Java Generics in its proposed form does not qualify to be called generics (as in generic programming) as yet.

Although some generic programming concepts are difficult in C++, compared to Java, C++ is well advanced and Java has a lot to catch up with. Consequently, claims of Java Generics being "better than C++ templates" are naive and ungrounded at best.

Nevertheless, both languages have their applications and their devoted users. There is enough room for everyone.

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
14. http://drdobbs.com/184401818