Freitag, Februar 23, 2007

Uniform Syntax

The syntax of a programming language defines (a) valid notational elements for use and (b) rules of their arrangement. By the way, this definition of syntax resembles very much the notion of a protocol. A protocol defines (a) messages and their constituting elements and (b) rules of valid message sequences. In an interactive programming environment (like if you program in Python interactively via the console), you communicate with the programming system according to a protocol; and the protocol is given by the syntax. There is an interesting duality between the notion of a protocol and the notion of syntax.

If you program in Scheme or Lisp, the syntax has a very interesting form: everything you type in in Scheme has to follow the syntactical form of lists. In Scheme and Lisp, lists are notated in the following way:

(first_element second_element third_element ...)

Lists can be nested: any element in a list can be a list. This is almost everything you need to know, in order to write down syntactically correct List/Scheme programms. All you have to take care about is that the number of left parentheses match the number of right parentheses.

The uniform syntax of Scheme and Lisp has very interesting consequences. First, program transformation is very easy. You just have to transform lists into lists. The way you do program transformation in Scheme and Lisp is via macros. Macros are a powerful tool in Scheme and Lisp. That is, why generative programming is something, Lisp and Scheme programmers are used to since decades. Second, since the uniform syntax of lists does not provide any kind of hint, what is actually meant by a list, what it is used for, we can't rely on the syntax alone. The syntax is, so to speak, too primitive. In order to understand what a list means in terms of programming instructions, we have to introduce a sort of second layer of "syntax". Certain conventions in the use of lists have to be introduced. For example, if a "if" symbol is the very first element in a list, we have an if-expression at hand, which expects at least two and at most three further list elements: the second is the test, the third the so called consequent, the (optional) forth the alternate.

The point here is that this second layer of syntax does not break the first layer of syntax, the notational form of lists. In other words, the syntax of Lisp and Scheme does not shape and structure the notational form of programs beyond the form of lists. This explains, why Lisp and Scheme programs are not so easy to read. Human beings are very sensitive on visual shape and form; it helps us easily recognize a pattern. In Scheme and Lisp, you need to look "through" all the parentheses and train your brain on the "hidden" layer of syntax; and that takes some time. It's also an ability that gets quite easily lost if not trained permanently.

So, there is a benefit and a drawback with uniform syntax: you get a powerful transformation system, but you loose readability of your programs.

By the way, if you want to, you can benefit from the power of a uniform form (I don't like to say "syntax" in this context) in your favorite OO language as well. Program your conceptions as classes (your second layer) and enable object configurations solely via constructors (your first layer, the uniform "syntax"). (In Python, it's the "__init__"-Method.) Instantiation would look something like this:

If(And(Equal(Var("a"),Var("b")),LessThan(3,4)),Print("Hello"))

The result is that you get an Abstract Syntax Tree (AST) for free and that you can do program transformations if you like. It's a cool technique for creating a Domain Specific Language (DSL). It puts you somewhat closer to the power of Lisp and Scheme.

I'm -- of course -- not the first, who describes the problems of uniform syntax. You can, for example, read about it in the book from Peter van Roy and Seif Haridi, "Concepts, Techniques, and Models of Computer Programming", MIT Press, 2004, p. 544f.

Mittwoch, Februar 14, 2007

Online-Durchsuchungen

Wissen Sie, welches Thema mich zunehmend ärgert? Die sogenannte Online-Durchsuchung.


Die heimliche Durchsuchung der im Computer eines Beschuldigten gespeicherten Dateien mit Hilfe eines Programms, das ohne Wissen des Betroffenen aufgespielt wurde (verdeckte Online-Durchsuchung), ist nach der Strafprozessordnung unzulässig.


So beginnt die Pressemitteilung (Nr. 17/2007) des Bundesgerichtshofs dazu. Und ich dachte, das Thema wäre damit erledigt. Doch es kocht weiter. Die Politik wird nicht müde, ihrem Wunsch nach Online-Durchsuchungen Gehör zu verschaffen. Natürlich möchte niemand rechtsstaatliche Prinzipien aushebeln. Doch die Online-Durchsuchung scheint ein überaus effizientes Mittel zur Kriminalitätsbekämpfung zu sein. Soll man darauf verzichten? Mit Schrecken muss man dann noch lesen (so z.B. auf Spiegel-Online, "Hacken für jedermann", 12. Feb. 2007), wie leicht ein "normaler" PC ausspioniert ist.

Mich verwundert und ärgert: Warum schreibt eigentlich niemand darüber, wie leicht man eine Online-Durchsuchung ins Leere laufen lassen kann?!

Nur weil ein Rechner am Netz hängt, hat noch lange niemand einen Zugang zu den Daten. Wer nicht gerade fahrlässig Netzlaufwerke freigibt oder ungesichert per WLAN kommuniziert, dem muss man schon anders kommen. Es gilt, ihr oder ihm Passwörter zu entlocken oder ein "Schadprogramm" unterzujubeln. Auch das will nicht so einfach gelingen bei Rechnern, die sich einiger Hilfsprogramme wie Firewall, Viren-Erkennung etc. bedienen. Wer ein paar Verhaltensregeln beherzigt, seine EMails und die Festplatte verschlüsselt, der wird nur sehr schwer angreifbar. Wer zu guter Letzt die Technik der Virtualisierung nutzt, kann gerne einen "Pseudo-Rechner" durchsuchen lassen, bleibt ansonsten unsichtbar und schaut den Behörden schadenfroh bei ihrer "Durchsuchung" zu.

Natürlich, es gibt keine absolute Sicherheit. Trotz Verschlüsselung der Platte, trotz Beachtung einiger Verhaltensregeln, trotz Virtualisierung schafft es vielleicht doch ein "Bundes-Trojaner" auf einen Rechner. Gut, gewonnen. Aber auch dem Weg dahin lassen sich relativ leicht Hürden in den Weg stellen, die kaum zu nehmen sind.

Dienstag, Februar 06, 2007

Kooperatives Multi-Threading

In meinem letzten Posting ging es um zwei Kontrolltechniken der Verzögerung: verzögerter Aufruf und verzögerte Ausführung. Hier möchte ich Ihnen zeigen, was Sie damit machen können. Wir werden kooperatives Mutil-Threading realisieren. Das Beispiel ist in Python programmiert.

Zur Erinnerung: Die zu einem zurückgestellten Aufruf benötigte Information speichern wir in einer Datenklasse "DelayedCall".

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

Bauen wir uns zunächst die Infrastruktur, die wir benötigen, um mehrere zurückgestellte Aufrufe zusammen mit ihren (optionalen) zurückgestellten Ausführungen zu speichern. Wir nennen einen solchen Speicher "Scheduler" und die Speicheroperation "schedule". Gespeicherte Aufruf/Ausführungs-Paare sind vom Scheduler via "next" abrufbar; mit dieser Operation wird das Paar außerdem aus dem Speicher gelöscht. Im Grunde handelt es sich um eine einfache Queue, die nach dem FIFO-Prinzip arbeitet (FIFO = First In First Out). Die Methoden "next" und "__iter__" erfüllen in Python das Iterator-Protokoll, so dass der Scheduler als Iterator z.B. in einem for-Statement eingesetzt werden kann. Wir werden das gleich beim Dispatcher im Einsatz sehen.

class Scheduler(object):

def __init__(self):
self.callList = []

def schedule(self,call,callback=None):
assert isinstance(call,DelayedCall) and \
(callback == None or callable(callback))
self.callList.append((call,callback))

def next(self):
if self.callList == []: raise StopIteration
call, callback = self.callList.pop(0)
return call, callback

def __iter__(self):
return self

Eine weitere Klasse namens "Dispatcher" soll verzögerte Aufrufe ausführen und das Ergebnis eines Aufrufs an die callback-Funktion übergeben, falls ein callback gegeben ist. Die callback-Funktion wird nicht direkt ausgeführt, sondern dem Scheduler übergeben. Der callback reiht sich ein in die Schlange der noch auszuführenden Aufrufe! Der Dispatcher läuft nach "run" so lange, bis ihm der Scheduler keine "Nahrung" mehr bietet.

class Dispatcher(object):

def __init__(self,scheduler):
self.scheduler = scheduler

def run(self):
for call, callback in self.scheduler:
result = call.func(*call.args,**call.kw)
if callback:
self.scheduler.schedule(DelayedCall(callback,result))

Mit Scheduler und Dispatcher haben wir uns im Kern die Funktionalität aufgebaut, die z.B. in einem Betriebssystem steckt, um Multi-Tasking (threads) zu realisieren. Im Folgenden nutzen wir diese Infrastruktur, um uns ein eigenes "kooperatives Multi-Threading"-System zu bauen; "kooperativ" deshalb, weil der Aufgerufene freiwillig die Kontrolle wieder an den Dispatcher/Scheduler zurück gibt, denn zwingen kann man ihn nicht dazu. In Simulatoren und Echtzeit-Systemen werden Sie diese Techniken ebenfalls gebrauchen können.

Nun verzeihen Sie mir, dass mir kein besseres Beispiel eingefallen ist. Eine Player-Klasse implementiert ein mehr oder minder aggressives Wesen, das austeilen (fight) und auch einstecken (take_this) muss. Das Ergebnis eines angezettelten fights wird in "follow_up" via callback nachgehalten.

import random

class Player(object):
def __init__(self,name,aggressiveness,scheduler):
assert 0 <= aggressiveness <= 1
self.name = name
self.aggressiveness = aggressiveness
self.scheduler = scheduler
self.fear = 0
self.action = ["hit","hurt","wounded","punched","scratched","annoyed"]
self.comment = ["Hey, you seem to like it!",
"You Bastard",
"You getting serious",
"Ok, I got enough of that",
"I got the message!",
"Ok, I give up"]

def fight(self,opponent):
action = self.action[int(random.random()*len(self.action))]
print '%s: "%s, you will get %s"' % (self.name, opponent.name, action)
self.scheduler.schedule(\
DelayedCall(opponent.take_this,self,action),\
self.follow_up)

def follow_up(self,result):
self.fear += result
try:
comment = self.comment[int(self.fear)]
except IndexError:
comment = self.comment[-1]
print '%s: "%s"' % (self.name,comment)

def take_this(self,opponent,impact):
self.fear += 1
print '%s: "Ouch! %s, you %s me!"' % (self.name,opponent.name,impact)
if random.random() <= self.aggressiveness:
print '%s: "Hey %s, you will regret this"' % (self.name, opponent.name)
self.scheduler.schedule(DelayedCall(self.fight,opponent))
return self.aggressiveness * 2
return 0

Natürlich ist das Beispiel etwas gekünstelt, es soll einfach nur zeigen, wie die Ideen des letzten Posts zum Einsatz kommen. Bereiten wir für unsere Spieler noch die Bühne, sich zu produzieren:

class Game(object):
def __init__(self):
self.scheduler = Scheduler()
self.dispatcher = Dispatcher(self.scheduler)
self.player1 = Player("Hulk",0.7,self.scheduler)
self.player2 = Player("Hogan",0.5,self.scheduler)

def round(self,attacker,attacked):
attacker.fear = 0
attacked.fear = 0
attacker.fight(attacked)
self.dispatcher.run()

Schauen wir uns einmal das Gehabe zwischen Hulk und Hogan ;-) an. Wir nutzen dazu die Textkonsole in Python:

>>> g.round(g.player1,g.player2)
Hulk: "Hogan, you will get annoyed"
Hogan: "Ouch! Hulk, you annoyed me!"
Hogan: "Hey Hulk, you will regret this"
Hogan: "Hulk, you will get hit"
Hulk: "You Bastard"
Hulk: "Ouch! Hogan, you hit me!"
Hulk: "Hey Hogan, you will regret this"
Hulk: "Hogan, you will get hit"
Hogan: "You getting serious"
Hogan: "Ouch! Hulk, you hit me!"
Hogan: "Hey Hulk, you will regret this"
Hogan: "Hulk, you will get annoyed"
Hulk: "Ok, I got enough of that"
Hulk: "Ouch! Hogan, you annoyed me!"
Hogan: "Ok, I got enough of that"
>>>

Nett, gell? Warum haben wir diesen ganzen Aufwand eigentlich betrieben? Verändern Sie einmal den Dispatcher geringfügig, indem der callback nicht gescheduled, sondern sofort zur Ausführung gebracht wird.

class Dispatcher(object):

def __init__(self,scheduler):
self.scheduler = scheduler

def run(self):
for call, callback in self.scheduler:
result = call.func(*call.args,**call.kw)
if callback:
callback(result)

Plötzlich verhalten sich Hulk und Hogan anders (abgesehen von den Zufallszuteilungen)!

>>> g.round(g.player1,g.player2)
Hulk: "Hogan, you will get hurt"
Hogan: "Ouch! Hulk, you hurt me!"
Hogan: "Hey Hulk, you will regret this"
Hulk: "You Bastard"
Hogan: "Hulk, you will get punched"
Hulk: "Ouch! Hogan, you punched me!"
Hulk: "Hey Hogan, you will regret this"
Hogan: "You getting serious"
Hulk: "Hogan, you will get scratched"
Hogan: "Ouch! Hulk, you scratched me!"
Hogan: "Hey Hulk, you will regret this"
Hulk: "Ok, I got enough of that"
Hogan: "Hulk, you will get hit"
Hulk: "Ouch! Hogan, you hit me!"
Hogan: "Ok, I got enough of that"
>>>

Diese Änderung im Dispatcher zeigt eines ganz deutlich: Wir können die Strategie der Ausführung nun selbst und an zentraler Stelle verändern. Ebenso kann der Scheduler die Strategie der Einreihung und Auslieferung verändern. Z.B. gibt es in Echtzeit-Systemen Vorgänge, die mit höherer Priorität abgearbeitet werden müssen als "normale" Vorgänge. Ein Prioritäten-Scheduler kommt in einem solchen Fall zum Einsatz, der die Priorität eines verzögerten Aufrufs mit berücksichtigt.

Wie Sie sehen: Wir haben das "Gesetz des nächsten Befehls" im übertragenen Sinne "durchbrochen".

Montag, Februar 05, 2007

Countdown: Karl-Steinbuch-Stipendium

Am 9. Februar 2007 ist das Ende der Frist für eine Bewerbung zum Karl-Steinbuch-Stipendium -- ich hatte Leser und Leserinnen meines Blog auf das Stipendium schon einmal hingewiesen. Es fördert Studierende aus Baden Württemberg.

Kurzentschlossene mögen sich also dransetzen. Falls Sie mir Ihren Projektideen hadern, ich helfe Ihnen gerne dabei. Ein paar Anregungen finden Sie ja auch in diesem Blog. Kontaktieren Sie mich einfach!

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.