Generic programming
|
|
In computer science, generics is a technique that allows one value to take different datatypes (so-called polymorphism) as long as certain contracts such as subtypes and signature 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<T>, where T represented the type. When instantiated, one could create List<Integer> or List<Animal>. 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 provide generic facilities. VB.NET and C# began providing them 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 as is 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 some of the benefits of dynamic typing with the advantages of having static typing.
| Contents |
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:
template <typename T>
T max(T x, T y)
{
if (x < y)
return y;
else
return x;
}
This template can be called just like a function:
cout << max(3, 7); // outputs 7
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 (http://java.sun.com/j2se/1.5.0/docs/guide/language/generics.html)
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 Haskell in particular, some language extensions have been developed for generic programming, and the language itself contains some generic aspects included.
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:
- 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 {| t :: k |} :: Eq {[ k ]} t t
eq {| Unit |} _ _ = 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 {| Int |} = (==)
eq {| Char |} = (==)
eq {| Bool |} = (==)
The "Scrap your boilerplate" approach
The Scrap your boilerplate approach is a lightweight generic programming approach for Haskell. The approach is supported in the GHC >= 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’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
External references and links
- David Vandevoorde, C++ Templates: The Complete Guide, 2003 Addison-Wesley. ISBN 0-201-73484-2
- Papers (http://www.stepanovpapers.com/) by Alexander A. Stepanov (creator of the STL)
- Introducing Generics in the Microsoft CLR (MSDN Magazine) (http://msdn.microsoft.com/msdnmag/issues/03/09/NET/)
- More on Generics in the Microsoft CLR (MSDN Magazine) (http://msdn.microsoft.com/msdnmag/issues/03/10/NET/)
- Generic Haskell, a language for generic programming (http://www.generic-haskell.org/)
- Löh, Andres (2004), Exploring Generic Haskell (http://www.cs.uu.nl/~andres/ExploringGH.pdf), ISBN 90-393-3765-9
- Dæv Clarke, Johan Jeuring and Andres Löh, The Generic Haskell user's guide (http://www.cs.uu.nl/research/projects/generic-haskell/compiler/beryl/GHUsersGuide.pdf)
- Hinze, Ralf (2004), Generics for the Masses (http://www.informatik.uni-bonn.de/~ralf/publications/ICFP04.pdf)
- Ralf Lämmel and Simon Peyton Jones (2003), Scrap your boilerplate ... in Haskell (http://www.cs.vu.nl/boilerplate/)
- Generic Programming In Java (http://java.sun.com/j2se/1.5.0/docs/guide/language/generics.html)
de:Template
no:Generisk Programmering
pl:Szablon (C plus plus)