Generic programming

In computer science, generics is a technique that allows one value to take different Datatypes (so-called polymorphism (computer science)) as long as certain contracts such as subtypes and signature (computer science) are kept. The programming style emphasizing use of this technique is called 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 programming languages, C plus plus, D programming language, BETA programming language, Eiffel programming language, Ada programming language, and versions of Java programming language (1.5 and higher) provide generic facilities. Visual_Basic_.NET and C Sharp programming language began providing them with .NET 2.0. Much earlier than in all mentioned languages, generic programming was implemented in CLU_programming_language.

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 as is featured in Objective-C, and, if necessary, judicious use of interface (computing) 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 some of 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 in object-oriented programming 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:

template T max(T x, T y) { if (x < y) return y; else return x; }

This template can be called just like a function:

cout 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 -> 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_programming_language, developed at Utrecht University. The extensions it provides are:

Type-indexed values are defined as a value indexed over the various Haskell type constructors (unit, primitive types, sums, products, and user-defined type constructors). In addition, we can also specify the behaviour of a type-indexed values for a specific constructor using constructor cases , and reuse one generic definition in another using default cases .

The resulting type-indexed value can be specialised to any type.

Kind-indexed types are types indexed over kinds, defined by giving a case for both * and k → k. Instances are obtained by applying the kind-indexed type to a kind.

Generic definitions can be used by applying them to a type or kind. This is called generic application . The result is a type or value, depending on which sort of generic definition is applied.

Generic abstraction enables generic definitions be defined by abstracting a type parameter (of a given kind).

Type-indexed types are types which are indexed over the type constructors. These can be used to give types to more involved generic values. The resulting type-indexed types can be specialised to any type.

As an example, the equality function in Generic Haskell: type Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool type Eq {[ k -> l ]} t1 t2 = forall u1 u2. Eq {[ k ]} u1 u2 -> Eq {[ l ]} (t1 u1) (t2 u2) eq :: Eq {[ k ]} t t eq _ _ = True eq eqA eqB (Inl a1) (Inl a2) = eqA a1 a2 eq eqA eqB (Inr b1) (Inr b2) = eqB b1 b2 eq eqA eqB _ _ = False eq eqA eqB (a1 :*: b1) (a2 :*: b2) = eqA a1 a2 && eqB b1 b2 eq = (==) eq = (==) eq = (==)

==The Scrap your boilerplate approach==

The Scrap your boilerplate approach is a lightweight generic programming approach for Haskell. The approach is supported in the Glasgow Haskell Compiler >= 6.0 implementation of Haskell. Using this approach, the programmer can write generic functions such as traversal schemes (e.g., everywhere and everything), as well as generic read, generic show and generic equality (i.e., gread, gshow, and geq). This approach is based on just a few primitives for type-safe cast and processing constructor applications.

==Generics for the masses==

In all the previous language extensions seen, none could work totally inside the Haskell 98 standard: they all require something extra, either a more sophisticated type system or an additional language construct. The purpose of Generics for the masses is to show that one can, in fact, program generically within Haskell 98 obviating to some extent the need for fancy type systems or separate tools. Haskell_programming_language’s type classes are at the heart of this approach: they ensure that generic functions can be defined succinctly and, in particular, that they can be used painlessly.

=See also=

Comparison of generics to templates

Partial evaluation

= External references and links =

*David Vandevoorde, C++ Templates: The Complete Guide , 2003 Addison-Wesley. ISBN 0-201-73484-2 *[http://www.stepanovpapers.com/ Papers] by Alexander A. Stepanov (creator of the Standard Template Library) *[http://msdn.microsoft.com/msdnmag/issues/03/09/NET/ Introducing Generics in the Microsoft CLR (MSDN Magazine)] *[http://msdn.microsoft.com/msdnmag/issues/03/10/NET/ More on Generics in the Microsoft CLR (MSDN Magazine)] *[http://www.generic-haskell.org/ Generic Haskell, a language for generic programming] *Löh, Andres (2004), [http://www.cs.uu.nl/~andres/ExploringGH.pdf Exploring Generic Haskell], ISBN 90-393-3765-9 *Dæv Clarke, Johan Jeuring and Andres Löh, [http://www.cs.uu.nl/research/projects/generic-haskell/compiler/beryl/GHUsersGuide.pdf The Generic Haskell user s guide] *Hinze, Ralf (2004), [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP04.pdf Generics for the Masses] *Ralf Lämmel and Simon Peyton Jones (2003), [http://www.cs.vu.nl/boilerplate/ Scrap your boilerplate ... in Haskell] *[http://java.sun.com/j2se/1.5.0/docs/guide/language/generics.html Generic Programming In Java]