Verzögerte Ausführung mit Python

Programmiersprachen können unter anderem in der Art unterschieden werden wie sie Ausdrücke auswerten. Die meisten Programmiersprachen verwenden sogenannte eager evaluation - Ausdrücke werden in dem Moment berechnet, wo sie im Programmfluss stehen. Andere Programmiersprachen (zum Beispiel Miranda und Haskell) gehören zu den Sprachen die lazy evaluation benutzen: Ausdrücke werden zum spätest möglichen Zeitpunkt ausgewertet, nämlich erst dann wenn ihr Ergebnis zwingend benötigt wird.

Lazy Evaluation bietet dabei einige praktische Vorteile: zum Beispiel können komplette Ausdrücke und Funktionsaufrufe einfach verworfen werden, wenn sich im späteren Programmfluss ergibt das sie garnicht benötigt werden. Auch können komplexe Datenstrukturen nur so weit ermittelt werden, wie sie tatsächlich benötigt werden. In Sprachen mit eager evaluation wird in einem Programm oft Code ausgeführt dessen Ergebnis nichts zur eigentlichen Problemlösung beiträgt - eine Tatsache die sich aber im Programmfluss noch garnicht ergeben hatte, als dieser Code ausgeführt wurde - erst viel später wurde festgestellt, das ein Ergebnis nicht nötig ist.

Als Brücke zwischen diesen beiden Extremen gibt es oft einen Mechanismus namens delayed execution - hierbei wird Programmcode so eingebettet, das anstelle den Ausdruck zu berechnen einfach nur ein Versprechen (ein Promise) ermittelt wird. Dieser Promise garantiert das in geeigneter Situation diese Berechnung ausgeführt werden kann - und zwar in dem Kontext in dem sie bei Erstellung des Promise war (also im gleichen lexikalischen Context).

Hierzu benötigt eine Sprache die Möglichkeit einen lexikalischen Context einzufangen - eine Closure zu bilden. Eine Closure ist im Prinzip ein Stück Code mit aufgelösten freien Variablen (Variablen die nicht in diesem Code selber definiert sind) auf die Werte, die zum Zeitpunkt der Bildung der Closure vorlagen.

Eine Sprache die sowohl Closures als auch delayed execution anbietet ist Scheme. Hier gibt es die beiden speziellen Ausdrücke delay und force. delay bildet eine Closure über einen als Parameter übergebenen Ausdruck und verpackt diesen als Promise. force zwingt die Auswertung eines Promise und cached das Ergebnis so das weitere Aufrufe von force auf den Promise das gleiche Ergebnis liefern.

In Python kann man diesen Mechanismus sehr einfach mit anonymen Funktionen - lambda - nachbilden:

def delay(func, *args, **kw):

    return lambda : apply(func, args, kw)

def force(promise):

    return promise()

# einen Promise für die Berechnung einer Liste von

# Zahlen bilden.

promise = delay(range, 0, 10)

# die Zahlen ermitteln

liste = force(promise)

Diese sehr einfacher Realisierung hat allerdings zwei Probleme: zum Einen wird das Ergebnis nicht zwischengespeichert (und damit eine Forderung an den Promise - das er bei jedem Aufruf das gleiche Ergebnis liefert - unter Umständen nicht erfüllt) und zum Anderen kann man einen Promise nicht gut erkennen. Alles mögliche kann eine Funktion sein - der Typ des von delay zurückgelieferten Wertes ist ja einfach eine Funktion.

Was wir also brauchen ist ein Weg diese beiden Zielen - Caching eines einmal ermittelten Wertes und Erkennbarkeit eines Promise - zu erreichen. Das geht mit Objekten ganz hervorragend:

# die folgende Klasse ist ein Singleton - es gibt nur

# einen einzigen Wert. Dieser Wert dient dazu als

# nicht existenter Wert benutzt zu werden. Wir können

# nicht None benutzen, da None ja ein gültiges Ergebnis

# einer Funktion sein könnte!

class NoneSoFar(object):

      pass

NoneSoFar = NoneSoFar()

class Promise(object):

      def __init__(self, func, args, kw):

          self.__func = func

          self.__args = args

          self.__kw = kw

          self.__result = NoneSoFar

      def __force__(self):

          if self.__result is NoneSoFar:

             self.__result = apply(self.__func,

                     self.__args, self.__kw)

          return self.__result

def delay(func, *args, **kw):

    return Promise(func, args, kw)

def force(promise):

    if hasattr(promise, '__force__'):

       return promise.__force__()

    return promise

# die lazy liste bilden

promise = delay(range, 0, 10)

# die Liste ermitteln

liste = force(promise)

Diese Lösung hat auch noch den netten Vorteil das unsere force Funktion erkennt ob sie einen Promise vor sich hat - und zwar daran, das eine Methode __force__ definiert ist. Das passt gut zu anderen Situationen in Python wo Typen nicht durch die Klasse oder den Typ selber definiert sind, sondern durch die Eigenschaften die sie erfüllen. Man nennt das duck typing: if it quacks like a duck, if it looks like a duck and if it walks like a duck - treat it like a duck.

Obiges Beispiel kann nicht nur Funktionsausdrücke kapseln - man kann jede Berechnung einfangen in dem man einfach eine Closure bildet:

# komplexe Berechnung als Promise speichern

promise = delay(lambda : 5+6)

# komplexe Berechnung später aufrufen

wert = force(promise)

Eventuelle freie Variablen im Ausdruck werden durch die Closure zum Zeitpunkt der Definition eingefangen und mit im Promise gespeichert.

Die obige Lösung hat noch ein wichtiges Problem: der Aufruf von force muss zwingend vom Programmierer verwendet werden. Wir sind schon besser dran als in der ersten Lösung, da wir eindeutig einen Promise erkennen können und deshalb Werte die kein Promise sind von force einfach durchgelassen werden ohne Veränderung (force verhält sich hier wie die Identitätsfunktion).

Allerdings ist es trotzdem lästig wenn man Ausdrücke schreibt die mit Parametern arbeiten die eventuell ein Promise sein könnten - an allen Ecken und Enden tauchen die force Aufrufe auf. Im Ergebnis führt das oft dazu, das Programmierer die force Aufrufe rein aus Verdacht früh im Code machen. Und damit einen Teil der Vorteile von lazy evaluation negieren: das Ergebnisse erst dann berechnet werden, wenn sie gebraucht werden.

Python bietet hierfür auch eine sehr praktische Methode: alle möglichen innereien sind überschreibbar durch die sogenannten magic methods: Methoden an Objekten die Namen haben die mit zwei Unterstrichen eingeleitet und ausgeleitet werden. Zum Beispiel gibt es __add__ zur Implementierung des + Operators und dementsprechend __sub__ für die Subtraktion. Und noch einen ganzen Satz weiterer Funktionen - eine komplette Liste gibt es in der Python Sprachdefinition.

Wir können also unser kleines Beispiel ein bischen aufmotzen. Die folgende Version wird automatisch bei einem Promise den force Aufruf machen, wenn das Ergebnis in einer binären Operation benutzt wird:

# die folgende Klasse ist ein Singleton - es gibt nur

# einen einzigen Wert. Dieser Wert dient dazu als

# nicht existenter Wert benutzt zu werden. Wir können

# nicht None benutzen, da None ja ein gültiges Ergebnis

# einer Funktion sein könnte!

class NoneSoFar(object):

      pass

NoneSoFar = NoneSoFar()

class Promise(object):

      def __init__(self, func, args, kw):

          self.__func = func

          self.__args = args

          self.__kw = kw

          self.__result = NoneSoFar

      def __force__(self):

          if self.__result is NoneSoFar:

             self.__result = apply(self.__func,

                     self.__args, self.__kw)

          return self.__result

      def __add__(self, other):

          self = force(self)

          other = force(other)

          return self + other

      def __sub__(self, other):

          self = force(self)

          other = force(other)

          return self - other

      def __mul__(self, other):

          self = force(self)

          other = force(other)

          return self * other

      def __div__(self, other):

          self = force(self)

          other = force(other)

          return self / other

def delay(func, *args, **kw):

    return Promise(func, args, kw)

def force(promise):

    if hasattr(promise, '__force__'):

       return promise.__force__()

    return promise

# zwei komplizierte Operationen als Promise speichern

promise1 = delay(lambda : 5+6)

promise2 = delay(lambda : 7+8)

# das Ergebnis multiplizieren

wert = promise1 * promise2

# zwei lazy listen bilden

promise1 = delay(range, 0, 10)

promise2 = delay(range, 10, 20)

# die Listen zusammenfügen

liste = promise1 + promise2

Diese Beispiele zeigen das der Aufruf von force gut automatisiert ausgeführt werden kann, wenn denn bekannt ist, das eine bestimmte Operation zwingend einen Wert braucht. Da die Operatoren den force Aufruf auf beide Seiten ausführen ist auch relativ egal wo der Promise steht - wichtig wäre nur, das man auch die rechts-Varianten (__radd__ and friends) implementiert. Eine geeignete Version von Promise könnte also wie folgt aussehen:

# die folgende Klasse ist ein Singleton - es gibt nur

# einen einzigen Wert. Dieser Wert dient dazu als

# nicht existenter Wert benutzt zu werden. Wir können

# nicht None benutzen, da None ja ein gültiges Ergebnis

# einer Funktion sein könnte!

class NoneSoFar(object):

      pass

NoneSoFar = NoneSoFar()

class Promise(object):

      def __init__(self, func, args, kw):

          self.__func = func

          self.__args = args

          self.__kw = kw

          self.__result = NoneSoFar

      def __force__(self):

          if self.__result is NoneSoFar:

             self.__result = apply(self.__func,

                     self.__args, self.__kw)

          return self.__result

      def __add__(self, other):

          self = force(self)

          other = force(other)

          return self + other

      def __sub__(self, other):

          self = force(self)

          other = force(other)

          return self - other

      def __mul__(self, other):

          self = force(self)

          other = force(other)

          return self * other

      def __div__(self, other):

          self = force(self)

          other = force(other)

          return self / other

      def __radd__(self, other):

          self = force(self)

          other = force(other)

          return other + self

      def __rsub__(self, other):

          self = force(self)

          other = force(other)

          return other - self

      def __rmul__(self, other):

          self = force(self)

          other = force(other)

          return other * self

      def __rdiv__(self, other):

          self = force(self)

          other = force(other)

          return other / self

def delay(func, *args, **kw):

    return Promise(func, args, kw)

def force(promise):

    if hasattr(promise, '__force__'):

       return promise.__force__()

    return promise

# eine komplizierte Operationen als Promise speichern

promise = delay(lambda : 5+6)

# den Wert des Promise in zwei Ausdrücken benutzen

wert1 = 5 * promise

wert2 = promise * 5

Wer sich die ganzen magic methods in der Python Sprachdefinition durchguckt wird feststellen das er eine ganze Menge Methoden schreiben darf. Das kann man natürlich locker machen, schliesslich ist das nur einmal zu machen. Aber vielleicht will man ja den Promise auch mal in anderer Form speichern - wie oben geschrieben, ein Promise ist einfach nur etwas das eine Methode namens __force__ definiert, was sie sonst macht bleibt ihr überlassen. Es könnte also sein das man eine ganz eigene Klasse für Promises schreiben will - und dann muss man wieder all die lästigen Funktionen definieren. Oder von einer Basisklasse vererben.

Hier bietet Python ebenfalls ein mächtiges Mittel: die Metaklassen. Metaklassen sind die Klassen von denen die Klassen von Instanzen die Instanzen sind. Komplett verwirrt? Gut. Smiley

Nochmal zum Auseinanderpflücken: in Python sind Objekte Instanzen von Klassen. Diese Klassen hingegen sind auch wieder Instanzen - und zwar Instanzen von Metaklassen. Die Klassenmethoden einer Klasse sind einfach die Instanzmethoden der Metaklasse. Wer in Python mit classmethod(method) eine Klassenmethode definiert, definiert in Wirklichkeit eine Instanzmethode an einer Metaklasse. Jede Klasse hat eine Metaklasse - bzw. eine Instanz einer Metaklasse. Die meisten Klassen benutzen Standardmetaklassen.

Man kann diese aber sehr einfach überschreiben. Bei den new style Klassen in Python (denen die von einem eingebauten Typ - meistens object - abgeleitet sind) wird dazu einfach eine Klassenvariable __metaclass__ definiert, die auf die zu verwendende Metaklasse zeigt.

Was machen Metaklassen nun? Sie sind eigentlich nichts weiter als die Produktionsstätten unserer Klassen die wir definieren. Ihr Code wird also zum Definitionszeitpunkt einer Klasse ausgeführt. Dadurch können Metaklassen das Verhalten einer Klasse zum Definitionszeitpunkt komplett verändern. Wir sind nur an einer Möglichkeit dieser Veränderung interessiert: wir wollen einen ganzen Satz von Methoden an einer Klasse automatisch definieren. Das ganze sieht einfacher aus als es sich beschreiben lässt, also hier das Beispiel:

# den kennen wir ja schon

class NoneSoFar(object):

      pass

NoneSoFar = NoneSoFar()

# Metaklassen erben vom Typ type

class MetaPromise(type):

      __magicmethods__ = {

         '__len__': len,

         '__add__': lambda a,b: a+b,

         '__sub__': lambda a,b: a-b,

         '__mul__': lambda a,b: a*b,

         '__div__': lambda a,b: a/b,

         '__radd__': lambda a,b: b+a,

         '__rsub__': lambda a,b: b-a,

         '__rmul__': lambda a,b: b*a,

         '__rdiv__': lambda a,b: b/a

      }

      def __init__(klass, name, bases, attributes):

          for (n,f) in klass.__magicmethods__.items():

              setattr(klass, n, klass.__forced__(f))

          super(MetaPromise, klass).__init__(name,

                   bases, attributes)

      def __forced__(klass, func):

          def wrapper(*args, **kw):

              args = [force(arg) for arg in args]

              kw = dict([(k, force(v)) for (k,v)

                            in kw.items()])

              return apply(func, args, kw)

          return wrapper

class Promise(object):

      __metaclass__ = MetaPromise

      def __init__(self, func, args, kw):

          self.__func = func

          self.__args = args

          self.__kw = kw

          self.__result = NoneSoFar

      def __force__(self):

          if self.__result is NoneSoFar:

             self.__result = apply(self.__func,

                  self.__args, self.__kw)

          return self.__result

def delay(func, *args, **kw):

    return Promise(func, args, kw)

def force(promise):

    if hasattr(promise, '__force__'):

       return promise.__force__()

    return promise

# einen Promise erzeugen

promise = delay(range, 0, 10)

# den die länge der Liste ermitteln (macht den force)

print len(promise)

Ok, das war jetzt doch ein bischen viel Code auf einem Haufen. Gehen wir es einfach der Reihe nach durch:

die Klasse MetaPromise ist die Metaklasse unserer Promises. Ihre Aufgabe ist die Erstellung der Promise Klassen die sich auf sie beziehen.
in der Klasse MetaPromise ist ein Dictionary unter dem Namen __magicmethods__ definiert. Dieses enthält eine Reihe von Methodennamen und eine simple Alternativimplementierung - entweder direkt als Funktion oder über einen lambda Ausdruck.
in der __init__ Methode der Metaklasse wird die eigentliche Klasse selber erzeugt - immer dran denken, Klassen sind einfach Instanzen von Metaklassen. Und so wie bei normalen Instanzen die __init__ Methode zur Initialisierung ausgeführt wird, so passiert das gleiche auch bei Klassen und ihren Metaklassen.
die __init__ Methode patched als erstes die ganzen Methoden aus __magicmethods__ in die zu definierende Klasse rein. Sie benutzt dazu eine Methode __forced__ der Klasse MetaPromise.
Die Methode __force__ benutzt Closures und nested Scope um eine leicht veränderte Funktion zu erstellen. Und zwar wird jeder von uns in __magicmethods__ definierten Funktion der nötige Code zum force auf die Parameter vorgestellt.
die Klasse Promise selber referenziert einfach nur die Metaklasse als ihre zu verwendende Metaklasse in __metaclass__.

Der Rest ist wieder ganz normal. Wenn jetzt eine Instanz der Klasse Promise gebildet wird, hat diese automatisch die ganzen speziellen Methoden die benötigt werden um schnell und heimlich den force Aufruf reinzumogeln, wenn das Ergebnis in einem Ausdruck benutzt wird der ein Ergebnis verlangt.

Das ganze Beispiel kann man jetzt um die ganzen magic methods erweitern die Python unterstützt. Ich selber habe das in meinem lazypy gemacht. Eine Besonderheit dort: Aufrufe der __getattr__, __getitem__, __getslice__ und __call__ Methoden bewirkt nicht eine direkte Ermittlung des Wertes (also einen Aufruf von force), sondern erzeugt einen weiteren Promise. Dadurch werden Attributzugriffe und Zugriffe auf Items von Dictionaries und die Aufrufe von Methoden (ein Methodenaufruf ist in Python nur ein Aufruf von __getattr__ gefolgt von einem Aufruf von __call__) auch verzögert. Dadurch kann man mit meinem Modul hervorragend Datentypen definieren die lazy evaluation benutzen: alle Objektzugriffe und Zugriffe auf enthaltene Dictionarystrukturen und Listen (Objekte, Dictionaries und Listen werden in Python ja gerne für die Konstruktion komplexer Datenstrukturen verwendet) werden erst ausgeführt, wenn der Ergebniswert wirklich gebraucht wird.

Für das ganze habe ich sogar eine praktische Anwendung (allerdings ist lazypy dort noch nicht eingebaut sondern derzeit noch eine recht gehackte Implementierung): ich habe in asfPY sogenannte Autocommit-Roots eingeführt. Die Root ist ja in asfPY der Aufhänger für alle Datenbankzugriffe. Die Autocommit-Root ist eine Form der Root die direkt und sofort einen Commit ausführt, sofern ihr innerer Code ohne Fehler durchläuft. Das ist für einfachen Programmcode oft ausreichend und ideal für interaktives Spielen mit der Datenbank.

Ein wesentlicher Punkt von Autocommit-Roots ist, das die eigentlichen Zugriffe so spät wie möglich gemacht werden, damit die enthaltene Transaktion möglichst viel Datenbankcode umfasst. Denn entgegen der klassischen relationalen Datenbank ist der kleinste Zugriff auf asfPY ja gleich ein Zugriff auf ein ganzes Bündel von Datenbanktabellen.

Durch lazy evaluation kann ich jetzt dafür sorgen, das die eigentlichen Datenbankzugriffe alle in einem zeitlichen Punkt ablaufen - und zwar direkt dann, wenn das Ergebnis auch gebraucht wird. Wird das Ergebnis garnicht gebraucht, fällt auch kein einziger Datenbankzugriff an!

Ich hoffe dieser Text konnte einige der mächtigen Sprachmittel von Python nahe bringen und ein paar Denkanstösse geben, wie man vielleicht das eine oder andere Problem in Python eleganter lösen kann.

Der Code ist übrigens grösstenteils so runtergeschrieben - wenn jemandem ein Fehler auffällt, bitte melden. Ich hab nicht alle Beispiele direkt ausprobiert.