- Generic programming
Generic programming is a style of
computer programmingin which algorithms are written in terms of "to-be-specified-later" types that are then "instantiated" when needed for specific types provided as parameters and was pioneered by Ada which appeared in 1983. This approach permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication. Software entities created using generic programming are known as "generics" in Ada, Eiffel, Java, C#, Visual Basic .NETand Haskell; "templates" in C++; and "parameterized types" in the influential 1994 book " Design Patterns". The authors of " Design Patterns" note that this technique, especially when combined with delegation, is very powerful but that "Dynamic, highly parameterized software is harder to understand than more static software." (Gang of Four 1995:21)
Generic programming refers to features of certain statically typed
programming languagesthat allow some code to effectively circumvent the static typing requirements. For instance in C++, a template is a routine in which some parameters are qualified by a type variable. Since code generation in C++ depends on concrete types, the template is specialized for each combination of argument types that occur in practice. Generic programming is commonly used to implement containers such as lists and hash tables and functions such as a particular sorting algorithm for objects specified in terms more general than a concrete type.
Programming language support for generic programming
Generic programming facilities first appeared in the 1970s in languages like CLU and Ada, and were subsequently adopted by many object-based and object-oriented languages, including BETA,
C++, D, Eiffel, Java, and DEC's now defunct Trellis-Owllanguage. Implementations of generics in languages such as Java and C# are formally based on the notion of parametricity, due to John C. Reynolds. Software entities created using generic programming are known as "generics" in Ada, Eiffel, Java, C#, VB .NET and Haskell; "templates" in C++; and "parameterized types" in Design Patterns.
Generic programming is implemented and supported differently within each language. The term "generic" has also been used differently in programming contexts. For example, in Forth the compiler can execute code while compiling and one can create new "compiler keywords" and new implementations for those words on the fly. It has few "words" that expose the compiler behaviour and therefore naturally offers "generic programming" capacities which, however, are not referred to as such in most Forth texts. The term has been used in
functional programming, specifically in Haskell-like languages, which use a structural type systemwhere types are always parametric and the actual code on those types is generic. In these uses "generic programming" still serves the similar purpose of code-saving and the rendering of an abstraction.
Generic programming in object-oriented languages
When creating containers of objects it is possible to write specific implementations for each datatype contained, even if the code is virtually identical except for different datatypes. In C++, this duplication of code can be circumvented by defining a template class:Above, T is a placeholder for whatever type is specified when the list is created. These "containers-of-type-T", commonly called generics, are a generic programming technique allowing a class to be reused with different datatypes as long as certain contracts such as
subtypes and signature are kept. Generic programming should not to be confused with "inclusion polymorphism", which is the algorithmic usage of exchangeable sub-classes: for instance, a list of objects of type Moving_Object containing objects of type Animal and Car. Generics can also be used for type-independent functions as in the
templateconstruct used above is widely cited as the generic programming construct that popularized the notion among programmers and language designers and supports many generic programming idioms. The D programming language also offers fully generic-capable templates based on the C++ precedent but with a simplified syntax. The Java programming language has provided generic programming facilities syntactically based on C++'s since the introduction of
J2SE5.0 and implements the "generics" subset of generic programming.
Although the examples above are a common use of generic programming, and some languages implement only this aspect of it, the concept of generic programming is not limited to "generics" as a programming language construct. In Python, a language with strong, dynamic typing, generic programming is both transparent and also the simplest way to write routines. For example, the preceding example can be translated into Python if a box class is created to simulate the C++ notion of call-by-reference.
C# 2.0, Chrome 1.5 and Visual Basic .NET 2005 have constructs that take advantage of the support for generics present in the Microsoft .NET Framework since version 2.0. The ML family of programming languages encourage generic programming through parametric polymorphism and generic modules called "functors." The
type classmechanism of Haskell supports generic programming. 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. While 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.
Generics in Ada
Ada has had generics since it was first designed in 1977-1980. The standard libraryuses generics to provide many services. Ada 2005 adds a comprehensive genericcontainer library to the standard library, which was inspired by C++'s standardtemplate library.
A "generic unit" is a package or a subprogram that takes one or more"generic formal parameters".
A "generic formal parameter" is a value, a variable, a constant, a type, asubprogram, or even an instance of another, designated, generic unit.For generic formal types, the syntax distinguishes between discrete, floating-point,fixed-point, access (pointer) types, etc. Some formal parameters can have default values.
To "instantiate" a generic unit, the programmer passes "actual" parametersfor each formal. The generic instance then behaves just like any other unit.It is possible to instantiate generic units at run-time, for example insidea loop.
The specification of a generic package:
Instantiating the generic package:
Using an instance of a generic package:
Advantages and limitations
The language syntax allows precise specification of constraints on genericformal parameters. For example, it is possible to specify that a generic formaltype will only accept a modular type as the actual. It is also possible to express constraints "between"generic formal parameters; for example:
In this example, Array_Type is constrained by both Index_Type and Element_Type.When instantiating the unit, the programmer must pass an actual array type thatsatisfies these constraints.
The disadvantage of this fine-grained control is a complicated syntax, but, becauseall generic formal parameters are completely defined in the specification, the compilercan instantiate generics without looking at the body of the generic.
Unlike C++, Ada does not allow specialised generic instances, and requires that allgenerics be instantiated explicitly. These rules have several consequences:
* the compiler can implement "shared generics": the object code for a generic unit can be shared between all instances (unless the programmer requests inlining of subprograms, of course). As further consequences:
** there is no possibility of code bloat (code bloat is common in C++ and requires special care, as explained below).
** it is possible to instantiate generics at run time, as well as at compile time, since no new object code is required for a new instance.
** actual objects corresponding to a generic formal object are always considered to be nonstatic inside the generic; see in the Wikibook for details and consequences.
* all instances of a generic being exactly the same, it is easier to review and understand programs written by others; there are no "special cases" to take into account.
* all instantiations being explicit, there are no hidden instantiations that might make it difficult to understand the program.
* Ada does not permit "template metaprogramming", because it does not allow specialisations.
Templates in C++
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 a framework of connected templates. Templates in C++ may also be used for template metaprogramming, which is a way of pre-evaluating some of the code at compile-time rather than run-time.
There are two kinds of templates: function templates and class templates. A "function template" is a pattern for creating ordinary functions based upon the parameterizing types supplied when instantiated. For example, the C++ Standard Template Library contains the function template
max(x, y)which creates functions that return either "x" or "y," whichever is larger.
max()could be defined like this:
"Specializations" of this function template, instantiations with specific types, can be called just like an ordinary function:
The compiler examines the arguments used to call
maxand determines that this is a call to
max(int, int). It then instantiates a version of the function where the parameterizing type
int, making the equivalent of the following function:
This works whether the arguments
yare integers, strings, or any other type for which the expression
x < yis sensible, or more specifically, for any type for which
operator<is defined. Common inheritance is not needed for the set of types that can be used, and so it is very similar to duck typing. A program defining a custom data type can use operator overloading to define the meaning of
<for that type, thus allowing its use with the
max()function template. 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
binary_search()algorithms or be put inside data structures such as
sets, heaps, and associative arrays.
C++ templates are completely type safe at compile time. As a demonstration, the standard type
complexdoes 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
complexvalues. Likewise, other templates that rely on
<cannot be applied to
complexdata. Unfortunately, compilers historically generate somewhat esoteric, long, and unhelpful error messages for this sort of error. Ensuring that a certain object adheres to a method protocol can alleviate this issue.
The second kind of template, a "class template," extends the same concept to classes. A class template specialization is a class. Class templates are often used to make generic containers. For example, the STL has a
linked listcontainer. To make a linked list of integers, one writes
list<int>. A list of strings is denoted
listhas a set of standard functions associated with it, which work for any compatible parameterizing types.
Unlike function templates, class templates can be "partially specialized." That means that an alternate version of the class template code can be provided when some of the template parameters are known, while leaving other template parameters generic. This can be used, for example, to create a default implementation (the "primary specialization") that assumes that copying a parameterizing type is expensive and then create partial specializations for types that are cheap to copy, thus increasing overall efficiency. Clients of such a class template just use specializations of it without needing to know whether the compiler used the primary specialization or some partial specialization in each case. Class templates can also be "fully specialized," which means that an alternate implementation can be provided when all of the parameterizing types are known.
A powerful feature of C++'s templates is "template specialization". This allows alternative implementations to be provided based on certain characteristics of the parameterized type that is being instantiated. Template specialization has two purposes: to allow certain forms of optimization, and to reduce code bloat.
For example, consider a
sort()template function. One of the primary activities that such a function does is to swap or exchange the values in two of the container's positions. If the values are large (in terms of the number of bytes it takes to store each of them), then it is often quicker to first build a separate list of pointers to the objects, sort those pointers, and then build the final sorted sequence. If the values are quite small however it is usually fastest to just swap the values in-place as needed. Furthermore if the parameterized type is already of some pointer-type, then there is no need to build a separate pointer array. Template specialization allows the template creator to write different implementations and to specify the characteristics that the parameterized type(s) must have for each implementation to be used.
Advantages and disadvantages
Some uses of templates, such as the
max()function, were previously filled by function-like
preprocessormacros (a legacy of the C programming language). For example, here is a possible
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: compiler support, poor error messages, and code bloat.Many compilers historically have poor support for templates, thus the use of templates can make code somewhat less portable. Support may also be poor when a C++ compiler is being used with a
linkerwhich is not C++-aware, or when attempting to use templates across shared library boundaries. Most modern compilers however now have fairly robust and standard template support, and the new C++ standard, C++0x, is expected to further address these issues.
Almost all compilers produce confusing, long, or sometimes unhelpful error messages when errors are detected in code that uses templates. This can make templates difficult to develop.
Finally, the use of templates requires the compiler to generate a separate "instance" of the templated class or function for every
permutationof type parameters used with it. (This is necessary because types in C++ are not all the same size, and the sizes of data fields are important to how classes work.) So the indiscriminate use of templates can lead to code bloat, resulting in excessively large executables. However, judicious use of template specialization can dramatically reduce such code bloat in some cases. 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.
Also, because the compiler needs to perform macro-like expansions of templates and generate different instances of them at compile time, the implementation source code for the templated class or function must be available (e.g. included in a header) to the code using it. Templated classes or functions, including much of the Standard Template Library (STL), cannot be compiled. (This is in contrast to non-templated code, which may be compiled to binary, providing only a declarations header file for code using it.) This may be a disadvantage by exposing the implementing code, which removes some abstractions, and is bad for closed-source projects.
Templates in D
D programming languagesupports templates that are evolved from those in C++. Most C++ template idioms will carry over to D without alteration, but D adds functionality that streamlines some common cases.
The most obvious differences are syntax changes. D uses parentheses ( ) instead of angle-brackets < > in a template definition. It also uses the !( ) construct (that is, parentheses preceded by an exclamation point) instead of angle-brackets in template instantiation. Therefore,
a!(b)in D is the equivalent of
a<b>in C++. These changes were made in the interest of making templates easier to parse, as using angle-brackets can lead to ambiguous syntax.
D provides a
static ifconstruct that checks conditions at compile-time. This is vaguely analogous to C++'s
#endifpreprocessor macros. The major difference is that
static ifhas access to all compile-time values, including template arguments. Therefore, many situations which require template specialization in C++ may be written inline in D. Recursive templates in D can look almost identical to their runtime equivalents. This is shown in the classic compile-time factorial template.
Templates in D may also accept alias parameters. Alias parameters are similar to C++'s
typedefbut can also substitute templates parameters. This is a superset of the functionality of template arguments in C++, and will be added in the forthcoming
C++0xspecification. Alias parameters may be templates, functions, types, or any other compile-time symbol. This allows a coder to, for example, "inject" a function into the middle of a template function.
This sort of template might be useful when interfacing D code with a C API. If a hypothetical C API wants a function pointer, you might use the template like this:
Generics in Java
Support for the "generics", or "containers-of-type-T", subset of generic programming were added to the Java programming language in 2004 as part of J2SE 5.0. In Java, generics are checked at compile time for type correctness. The generic type information is then removed via a process called
type erasure, and is unavailable at runtime. For example, a
List<String>is converted to the raw type
List. The compiler inserts type casts to convert the elements to the
Stringtype when they are retrieved from the list.
Generic programming in C# and .NET
Generics in C# (and other .NET languages) were added as part of .NET Framework 2.0 in
November 2005. Although similar to generics in Java, .NET generics do not apply type erasure, but implement generics as a first class citizen in the runtime using reification. This design choice is leveraged to provide additional functionality, such as allowing reflection with preservation of generic types, as well as alleviating some of the limitations of erasure (such as being unable to create generic arrays). [ [http://www.ondotnet.com/pub/a/dotnet/2005/10/17/interview-with-anders-hejlsberg.html C#: Yesterday, Today, and Tomorrow: An Interview with Anders Hejlsberg] ] [ [http://www.artima.com/intv/generics2.html Generics in C#, Java, and C++] ] This also means that there is no performance hit from runtime casts and expensive boxing conversions. When primitive and value types are used as generic arguments, they get specialized implementations, allowing for efficient generic collections and methods. As in C++ and Java, nested generic types such as
Dictionary<string, List<int>>are valid types.
C# (and .NET in general) allows six generic type constraints using the
wherekeyword including restricting generic types to be value types, to be classes, to have constructors, and to inherit from interfaces. [ [http://msdn2.microsoft.com/en-us/library/d5x73970.aspx Constraints on Type Parameters (C# Programming Guide)] ] Below is an example with an interface constraint:
Since all arrays implement the
IListinterface (commonly associated with list classes), the
MakeAtLeast()method allows operation on arrays, with elements of type
T. The method's type constraint indicates that the method is applicable to any type
Tthat implements the generic
IComparable<T>interface. This ensures a
compile timeerror if the method is called with a list of another type. The interface provides the generic method
The above method could also be written without generic types, simply using the non-generic
IListtype. However, this would make the method less
type safe, as it would allow the method to be applied to a list of incomparable items, resulting in a run time error. The method would need to access the list items as objects instead, and would require casting to compare two elements. (For value types like types such as
intthis requires a boxing conversion, although this can be worked around using the
Comparer<T>class, as is done in the standard collection classes.)
Generic programming in Functional languages
Generic programming in Haskell
Six of the predefined type classes in Haskell (including
Eq, the types that can be compared for equality, and
Show, the types whose values can be rendered as strings) have the special property of supporting "derived instances." This means that a programmer defining a new type can state that this type is to be an instance of one of these special type classes, without providing implementations of the class methods as is usually necessary when declaring class instances. All the necessary methods will be "derived" -- that is, constructed automatically -- based on the structure of the type.For instance, the following declaration of a type of
binary trees states that it is to be an instance of the classes
This results in an equality function (
=) and a string representation function (
show) being automatically defined for any type of the form
BinTree Tprovided that
Titself supports those operations.
The support for derived instances of
Showmakes their methods
showgeneric in a qualitatively different way from parametrically polymorphic functions: these "functions" (more accurately, type-indexed families of functions) can be applied to values of various types, and although they behave differently for every argument type, little work is needed to add support for a new type. Ralf Hinze (2004) has shown that a similar effect can be achieved for user-defined type classes by certain programming techniques. Other researchers have proposed approaches to this and other kinds of genericity in the context of Haskell and extensions to Haskell (discussed below).
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:
Generic Haskell is another extension to Haskell, developed at
Utrecht Universityin The Netherlands. 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: [ [http://www.cs.uu.nl/research/projects/generic-haskell/compiler/diamond/GHUsersGuide.pdf The Generic Haskell User's Guide] ]
The "Scrap your boilerplate" approach
The "Scrap your boilerplate" approach is a lightweight generic programming approach for Haskell (Lämmel and Peyton Jones, 2003). A [http://www.cs.vu.nl/boilerplate/ web site] for this approach explains which components of it are currently implemented in GHC.
Clean offers generic programming based PolyP and the generic Haskell as supported by the GHC>=6.0. It parametrizes by kind as those but offers overloading.
Generic programming features in other languages
Standard MLand OCamlprovide functors, which are similar to class templates and to Ada's generic packages. Scheme syntactic abstractions also have connection to generic programming -- these are in fact a superset of templating a la C++.
Concept (generic programming)
External links and references
* Bertrand Meyer. " [http://se.ethz.ch/~meyer/publications/acm/geninh.pdf Genericity vs Inheritance] ." In "OOPSLA (First ACM Conference on Object-Oriented Programming Systems, Languages and Applications)," Portland (Oregon), September 29–October 2, 1986, pages 391–405.
* Gabriel Dos Reis and Jaakko Järvi, " [http://lcsd05.cs.tamu.edu/papers/dos_reis_et_al.pdf What is Generic Programming?] ," [http://lcsd05.cs.tamu.edu LCSD 2005] .
* Alexander A. Stepanov, [http://www.stepanovpapers.com/ Collected Papers of Alexander A. Stepanov] (creator of the STL)
* Walter Bright, " [http://www.digitalmars.com/d/templates-revisited.html Templates Revisited] ."
* David Vandevoorde, "C++ Templates: The Complete Guide", 2003 Addison-Wesley. ISBN 0-201-73484-2
* Jason Clark, " [http://msdn.microsoft.com/msdnmag/issues/03/09/NET/ Introducing Generics in the Microsoft CLR] ," September 2003, "MSDN Magazine", Microsoft.
* Jason Clark, " [http://msdn.microsoft.com/msdnmag/issues/03/10/NET/ More on Generics in the Microsoft CLR] ," October 2003, "MSDN Magazine", Microsoft.
* M. Aamir Maniar, [http://codeplex.com/Wiki/View.aspx?ProjectName=genericsnet Generics.Net] . An open source generics library for C#.
* Dæv Clarke, Johan Jeuring and Andres Löh, [http://www.cs.uu.nl/research/projects/generic-haskell/compiler/diamond/GHUsersGuide.pdf The Generic Haskell user's guide]
* Ralf Hinze, " [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP04.pdf Generics for the Masses] ," In "Proceedings of the ACM
SIGPLAN International Conference on Functional Programming(ICFP)," 2004.
Simon Peyton Jones, editor, " [http://haskell.org/onlinereport/index.html The Haskell 98 Language Report] ," Revised 2002.
Ralf Lämmeland Simon Peyton Jones, "Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming," In "Proceedings of the ACM SIGPLANInternational Workshop on Types in Language Design and Implementation (TLDI'03)," 2003. (Also see the website [http://www.cs.vu.nl/boilerplate/ devoted to this research] )
* Andres Löh, " [http://www.cs.uu.nl/~andres/ExploringGH.pdf Exploring Generic Haskell] ," Ph.D. thesis, 2004
Utrecht University. ISBN 90-393-3765-9
* [http://www.generic-haskell.org/ Generic Haskell: a language for generic programming]
* Gilad Bracha, " [http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf Generics in the Java Programming Language] ," 2004.
* Maurice Naftalin and Philip Wadler, "Java Generics and Collections," 2006, O'Reilly Media, Inc. ISBN 0-596-52775-6
* Peter Sestoft, "Java Precisely, Second Edition," 2005 MIT Press. ISBN 0-262-69325-9
*, 2004 Sun Microsystems, Inc.
* [http://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.html Java Generics FAQs]
* Object Pascal: [http://www.freepascal.org/docs-html/ref/refch8.html Free Pascal Reference guide Chapter 8: Generics] , Michaël Van Canneyt, 2007
* Delphi: [http://www.felix-colibri.com/papers/oop_components/delphi_generics_tutorial/delphi_generics_tutorial.html : Delphi Generics] , Felix COLIBRI, 2008
Wikimedia Foundation. 2010.