Generic programming is a style ofcomputer programming in whichalgorithms are written in terms ofdata typesto-be-specified-later that are theninstantiated when needed for specific types provided asparameters. This approach, pioneered in theprogramming languageML in 1973,[1][2] permits writing commonfunctions ordata types that differ only in theset of types on which they operate when used, thus reducingduplicate code.
Generic programming was introduced to the mainstream withAda in 1977. Withtemplates inC++, generic programming became part of the repertoire of professionallibrary design. The techniques were further improved andparameterized types were introduced in the influential 1994 bookDesign Patterns.[3]
New techniques were introduced byAndrei Alexandrescu in his 2001 bookModern C++ Design: Generic Programming and Design Patterns Applied. Subsequently,D implemented the same ideas.
Such software entities are known asgenerics inAda,C#,Delphi,Eiffel,F#,Java,Nim,Python,Go,Rust,Swift,TypeScript, andVisual Basic (.NET). They are known asparametric polymorphism inML,Scala,Julia, andHaskell. (Haskell terminology also uses the termgeneric for a related but somewhat different concept.)
The termgeneric programming was originally coined byDavid Musser andAlexander Stepanov[4] in a more specific sense than the above, to describe a programming paradigm in which fundamental requirements on data types are abstracted from across concrete examples of algorithms anddata structures and formalized asconcepts, withgeneric functions implemented in terms of these concepts, typically using language genericity mechanisms as described above.
Generic programming is defined inMusser & Stepanov (1989) as follows,
Generic programming centers around the idea of abstracting from concrete, efficient algorithms to obtain generic algorithms that can be combined with different data representations to produce a wide variety of useful software.
— Musser, David R.; Stepanov, Alexander A., Generic Programming[5]
The "generic programming" paradigm is an approach to software decomposition whereby fundamental requirements on types are abstracted from across concrete examples of algorithms and data structures and formalized asconcepts, analogously to the abstraction of algebraic theories inabstract algebra.[6] Early examples of this programming approach were implemented in Scheme and Ada,[7] although the best known example is theStandard Template Library (STL),[8][9] which developed a theory ofiterators that is used to decouple sequence data structures and the algorithms operating on them.
For example, givenN sequence data structures, e.g. singly linked list, vector etc., andM algorithms to operate on them, e.g.find
,sort
etc., a direct approach would implement each algorithm specifically for each data structure, givingN ×M combinations to implement. However, in the generic programming approach, each data structure returns a model of an iterator concept (a simple value type that can be dereferenced to retrieve the current value, or changed to point to another value in the sequence) and each algorithm is instead written generically with arguments of such iterators, e.g. a pair of iterators pointing to the beginning and end of the subsequence orrange to process. Thus, onlyN +M data structure-algorithm combinations need be implemented. Several iterator concepts are specified in the STL, each a refinement of more restrictive concepts e.g. forward iterators only provide movement to the next value in a sequence (e.g. suitable for a singly linked list or a stream of input data), whereas a random-access iterator also provides direct constant-time access to any element of the sequence (e.g. suitable for a vector). An important point is that a data structure will return a model of the most general concept that can be implemented efficiently—computational complexity requirements are explicitly part of the concept definition. This limits the data structures a given algorithm can be applied to and such complexity requirements are a major determinant of data structure choice. Generic programming similarly has been applied in other domains, e.g. graph algorithms.[10]
Although this approach often uses language features ofcompile-time genericity and templates, it is independent of particular language-technical details. Generic programming pioneer Alexander Stepanov wrote,
Generic programming is about abstracting and classifying algorithms and data structures. It gets its inspiration fromKnuth and not from type theory. Its goal is the incremental construction of systematic catalogs of useful, efficient and abstract algorithms and data structures. Such an undertaking is still a dream.
I believe that iterator theories are as central to Computer Science as theories ofrings orBanach spaces are central to Mathematics.
— Alexander Stepanov, An Interview with A. Stepanov[13]
Bjarne Stroustrup noted,
Following Stepanov, we can define generic programming without mentioning language features: Lift algorithms and data structures from concrete examples to their most general and abstract form.
— Bjarne Stroustrup, Evolving a language in and for the real world: C++ 1991-2006[12]
Other programming paradigms that have been described as generic programming includeDatatype generic programming as described in "Generic Programming – an Introduction".[14] The Scrap yourboilerplate approach is a lightweight generic programming approach for Haskell.[15]
In this article we distinguish the high-levelprogramming paradigms ofgeneric programming, above, from the lower-level programming languagegenericity mechanisms used to implement them (seeProgramming language support for genericity). For further discussion and comparison of generic programming paradigms, see.[16]
Genericity facilities have existed in high-level languages since at least the 1970s in languages such asML,CLU andAda, and were subsequently adopted by manyobject-based andobject-oriented languages, includingBETA,C++,D,Eiffel,Java, andDEC's now defunctTrellis-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, inForth thecompiler can execute code while compiling and one can create newcompiler keywords and new implementations for those words on the fly. It has fewwords that expose the compiler behaviour and therefore naturally offersgenericity capacities that, however, are not referred to as such in most Forth texts. Similarly, dynamically typed languages, especially interpreted ones, usually offergenericity 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 labeledgenericity as it's a direct consequence of the dynamic typing system employed by the language.[citation needed] The term has been used infunctional programming, specifically inHaskell-like languages, which use astructural 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 andstructs 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 thecompiler and the syntax differs from other generic constructs. Someextensible 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.[17]
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:
template<typenameT>classList{// 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 is created. These "containers-of-type-T", commonly calledtemplates, allow a class to be reused with different datatypes as long as certain contracts such assubtypes andsignature are kept. This genericity mechanism should not be confused withinclusion polymorphism, which is thealgorithmic usage of exchangeable sub-classes: for instance, a list of objects of typeMoving_Object
containing objects of typeAnimal
andCar
. Templates can also be used for type-independent functions as in theSwap
example below:
// "&" denotes a referencetemplate<typenameT>voidSwap(T&a,T&b){// A similar, but safer and potentially faster function// is defined in the standard library header <utility>Ttemp=b;b=a;a=temp;}std::stringworld="World!";std::stringhello="Hello, ";Swap(world,hello);std::cout<<world<<hello<<‘\n’;// Output is "Hello, World!".
The C++template
construct used above is widely cited[citation needed] as the genericity construct that popularized the notion among programmers andlanguage 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 ofJava Platform, Standard Edition (J2SE) 5.0.
C# 2.0,Oxygene 1.5 (formerly Chrome) andVisual Basic (.NET) 2005 have constructs that exploit the support for generics present in Microsoft.NET Framework since version 2.0.
This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved. Find sources: "Generic programming" – news ·newspapers ·books ·scholar ·JSTOR(January 2024) (Learn how and when to remove this message) |
Ada has had generics since it was first designed in 1977–1980. Thestandard library uses generics to provide many services. Ada 2005 adds a comprehensive generic container library to the standard library, which was inspired by C++'sStandard Template Library.
Ageneric unit is a package or a subprogram that takes one or moregeneric formal parameters.[18]
Ageneric 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.
Toinstantiate a generic unit, the programmer passesactual parameters for each formal. The generic instance then behaves just like any other unit. It is possible to instantiate generic units atrun-time, for example inside a loop.
The specification of a generic package:
genericMax_Size:Natural;-- a generic formal valuetypeElement_Typeisprivate;-- a generic formal type; accepts any nonlimited typepackageStacksistypeSize_Typeisrange0..Max_Size;typeStackislimitedprivate;procedureCreate(S:outStack;Initial_Size:inSize_Type:=Max_Size);procedurePush(Into:inoutStack;Element:inElement_Type);procedurePop(From:inoutStack;Element:outElement_Type);Overflow:exception;Underflow:exception;privatesubtypeIndex_TypeisSize_Typerange1..Max_Size;typeVectorisarray(Index_Typerange<>)ofElement_Type;typeStack(Allocated_Size:Size_Type:=0)isrecordTop:Index_Type;Storage:Vector(1..Allocated_Size);end record;endStacks;
Instantiating the generic package:
typeBookmark_TypeisnewNatural;-- records a location in the text document we are editingpackageBookmark_Stacksis newStacks(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:
typeDocument_TypeisrecordContents:Ada.Strings.Unbounded.Unbounded_String;Bookmarks:Bookmark_Stacks.Stack;end record;procedureEdit(Document_Name:inString)isDocument:Document_Type;begin-- Initialise the stack of bookmarks:Bookmark_Stacks.Create(S=>Document.Bookmarks,Initial_Size=>10);-- Now, open the file Document_Name and read it in...endEdit;
The language syntax allows precise specification of constraints on generic formal parameters. For example, it is possible to specify that a generic formal type will only accept a modular type as the actual. It is also possible to express constraintsbetween generic formal parameters; for example:
generictypeIndex_Typeis(<>);-- must be a discrete typetypeElement_Typeisprivate;-- can be any nonlimited typetypeArray_Typeisarray(Index_Typerange<>)ofElement_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 that satisfies 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, thecompiler can instantiate generics without looking at the body of the generic.
Unlike C++, Ada does not allow specialised generic instances, and requires that all generics be instantiated explicitly. These rules have several consequences:
C++ uses templates to enable generic programming techniques. The C++ Standard Library includes theStandard Template Library or STL that provides a framework of templates for common data structures and algorithms. Templates in C++ may also be used fortemplate metaprogramming, which is a way of pre-evaluating some of the code at compile-time rather thanrun-time. Using template specialization, C++ Templates areTuring complete.
There are many kinds of templates, the most common being function templates and class templates. Afunction 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 templatemax(x, y)
that creates functions that return eitherx ory, whichever is larger.max()
could be defined like this:
template<typenameT>Tmax(Tx,Ty){returnx<y?y:x;}
Specializations of this function template, instantiations with specific types, can be called just like an ordinary function:
std::cout<<max(3,7);// Outputs 7.
The compiler examines the arguments used to callmax
and determines that this is a call tomax(int, int)
. It then instantiates a version of the function where the parameterizing typeT
isint
, making the equivalent of the following function:
intmax(intx,inty){returnx<y?y:x;}
This works whether the argumentsx
andy
are integers, strings, or any other type for which the expressionx < y
is sensible, or more specifically, for any type for whichoperator<
is defined. Common inheritance is not needed for the set of types that can be used, and so it is very similar toduck typing. A program defining a custom data type can useoperator overloading to define the meaning of<
for that type, thus allowing its use with themax()
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 standardsort()
,stable_sort()
, andbinary_search()
algorithms or to be put inside data structures such asset
s,heaps, andassociative arrays.
C++ templates are completelytype safe at compile time. As a demonstration, the standard typecomplex
does not define the<
operator, because there is no strict order oncomplex numbers. Therefore,max(x, y)
will fail with a compile error, ifx andy arecomplex
values. Likewise, other templates that rely on<
cannot be applied tocomplex
data unless a comparison (in the form of a functor or function) is provided. E.g.: Acomplex
cannot be used as key for amap
unless a comparison is provided. Unfortunately, compilers historically generate somewhat esoteric, long, and unhelpful error messages for this sort of error. Ensuring that a certain object adheres to amethod protocol can alleviate this issue. Languages which usecompare
instead of<
can also usecomplex
values as keys.
Another kind of template, aclass 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 alinked list container. To make a linked list of integers, one writeslist<int>
. A list of strings is denotedlist<string>
. Alist
has a set of standard functions associated with it, that work for any compatible parameterizing types.
A powerful feature of C++'s templates istemplate 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 asort()
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.
Unlike function templates, class templates can bepartially 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 (theprimary 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 befully specialized, which means that an alternate implementation can be provided when all of the parameterizing types are known.
Some uses of templates, such as themax()
function, were formerly filled by function-likepreprocessormacros (a legacy of theC language). For example, here is a possible implementation of such macro:
#define max(a,b) ((a) < (b) ? (b) : (a))
Macros are expanded (copy pasted) by thepreprocessor, before program compiling; templates are actual real functions. Macros are always expanded inline; templates can also beinline functions when the compiler deems it appropriate.
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, such as evaluating parameters with side effects twice. Perhaps most importantly, templates were designed to be applicable to much larger problems than macros.
There are four primary drawbacks to the use of templates: supported features, compiler support, poor error messages (usually with pre C++20substitution failure is not an error (SFINAE)), andcode bloat:
So, can derivation be used to reduce the problem of code replicated because templates are used? This would involve deriving a template from an ordinary class. This technique proved successful in curbing code bloat in real use. People who do not use a technique like this have found that replicated code can cost megabytes of code space even in moderate size programs.
— Bjarne Stroustrup, The Design and Evolution of C++, 1994[20]
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.[citation needed]
TheD language supports templates based in design on C++. Most C++ template idioms work in D without alteration, but D adds some functionality:
static if
statement provide an alternative to respectively C++'sC++ concepts andif constexpr
.is(...)
expression allows speculative instantiation to verify an object's traits at compile time.auto
keyword and thetypeof
expression allowtype inference for variable declarations and function return values, which in turn allows "Voldemort types" (types that do not have a global name).[21]Templates in D use a different syntax than in C++: whereas in C++ template parameters are wrapped in angular brackets (Template<param1, param2>
),D uses an exclamation sign and parentheses:Template!(param1, param2)
.This avoids theC++ 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 providecompile-time polymorphism using trait-based generic programming.For example, an inputrange is defined as any type that satisfies the checks performed byisInputRange
, which is defined as follows:
templateisInputRange(R){enumboolisInputRange=is(typeof((inoutint=0){Rr=R.init;// can define a range objectif(r.empty){}// can test for emptyr.popFront();// can invoke popFront()autoh=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:
autofun(Range)(Rangerange)if(isInputRange!Range){// ...}
In addition to template metaprogramming, D also provides several features to enable compile-time code generation:
import
expression allows reading a file from disk and using its contents as a string expression.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 typeto perform serialization and deserialization.User-defined attributes could further indicate serialization rules.
Theimport
expression and compile-time function execution also allow efficiently implementingdomain-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.enumhtmlTemplate=import("example.htt");// Transpile the HTML template to D code.enumhtmlDCode=htmlTemplateToD(htmlTemplate);// Paste the contents of htmlDCode as D code.mixin(htmlDCode);
Generic classes have been a part ofEiffel since the original method and language design. The foundation publications of Eiffel,[22][23] use the termgenericity to describe creating and using generic classes.
Generic classes are declared with their class name and a list of one or moreformal generic parameters. In the following code, classLIST
has one formal generic parameterG
classLIST[G]...feature-- Accessitem:G-- The item currently pointed to by cursor...feature-- Element changeput(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 twogeneric derivations below, whereACCOUNT
andDEPOSIT
are other class names.ACCOUNT
andDEPOSIT
are consideredactual generic parameters as they provide real class names to substitute forG
in actual use.
list_of_accounts:LIST[ACCOUNT]-- Account listlist_of_deposits:LIST[DEPOSIT]-- Deposit list
Within the Eiffel type system, although classLIST [G]
is considered a class, it is not considered a type. However, a generic derivation ofLIST [G]
such asLIST [ACCOUNT]
is considered a type.
For the list class shown above, an actual generic parameter substituting forG
can be any other available class. To constrain the set of classes from which valid actual generic parameters can be chosen, ageneric constraint can be specified. In the declaration of classSORTED_LIST
below, the generic constraint dictates that any valid actual generic parameter will be a class that inherits from classCOMPARABLE
. The generic constraint ensures that elements of aSORTED_LIST
can in fact be sorted.
classSORTED_LIST[G->COMPARABLE]
Support for thegenerics, or "containers-of-type-T" was added to theJava 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 calledtype erasure, to maintain compatibility with oldJVM implementations, making it unavailable at runtime.[24] For example, aList<String>
is converted to the raw typeList
. The compiler insertstype casts to convert the elements to theString
type when they are retrieved from the list, reducing performance compared to other implementations such as C++ templates.
Generics were added as part of.NET Framework 2.0 in November 2005, based on a research prototype from Microsoft Research started in 1999.[25] Although similar to generics in Java, .NET generics do not applytype erasure,[26]: 208–209 but implement generics as a first class mechanism in the runtime usingreification. This design choice provides additional functionality, such as allowingreflection with preservation of generic types, and alleviating some of the limits of erasure (such as being unable to create generic arrays).[27][28] This also means that there is no performance hit from runtimecasts and normally expensiveboxing conversions. When primitive and value types are used as generic arguments, they get specialized implementations, allowing for efficient genericcollections and methods. As in C++ and Java, nested generic types such as Dictionary<string, List<int>> are valid types, however are advised against for member signatures in code analysis design rules.[29]
.NET allows six varieties of generic type constraints using thewhere
keyword including restricting generic types to be value types, to be classes, to have constructors, and to implement interfaces.[30] Below is an example with an interface constraint:
usingSystem;classSample{staticvoidMain(){int[]array={0,1,2,3};MakeAtLeast<int>(array,2);// Change array to { 2, 2, 2, 3 }foreach(intiinarray)Console.WriteLine(i);// Print results.Console.ReadKey(true);}staticvoidMakeAtLeast<T>(T[]list,Tlowest)whereT:IComparable<T>{for(inti=0;i<list.Length;i++)if(list[i].CompareTo(lowest)<0)list[i]=lowest;}}
TheMakeAtLeast()
method allows operation on arrays, with elements of generic typeT
. The method's type constraint indicates that the method is applicable to any typeT
that implements the genericIComparable<T>
interface. This ensures acompile time error, if the method is called if the type does not support comparison. The interface provides the generic methodCompareTo(T)
.
The above method could also be written without generic types, simply using the non-genericArray
type. However, since arrays arecontravariant, the casting would not betype 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 asobject
s instead, and would requirecasting to compare two elements. (For value types like types such asint
this requires aboxing conversion, although this can be worked around using theComparer<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).
// A generic classpublicclassGenTest<T>{// A static variable - will be created for each type on reflectionstaticCountedInstancesOnePerType=newCountedInstances();// a data memberprivateT_t;// simple constructorpublicGenTest(Tt){_t=t;}}// a classpublicclassCountedInstances{//Static variable - this will be incremented once per instancepublicstaticintCounter;//simple constructorpublicCountedInstances(){//increase counter by one during object instantiationCountedInstances.Counter++;}}// main code entry point// at the end of execution, CountedInstances.Counter = 2GenTest<int>g1=newGenTest<int>(1);GenTest<int>g11=newGenTest<int>(11);GenTest<int>g111=newGenTest<int>(111);GenTest<double>g2=newGenTest<double>(1.0);
ForPascal, generics were first implemented in 2006, in the implementationFree Pascal.
TheObject Pascal dialectDelphi acquired generics in the 2007 Delphi 11 release byCodeGear, 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:
programSample;{$APPTYPE CONSOLE}usesGenerics.Defaults;//for IComparer<>typeTUtils=classclassprocedureMakeAtLeast<T>(Arr:TArray<T>;constLowest:T;Comparer:IComparer<T>);overload;classprocedureMakeAtLeast<T>(Arr:TArray<T>;constLowest:T);overload;end;classprocedureTUtils.MakeAtLeast<T>(Arr:TArray<T>;constLowest:T;Comparer:IComparer<T>);varI:Integer;beginifComparer=nilthenComparer:=TComparer<T>.Default;forI:=Low(Arr)toHigh(Arr)doifComparer.Compare(Arr[I],Lowest)<0thenArr[I]:=Lowest;end;classprocedureTUtils.MakeAtLeast<T>(Arr:TArray<T>;constLowest:T);beginMakeAtLeast<T>(Arr,Lowest,nil);end;varInts:TArray<Integer>;Value:Integer;beginInts:=TArray<Integer>.Create(0,1,2,3);TUtils.MakeAtLeast<Integer>(Ints,2);forValueinIntsdoWriteLn(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.
Free Pascal implemented generics in 2006 inversion 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 styleunitA;{$ifdef fpc}{$mode delphi}{$endif}interfacetypeTGenericClass<T>=classfunctionFoo(constAValue:T):T;end;implementationfunctionTGenericClass<T>.Foo(constAValue:T):T;beginResult:=AValue+AValue;end;end.// Free Pascal's ObjFPC styleunitB;{$ifdef fpc}{$mode objfpc}{$endif}interfacetypegenericTGenericClass<T>=classfunctionFoo(constAValue:T):T;end;implementationfunctionTGenericClass.Foo(constAValue:T):T;beginResult:=AValue+AValue;end;end.// example usage, Delphi styleprogramTestGenDelphi;{$ifdef fpc}{$mode delphi}{$endif}usesA,B;varGC1:A.TGenericClass<Integer>;GC2:B.TGenericClass<String>;beginGC1:=A.TGenericClass<Integer>.Create;GC2:=B.TGenericClass<String>.Create;WriteLn(GC1.Foo(100));// 200WriteLn(GC2.Foo('hello'));// hellohelloGC1.Free;GC2.Free;end.// example usage, ObjFPC styleprogramTestGenDelphi;{$ifdef fpc}{$mode objfpc}{$endif}usesA,B;// required in ObjFPCtypeTAGenericClassInt=specializeA.TGenericClass<Integer>;TBGenericClassString=specializeB.TGenericClass<String>;varGC1:TAGenericClassInt;GC2:TBGenericClassString;beginGC1:=TAGenericClassInt.Create;GC2:=TBGenericClassString.Create;WriteLn(GC1.Foo(100));// 200WriteLn(GC2.Foo('hello'));// hellohelloGC1.Free;GC2.Free;end.
Thetype class mechanism ofHaskell supports generic programming. Six of the predefined type classes in Haskell (includingEq
, the types that can be compared for equality, andShow
, the types whose values can be rendered as strings) have the special property of supportingderived 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 ofbinary trees states that it is to be an instance of the classesEq
andShow
:
dataBinTreea=Leafa|Node(BinTreea)a(BinTreea)deriving(Eq,Show)
This results in an equality function (==
) and a string representation function (show
) being automatically defined for any type of the formBinTree T
provided thatT
itself supports those operations.
The support for derived instances ofEq
andShow
makes their methods==
andshow
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 was the first generic programming language extension toHaskell. In PolyP, generic functions are calledpolytypic. 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 ofkind* → *, and ifa is the formal type argument in the definition, then all recursive calls tot must have the formt 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::Regulard=>da->[a]flatten=cataflpolytypicfl::fa[a]->[a]casefofg+h->eitherflflg*h->\(x,y)->flx++fly()->\x->[]Par->\x->[x]Rec->\x->xd@g->concat.flatten.pmapflCont->\x->[]cata::Regulard=>(FunctorOfdab->b)->da->b
Generic Haskell is another extension toHaskell, developed atUtrecht University in theNetherlands. The extensions it provides are:
The resulting type-indexed value can be specialized to any type.
As an example, the equality function in Generic Haskell:[31]
typeEq{[*]}t1t2=t1->t2->BooltypeEq{[k->l]}t1t2=forallu1u2.Eq{[k]}u1u2->Eq{[l]}(t1u1)(t2u2)eq{|t::k|}::Eq{[k]}tteq{|Unit|}__=Trueeq{|:+:|}eqAeqB(Inla1)(Inla2)=eqAa1a2eq{|:+:|}eqAeqB(Inrb1)(Inrb2)=eqBb1b2eq{|:+:|}eqAeqB__=Falseeq{|:*:|}eqAeqB(a1:*:b1)(a2:*:b2)=eqAa1a2&&eqBb1b2eq{|Int|}=(==)eq{|Char|}=(==)eq{|Bool|}=(==)
Clean offers generic programming basedPolyP and theGeneric Haskell as supported by the GHC ≥ 6.0. It parametrizes by kind as those but offers overloading.
Languages in theML family support generic programming throughparametric polymorphism and genericmodules calledfunctors. BothStandard ML andOCaml 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.
AVerilog module may take one or more parameters, to which their actual values are assigned upon the instantiation of the module. One example is a genericregister 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.[32]
VHDL, being derived from Ada, also has generic abilities.[33]
C has a feature called "type-generic expressions" using the_Generic
keyword:[34] This feature gives cfunction overloading capabilities, but is not related to generic programming. Generic programming can be achieve by using the proprocessor to define the generic code, with macro expansion taking the role ofinstantiation. Sometimes the non-standard extention "statement expressions" is used to simulate function like behaviour for generic code:
#define max(a,b) \ ({ typeof (a) _a = (a); \ typeof (b) _b = (b); \ _a > _b ? _a : _b; })