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,[1][2] 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.[3] 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#, Delphi, Eiffel, F#, Java, 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[4] 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. Stepanov–Musser and other generic programming paradigmsGeneric programming is defined in Musser & Stepanov (1989) as follows,
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 concepts, analogously to the abstraction of algebraic theories in abstract algebra.[6] Early examples of this programming approach were implemented in Scheme and Ada,[7] although the best known example is the Standard Template Library (STL),[8][9] which developed a theory of iterators 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. 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,
Bjarne Stroustrup noted,
Other programming paradigms that have been described as generic programming include Datatype generic programming as described in "Generic Programming – an Introduction".[14] The Scrap your boilerplate approach is a lightweight generic programming approach for Haskell.[15] In this article we distinguish the high-level programming paradigms of generic programming, above, from the lower-level programming language genericity mechanisms used to implement them (see Programming language support for genericity). For further discussion and comparison of generic programming paradigms, see.[16] Programming language support for genericityGenericity facilities have existed in high-level languages since at least the 1970s in languages such as ML, CLU and Ada, and were subsequently adopted by many object-based and object-oriented languages, including BETA, C++, D, Eiffel, Java, and 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 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] 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. Arrays and 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 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.[17] In object-oriented languagesWhen 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: template<typename T>
class List {
// Class contents.
};
List<Animal> list_of_animals;
List<Car> list_of_cars;
Above, // "&" 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>
T temp = b;
b = a;
a = temp;
}
std::string world = "World!";
std::string hello = "Hello, ";
Swap(world, hello);
std::cout << world << hello << ‘\n’; // Output is "Hello, World!".
The C++ C# 2.0, 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
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.[18] 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. To instantiate a generic unit, the programmer passes actual parameters for each formal. The generic instance then behaves just like any other unit. It is possible to instantiate generic units at run-time, for example inside a loop. ExampleThe specification of a generic package: generic
Max_Size : Natural; -- a generic formal value
type Element_Type is private; -- a generic formal type; accepts any nonlimited type
package Stacks is
type Size_Type is range 0 .. Max_Size;
type Stack is limited private;
procedure Create (S : out Stack;
Initial_Size : in Size_Type := Max_Size);
procedure Push (Into : in out Stack; Element : in Element_Type);
procedure Pop (From : in out Stack; Element : out Element_Type);
Overflow : exception;
Underflow : exception;
private
subtype Index_Type is Size_Type range 1 .. Max_Size;
type Vector is array (Index_Type range <>) of Element_Type;
type Stack (Allocated_Size : Size_Type := 0) is record
Top : Index_Type;
Storage : Vector (1 .. Allocated_Size);
end record;
end Stacks;
Instantiating the generic package: 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: 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 limitsThe 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: 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:
Templates in 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. Using template specialization, C++ Templates are Turing complete. Technical overviewThere 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 template<typename T>
T max(T x, T y) {
return x < y ? y : x;
}
Specializations of this function template, instantiations with specific types, can be called just like an ordinary function: std::cout << max(3, 7); // Outputs 7.
The compiler examines the arguments used to call int max(int x, int y) {
return x < y ? y : x;
}
This works whether the arguments C++ templates are completely type safe at compile time. As a demonstration, the standard type 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 linked list container. To make a linked list of integers, one writes Template specializationA 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 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 disadvantagesSome uses of templates, such as the #define max(a,b) ((a) < (b) ? (b) : (a))
Macros are expanded (copy pasted) by the preprocessor, before program compiling; templates are actual real functions. Macros are always expanded inline; templates can also be inline functions when the compiler deems it appropriate. 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 substitution failure is not an error (SFINAE)), and code bloat:
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. Also, the implementation source code for the template must be completely available (e.g. included in a header) to the translation unit (source file) using it. Templates, including much of the Standard Library, if not included in header files, cannot be compiled. (This is in contrast to non-templated code, which may be compiled to binary, providing only a declarations header file for code using it.) This may be a disadvantage by exposing the implementing code, which removes some abstractions, and could restrict its use in closed-source projects.[citation needed] Templates in DThe D language supports templates based in design on C++. Most C++ template idioms work in D without alteration, but D adds some functionality:
Templates in D use a different syntax than in C++: whereas in C++ template parameters are wrapped in angular brackets ( 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 template isInputRange(R)
{
enum bool isInputRange = is(typeof(
(inout int = 0)
{
R r = R.init; // can define a range object
if (r.empty) {} // can test for empty
r.popFront(); // can invoke popFront()
auto h = r.front; // can get the front of the range
}));
}
A function that accepts only input ranges can then use the above template in a template constraint: auto fun(Range)(Range range)
if (isInputRange!Range)
{
// ...
}
Code generationIn addition to template metaprogramming, D also provides several features to enable compile-time code generation:
Combining the above allows generating code based on existing declarations. For example, D serialization frameworks can enumerate a type's members and generate specialized functions for each serialized type to perform serialization and deserialization. User-defined attributes could further indicate serialization rules. The // Import the contents of example.htt as a string manifest constant.
enum htmlTemplate = import("example.htt");
// Transpile the HTML template to D code.
enum htmlDCode = htmlTemplateToD(htmlTemplate);
// Paste the contents of htmlDCode as D code.
mixin(htmlDCode);
Genericity in EiffelGeneric classes have been a part of Eiffel since the original method and language design. The foundation publications of Eiffel,[22][23] use the term genericity to describe creating and using generic classes. Basic, unconstrained genericityGeneric classes are declared with their class name and a list of one or more formal generic parameters. In the following code, class class
LIST [G]
...
feature -- Access
item: G
-- The item currently pointed to by cursor
...
feature -- Element change
put (new_item: G)
-- Add `new_item' at the end of the list
...
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 list_of_accounts: LIST [ACCOUNT]
-- Account list
list_of_deposits: LIST [DEPOSIT]
-- Deposit list
Within the Eiffel type system, although class Constrained genericityFor the list class shown above, an actual generic parameter substituting for class
SORTED_LIST [G -> COMPARABLE]
Generics in JavaSupport for the generics, or "containers-of-type-T" was added to the 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 JVM implementations, making it unavailable at runtime.[24] For example, a Genericity in .NET [C#, VB.NET]Generics were added as part of .NET Framework 2.0 in November 2005, based on a research prototype from Microsoft Research started in 1999.[25] Although similar to generics in Java, .NET generics do not apply type erasure,[26]: 208–209 but implement generics as a first class mechanism in the runtime using reification. This design choice provides additional functionality, such as allowing reflection with preservation of generic types, and alleviating some of the limits of erasure (such as being unable to create generic arrays).[27][28] This also means that there is no performance hit from runtime casts and normally expensive boxing conversions. When primitive and value types are used as generic arguments, they get specialized implementations, allowing for efficient generic collections and methods. As in C++ and Java, nested generic types such as Dictionary<string, List<int>> are valid types, however are advised against for member signatures in code analysis design rules.[29] .NET allows six varieties of generic type constraints using the using System;
class Sample
{
static void Main()
{
int[] array = { 0, 1, 2, 3 };
MakeAtLeast<int>(array, 2); // Change array to { 2, 2, 2, 3 }
foreach (int i in array)
Console.WriteLine(i); // Print results.
Console.ReadKey(true);
}
static void MakeAtLeast<T>(T[] list, T lowest) where T : IComparable<T>
{
for (int i = 0; i < list.Length; i++)
if (list[i].CompareTo(lowest) < 0)
list[i] = lowest;
}
}
The The above method could also be written without generic types, simply using the non-generic A notable behavior of static members in a generic .NET class is static member instantiation per run-time type (see example below). // A generic class
public class GenTest<T>
{
// A static variable - will be created for each type on reflection
static CountedInstances OnePerType = new CountedInstances();
// a data member
private T _t;
// simple constructor
public GenTest(T t)
{
_t = t;
}
}
// a class
public class CountedInstances
{
//Static variable - this will be incremented once per instance
public static int Counter;
//simple constructor
public CountedInstances()
{
//increase counter by one during object instantiation
CountedInstances.Counter++;
}
}
// main code entry point
// at the end of execution, CountedInstances.Counter = 2
GenTest<int> g1 = new GenTest<int>(1);
GenTest<int> g11 = new GenTest<int>(11);
GenTest<int> g111 = new GenTest<int>(111);
GenTest<double> g2 = new GenTest<double>(1.0);
Genericity in PascalFor Pascal, generics were first implemented in 2006, in the implementation Free Pascal. In DelphiThe Object Pascal dialect 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: program Sample;
{$APPTYPE CONSOLE}
uses
Generics.Defaults; //for IComparer<>
type
TUtils = class
class procedure MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T;
Comparer: IComparer<T>); overload;
class procedure MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T); overload;
end;
class procedure TUtils.MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T;
Comparer: IComparer<T>);
var
I: Integer;
begin
if Comparer = nil then Comparer := TComparer<T>.Default;
for I := Low(Arr) to High(Arr) do
if Comparer.Compare(Arr[I], Lowest) < 0 then
Arr[I] := Lowest;
end;
class procedure TUtils.MakeAtLeast<T>(Arr: TArray<T>; const Lowest: T);
begin
MakeAtLeast<T>(Arr, Lowest, nil);
end;
var
Ints: TArray<Integer>;
Value: Integer;
begin
Ints := TArray<Integer>.Create(0, 1, 2, 3);
TUtils.MakeAtLeast<Integer>(Ints, 2);
for Value in Ints do
WriteLn(Value);
ReadLn;
end.
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. In Free PascalFree Pascal implemented generics in 2006 in 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 Delphi and Free Pascal example: // Delphi style
unit A;
{$ifdef fpc}
{$mode delphi}
{$endif}
interface
type
TGenericClass<T> = class
function Foo(const AValue: T): T;
end;
implementation
function TGenericClass<T>.Foo(const AValue: T): T;
begin
Result := AValue + AValue;
end;
end.
// Free Pascal's ObjFPC style
unit B;
{$ifdef fpc}
{$mode objfpc}
{$endif}
interface
type
generic TGenericClass<T> = class
function Foo(const AValue: T): T;
end;
implementation
function TGenericClass.Foo(const AValue: T): T;
begin
Result := AValue + AValue;
end;
end.
// example usage, Delphi style
program TestGenDelphi;
{$ifdef fpc}
{$mode delphi}
{$endif}
uses
A,B;
var
GC1: A.TGenericClass<Integer>;
GC2: B.TGenericClass<String>;
begin
GC1 := A.TGenericClass<Integer>.Create;
GC2 := B.TGenericClass<String>.Create;
WriteLn(GC1.Foo(100)); // 200
WriteLn(GC2.Foo('hello')); // hellohello
GC1.Free;
GC2.Free;
end.
// example usage, ObjFPC style
program TestGenDelphi;
{$ifdef fpc}
{$mode objfpc}
{$endif}
uses
A,B;
// required in ObjFPC
type
TAGenericClassInt = specialize A.TGenericClass<Integer>;
TBGenericClassString = specialize B.TGenericClass<String>;
var
GC1: TAGenericClassInt;
GC2: TBGenericClassString;
begin
GC1 := TAGenericClassInt.Create;
GC2 := TBGenericClassString.Create;
WriteLn(GC1.Foo(100)); // 200
WriteLn(GC2.Foo('hello')); // hellohello
GC1.Free;
GC2.Free;
end.
Functional languagesGenericity in HaskellThe type class mechanism of Haskell supports generic programming. Six of the predefined type classes in Haskell (including data BinTree a = Leaf a | Node (BinTree a) a (BinTree a)
deriving (Eq, Show)
This results in an equality function ( The support for derived instances of PolyPPolyP was the first generic programming language extension to Haskell. In PolyP, generic functions are called polytypic. The language introduces a special construct in which such polytypic functions can be defined via structural induction over the structure of the pattern functor of a regular datatype. Regular datatypes in PolyP are a subset of Haskell datatypes. A regular datatype t must be of kind * → *, and if a is the formal type argument in the definition, then all recursive calls to t must have the form t a. These restrictions rule out higher-kinded datatypes and nested datatypes, where the recursive calls are of a different form. The flatten function in PolyP is here provided as an example: flatten :: Regular d => d a -> [a]
flatten = cata fl
polytypic fl :: f a [a] -> [a]
case f of
g+h -> either fl fl
g*h -> \(x,y) -> fl x ++ fl y
() -> \x -> []
Par -> \x -> [x]
Rec -> \x -> x
d@g -> concat . flatten . pmap fl
Con t -> \x -> []
cata :: Regular d => (FunctorOf d a b -> b) -> d a -> b
Generic HaskellGeneric Haskell is another extension to Haskell, developed at Utrecht University in the Netherlands. The extensions it provides are:
The resulting type-indexed value can be specialized to any type.
As an example, the equality function in Generic Haskell:[31] 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)
eq {| t :: k |} :: Eq {[ k ]} t t
eq {| Unit |} _ _ = True
eq {| :+: |} eqA eqB (Inl a1) (Inl a2) = eqA a1 a2
eq {| :+: |} eqA eqB (Inr b1) (Inr b2) = eqB b1 b2
eq {| :+: |} eqA eqB _ _ = False
eq {| :*: |} eqA eqB (a1 :*: b1) (a2 :*: b2) = eqA a1 a2 && eqB b1 b2
eq {| Int |} = (==)
eq {| Char |} = (==)
eq {| Bool |} = (==)
CleanClean offers generic programming based PolyP and the Generic Haskell as supported by the GHC ≥ 6.0. It parametrizes by kind as those but offers overloading. Other languagesLanguages in the ML family support generic programming through parametric polymorphism and generic modules called functors. Both Standard ML and OCaml provide functors, which are similar to class templates and to Ada's generic packages. Scheme syntactic abstractions also have a connection to genericity – these are in fact a superset of C++ templates. 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 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.[32] VHDL, being derived from Ada, also has generic abilities.[33] C supports "type-generic expressions" using the #define cbrt(x) _Generic((x), long double: cbrtl, \
default: cbrt, \
float: cbrtf)(x)
See alsoReferences
Sources
Further reading
External links
|
Portal di Ensiklopedia Dunia
