Programmieren: Paradigmen: Generische Programmierung

Aus Wikibooks

Generische Programmierung ist ein Programmier-Paradigma, das darauf abzielt, Algorithmen möglichst unabhängig von den verwendeten Datentypen zu formulieren. Das prominenteste Beispiel einer generischen Bibliothek ist die Standard Template Library, die Eingang in die C++-Standardbibliothek gefunden hat.

In statisch typisierten Programmiersprachen (etwa C++) ist die Voraussetzung, generische Programmierung überhaupt durchführen zu können, ein Mechanismus für parametrisierte Funktionen und Typen, wie etwa die Templates in C++. Während ein solcher Mechanismus die generische Programmierung bereits ermöglicht, erfordern viele Techniken der generischen Programmierung in diesem Rahmen relativ komplizierte Template-Definitionen, was der generischen Programmierung teilweise den Ruf eingebracht hat, kompliziert zu sein. Ein Großteil der Komplexität beruht jedoch einfach darauf, dass der Template-Mechanismus die generische Programmierung zwar ermöglicht, aber nicht wirklich gut unterstützt (dies ist vergleichbar mit objektorientierter Programmierung in C). Eine gute Unterstützung benötigt weitere Sprachelemente, wie sie zum Beispiel für die nächste Version von C++ in der Form von concepts vorgesehen sind.

Die wesentliche Vorgehensweise bei der generischen Programmierung ist das so genannte Lifting: Ausgehend von einem konkreten Algorithmus wird untersucht, welche Eigenschaften der verwendeten Typen und Operationen eigentlich verwendet werden, und der Algorithmus entsprechend verallgemeinert. Dies erlaubt es, denselben Algorithmus in einem völlig anderen Kontext wiederzuverwenden, wobei ein guter Compiler in der Regel genauso effizienten Code erzeugen kann wie bei einer explizit für diesen Fall handgeschriebenen Funktion.

Das folgende Beispiel illustriert diesen Prozess. Hierzu wird ein (hoffentlich) selbsterklärender Pseudocode verwendet.

Gegeben sei die folgende Funktion, die aus einem Array ganzer Zahlen die größte Zahl zurückgibt:

Funktion MaximalesElement: a: Array von Ganzzahl -> Ergebnis: Ganzzahl
  Kandidat: Ganzzahl
  Kandidat := a[1] // Erstes Element des Arrays
  für Index: Ganzzahl von 2 bis Länge(a)
    wenn Kandidat < a[Index]
      Kandidat := a[Index]
  Ergebnis := Kandidat

Die erste offensichtliche Erweiterung ist, dass diese Funktion offensichtlich nicht nur für ganze Zahlen sinnvoll ist. Beispielsweise könnte man auch aus einem Array von Fließpunktzahlen das größte Element auswählen. Eine genauere Betrachtung des Algorithmus zeigt, dass eigentlich nur zwei Eigenschaften des Ganzzahl-Typs verwendet werden: Man kann ihn zuweisen, und man kann in mit dem Kleiner-als-Operator (also "<") vergleichen. Der Rückgabetyp ist natürlich jeweils derselbe wie die Elementtypen. Man kann also die Funktion folgendermaßen verallgemeinern:

 Funktion MaximalesElement[Typ T: zuweisbar, kleiner_als_vergleichbar]:
          a: Array von T -> Ergebnis: T
   Kandidat: T
   Kandidat := a[1]
   für Index: Ganzzahl von 2 bis Länge(a)
     wenn Kandidat < a[Index]
       Kandidat := a[Index]
   Ergebnis := Kandidat

Hierbei wird angenommen, dass die Konzepte zuweisbar und mit_kleiner_als_vergleichbar bereits vom Compiler bzw. der Standardbibliothek zur Verfügung gestellt werden.

Eine weitere Verallgemeinerung ist, dass die zu vergleichenden Objekte nicht unbedingt in einem Array stehen müssen. Man könnte auch das maximale Element in einer verketteten Liste suchen, oder sogar die größte Zahl, die man aus einer Datei einliest. Hierzu muss die Art, wie man auf die Zahl zugreift, abstrahiert werden. In der Regel wird dies über so genannte Iteratoren gemacht. Für Iteratoren ließe sich beispielsweise folgendes Konzept definieren:

Konzept: I ist Iterator
  benötigt: I ist istgleich_vergleichbar
  Typ Wert;
  Funktion Element: I -> Wert
  Funktion Nächster: I -> I

Mit dieser Definition kann MaximalesElement zum Beispiel folgendermaßen aussehen:

Funktion MaximalesElement[Typ I: Iterator,
                          I.Wert: zuweisbar, kleiner_als_vergleichbar]:
         Anfang, Ende: I -> Ergebnis: I.Wert
  Kandidat: I.Wert;
  Iter: I;
  Kandidat := Element(Anfang)
  Iter := Nächster(Anfang)
  solange Iter != Ende
    wenn Kandidat < Element(Iter)
      Kandidat := Element(Iter)
    Iter = Nächster(Iter)
  Ergebnis := Kandidat

Eine weitere offensichtliche Verallgemeinerung ist, statt des Kleiner-Operators eine beliebige Vergleichsfunktion zuzulassen. Außerdem ist es bei dieser Allgemeinheit sinnvoll, statt des Wertes dessen Position zurückzugeben (dies kann über den entsprechenden Iterator passieren).

Danach ist vermutlich der maximale Abstraktionsgrad erreicht; die Funktion beschreibt nur noch den Algorithmus selber, nicht mehr die in unterschiedlichen Anwendungen verschiedenen Details (welcher Datentyp verwendet wird, wo sich die Objekte befinden bzw. wie man die entsprechenden Werte erhält, wie man sie vergleicht)

Dieselbe Funktion kann nun unverändert für so verschiedene Dinge verwendet werden wie:

• In einem Array die größte Zahl herauszufinden
• In einer Liste komplexer Zahlen diejenige mit dem kleinsten Betrag zu finden
• In einer Textdatei die längste Zeile zu ermitteln
• In einer Schülerdatenbank den besten Schüler zu ermitteln