Generic programming: Difference between revisions

Revision as of 14:14, 24 June 2023

Revision as of 10:13, 7 August 2023

Line 44:

| 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 journalbook |doi=10.1145/317500.317529 |title=A library of generic algorithms in Ada |author1=Musser, David R. |author2=Stepanov, Alexander A. |journaltitle=Proceedings of the 1987 Annualannual ACM SIGAda Internationalinternational Conferenceconference on Ada - SIGAda '87 |chapter=A library of generic algorithms in Ada |date=1987 |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>