Generische Programmierung

Generische Programmierung ist ein Programmierstil, in dem die Algorithmen so weit wie möglich von den Datenstrukturen, auf denen sie arbeiten, getrennt werden. Paradebeispiel ist die STL, die in die Standardbibliothek von C++ integriert wurde.

Wesentlich bei der generischen Programmierung ist, daß die Algorithmen nicht für einen bestimmten Typ geschrieben werden, sondern nur bestimmte Anforderungen an die Typen stellen. Ein gutes Beispiel liefert die Maximumsfunktion

\mathrm {max} :T\times T\rightarrow T

,

die für zwei gegebene Werte a, b desselben Typs den größeren Wert max(a,b) zurückgibt.

Voraussetzung ist, dass a und b miteinander vergleichbar sind, der Ausdruck $a<b$ also definiert ist und eine Ordnung beschreibt.

In klassischen Programmiersprachen würde man hier für jeden Datentyp eine Funktion programmieren, die für jeden Typ getrennt dasselbe tun, z.B. in C:

int maxint(int a, int b)
{
  if (a<b) return b;
  else return a;
}

int maxfloat(float a, float b)
{
  if (a<b) return b;
  else return a;
}

Hierbei fällt auf, daß der Code an sich immer derselbe ist, nur die Typen unterscheiden sich. Diese Wiederholung läßt sich zwar mit Makros umgehen (so wird in C üblicherweise die Maximumsfunktion über ein Makro

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

definiert, wobei ?: ein if/else für Ausdrücke ist), aber damit handelt man sich andere Nachteile ein (z.B. werden bei obigem Makro beide Ausdrücke zweimal ausgewertet).

Auch der objektorientierte Ansatz funktioniert hier nicht zufriedenstellend: Definiert man (z.B. in C++) eine Klasse Vergleichbares und leitet davon z.B. für eine physikalische Simulation die Klassen Laenge und Masse ab (sagt also, daß sowohl Laengen als auch Massen etwas vergleichbares sind), so kann man zwar schreiben:

Vergleichbares& max(Vergleichbares& a, Vergleichbares& b)
{
  if (a<b) return b;
  else return a;
}

aber es gibt immer noch 2 Probleme:

Zunächst, dass der Ergebnistyp nur "Vergleichbares" ist; man muß dem Compiler also beim Aufruf explizit sagen, daß das Maximum zweier Längen wieder eine Länge ist (sofern man dessen Längeneigenschaften benutzen will, was wahrscheinlich ist), vor allem aber,
daß diese Funktion es erlaubt, das Maximum einer Länge und einer Masse zu "bestimmen", obwohl diese Operation völliger Unsinn ist.

Generische Programmierung, z.B. in C++ über Templates realisiert, verbindet nun die Flexibilität des Makros mit der Typsicherheit und den anderen Eigenschaften der Funktion. Die generische Implementierung von max in C++ ist

template<class T>
 T max(T a, T b)
{
  if (a<b) return b;
  else return a;
}

Die so definierte Funktion max<> kann nun für alle Typen mit Vergleichsoperator verwendet werden.

Ein weiterer Vorteil ist, daß man nicht explizit bei der Definition sagen muß, daß ein Typ vergleichbar ist (z.B. durch Ableiten von einer entsprechenden Klasse), sondern man muß nur sicherstellen, daß er die nötigen Eigenschaften hat (in diesem Fall einen operator< mit korrekter Semantik). Auf diese Weise können auch Typen mit der Funktion verwendet werden, die in Unkenntnis der Funktion entworfen wurden (z.B. die eingebauten Typen der Programmiersprache).

Ein Algorithmus sollte dabei stets möglichst wenig vom Typ fordern. So arbeiten die Algorithmen der STL nicht direkt auf den Containern, sondern mit Iteratoren. Auf diese Weise werden sie weitgehend unabhängig von den genauen Eigenschaften des speziellen Containers und können teilweise sogar direkt auf Ein- und Ausgabeströmen arbeiten.