"To think is to forget differences, it is to generalize, to abstract" (Borges).
"We think in generalities, but we live in details" (A.N. Whitehead).
"One should always generalize" (Carl Jacobi).
"The generic can be more intense than the concrete" (Borges).
Generic Programming
Generic programming is a technique of developing software components as general as possible, with several objectives:
So that components can be reused in other applications.
So that they depend as little as possible on the execution environment, implementer details are ignored and interoperability is achieved.
To make developments more conceptual and intelligible.
For example, an algorithm could rely on general concepts, such as: traversing a data structure, accessing one of its elements, selecting the elements that meet certain conditions, etc.
While these goals are desirable and beneficial, there are some drawbacks:
Developments may be less efficient. Generality and efficiency are, in general, opposing forces.
If the programming language is not high-level, generic developments can be more extensive than specific ones. This is due to the additional code needed to parse the type of each argument, the different treatment associated with each type, the possible inclusion of additional parameters, etc.
The implementation of generic programming depends primarily on the language used and the level of abstraction it supports.
The generic aspects
The concept "generic" in generic programming has different aspects:
In parameterized components, it refers to the fact that the parameters are not limited to a certain type of data. This is what is called "parametric polymorphism".
It is common to have to write different versions of the same component for different types of data. For example, one function for sorting numbers, another for sorting strings, and so on. Ideally, there would be one generic sorting function, which would be suitable for all types of elements. Another example would be a search algorithm that works with lists, files, arrays, etc., as well as portions of these structures.
In parameterized components, that the number of parameters be variable.
In components that produce a result, that the result is not limited to certain types of data, but can be any type of expression: a data, a structure, a class, an object, a function, a set, etc.
That higher-order software components can be defined, for example: functions returning functions, objects composed of objects, classes of classes, etc.
That combinations of different types of elements can be realized, for example: functions returning objects, classes of functions, structures consisting of procedures, sets of objects, etc.
Implementation in MENTAL
Generic programming is at its best in this language, since it covers all the aspects mentioned above:
MENTAL is a generic language because the language primitives are universal and, therefore, generic. Because universal concepts are used, developments tend to be generic.
Many derived operations, such as length, depth, element selection, etc. are generic, that is, they are independent of the type of the arguments. And if the arguments are not of the required type and the operation cannot be performed, then the result is the operation itself. For example:
a+b // self-evaluates
(a...a+5) // rep. a a+1 a+2 a+3 a+4 a+5
a/(b=3) // self-evaluates itself
The combinatorics of primitives is generic, that is, the primitives are orthogonal and can be freely combined.
Generic expressions (parameterized or not) can be specified.
Reusability is general: it applies to all types of expressions.
Examples
Copy the n first elements of the sequence x into the sequence y. Supone n>0.
⟨( Copy(x and n) = [y\i = x\i)/(i=[1...n])] )⟩
This function is valid for any sequence, regardless of the type of its components.
Application example:
x=(a (b c) 17.4 {d e} u v)
y=(1 2 3 4 5 6)
Copy(x y 4) // copy the first 4 elements of x into y
y // ev. (a (b c) 17.4 {d e} 5 6)
Replace the n first elements of the sequence x by the element y. Supone n>0
⟨( Substitute(x n y) = [x\i = y)/(i=[1...n])] )⟩
Application examples:
x=(a (b c) 17.4 {d e} u v)
Substitute(x 4 y)
x // ev.(y y y y y y u v)
x=(a (b c) 17.4 {d e} u v)
Substitute(x 2 (s1 s2))
x // ev. ((s1 s2) (s1 s2) (s1 s2) 17.4 {d e} u v)
Sum all components of a sequence.
In this case, there is a single parameter (the sequence), whose number of elements is variable. It is equivalent, in short, to a variable number of parameters.
⟨( Sum(x) = +⊣x )⟩
Application examples:
Add(1 2 3 4) // ev. 10
Add(1234) // ev. 10
Add(a b c d) // ev. a+b+c+d
Sum(abcd) // ev. a+b+c+d
Add(a 1 b 2 c 3) // ev. a+b+c+6
Addenda
History of generic programming
The Lisp language can be implicitly considered as the first generic programming language, thanks to its high level of abstraction, its unified system of code and data storage (the lists), its dynamic types, its parameterization capabilities, and the possibility of working with higher-order functions.
The C++ language is the first language to explicitly support two generic mechanisms:
Templates.
A template is a kind of code cast, from which the compiler can generate specific instances. Templates are used to create general-purpose code libraries.
Polymorphic operators.
A polymorphic (also called "overloaded") operator is one that can operate on different types of data.
C++ is a language that has no versioning. The ANSI/ISO (1988) standard defines the core of the language. C++ is multi-paradigm (object-oriented, functional and procedural).
The efficiency of an algorithm can be relative if it is as efficient as the non-generic version (written in the same language) and absolute if it is as efficient as a non-generic version written in assembly language. With C++, relative efficiency has been achieved and approaching absolute efficiency, so that efficiency and generality are not mutually exclusive.
It is considered that true generic programming was born with the work of Alexander Stepanov with the Ada language and later transferred to C++ to create the STL (Standard Template Library, Standard Template Library), a library of generic software components implemented as templates, which was adopted as the ANSI/ISO standard of the language. This library was followed by others, also of generic type, such as the Boost Graph Library and the Matrix Template Library. C++ then became a multi-paradigm language enriched with generic programming.
Generic programming is a paradigm that has been gaining increasing importance, such that, in recent years, many languages (such as Standard ML, Haskell, Eiffel and Java) have incorporated generic mechanisms (at least in a basic form), inspired mainly by the STL model. Recent specific generic programming languages are Generic Haskell (2000) and Generic C# (2003).
STL
The C++ template library was designed to achieve maximum reusability without sacrificing efficiency. Its importance lies in its concepts (or abstract categories), rather than in the implementing details. STL sources have the C syntax. It is even possible to program in STL without knowing C++. Among these concepts the most prominent are the following:
Containers.
These are objects that can contain objects of any type (integers, pointers, characters, etc.), including user-defined types.
There are different types of containers, depending on the organization of their elements and ways of access: vector, array, list, queue, double queue (deque), stack, map, set, and bitset (set of boolean values).
Iterators.
They are a kind of generalized pointers that act as a link between algorithms and containers.
There are 5 types of iterators: 3 for traversing a container (forward, bidirectional and direct access) and 2 for reading or updating a container element (input and output iterator).
Each type of container uses the most appropriate iterators to ensure an efficient implementation.
Adapters.
They are modifiers of other components. There are several kinds, for example: the "stack" adapter, which converts a container into a simple stack; the "reverse iterator" adapter, which reverses the movement of an iterator, etc.
function objects.
These are objects that can be called as if they were functions. A function object that returns a boolean value is called a "predicate object".
Bibliography
Alexandrescu, Andrei. Modern C++ Design. Generic Programming and Design Patterns Applied. Addison-Wesley Professional, 2001.
Austern, Matthew H. Generic Programming and the STL: Using and Extending the C++ Standard Template Library. Addison-Wesley, 1998.
Backhouse, Roland; Gibbons, Jeremy (editors). Generic Programming. Advanced Lectures Lecture Notes in Computer Science, Springer, 2003.
García, R.; Järvi, J.; Lumsdaine, A.; Siek, J.G. ; Willcock, J. A comparative study of language support for generic programming. In OOSPLA, Oct. 2003.
Musser, David R.; Derge, Gillmer J.; Saini, Atud. STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library. Addison-Wesley, 2001.
Stepanov, Alexander. The Standard Template Library – how do you build an algorithm that is both generic and efficient? Byte Magazine, 20 (10), Oct. 1995.
Web STL de Silicon Graphics Computer Systems, Inc.: http://www.sgi.com/tech/stl/
