Generic programming

Generic programming is a style of computer programming in which algorithms are written in terms of data types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered in the programming language ML in 1973, permits writing common functions or data types that differ only in the set of types on which they operate when used, thus reducing duplicate code.

Generic programming was introduced to the mainstream with Ada in 1977. With templates in C++, generic programming became part of the repertoire of professional library design. The techniques were further improved and parameterized types were introduced in the influential 1994 book Design Patterns.

New techniques were introduced by Andrei Alexandrescu in his 2001 book Modern C++ Design: Generic Programming and Design Patterns Applied. Subsequently, D implemented the same ideas.

Such software entities are known as generics in Ada, C#, Dart, Delphi, Eiffel, F#, Java, Mojo, Nim, Python, Go, Rust, Swift, TypeScript, and Visual Basic (.NET). They are known as parametric polymorphism in ML, Scala, 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 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 structures and formalized as concepts, with generic functions implemented in terms of these concepts, typically using language genericity mechanisms as described above.

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—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.

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,

{{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>"}},"i":0}}]}'/>

Generic programming is about abstracting and classifying algorithms and data structures. It gets its inspiration from 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.

— Alexander Stepanov, Short History of STL

{{cite web |url =https://www.stlport.org/resources/StepanovUSA.html |title=An Interview with A. Stepanov |last=Lo Russo |first=Graziano}}</ref>"}},"i":0}}]}'/>

I believe that iterator theories are as central to Computer Science as theories of rings or Banach spaces are central to Mathematics.

— Alexander Stepanov, An Interview with A. Stepanov

Bjarne Stroustrup noted,

"}},"i":0}}]}'/>

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.

— Bjarne Stroustrup, Evolving a language in and for the real world: C++ 1991-2006

Other programming paradigms that have been described as generic programming include Datatype generic programming as described in "Generic Programming – an Introduction". The classAnimal{ // ... }; classCar{ // ... }; template<typenameT> classMyList{ // Class contents. }; MyList<Animal>animalList; MyList<Car>carList;

Above, T is a placeholder for whatever type is specified when the list is created. These "generic objects of type T", commonly called templates, allow a class to be reused with different datatypes as long as certain contracts such as subtypes and signature are kept. This genericity mechanism should not be confused with inclusion polymorphism, which is the algorithmic usage of exchangeable sub-classes: for instance, a list of objects of type MovingEntity containing objects of type Animal and Car. Templates can also be used for type-independent functions as in the swapping example below:

\ntemplate <typename T>\nvoid swap(T& a, T& b) noexcept {\n T temp = b;\n b = a;\n a = temp;\n}\n\nint main(int argc, char* argv[]) {\n string world = \"World!\";\n string hello = \"Hello,\";\n swap(world, hello);\n std::println(\"{} {}\", world, hello); // Output is \"Hello, World!\".\n}\n"}}'>importstd; usingstd::string; // A similar, but safer and potentially faster function // is defined in the standard library header <utility> template<typenameT> voidswap(T&a,T&b)noexcept{ Ttemp=b; b=a; a=temp; } intmain(intargc,char*argv[]){ stringworld="World!"; stringhello="Hello,"; swap(world,hello); std::println("{} {}",world,hello);// Output is "Hello, World!". }

The C++ template construct used above is widely cited type Bookmark_Type is new Natural; -- records a location in the text document we are editing package Bookmark_Stacks is new Stacks (Max_Size => 20, Element_Type => Bookmark_Type); -- Allows the user to jump between recorded locations in a document

Using an instance of a generic package:

Document.Bookmarks, Initial_Size => 10);\n -- Now, open the file Document_Name and read it in...\n end Edit;\n"}}'> type Document_Type is record Contents : Ada.Strings.Unbounded.Unbounded_String; Bookmarks : Bookmark_Stacks.Stack; end record; procedure Edit (Document_Name : in String) is Document : Document_Type; begin -- Initialise the stack of bookmarks: Bookmark_Stacks.Create (S => Document.Bookmarks, Initial_Size => 10); -- Now, open the file Document_Name and read it in... end Edit;

Advantages and limits

edit

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:

); -- must be a discrete type\n type Element_Type is private; -- can be any nonlimited type\n type Array_Type is array (Index_Type range <>) of Element_Type;\n"}}'> generic type Index_Type is (<>); -- must be a discrete type type Element_Type is private; -- can be any nonlimited type type Array_Type is array (Index_Type range <>) of Element_Type;

In this example, Array_Type is constrained by both Index_Type and Element_Type. When instantiating the unit, the programmer must pass an actual array type that satisfies these constraints.

The disadvantage of this fine-grained control is a complicated syntax, but, because all generic formal parameters are completely defined in the specification, the compiler can instantiate generics without looking at the body of the generic.

Unlike C++, Ada does not allow specialised generic instances, and requires that all generics be instantiated explicitly. These rules have several consequences:

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, and at compile time, since no new object code is required for a new instance.
- actual objects corresponding to a generic formal object are always considered to be non-static inside the generic; see 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.
all instantiations being explicit, there are no hidden instantiations that might make it difficult to understand the program.
Ada does not permit arbitrary computation at compile time, because operations on generic arguments are performed at runtime.

C++

edit

template<typenameT> [[nodiscard]] constexprTmax(Tx,Ty)noexcept{ returnx<y?y:x; }

Specializations of this function template, instantiations with specific types, can be called just like an ordinary function:

importstd; usingstd::totally_ordered; // in typename declaration: template<totally_orderedT> [[nodiscard]] constexprTmax(Tx,Ty)noexcept{ returnx<y?y:x; } // in requires clause: template<typenameT> requirestotally_ordered<T> [[nodiscard]] constexprTmax(Tx,Ty)noexcept{ returnx<y?y:x; }

Template specialization

edit

A powerful feature of C++'s templates is template specialization. This allows alternative implementations to be provided based on certain characteristics of the parameterized type that is being instantiated. Template specialization has two purposes: to allow certain forms of optimization, and to reduce code bloat.

For example, consider a sort() template function. One of the primary activities that such a function does is to swap or exchange the values in two of the container's positions. If the values are large (in terms of the number of bytes it takes to store each of them), then it is often quicker to first build a separate list of pointers to the objects, sort those pointers, and then build the final sorted sequence. If the values are quite small however it is usually fastest to just swap the values in-place as needed. Furthermore, if the parameterized type is already of some pointer-type, then there is no need to build a separate pointer array. Template specialization allows the template creator to write different implementations and to specify the characteristics that the parameterized type(s) must have for each implementation to be used.

Unlike function templates, class templates can be partially specialized. That means that an alternate version of the class template code can be provided when some of the template parameters are known, while leaving other template parameters generic. This can be used, for example, to create a default implementation (the primary specialization) that assumes that copying a parameterizing type is expensive and then create partial specializations for types that are cheap to copy, thus increasing overall efficiency. Clients of such a class template just use specializations of it without needing to know whether the compiler used the primary specialization or some partial specialization in each case. Class templates can also be fully specialized, which means that an alternate implementation can be provided when all of the parameterizing types are known.

Advantages and disadvantages

edit

Some uses of templates, such as the max() function, were formerly filled by function-like preprocessor macros (a legacy of the C language). For example, here is a possible implementation of such macro:

D

edit

The 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 static if statement provide an alternative to respectively C++'s C++ concepts and if constexpr.
The is(...) expression allows speculative instantiation to verify an object's traits at compile time.
The auto keyword and the typeof 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).

Templates in D use a different syntax than in C++: whereas in C++ template parameters are wrapped in angular brackets (Template<param1, param2>), D uses an exclamation sign and parentheses: Template!(param1, param2). This avoids the C++ parsing difficulties due to ambiguity with comparison operators. If there is only one parameter, the parentheses can be omitted.

Conventionally, D combines the above features to provide compile-time polymorphism using trait-based generic programming. For example, an input range is defined as any type that satisfies the checks performed by isInputRange, which is defined as follows:

View original on Wikipedia | Back | FazBrowse Home