Generic programming: Difference between revisions

Revision as of 10:17, 10 November 2024

Latest revision as of 06:37, 17 August 2025

(20 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|Style of computer programming}}

{{Distinguish|Genetic 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 by the [[ML (programming language)|ML]] programming language in 1973,<ref name="Lee2008">

'''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

| lastlast1=Lee

| firstfirst1=Kent D.

| date=15 December 2008

| title=Programming Languages: An Active Learning Approach

| url=https://books.google.com/books?id=OuW5dC2O99AC&pg=PA9

| date=15 December 2008

| 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 [[functionFunction (computer science)|functions]] or [[typedata (computer science)|type]]s that differ only in the [[Set (mathematics)|set]] of types on which they operate when used, thus reducing [[duplicate code]].

Generic programming was introduced to the mainstream with [[Ada (programming language)|Ada]] in 1977. With [[Template (C++)|templates]] in [[C++]], generic programming became part of the repertoire of professional [[Library (computing)|library]] design. The techniques were further improved and ''parameterized types'' were introduced in the influential 1994 book ''[[Design Patterns]]''.<ref name="GoF">

{{cite book |last1=Gamma

|first1=Erich

Line 30 ⟶ 31:

}}</ref>

New techniques were introduced by [[Andrei Alexandrescu]] in his 2001 book ''[[Modern C++ Design|Modern C++ Design]]: Generic Programming and Design Patterns Applied]]''. Subsequently, [[D (programming language)|D]] implemented the same ideas.

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 "''generic"'' for a related but somewhat different concept.)

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 in which fundamental requirements on data types are abstracted from across concrete examples of algorithms and [[data structure]]s and formalized as [[Concept (generic programming)|concepts]], with [[generic function]]s implemented in terms of these concepts, typically using language genericity mechanisms as described above.

Line 69 ⟶ 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 [[object-based]] and [[Object-oriented programming|object-oriented]] languages, including [[BETA (programming language)|BETA]], [[C++]], [[D (programming language)|D]], [[Eiffel (programming language)|Eiffel]], [[Java (programming language)|Java]], and [[Digital Equipment Corporation|DEC]]'s now defunct [[Trellis-Owl]].

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 79 ⟶ 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 { ... };

template<typename T>

class ListCar { ... };

// Class contents.

template <typename T>

class MyList {

// Class contents.

};

ListMyList<Animal> list_of_animalsanimalList;

ListMyList<Car> list_of_carscarList;

</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) { // A similar, but safer and potentially faster function

// is defined in the standard library header <utility>

template <typename T>

T temp = b;

void swap(T& a, T& b) noexcept {

b = a;

a = T temp = b;

b = a;

a = temp;

}

int main(int argc, char* argv[]) {

std::string world = "World!";

std::string helloworld = "Hello, World!";

Swap(world, std::string hello) = "Hello, ";

swap(world, hello);

std::cout << world << hello << ‘\n’; // Output is "Hello, World!".

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 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]] (J2SE) 5.0.

[[C Sharp (programming language)|C#]] 2.0, [[Oxygene (programming language)|Oxygene]] 1.5]] (formerly Chrome) and [[Visual Basic (.NET)]] 2005 have constructs that exploit the support for generics present in Microsoft [[.NET Framework]] since version 2.0.

====Generics in Ada====

Line 199 ⟶ 209:

====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="cpp">

template <typename T>

[[nodiscard]]

T max(T x, T y) {

constexpr T returnmax(T x, <T y) ?noexcept y : x;{

return x < y ? y : x;

}

</syntaxhighlight>

Line 214 ⟶ 226:

<syntaxhighlight lang="cpp">

std::cout <<println("{}", max(3, 7)); // Outputs 7.

</syntaxhighlight>

Line 220 ⟶ 232:

<syntaxhighlight lang="cpp">

[[nodiscard]]

int max(int x, int y) {

constexpr int max(int x, int y) noexcept {

return x < y ? y : x;

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 &lt;< y</code> is sensible, or more specifically, for any type for which <code>operator&lt;</code> is defined. Common inheritance is not needed for the set of types that can be used, and so it is very similar to [[Duck typing#Templates or generic types|duck typing]]. A program defining a custom data type can use [[operator overloading]] to define the meaning of <code>&lt;<</code> for that type, thus allowing its use with the <code>std::max()</code> function template. While this may seem a minor benefit in this isolated example, in the context of a comprehensive library like the STL it allows the programmer to get extensive functionality for a new data type, just by defining a few operators for it. Merely defining <code>&lt;<</code> allows a type to be used with the standard <code>std::sort()</code>, <code>std::stable_sort()</code>, and <code>std::binary_search()</code> algorithms or to be put inside data structures such as <code>std::set</code>s (equivalent to <code>TreeSet</code>, [[heap (programming)|heap]]s, and [[associative array]]s.

C++ templates are completely [[type safe]] at compile time. As a demonstration, the standard type <code>std::complex</code> does not define the <code>&lt;<</code> operator, because there is no strict order on [[complex number]]s. Therefore, <code>std::max(x, y)</code> will fail with a compile error, if ''x'' and ''y'' are <code>complex</code> values. Likewise, other templates that rely on <code>&lt;<</code> cannot be applied to <code>complex</code> data unless a comparison (in the form of a functor or function) is provided. E.g.:For Ainstance, <code>std::complex</code> cannot be used as key for a <code>std::map</code> (equivalent to <code>TreeMap</code>) unless a comparison is provided. Unfortunately, compilers historically generate somewhat esoteric, long, and unhelpful error messages for this sort of error. Ensuring that a certain object adheres to a [[protocol (computer science)|method protocol]] can alleviate this issue. Languages which use <code>std::compare</code> instead of <code>&lt;<</code> can also use <code>std::complex</code> values as keys.

Another kind of template, a ''class template,'', extends the same concept to classes. A class template specialization is a class. Class templates are often used to make generic containers. For example, the STL has a [[doubly linked list]] container, <code>std::list</code> (equivalent to <code>LinkedList</code>). To make a linked list of integers, one writes <code>std::list&lt;<int&gt;></code>. A list of strings is denoted <code>std::list&lt;<std::string&gt;></code>. A <code>std::list</code> has a set of standard functions associated with it, that work for any compatible parameterizing types.

[[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 383 ⟶ 415:

static void Main()

{

int[] arraya = { 0, 1, 2, 3 };

MakeAtLeast<int>(arraya, 2); // Change arraya to { 2, 2, 2, 3 }

foreach (int i in arraya)

{

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 406 ⟶ 444:

<syntaxhighlight lang="csharp">

using System;

// A generic class

public class GenTest<T>

{

// A static variable - will be created for each type on reflection

static CountedInstances OnePerType = new CountedInstances();

// A generic class

// a data member

class GenericTest<T>

private T _t;

{

// A static variable - will be created for each type on reflection

static CountedInstances OnePerType = new CountedInstances();

// simpleA data constructormember

private T _t;

public GenTest(T t)

{

_t = t;

}

}

// aDefault classconstructor

public classGenericTest(T CountedInstancest)

{

_t = t;

//Static variable - this will be incremented once per instance

}

public static int Counter;

}

// a class

//simple constructor

publicclass CountedInstances()

{

{

// Static variable - this will be incremented once per instance

//increase counter by one during object instantiation

public static int CountedInstances.Counter++;

}

// Default constructor

public CountedInstances()

{

// Increase counter by one during object instantiation

CountedInstances.Counter++;

}

}

public class GenericExample

// main code entry point

{

// at the end of execution, CountedInstances.Counter = 2

static void Main(string[] args)

GenTest<int> g1 = new GenTest<int>(1);

{

GenTest<int> g11 = new GenTest<int>(11);

// Main code entry point

GenTest<int> g111 = new GenTest<int>(111);

// At the end of execution, CountedInstances.Counter = 2

GenTest<double> g2 = new GenTest<double>(1.0);

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 DelphiPascal====

For [[Pascal (programming language)|Pascal]], generics were first implemented in 2006, in the implementation [[#In Free Pascal|Free Pascal]].

[[Delphi (software)|Delphi's]] [[Object Pascal]] dialect acquired generics in the Delphi 2007 release, initially only with the (now discontinued) .NET compiler before being added to the native code in the Delphi 2009 release. The semantics and capabilities of Delphi generics are largely modelled on those had by generics in .NET 2.0, though the implementation is by necessity quite different. Here's a more or less direct translation of the first C# example shown above:

=====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="delphi">

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.

====Genericity in=In Free Pascal=====

[[Free Pascal]] implemented generics in 2006 in [[Free Pascal#Version 2.2.x|version 2.2.0]], before Delphi, and with different syntax and semantics. However, since FPC version 2.6.0, the Delphi-style syntax is available when using the language mode <code>{$mode Delphi} language mode</code>. Thus, Free Pascal code supports generics in either style.

Delphi and Free Pascal example:

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]] supportshas a feature called "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> This feature gives C [[function overloading]] capabilities, but is not related to generic programming. Generic programming can be achieved by using the preprocessor to define the generic code, with macro expansion taking the role of ''instantiation''. Sometimes, the non-standard extension "statement expressions" is used to simulate function-like behaviour for generic code:

<syntaxhighlight lang="c">

#define cbrtmax(xa,b) _Generic((x), long double: cbrtl, \

({ typeof (a) _a = default: cbrt,(a); \

typeof (b) _b = float: cbrtf)(xb)</syntaxhighlight>; \

_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