Generizität

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

Gemeint sind :

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

--> ohne Neuimplemenation

• Code austauschen in Bibliotheken

Beispiel :

Kopieren eines Containers

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 Implementaionsaufwand <math>O({N}^2 )</math>. Alle Funktionen machen das gleiche mit uninteressantem Unterschied

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)

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

---

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

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

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

besser stattdessen :

     return self.__class__(self.node)          # ist allgemeiner

Was tut Python bei " for k in quelle"(in gernericCopy)?:

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

Rückwärts kopieren :

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(), []),
revList = genericCopy(reversed(array), DoublyLinkedList())

Funktoren

---

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 Funkion 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
aber 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 is mehr als ein required Interface.