Generic programming

For example, if one wanted to create a list using generics, a possible declaration would be to say List, where T represented the type. When instantiated, one could create List or List. The list then, is treated as a list of whichever type is specified.

Among object-oriented languages, C++, D, BETA, Eiffel, Ada, and later versions of Java. VB.NET and C# began providing generic facilities with .NET 2.0.

It was, however, templates of C++ that popularized the notion of generics.
Templates allow code to be written without consideration of the data type with which it will eventually be used.

Dynamic typing, such featured in Objective-C, and, if necessary, judicious use of protocols circumvent the need for use of generic programming techniques, since there exists a general type to contain any object. Whilst Java does so also, the casting that needs to be done breaks the discipline of static typing, and generics are one way of achieving the benefits of dynamic typing with the advantages of having static typing.

Templates

Templates are of great utility to programmers in C++, especially when combined with multiple inheritance and operator overloading. The C++ Standard Template Library (STL) provides many useful functions within a framework of connected templates.

As the templates in C++ are very expressive they may be used for things other than generic programming. One such use is called template metaprogramming, which is a way of pre-evaluating some of the code at compile-time rather than run-time. Further discussion here only relates to templates as a method of generic programming.

Technical overview

There are two kinds of templates. A function template behaves like a function that can accept arguments of many different types. For example, the C++ Standard Template Library contains the function template max(x, y) which returns either x or y, whichever is larger. max() could be defined like this:

This template can be called just like a function:

The compiler determines by examining the arguments that this is a call to max(int, int) and instantiates a version of the function where the type T is int.

This works whether the arguments x and y are integers, strings, or any other type for which it makes sense to say "x < y". If you have defined your own data type, you can use operator overloading to define the meaning of < for your type, thus allowing you to use the max() function. While this may seem a minor benefit in this isolated example, in the context of a comprehensive library like the STL it allows the programmer to get extensive functionality for a new data type, just by defining a few operators for it. Merely defining < allows a type to be used with the standard sort(), stable_sort(), and binary_search() algorithms; data structures such as sets, heaps, and associative arrays; and more.

As a counterexample, the standard type complex does not define the < operator, because there is no strict order on complex numbers. Therefore max(x, y) will fail with a compile error if x and y are complex values. Likewise, other templates that rely on < cannot be applied to complex data. Unfortunately, compilers historically generate somewhat esoteric and unhelpful error messages for this sort of error. Ensuring that a certain object adheres to a method protocol can alleviate this issue.

A class template extends the same concept to classes. Class templates are often used to make generic containers. For example, the STL has a linked list container. To make a linked list of integers, one writes list<int>. A list of strings is denoted list<string>. A list has a set of standard functions associated with it, which work no matter what you put between the brackets.

Advantages and disadvantages

Some uses of templates, such as the max() function, were previously filled by function-like preprocessor macros. For example, here is a max() macro:

#define max(a,b) ((a) < (b) ? (b) : (a)) Both macros and templates are expanded at compile time. Macros are always expanded inline; templates can also be expanded as inline functions when the compiler deems it appropriate. Thus both function-like macros and function templates have no run-time overhead.

However, templates are generally considered an improvement over macros for these purposes. Templates are type-safe. Templates avoid some of the common errors found in code that makes heavy use of function-like macros. Perhaps most importantly, templates were designed to be applicable to much larger problems than macros.

There are three primary drawbacks to the use of templates. First, many compilers historically have very poor support for templates, so the use of templates can make code somewhat less portable. Second, almost all compilers produce confusing, unhelpful error messages when errors are detected in template code. This can make templates difficult to develop. Third, each use of a template may cause the compiler to generate extra code (an instantiation of the template), so the indiscriminate use of templates can lead to code bloat, resulting in excessively large executables. The extra instantiations generated by templates can also cause debuggers to have difficulty working gracefully with templates. For example, setting a debug breakpoint within a template from a source file may either miss setting the breakpoint in the actual instantiation desired or may set a breakpoint in every place the template is instantiated.

Generic programming features in other languages

Templates were left out of some C++-based languages, such as Java and C#, largely due to the problems with templates in C++. These languages have adopted other methods of dealing with the same problems. However, C# is currently adopting generic programming features comparable to templates.

Java supports generics as of J2SE 1.5.0. Generics In Java

D supports template programming as advanced as C++'s,
and in some ways even more powerful.

Ada's generics predate templates.

Generic programming in Haskell

In the language itself

For instance, in a declaration of a user-defined data type (a binary tree with values of some given type a in the nodes and leaves):

data BinTree a = Leaf a | Node (BinTree a) a (Bintree a) deriving (Eq, Show) , the keyword deriving followed by the two type classes, Eq and Show, will make it possible for the programmer to automatically have an equality function defined for BinTree's (==), as well as a way to transform them into printable output (show).

So, the Haskell compiler can, in a generic fashion, generate instances of particular functions for any given data type (although some restrictions apply). Other instances that can be generated are Ord and Read, for instance.

PolyP extension

PolyP was the first generic programming language extension to Haskell. In PolyP, generic functions are called polytypic. The language introduces a special construct in which such polytypic functions can be defined via structural induction over the structure of the pattern functor of a regular datatype. Regular datatypes in PolyP are a subset of Haskell datatypes. A regular datatype t must be of kind * → *, and if a is the formal type argument in the definition, then all recursive calls to t must have the form t a. These restrictions rule out higher kinded datatypes as well as nested datatypes, where the recursive calls are of a different form.
The flatten function in PolyP is here provided as an example:
flatten :: Regular d => d a -> [a]
flatten = cata fl
polytypic fl :: f a [a] -> [a]
case f of
g+h -> either fl fl
g*h -> \\(x,y) -> fl x ++ fl y
() -> \\x -> []
Par -> \\x -> [x]
Rec -> \\x -> x
d@g -> concat . flatten . pmap fl
Con t -> \\x -> []
cata :: Regular d => (FunctorOf d a b -> b) -> d a -> b

Generic Haskell

Generic Haskell is another extension to Haskell, developed at Utrecht University. The extensions it provides are: