Generizität

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

Gemeint sind :

• verschiedene Anwendungen
• mit vielen Kombinationsmöglichkeiten
• als wiederverwendbare Bibliothek

--> ohne Neuimplementation

• Code austauschen in Bibliotheken

Motivation

An einem Beispiel wollen wir zeigen, wie ähnlich das Kopieren eines Containers für verschiedene Datentypen abläuft:

Code

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

class Node :
 def__init__(self, data, next)
    self.data = data
    self.next = next

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

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

Beobachtung

Für N Datenstrukuren ist der Implementationsaufwand <math>O(N^2) </math>, wenn man je zwei Datenstrukturen ineinander umwandeln können will. Alle Funktionen machen das gleiche mit einem uninteressantem Unterschied. Wir wollen daher im Folgenden eine Möglichkeit angeben, das kopieren der Daten zu vereinheitlichen.

Verbesserungsmöglichkeiten

Verbesserung durch Verallgemeinerung zweier Aspekte :

• Navigieren durch die Quelldaten
• Aufbauen der Zieldatenstruktur

Vereinheitlichung der Zieldatenstruktur :

• standardisierte Funktion "append"
• Array hat sie schon
• Liste : definiere Klasse DoublyLinkedList

class SentinelTag : pass     # keine Daten

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)

class DoublyLinkedList :             # Realisiert doppelt verbundene kreisförmige Kette mit Sentinel                                                                                  
                                      #  als "Anker"
  def__init__(self):
           self.sentinel = DoublyLinkedNode()
           self.size = 0
      def__len__(self): return self.size   #len(l)
      def append(self, value):
          DoublyLinkedNode(value, self.sentinel)
          self.size += size
      def__iter__(self):
           return ListIterator(self.sentinel.next)
      def reverseIterator(self):
            return ListIterator(self.sentinel.prev)

verbesserter Code

Mit diesen Schnittstellen reicht uns nun eine einzige Methode zum Kopieren eines Containers aus.

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

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

Iteratoren

---

Definition Iterator: siehe [2]

Navigation in der Quelldatenstruktur ( Iteratoren ) soll
für alle Datenstrukturen funktionieren

Ein Iterator ist ein Objekt,

• das auf ein Element des Containers zeigt
• das zum nächsten Element weiter rücken kann
• das anzeigt, wenn das Ende der Sequenz erreicht ist

Beispiel:

class ListIterator:
      def __init__(self, node):
           self.node = node
      def next(self):
            if self.node.isSentinel():
                  raise StopIteration()            #Python Konvention
            v = self.node.data
            self.node = self.node.next            # zeigt Ende der Sequenz
            return v                                   # Pythonkonvention, gebe vorigen Wert zurück

      def __iter__(self):
         return ListIterator(self.node)            # Pythonkonvention, Kopie des Iterators zurückgeben
            #oder stattdessen besser:
         return self.__class__(self.node)          # ist allgemeiner

Was tut Python bei " for k in quelle"( in genericCopy ) ?:
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?
Das Schlüsselwort for ruft dabei die Methode iter() der entsprechenden Klasse auf, die einen Zeiger auf ein Iterator-Objekt zurückgibt. Dieses Objekt definiert eine Methode next(), womit man das nächste Element der Datenstruktur bekommen kann. Wenn keine weiteren Elemente mehr vorhanden sind, wird eine Exception StopIteration ausgelöst.

iter = quelle.__iter__()
try :
       while True :
             k = iter.next()
             ...             # Schleifeninhalt
except StopIteration: pass

Rückwärts kopieren : Um eine Liste rückwärts zu kopieren, könnten wir also folgenden Iterator verwenden:

class ReverseListIterator(ListIterator)
  def next(self):
      if self.node.isSentinel(): raise StopIteration()
      v = self.node.data
      self.node = self.node.prev
      return v

revArray = genericCopy(list.reverseIterator(), []),          # Liste in ein Array kopieren
revList = genericCopy(reversed(array), DoublyLinkedList())   # Array umdrehen und dann in eine Liste kopieren

Funktoren

---

Definition eines Funktors : siehe [3]

Verallgemeinerung auf Funktionen die " etwas tun":

    def sumArray(a):
        s = 0
        for k in a :
            s += a       # s = add(s,k)
      return a

def maxList(l):
   m = -1111111111111111
   while not l.isSentinel:
        m = max(m, l.data)                    # max ist eingebaute Funktion in Python
        l =l.next
   return m

Verallgemeinerung durch Funktoren :

• Funktor muss "callable" sein : falls f Funktor ist, funktioniert v = f(a1, a2,...)
• Funktion, oder Objekt bei dem die Funktion __call___ definiert ist.

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

Statt maxList:

m = doSomethingGeneric(max,list, -1111111111111111)  

Statt sumArray :

def add(x,y): return x + y
  s = doSomethingGeneric(add, array, 0)

Statt genericCopy :

def append(x,y):
     x.append(y)
   return x
array4 = doSomeThingGeneric(append, array, [])

doSomethingGeneric gibt es in vielen Programmiersprachen :

• in Python : reduce
• in C++ : accumulate

...funktionale Sprachen (Lisp, Haskell...)

verwandte generische Funktionen

map:

[x1, x2,...] --> [f(x1),f(x2),...] # Funktor mit einem Argument

Offered Interface versus Required Interface

---

Interface:

• standardisierte Schnittstelle zwischen Algorithmen und Datenstruktur

Offered Interface:

• Funktionalität, die eine Datenstruktur anbietet.
• Die Datensruktur 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.