Generic programming

Last updated

Generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered by the ML programming language in 1973, [1] [2] permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication. Such software entities are known as generics in Ada, C#, Delphi, Eiffel, F#, Java, Nim, Python, Rust, Swift, TypeScript and Visual Basic .NET. They are known as parametric polymorphism in ML, Scala, Julia, and Haskell (the Haskell community also uses the term "generic" for a related but somewhat different concept); templates in C++ and D; and parameterized types in the influential 1994 book Design Patterns . [3]

Contents

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 whereby fundamental requirements on 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 paradigms

Generic programming is defined in Musser & Stepanov (1989) as follows,

Generic programming centers around the idea of abstracting from concrete, efficient algorithms to obtain generic algorithms that can be combined with different data representations to produce a wide variety of useful software.

Musser, David R.; Stepanov, Alexander A., Generic Programming [5]

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. find, sort etc., a direct approach would implement each algorithm specifically for each data structure, giving 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 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. [10]

Note that although this approach often utilizes language features of compile-time genericity/templates, it is in fact independent of particular language-technical details. Generic programming pioneer Alexander Stepanov wrote,

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 [11] [12]

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 [13]

Bjarne Stroustrup noted,

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 [12]

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 genericity

Genericity 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 language.

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 utilized 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 usages still serve a similar purpose of code-saving and the rendering of 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 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:

template<typenameT>classList{// Class contents.};List<Animal>list_of_animals;List<Car>list_of_cars;

Above, T is a placeholder for whatever type is specified when the list is created. These "containers-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 Moving_Object containing objects of type Animal and Car. Templates can also be used for type-independent functions as in the Swap example below:

// "&" passes parameters by referencetemplate<typenameT>voidSwap(T&a,T&b){Ttemp=b;b=a;a=temp;}std::stringhello="World!";std::stringworld="Hello, ";Swap(world,hello);std::cout<<hello<<world<<std::endl;// Output is "Hello, World!".

The C++ template construct used above is widely cited[ citation needed ] 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 J2SE 5.0.

C# 2.0, Oxygene 1.5 (also known as Chrome) and Visual Basic .NET 2005 have constructs that take advantage of the support for generics present in the 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.

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.

Example

The specification of a generic package:

genericMax_Size:Natural;-- a generic formal valuetypeElement_Typeisprivate;-- a generic formal type; accepts any nonlimited typepackageStacksistypeSize_Typeisrange0..Max_Size;typeStackislimitedprivate;procedureCreate(S: outStack;Initial_Size: inSize_Type:=Max_Size);procedurePush(Into: inoutStack;Element: inElement_Type);procedurePop(From: inoutStack;Element: outElement_Type);Overflow:exception;Underflow:exception;privatesubtypeIndex_TypeisSize_Typerange1..Max_Size;typeVectorisarray(Index_Typerange<>)ofElement_Type;typeStack(Allocated_Size: Size_Type:=0)isrecordTop:Index_Type;Storage:Vector(1..Allocated_Size);end record;endStacks;

Instantiating the generic package:

typeBookmark_TypeisnewNatural;-- records a location in the text document we are editingpackageBookmark_Stacksis newStacks(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:

typeDocument_TypeisrecordContents:Ada.Strings.Unbounded.Unbounded_String;Bookmarks:Bookmark_Stacks.Stack;end record;procedureEdit(Document_Name: inString)isDocument: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...endEdit;
Advantages and limitations

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:

generictypeIndex_Typeis(<>);-- must be a discrete typetypeElement_Typeisprivate;-- can be any nonlimited typetypeArray_Typeisarray(Index_Typerange<>)ofElement_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, as well as 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 "template metaprogramming", because it does not allow specialisations.

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 considered Turing complete.

Technical overview

There are two kinds of templates: 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 max(x, y) that creates functions that return either x or y, whichever is larger. max() could be defined like this:

template<typenameT>Tmax(Tx,Ty){returnx<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 max and determines that this is a call to max(int, int). It then instantiates a version of the function where the parameterizing type T is int, making the equivalent of the following function:

intmax(intx,inty){returnx<y?y:x;}

This works whether the arguments x and y are integers, strings, or any other type for which the expression x < y is sensible, or more specifically, for any type for which operator< 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. A program defining a custom data type can use operator overloading to define the meaning of < for that type, thus allowing its use with the max() 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 < allows a type to be used with the standard sort(), stable_sort(), and binary_search() algorithms or to be put inside data structures such as sets, heaps, and associative arrays.

C++ templates are completely type safe at compile time. As a demonstration, the standard type complex does not define the < operator, because there is no strict order on complex numbers. Therefore, max(x, y) will fail with a compile error, if x and y are complex values. Likewise, other templates that rely on < cannot be applied to complex data unless a comparison (in the form of a functor or function) is provided. E.g.: A complex cannot be used as key for a map 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 method protocol can alleviate this issue. Languages which use compare instead of < can also use complex values as keys.

The second 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 list<int>. A list of strings is denoted list<string>. A list has a set of standard functions associated with it, that work for any compatible parameterizing types.

Template specialization

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

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

#define max(a,b) ((a) < (b) ? (b) : (a))

Macros are expanded by preprocessor, before compilation proper; templates are expanded at compile time. Macros are always expanded inline; templates can also be expanded as inline functions when the compiler deems it appropriate. Thus both function-like macros and function templates have no run-time overhead.

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, and code bloat:

  1. 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 complicated tricks which leads to bloated, hard to understand and hard to maintain code. Current developments in the C++ standards exacerbate this problem by making heavy use of these tricks and building a lot of new features for templates on them or with them in mind.
  2. Many compilers historically have poor support for templates, thus the use of templates can make code somewhat less portable. Support may also be poor when a C++ compiler is being used with a linker that is not C++-aware, or when attempting to use templates across shared library boundaries. Most modern compilers however now have fairly robust and standard template support, and the new C++ standard, C++11, further addresses these issues.
  3. Almost all compilers produce confusing, long, or sometimes unhelpful error messages when errors are detected in code that uses templates. [18] This can make templates difficult to develop.
  4. Finally, the use of templates requires the compiler to generate a separate instance of the templated class or function for every permutation of 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:

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 [19]

The extra instantiations generated by templates can also cause 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, because the compiler needs to perform macro-like expansions of templates and generate different instances of them at compile time, the implementation source code for the templated class or function must be available (e.g. included in a header) to the code using it. Templated classes or functions, including much of the Standard Template Library (STL), 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 D

The D programming language supports templates based in design on C++. Most C++ template idioms will carry over to D without alteration, but D adds some additional functionality:

  • Template parameters in D are not restricted to just types and primitive values, 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 C++'s substitution failure is not an error (SFINAE) mechanism, similar to C++ concepts.
  • 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). [20]

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:

templateisInputRange(R){enumboolisInputRange=is(typeof((inoutint=0){Rr=R.init;// can define a range objectif(r.empty){}// can test for emptyr.popFront();// can invoke popFront()autoh=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:

autofun(Range)(Rangerange)if(isInputRange!Range){// ...}
Code generation

In addition to template metaprogramming, D also provides several features to enable compile-time code generation:

  • The import 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 compilation.
  • User-defined attributes allow users to attach arbitrary identifiers to declarations, which can then be enumerated using compile-time reflection.
  • Compile-Time Function Execution (CTFE) allows a subset of D (restricted to safe operations) to be interpreted during compilation.
  • String mixins allow evaluating and compiling the contents of a string expression as D code that becomes part of the program.

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 expression and compile-time function execution also allow efficiently implementing domain-specific languages. 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:

// Import the contents of example.htt as a string manifest constant.enumhtmlTemplate=import("example.htt");// Transpile the HTML template to D code.enumhtmlDCode=htmlTemplateToD(htmlTemplate);// Paste the contents of htmlDCode as D code.mixin(htmlDCode);

Genericity in Eiffel

Generic classes have been a part of Eiffel since the original method and language design. The foundation publications of Eiffel, [21] [22] use the term genericity to describe the creation and use of generic classes.

Basic/Unconstrained genericity

Generic classes are declared with their class name and a list of one or more formal generic parameters. In the following code, class LIST has one formal generic parameter G

classLIST[G]...feature-- Accessitem:G-- The item currently pointed to by cursor...feature-- Element changeput(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 ACCOUNT and DEPOSIT are other class names. ACCOUNT and DEPOSIT are considered actual generic parameters as they provide real class names to substitute for G in actual use.

list_of_accounts:LIST[ACCOUNT]-- Account listlist_of_deposits:LIST[DEPOSIT]-- Deposit list

Within the Eiffel type system, although class LIST [G] is considered a class, it is not considered a type. However, a generic derivation of LIST [G] such as LIST [ACCOUNT] is considered a type.

Constrained genericity

For the list class shown above, an actual generic parameter substituting for G 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 SORTED_LIST below, the generic constraint dictates that any valid actual generic parameter will be a class that inherits from class COMPARABLE. The generic constraint ensures that elements of a SORTED_LIST can in fact be sorted.

classSORTED_LIST[G->COMPARABLE]

Generics in Java

Support 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. For example, a List<String> is converted to the raw type List. The compiler inserts type casts to convert the elements to the String type when they are retrieved from the list, reducing performance compared to other implementations such as C++ templates.

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. [23] Although similar to generics in Java, .NET generics do not apply type erasure, 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, as well as alleviating some of the limitations of erasure (such as being unable to create generic arrays). [24] [25] 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. [26]

.NET allows six varieties of generic type constraints using the where keyword including restricting generic types to be value types, to be classes, to have constructors, and to implement interfaces. [27] Below is an example with an interface constraint:

usingSystem;classSample{staticvoidMain(){int[]array={0,1,2,3};MakeAtLeast<int>(array,2);// Change array to { 2, 2, 2, 3 }foreach(intiinarray)Console.WriteLine(i);// Print results.Console.ReadKey(true);}staticvoidMakeAtLeast<T>(T[]list,Tlowest)whereT:IComparable<T>{for(inti=0;i<list.Length;i++)if(list[i].CompareTo(lowest)<0)list[i]=lowest;}}

The MakeAtLeast() method allows operation on arrays, with elements of generic type T. The method's type constraint indicates that the method is applicable to any type T that implements the generic IComparable<T> interface. This ensures a compile time error, if the method is called if the type does not support comparison. The interface provides the generic method CompareTo(T).

The above method could also be written without generic types, simply using the non-generic Array type. However, since arrays are contravariant, the casting would not be type safe, and the compiler would be unable to find certain possible errors that would otherwise be caught when using generic types. In addition, the method would need to access the array items as objects instead, and would require casting to compare two elements. (For value types like types such as int this requires a boxing conversion, although this can be worked around using the Comparer<T> class, as is done in the standard collection classes.)

A notable behavior of static members in a generic .NET class is static member instantiation per run-time type (see example below).

//A generic classpublicclassGenTest<T>{//A static variable - will be created for each type on reflectionstaticCountedInstancesOnePerType=newCountedInstances();//a data memberprivateTmT;//simple constructorpublicGenTest(TpT){mT=pT;}}//a classpublicclassCountedInstances{//Static variable - this will be incremented once per instancepublicstaticintCounter;//simple constructorpublicCountedInstances(){//increase counter by one during object instantiationCountedInstances.Counter++;}}//main code entry point//at the end of execution, CountedInstances.Counter = 2GenTest<int>g1=newGenTest<int>(1);GenTest<int>g11=newGenTest<int>(11);GenTest<int>g111=newGenTest<int>(111);GenTest<double>g2=newGenTest<double>(1.0);

Genericity in Delphi

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:

programSample;{$APPTYPE CONSOLE}usesGenerics.Defaults;//for IComparer<>typeTUtils=classclassprocedureMakeAtLeast<T>(Arr:TArray<T>;constLowest:T;Comparer:IComparer<T>);overload;classprocedureMakeAtLeast<T>(Arr:TArray<T>;constLowest:T);overload;end;classprocedureTUtils.MakeAtLeast<T>(Arr:TArray<T>;constLowest:T;Comparer:IComparer<T>);varI:Integer;beginifComparer=nilthenComparer:=TComparer<T>.Default;forI:=Low(Arr)toHigh(Arr)doifComparer.Compare(Arr[I],Lowest)<0thenArr[I]:=Lowest;end;classprocedureTUtils.MakeAtLeast<T>(Arr:TArray<T>;constLowest:T);beginMakeAtLeast<T>(Arr,Lowest,nil);end;varInts:TArray<Integer>;Value:Integer;beginInts:=TArray<Integer>.Create(0,1,2,3);TUtils.MakeAtLeast<Integer>(Ints,2);forValueinIntsdoWriteLn(Value);ReadLn;end.

As with C#, methods as well as 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 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 programmers are able to use generics in whichever style they prefer.

Delphi and Free Pascal example:

// Delphi styleunitA;{$ifdef fpc}{$mode delphi}{$endif}interfacetypeTGenericClass<T>=classfunctionFoo(constAValue:T):T;end;implementationfunctionTGenericClass<T>.Foo(constAValue:T):T;beginResult:=AValue+AValue;end;end.// Free Pascal's ObjFPC styleunitB;{$ifdef fpc}{$mode objfpc}{$endif}interfacetypegenericTGenericClass<T>=classfunctionFoo(constAValue:T):T;end;implementationfunctionTGenericClass.Foo(constAValue:T):T;beginResult:=AValue+AValue;end;end.// example usage, Delphi styleprogramTestGenDelphi;{$ifdef fpc}{$mode delphi}{$endif}usesA,B;varGC1:A.TGenericClass<Integer>;GC2:B.TGenericClass<String>;beginGC1:=A.TGenericClass<Integer>.Create;GC2:=B.TGenericClass<String>.Create;WriteLn(GC1.Foo(100));// 200WriteLn(GC2.Foo('hello'));// hellohelloGC1.Free;GC2.Free;end.// example usage, ObjFPC styleprogramTestGenDelphi;{$ifdef fpc}{$mode objfpc}{$endif}usesA,B;// required in ObjFPCtypeTAGenericClassInt=specializeA.TGenericClass<Integer>;TBGenericClassString=specializeB.TGenericClass<String>;varGC1:TAGenericClassInt;GC2:TBGenericClassString;beginGC1:=TAGenericClassInt.Create;GC2:=TBGenericClassString.Create;WriteLn(GC1.Foo(100));// 200WriteLn(GC2.Foo('hello'));// hellohelloGC1.Free;GC2.Free;end.

Functional languages

Genericity in Haskell

The type class mechanism of Haskell supports generic programming. Six of the predefined type classes in Haskell (including Eq, the types that can be compared for equality, and Show, 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 instance, the following declaration of a type of binary trees states that it is to be an instance of the classes Eq and Show:

dataBinTreea=Leafa|Node(BinTreea)a(BinTreea)deriving(Eq,Show)

This results in an equality function (==) and a string representation function (show) being automatically defined for any type of the form BinTree T provided that T itself supports those operations.

The support for derived instances of Eq and Show makes their methods == and show generic in a qualitatively different way from para-metrically polymorphic functions: these "functions" (more accurately, type-indexed families of functions) can be applied to values of various types, and although they behave differently for every argument type, little work is needed to add support for a new type. Ralf Hinze (2004) has shown that a similar effect can be achieved for user-defined type classes by certain programming techniques. Other researchers have proposed approaches to this and other kinds of genericity in the context of Haskell and extensions to Haskell (discussed below).

PolyP

PolyP 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 as well as nested datatypes, where the recursive calls are of a different form. The flatten function in PolyP is here provided as an example:

flatten::Regulard=>da->[a]flatten=cataflpolytypicfl::fa[a]->[a]casefofg+h->eitherflflg*h->\(x,y)->flx++fly()->\x->[]Par->\x->[x]Rec->\x->xd@g->concat.flatten.pmapflCont->\x->[]cata::Regulard=>(FunctorOfdab->b)->da->b
Generic Haskell

Generic Haskell is another extension to Haskell, developed at Utrecht University in the Netherlands. The extensions it provides are:

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

  • Kind-indexed types are types indexed over kinds, defined by giving a case for both * and k → k'. Instances are obtained by applying the kind-indexed type to a kind.
  • Generic definitions can be used by applying them to a type or kind. This is called generic application. The result is a type or value, depending on which sort of generic definition is applied.
  • Generic abstraction enables generic definitions be defined by abstracting a type parameter (of a given kind).
  • Type-indexed types are types that are indexed over the type constructors. These can be used to give types to more involved generic values. The resulting type-indexed types can be specialized to any type.

As an example, the equality function in Generic Haskell: [28]

typeEq{[*]}t1t2=t1->t2->BooltypeEq{[k->l]}t1t2=forallu1u2.Eq{[k]}u1u2->Eq{[l]}(t1u1)(t2u2)eq{|t::k|}::Eq{[k]}tteq{|Unit|}__=Trueeq{|:+:|}eqAeqB(Inla1)(Inla2)=eqAa1a2eq{|:+:|}eqAeqB(Inrb1)(Inrb2)=eqBb1b2eq{|:+:|}eqAeqB__=Falseeq{|:*:|}eqAeqB(a1:*:b1)(a2:*:b2)=eqAa1a2&&eqBb1b2eq{|Int|}=(==)eq{|Char|}=(==)eq{|Bool|}=(==)

Clean

Clean 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 languages

The ML family of programming languages 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 templating à la C++.

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 the 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. [29]

VHDL, being derived from Ada, also has generic capabilities.

See also

Related Research Articles

Templates are a feature of the C++ programming language that allows functions and classes to operate with generic types. This allows a function or class to work on many different data types without being rewritten for each one.

C++ General-purpose programming language

C++ is a general-purpose programming language created by Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significantly over time, and modern C++ now has object-oriented, generic, and functional features in addition to facilities for low-level memory manipulation. It is almost always implemented as a compiled language, and many vendors provide C++ compilers, including the Free Software Foundation, LLVM, Microsoft, Intel, Oracle, and IBM, so it is available on many platforms.

Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.

The Standard Template Library (STL) is a software library for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators.

Template metaprogramming (TMP) is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates include compile-time constants, data structures, and complete functions. The use of templates can be thought of as compile-time polymorphism. The technique is used by a number of languages, the best-known being C++, but also Curl, D, and XL.

In computer science, an object type is a datatype that is used in object-oriented programming to wrap a non-object type to make it look like a dynamic object.

The Glasgow Haskell Compiler (GHC) is an open-source native code compiler for the functional programming language Haskell. It provides a cross-platform environment for the writing and testing of Haskell code and it supports numerous extensions, libraries, and optimisations that streamline the process of generating and executing code. GHC is the most commonly used Haskell compiler. The lead developers are Simon Peyton Jones and Simon Marlow.

Many programming language type systems support subtyping. For instance, if the type Cat is a subtype of Animal, then an expression of type Cat should be substitutable wherever an expression of type Animal is used.

<i>Modern C++ Design</i>

Modern C++ Design: Generic Programming and Design Patterns Applied is a book written by Andrei Alexandrescu, published in 2001 by Addison-Wesley. It has been regarded as "one of the most important C++ books" by Scott Meyers.

typedef is a reserved keyword in the programming languages C and C++. It is used to create an additional name (alias) for another data type, but does not create a new type, except in the obscure case of a qualified typedef of an array type where the typedef qualifiers are transferred to the array element type. As such, it is often used to simplify the syntax of declaring complex data structures consisting of struct and union types, but is just as common in providing specific descriptive type names for integer data types of varying lengths.

In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without depending on their type. Such functions and data types are called generic functions and generic datatypes respectively and form the basis of generic programming.

In computer science, a type class is a type system construct that supports ad hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and a type variable a, and means that a can only be instantiated to a type whose members support the overloaded operations associated with T.

A class in C++ is a user-defined type or data structure declared with keyword class that has data and functions as its members whose access is governed by the three access specifiers private, protected or public. By default access to members of a C++ class is private. The private members are not accessible outside the class; they can be accessed only through methods of the class. The public members form an interface to the class and are accessible outside the class.

sizeof is a unary operator in the programming languages C and C++. It generates the storage size of an expression or a data type, measured in the number of char-sized units. Consequently, the construct sizeof (char) is guaranteed to be 1. The actual number of bits of type char is specified by the preprocessor macro CHAR_BIT, defined in the standard include file limits.h. On most modern computing platforms this is eight bits. The result of sizeof has an unsigned integer type that is usually denoted by size_t.

In computer programming, an enumerated type is a data type consisting of a set of named values called elements, members, enumeral, or enumerators of the type. The enumerator names are usually identifiers that behave as constants in the language. An enumerated type can be seen as a degenerate tagged union of unit type. A variable that has been declared as having an enumerated type can be assigned any of the enumerators as a value. In other words, an enumerated type has values that are different from each other, and that can be compared and assigned, but are not specified by the programmer as having any particular concrete representation in the computer's memory; compilers and interpreters can represent them arbitrarily.

C++11 is a version of the standard for the programming language C++. It was approved by International Organization for Standardization (ISO) on 12 August 2011, replacing C++03, superseded by C++14 on 18 August 2014 and later, by C++17. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

This article describes the syntax of the C# programming language. The features described are compatible with .NET Framework and Mono.

ATS (programming language) Programming language

ATS is a programming language designed to unify programming with formal specification. ATS has support for combining theorem proving with practical programming through the use of advanced type systems. A past version of The Computer Language Benchmarks Game has demonstrated that the performance of ATS is comparable to that of the C and C++ programming languages. By using theorem proving and strict type checking, the compiler can detect and prove that its implemented functions are not susceptible to bugs such as division by zero, memory leaks, buffer overflow, and other forms of memory corruption by verifying pointer arithmetic and reference counting before the program compiles. Additionally, by using the integrated theorem-proving system of ATS (ATS/LF), the programmer may make use of static constructs that are intertwined with the operative code to prove that a function attains its specification.

In C++ computer programming, allocators are a component of the C++ Standard Library. The standard library provides several data structures, such as list and set, commonly referred to as containers. A common trait among these containers is their ability to change size during the execution of the program. To achieve this, some form of dynamic memory allocation is usually required. Allocators handle all the requests for allocation and deallocation of memory for a given container. The C++ Standard Library provides general-purpose allocators that are used by default, however, custom allocators may also be supplied by the programmer.

The programming language C# introduces several new features in version 2.0. These include:

References

  1. Lee, Kent D. (15 December 2008). Programming Languages: An Active Learning Approach. Springer Science & Business Media. pp. 9–10. ISBN   978-0-387-79422-8.
  2. Milner, R.; Morris, L.; Newey, M. (1975). "A Logic for Computable Functions with Reflexive and Polymorphic Types". Proceedings of the Conference on Proving and Improving Programs.
  3. Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John (1994). Design Patterns . Addison-Wesley. ISBN   0-201-63361-2.
  4. Musser & Stepanov 1989.
  5. Musser, David R.; Stepanov, Alexander A. Generic Programming (PDF).
  6. Alexander Stepanov; Paul McJones (19 June 2009). Elements of Programming. Addison-Wesley Professional. ISBN   978-0-321-63537-2.
  7. Musser, David R.; Stepanov, Alexander A. (1987). "A library of generic algorithms in Ada". Proceedings of the 1987 Annual ACM SIGAda International Conference on Ada: 216–225. CiteSeerX   10.1.1.588.7431 . doi:10.1145/317500.317529. ISBN   0897912438. S2CID   795406.
  8. Alexander Stepanov and Meng Lee: The Standard Template Library. HP Laboratories Technical Report 95-11(R.1), 14 November 1995
  9. Matthew H. Austern: Generic programming and the STL: using and extending the C++ Standard Template Library. Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA 1998
  10. Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley 2001
  11. Stepanov, Alexander. Short History of STL (PDF).
  12. 1 2 Stroustrup, Bjarne. Evolving a language in and for the real world: C++ 1991-2006 (PDF). doi:10.1145/1238844.1238848. S2CID   7518369.
  13. Lo Russo, Graziano. "An Interview with A. Stepanov".
  14. Roland Backhouse; Patrik Jansson; Johan Jeuring; Lambert Meertens (1999). Generic Programming – an Introduction (PDF).
  15. Lämmel, Ralf; Peyton Jones, Simon. "Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming" (PDF). Microsoft. Retrieved 16 October 2016.
  16. Gabriel Dos Reis; Jaakko Ja ̈rvi (2005). "What is Generic Programming? (preprint LCSD'05)" (PDF). Archived from the original (PDF) on 25 December 2005.
  17. R. Garcia; J. Ja ̈rvi; A. Lumsdaine; J. Siek; J. Willcock (2005). "An extended comparative study of language support for generic programming (preprint)". CiteSeerX   10.1.1.110.122 .Cite journal requires |journal= (help)
  18. Stroustrup, Dos Reis (2003): Concepts - Design choices for template argument checking
  19. Stroustrup, Bjarne (1994). "15.5 Avoiding Code Replication". The Design and Evolution of C++. Reading, Massachusetts: Addison-Wesley. pp. 346–348. Bibcode:1994dec..book.....S. ISBN   978-81-317-1608-3.
  20. Bright, Walter. "Voldemort Types in D". Dr. Dobbs. Retrieved 3 June 2015.
  21. Object-Oriented Software Construction, Prentice Hall, 1988, and Object-Oriented Software Construction, second edition, Prentice Hall, 1997.
  22. Eiffel: The Language, Prentice Hall, 1991.
  23. .NET/C# Generics History: Some Photos From Feb 1999
  24. C#: Yesterday, Today, and Tomorrow: An Interview with Anders Hejlsberg
  25. Generics in C#, Java, and C++
  26. Code Analysis CA1006: Do not nest generic types in member signatures
  27. Constraints on Type Parameters (C# Programming Guide)
  28. The Generic Haskell User's Guide
  29. Verilog by Example, Section The Rest for Reference. Blaine C. Readler, Full Arc Press, 2011. ISBN   978-0-9834973-0-1

Sources

Further reading

C++/D
C#/.NET
Delphi/Object Pascal
Eiffel
Haskell
Java