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

The two major benefits of generics in Java are:

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.

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.

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