Generic Programming
2. Stepanov–Musser and other generic programming paradigms
Generic programming is defined in Musser & 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
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. find, sort etc., a direct approach would implement each algorithm specifically for each data structure, giving N × 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 or range to process. Thus, only N + 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.
Note that although this approach often utilizes language features of compile-time genericity/templates, it is in fact 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 from Knuth 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.
– Alexander Stepanov, Short History of STL
I believe that iterator theories are as central to Computer Science as theories of rings or Banach spaces are central to Mathematics.
– Alexander Stepanov, An Interview with A. Stepanov
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
Other programming paradigms that have been described as generic programming include Datatype generic programming as described in "Generic Programming – an Introduction". The Scrap your boilerplate approach is a lightweight generic programming approach for Haskell. In this article we distinguish the high-level programming paradigms of generic programming, above, from the lower-level programming language genericity mechanisms used to implement them (see Programming language support for genericity). For further discussion and comparison of generic programming paradigms.