Generizität

Generische Programmierung - Definition und Motivation

Ziel von generischer Programmierung ist es, Algorithmen und Datenstrukturen so zu entwerfen und zu implementieren, dass sie möglichst vielfältig verwendbar sind.

Vielfältig verwendbar meint hierbei, dass generische Algorithmen und Datenstrukturen ohne Neumiplementation in

• den verschiedensten Anwendungen eingesetzt,
• vielseitig miteinander kombiniert und
• als wiederverwendbare Bibliotheken zur Verfügung gestellt werden können.

Dadurch gelingt es, auch sehr komplizierte Algorithmen und Datenstrukturen praktisch nutzbar zu machen. Ohne Generizität müssten diese jedesmal neu implementiert und getestet werden, wofür der Aufwand oft zu hoch wäre. Außerdem muss derselbe Algorithmus dann oft in vielen Varianten implementiert werden, ohne dass sich die Varianten auf interessante Weise unterscheiden.

Beispiel eines nicht-generischen Algorithmus

Wir demonstrieren am folgenden Beispiel, wie es ohne Generizität nötig wird, denselben Algorithmus 'kopiere Container' für jede Kombination von Quell- und Zielcontainer neu zu implementieren. Dies ist besonders störend, weil die Unterschiede der Varianten trivial sind. Wir zeigen weiter unten, dass mit Generizität eine einzige Implementation ausreichend ist.

Kopie Array → Array

Die folgende einfache Funktion kopiert die Daten aus einem gegebenen Array a in ein (dynamisches) Array r:

def copyArray(a):
  r =[]
  for k in a:
     r.append(k)
  return r

Kopie Array → verkettete Liste

Um in eine verkettete Liste kopieren zu können, definieren wir zunächst den Knotentyp der Liste:

class Node :
 def __init__(self, data, next)
    self.data = data
    self.next = next

Die Kopie aus einem Array in eine Liste kann dann wie folgt implementiert werden:

def copyArrayToList(a) :
   if len(a) == 0 : 
        return None
   first = last = Node (a[0], None)
   for k in a[1:]  :
      last.next = Node(k, None)
      last = last.next
   return first

Kopie verkettete Liste → Array

Eine wieder andere Implementation benötigt man, wenn man umgekehrt von einer Liste in ein Array kopieren möchte:

def copyListToArray(l):
    r = []
    while l is not None :
        r.append(l.data)
        l = l.next
    return r

Entscheidende Beobachtung

Für N Datenstrukuren ist der Implementationsaufwand <math>O(N^2)</math>, wenn man alle Paare von Datenstrukturen ineinander umwandeln können will. Alle Funktionen machen das Gleiche, mit nur uninteressanten Unterschieden. Wir wollen daher im Folgenden eine Möglichkeit angeben, das Kopieren der Daten zu vereinheitlichen, so dass nur noch eine generische Kopierfunktion benötigt wird.

Transformation in eine generische Form

Die Kopierfunktion enthält zwei wesentliche Funktionalitäten:

• das Navigieren durch die Quelldaten und
• das Aufbauen der Zieldatenstruktur

Wenn wir die Implementation generisch gestalten wollen, müssen wir diese beiden Aspekte des Kopierens verallgemeinern.

Vereinheitlichung der Zieldatenstruktur durch standardisierte Einfügefunktion

Wir beginnen mit dem Aufbauen der Zieldatenstruktur. Hier brauchen wir eine verallgemeinerte Methode, neue Elemente an eine bereits existierende Datenstruktur anzuhängen. Dazu bietet es sich an, eine

• standardisierte Funktion append zu verwenden.

Das dynamische Array hat diese Funktion bereits. Für eine einfach verkettete Liste kann sie nicht ohne weiteres effizient implementiert werden (einfach verkettete Listen unterstützen in erster Linie das Einfügen eines neuen Elements am Anfang der Liste, also prepend). Wir implementieren deshalb eine neue Datenstruktur DoublyLinkedList, die eine in beiden Richtungen verkettete Liste realisiert.

Um Anfang und Ende der Liste zu markieren, verwenden wir eine spezielle Sentinel-Datenstruktur. Da sie nur als Markierung dient, benötigt sie keine eigenen Daten.

class SentinelTag : pass     # keine Daten

Der Knotentyp einer DoublyLinkedList enthält zwei Verkettungen: prev und next. Falls im Konstruktor kein Nachfolger next angegeben wird, werden die Verkettungen auf self initialisiert (dies bedeutet, dass der Knoten eine leere Liste repräsentiert), andernfalls werden alle Verkettungen so aktualisiert, dass der neue Knoten Vorgänger von next wird. Ein Sentinel-Knoten wird dadurch gekennzeichnet, dass sein Datenfeld den Typ SentinelTag hat. Dies ist auch die Initialisierung, falls im Konstruktor keine Daten übergeben werden:

class DoublyLinkedNode:

    def __init__(self, data = SentinelTag(), next = None)
        self.data = data
        if next is None :
            self.prev = self.next = self
        else:
            self.next = next
            self.prev = next.prev
            next.prev.next = self
            next.prev = self

   def isSentinel(self ) : 
        return isinstance( self.data, SentinelTag) # Python-Standardfunktion zum Prüfen des Typs einer Variable

Die Klasse DoublyLinkedList kapselt nun die Verwaltung der Knoten. Die Liste selbst wird dabei als doppelt verbundene, kreisförmige Kette mit dem Sentinel als "Anker" realisiert. Dies hat den Vorteil, dass man das erste bzw. letzte Element der Liste einfach als Nachfolger bzw. Vorgänger des Ankerelements abfragen kann. Ein weiterer Vorteil besteht darin, dass auch die leere Liste noch ein Element enthält (nämlich den Sentinel), so dass beim Einfügen und Löschen von Elementen keine Spezialbehandlung für die leere Liste notwendig ist.

class DoublyLinkedList : 

    def __init__(self):        # Konstruktor initialisert leere Liste, die nur aus dem Sentinel besteht
        self.sentinel = DoublyLinkedNode()
        self.size = 0

    def __len__(self):         # wird ausgeführt, wenn man 'len(list)' aufruft
        return self.size 

    def append(self, value):   # value am Ende anhängen, d.h. Sentinel soll Nachfolger des neuen Elements sein
        DoublyLinkedNode(value, self.sentinel)  # die Verkettungen werden im Konstruktor automatisch aktualisiert
        self.size += 1

    def prepend(self, value):  # value am Anfang (= nach dem Sentinel, d.h. vor dessen Nachfolger) einfügen
        DoublyLinkedNode(value, self.sentinel.next)  
        self.size += 1

    def __iter__(self):        # Iterator für die Liste erzeugen (siehe unten)
        return ListIterator(self.sentinel.next)

    def reverseIterator(self): # Rückwärts-Iterator für die Liste erzeugen (siehe unten)
        return ReverseListIterator(self.sentinel.prev)

Damit können wir die Zieldatenstruktur einheitlich durch ziel.append(value) aufbauen, unabhängig davon, ob ziel nun ein Array oder eine doppelt verkettete Liste ist.

Vereinheitlichung der Quelldatenstruktur durch Iteratoren

Die Vereinheitlichung der Quelldatenstruktur ist komplizierter, weil die Navigationmethoden sich von Datenstruktur zu Datenstruktur sehr stark unterscheiden. Ein einheitlicher, standardisierter Funktionenname tut es hier nicht. Der Schlüssel für die Lösung besteht in der Beobachtung, dass wir, unabhängig von der Art der Datenstruktur, immer sequentiell auf die Datenelemente zugreifen. Man definiert deshalb eine Hilfsklasse Iterator, die die Elemente in der richtigen Reihenfolge heraussucht, die aber verbirgt (kapselt), wie jedes Datenelement konkret gefunden wird.

Definition Iterator

Ein Iterator ist ein Objekt,

• das auf ein Element des Containers zeigt und die Daten aus diesem Element an den aufrufenden Algorithmus übergeben kann
• das zum nächsten Element weiter rücken kann
• das anzeigt, wenn das Ende der Sequenz erreicht ist

(siehe dazu auch die Wikipedia).

Die Syntax dieser Funktionalitäten muss natürlich standardisiert sein, damit man das Ziel der Generizität erreicht. Wie genau die Standardisierung erfolgt, ist von Programmiersprache zu Programmiersprache unterschiedlich (falls die Sprache überhaupt Iteratoren unterstützt -- das gilt z.B. für C++ und Java). In Python gelten folgende Konventionen:

• Das Weiterrücken zum nächsten Element erfolgt durch die Funktion next(). Diese Funktion gibt gleichzeitig die Daten desjenigen Elements zurück, das man gerade verlassen hat.
• Alle Datenstrukturen, die Iteratoren anbieten, sowie die Iteratoren selbst, müssen eine Funktion __iter__() haben, die einen neuen Iterator (bzw. eine Kopie des schon vorhandenen Iterators) zurückgibt. Diese Funktion wird von Python intern benutzt (siehe unten).
• Das Ende der Sequenz ist erreicht, wenn die Funktion next mit einer StopIteration-Exception verlassen wird.

Die Array-Datenstruktur in Python bietet einen solchen Iterator bereits an.

Iterator für die doppelt verkettete Liste

Aufgrund dieser Konventionen können wir den Iterator für die Klasse DoublyLinkedList wie folgt implementieren:

class ListIterator:
      def __init__(self, node):          # Iterator zeigt anfangs auf den angegebenen Knoten
          self.node = node

      def next(self):
          if self.node.isSentinel():
              raise StopIteration()      # Pythonkonvention: Ende der Sequenz erreicht
          v = self.node.data             # speichere die Daten des aktuellen Knotens ...
          self.node = self.node.next     # ... und rücke zum nächsten Knoten weiter ...
          return v                       # ... und gebe vorigen Wert zurück (Pythonkonvention)

      def __iter__(self):
          return ListIterator(self.node) # Pythonkonvention, Kopie des Iterators zurückgeben

Die Funktion DoublyLiinkedList.__iter__() erzeugt einen solchen Iterator und setzt ihn auf das erste Element der Liste.

Generische Kopierfunktion

Mit den so definierten Schnittstellen genügt nun eine einzige Methode zum Kopieren eines Containers:

def genericCopy (quelle, ziel) :
    for k in quelle :
        ziel.append(k)
    return ziel

Diese Funktion kann an Stelle der spezialisierten Kopierfunktionen verwendet werden. Das zweite Argument von genericCopy zeigt an, in welche Zieldatenstruktur kopiert werden soll:

liste  = genericCopy(array, DoublyLinkedList())      # statt copyArrayToList
array2 = genericCopy(array, [])                      # statt copyArray 
array3 = genericCopy(liste, [])                      # statt copyListToArray

Was tut Python bei "for k in quelle:" ?

Will man in Python alle Elemente eines Containers durchlaufen, so tut man dies leicht mit einem Statement der Form for k in quelle:. Was passiert dabei eigentlich? (Die folgende Darstellung ist etwas vereinfacht und zeigt die Python-Funktionalität nur für den Fall, dass die Quelldatenstruktur einen Iterator anbietet. In Wirklichkeit unterstützt for k in quelle: noch weitere Arten von Datenstrukturen.)

Das Schlüsselwort for ruft die Methode __iter__() des Objekts quelle auf, die eine Referenz auf ein Iterator-Objekt zurückgibt. Dieses Objekt definiert eine Methode next(). Der von next() zurückgegebene Wert wird an die Laufvariable k zugewiesen, mit der dann der eigentliche Schleifeninhalt ausgefürt wird. Wenn keine weiteren Elemente mehr vorhanden sind, wird die Schleife durch die Exception StopIteration beendet.

iter = quelle.__iter__()
try :
       while True :
             k = iter.next() # löst am Ende die Exception 'StopIteration' aus
             ...             # Schleifeninhalt
except StopIteration: pass   # alle anderen Expcetions werden normal weitergereicht

Kopieren einer Sequenz in umgekehrter Reihenfolge

Die Funktion genericCopy ist jetzt mächtig genug, um auch Kopiervorgänge zu unterstützen, an die wir anfangs gar nicht gedacht haben. Ein Beispiel dafür ist das Kopieren der Sequenz in umgekehrter Reihenfolge. Man könnte dies erreichen, indem man die Aufrufe von append durch Aufrufe von prepend unterstützt, aber dann hätte man eine neue Funktion reverseCopy. Viel eleganter ist es, das Auslesen der Quellsequenz zu manipulieren, indem man einen Iterator programmiert, der die Sequenz rückwärts durchläuft.

Für die doppelt verkettete Liste unterscheidet sich ein solcher Rückwärtsiterator fast gar nicht vom normalen Vorwärtsiterator:

class ReverseListIterator:
      def __init__(self, node):         
          self.node = node

      def next(self):
          if self.node.isSentinel():
              raise StopIteration()      
          v = self.node.data             
          self.node = self.node.prev     # gehe zum Vorgängerknoten - einziger wesentlicher Unterschied zum ListIterator
          return v                       

      def __iter__(self):
          return ReverseListIterator(self.node) # die Kopie des Iterators muss natürlich auch vom richtigen Typ sein

Der Rückwärtsiterator wird genau wie der Vorwärtsiterator verwendet. Man beachte aber, dass list.reverseIterator() den Iterator auf das letzte Element der Liste initialisieren muss (siehe oben in der Implementation von DoublyLinkedList):

reverseArray = genericCopy(list.reverseIterator(), []),          # Liste rückwärts in ein Array kopieren

Die Syntax for k in quelle: funktioniert weiterhin, weil auch der Iterator die dazu notwendige Funktion __iter__ anbietet.

Soll ein Array rückwärts kopiert werden, verwendet man die Python-Standardfunktion reversed, um den passenden Iterator zu erzeugen:

reverseList  = genericCopy(reversed(array), DoublyLinkedList())  # Array rückwärts in eine Liste kopieren

Funktoren

Nachdem wir die Kopierfunktion erfolgreich verallgemeinert haben, liegt die Frage nahe, ob dies auch für andere Funktionen funktioniert, die in der inneren Schleife kompliziertere Dinge tun als einfach die Daten zu kopieren. Bei näherem Hinschauen bemerkt man auch bei solchen Funktionen viele Gemeinsamkeiten.

Betrachten wir z.B. eine Funktion, die die Summe der Elemente eines Arrays berechnet:

def sumArray(a):
    k, sum = 0, 0
    while k < len(a):
        sum = sum + a[k]  # wird später in der generischen Version durch 'sum = add(sum, a[k])' ersetzt
        k += 1
    return sum

Das Maximum der Werte in einer Liste kann man wie folgt berechnen:

def maxList(node):
    m = -999999999999999       # eine Zahl, die hoffentlich kleiner ist als das gesuchte Maximum
    while not node.isSentinel():
        m = max(m, node.data)  # max() ist eingebaute Funktion in Python
        node = node.next
    return m

Offensichtlich sind sich diese Funktionen strukturell sehr ähnlich. Außerdem wissen wir bereits, wie wir die Navigation durch die Datenstruktur mit Hilfe von Iteratoren verallgemeinern können. Es bleibt noch, die Funktionalität in der Schleife generisch zu machen. Dies geschieht mit Hilfe des Konzepts der Funktoren (auch Funktionsobjekte genannt, siehe auch in der Wikipedia).

Definition Funktor

Ein Objekt wird Funktor genannt, wenn es sich syntaktisch wie eine Funktion verwenden, das heißt mit Argumentklammer aufrufen, läßt. Wenn f ein Funktor ist, unterstützt er also Ausdrücke der Form

    f(a)      # unärer Funktor
    f(a, b)   # binärer Funktor

Das betreffende Objekt f wird dann auch als callable bezeichnet. Je nach Anzahl der erlaubten Funktionsargumente unterscheidet man unäre Funktoren (ein Argument), binäre Funktoren (zwei Argumente) usw.

In Python ist jede Funktion trivialerweise ein Funktor, denn man kann sie "wie eine Funktion" aufrufen. Anstelle des in sumArray verwendeten Additionsoperator kann man z.B. folgenden Funktor verwenden:

def add(a, b):
    return a + b

Es ist aber auch möglich, Objekte als Funktoren zu verwenden. Dazu muss die entsprechende Klasse eine Funktion __call__ bereitstellen. Die Summation kann so auch als Klassenfunktor implementiert werden:

class AddFunctor: 
    def __call__(self, a, b):
        return a + b

addf = AddFunctor()  # Funktorobjekt erzeugen
print addf(1, 2)     # AddFunctor.__call__ wird aufgerufen und gibt 3 aus

Die obigen Funktionen sumArray und maxList werden nun generisch verallgemeinert, indem man die Funktionalität in der Schleife als Funktor bereitstellt. Die Datenstruktur wird durch einen Iterator repräsentiert. Die Variable, die die Berechnungen in der Schleife akkumuliert, muss jetzt von außen an die Funktion übergeben und passend initialisiert werden:

def doSomethingGeneric(functor, iterator, accumulator):
    for k in iterator:
        accumulator = functor(accumulator, k)
    return accumulator

Damit erhalten wir folgende generische Aufrufe:

sum = doSomethingGeneric(add,  array, 0)             # statt sumArray()
sum = doSomethingGeneric(addf, array, 0)             # dito, aber mit Funktorobjekt


m = doSomethingGeneric(max, list, -999999999999999)  # statt maxList()


def append(x, y):   # Kapselt das Anfügen an eine Datenstruktur in einem Funktor
     x.append(y)
     return x

array4 = doSomethingGeneric(append, array, [])       # statt genericCopy()

Aufgrund ihrer großen Allgemeinheit und Nützlichkeit gibt es eine zu doSomethingGeneric äquivalente Funktion in vielen Programmiersprachen. Nur die Namen der Funktion und andere Details unterscheiden sich, z.B.:

• in Python und Lisp: reduce (in Python sind doSomethingGeneric und reduce vollkommen äquivalent, außer in der Geschwindigkeit, weil reduce in C implementiert ist.)
• in C++ : std::accumulate
• in Haskell: foldl

Verwandte generische Funktionen

Einige mit reduce eng verwandte Funktionen werden ebenfalls in vielen Programmiersprachen häufig angeboten. In Python gibt es z.B. die folgenden Funktionen

map

Gegeben eine Sequenz, erzeugt map eine neue Sequenz, wo ein Funktor auf jedes Element der ursprünglichen Sequenz angewendet wurde

  res = map(f, [x1, x2,...])    # gibt [f(x1), f(x2),...] zurück

Der Funktor f muss hier ein unärer Funktor sein. Angewendet auf ein Array, ist die Funktion map damit äquivalent zu

  def apply_f(x, y):
      x.append(f(y))
      return x

  res = reduce(apply_f, array, [])

filter

Gegeben eine Sequenz, erzeugt filter eine neue Sequenz, die nur diejenigen Elemente enthält, bei denen der Funktor den Wert 'True' zurückgegeben hat (f wird dann auch als unäres Prädikat bezeichnet):

  res = filter(f, [x1, x2, x3, x4,...])   # gibt [x2, x3,...] zurück, wenn f(x1) und f(x4) 'False' war

Angewendet auf ein Array, ist die Funktion filter damit äquivalent zu

  def copy_if(x, y):
      if f(y):
          x.append(y)
      return x

  res = reduce(copy_if, array, [])

Definition von Generischen Schittstellen zwischen Algorithmen und Datenstrukturen

Eine Schnittstelle (Interface) standardisiert die Kommunikation zwischen einem Algorithmus und einer Datenstruktur. Die Schnittstelle ist generisch, wenn sie nur generische Funktionalität wie z.B. standardisierte Einfügeoperationen (append), Iteratoren und Funktoren verwendet. Generischer Scnittstelle ist eng mit der Definition von Abstrakten Datentypen verwandt.

Abstrakte Datentypen

Abstrakte Datentypen sind, wie im Kapitel Einführung bereits erwähnt, durch abstrake Operationen und deren Semantik (Bedeutung ) charakterisiert. Genauer muss ein abstrakter Datentyp folgendes definieren:

• Ein Universum legaler Werte für die Objekte des Datentyps. Beim Datentyp int sind dies z.B. gewöhnlich die ganzen Zahlen zwischen -2147483648 und 2147483647, in Python jedoch alle ganzen Zahlen, soweit sie mit dem verfügbaren Hauptspeicher darstellbar sind (ein solcher Datentyp wird auch als big int bezeichnet).
• Ein (oder mehrere) Konstruktoren, die ein Objekt des Typs erzeugen, das einen legalen Initialwert repräsentiert (bei int gewöhnlich die 0).
• Eventuell Destruktoren, die die Resourcen von nicht mehr benötigten Objekten (insbesondere ihren Speicher) wieder freigeben.
• Eine Menge von Operatoren, die Objekte des Datentyps in einen anderen legalen Zustand transformieren (bei int z.B. k += 1) bzw. neue Objekte des Typs erzeugen (z.B. k + l). Die Operatoren müssen zwei Eigenschaften haben:

• Sie müssen vollständig sein, d.h. jeder legale Zustand muss durch eine geeignete Sequenz von Operatoraufrufen erreichbar sein.
• Sie müssen abgeschlossen sein, d.h. kein Zustand außerhalb des legalen Universums darf jemals entstehen.

Beispielsweise erfüllen die gewöhnlichen arithmetischen Operationen diese Anforderungen beim Datentyp int.

Für mathematische Interessierte: Der Datentyp int implementiert das mathematische Konzept eines kommutativen Rings. Darüber hinaus bietet er eine Divisionsoperation, die aber nicht die Anforderungen an einen algebraischen Zahlenkörper (engl. field) erfüllt.

Ein anderer typischer abstrakter Datentyp ist der Stack: Das Universum ist hier die Menge aller geordneten Folgen von Elementen (soweit sie in den Hauptspeicher passen), und die Operationen sind der Konstruktor (erzeugt einen leeren Stack), push (fügt ein Element ein) und pop (entfernt das zuletzt eingefügte Element). Die Abgeschlossenheit wird sichergestellt, indem der Aufruf von pop bei einem leeren Stack eine Exception auslöst.

Offered Interface versus Required Interface

Wenn man Schnittstellen vom Standpunkt der generischen Programmierung betrachtet, fällt auf, das man eine grundlegende Unterscheidung zwischen Offered Interfaces (d.h. was eine Datenstruktur anbietet) und Required Interfaces (d.h. was ein Algorithmus tatsächlich verwendet) treffen muss.

Definition Offered Interface

Das Offered Interface umfaßt die gesamte standardisierte Funktionalität, die eine Datenstruktur anbietet.

Damit eine Datenstruktur möglichst vielseitig verwendbar ist, kann ihr Offered Interface sehr breit angelegt sein. Es ist z.B. typisch, dass eine gegeben Datenstruktur mehrere abstrakte Datentypen gleichzeitig implementiert. Das Python-Array (Datentyp list) unterstützt beispielsweise die Funktionalität:

• dynamisches Array (a[i], a.append(x) etc.)
• Stack (a.pop() und a.append(x) statt push)
• Queue und Deque (via a.insert(0, x))
• verkettete Liste (Einfügen und Löschen an beliebiger Stelle via a.insert(index, x) und del a[index])

Die beiden letzten Punkte sind allerdings (gegenüber spezialisierten Datenstrukturen) mit Abstrichen in der Performanz verbunden -- diese Operationen erfordern beim Python-Array lineare Zeit, anstatt konstanter wie bei einer echten Queue oder verketten Liste.

Oft bietet ein Offered Interface auch die gleiche Funktionalität unter mehreren Namen, damit die Datenstruktur in verschiedenen Umgebungen verwendbar ist (beispielsweise kann eine Funktion zum Zwecke der Rückwärtskompatibiltät beibehalten werden, obwohl sie inzwischen als deprecated gekennzeichnet wurde). Häufig findet man auch sogenannte convenience functions, die im strengen Sinne nicht notwendig sind (weil sie aus bereits vorhandenen Funktionen zusammengebaut werden können), aber trotzdem das Leben des Programmierers erleichtern. Beispielsweise würde es beim Datentyp int vollkommen ausreichen, wenn nur der Vergleichsoperator "<" angeboten würde, denn alle anderen Vergleiche kann man leicht damit implementieren:

a = b ⇔ ¬(a < b) ∧ ¬(b < a)

a ≠ b ⇔ (a < b) ∨ (b < a)

a ≤ b ⇔ ¬(b < a)

a > b ⇔ b < a

a ≥ b ⇔ ¬(a < b)

Trotzdem bietet int alle Vergleichsoperatoren, weil obige Ersetzungen unbequem und schwerer lesbar wären.

Definition Required Interface

Das Required Interface umfasst die Funktionalität einer Datenstruktur, die ein Algorithmus tatsächlich benutzt.

Das Required Interface umfasst gewöhnlich nur einen (evtl. kleinen) Teil des Offered Interface. Ein typischer Fall ist es beispielsweise, dass ein Algorithmus nur lesend auf eine Datenstruktur zugreift, obwohl die Datenstruktur auch schreibenden Zugriff anbietet. Bei Zahlen kommt es häufig vor, dass nur die Addition benutzt wird, obwohl int auch die Subtraktion und Multiplikation etc. unterstützt.

Der entscheidende Punkt besteht nun darin, dass Required Interfaces minimal sein sollten und getrennt von den Offered Interfaces (welche ja gerade nicht minimal sind) standardisiert werden müssen, damit Algorithmen ihre volle Generizität erreichen. Beispielsweise unterstützen alle Python-Containerdatentypen, so verschieden sie sonst auch sind, die Funktion len(container). Die Standardisierung des Required Interface fordert nun, dass diese Funktion auch tatsächlich bei allen Containern len heißt, und nicht einmal size, und dann wieder numberOfElements. Man beachte, dass diese Standardisierung in der Tat unabhängig von den Offered Interfaces ist, weil dieselbe Datenstruktur durchaus size, length und numberOfElements gleichzeitig anbieten kann, wenn sie in mehreren Algorithmenumgebungen lauffähig sein soll, deren Required Interfaces verschiedenen Standards unterliegen.

Im Sinne der Minimalität kann sich ein Algorithmus z.B. darauf beschränken, nur den Vergleichsoperator "<" zu verwenden, und die anderen Vergleichsoperatoren wie oben beschrieben zu ersetzen, auch wenn dies weniger bequem ist. Dann wäre der Algorithmus immer noch lauffähig, wenn eine Datenstruktur nur "<" implementiert, auch wenn dies ein eher hypothetischer Fall ist.

Required Interfaces werden häufig in Form von Konzepten standardisiert. Ein Konzept umfaßt eine Menge von Operationen, die ein Algorithmus typischerweise zusammen benötigt. Konzepte sind damit das Gegenstück zu Abstrakten Datentypen, da letztere Operationen enthalten, die Datenstrukturen typischerweise zusammen anbieten. Das Konzept für Container, die die Funktion len(container) unterstützen, könnte z.B. Sized genannt werden (falls es Algorithmen gibt, die sonst weiter nichts von einer Datenstruktur fordern. Andernfalls wäre die Einführung eines separaten Konzepts hierfür überflüssig.) Die Entwicklung einer Menge von sorgfältig aufeinander abgestimmten Konzepten, und ihre Organisation in Konzepthierarchien, ist zur Zeit ein aktives Forschungsgebiet. Die Standard Template Library der Progammiersprache C++ muss in dieser Hinsicht als vorbildlich bezeichnet werden. Hier sind die Konzepte extrem sorgfältig definiert, und Offered Interfaces sind konsequent als Sammlung aller Konzepte definiert, die eine gegebene Datenstruktur effizient unterstützen kann.

Wichtige Konzepte

Einige wichtige Konzepte sollen hier erwähnt werden:

• Copy Constructible: Objekte, die man kopieren kann (in Python durch copy.deepcopy).
• Singleton: Objekte, die man nicht kopieren kann (z.B. weil sie einen Drucker repräsentieren, der physisch nur einmal vorhanden ist).
• Default Constructible: Klassen, die einen Konstruktor ohne Argumente unterstützen, welcher ein Objekt in einem Standardzustand initialisiert (in Python z.B. list() für ein leeres Array, int() für die Zahl 0, und allgemein v1 = v.__class__() für beliebige Klassen).
• Vergleiche:

• Equality Comparable: unterstützt a == b
• LessThan Comparable: unterstützt a < b
• ThreeWay Comparable: unterstützt cmp(a, b) mit Ergebnis -1, falls a < b, 0 falls a = b und +1 falls a > b.

• Indexable: unterstützt x = a[k] und a[k] = x, wobei k ein Integer im Bereich 0, ..., len(a)-1 ist.
• Mapping: unterstützt x = a[key] und a[key] = x, wobei der Typ von key beliebig sein kann, solange er Hashable ist.
• Hashable: key unterstützt hash(key), so dass key als Schlüssel in einer Hashtabelle verwendet werden kann.
• Iteratoren:

• ForwardIterator unterstützt iter.next() um zum nächsten Element zu gelangen
• BidirectionalIterator unterstützt zusätzlich iter.prev() um zum vorhergehenden Element zu gelangen
• RandomAccessIterator unterstützt zusätzlich iter.next(k) und iter.prev(k) um vorwärts oder rückwärts k Elemente zu überspringen

Die beiden letzeren Konzepte sind zur Zeit in Python nicht standardisiert, jedoch z.B. in C++. Forward Iteratoren werden normalerweise von allen Containern unterstützt (manche bieten sogar mehrere, je nach gewünschter Reihenfolge, z.B. Preorder-, Inorder-, und Postordertraversal bei einem Binärbaum). Bidirektionale Iteratoren werden typischerweise von doppelt verketteten Listen unterstützt, random access Iteratoren typischerweise von statischen und dynamischen Arrays. Wenn man für eine Datenstruktur mindestens einen bidirektionalen Iterator hat, kann man stets einen Rückwärtsiterator implementieren (indem man next und prev vertauscht).

• Funktoren:

• Unary Functor: unterstützt y = f(x)
• Binary Functor: unterstützt y = f(x1, x2)
• Unary Predicate: unterstützt f(x) → {True, False}

etc.

• Mathematische Konzepte:

• Addable: unterstützt a + b
• Subtractable: unterstützt a - b
• Multiplicable: unterstützt a * b
• Dividable: unterstützt a / b

etc.

Wenn man in Python eine Klasse implementieren will, die eins der genannten Konzepte unterstützt, gibt es standardisierte Funktionennamen, die mit zwei Unterstrichen beginnen und enden, wie z.B. __init__ (Konstruktor), __cmp__ (3-Wege-Vergleich), __hash__ (Hashwert), __getitem__ und __setitem__ (lesender und schreibender Arrayzugriff) , __iter__ (Iterator), __add__ (Addition), __sub__ (Subtraktion), __mul__ (Multiplikation), __div__ (Division) etc (eine vollständige Liste findet man im Python Index). Der Python-Interpreter transformiert die normale Pythonsyntax automatisch in Aufrufe dieser Funktionen, falls ein Ausdruck Objekte enthält, die die entsprechenden Konzepte unterstützen.

Nächstes Thema