Content deleted Content added
m →Programming language support for genericity: cite repair; |
Jerryobject (talk | contribs) WP:REFerence WP:CITation parameters: adds, fills, reorders, respaces, update-standardizes. WP:LINKs: needless WP:PIPEs > WP:NOPIPEs, update-standardizes, underscores > spaces, adds. WP:COPYEDITs WP:EoS: WP:TERSE, clarify. Template:Quote, Template:Main article updates > Template:Blockquote, Template:Main. MOS:FIRSTABBReviation define before WP:ABBR. Cut needless carriage return in paragraphs. WP:SLASHes > comma+space. |
||
Line 3:
{{Use dmy dates|date=November 2020}}
{{Programming paradigms}}
'''Generic programming''' is a style of [[computer programming]] in which [[algorithm]]s are written in terms of [[data type
{{cite book
| last=Lee
Line 12:
| publisher=Springer Science & Business Media
| isbn=978-0-387-79422-8
| pages=9–10}}</ref><ref>{{cite conference |last1=Milner |first1=R. |last2=Morris |first2=L. |last3=Newey |first3=M. |year=1975 |title=A Logic for Computable Functions with Reflexive and Polymorphic Types |
Generics was introduced to the main-stream programming with Ada in 1977 and then with ''[[Template (C++)|
{{cite book |last1
|first1
|last2
|first2
|last3
|first3
|last4
|first4
|title
▲ |date = 1994
|publisher
|isbn
|url-access
|url
}}</ref>
New techniques were introduced by [[Andrei Alexandrescu]] in his 2001 book, [[Modern C++ Design
Such software entities are known as ''generics'' in [[Ada (programming language)|Ada]], [[C Sharp (programming language)|C#]], [[Delphi (
The term "generic programming" was originally coined by [[David Musser]] and [[Alexander Stepanov]]{{sfn|Musser|Stepanov|1989}} in a more specific sense than the above, to describe a programming paradigm whereby fundamental requirements on data types are abstracted from across concrete examples of algorithms and [[data
== Stepanov–Musser and other generic programming paradigms ==
Generic programming is defined in {{harvtxt|Musser|Stepanov|1989}} as follows,
{{Blockquote
| text
| author = Musser, David R.; Stepanov, Alexander A.
| source = Generic Programming<ref>{{cite book |
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 journal |
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>
{{Blockquote
| text
| author
| source
{{Blockquote
| text
| author
| source
[[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
| source
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
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) |
==Programming language support for genericity==
Genericity facilities have existed in high-level languages since at least the 1970s in languages such as [[ML (programming language)|ML]], [[CLU (programming language)|CLU]] and [[Ada (programming language)|Ada]], and were subsequently adopted by many [[
Genericity is implemented and supported differently in various programming languages; the term "generic" has also been used differently in various programming contexts. For example, in [[Forth (programming language)|Forth]] the [[compiler]] can execute code while compiling and one can create new ''compiler keywords'' and new implementations for those words on the fly. It has few ''words'' that expose the compiler behaviour and therefore naturally offers ''genericity'' capacities that, however, are not referred to as such in most Forth texts. Similarly, dynamically typed languages, especially interpreted ones, usually offer ''genericity'' by default as both passing values to functions and value assignment are type-indifferent and such behavior is often
[[Array data type|Arrays]] and [[struct (C programming language)|structs]] 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 the [[compiler]] and the syntax differs from other generic constructs. Some [[extensible programming|extensible 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.<ref>{{
===In object-oriented languages===
Line 110:
</syntaxhighlight>
The C++ <code>template</code> construct used above is widely cited{{Citation needed|date=May 2010}} as the genericity construct that popularized the notion among programmers and language designers and supports many generic programming idioms. The D programming language also offers fully generic-capable templates based on the C++ precedent but with a simplified syntax. The Java programming language has provided genericity facilities syntactically based on C++'s since the introduction of [[Java Platform, Standard Edition
[[C Sharp (programming language)|C#]] 2.0, [[
====Generics in Ada====
Line 179:
</syntaxhighlight>
=====Advantages and
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 constraints ''between'' generic formal parameters; for example:
Line 198:
* the compiler can implement ''shared generics'': the object code for a generic unit can be shared between all instances (unless the programmer requests inlining of subprograms, of course). As further consequences:
** there is no possibility of code bloat (code bloat is common in C++ and requires special care, as explained below).
** it is possible to instantiate generics at run-time,
** actual objects corresponding to a generic formal object are always considered to be non-static inside the generic; see [[wikibooks:Ada Programming/Generics#Generic formal objects|Generic formal objects]] in the Wikibook for details and consequences.
* all instances of a generic being exactly the same, it is easier to review and understand programs written by others; there are no "special cases" to take into account.
Line 205:
====Templates in C++====
{{Main
C++ uses templates to enable generic programming techniques. The C++ Standard Library includes the [[Standard Template Library]] or STL that provides a framework of templates for common data structures and algorithms. Templates in C++ may also be used for [[template metaprogramming]], which is a way of pre-evaluating some of the code at compile-time rather than [[Run time (program lifecycle phase)|run-time]]. Using template specialization, C++ Templates are considered [[Turing complete]].
Line 246:
=====Advantages and disadvantages=====
Some uses of templates, such as the <code>max()</code> function, were previously filled by function-like [[preprocessor]] [[Macro (computer science)|macros]] (a legacy of the [[C (programming language)|C
<syntaxhighlight lang="Cpp">
Line 252:
</syntaxhighlight>
Macros are expanded (copy pasted) by [[preprocessor]], before
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.
Line 261:
# Many compilers historically had poor support for templates, thus the use of templates could have made code somewhat less portable. Support may also be poor when a C++ compiler is being used with a [[Linker (computing)|linker]] that is not C++-aware, or when attempting to use templates across [[Library (computer science)#Shared libraries|shared library]] boundaries.
# Compilers can produce confusing, long, and sometimes unhelpful error messages when errors are detected in code that uses SFINAE.<ref>[https://www.stroustrup.com/N1522-concept-criteria.pdf Stroustrup, Dos Reis (2003): Concepts - Design choices for template argument checking]</ref> This can make templates difficult to develop with.
# Finally, the use of templates requires the compiler to generate a separate ''instance'' of the templated class or function for every type parameters used with it. (This is necessary because types in C++ are not all the same size, and the sizes of data fields are important to how classes work.) So the indiscriminate use of templates can lead to [[code bloat]], resulting in excessively large executables. However, judicious use of template specialization and derivation can dramatically reduce such code bloat in some cases:{{
# Templated classes or functions may require an ''explicit specialization'' of the template class which would require rewriting of an entire class for a specific template parameters used by it.
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.
Line 269:
====Templates in D====
The [[D (programming language)|D]] language supports templates based in design on C++. Most C++ template idioms carry over to D without alteration, but D adds some functionality:
* Template parameters in D are not restricted to just types and primitive values (as it was in C++ before C++20), but also allow arbitrary compile-time values (such as strings and struct literals), and aliases to arbitrary identifiers, including other templates or template instantiations.
* Template constraints and the <code>static if</code> statement provide an alternative to respectively C++'s [[Concepts (C++)|C++ concepts]] and <code>if constexpr</code>.
* The <code>is(...)</code> expression allows speculative instantiation to verify an object's traits at compile time.
* The <code>auto</code> keyword and the <code>[[typeof]]</code> expression allow [[type inference]] for variable declarations and function return values, which in turn allows "Voldemort types" (types that do not have a global name).<ref>{{cite web |
Templates in D use a different syntax than in C++: whereas in C++ template parameters are wrapped in angular brackets (<code>Template<param1, param2></code>),
Line 314 ⟶ 313:
* The <code>import</code> expression allows reading a file from disk and using its contents as a string expression.
* Compile-time reflection allows enumerating and inspecting declarations and their members during
* User-defined [[Attribute (computing)|attributes]] allow users to attach arbitrary identifiers to declarations, which can then be enumerated using compile-time reflection.
* [[Compile-time function execution
* String mixins allow evaluating and compiling the contents of a string expression as D code that becomes part of the program.
Line 340 ⟶ 339:
====Genericity in Eiffel====
Generic classes have been a part of [[Eiffel (programming language)|Eiffel]] since the original method and language design. The foundation publications of Eiffel,<ref>''Object-Oriented Software Construction,'' Prentice Hall, 1988, and ''Object-Oriented Software Construction, second edition,'' Prentice Hall, 1997.</ref><ref>''Eiffel: The Language,'' Prentice Hall, 1991.</ref> use the term ''genericity'' to describe
=====Basic
Generic classes are declared with their class name and a list of one or more ''formal generic parameters''. In the following code, class <code lang=Eiffel>LIST</code> has one formal generic parameter <code lang=Eiffel>G</code>
Line 381 ⟶ 380:
====Generics in Java====<!-- This section is linked from [[Comparison of Java and C++]] -->
▲{{Main article|Generics in Java}}
Support for the ''generics'', or "containers-of-type-T" was added to the [[Java (programming language)|Java 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 called [[type erasure]], to maintain compatibility with old [[Java virtual machine|JVM]] implementations, making it unavailable at runtime.{{sfn|Bloch|2018|loc=§Item 28: Prefer lists to arrays|p=126}} For example, a <code>List<String></code> is converted to the raw type <code>List</code>. The compiler inserts [[Type conversion|type casts]] to convert the elements to the <code>String</code> type when they are retrieved from the list, reducing performance compared to other implementations such as C++ templates.
Line 388 ⟶ 386:
====Genericity in .NET [C#, VB.NET]====
Generics were added as part of [[.NET Framework#.NET Framework 2.0|.NET Framework 2.0]] in November 2005, based on a research prototype from Microsoft Research started in 1999.<ref>[https://docs.microsoft.com/en-us/archive/blogs/dsyme/netc-generics-history-some-photos-from-feb-1999 .NET/C# Generics History: Some Photos From Feb 1999]</ref> Although similar to generics in Java, .NET generics do not apply [[type erasure]],{{sfn|Albahari|2022}}{{rp|208-209}} but implement generics as a first class mechanism in the runtime using [[Reification (computer science)|reification]]. This design choice provides additional functionality, such as allowing [[
.NET allows six varieties of generic type constraints using the <code>where</code> keyword including restricting generic types to be value types, to be classes, to have constructors, and to implement interfaces.<ref>[https://msdn2.microsoft.com/en-us/library/d5x73970.aspx Constraints on Type Parameters (C# Programming Guide)]</ref> Below is an example with an interface constraint:
Line 461 ⟶ 459:
====Genericity in Delphi====
[[Delphi (
<syntaxhighlight lang="Delphi">
Line 506 ⟶ 504:
</syntaxhighlight>
As with C#, methods
====Genericity in Free Pascal====
[[Free Pascal]] implemented generics before Delphi, and with different syntax and semantics. However, since FPC version 2.6.0, the Delphi-style syntax is available when using the {$mode Delphi} language mode. Thus, Free Pascal
Delphi and Free Pascal example:
Line 611 ⟶ 609:
====Genericity in Haskell====
The [[type class]] mechanism of [[Haskell]] supports generic programming. Six of the predefined type classes in Haskell (including <code>Eq</code>, the types that can be compared for equality, and <code>Show</code>, the types whose values can be rendered as strings) have the special property of supporting ''derived 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 of [[binary tree]]s states that it is to be an instance of the classes <code>Eq</code> and <code>Show</code>:▼
▲Six of the predefined type classes in Haskell (including <code>Eq</code>, the types that can be compared for equality, and <code>Show</code>, the types whose values can be rendered as strings) have the special property of supporting ''derived 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.
<syntaxhighlight lang="Haskell">
Line 625 ⟶ 621:
===== PolyP =====
PolyP was the first generic programming language extension to [[
The flatten function in PolyP is here provided as an example:
Line 646 ⟶ 642:
=====Generic Haskell=====
Generic Haskell is another extension to [[
*''Type-indexed values'' are defined as a value indexed over the various Haskell type constructors (unit, primitive types, sums, products, and user-defined type constructors). In addition, we can also specify the behaviour of a type-indexed values for a specific constructor using ''constructor cases'', and reuse one generic definition in another using ''default cases''.
The resulting type-indexed value can be specialized to any type.
Line 673 ⟶ 669:
====Clean====
[[Clean (programming language)|Clean]] offers generic programming based
===Other languages===
Line 680 ⟶ 676:
A [[Verilog]] module may take one or more parameters, to which their actual values are assigned upon the instantiation of the module. One example is a generic [[Hardware register|register]] 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.<ref>Verilog by Example, Section ''The Rest for Reference''. Blaine C. Readler, Full Arc Press, 2011. {{ISBN|978-0-9834973-0-1}}</ref>
[[VHDL]], being derived from Ada, also has generic
[[C (programming language)|C]] supports "type-generic expressions" using the {{c-lang|_Generic}} keyword:<ref name="N1516">[https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1516.pdf WG14 N1516 Committee Draft — October 4, 2010]</ref>
Line 700 ⟶ 696:
{{refbegin}}
* {{cite book |last=Albahari |first=Joseph |title= C# 10 in a Nutshell |publisher= O'Reilly |isbn= 978-1-098-12195-2|edition=First|year=2022}}
*{{cite book |
* {{Cite book |
* {{cite conference |
* {{cite book |title=Design Patterns: Elements of Reusable Object-Oriented Software |first1=Erich |last1=Gamma |first2=Richard |last2=Helm |first3=Ralph |last3=Johnson |first4=John |last4=Vlissides |year=1994 |publisher=Addison-Wesley |isbn=0-201-63361-2 |bibcode=1995dper.book.....G |url-access=registration |url=https://archive.org/details/designpatternsel00gamm
{{refend}}
== Further reading ==
* Gabriel Dos Reis and Jaakko Järvi, ''[https://www.elegantcoding.com/2012/04/what-is-generic-programming.html What is Generic Programming?],'' [https://lcsd05.cs.tamu.edu LCSD 2005] {{Webarchive|url=https://web.archive.org/web/20190828045251/https://lcsd05.cs.tamu.edu/ |date=28 August 2019
* {{cite conference |
|
|
|
|
* {{cite book|doi=10.1145/28697.28738|chapter=Genericity versus inheritance|title=Conference proceedings on Object-oriented programming systems, languages and applications - OOPSLA '86|pages=391–405|year=1986|last1=Meyer|first1=Bertrand|isbn=0897912047|s2cid=285030|author-link1=Bertrand Meyer}}
Line 719 ⟶ 715:
* Alexander A. Stepanov, [https://www.stepanovpapers.com/ Collected Papers of Alexander A. Stepanov] (creator of the [[Standard Template Library|STL]])
;C++
* Walter Bright, ''[https://www.digitalmars.com/d/templates-revisited.html Templates Revisited].''
* David Vandevoorde, Nicolai M Josuttis, ''C++ Templates: The Complete Guide'', 2003 Addison-Wesley. {{ISBN|0-201-73484-2}}
;C#
* Jason Clark, "[https://msdn.microsoft.com/msdnmag/issues/03/09/NET/ Introducing Generics in the Microsoft CLR]," September 2003, ''MSDN Magazine'', Microsoft.
* Jason Clark, "[https://msdn.microsoft.com/msdnmag/issues/03/10/NET/ More on Generics in the Microsoft CLR]," October 2003, ''MSDN Magazine'', Microsoft.
* M. Aamir Maniar, [https://codeplex.com/Wiki/View.aspx?ProjectName=genericsnet Generics.Net]. An open source generics library for C#.
;Delphi
* Nick Hodges, "[https://edn.embarcadero.com/article/38757 Delphi 2009 Reviewers Guide]," October 2008, ''Embarcadero Developer Network'', Embarcadero.
* Craig Stuntz, "[https://web.archive.org/web/20090131211440/https://blogs.teamb.com/craigstuntz/2008/08/29/37832/ Delphi 2009 Generics and Type Constraints]," October 2008
Line 756 ⟶ 752:
{{Data types}}
{{Authority control}}
| |||