Montag, Februar 05, 2007

Kontrolltechnik: Verzögerung

Bei imperativen (= befehlsorientierten) Programmiersprachen wie Python, Ruby, Java oder C# herrscht das "Gesetz des nächsten Befehls" -- so nenne ich das jedenfalls gerne. Nach der Ausführung eines Befehls wird unweigerlich der nächste Befehl abgearbeitet, dann der übernächste, dann der überübernächste usw. Die Anweisungen werden schlicht in Reihe (sequentiell) abgearbeitet. Eine Ausnahme davon bilden Sprünge. Eine Sprunganweisung erlaubt es, mehrere Anweisungen vor oder zurück zu springen. Ist die Sprunganweisung an eine Bedingung geknüpft, dann kann bedarfsweise gesprungen werden. Ohne bedingte Sprünge wäre das Programmierleben ziemlich trist. Es gäbe sonst nur Programme, die Befehle "von oben nach unten" abarbeiteten und schlimmstenfalls in einer Endlosschleife gefangen blieben.

An dem "Gesetz des nächsten Befehls" ist nicht zu rütteln. Vordergründig ist ein Programm in einer imperativen Sprache als Kette von Anweisungen zu schreiben und zu verstehen. Der Kontrollfluss, der thread of control, folgt den Anweisungen. Sobald ein Programmierer aber irgendetwas Interessantes machen möchte, ist er zwar gezwungen dieses vordergründige Ausführungsschema beizubehalten, tatsächlich aber wird er in die "Trickkiste" greifen, um sich aus dieser Abhängigkeit zu lösen. Zwei dieser wesentlichen "Tricks" möchte ich Ihnen heute vorstellen: verzögerter Aufruf und verzögerte Ausführung. Statt "verzögerter Aufruf" könnte man auch "verzögerte Kommunikation" sagen, da in imperativen Sprachen Aufrufe das Mittel zur Kommunikation zwischen Programmteilen sind. Als Programmierer werden Ihnen beide Techniken bekannt sein, nur vielleicht nicht unter diesem Namen. Und vielleicht haben Sie beide Techniken auch noch nicht auf diese Weise in "Reinkultur" betrachtet.

Verzögerter Aufruf

Nehmen wir folgendes Programmfragment in der Sprache Python. Zunächst binden wir die Bibliothek "math" ein, dann definieren wir die Funktion "calc". Die Funktion nimmt eine Zahl entgegen, ruft die "Wurzelzieh"-Funktion aus der Mathe-Bibliothek aus, addiert Eins dazu und liefert das Ergebnis zurück.

import math

def calc(n):
x = math.sqrt(n)
return x + 1

Wenn eine andere Funktion aufgerufen wird, hier "math.sqrt", dann folgt der Kontrollfluss dem Aufruf. Es handelt sich also um einen unbedingten (nicht von einer Bedingung abhängigen) Sprung! Bevor der Sprung zu der anderen Funktion ausgeführt wird, merkt sich die Python-Ausführungsmaschine zum einen den aktuellen Wert von Variablen in "calc", hier den Wert von "n". Zum anderen wird sich gemerkt, an welcher Stelle die Ausführung nach dem Aufruf von "math.sqrt" fortzusetzen ist, d.h. an welche Stelle nach der Ausführung von "math.sqrt" zurück zu springen ist. Diese Information wird auf einem sogenannten Call-Stack abgelegt.

Was können wir tun, wenn wir den Aufruf (call) "math.sqrt(n)" nicht sofort ausführen, sondern vorläufig zurückstellen wollen?

Statt des Aufrufs kapseln wir alle zum Aufruf benötigten Informationen in einer Datenklasse "DelayedCall" (verzögerter Aufruf):

class DelayedCall(object):
def __init__(self,func,*args,**kw):
self.func, self.args, self.kw = func, args, kw

Auch wenn Sie den Konstruktor ("__init__") von DelayedCall in Python nicht gleich verstehen, ist es ganz einfach, was hier getan wird. Eine beliebige Anzahl übergebener Argumente wird als Liste gespeichert in "self.args". Benamte Argumente werden als Dictionary (HashMap) in "self.kw" abgelegt.

Der zurückgestellte Aufruf verändert unser Programmfragment wie folgt:

def calc(n):
x = DelayedCall(math.sqrt,n)
return x + 1

Nun hält "x" nicht mehr das Ergebnis eines Wurzelaufrufs, sondern einen zurückgestellten Aufruf! Der Aufruf kann jetzt jederzeit nachgeholt werden via

x.func(*x.args,**x.kw)

Allerdings haben wir jetzt ein neues Problem. Wir können nicht einfach mit "return x + 1" fortfahren. Die Addition arbeitet mit Zahlen und nicht mit einem DelayedCall-Objekt.

Verzögerte Ausführung

Stellen wir doch die Ausführung von Anweisungen nach einem verzögerten Aufruf ebenfalls zurück! Auch das ist ganz einfach: Wir kapseln jetzt die ausstehenden Anweisungen in einer Funktion, die wir "callback" nennen. Als Input verarbeite die Funktion das Ergebnis des zurückgestellten "math.sqrt"-Aufrufs.

def calc(n):
x = DelayedCall(math.sqrt,n)
def callback(x):
return x + 1
return x, callback

Der Ursprungscode für "calc" lässt sich noch erkennen, aber es hat sich einiges verändert. Die Funktion "calc" führt weder den Aufruf, noch die darauf folgenden Anweisungen aus und gibt auch keine Zahl mehr als Ergebnis zurück. Stattdessen gibt "calc" das Objekt mit dem gekapselten Aufrufparametern und eine Funktion namens "callback" zurück. Nun ist es an jemand anderem, (z.B dem Aufrufer von "calc") Aufruf und Ausführung nachzuholen.

callback(x.func(*x.args,**x.kw))

Die Bedeutung von "calc" hat sich vollkommen verändert. Es ist keine Funktion mehr, die eine Wurzel berechnet und das um Eins erhöhte Ergebnis zurück liefert. "calc" ist zum Konstruktor geworden für "Aktionskapseln", die zwar ebendieses tun, aber eben zu einem späteren Zeitpunkt.

Dieses Ablösung dessen, was das "Gesetz des nächsten Befehls" verlangt und was ein Programmierer durch solche Techniken intendiert (beabsichtigt), ist der Grund dafür, warum Programme im imperativen Stil oft so schwer zu durchschauen sind. Man muss erst herausfinden, was der Programmierer da eigentlich treibt, bevor man zur eigentlichen Programmlogik vordringt.

Und noch eines lässt sich an diesem Beispiel sehr schön zeigen: Diese Techniken greifen auf der Code-Ebene und zielen darauf ab, den Kontrollfluss zu manipulieren. Die UML (Unified Modeling Language) ist eigentlich nicht dafür geeignet, solche Details abzubilden. Dabei sind diese Details enorm wichtig, da sie die Code-Ausführung erheblich beeinflussen und damit die Semantik eines Programms verändern.

Kommentare:

Clement Staedtler hat gesagt…

"Was können wir tun, wenn wir den Aufruf (call) "math.sqrt(n)" nicht sofort ausführen, sondern vorläufig zurückstellen wollen?"

n merken und math.sqrt(n) später aufrufen?


Also entweder ich denke nicht weit genug, oder das ist total triviales Zeug kompliziert erklärt. Für was würde man sowas denn im "wahren Leben" einsetzen? Praktisches Beispiel damit ich die Vorteile verstehe? Ich danke!

dh hat gesagt…

Die meisten Programmier-Geeks erfreuen sich an solchen Techniken allein schon deshalb, weil's ein Denken und Strukturieren von Programmen abseits vom Gewohnten ist. Aber diesmal geht es in der Tat tiefer. Das, was ich Ihnen hier gezeigt habe, ist die Grundlage von vielen Techniken in der Programmierung. Das reicht vom Observer Pattern, zur Ereignissteuerung bis hin zum Multi-Tasking.

Wenn Sie sich noch ein paar Tage gedulden, zeige ich Ihnen, wie man mit dieser Technik "kooperatives Multi-Tasking" realisiert. Ihnen ist sicher nicht entgangen, dass sich mit DelayedCall jeder Funktionsaufruf (eben nicht nur math.sqrt) zurückstellen lässt. Ich habe Ihnen also eine generelle Technik erklärt. Ebenso mit callback.

Ich hoffe, Sie werden noch den Nutzen und den Gebrauch verzögerter Aufrufe und verzögerter Ausführung entdecken.

Aaron Müller hat gesagt…

Tolle Technik!
Allerdings weiß ich nicht, ob ich das mit dem verzögerten Aufrufen richtig verstanden habe. "callback(x.func(*x.args,**x.kw))" lässt sich ja nur innerhalb der calc()-Funktion aufrufen, da die callback()-Funktion nur in diesem Codeabschnitt sichtbar ist. Aber der Gedanke war doch, das man die calc()-Funktion an einer komplett anderen Stelle ausführen kann, oder?

Wenn man die Funktion so aufruft:

dc, cb = calc(9)

kann man die Ausführung irgend wo anders auslagern und die callback()-Funktion dort "abfeuern":

print cb(dc.func(*dc.args, **dc.kw))

Oder hab ich da jetzt was ganz falsch verstanden?

dh hat gesagt…

Das haben Sie vollkommen richtig verstanden, lieber Herr Müller. Das ist genau der Gag, dass Sie die callback-Funktion zwar innerhalb von calc, d.h. im lexikalischen Scope von calc definieren, diese Funktion aber als Funktionsobjekt via return "rausgeben". Damit kann callback außerhalb von calc aufgerufen werden. Ein callback-Aufruf arbeitet dennoch im lexikalischen Kontext von calc.