Content deleted Content added
TamaMcGlinn (talk | contribs) Turing completeness of Template metaprogramming in C++ is not an opinion, but a proven fact |
Tags: Mobile edit Mobile web edit |
||
| (33 intermediate revisions by 18 users not shown) | |||
Line 1:
{{Short description|Style of computer programming}}
{{Use dmy dates|date=November 2020}}
{{Distinguish|Genetic programming|Pseudocode}}
'''Generic programming''' is a style of [[computer programming]] in which [[algorithm]]s are written in terms of [[data type]]s ''to-be-specified-later'' that are then ''instantiated'' when needed for specific types provided as [[Parameter (computer programming)|parameters]]. This approach, pioneered in the [[programming language]] [[ML (programming language)|ML]] in 1973,<ref name="Lee2008">
{{cite book
|
|
| date=15 December 2008
| title=Programming Languages: An Active Learning Approach
| url=https://books.google.com/books?id=OuW5dC2O99AC&pg=PA9
| publisher=Springer Science & Business Media
| isbn=978-0-387-79422-8
| pages=9–10}}</ref><ref>{{cite conference |last1=Milner |first1=R. |author1-link=Robin Milner |last2=Morris |first2=L. |last3=Newey |first3=M. |year=1975 |title=A Logic for Computable Functions with Reflexive and Polymorphic Types |book-title=Proceedings of the Conference on Proving and Improving Programs}}</ref> permits writing common [[
{{cite book |last1=Gamma
|first1=Erich
Line 31:
}}</ref>
New techniques were introduced by [[Andrei Alexandrescu]] in his 2001 book
Such software entities are known as ''generics'' in [[Ada (programming language)|Ada]], [[C Sharp (programming language)|C#]], [[Delphi (software)|Delphi]], [[Eiffel (programming language)|Eiffel]], [[F Sharp (programming language)|F#]], [[Java (programming language)|Java]], [[Nim (programming language)|Nim]], [[Python (programming language)|Python]], [[Go (programming language)|Go]], [[Rust (programming language)|Rust]], [[Swift (programming language)|Swift]], [[TypeScript]], and [[Visual Basic (.NET)]]. They are known as ''[[parametric polymorphism]]'' in [[ML (programming language)|ML]], [[Scala (programming language)|Scala]], [[Julia (programming language)|Julia]], and [[Haskell]]. (Haskell terminology also uses the term
The term
== Stepanov–Musser and other generic programming paradigms ==
Line 70:
==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 used for abstraction or code terseness, however this is not typically labeled ''genericity'' as it's a direct consequence of the dynamic typing system employed by the language.{{citation needed|date=August 2015}} The term has been used in [[functional programming]], specifically in [[Haskell]]-like languages, which use a [[structural type system]] where types are always parametric and the actual code on those types is generic. These uses still serve a similar purpose of code-saving and rendering an abstraction.
Line 80:
===In object-oriented languages===
When creating container classes in statically typed languages, it is inconvenient to write specific implementations for each datatype contained, especially if the code for each datatype is virtually identical. For example, in C++, this duplication of code can be circumvented by defining a class template:
<syntaxhighlight lang="Cpp">
class Animal { ... };
class
template <typename T>
class MyList {
// Class contents.
};
</syntaxhighlight>
Above, <code>T</code> is a placeholder for whatever type is specified when the list is created. These "containers-of-type-T", commonly called [[template (programming)|templates]], allow a class to be reused with different datatypes as long as certain contracts such as [[Subtyping|subtype]]s and [[Type signature|signature]] are kept. This genericity mechanism should not be confused with ''[[polymorphism (computer science)|inclusion polymorphism]]'', which is the [[algorithm]]ic usage of exchangeable sub-classes: for instance, a list of objects of type <code>Moving_Object</code> containing objects of type <code>Animal</code> and <code>Car</code>. Templates can also be used for type-independent functions as in the <code>Swap</code> example below:
<syntaxhighlight lang="Cpp">
// "&" denotes a reference
template <typename T>
void swap(T& a, T& b) noexcept {
b = a;
a = temp;
}
int main(int argc, char* argv[]) {
std::string
swap(world, hello);
std::println("{}{}", world, hello); // Output is "Hello, World!".
}
</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 [[List of programming language researchers|language designers]] and supports many generic programming idioms. The D
[[C Sharp (programming language)|C#]] 2.0, [[Oxygene (programming language)|Oxygene]] 1.5
====Generics in Ada====
{{unreferenced|section|date=January 2024}}
[[Ada (programming language)|Ada]] has had generics since it was first designed in 1977–1980. The [[standard library]] uses generics to provide many services. Ada 2005 adds a comprehensive generic container library to the standard library, which was inspired by C++'s [[Standard Template Library]].
A ''generic unit'' is a package or a subprogram that takes one or more ''generic formal parameters''.<ref>{{Cite web |title=Generic Units |url=https://www.adaic.org/resources/add_content/standards/05rm/html/RM-12.html |access-date=2024-04-25 |website=www.adaic.org}}</ref>
A ''generic formal parameter'' is a value, a variable, a constant, a type, a subprogram, or even an instance of another, designated, generic unit. For generic formal types, the syntax distinguishes between discrete, floating-point, fixed-point, access (pointer) types, etc. Some formal parameters can have default values.
Line 123 ⟶ 133:
The specification of a generic package:
<syntaxhighlight lang="
generic
Max_Size : Natural; -- a generic formal value
Line 159 ⟶ 169:
Using an instance of a generic package:
<syntaxhighlight lang="
type Document_Type is record
Contents : Ada.Strings.Unbounded.Unbounded_String;
Line 177 ⟶ 187:
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:
<syntaxhighlight lang="
generic
type Index_Type is (<>); -- must be a discrete type
Line 195 ⟶ 205:
* 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.
* all instantiations being explicit, there are no hidden instantiations that might make it difficult to understand the program.
* Ada does not permit
====Templates in C++====
{{Main|Template (C++)}}
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 [[Turing complete]].
=====Technical overview=====
There are many kinds of templates, the most common being function templates and class templates. A ''function template'' is a pattern for creating ordinary functions based upon the parameterizing types supplied when instantiated. For example, the C++ Standard Template Library contains the function template <code>std::max(x, y)</code> that creates functions that return either ''x'' or ''y,'' whichever is larger. <code>max()</code> could be defined like this:
<syntaxhighlight lang="
template <typename T>
[[nodiscard]]
constexpr T
return x < y ? y : x;
}
</syntaxhighlight>
Line 213 ⟶ 225:
''Specializations'' of this function template, instantiations with specific types, can be called just like an ordinary function:
<syntaxhighlight lang="
std::
</syntaxhighlight>
The compiler examines the arguments used to call <code>max</code> and determines that this is a call to <code>max(int, int)</code>. It then instantiates a version of the function where the parameterizing type <code>T</code> is <code>int</code>, making the equivalent of the following function:
<syntaxhighlight lang="
[[nodiscard]]
constexpr int max(int x, int y) noexcept {
return x < y ? y : x;
}
</syntaxhighlight>
This works whether the arguments <code>x</code> and <code>y</code> are integers, strings, or any other type for which the expression <code>x
C++ templates are completely [[
Another kind of template, a ''class template
[[C++20]] introduces constraining template types using [[Concepts (C++)|concepts]]. Constraining the <code>max()</code> could look something like this:
<syntaxhighlight lang="cpp">
// in typename declaration:
template <std::totally_ordered T>
[[nodiscard]]
constexpr T max(T x, T y) noexcept {
return x < y ? y : x;
}
// in requires clause:
template <typename T>
requires std::totally_ordered<T>
[[nodiscard]]
constexpr T max(T x, T y) noexcept {
return x < y ? y : x;
}
</syntaxhighlight>
=====Template specialization=====
Line 239 ⟶ 271:
=====Advantages and disadvantages=====
Some uses of templates, such as the <code>max()</code> function, were
<syntaxhighlight lang="
#define max(a,b) ((a) < (b) ? (b) : (a))
</syntaxhighlight>
Macros are expanded (copy pasted) by the [[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.
There are four primary drawbacks to the use of templates: supported features, compiler support, poor error messages (usually with pre C++20
# Templates in C++ lack many features, which makes implementing them and using them in a straightforward way often impossible. Instead programmers have to rely on
# Many compilers historically had poor support for templates, thus the use of templates could
# 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:{{Blockquote|So, can derivation be used to reduce the problem of code replicated because templates are used? This would involve deriving a template from an ordinary class. This technique proved successful in curbing code bloat in real use. People who do not use a technique like this have found that replicated code can cost megabytes of code space even in moderate size programs.|[[Bjarne Stroustrup]]|The Design and Evolution of C++, 1994<ref name="Stroustrup94Design">{{cite book |
# 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 262 ⟶ 294:
The [[D (programming language)|D]] language supports templates based in design on C++. Most C++ template idioms work in 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 [[
* 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 |last=Bright |first=Walter |title=Voldemort Types in D |url =https://www.drdobbs.com/cpp/voldemort-types-in-d/232901591 |website=Dr. Dobbs |access-date=3 June 2015}}</ref>
Line 274 ⟶ 306:
For example, an input [[Range (computer programming)#Range as an alternative to iterator|range]] is defined as any type that satisfies the checks performed by <code>isInputRange</code>, which is defined as follows:
<syntaxhighlight lang="
template isInputRange(R)
{
Line 290 ⟶ 322:
A function that accepts only input ranges can then use the above template in a template constraint:
<syntaxhighlight lang="
auto fun(Range)(Range range)
if (isInputRange!Range)
Line 314 ⟶ 346:
For example, given a function that takes a string containing an HTML template and returns equivalent D source code, it is possible to use it in the following way:
<syntaxhighlight lang="
// Import the contents of example.htt as a string manifest constant.
enum htmlTemplate = import("example.htt");
Line 331 ⟶ 363:
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>
<syntaxhighlight lang="
class
LIST [G]
Line 347 ⟶ 379:
The formal generic parameters are placeholders for arbitrary class names that will be supplied when a declaration of the generic class is made, as shown in the two ''generic derivations'' below, where <code lang=Eiffel>ACCOUNT</code> and <code lang=Eiffel>DEPOSIT</code> are other class names. <code lang=Eiffel>ACCOUNT</code> and <code lang=Eiffel>DEPOSIT</code> are considered ''actual generic parameters'' as they provide real class names to substitute for <code lang=Eiffel>G</code> in actual use.
<syntaxhighlight lang="
list_of_accounts: LIST [ACCOUNT]
-- Account list
Line 361 ⟶ 393:
For the list class shown above, an actual generic parameter substituting for <code lang=Eiffel>G</code> can be any other available class. To constrain the set of classes from which valid actual generic parameters can be chosen, a ''generic constraint'' can be specified. In the declaration of class <code lang=Eiffel>SORTED_LIST</code> below, the generic constraint dictates that any valid actual generic parameter will be a class that inherits from class <code lang=Eiffel>COMPARABLE</code>. The generic constraint ensures that elements of a <code lang=Eiffel>SORTED_LIST</code> can in fact be sorted.
<syntaxhighlight lang="
class
SORTED_LIST [G -> COMPARABLE]
Line 369 ⟶ 401:
{{Main|Generics in Java}}
Support for the ''generics'', or "containers-of-type-T" was added to the [[
====Genericity in .NET [C#, VB.NET]====
Line 376 ⟶ 408:
.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:
<syntaxhighlight lang="
using System;
Line 383 ⟶ 415:
static void Main()
{
int[]
MakeAtLeast<int>(
foreach (int i in
{
Console.WriteLine(i); // Print results.
}
Console.ReadKey(true);
}
Line 393 ⟶ 427:
{
for (int i = 0; i < list.Length; i++)
{
if (list[i].CompareTo(lowest) < 0)
{
list[i] = lowest;
}
}
}
}
Line 405 ⟶ 443:
A notable behavior of static members in a generic .NET class is static member instantiation per run-time type (see example below).
<syntaxhighlight lang="
using System;
// A generic class
class GenericTest<T>
{
// A static variable - will be created for each type on reflection
static CountedInstances OnePerType = new CountedInstances();
// A data member
private T _t;
//
public
{
_t = t;
}
}
// a class
{
// Static variable - this will be incremented once per instance
public static int
// Default constructor
public CountedInstances()
{
// Increase counter by one during object instantiation
CountedInstances.Counter++;
}
}
public class GenericExample
{
static void Main(string[] args)
{
// Main code entry point
// At the end of execution, CountedInstances.Counter = 2
GenericTest<int> g1 = new GenericTest<int>(1);
GenericTest<int> g11 = new GenericTest<int>(11);
GenericTest<int> g111 = new GenericTest<int>(111);
GenericTest<double> g2 = new GenericTest<double>(1.0);
}
}
</syntaxhighlight>
====Genericity in
For [[Pascal (programming language)|Pascal]], generics were first implemented in 2006, in the implementation [[#In Free Pascal|Free Pascal]].
=====In Delphi=====
The [[Object Pascal]] dialect [[Delphi (software)|Delphi]] acquired generics in the 2007 Delphi 11 release by [[CodeGear]], initially only with the .NET compiler (since discontinued) before being added to the native code in the 2009 Delphi 12 release. The semantics and abilities of Delphi generics are largely modelled on those of generics in .NET 2.0, though the implementation is by necessity quite different. Here is a more or less direct translation of the first C# example shown above:
<syntaxhighlight lang="
program Sample;
Line 492 ⟶ 541:
As with C#, methods and whole types can have one or more type parameters. In the example, TArray is a generic type (defined by the language) and MakeAtLeast a generic method. The available constraints are very similar to the available constraints in C#: any value type, any class, a specific class or interface, and a class with a parameterless constructor. Multiple constraints act as an additive union.
====
[[Free Pascal]] implemented generics in 2006 in [[Free Pascal#Version 2.2.x|version 2.2.0]], before Delphi
Delphi and Free Pascal example:
<syntaxhighlight lang="
// Delphi style
unit A;
Line 596 ⟶ 645:
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>:
<syntaxhighlight lang="
data BinTree a = Leaf a | Node (BinTree a) a (BinTree a)
deriving (Eq, Show)
Line 609 ⟶ 658:
The flatten function in PolyP is here provided as an example:
<syntaxhighlight lang="
flatten :: Regular d => d a -> [a]
flatten = cata fl
Line 637 ⟶ 686:
As an example, the equality function in Generic Haskell:<ref>[https://www.cs.uu.nl/research/projects/generic-haskell/compiler/diamond/GHUsersGuide.pdf The Generic Haskell User's Guide]</ref>
<syntaxhighlight lang="
type Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool
type Eq {[ k -> l ]} t1 t2 = forall u1 u2. Eq {[ k ]} u1 u2 -> Eq {[ l ]} (t1 u1) (t2 u2)
Line 662 ⟶ 711:
[[VHDL]], being derived from Ada, also has generic abilities.<ref>https://www.ics.uci.edu/~jmoorkan/vhdlref/generics.html VHDL Reference</ref>
[[C (programming language)|C]]
<syntaxhighlight lang="c">
#define
({ typeof (a) _a =
typeof (b) _b =
_a > _b ? _a : _b; })</syntaxhighlight>
The keyword <code>_Generic</code> is used in C preprocessor macros to automatically match the type of its parameter.
<syntaxhighlight lang="c">
#include <stdio.h>
#define type_of(x) _Generic((x), \
int: "int", \
float: "float", \
double: "double", \
char*: "string", \
default: "unknown")
int main(int argc, char* argv[]) {
printf("%s\n", type_of(42));
printf("%s\n", type_of(3.14f));
printf("%s\n", type_of(2.718));
printf("%s\n", type_of("hello"));
printf("%s\n", type_of((void *)0));
return 0;
}
</syntaxhighlight>
==See also==
Line 714 ⟶ 786:
* [[Free Pascal]]: [https://www.freepascal.org/docs-html/ref/refch8.html Free Pascal Reference guide Chapter 8: Generics], Michaël Van Canneyt, 2007
* Delphi for Win32: [https://sjrd.developpez.com/delphi/tutoriel/generics/ Generics with Delphi 2009 Win32], Sébastien DOERAENE, 2008
* Delphi for .NET: [https://www.felix-colibri.com/papers/oop_components/delphi_generics_tutorial/delphi_generics_tutorial.html Delphi Generics] {{Webarchive|url=https://web.archive.org/web/20230114100915/http://www.felix-colibri.com/papers/oop_components/delphi_generics_tutorial/delphi_generics_tutorial.html |date=14 January 2023 }}, Felix COLIBRI, 2008
;Eiffel
Line 735 ⟶ 807:
* Angelika Langer, [https://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.html Java Generics FAQs]
{{Programming paradigms navbox}}
{{Data types}}
{{Authority control}}
[[Category:Generic programming| ]]
[[Category:Programming language comparisons]]
<!-- Hidden categories below -->
[[Category:Articles with example Ada code]]
[[Category:Articles with example C++ code]]
Line 745 ⟶ 820:
[[Category:Articles with example Eiffel code]]
[[Category:Articles with example Haskell code]]
[[Category:Articles with example Pascal code]]
| |||