Generizität

Generische Programmierung - Definition und Motivation

Ziel von generischer Programmierung [1] 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 nit 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 k

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 in 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 generische 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 Liste 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 signalisieren, implementieren 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 keine 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 Knostruktor 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 aufruffenden 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

Generische Kopierfunktion

Mit diesen 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 nun 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)     # 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 nun 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):   # Kapsle 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

Offered Interface versus Required Interface

Interface:

• standardisierte Schnittstelle zwischen Algorithmen und Datenstruktur

Offered Interface:

• Funktionalität, die eine Datenstruktur anbietet.
• Die Datenstruktur sollte möglichst vielseitig sein.

z.B. PythonList unterstützt Funktionalität von :

• Dynamisches Array
• Stack
• Deque
• LinkedList

• standardisiert durch abstrakte Datentypen

Required Interface:

• Funktionalität, die von einem Algorithmus benutzt wird
• das required Interface ist meist weniger als das offered Interface

z.B.:

RI: lesender Zugriff
OI schreibender Zugriff Konstruktor, remove...

• standardisiert durch Konzepte

• ADT sind Sammlungen zusammengehörender Konzepte
• RIs sollten minimal sein

Konzepte ( + Hierarchie)

• copy Constructible ( Python:Klassen, die man auf deepcopy anwenden kann, copy.deepcopy)

(Gegenteil : Singleton)

• Default Constructible (v1 = v.__class__() ist aufrufbar ) # DoublylinkedNode
• EqualityComparable('=='), LessThanComparable('<')
• ThreeWayComparable(__cmp__ ist aufrufbar)
• Indexable("a[k]", k ist Integer)
• Mapping("a[key]", key ist arbitrary)
• Hashable(__hash__ für key)

• Iteratoren :(C++ : ForwardIterator : next, BidirektionalIterator : next, prev ,
  RandomAccessIterator : next[k])

Container :               Sequence                                       Array

Mathematische Konzepte :

Addable(__add__)
Subtractable(__sub__)
Multiplyable(__mul__)
Dividable(__div__)

Ein offered Interface ist mehr als ein required Interface.