Genericity facilities have existed in high-level languages since at least the 1970s in languages such as
ML,
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-Owl. Genericity is implemented and supported differently in various programming languages; the term "generic" has also been used differently in various 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
genericity capacities that, however, are not referred to as such in most Forth texts. Similarly, dynamically typed languages, especially interpreted ones, usually offer
genericity by default as both passing values to functions and value assignment are type-indifferent and such behavior is often used for abstraction or code terseness, however this is not typically labeled
genericity as it's a direct consequence of the dynamic typing system employed by the language. The term has been used in
functional programming, specifically in
Haskell-like languages, which use a
structural type system where types are always parametric and the actual code on those types is generic. These uses still serve a similar purpose of code-saving and rendering an abstraction.
Arrays and
structs can be viewed as predefined generic types. Every usage of an array or struct type instantiates a new concrete type, or reuses a previous instantiated type. Array element types and struct element types are parameterized types, which are used to instantiate the corresponding generic type. All this is usually built-in in the
compiler and the syntax differs from other generic constructs. Some
extensible programming languages try to unify built-in and user defined generic types. A broad survey of genericity mechanisms in programming languages follows. For a specific survey comparing suitability of mechanisms for generic programming, see.
In object-oriented languages When creating container classes in statically typed languages, it is inconvenient to write specific implementations for each datatype contained, especially if the code for each datatype is virtually identical. For example, in C++, this duplication of code can be circumvented by defining a class template: class Animal { // ... }; class Car { // ... }; template class MyList { // Class contents. }; MyList animalList; MyList carList; Above, T is a placeholder for whatever type is specified when the list is created. These "containers-of-type-T", commonly called
templates, allow a class to be reused with different datatypes as long as certain contracts such as
subtypes and
signature are kept. This genericity mechanism should not 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. Templates can also be used for type-independent functions as in the Swap example below: import std; using std::string; // A similar, but safer and potentially faster function // is defined in the standard library header template void swap(T& a, T& b) noexcept { T temp = b; b = a; a = temp; } int main(int argc, char* argv[]) { string world = "World!"; string hello = "Hello,"; swap(world, hello); std::println("{} {}", world, hello); // Output is "Hello, World!". } The C++ template construct used above is widely cited as the genericity construct that popularized the notion among programmers and
language designers and supports many generic programming idioms. The D language also offers fully generic-capable templates based on the C++ precedent but with a simplified syntax. The Java language has provided genericity facilities syntactically based on C++'s since the introduction of
Java Platform, Standard Edition (J2SE) 5.0.
C# 2.0,
Oxygene 1.5 (formerly Chrome) and
Visual Basic (.NET) 2005 have constructs that exploit the support for generics present in Microsoft
.NET Framework since version 2.0.
Generics in Ada Ada has had generics since it was first designed in 1977–1980. The
standard library uses generics to provide many services. Ada 2005 adds a comprehensive generic container library to the standard library, which was inspired by C++'s
Standard Template 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, a subprogram, 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 parameters for each formal. The generic instance then behaves just like any other unit. It is possible to instantiate generic units at
run-time, for example, inside a loop. This can make templates difficult to develop with. • Finally, the use of templates requires the compiler to generate a separate
instance of the templated class or function for every 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 and derivation can dramatically reduce such code bloat in some cases: • Templated classes or functions may require an
explicit specialization of the template class which would require rewriting of an entire class for a specific template parameters used by it. The extra instantiations generated by templates can also cause some 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, the implementation source code for the template must be completely available (e.g. included in a header) to the translation unit (source file) using it. Templates, including much of the Standard Library, if not included in header files, 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 could restrict its use in closed-source projects.
Templates in D The
D language supports templates based in design on C++. Most C++ template idioms work in D without alteration, but D adds some functionality: • Template parameters in D are not restricted to just types and primitive values (as it was in C++ before C++20), but also allow arbitrary compile-time values (such as strings and struct literals), and aliases to arbitrary identifiers, including other templates or template instantiations. • Template constraints and the static if statement provide an alternative to respectively C++'s
C++ concepts and if constexpr. • The is(...) expression allows speculative instantiation to verify an object's traits at compile time. • The auto keyword and the
typeof expression allow
type inference for variable declarations and function return values, which in turn allows "Voldemort types" (types that do not have a global name). Templates in D use a different syntax than in C++: whereas in C++ template parameters are wrapped in angular brackets (Template), D uses an exclamation sign and parentheses: Template!(param1, param2). This avoids the
C++ parsing difficulties due to ambiguity with comparison operators. If there is only one parameter, the parentheses can be omitted. Conventionally, D combines the above features to provide
compile-time polymorphism using trait-based generic programming. For example, an input
range is defined as any type that satisfies the checks performed by isInputRange, which is defined as follows: template isInputRange(R) { enum bool isInputRange = is(typeof((inout int = 0) { R r = R.init; // can define a range object if (r.empty) {} // can test for empty r.popFront(); // can invoke popFront() auto h = r.front; // can get the front of the range })); } A function that accepts only input ranges can then use the above template in a template constraint: auto fun(Range)(Range range) if (isInputRange!Range) { // ... }
Code generation In addition to template metaprogramming, D also provides several features to enable compile-time code generation: • The import expression allows reading a file from disk and using its contents as a string expression. • Compile-time reflection allows enumerating and inspecting declarations and their members during compiling. • User-defined
attributes allow users to attach arbitrary identifiers to declarations, which can then be enumerated using compile-time reflection. •
Compile-time function execution (CTFE) allows a subset of D (restricted to safe operations) to be interpreted during compiling. • String mixins allow evaluating and compiling the contents of a string expression as D code that becomes part of the program. Combining the above allows generating code based on existing declarations. For example, D serialization frameworks can enumerate a type's members and generate specialized functions for each serialized type to perform serialization and deserialization. User-defined attributes could further indicate serialization rules. The import expression and compile-time function execution also allow efficiently implementing
domain-specific languages. For example, given a function that takes a string containing an HTML template and returns equivalent D source code, it is possible to use it in the following way: // Import the contents of example.htt as a string manifest constant. enum htmlTemplate = import("example.htt"); // Transpile the HTML template to D code. enum htmlDCode = htmlTemplateToD(htmlTemplate); // Paste the contents of htmlDCode as D code. mixin(htmlDCode);
Genericity in Eiffel Generic classes have been a part of
Eiffel since the original method and language design. The foundation publications of Eiffel, use the term
genericity to describe creating and using generic classes.
Basic, unconstrained genericity Generic classes are declared with their class name and a list of one or more
formal generic parameters. In the following code, class LIST has one formal generic parameter G class LIST [G] ... feature -- Access item: G -- The item currently pointed to by cursor ... feature -- Element change put (new_item: G) -- Add `new_item' at the end of the list ... The formal generic parameters are placeholders for arbitrary class names that will be supplied when a declaration of the generic class is made, as shown in the two
generic derivations below, where ACCOUNT and DEPOSIT are other class names. ACCOUNT and DEPOSIT are considered
actual generic parameters as they provide real class names to substitute for G in actual use. list_of_accounts: LIST [ACCOUNT] -- Account list list_of_deposits: LIST [DEPOSIT] -- Deposit list Within the Eiffel type system, although class LIST [G] is considered a class, it is not considered a type. However, a generic derivation of LIST [G] such as LIST [ACCOUNT] is considered a type.
Constrained genericity For the list class shown above, an actual generic parameter substituting for G can be any other available class. To constrain the set of classes from which valid actual generic parameters can be chosen, a
generic constraint can be specified. In the declaration of class SORTED_LIST below, the generic constraint dictates that any valid actual generic parameter will be a class that inherits from class COMPARABLE. The generic constraint ensures that elements of a SORTED_LIST can in fact be sorted. class SORTED_LIST [G -> COMPARABLE]
Generics in Java Support for the
generics, or "containers-of-type-T" was added to the
Java programming language in 2004 as part of J2SE 5.0. In Java, generics are only checked at compile time for type correctness. The generic type information is then removed via a process called
type erasure, to maintain compatibility with old
JVM implementations, making it 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 String type when they are retrieved from the list, reducing performance compared to other implementations such as C++ templates.
Genericity in .NET [C#, VB.NET] Generics were added as part of
.NET Framework 2.0 in November 2005, based on a research prototype from Microsoft Research started in 1999. Although similar to generics in Java, .NET generics do not apply
type erasure, but implement generics as a first class mechanism in the runtime using
reification. This design choice provides additional functionality, such as allowing
reflection with preservation of generic types, and alleviating some of the limits of erasure (such as being unable to create generic arrays). This also means that there is no performance hit from runtime
casts and normally 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> are valid types, however are advised against for member signatures in code analysis design rules. .NET allows six varieties of generic type constraints using the where keyword including restricting generic types to be value types, to be classes, to have constructors, and to implement interfaces. Below is an example with an interface constraint: namespace Wikipedia.Examples; using System; public class Example { static void Main() { int[] a = { 0, 1, 2, 3 }; MakeAtLeast(a, 2); // Change a to { 2, 2, 2, 3 } foreach (int i in a) { Console.WriteLine(i); // Print results. } Console.ReadKey(true); } static void MakeAtLeast(T[] list, T lowest) where T : IComparable { for (int i = 0; i The MakeAtLeast() method allows operation on arrays, with elements of generic type T. The method's type constraint indicates that the method is applicable to any type T that implements the generic IComparable<T> interface. This ensures a
compile time error, if the method is called if the type does not support comparison. The interface provides the generic method CompareTo(T). The above method could also be written without generic types, simply using the non-generic Array type. However, since arrays are
contravariant, the casting would not be
type safe, and the compiler would be unable to find certain possible errors that would otherwise be caught when using generic types. In addition, the method would need to access the array items as objects instead, and would require
casting to compare two elements. (For value types like types such as int this requires a
boxing conversion, although this can be worked around using the Comparer<T> class, as is done in the standard collection classes.) A notable behavior of static members in a generic .NET class is static member instantiation per run-time type (see example below). namespace Wikipedia.Examples; using System; // A generic class class GenericTest { // A static variable - will be created for each type on reflection static CountedInstances OnePerType = new(); // A data member private T _t; // Default constructor public GenericTest(T t) { _t = t; } } // a class class CountedInstances { // Static variable - this will be incremented once per instance public static int Counter; // Default constructor public CountedInstances() { // Increase counter by one during object instantiation CountedInstances.Counter++; } } public class GenericExample { static void Main(string[] args) { // Main code entry point // At the end of execution, CountedInstances.Counter = 2 GenericTest g1 = new(1); GenericTest g11 = new(11); GenericTest g111 = new(111); GenericTest g2 = new(1.0); } }
Genericity in Pascal For
Pascal, generics were first implemented in 2006, in the implementation
Free Pascal.
In Delphi The
Object Pascal dialect
Delphi acquired generics in the 2007 Delphi 11 release by
CodeGear, initially only with the .NET compiler (since discontinued) before being added to the native code in the 2009 Delphi 12 release. The semantics and abilities of Delphi generics are largely modelled on those of generics in .NET 2.0, though the implementation is by necessity quite different. Here is a more or less direct translation of the first C# example shown above: program Sample; {$APPTYPE CONSOLE} uses Generics.Defaults; //for IComparer<> type TUtils = class class procedure MakeAtLeast(Arr: TArray; const Lowest: T; Comparer: IComparer); overload; class procedure MakeAtLeast(Arr: TArray; const Lowest: T); overload; end; class procedure TUtils.MakeAtLeast(Arr: TArray; const Lowest: T; Comparer: IComparer); var I: Integer; begin if Comparer = nil then Comparer := TComparer.Default; for I := Low(Arr) to High(Arr) do if Comparer.Compare(Arr[I], Lowest) (Arr: TArray; const Lowest: T); begin MakeAtLeast(Arr, Lowest, nil); end; var Ints: TArray; Value: Integer; begin Ints := TArray.Create(0, 1, 2, 3); TUtils.MakeAtLeast(Ints, 2); for Value in Ints do WriteLn(Value); ReadLn; end. As with C#, methods and whole types can have one or more type parameters. In the example, TArray is a generic type (defined by the language) and MakeAtLeast a generic method. The available constraints are very similar to the available constraints in C#: any value type, any class, a specific class or interface, and a class with a parameterless constructor. Multiple constraints act as an additive union.
In Free Pascal Free Pascal implemented generics in 2006 in
version 2.2.0, before Delphi and with different syntax and semantics. However, since FPC version 2.6.0, the Delphi-style syntax is available when using the language mode {$mode Delphi}. Thus, Free Pascal code supports generics in either style. Delphi and Free Pascal example: // Delphi style unit A; {$ifdef fpc} {$mode delphi} {$endif} interface type TGenericClass = class function Foo(const AValue: T): T; end; implementation function TGenericClass.Foo(const AValue: T): T; begin Result := AValue + AValue; end; end. // Free Pascal's ObjFPC style unit B; {$ifdef fpc} {$mode objfpc} {$endif} interface type generic TGenericClass = class function Foo(const AValue: T): T; end; implementation function TGenericClass.Foo(const AValue: T): T; begin Result := AValue + AValue; end; end. // example usage, Delphi style program TestGenDelphi; {$ifdef fpc} {$mode delphi} {$endif} uses A,B; var GC1: A.TGenericClass; GC2: B.TGenericClass; begin GC1 := A.TGenericClass.Create; GC2 := B.TGenericClass.Create; WriteLn(GC1.Foo(100)); // 200 WriteLn(GC2.Foo('hello')); // hellohello GC1.Free; GC2.Free; end. // example usage, ObjFPC style program TestGenDelphi; {$ifdef fpc} {$mode objfpc} {$endif} uses A,B; // required in ObjFPC type TAGenericClassInt = specialize A.TGenericClass; TBGenericClassString = specialize B.TGenericClass; var GC1: TAGenericClassInt; GC2: TBGenericClassString; begin GC1 := TAGenericClassInt.Create; GC2 := TBGenericClassString.Create; WriteLn(GC1.Foo(100)); // 200 WriteLn(GC2.Foo('hello')); // hellohello GC1.Free; GC2.Free; end.
Functional languages Genericity in Haskell The
type class mechanism of
Haskell supports generic programming. 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 example, the following declaration of a type of
binary trees states that it is to be an instance of the classes Eq and Show: data BinTree a = Leaf a | Node (BinTree a) a (BinTree a) deriving (Eq, Show) This results in an equality function (==) and a string representation function (show) being automatically defined for any type of the form BinTree T provided that T itself supports those operations. The support for derived instances of Eq and Show makes their methods == and show generic 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 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 and 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 in 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 specialized 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 that 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 specialized 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 = (==)
Clean 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.
Other languages Languages in the
ML family support generic programming through
parametric polymorphism and generic
modules called
functors. Both
Standard ML and
OCaml provide functors, which are similar to class templates and to Ada's generic packages.
Scheme syntactic abstractions also have a connection to genericity – these are in fact a superset of C++ templates. A
Verilog module may take one or more parameters, to which their actual values are assigned upon the instantiation of the module. One example is a generic
register array where the array width is given via a parameter. Such an array, combined with a generic wire vector, can make a generic buffer or memory module with an arbitrary bit width out of a single module implementation.
VHDL, being derived from Ada, also has generic abilities.
C has a feature called "type-generic expressions" using the keyword: This feature gives C
function overloading capabilities, but is not related to generic programming. Generic programming can be achieved by using the preprocessor to define the generic code, with macro expansion taking the role of
instantiation. Sometimes, the non-standard extension "statement expressions" is used to simulate function-like behaviour for generic code. Combining this two features enables implementing a generic max function, similar to in c++: • define max(a,b) \ ({ typeof (a) _a = (a); \ typeof (b) _b = (b); \ _a > _b ? _a : _b; }) ==See also==