Editing Generic programming (section)

== Stepanov–Musser and other generic programming paradigms ==
Generic programming is defined in {{harvtxt|Musser|Stepanov|1989}} as follows,
{{Blockquote
| text = 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.
| author = Musser, David R.; Stepanov, Alexander A.
| source = Generic Programming<ref>{{cite book |url=https://stepanovpapers.com/genprog.pdf |title=Generic Programming |author1=Musser, David R. |author2=Stepanov, Alexander A.}}</ref>}}

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 [[Concept (generic programming)|concepts]], analogously to the abstraction of algebraic theories in [[abstract algebra]].<ref>{{cite book|author1 =Alexander Stepanov |author2 =Paul McJones|title=Elements of Programming|publisher=Addison-Wesley Professional |date=19 June 2009|isbn=978-0-321-63537-2}}</ref> Early examples of this programming approach were implemented in Scheme and Ada,<ref>{{cite book |doi=10.1145/317500.317529 |author1=Musser, David R. |author2=Stepanov, Alexander A. |title=Proceedings of the 1987 annual ACM SIGAda international conference on Ada - SIGAda '87 |chapter=A library of generic algorithms in Ada |pages=216–225| year=1987 |isbn=0897912438 |citeseerx=10.1.1.588.7431 |s2cid=795406}}</ref> although the best known example is the [[Standard Template Library]] (STL),<ref>Alexander Stepanov and Meng Lee: The Standard Template Library. HP Laboratories Technical Report 95-11(R.1), 14 November 1995</ref><ref>Matthew H. Austern: Generic programming and the STL: using and extending the C++ Standard Template Library. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA 1998</ref> which developed a theory of [[iterator]]s 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 {{nowrap|''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 {{nowrap|''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—[[Analysis of algorithms|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.<ref>Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley 2001</ref>

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,
{{Blockquote
| text = Generic programming is about abstracting and classifying algorithms and data structures. It gets its inspiration from [[Donald Knuth|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.
| author = Alexander Stepanov
| source = Short History of STL<ref>{{cite book |last=Stepanov |first=Alexander |url=https://stepanovpapers.com/history%20of%20STL.pdf |title=Short History of STL}}</ref><ref name="stroustrup2007">{{cite book |last=Stroustrup |first=Bjarne |url=https://www.stroustrup.com/hopl-almost-final.pdf |title=Evolving a language in and for the real world: C++ 1991-2006 |doi=10.1145/1238844.1238848 |s2cid=7518369}}</ref>}}

{{Blockquote
| text = I believe that iterator theories are as central to Computer Science as theories of [[Ring (mathematics)|rings]] or [[Banach space]]s are central to Mathematics.
| author = Alexander Stepanov
| source = An Interview with A. Stepanov<ref name=stepanov2011>{{cite web |url =https://www.stlport.org/resources/StepanovUSA.html |title=An Interview with A. Stepanov |last=Lo Russo |first=Graziano}}</ref>}}

[[Bjarne Stroustrup]] noted,
{{Blockquote
| text = 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.
| author = Bjarne Stroustrup
| source = Evolving a language in and for the real world: C++ 1991-2006<ref name="stroustrup2007"/>}}

Other programming paradigms that have been described as generic programming include ''Datatype generic programming'' as described in  "Generic Programming – an Introduction".<ref>{{cite book |last1=Backhouse |first1=Roland |last2=Jansson |first2=Patrik |last3=Jeuring |first3=Johan |last4=Meertens |first4=Lambert |author4-link=Lambert Meertens |year=1999 |url=https://www.cse.chalmers.se/~patrikj/poly/afp98/genprogintro.pdf |title=Generic Programming – an Introduction}}</ref> The {{em | Scrap your [[Boilerplate code|boilerplate]]}} approach is a lightweight generic programming approach for Haskell.<ref>{{cite web |url=https://www.microsoft.com/en-us/research/wp-content/uploads/2003/01/hmap.pdf |title=Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming |last1=Lämmel |first1=Ralf |last2=Peyton Jones |first2=Simon |author2-link=Simon Peyton Jones |date=January 2003 |publisher=Microsoft |access-date=16 October 2016}}</ref>

In this article we distinguish the high-level [[programming paradigm]]s of ''generic programming'', above, from the lower-level programming language ''genericity mechanisms'' used to implement them (see [[#Programming language support for genericity|Programming language support for genericity]]). For further discussion and comparison of generic programming paradigms, see.<ref>{{cite web |url=https://lcsd05.cs.tamu.edu/papers/dos_reis_et_al.pdf |title=What is Generic Programming? (preprint LCSD'05) |last1=Dos Reis |first1=Gabriel |last2=Ja ̈rvi |first2=Jaakko |year=2005 |url-status=dead |archive-url=https://web.archive.org/web/20051225114849/https://lcsd05.cs.tamu.edu/papers/dos_reis_et_al.pdf |archive-date=25 December 2005}}</ref>