Generic programming is a style of computer programming in which algorithms are written in terms of data types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered in the programming language ML in 1973, permits writing common functions or data types that differ only in the set of types on which they operate when used, thus reducing duplicate code.
Generic programming was introduced to the mainstream with Ada in 1977. With templates in C++, generic programming became part of the repertoire of professional library design. The techniques were further improved and parameterized types were introduced in the influential 1994 book Design Patterns.
New techniques were introduced by Andrei Alexandrescu in his 2001 book Modern C++ Design: Generic Programming and Design Patterns Applied. Subsequently, D implemented the same ideas.
Such software entities are known as generics in Ada, C#, Delphi, Eiffel, F#, Java, Mojo, Nim, Python, Go, Rust, Swift, TypeScript, and Visual Basic (.NET). They are known as parametric polymorphism in ML, Scala, Julia, and Haskell. (Haskell terminology also uses the term generic for a related but somewhat different concept.)
The term generic programming was originally coined by David Musser and Alexander Stepanov 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 and data structures and formalized as concepts, with generic functions implemented in terms of these concepts, typically using language genericity mechanisms as described above.
Stepanov–Musser and other generic programming paradigms
Generic programming is defined in as follows,
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 as concepts, analogously to the abstraction of algebraic theories in abstract algebra. Early examples of this programming approach were implemented in Scheme and Ada, although the best known example is the Standard Template Library (STL), which developed a theory of iterators that is used to decouple sequence data structures and the algorithms operating on them.
For example, given N sequence data structures, e.g. singly linked list, vector etc., and M algorithms to operate on them, e.g. <code>find</code>, <code>sort</code> etc., a direct approach would implement each algorithm specifically for each data structure, giving 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 or range to process. Thus, only 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.
Although this approach often uses language features of compile-time genericity and templates, it is independent of particular language-technical details. Generic programming pioneer Alexander Stepanov wrote,
Bjarne Stroustrup noted,