| | This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (July 2007) | Generic programming is a style of computer programming where algorithms are written in an extended grammar and are made adaptable by specifying variable parts that are then somehow instantiated later by the compiler with respect to the base grammar. Image File history File links Question_book-3. ...
Image File history File links Broom_icon. ...
Programming redirects here. ...
It differs from normal programming in that it somehow invokes within the language a metaprogramming facility. Because it happens as an extension of the language, new semantics are introduced and the language is enriched in this process. It is closely related to metaprogramming, but does not involve the generation of source code (none, at least, that is visible to the user of the language). It is different from programming with macros as well, since the latter refers to textual search-and-replace and is not part of the grammar of the language but implemented by a pre-processor. One exception to this is the macro facility in programming languages that are a member of the Lisp family in which macros operate on parse trees rather than text. Metaprogramming is the writing of computer programs that write or manipulate other programs (or themselves) as their data or that do part of the work during compile time that is otherwise done at run time. ...
For other uses, see Macro (disambiguation) A macro in computer science is a rule or pattern that specifies how a certain input sequence (often a sequence of characters) should be mapped to an output sequence (also often a sequence of characters) according to a defined procedure. ...
“LISP†redirects here. ...
Generic programming facilities first appeared in the 1970s in languages like 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. CLU is a programming language created at MIT by Barbara Liskov and her students between 1974 and 1975. ...
Ada is a structured, statically typed imperative computer programming language designed by a team led by Jean Ichbiah of CII Honeywell Bull during 1977–1983. ...
In computer science, Object-based has two different, non compatible, senses: A) A limited version of object-oriented programming where one or more of the following restrictions applies: there is no implicit inheritance there is no polymorphism only a very reduced subset of the available values are objects (typically the...
Object-oriented programming (OOP) is a programming paradigm that uses objects and their interactions to design applications and computer programs. ...
BETA is a pure object-oriented language from the Scandinavian School in System Development where the first object-oriented language Simula was developed. ...
C++ (pronounced ) is a general-purpose programming language. ...
D is an object-oriented, imperative system programming language designed by Walter Bright of Digital Mars as a re-engineering of C/C++. He has done this by re-designing many C++ features, and borrowing ideas from other programming languages. ...
Eiffel is an ISO-standardized object-oriented programming language designed for extensibility, reusability, reliability and programmer productivity. ...
Java language redirects here. ...
DEC, dec or Dec may refer to: December - a month of the year in the Gregorian Calendar Department of Environment and Conservation Digital Equipment Corporation - a computer and technology company, now part of HP Declination - a term from astronomy Diethylcarbamazine - a drug commonly used to treat infections by filarial parasites...
The authors of the influential 1994 book Design Patterns refer to generics as 'parameterized types', which are also known as 'generics' (Ada, Eiffel, Java, C#, VB .NET) or 'templates' (C++). These allow a type to be defined without specifying all the other types it uses--the unspecified types are supplied as parameters at the point of use. The authors note that this technique (especially when combined with delegation) is very powerful, and also that: "Dynamic, highly parameterized software is harder to understand than more static software." (Gang of Four 1995:21) This article is about the book by Gamma et al. ...
In software engineering, the Gang of Four (or GoF) are Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, authors of the seminal book Design Patterns. ...
Generic programming is implemented and supported differently within each language; the term "generic" has also been used differently in 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 generic programming capacities, which, however, are not referred to as such in most Forth texts. Some interpreted languages like Python expose their internals allowing one to create meta-classes. 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. In these uses generic programming still serves the similar purpose of code-saving and the rendering of an abstraction. Forth is a programming language and programming environment, initially developed by Charles H. Moore at the US National Radio Astronomy Observatory in the early 1970s. ...
Python is a general-purpose, high-level programming language. ...
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. ...
Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
A structual type system is a major class of type system, in which type compatibility and equivalence are determined by the types structure, and not through explicit declarations. ...
Generic programming in object-oriented languages
As an example of the benefits of generic programming, when creating containers of objects it is common to write specific implementations for each datatype contained, even if the code is virtually identical except for different datatypes. Instead, a possible declaration using generic programming could be to define a template class (using the C++ idiom): template<typename T> class List { /* class contents */ }; List<Animal> list_of_animals; List<Car> list_of_cars; Above T represents the type to be instantiated. The list generated is then treated as a list of whichever type is specified. These "containers-of-type-T", commonly called generics, are a generic programming technique that allows the defining of a class that takes and contains different datatypes as long as certain contracts such as subtypes and signature are kept. Generic programming should not to 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. Although the example above is the most common use of generic programming, and some languages implement only this aspect of it, generic programming as a concept is not limited to generics. Another application is type-independent functions as in the Swap example below: In computer science, a subtype is a datatype that is generally related to another datatype (the supertype) by some notion of substitutability, meaning that computer programs written to operate on elements of the supertype can also operate on elements of the subtype. ...
The signature of a function is roughly equivalent to its prototype definition in the C programming language. ...
In computer science, polymorphism means allowing a single definition to be used with different types of data (specifically, different classes of objects). ...
Flowcharts are often used to graphically represent algorithms. ...
template<typename T> void Swap(T & a, T & b) //"&" passes parameters by reference { T temp = b; b = a; a = temp; } string hello = "world!", world = "Hello, "; Swap( world, hello ); cout << hello << world << endl; //Output is "Hello, world!" The template construct of C++ used in the examples above is widely cited as the generic programming construct that popularized the notion among programmers and language designers and provides full support for many generic programming idioms. D also offers fully generic-capable templates based on the C++ precedent but with a simplified syntax. Java has provided generic programming facilities syntactically based on C++'s since the introduction of J2SE 5.0 and implements the generics, or "containers-of-type-T", subset of generic programming. Java 2 Platform, Standard Edition or J2SE is a collection of java Application Programming Interfaces targeting Java platform applications running on a workstation. ...
C# 2.0, Chrome 1.5 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. The ML family of programming languages encourage generic programming through parametric polymorphism and generic modules called functors. The type class mechanism of Haskell supports generic programming. The title given to this article is incorrect due to technical limitations. ...
Chrome is a programming language for the Common Language Infrastructure developed by RemObjects Software. ...
Visual Basic . ...
The Microsoft . ...
ML is a general-purpose functional programming language developed by Robin Milner and others in the late 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM. Historically, ML stands for metalanguage as it was conceived to develop proof tactics in the LCF theorem prover (the language of...
In computer science, polymorphism means allowing a single definition to be used with different types of data (specifically, different classes of objects). ...
It has been suggested that this article or section be merged into Modularity (programming). ...
The type system of the Haskell programming language includes a construct called the type class that provides a powerful form of restricted parametric polymorphism. ...
Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
Dynamic typing, such as is featured in Objective-C, and, if necessary, judicious use of protocols circumvent the need for use of generic programming techniques, since there exists a general type to contain any object. While Java does so also, the casting that needs to be done breaks the discipline of static typing, and generics are one way of achieving some of the benefits of dynamic typing with the advantages of having static typing. In computer science, a type system defines how a programming language classifies values and expressions into types, how it can manipulate those types and how they interact. ...
Objective-C, often referred to as ObjC or more seldomly as Objective C or Obj-C, is an object oriented programming language implemented as an extension to C. It is used primarily on Mac OS X and GNUstep, two environments based on the OpenStep standard, and is the primary language...
An interface is a specification that exists between software components that specifies a selected means of interaction, by means of properties of other software modules, which abstract and encapsulate their data. ...
On computer science, a datatype (often simply type) is a name or label for a set of values and some operations which can be performed on that set of values. ...
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. Ada is a structured, statically typed, imperative, and object-oriented high-level computer programming language. ...
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.
Ada example The 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 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: 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, 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 nonstatic 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++ Templates are of great utility to programmers in C++, especially when combined with multiple inheritance and operator overloading. The C++ Standard Template Library (STL) provides a framework of connected templates. 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. See inheritance (computer science) for other computing uses of inheritance. ...
In computer programming, operator overloading (less commonly known as operator ad-hoc polymorphism) is a specific case of polymorphism in which some or all of operators like +, = or == have different implementations depending on the types of their arguments. ...
[[Im[[Image:Example. ...
Template metaprogramming is a programming 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. ...
Technical overview There are two kinds of templates: function templates and class templates. A function template behaves like an ordinary function, but can accept arguments of many possibly unrelated types. For example, the C++ Standard Template Library contains the function template max(x, y) which returns either x or y, whichever is larger. max() could be defined like this: template <typename T> T max(T x, T y) { if (x < y) return y; else return x; } This template can be called just like a function: cout << max(3, 7); // outputs 7 The compiler determines by examining the arguments that this is a call to max(int, int) and instantiates a version of the function where the type T is int.
This works whether the arguments x and y are integers, strings, or any other type for which it makes sense to say "x < y", or more specifically, for any type that has an operator< specified. Common inheritance is not needed for the set of types that can be used, and so it is very similar to duck typing. If a program defines a custom data type, all it needs to do is to use operator overloading to define the meaning of < for that type, thus allowing it to be used by the max() function. 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 put inside data structures such as sets, heaps, and associative arrays; and more.
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. Unfortunately, compilers historically generate somewhat esoteric and unhelpful error messages for this sort of error. Ensuring that a certain object adheres to a method protocol can alleviate this issue. In computer science, a programming language is type safe when the language does not permit the programmer to treat a value as a type to which it does not belong. ...
In mathematics, a complex number is a number which is often formally defined to consist of an ordered pair of real numbers , often written: In mathematics, the adjective complex means that the underlying number field is complex numbers, for example complex analysis, complex matrix, complex polynomial and complex Lie algebra. ...
In computer sciences object-oriented programming, a protocol (Java: interface) is what or how unrelated objects use to communicate with each other. ...
The second kind of template, a class template extends the same concept to classes. 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, which work no matter what you put between the brackets. In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ...
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.
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: In computer science, a preprocessor is a program that processes its input data to produce output that is used as input to another program. ...
C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...
#define max(a,b) ((a) < (b) ? (b) : (a)) Both macros and 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. Perhaps most importantly, templates were designed to be applicable to much larger problems than macros.
There are three primary drawbacks to the use of templates: compiler support, poor error messages, and code bloat. 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 which 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++0x, is expected to further address these issues. Figure of the linking process, where object files and static libraries are assembled into a new library or executable. ...
Illustration of an application which may use libvorbisfile. ...
C++0x is the planned new standard for the C++ programming language. ...
Almost all compilers produce confusing, long, or sometimes unhelpful error messages when errors are detected in code that uses templates. This can make templates difficult to develop.
Finally, the use of templates requires the compiler to generate a separate instance of the templated class or function for every type parameter 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 can dramatically reduce such code bloat in some cases. 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. It has been suggested that this article or section be merged into Software bloat. ...
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), 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 is bad for closed-source projects.
Templates in D The D programming language supports templates that are evolved from those in C++. Most C++ template idioms will carry over to D without alteration, but D adds functionality that streamlines some common cases. D is an object-oriented, imperative system programming language designed by Walter Bright of Digital Mars as a re-engineering of C/C++. He has done this by re-designing many C++ features, and borrowing ideas from other programming languages. ...
The most obvious differences are syntax changes. D uses parentheses ( ) instead of angle-brackets < > in a template definition. It also uses the !( ) construct (that is, parentheses preceded by an exclamation point) instead of angle-brackets in template instantiation. Therefore, a!(b) in D is the equivalent of a<b> in C++. These changes were made in the interest of making templates easier to parse, as using angle-brackets can lead to ambiguous syntax.
Static-if D provides a static if construct that checks conditions at compile-time. This is vaguely analogous to C++'s #if and #endif preprocessor macros. The major difference is that static if has access to all compile-time values, including template arguments. Therefore, many situations which require template specialization in C++ may be written inline in D. Recursive templates in D can look almost identical to their runtime equivalents. This is shown in the classic compile-time factorial template. In computer science, a preprocessor is a program that processes its input data to produce output that is used as input to another program. ...
template factorial(uint n) { static if (n < 2) const uint factorial = 1; else const uint factorial = n * factorial!(n-1); }
Alias parameters Templates in D may also accept alias parameters. Alias parameters are similar to C++'s typedef but can also substitute templates parameters. This is a superset of the functionality of template arguments in C++, and will be added in the forthcoming C++0x specification. Alias parameters may be templates, functions, types, or any other compile-time symbol. This allows a coder to, for example, "inject" a function into the middle of a template function. C++0x is the planned new standard for the C++ programming language. ...
template wrapper(alias Fn) { // Wraps a D function with an "extern(C)" interface. extern(C) void wrapper() { Fn(); } } This sort of template might be useful when interfacing D code with a C API. If a hypothetical C API wants a function pointer, you might use the template like this: void foo() { // ... } some_c_function(&wrapper!(foo));
Generics in Java -
Support for the generics, or "containers-of-type-T", subset of generic programming were added to the Java programming language in 2004 as part of J2SE 5.0. In Java, generics are checked at compile time for type correctness. The generic type information is then removed via a process called type erasure, and is 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. Generics were added to the Java programming language in 2004 as part of J2SE 5. ...
Java language redirects here. ...
The term Generic programming first appeared in object oriented languages with the appearance of generic types. ...
In computer science, type conversion or typecasting refers to changing an entity of one data type into another. ...
Generic programming in C# and .NET Generics in C# (and other .NET languages) were added as part of .NET Framework 2.0 in November 2005. Although similar to generics in Java, .NET generics do not apply type erasure, but implement generics as a first class citizen in the runtime using reification. This design choice is leveraged to provide 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).[1][2] This also means that there is no performance hit from runtime casts and 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. The Microsoft . ...
Ongoing events • Abramoff-Reed gambling scandal • Al Jazeera bombing memo • Avian influenza (H5N1) outbreak • Black sites scandal • Conservative leadership race (UK) • Fuel prices • Irans nuclear program • Jilin chemical plant explosions • Kashmir earthquake • Malawi food crisis • Malaysian prisoner abuse scandal • New Delhi bombings investigation • Niger food crisis • North Indian cyclone...
Reification, in the context of object-oriented programming, is the implementation of an abstract behavior. ...
In computer science, reflection is the process by which a computer program of the appropriate type can be modified in the process of being executed, in a manner that depends on abstract features of its code and its runtime behavior. ...
In computer science, type conversion or typecasting refers to changing an entity of one data type into another. ...
In computer science, an object type (a. ...
In object-oriented programming, a collection class is any class that is capable of storing other objects. ...
C# (and .NET in general) allows a wide range of generic type constraints using the where keyword including restricting generic types to be value types, to be classes, to have constructors, and to inherit from interfaces.[3] Below is an example with an interface constraint:
class Sample { public static void Main() { int[] list = { 0, 1, 2, 3 }; MakeAtLeast<int>(list, 2); // change array to { 2, 2, 2, 3 } } public static void MakeAtLeast<T>(IList<T> list, T lowest) where T : IComparable<T> { for (int i = 0; i < list.Count; i++) if (list[i].CompareTo(lowest) < 0) list[i] = lowest; } } Since all arrays implement the IList<T> interface (commonly associated with list classes), the MakeAtLeast() method allows operation on arrays, with elements of 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 with a list of another type. The interface provides the generic method CompareTo(T). Look up list in Wiktionary, the free dictionary. ...
In computer science, compile time, as opposed to runtime, is the time when a compiler compiles code written in a programming language into an executable form. ...
The above method could also be written without generic types, simply using the non-generic IList type. However, this would make the method less type safe, as it would allow the method to be applied to a list of incomparable items, resulting in a run time error. The method would need to access the list 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.) In computer science, a programming language is type safe when the language does not permit the programmer to treat a value as a type to which it does not belong. ...
In computer science, runtime or run time describes the operation of a computer program, the duration of its execution, from beginning to termination (compare compile time). ...
In computer science, type conversion or typecasting refers to changing an entity of one data type into another. ...
Generic programming in Functional languages
Generic programming in Haskell 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: In computer science, a binary tree is a tree data structure in which each node has at most two children. ...
data BinTree a = Leaf a | Node (BinTree a) a (BinTree a) 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 parametrically 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: Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
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 () -> &# 0;> [] Par -> &# 0;> [x] Rec -> &# 0;> x d@g -> concat . flatten . pmap fl Con t -> &# 0;> [] cata :: Regular d => (FunctorOf d a b -> b) -> d a -> b
Generic Haskell Generic Haskell is another extension to Haskell, developed at Utrecht University in The Netherlands. The extensions it provides are: Haskell is a standardized purely functional programming language with non-strict semantics, named after the logician Haskell Curry. ...
Utrecht University (Universiteit Utrecht in Dutch) is a university in Utrecht, The Netherlands. ...
Motto: Je Maintiendrai (Dutch: Ik zal handhaven, English: I Shall Uphold) Anthem: Wilhelmus van Nassouwe Capital Amsterdam1 Largest city Amsterdam Official language(s) Dutch2 Government Parliamentary democracy Constitutional monarchy - Queen Beatrix - Prime minister Jan Peter Balkenende Independence Eighty Years War - Declared July 26, 1581 - Recognised January 30, 1648 (by Spain...
- 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 specialised 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 which 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 specialised to any type.
As an example, the equality function in Generic Haskell:[4] 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 |} = (==)
The "Scrap your boilerplate" approach The Scrap your boilerplate approach is a lightweight generic programming approach for Haskell (Lämmel and Peyton Jones, 2003). A web site for this approach explains which components of it are currently implemented in GHC. Boilerplate refers to any text that is or can be reused in new contexts or applications without being changed much from the original. ...
The Glasgow Haskell Compiler (or GHC) is an open source Native code Compiler for the functional programming language Haskell which was developed at the University of Glasgow. ...
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. In computer science, Clean is a general-purpose purely functional computer programming language. ...
Generic programming features in other languages Standard ML and OCaml provide functors, which are similar to class templates and to Ada's generic packages. Scheme syntactic abstractions also have connection to generic programming -- these are in fact a superset of templating a la C++. Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. ...
Objective Caml (OCaml) is a general-purpose programming language descended from the ML family, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ...
Scheme is a multi-paradigm programming language. ...
See also In computing, partial evaluation is a technique for program optimization by specialization. ...
In generic programming, a concept is a description of supported operations on a type, including syntax and semantics. ...
External links and references
General [[Im[[Image:Example. ...
C++/D - Walter Bright, Templates Revisited.
- David Vandevoorde, C++ Templates: The Complete Guide, 2003 Addison-Wesley. ISBN 0-201-73484-2
C#/.NET - Jason Clark, "Introducing Generics in the Microsoft CLR," September 2003, MSDN Magazine, Microsoft.
- Jason Clark, "More on Generics in the Microsoft CLR," October 2003, MSDN Magazine, Microsoft.
- M. Aamir Maniar, Generics.Net. An open source generics library for C#.
Haskell/functional - Dæv Clarke, Johan Jeuring and Andres Löh, The Generic Haskell user's guide
- Ralf Hinze, "Generics for the Masses," In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP), 2004.
- Simon Peyton Jones, editor, The Haskell 98 Language Report, Revised 2002.
- Ralf Lämmel and Simon Peyton Jones, "Scrap Your Boilerplate: A Practical Design Pattern for Generic Programming," In Proceedings of the ACM SIGPLAN International Workshop on Types in Language Design and Implementation (TLDI'03), 2003. (Also see the website devoted to this research)
- Andres Löh, Exploring Generic Haskell, Ph.D. thesis, 2004 Utrecht University. ISBN 90-393-3765-9
- Generic Haskell: a language for generic programming
The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...
SIGPLAN is the Association for Computing Machinerys Special Interest Group on programming languages. ...
The International Conference on Functional Programming (ICFP) is an annual academic conference in the field of computer science sponsored by the ACM SIGPLAN, in association with IFIP Working Group 2. ...
Simon Peyton Jones is a British computer scientist who does research on the implementation and applications of functional programming languages, particularly lazy functional languages. ...
Simon Peyton Jones is a British computer scientist who does research on the implementation and applications of functional programming languages, particularly lazy functional languages. ...
The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ...
SIGPLAN is the Association for Computing Machinerys Special Interest Group on programming languages. ...
Utrecht University (Universiteit Utrecht in Dutch) is a university in Utrecht, The Netherlands. ...
Java - Gilad Bracha, Generics in the Java Programming Language, 2004.
- Maurice Naftalin and Philip Wadler, Java Generics and Collections, 2006, O'Reilly Media, Inc. ISBN 0-596-52775-6
- Peter Sestoft, Java Precisely, Second Edition, 2005 MIT Press. ISBN 0-262-69325-9
- Generic Programming In Java, 2004 Sun Microsystems, Inc.
- Java Generics FAQs
Other languages
Notes - ^ C#: Yesterday, Today, and Tomorrow: An Interview with Anders Hejlsberg
- ^ Generics in C#, Java, and C++
- ^ Constraints on Type Parameters (C# Programming Guide)
- ^ The Generic Haskell User's Guide
|
Feeds |
Contact