Generic Programming

The functional programming paradigm was introduced in the last section. As it can be seen, the generic programming was already used with the template mechanism of C++. But generic programming is more than just using template for various types. If we consider the imperative (structured), object-oriented, and functional programmig, it is getting clear, that one mechanism has to be introduced to use all these mechanism efficiently together: the generic programming paradigm.

From Monomorphic to Polymorphic Programming


Conventional typed languages, such as C or Pascal, are based on the idea that functions and procedures, and hence their operands, have a unique type. Such languages are said to be monomorphic, in the sense that every value and variable can be interpreted to be of one and only one type. In contrast, polymorphic languages can have more than one type for some values and variables.

There are several types of polymorphic programming as can be seen in the picture to the right:

Sub-typing: this type summarizes the mechanisms of inheritance. Also called inclusion.
Parametric: generics or template based programming.
Overloading: used to adapt methods to different call mechanisms.
Coercion: the technical term for an automatic type conversion by the compiler.

The most important type is the universal polymorphism which can be modelled by inheritance (object-orientation) and template programming (generic programming). These types differ in the following features:

Virtual function calls are slower during run-time than function templates
Run-time dispatch versus compile-time dispatch
Code size: virtual functions are small, templates are (can be) big
The binary method problem in the inheritance mechanism

Virtual function calls are currently used in all object-oriented programming languages such as Java and C++. The disadvantage of the virtual function mechanism is the lack of optimization from the compiler. The compiler cannot inline code elements. Due to the runtime dispatch one level of indirection causes another performance degretation. The template mechanism of C++ leads to bigger code size due to the instantiation of code elements for several data types. Finally, the binary method problem restricts the usability of the currently used mechanism within object-oriented programming languages.


An important question remains. How can the unique property of the absence of side-effects be used with the advantages of the object-oriented and imperative programming paradigm? From our point of view does the generic programming paradigm connect these different paradigms. We want to show this with the following example (the stable_partition algorithm can be found at: www.sgi.com/tech/stl/stable_partition.html):

int main()
{
  short B[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  const short N2 = sizeof(B)/sizeof(short);

  std::stable_partition(B, B + N2, arg1 % 2 == 0 );
  std::for_each(B,B+N2, std::cout << arg1 << "  ");

  return 0;
}

Here we use a generic partition algorithm which separates the sequence of data according due to the given expression. The result is given by:

2 4 6 8 10 1 3 5 7 9

We want to explain the differen paradigms used in this two lines.

 

From an abstract point of view the various paradigms can be summarized with the following relation

\mathrm{state} \iff \mathrm{function}

where the left side provides the input or data structure and therefore has to use states. The imperative and object-oriented paradigms are suited best for this task. The right side should be specified functionally (stateless) whereas the functional programming accomplishes this task greatly.

The generic paradigm provides the correctnes between these two sides based on the concepts and therewith the right data type (polymorphism). No implicit conversions should be necessary.