4.5.4.2 Generic programming in object-oriented languages
When creating containers of objects it is possible to write specificimplementations for each datatype contained, even if the code is virtuallyidentical except for different datatypes. In C++, this duplication of codecan be circumvented by defining a template class:
| Example |
|---|
template<typename T>
class List
{
/* class contents */
};
List<Animal> list_of_animals;
List<Car> list_of_cars;
|
Above, T is a placeholder for whatever type is specified when the list iscreated. These "containers-of-type-T", commonly called generics, are ageneric programming technique allowing a class to be reused with differentdatatypes as long as certain contracts such as subtypes and signature arekept. 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 Animaland Car. Generics can also be used for type-independent functions as inthe Swap example below:
| Example |
|---|
template<typename T>
void Swap(T & a, T & b) //"&" passes parameters by reference
{
T temp = b;
b = a;
a = temp;
}
string hello = "world!", world = "Hello, ";
Swap( world, hello );
cout << hello << world << endl; //Output is "Hello, world!"
|
The C++ template construct used above is widely cited as the genericprogramming construct that popularized the notion among programmers andlanguage designers and supports many generic programming idioms. The Dprogramming language also offers fully generic-capable templates basedon the C++ precedent but with a simplified syntax. The Java programminglanguage has provided generic programming facilities syntactically basedon C++'s since the introduction of J2SE 5.0 and implements the genericssubset of generic programming.
Although the examples above are a common use of generic programming, andsome languages implement only this aspect of it, the concept of genericprogramming is not limited to "generics" as a programming language Python, a language with strong, dynamic typing, generic programmingis both transparent and also the simplest way to write routines. Forexample, the preceding example can be translated into Python if a boxclass is created to simulate the C++ notion of call-by-reference.
| Example |
|---|
class Box:
def __init__(self,ob):
= ob
def swap(box1,box2):
, = ,
|
C# 2.0, Chrome 1.5 and Visual Basic .NET 2005 have constructs that takeadvantage of the support for generics present in the Microsoft .NETFramework since version 2.0. The ML family of programming languages encouragegeneric programming through parametric polymorphism and generic modules calledfunctors. The type class mechanism 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 programmingtechniques, since there exists a general type to contain any object. WhileJava does so also, the casting that needs to be done breaks the disciplineof static typing, and generics are one way of achieving some of the benefitsof 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 standardlibrary uses generics to provide many services. Ada 2005 adds a comprehensivegeneric container library to the standard library, which was inspired by C++'sstandard template library.
A generic unit is a package or a subprogram that takes one or more genericformal parameters.
A generic formal parameter is a value, a variable, a constant, a type,a subprogram, or even an instance of another, designated, generic unit. Forgeneric formal types, the syntax distinguishes between discrete, floating-point,fixed-point, access (pointer) types, etc. Some formal parameters can havedefault values.
To instantiate a generic unit, the programmer passes actual parametersfor each formal. The generic instance then behaves just like any otherunit. It is possible to instantiate generic units at run-time, for exampleinside a loop.
Ada example
The specification of a generic package:
| Example |
|---|
generic
Max_Size : Natural; -- a generic formal value
type Element_Type is private; -- a generic formal type; accepts any
nonlimited type
package Stacks is
type Size_Type is range 0 .. Max_Size;
type Stack is limited private;
procedure Create (S : out Stack;
Initial_Size : in Size_Type := Max_Size);
procedure Push (Into : in out Stack; Element : in Element_Type);
procedure Pop (From : in out Stack; Element : out Element_Type);
Overflow : exception;
Underflow : exception;
private
subtype Index_Type is Size_Type range 1 .. Max_Size;
type Vector is array (Index_Type range <>) of Element_Type;
type Stack (Allocated_Size : Size_Type := 0) is record
Top : Index_Type;
Storage : Vector (1 .. Allocated_Size);
end record;
end Stacks;
|
Instantiating the generic package:
| Example |
|---|
type Bookmark_Type is new Natural;
-- records a location in the text document we are editing
package Bookmark_Stacks is new Stacks (Max_Size => 20,
Element_Type => Bookmark_Type);
-- Allows the user to jump between recorded locations in a document
|
Using an instance of a generic package:
| Example |
|---|
type Document_Type is record Contents : .Unbounded_String; Bookmarks : Bookmark_Stacks.Stack; end record; procedure Edit (Document_Name : in String) is Document : Document_Type; begin -- Initialise the stack of bookmarks: Bookmark_Stacks.Create (S => , Initial_Size => 10); -- Now, open the file Document_Name and read it in... end Edit; |
Advantages and limitations
The language syntax allows precise specification of constraints on genericformal parameters. For example, it is possible to specify that a genericformal type will only accept a modular type as the actual. It is alsopossible to express constraints between generic formal parameters; forexample:
| Example |
|---|
generic type Index_Type is (<>); -- must be a discrete type type Element_Type is private; -- can be any nonlimited type type Array_Type is array (Index_Type range <>) of Element_Type; |
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,because all generic formal parameters are completely defined in the specification,the compiler can instantiate generics without looking at the body of the generic.
Unlike C++, Ada does not allow specialised generic instances, and requiresthat all generics be instantiated explicitly. These rules have several consequences:
the compiler can implement shared generics: the object code for ageneric unit can be shared between all instances (unless the programmerrequests inlining of subprograms, of course).As further consequences:
- there is no possibility of code bloat (code bloat is common inC++ and requires special care, as explained below).
- it is possible to instantiate generics at run time, as well asat compile time, since no new object code is required for a new instance.
- actual objects corresponding to a generic formal object arealways considered to be nonstatic inside the generic; seeGeneric formal objects in the Wikibook for details and consequences.
all instances of a generic being exactly the same, it is easier toreview and understand programs written by others; there are no"special cases" to take into account.
all instantiations being explicit, there are no hidden instantiationsthat might make it difficult to understand the program.
Ada does not permit "template metaprogramming", because it does notallow specialisations.
Templates in C++
Templates are of great utility to programmers in C++, especially when combinedwith multiple inheritance and operator overloading. The C++ Standard TemplateLibrary (STL) provides a framework of connected templates. Templates in C++may also be used for template metaprogramming, which is a way of pre-evaluatingsome of the code at compile-time rather than run-time. Due to Templatespecialization, C++ Templates are considered turing complete.
Technical overview
There are two kinds of templates: function templates and class function template is a pattern for creating ordinary functions basedupon 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 () could be defined like this:
| Example |
|---|
template <typename T>
T max(T x, T y)
{
if (x < y)
return y;
else
return x;
}
|
Specializations of this function template, instantiations with specifictypes, can be called just like an ordinary function:
| Example |
|---|
cout << max(3, 7); // outputs 7 |
The compiler examines the arguments used to call max and determines thatthis is a call to max(int, int). It then instantiates a version of thefunction where the parameterizing type T is int, making the equivalentof the following function:
| Example |
|---|
int max(int x, int y)
{
if (x < y)
return y;
else
return x;
}
|
This works whether the arguments x and y are integers, strings, or anyother type for which the expression x < y is sensible, or more specifically,for any type for which operator< is defined. Common inheritance is notneeded for the set of types that can be used, and so it is very similarto duck typing. A program defining a custom data type can use operatoroverloading to define the meaning of < for that type, thus allowing itsuse with the max() function template. While this may seem a minor benefitin this isolated example, in the context of a comprehensive library likethe STL it allows the programmer to get extensive functionality for anew data type, just by defining a few operators for it. Merelydefining < allows a type to be used with the standard sort(), stable_sort(),and binary_search() algorithms or to be put inside data structures suchas sets, heaps, and associative arrays.
C++ templates are completely type safe at compile time. As a demonstration,the standard type complex does not define the < operator, because thereis no strict order on complex numbers. Therefore max(x, y) will fail witha compile error if x and y are complex values. Likewise, other templatesthat rely on < cannot be applied to complex data. Unfortunately,compilers historically generate somewhat esoteric, long, and unhelpfulerror messages for this sort of error. Ensuring that a certain objectadheres to a method protocol can alleviate this issue.
The second kind of template, a class template, extends the same conceptto classes. A class template specialization is a class. Class templatesare often used to make generic containers. For example, the STL has alinked list container. To make a linked list of integers, one writeslist<int>. A list of strings is denoted list<string>. A list has a setof standard functions associated with it, which work for any compatibleparameterizing types.
Template specialization
A powerful feature of C++'s templates is template specialization. Thisallows alternative implementations to be provided based on certaincharacteristics of the parameterized type that is being specialization has two purposes: to allow certain forms ofoptimization, and to reduce code bloat.
For example, consider a sort() template function. One of the primaryactivities that such a function does is to swap or exchange the valuesin two of the container's positions. If the values are large (in termsof the number of bytes it takes to store each of them), then it is oftenquicker to first build a separate list of pointers to the objects, sortthose pointers, and then build the final sorted sequence. If the valuesare quite small however it is usually fastest to just swap the valuesin-place as needed. Furthermore if the parameterized type is alreadyof some pointer-type, then there is no need to build a separate pointerarray. Template specialization allows the template creator to writedifferent implementations and to specify the characteristics that theparameterized type(s) must have for each implementation to be used.
Unlike function templates, class templates can be partially means that an alternate version of the class template code can beprovided when some of the template parameters are known, while leavingother template parameters generic. This can be used, for example, tocreate a default implementation (the primary specialization) that assumesthat copying a parameterizing type is expensive and then create partialspecializations for types that are cheap to copy, thus increasing overallefficiency. Clients of such a class template just use specializations ofit without needing to know whether the compiler used the primaryspecialization or some partial specialization in each case. Classtemplates can also be fully specialized, which means that an alternateimplementation can be provided when all of the parameterizing types are known.
Advantages and disadvantages
Some uses of templates, such as the max() function, were previously filledby function-like preprocessor macros (a legacy of the C programming language).For example, here is a possible max() macro:
| Example |
|---|
#define max(a,b) ((a) < (b) ? (b) : (a)) |
Both macros and templates are expanded at compile time. Macros are alwaysexpanded inline; templates can also be expanded as inline functions whenthe compiler deems it appropriate. Thus both function-like macros andfunction templates have no run-time overhead.
However, templates are generally considered an improvement over macrosfor these purposes. Templates are type-safe. Templates avoid some of thecommon errors found in code that makes heavy use of function-like most importantly, templates were designed to be applicable tomuch 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 poorsupport for templates, thus the use of templates can make code somewhatless portable. Support may also be poor when a C++ compiler is being usedwith a linker which is not C++-aware, or when attempting to use templatesacross shared library boundaries. Most modern compilers however now havefairly 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 errormessages when errors are detected in code that uses templates. This canmake templates difficult to develop.
Finally, the use of templates requires the compiler to generate a separateinstance of the templated class or function for every permutation of typeparameters used with it. (This is necessary because types in C++ are notall the same size, and the sizes of data fields are important to howclasses work.) So the indiscriminate use of templates can lead to codebloat, resulting in excessively large executables. However, judicioususe of template specialization can dramatically reduce such code bloatin some cases. The extra instantiations generated by templates can alsocause debuggers to have difficulty working gracefully with example, setting a debug breakpoint within a template from a sourcefile may either miss setting the breakpoint in the actual instantiationdesired or may set a breakpoint in every place the template is instantiated.
Also, because the compiler needs to perform macro-like expansions of templatesand generate different instances of them at compile time, the implementationsource code for the templated class or function must be available ( 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 bea disadvantage by exposing the implementing code, which removes someabstractions, and could restrict its use in closed-source projects.
Templates in D
The D programming language supports templates that are evolved from thosein 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 usesthe !( ) construct (that is, parentheses preceded by an exclamation point)instead of angle-brackets in template instantiation. Therefore, a!(b) inD is the equivalent of a<b> in C++. These changes were made in the interestof making templates easier to parse, as using angle-brackets can lead toambiguous syntax.
Static-if
D provides a static if construct that checks conditions at is vaguely analogous to C++'s #if and #endif preprocessor major difference is that static if has access to all compile-timevalues, including template arguments. Therefore, many situations whichrequire template specialization in C++ may be written inline in templates in D can look almost identical to their runtimeequivalents. This is shown in the classic compile-time factorial template.
| Example |
|---|
template factorial(uint n) {
static if (n < 2)
const uint factorial = 1;
else
const uint factorial = n * factorial!(n-1);
}
|
Alias parameters
Templates in D may also accept alias parameters. Alias parameters aresimilar to C++'s typedef but can also substitute templates is a superset of the functionality of template arguments in C++,and will be added in the forthcoming C++0x specification. Alias parametersmay be templates, functions, types, or any other compile-time allows a coder to, for example, "inject" a function into the middleof a template function.
| Example |
|---|
template wrapper(alias Fn) {
// Wraps a D function with an "extern(C)" interface.
extern(C) void wrapper() {
Fn();
}
}
|
This sort of template might be useful when interfacing D code with a C a hypothetical C API wants a function pointer, you might use thetemplate like this:
| Example |
|---|
void foo() {
// ...
}
some_c_function(&wrapper!(foo));
|
Generics in Java
Support for the generics, or "containers-of-type-T", subset of genericprogramming were added to the Java programming language in 2004 as partof J2SE 5.0. In Java, generics are checked at compile time for typecorrectness. The generic type information is then removed via a processcalled type erasure, and is unavailable at runtime. For example, aList<String> is converted to the raw type List. The compiler insertstype casts to convert the elements to the String type when they areretrieved from the list.
Generic programming in C# and .NET
Generics in C# (and other .NET languages) were added as part of .NETFramework 2.0 in November 2005. Although similar to generics in Java,.NET generics do not apply type erasure, but implement generics as a firstclass object in the runtime using reification. This design choice isleveraged to provide additional functionality, such as allowing reflectionwith preservation of generic types, as well as alleviating some of thelimitations of erasure (such as being unable to create generic arrays).This also means that there is no performance hit from runtime casts andnormally expensive boxing conversions. When primitive and value types areused as generic arguments, they get specialized implementations, allowingfor efficient generic collections and methods. As in C++ and Java, nestedgeneric types such as Dictionary<string, List<int>> are valid types.
C# (and .NET in general) allows six varieties of generic type constraintsusing the where keyword including restricting generic types to be valuetypes, to be classes, to have constructors, and to inherit from is an example with an interface constraint:
| Example |
|---|
class Sample
{
public static void Main()
{
int[] list = { 0, 1, 2, 3 };
MakeAtLeast<int>(list, 2); // change array to { 2, 2, 2, 3 }
}
public static void MakeAtLeast<T>(IList<T> list, T lowest) where T : IComparable<T>
{
for (int i = 0; i < ; i++)
if (list[i].CompareTo(lowest) < 0) list[i] = lowest;
}
}
|
Since all arrays implement the IList<T> interface (commonly associatedwith list classes), the MakeAtLeast() method allows operation on arrays,with elements of type T. The method's type constraint indicates that themethod is applicable to any type T that implements the generic IComparable<T>interface. This ensures a compile time error if the method is called witha list of another type. The interface provides the generic method CompareTo(T).
The above method could also be written without generic types, simply usingthe non-generic IList type. However, this would make the method less typesafe, as it would allow the method to be applied to a list of incomparableitems, resulting in a run time error. The method would need to access thelist items as objects instead, and would require casting to compare twoelements. (For value types like types such as int this requires a boxingconversion, although this can be worked around using the Comparer<T> class,as is done in the standard collection classes.)
Generic programming in Delphi
Generic support was added to Delphi language in October 2008. The firstgeneric support to Generics was Delphi 2007 .NET in 2006, but it was onlyfor .NET platform, and real support for Generics in Delphi was add in Delphi 2009.