Sonntag, Dezember 14, 2008

Denken unter 150

184 Puls. Die Zone, in der ich nur noch renne. Kein Gedanke, kein denken -- nur kämpfen. Ich laufe gegen meinen Körper an. Längst bin ich im anaeroben Bereich. Ich kann nicht mehr soviel Sauerstoff in meine Lungen pumpen, wie ihn mein Körper benötigt. Ich spüre regelrecht, wie meine Zellen auf Hochtouren laufend die letzten Energien mobilisieren. Alles schmerzt. Warum tue ich mir diesen Berg eigentlich an? Gleich ist Schluss. Noch 23 Sekunden, die muss ich noch durchhalten, irgendwie.

"Wie lautet die Binärzahl von 197?"

Wie bitte? Die Aufgabe hämmert in meinem Kopf. Noch 18 Sekunden. Ich kann jetzt nicht rechnen. Ich schaue auf die Uhr. Noch 16 Sekunden den Körper durch die Qual treiben. Mein Puls fällt ab. Ich kann das Tempo nicht mehr halten. 197 ist kleiner als 256 und größer als 128. Mehr bekomme ich reflexartig nicht hin. Kämpfen steht im Vordergrund. Bei dem Puls kann ich keinen klaren Gedanken fassen. Wie auch? Ich versuche gerade meinen Körper zu bezwingen, das Limit noch für einen Moment aufrecht zu erhalten. Noch 6 Sekunden. Wie langsam die Zeit vergehen kann. Nicht aufgeben. Noch 4 Sekunden. Ja, gleich -- in meinem Kopf tobt der Wahnsinn. Ich kämpfe mit jedem Gedanken gegen all die Körpersignale an, die nicht mehr in 2 Sekunden, sondern sofort aufhören wollen. Da, 0 Sekunden. Erlösung.

Stoppuhr an!

Wie lange dauert es, bis ich einen "Denkpuls" erreicht habe? Bis sich mein Körper soweit von der Belastung erholt hat, dass mein Hirn wieder bereit für Input ist? Dass es bereit ist für eine Aufgabe? Dass es die Aufgabe lösen kann?

Im Moment geht gar nichts. Ich atme tief und heftig. Spucke auf den Asphalt. Luft. Luft. Ich will nur atmen. In meinen Ohren, überall hämmert der Puls. Aber er fällt. Jetzt ist er unter 176. Denken? Nein. Geht nicht. Ich gehe. Die Schmerzen lassen nach. Der ganze Körper lechzt nach Erholung.

Ab welchem Puls kann ich die Aufgabe lösen? Wie lautet die Binärzahl von 197?

Erste Denkreflexe melden sich. 197 ist größer als 128, hatten wir schon, also haben wir "ganz links" eine 1. Ungerade Zahl, also "ganz rechts" eine 1. Sonst? Achja, 8 Bits reichen.

Mehr geht nicht. Mein Puls fällt. So langsam regelt sich die Atmung wieder ein. 160 Puls. Erste Gedanken raten mir zu einem systematischen Vorgehen. Nächste Bitstelle? 64. Was ergibt 128 plus 64. Es fühlt sich nach weniger als 197 an. Wieviel weniger? Eine einfache Addition. Im Kopf -- derzeit unmöglich. Ich brauche noch etwas Pause.

Ich wage einen neuen Versuch. Puls knapp über 150. 128 plus 64 macht etwas mehr als 180, fehlen noch 8 plus 4, also 12. 192, das könnte sein. Ich habe noch kein Vertrauen in meine Denke. Vieles ist mechanisch abgeleitet. Eine echte Kontrolle im Hirn fehlt. Dafür bin ich noch zu sehr aus der Puste.

Ich spekuliere weiter. 128 plus 64 macht 192. Die 197 war gegeben, bleiben 5 übrig. Eine 1 hatte ich schon für das Ungerade-sein spendiert. Bleiben noch 4 übrig. Ok. Bitmuster "ganz rechts" 101, Bitmuster "ganz link" 11. Ich komme etwas zur Ruhe. Bin kurz vor 140 Puls. Jetzt weiß ich's. Ich habe fünf Bitstellen berechnet, noch drei weitere Bitstellen mit Null fehlen. Ergebnis: 11000101. Uff.

Hätte ich mir eine ernstere Aufgabe gestellt, ich bin mir sicher, erst in einem Bereich von 120 bis 130 Puls wäre eine Problemlösung möglich, mit ersten sinnvollen Gedanken um die 140 abwärts.

Angeregt zu diesem (virtuellen) Experiment hat mich das Buch von Josh Waitzkin: The Art of Learning -- An Inner Journey to Optimal Performance, Free Press, 2007. Er beschreibt in diesem Buch seine Lernerfahrungen als junges Schachgenie und später als Kampfsportler. In beiden Disziplinen ist bzw. war er sehr erfolgreich. Wem weder das Schachspiel noch der Kampfsport fremd sind, der wir seine Freude an diesem Buch haben und es vielleicht genauso wie ich verschlingen. Denn faszinierend sind seine Berichte und Einsichten schon, praktisch und anwendbar sind sie auch. So berichtet er unter anderem davon, wie wichtig der Zusammenhang zwischen körperlicher Fitness und der Fähigkeit zu sehr kurzer geistiger Erholung ist -- um Hochleistungen erbringen zu können, geistige ebenso wie sportliche. Es ist auch ein Weg, um bessere Klausuren schreiben und Prüfungen ablegen zu können.

Das ist die eine Buchempfehlung, die ich zu Weihnachten für Sie habe. Die andere ist ein Buch von John Medina: Brain Rules -- 12 Principles for Surviving and Thriving at Work, Home, and School, Pear Press, 2008. Und da erfahren wir, dass schon ein wenig körperliche Ertüchtigung die geistige Performanz boostet. Das ist Regel Nr. 1. Weitere elf Regeln verraten Ihnen noch mehr darüber, wie unser Gehirn tickert und wie wir gut mit ihm umgehen können. Selbst wenn Sie sich für das Buch nicht weiter interessieren, besuchen Sie die Webseite zu den Brain Rules -- es lohnt sich.

Montag, November 17, 2008

Syntax und Semantik

Was ist Syntax, was ist Semantik? Diese zwei Begriffe beschäftigen mich immer wieder, siehe zum Beispiel auch "Uniform Syntax" (23. Feb. 2007). Beide Begriffe spielen eine entscheidende Rolle bei jeder Art von maschinell-verarbeitbarer Sprache. Vom Dritten im Bunde, der Pragmatik, will ich an dieser Stelle ganz absehen.

Die Syntax bezieht sich auf die Form und die Struktur von Zeichen in einer Sprache, ohne auf die Bedeutung der verwendeten Zeichen in den Formen und Strukturen einzugehen. Syntaktisch korrekte Ausdrücke werden auch als "wohlgeformt" (well-formed) bezeichnet.

Die Semantik befasst sich mit der Bedeutung syntaktisch korrekter Zeichenfolgen einer Sprache. Im Zusammenhang mit Programmiersprachen bedeutet Semantik die Beschreibung des Verhaltens, das mit einer Interpretation (Auslegung) eines syntaktisch korrekten Ausdrucks verbunden ist.

[Die obigen Begriffserläuterungen sind angelehnt an das Buch von Kenneth Slonneger und Barry L. Kurtz: Formal Syntax and Semantics of Programming Languages -- A Laboratory Based Approach, Addison-Wesley, 1995, Kapitel 1.]

Die Grenze zwischen Syntax und Semantik ist fließend und lässt sich schön am Beispiel mit Hilfe regulärer Ausdrücke erläutern. Spezifizieren wir eine Syntax für die Angabe der Uhrzeit. Gemeint sind minutengenaue Zeitangaben im 24-Stunden-Format.

Ein einfacher regulärer Ausdruck beschreibt die Syntax sehr direkt: "\d\d:\d\d" -- dieser Ausdruck kam schon in der Einführung "Reguläre Ausdrücke" zur Anwendung und ist dort ausführlich beschrieben. Dieser reguläre Ausdruck ist zu allgemein, denn die Angabe "14:72" wäre genauso möglich wie "25:13". Das sind keine Uhrzeitangaben. Ein regulärer Ausdruck, der nur gültige, 4-stellige Zeitangaben erlaubt, ist "([01]\d)|(2[0-3]):[0-5]\d".

Worauf es mir hier ankommt, ist Folgendes: Der erste reguläre Ausdruck spezifiziert eine Uhrzeitsyntax, die so allgemein gefasst ist, dass eine Nachverarbeitung (Teil der Semantik(!)) prüfen muss, ob die Kombination von Stunden und Minutenangaben eine gültige Uhrzeit ist. Der zweite reguläre Ausdruck hingegen erfasst gültige, vierstellige Uhrzeitangaben vollständig syntaktisch. Jegliche Weiterverarbeitung, sprich jegliche Semantik kann sich darauf verlassen, mit ausschließlich gültigen Uhrzeitangaben zu arbeiten.

Wir beobachten an diesem Beispiel, dass es einen Spielraum gibt, was Syntax und was Semantik in einer Sprache ist. Je allgemeiner die Syntax, desto mehr Form- und Strukturwissen muss als Teil der Semantik behandelt werden. Je spezifischer die Syntax ist, desto weniger muss sich die Semantik um eine Erkennung bemühen. Im Idealfall ist die Semantik von aller Klärung befreit, wenn die Syntax eindeutig ist.

Im Fall der Uhrzeit ist es relativ leicht möglich, Uhrzeitangaben vollständig syntaktisch zu spezifizieren. Das geht nicht immer. Nehmen wir Datumsangaben. Eine vollständige syntaktische Spezifikation, welche Monate 30 bzw. 31 Tage haben, ist noch machbar -- ob sie sinnvoll ist, ist die Frage. Denn spätestens für den Monat Februar ist mit regulären Ausdrücken nicht mehr entscheidbar, ob 28 oder 29 Tage die korrekte Angabe sind. Es sind 29 Tage, sofern das Jahr ein Schaltjahr, also durch 4 teilbar ist. Es bleibt jedoch bei 28 Tagen, wenn die Jahreszahl durch 100 teilbar ist, nicht jedoch durch 400. Eine Datumsangabe kann nicht vollständig syntaktisch erkannt werden -- es sei denn, die Syntax hätte Rechenfähigkeiten.

Und damit sind wir genau an dem Punkt angelangt, was Syntax von Semantik unterscheidet: Syntax ist der Anteil einer Sprachdefinition, der gültige Zeichenfolgen einer Sprache erkennt (Form- und Strukturerkennung) und zwar mit einem Formalismus, der keine Rechenfähigkeit hat, sprich, der nicht Turing-äquivalent ist. Dieser syntaktische Anteil liefert die Vorverarbeitung. (In der Theorie der formalen Sprachen sind damit reguläre (Typ-3) bzw. kontextfreie (Typ-2) Grammatiken gemeint, siehe Chomsky-Hierarchie.). Die Semantik betrifft alle weitere Symbol-Verarbeitung, die mit einem Formalismus beschrieben ist, der Turing-äquivalent ist.

Mit diesem Verständnis von Syntax und Semantik kann man sinnvoll den Begriff der syntaktischen Obergrenze definieren: Die syntaktische Obergrenze reizt die Form- und Strukturerkennung aus und minimiert den semantischen Anteil, der eventuell notwendig ist, um die Erkennung von Formen und Strukturen eindeutig zu machen. Zum Beispiel beschreibt ein regulärer Ausdruck die syntaktische Obergrenze für eine Datumsangabe im Format "Tag-Monat-Jahr" (TT-MM-JJJJ), wenn semantisch einzig die Tagesangabe für den Februar überprüft werden muss. Das Muster "\d\d-\d\d-\d\d\d\d" liegt offensichtlich nicht an der syntaktischen Obergrenze. Der Semantik-Anteil muss umfangreiche Gültigkeitsprüfungen vornehmen.

Man kann in diesem konkreten Beispiel auch auf einen Formalismus für die Syntax zurückgreifen, der zwar Rechenfähigkeiten hat, in seinem Verarbeitungshorizont jedoch strikt begrenzt ist. Dann liegt eine kontextsensitive Grammatik vor (Typ-1). Kontextsensitive Grammatiken sind eher die Ausnahme. (Anmerkung: Grundsätzlich ist auch ein Formalismus für die Syntax denkbar, der Turing-äquivalent ist (Typ-0), allerdings fällt dann die Grenzziehung zwischen Syntax und Semantik schwer. Ein anderes Kriterium muss dann gefunden werden.)

Meine These ist, dass diese Zerlegung einer Verarbeitung in einen Anteil, der aus einem nicht Turing-äquivalenten Mechanismus und einem Turing-äquivalenten Mechanismus besteht, ein stets wiederkehrendes Thema in der Informatik ist. Pipe-Filter-Architekturen sind ein Beispiel, die Zerlegung eines Programms in Interfaces und Verhalten ein anderes. Interessanterweise habe ich bislang keinen Hinweis darauf gefunden, dass dieses Zerlegungsmuster bereits von jemand anderem postuliert worden wäre. Ich glaube, man könnte dieses Zerlegungsmuster sehr viel systematischer in der Software-Entwicklung einsetzen.

Ein Anmerkung, siehe im vorletzten Absatz, ist hinzu gekommen, um die Diskussion etwas abzurunden. (2008-11-18)

Dienstag, November 04, 2008

Studieren mit der PS3


Ungefähr 1000 PS3-Spielkonsolen dürften in etwa der Rechenleistung unseres Gehirns gleichkommen. Vielleicht ist das eine gewagte Schätzung, so ganz seriös sind solche Computer/Hirn-Vergleiche nie. Aber wer als "Niko" Bellic in die Welt von GTA IV eintaucht, dem wird diese Zahl vermutlich gar nicht so abwegig vorkommen. Es ist unglaublich, wieviel Welt so eine Spielkonsole simulieren kann.

In der PS3 leistet ein Spezialprozessor, der Cell-Chip, diese beachtliche Arbeit. Ein etwa 10 Jahre altes Rechenzentrum im Schachtelformat. Mehrere Einheiten arbeiten parallel und fressen Zahlen, was das Zeug hält.

Es hat eine ganz eigene Faszination, wenn man Linux auf die PS3 installiert und sich die Konsole zum ersten Mal meldet. Man hat Kontakt mit dieser geballten Rechenkraft aufgenommen. Plötzlich gehorcht sie einem aufs Wort. Und irgendwie hört man die Maschine nach Arbeit rufen. Das bisschen Linux, die paar Befehle, die über die Konsole reinwandern, die machen so ein Maschinchen nicht müde. Da steht ein Apparat, der es gewohnt ist, Sie durch Häuserschluchten zu jagen, Ihnen Aliens aufzuhetzen, Sie unter Beschuss zu nehmen und Ihnen wilde Verfolgungsjagden zu liefern. Diese Maschine hat Hunger! Diese Maschine sucht die Herausforderung und die Auseinandersetzung!

Nehmen Sie die Herausforderung an?

Geben Sie der Maschine Futter, programmieren Sie die PS3 selbst! Jagen Sie die PS3 mit Ihren Programmen an den Rand des Machbaren! Fangen Sie da an, wo der PC schlapp macht!

Einen Start bietet Ihnen unsere Webseite http://ps3.hs-heilbronn.de.

Montag, Oktober 27, 2008

Einladung in die Schreibbar

Daran kommt keine Studentin und kein Student vorbei: am Verfassen einer wissenschaftlichen Arbeit. Früher gab es (in den technisch orientierten Fächern) die Studien- und die Diplomarbeit, jetzt ist eine Bachelor oder Master Thesis zu schreiben. Seinerzeit hatte man die Chance, sich mit der Studienarbeit auf die Diplomarbeit vorzubereiten. Die Studienarbeit war so etwas wie eine Fahrschule zum wissenschaftliche Arbeiten und Schreiben. Jetzt geht es mit der Bachelor oder Master Thesis relativ unvorbereitet auf die Wissenschaftspiste. Plötzlich muss man alles beherrschen: das Zitieren, das Referenzieren, das Gliedern, Schreiben, Bewerten, Recherchieren etc. Es macht es nicht einfacher, dass man für eine Bachelor Thesis nicht gerade viel Zeit hat.

In der Schreibbar, "da werden Sie geholfen"! Die Schreibbar möchte das erste deutschsprachige Blog sein, das das wissenschaftliche Arbeiten zum Thema hat und Studierenden dabei Hilfestellung und Anleitung bietet. Die Schreibbar hat einen gewissen Fokus auf technisch-orientierte Fächer, aber sie wird in ihrem Themenspektrum sicher vielen Studierenden eine Hilfe sein.

Schauen Sie doch einfach mal vorbei. Meine Mitstreiterinnen und ich, wir würden uns auf Ihren Besuch freuen.

Link: schreibbar.wordpress.com

Montag, Oktober 20, 2008

Reguläre Ausdrücke

Eine typische Aufgabenstellung, mit der sich ein Software-Entwickler bzw. eine Software-Entwicklerin immer wieder konfrontiert sieht, ist die Verarbeitung von Textdateien. In der Regel interessiert die Verarbeitung von Textdateien oder Zeichenströmen, die von Maschinen für Maschinen gedacht sind. Solche Textdateien folgen klaren, eindeutigen Regeln des Aufbaus. Sonst ist die maschinelle Verarbeitung eher schwierig bis unmöglich.

Bei der Verarbeitung von Textdateien bzw. Zeichenströmen kommt man an regulären Ausdrücken (regular expressions) nicht vorbei. Mit ihnen kann man Zeichenfolgen in einem Text suchen und weiter verarbeiten. Reguläre Ausdrücke stehen in praktisch jeder Programmiersprache als nachladbare Bibliothek zur Verfügung (so z.B. in Java) oder sie sind bereits fester Bestandteil der Sprache (wie z.B. in Perl oder JavaScript). Jeder moderne Texteditor erlaubt die Suche nach Zeichenketten mit Hilfe von regulären Ausdrücken.

Reguläre Ausdrücke selbst sind Zeichenketten (strings). Die in dem String verwendeten Zeichen folgen bestimmten Vereinbarungen (Konventionen). Zum Beispiel steht die Zeichenfolge "\d" in einem regulären Ausdruck nicht für die Folge der Zeichen "\" und "d". Der Backslash "\" ist ein sogenanntes escape symbol. Die normale Bedeutung des Zeichens "\" als Backslash wird ausgehebelt. Zusammen mit dem "d" bekommt es eine Sonderfunktion. Die Zeichen "\d" stehen für eine beliebige Ziffer (digit) von 0 bis 9. Gleichwertig dazu ist der reguläre Ausdruck "[0-9]". In der Tat ist "\d" nicht mehr als eine Kurzform für "[0-9]". Die eckigen Klammer haben ebenso wie der Backslash eine Sonderbedeutung. Die zwischen den eckigen Klammern gelisteten Zeichen stellen Alternativen dar. Ein "[012]" steht entweder für eine "0" oder eine "1" oder eine "2". Ein Digit ist also ein "[0123456789]". Die von/bis-Notation "[0-9]" verkürzt den Schreibaufwand.

Und was ist, wenn man die Sonderbedeutung von "\", "[" bzw. "]" aufheben möchte? Dann kommt wieder das Escape-Zeichen, der Backslash, zum Einsatz. Ein "\\" meint genau das Zeichen "\". Und ein "\[" bzw. "\]" schaltet die Sonderbedeutung der eckigen Klammern aus und meint nun ausdrücklich die Zeichen "[" und "]".

Nachfolgende ist eine kurze Einführung in die Arbeit mit regulären Ausdrücken in der Programmiersprache Python gegeben. Diese Einführung ist weder vollständig noch umfassend. Ziel ist, Ihnen die Einstiegshürde zu nehmen.

In Python werden reguläre Ausdrücke über eine Bibliothek (ein Modul) zur Verfügung gestellt.

>>> import re

Ist die Suche nach einem Muster erfolgreich, liefert das re-Modul ein "Muster erkannt"-Objekt zurück. Schlägt die Suche fehl, wird None als Wert ausgeliefert.

>>> re.search("ll","hello")
<_sre.SRE_Match object at 0x00B8DBB8>
>>> re.search("ll","hexxo")
>>> re.search("ll","hexxo") == None
True

Neben der search-Methode steht auch eine match-Methode zur Verfügung. Ein Match erwartet im Gegensatz zum Search eine Passung des regulären Ausdrucks mit dem Anfang des übergebenen Strings. Bei Search wird im gesamten String nach dem Muster gefahndet.

>>> re.search("ll","hello")
<_sre.SRE_Match object at 0x00B8DB80>
>>> re.match("ll","hello")

Zur effizienten Verarbeitung können reguläre Ausdrücke intern compiliert werden. Das macht vor allem dann Sinn, wenn ein Muster mehrfach zum Einsatz kommt.

>>> hhmmRE = re.compile("\d\d:\d\d")
>>> hhmmRE
<_sre.SRE_Pattern object at 0x00B24870>
>>> hhmm = hhmmRE.search("It's 14:00!")
>>> hhmm
<_sre.SRE_Match object at 0x00B8DC28>

Match-Objekte bieten eine Reihe von Methoden an. Man kann z.B. den zum Muster passenden String erfragen oder sich die Position des Muster-Treffers im String angeben lassen.

>>> hhmm.group()
'14:00'
>>> hhmm.start()
5
>>> hhmm.end()
10
>>> hhmm.string
"It's 14:00!"
>>> hhmm.string[hhmm.start():hhmm.end()]
'14:00'

Teile eines regulären Ausdrucks können in Gruppen strukturiert werden. Auf die einzelnen Teile kann dann über das Match-Objekt zugegriffen werden. Angenommen, wir wollen die Stunden und die Minuten einer Uhrzeitangabe separat erfassen. Runde Klammern in einem regulären Ausdruck markieren Gruppen, die von 1 an aufsteigend durchgezählt werden.

Zusätzlich verbessern wir unser Suchmuster dahingehend, dass auch Uhrzeiten mit einstelliger Stundenangabe (z.B. 7:00 Uhr) erkannt werden. Ein Fragezeichen markiert als Sondersymbol die Optionalität des voranstehenden Zeichens. Ein "\d?" steht für einen Digit, der optional ist.

>>> hhmmRE = re.compile("(\d?\d):(\d\d)")
>>> hhmm = hhmmRE.search("Let's meet at 2:00 pm.")
>>> hhmm
<_sre.SRE_Match object at 0x00B97578>
>>> hhmm.group(1)
'2'
>>> hhmm.group(2)
'00'

Gruppen können auch mit sprechenden Namen assoziiert werden, was aus software-technischer Sicht zu empfehlen ist. Beim Durchzählen von Gruppen kann sich ein Programmierer oder eine Programmiererin leicht verzählen. Referenzbezüge mit sprechenden Namen sind weniger fehleranfällig.

Eine benamte Gruppe wird mit "(?P<name>...)" markiert.

>>> hhmmRE = re.compile("(?P<hh>\d?\d):(?P<mm>\d\d)")
>>> hhmm = hhmmRE.search("Let's meet at 13:45.")
>>> hhmm.group("hh")
'13'
>>> hhmm.group("mm")
'45'

Soweit der Einstieg mit Python. Es gibt noch eine Menge zu regulären Ausdrücken zu entdecken. Sie sind ein leistungsfähiges Werkzeug bei der Verarbeitung von Strings.

Es lohnt nicht unbedingt, sich ein Buch zu regulären Ausdrücken zuzulegen, auch wenn es zu diesem Thema exzellente Werke gibt. Einen raschen Überblick zur Historie und zum theoretischen Hintergrund liefern Ihnen beispielsweise der deutsche und der englische Wikipedia-Eintrag. Dort finden Sie auch etliche hilfreiche Weblinks. Im "Tagesgeschäft" sollte die Dokumentation zu den regulären Ausdrücken in der von Ihnen verwendeten Programmiersprache vollends ausreichen.

Samstag, September 27, 2008

Zuweisung, Verzögerung, Rekursion - alles Lambda, oder was?!

Es mag Spaß machen, einigermaßen komplexe Programme in eine einzige, unleserliche Zeile zu stopfen. In der Programmiersprache Perl sind die "one-liners" ja beinahe Kult.

Von geradezu didaktischem Wert ist die Konstruktion von Einzeilern für Python von Dan Piponi. Bei ihm lernt man, was die Mächtigkeit von Lambda-Ausdrücken ausmacht. Zuweisung, Verzögerung, Rekursion -- das alles kann man leicht mit Lambdas ausdrücken. Mit ihrer Hilfe kann man sich beliebige Einzeiler basteln, siehe "On writing Python one-liners".

Nicht, dass ich Sie zu Einzeilern ermutigen möchte. Aber Lambda-Ausdrücke sollte jeder Programmierer kennen. Sie sind die Wunderwaffe der funktionalen Programmierer!

Dienstag, September 23, 2008

Objekt-orientierte Parser-Kombinatoren in Python

Ich möchte Ihnen eine Technik zur Syntaxanalyse vorstellen, die zwar gar nicht so neu ist, aber immer wieder Aufmerksamkeit erregt. Zum Beispiel in der Smalltalk-Gemeinde durch einen Beitrag von Gilad Bracha zu Newspeak ("Executable Grammars in Newspeak"). In der Haskell-Welt machen Parser-Kombinatoren und die Forschung zu ihnen immer wieder von sich reden, siehe z.B. aktuell "Parser Combinators for Ambiguous Left-Recursive Grammars" von R.A. Frost, R. Hafiz und P. Callaghan, PADL 2008.

Im Folgenden setze ich voraus, dass Sie wissen, was ein Parser ist und Ihnen auch die EBNF zur Darstellung von Grammatiken bekannt ist. Wenn wir weiter unten von einer Parser-Funktion reden, dann meinen wir eine Funktion, die einen String entgegennimmt, diesen parst und ein geeignetes Ergebnis der Parse-Analyse zurückgibt.

Der Begriff des Kombinators kommt aus der Ecke der funktionalen Programmiersprachen. Ein Kombinator ist eine Funktion höherer Ordnung, eine Higher-Order Function (HOF), die selbst eine Funktion zurückgibt. Eine HOF ist eine Funktion, die Funktionen als Argumente entgegennimmt und gegebenenfalls eine Funktion zurückgibt. Von einem Kombinator wird dann gesprochen, wenn die HOF syntaktisch als Infix notiert werden kann. Anschaulich: Statt der bei Funktionen verbreiteten Prefix-Notation combinatorX(functionA,functionB) steht in der Infix-Notation der Kombinator in der Mitte: functionA combinatorX functionB. Damit wird hervorgehoben, dass der Kombinator, ähnlich einem Operator wie etwa "+", zwei Funktionen "kombiniert".

Ein Parser-Kombinator verknüpft Parser-Funktionen und liefert selber eine Parser-Funktion zurück. Nehmen wir an, wir haben eine Parser-Funktion token(), die Token erkennt. Angenommen, der Parser-Kombinator für Sequenzen oder Folgen von Parser-Funktionen kann mit einem Komma "," notiert werden. So lässt sich dann sehr kompakt ein Parser ausdrücken, der zwei Token-Parser als Sequenz kombiniert: token("Hell"),token("o"). Mit dieser Schreibweise kann die Struktur einer EBNF-Beschreibung einer Grammatik direkt als Kombination von Parser-Funktionen ausgedrückt werden. Die Funktionen bilden die Struktur einer EBNF-Beschreibung nach ("function follows form").

Da der Parser-Kombinator selber wieder ein Parser ist, können wir ihn mit einem String aufrufen: (token("Gut"),token("en"))("Guten Tag!")

In vielen Programmiersprachen ist es nicht so ohne weiteres möglich, die Syntax zur Schreibweise von Funktionen zu ändern. Eine Infix-Notation verbietet sich meist. So bleibt einem nur, Parser-Kombinatoren in der nicht ganz so eleganten Prefix-Notation zu nutzen. Ein sehr schönes Beispiel, wie man mit Python Parser-Kombinatoren bauen kann, liefert ein Autor namens "Stefan" (Kürzel "sma") im deutschen Python-Forum in dem Beitrag "Kleine Parser-Kombinator-Bibliothek" (16. Feb. 2008, 16:31). Wenn Sie diesen Beitrag lesen, werden Sie das Folgende besser verstehen.

Will man einen Parser-Kombinator konsequent objekt-orientiert anlegen, dann wird die Idee der Kombination von Parser-Funktionen abgelöst durch eine Kombination von Parser-Objekten, die wieder ein Parser-Objekt statt einer Parser-Funktion liefern. Die Kombination von Objekten, die wieder ein Objekt zurückliefern ist sehr elegant und einfach realisierbar durch Konstruktor-Methoden.

Werden wir konkret. Mit den folgenden zwei Parser-Klassen führen wir einen Token-Parser bzw. einen Parser für reguläre Ausdrücke ein. In Python kann man Objekte aufrufbar (callable) machen, indem man sie mit einer __call__-Methode ausstattet. Ein Objekt wird damit gleichermaßen zu einer "zustandsbehafteten Funktion". Die __repr__-Methode dient zur Überschreibung der standardmäßigen Selbstrepräsentation eines Objekts, vergleichbar mit der "toString"-Methode in anderen Sprachen.

import re, types

class Parser(object): pass

class Token(Parser):
def __init__(self,token,annotation=None):
self.token, self.annotation = token, annotation
assert isinstance(annotation,types.StringType) or annotation == None
def __call__(self,text):
if text.startswith(self.token):
return Node(self,self.token), text[len(self.token):]
return None, text
def __repr__(self):
return "Token('" + str(self.token) + "')"

class RegExp(Parser):
def __init__(self,regexp,annotation=None):
self.regexp, self.annotation = re.compile(regexp), annotation
assert isinstance(annotation,types.StringType) or annotation == None
def __call__(self,text):
match = self.regexp.match(text)
if match: return Node(self,match.group()),text[match.end():]
return None, text
def __repr__(self):
return "RegExp(" + str(self.regexp.pattern) + ")"

Schauen wir uns einmal den Gebrauch der Token-Klasse über die Kommandozeile an:

>>> Token("Hey")
Token('Hey')
>>> Token("Hey")("Hey!")
(Hey, '!')
>>> Token("Hey")("Heu")
(None, 'Heu')
>>>

Der Token-Parser liefert immer ein Tupel zurück. Der erste Teil des Tupels ist None, wenn der Parser nicht erfolgreich ist. Bei Erfolg wird ein Knoten-Objekt zurückgegeben. Der zweite Teil des Tupels ist der String-Anteil, den es noch zu parsen gilt. Bei Erfolg ist es der Rest-String (hier "!"), bei Misserfolg der gesamte übergebene String ("Heu").

Hier, der Vollständigkeit halber, der Code zu Node, den Sie der Parser-Klasse voranstellen müssen:

class Node(object):
def __init__(self,parser,result):
self.parser = parser
self.result = result
def __repr__(self): # reconstruct the parsed input
if self.result == None: return ""
if isinstance(self.result,types.TupleType):
assert all([isinstance(e,Node) for e in self.result])
return "".join([str(element) for element in self.result])
return str(self.result)

Nun wird es interessant. Kommen wir zu den Kombinatoren der Parser-Objekte um Sequenzen bzw. Alternativen abzubilden:

class NaryOperator(Parser):
def __init__(self,annotation="",*parsers):
assert all([isinstance(parser,Parser) for parser in parsers])
assert isinstance(annotation,types.StringType)
self.parsers, self.annotation = parsers, annotation

class Sequence(NaryOperator):
def __init__(self,annotation,*parsers):
NaryOperator.__init__(self,annotation,*parsers)
assert len(self.parsers) >= 1
def __call__(self,text):
results = ()
text_ = text
for parser in self.parsers:
node, text_ = parser(text_)
if not node: return None, text
results += (node,)
assert len(results) == len(self.parsers)
return Node(self,results), text_
def __repr__(self):
return "("+",".join([str(parser) for parser in self.parsers])+")"

class Alternative(NaryOperator):
def __init__(self,annotation,*parsers):
NaryOperator.__init__(self,annotation,*parsers)
assert len(self.parsers) >= 1
def __call__(self,text):
for parser in self.parsers:
node, text_ = parser(text)
if node: return Node(self,node), text_
return None, text
def __repr__(self):
return "("+"|".join([str(parser) for parser in self.parsers])+")"

Sie sehen, dass ich die Annotation von Parser-Objekten erlaube, womit später die Verarbeitung des erzeugten Parsebaums vereinfacht wird. Das soll hier aber nicht unser Thema sein. Schauen wir uns den Gebrauch der Parser-Kombinatoren an:

>>> s = Sequence("",Token("Gut"),Token("en"))
>>> s
(Token('Gut'),Token('en'))
>>> s("Guten Tag!")
(Guten, ' Tag!')
>>> s("Was ein Tag!")
(None, 'Was ein Tag!')
>>> a = Alternative("",Token("Gut"),Token("en"))
>>> a
(Token('Gut')|Token('en'))
>>> a("Guten Tag!")
(Gut, 'en Tag!')
>>> a("Tag!")
(None, 'Tag!')

Parser-Kombinatoren sind also tatsächlich selbst wiederum Parser -- genau so soll es sein!

Lassen Sie uns noch ein paar einwertige Parser-Kombinatoren hinzufügen, damit wir alles zusammen haben, um eine Grammatik vollständig beschreiben zu können:

class UnaryOperator(Parser):
def __init__(self,parser,annotation=None):
assert isinstance(parser,Parser)
assert isinstance(annotation,types.StringType) or annotation == None
self.parser, self.annotation = parser, annotation

class Optional(UnaryOperator):
def __call__(self,text):
node, text = self.parser(text)
if node: return Node(self,node), text
return Node(self,None), text
def __repr__(self):
return str(self.parser) + "?"

class ZeroOrMore(UnaryOperator):
def __call__(self,text):
results = ()
while True:
node, text = self.parser(text)
if not node: break
results += (node,)
return Node(self,results), text
def __repr__(self):
return str(self.parser) + "*"

class OneOrMore(UnaryOperator):
def __call__(self,text):
results = ()
text_ = text
while True:
node, text_ = self.parser(text_)
if not node: break
results += (node,)
if results == (): return None, text
return Node(self,results), text_
def __repr__(self):
return str(self.parser) + "+"

Ein Konsolenbeispiel zu OneOrMore:

>>> OneOrMore(Token('a'))('aaabbbccc')
(aaa, 'bbbccc')
>>> OneOrMore(Token('a'))('bbbccc')
(None, 'bbbccc')

Wir sind fast am Ziel! Wenn Sie eine Grammatik aufschreiben, in der es rekursive Bezüge gibt, werden Sie auf ein Problem stoßen. Probieren Sie mal Folgendes:

group = Sequence("group",Token("{"),doc,Token("}"))
config = Sequence("config",Token("["),doc,Token("]"))
comment = Sequence("comment",RegExp(r'%.*\n'))

doc = ZeroOrMore(Alternative("doc",comment,config,group))

Sie können nicht in "group" auf "doc" verweisen, bevor Sie "doc" eingeführt haben! Würden Sie die Regel von "doc" dem "group" voranstellen, hätten Sie dasselbe Problem, nur anders herum.

Eine Lösung ist, eine Delay-Klasse einzuführen, mit der Sie ein Parser-Objekt anlegen und seine "Logik" per set-Methode nachrüsten. In einer OO-Umgebung ist das eine sehr einfache Lösung, in einer funktionalen Programmierumgebung müssten Sie sich etwas anderes einfallen lassen.

class Delay(Parser):
def set(self,parser,annotation=None):
assert isinstance(parser,Parser)
assert isinstance(annotation,types.StringType) or annotation == None
self.parser = parser
self.annotation = annotation
def __call__(self,text):
return self.parser(text)
def __repr__(self):
if self.parser.annotation:
return "{"+ str(self.parser.annotation) + "}"
return "{" + self.parser.__class__.__name__ + "}"

Nun können wir die aus dem letzten Post vorgestellte einfache Grammatik für LateX ("Eine einfache Grammatik für LaTeX") mit unserem objekt-orientierten Parser-Kombinator beschreiben und mit ihr arbeiten:

doc = Delay()

text = RegExp(r"[^\\\{\}\[\]%]+","text")

group = Sequence("group",Token("{"),doc,Token("}"))
config = Sequence("config",Token("["),doc,Token("]"))
comment = Sequence("comment",RegExp(r'%.*\n'))

commandToken = RegExp(r"\\\\?[^\\\{\}\[\]%\s]*","commandToken")

commandConfig = Sequence("commandConfig",Optional(comment),config)
commandGroup = Sequence("commandGroup" ,Optional(comment),group)

command = Sequence("command",
commandToken,
Optional(commandConfig,"head"),
ZeroOrMore(commandGroup,"tail"))

doc.set(ZeroOrMore(Alternative("doc",command,comment,config,group,text)))

Ein erster Härtetest einer jeden Grammatik ist, ob der geparste Input als Output wieder erzeugt werden kann. Wenn Sie Spaß daran haben, probieren Sie es einmal mit einem LaTeX-File.

(Eine Anmerkung am Rande: Die Konstruktortechnik, hier zur Kombination von Parser-Objekten verwendet, habe ich schon einmal kurz erwähnt in dem Blogbeitrag "Uniform Syntax")

Donnerstag, September 18, 2008

Eine einfache Grammatik für LaTeX

Informatiker schreiben ihre Artikel, Berichte und Arbeiten natürlich mit TeX bzw. mit LaTeX -- sonst gehört man einfach irgendwie nicht dazu ;-) Es gibt unzählige Erweiterungen (im LaTeX-Slang "packages" genannt), die ebenso unzählige Features und Gimmicks nachrüsten für so ziemlich jedes Problem, das man sich vorstellen kann.

Für die Überarbeitung eines Artikels hatte mir der Verlag die Auflage gemacht, alle Änderungen zur vorigen Version hervorzuheben. In Microsoft Word ein Klacks, in LaTeX zugegebenermaßen ein Umstand. Aber mit \usepackage{changes} steht einem glücklicherweise ein Paket zur Verfügung, das an dieser Stelle aushilft. So übersäte ich mein LaTeX-Dokument mit \added{...}, \deleted{...} und \replaced{...}{...}.

Für eine erneute Überarbeitung wollte ich nun die vielen Änderungsauszeichnungen aus dem LaTeX-Dokument entfernen und zwar so, dass die Änderungen selbst im Text zurückbleiben. Natürlich automatisch und nicht per Hand. Das heißt, etwas vereinfacht gesagt: In dem LaTeX-Dokument können die \deleted{...}-Auszeichner samt Inhalt einfach verschwinden, von einem \added{...} muss der Inhalt in der geschweiften Klammerung erhalten bleiben, von einem \replaced{...}{...} nur der Inhalt der ersten geschweiften Klammerung.

Diese kleine Herausforderung ist ein fast klassisches Informatik-Problem. Die Anwendung von regulären Ausdrücken für einfache Ersetzungen funktioniert in LaTeX nicht, da LaTeX-Auszeichner verschachtelt sein können und somit das schließende Ende zu einer geöffneten geschweiften Klammer "{" nicht zuverlässig gefunden werden kann. Also muss man das LaTeX-Dokument parsen. Da TeX seine Grammatik zur Laufzeit ändern kann, ist auch das im Prinzip ein hoffnungsloses Unterfangen -- doch ganz so schlimm ist es in der Realität erfreulicherweise nicht. Für 99.99% aller LaTeX-Dokumente kommt ein sehr regelmäßiges Schema zum Tragen. Nur findet man dazu wenig im Netz.

Ich habe mir einen Parser in Python geschrieben (einen "Parser Combinator"), mit dem ich mit einigen einfachen Grammatiken für LaTeX-Dokumente experimentiert habe. Hier das Ergebnis, das mir für meine Zwecke gereicht hat:

text := RegExp(r"[^\\\{\}\[\]%]+")

group := "{" doc "}"
config := "[" doc "]"
comment := RegExp(r'%.*\n')

commandToken := RegExp(r"\\\\?[^\\\{\}\[\]%\s]*")

commandConfig := comment? config
commandGroup := comment? group

command := commandToken commandConfig? commandGroup*

doc := ( command | comment | config | group | text )*

Ein kleiner Hinweis: Der reguläre Ausdruck für "text" schließt alle die Zeichen aus, die bei "group", "config" und "comment" eine Sonderrolle haben. Auf diese Weise holt sich der Parser mit "text" immer möglichst zusammenhängende Textblöcke rein, ohne jedoch die Trigger "\[]{}%" für die anderen Regeln zu überlaufen.

Wenn Sie also mal in der Verlegenheit sind, eine Nachverarbeitung für LaTeX-Dokumente vornehmen zu müssen, so mag Ihnen diese einfache Grammatik den Einstieg möglicherweise erleichtern.

Sollte ich einmal Zeit dazu haben, dann erkläre ich Ihnen, wie man sich in einer objekt-orientierten Sprache einen Parser Combinator schreibt. Das geht erstaunlich einfach.

Sonntag, September 07, 2008

Add-ons for Chrome - or - A new architecture for browsers

On September 2nd, on Tuesday, Google released Chrome -- their own web browser. Chrome has a simple, unobtrusive user interface, it's based on WebKit, it's powered by a new JavaScript implementation, it runs a process for each new tab, and it promises a new approach to safe browsing. On this one, Chrome failed. Chrome has some severe security holes Google needs to fix. Nonetheless, I like the new browser.

Some hours after Google had released Chrome, I read a lot of comments about the Chrome experience. Most users seemed to be quite enthusiastic, some few were not. But one sort of comments caught my attention: Some folks argued that Firefox users will stay with Firefox. Why? Because of all these nice add-ons you can extend Firefox with.

My spontaneous reaction was: Who needs add-ons?

Before you laugh at me. I run Firefox with extensions like Firebug, Web Developer, ScrapBook and others. I use them extensively and like them a lot. Who wants to miss Firebug, for instance? Nobody, right?! I wouldn't use a browser without my beloved add-ons. And one is for sure. A browser without extension capabilities won't make it in the long run. (Ok, I'm not sooo sure.)

So what made me think "Who needs add-ons"?

I contemplated some time over my spontaneous reaction. Forgive me, I don't know much about how to write extensions for Firefix. I am an extension user, not an extension programmer. But my gut feeling tells me that the approach to extensions in Firefox is wrong. It's the worst Google could do to copy the extension mechanism of Firefox. I should rephrase my first reaction: "Who needs such an add-on architecture?"

Instead of criticizing Firefox's extension mechanism, of which I don't know much about, let me sketch an alternative approach to extensions.

Assume a "naked" browser: no buttons to click on, no url field, no menu, nothing. Assume that all the browser does after startup is run a JavaScript program. Let's call this program the "Controller". The key point is: You can change the Controller. Don't like the default Controller? Change it. The Controller is under your control!

The default Controller is a JavaScript program that creates buttons to click on and implements a history of web pages visited. It provides the url input field and displays suggestions while you type. It lets you have menus and so on.

Got it? The Controller is a program that creates a user interface that mimics Firefox. Or Chrome. Or IE. Or Opera. Or Safari. Whatever you want.

If you type in a url in the url field and hit enter, it's the Controller, which -- so to speak -- creates an IFrame and loads the given web page into that frame. So the web page remains fully under control of the Controller.

It does not require that much imagination to see that the Controller can easily be extended by -- right, by extensions or add-ons. These extensions are just other JavaScript programs, which are plugged into the Controller.

To oversimplify things, I envision a browser, which consists only of an HTML and CSS rendering engine and a virtual machine running JavaScript. The rest is initiated by an ordinary JavaScript program using web technology. In other words: My favorite browser is fully programmable with web technology.

The idea is simple, isn't it? It thrills me.

The development of such a "naked" browser inevitably raises questions like:

  • How do we guarantee that the Controller doesn't loose control?

  • How do we compose add-ons? How do we avoid interference of add-ons?

  • Do we need a component architecture? Or do we need a service-oriented architecture?

  • How do we ensure safe browsing and secure execution?


It's much about architecture thinking and a JavaScript implementation that supports fundamental notions of modularization, safety and security. These are aspects which should IMHO drive the standardization activities of JavaScript. Implementors of browsers should radically rethink the way browsers are built and function. Google did a first, tiny step in that direction with Chrome. But there's more to strive for.

Mittwoch, September 03, 2008

Multi-Stage Programming in Scheme

Vor nicht allzu langer Zeit habe ich mich in einem Beitrag mit "Multi-Stage Programming" (MSP) beschäftigt. Ich warf in dem Blog-Posting die Frage auf, ob MSP im Grunde nicht mit der Makroprogrammierung wie z.B. in Scheme oder Lisp vergleichbar sei.

In der Tat kann das MetaOCaml-Beispiel, die Auflösung der Power-Funktion, sehr leicht mit defmacro, dem Urmakro aus Lisp, in Scheme nachgebildet werden. Hier kommt PLT-Scheme zum Einsatz -- mit Dank an Tim für den Code:

(require (lib "defmacro.ss"))
; POWER MACRO
(define-macro power
(lambda (n x)
(if (= n 0)
'1
`(* ,x (power ,(- n 1) ,x)))))
(power 2 4)

Stellt man dem Code in PLT-Scheme noch ein

(require (lib "../macro-debugger/expand.ss"))

voran und gibt dann interaktiv ein

(expand/step '(power 2 2))

ein, dann öffnet sich ein Fenster zum schrittweisen Makroauflösen. Ich habe ein wenig mit den Check-Boxen experimentiert: Mit "Enable macro hiding?" und "Hide mzscheme syntax" sieht die Auflösung unkryptisch aus.

Nun lese ich die Tage von Oleg Kiselyov etwas über "MetaScheme, or untyped MetaOCaml". In seinem Beitrag implementiert er "the four MetaOCaml special forms -- bracket, escape, cross-stage persistence (aka `lift'), and run -- in R5RS Scheme." Er argumentiert, dass eine 1:1-Übersetzung der MetaOCaml Special Forms in Scheme ("MetaOCaml's bracket is like quasiquote, escape is like unquote, and `run' is eval") nicht zum gewünschten Ergebnis führt. Vor allem übersieht Scheme die Bindungsstrukturen, die MetaOCaml natürlich sauber berücksichtigt.

Kiselyov bietet die MetaOCaml Special Forms als Macros für R5RS an, die nun dasselbe Verhalten zeigen wie die Special Forms in MetaOCaml. Eine beeindruckende Lösung, die -- wie alles bei Kiselyov -- ein tiefes Verständnis für Scheme aufweist. Sie verrät aber auch, wie MSP implementiert werden kann.

Eine Einsicht bleibt dennoch: Macros sind der Fast Track zu MSP in Scheme bzw. Lisp -- ohne Netz und doppelten Boden.

Dienstag, September 02, 2008

Browsing aufpoliert: Google Chrome

Firefox, Opera, Safari, Internet Explorer -- die großen "Player" im Browser-Markt versuchen sich immer wieder an neuen, oft kleinen Features, die das Surfen im Internet angenehmer, komfortabler, sicherer und vielleicht auch ein wenig spaßiger gestalten sollen. Jüngst stellte Microsoft seinen neuen Internet Explorer 8 in der Beta-Version vor.

Seit gestern ist es semi-offiziell. Google möchte heute der Welt einen eigenen und etwas anderen Browser bescheren: Google Chrome ("A fresh take on the browser", 1. Sep. 2008). Man scheint es sehr ernst zu nehmen. Ein unterhaltsames Comic soll den Anwender bzw. die Anwenderin vom Vorteil und Nutzen des aufpolierten Browser-Modells überzeugen: "Google Chrome: Behind the Open Source Browser Project".

Technisch hat man das Browser-Modell auf neue Beine gestellt. Mehrere Webseiten lassen sich, wie gehabt, über Tabs gleichzeitig öffnen und organisieren. Doch nun stellt jeder Tab einen eigenen Prozess dar, was echte Parallelität liefert. So blockiert eine "hängende" Seite in einem Tab nicht die Arbeit des ganzen Browsers und damit der anderen Tab-Seiten. Erstaunlich, dass es zu diesem Mehr-Prozess-Fundament des Engagements von Google bedurfte. Doch scheint dieses Feature zusammen mit der neuen JavaScript-Engine namens V8 in der Techie-Szene bereits Begeisterung hervorzurufen (John Resig: "Google Chrome Process Manager"). Selbstredend ist auch Google Gears in Google Chrome integriert. Und Chrome soll open-source sein!

Ich bin gespannt -- und warte schon auf den Link zum Download! Bis dahin: Haben auch Sie viel Spaß an der Vorfreude mit dem Comic.

[[Update: Zwei Tipps zu Chrome. Der Browser verrät einige Interna durch sogenannte "about"-Seiten, siehe "Google Chrome's about:Pages". Ein paar Bedienhinweise liefert "Google Chrome Tips".]]

Dienstag, August 26, 2008

Zu den Ursprüngen: Das Internet

Ich weiß nicht, ob Sie auch zu den Freaks gehören, die gerne technische Standards lesen und sich immer mal wieder auf den RFC-Seiten der IETF, der Internet Engineering Task Force, wiederfinden. Manche mögen die technischen Sachverhalte, die in den "Request for Comments" (RFCs) dargelegt sind, für langweilig halten. Ich finde sie spannend. Man lernt eine Menge über das Internet. Wie es funktioniert, welche Ideen es angeleitet und getrieben haben und welche Konzepte und Ideen den einzelnen Netzschichten und Protokollen zugrunde liegen. Eine Unmenge an interessanten Informationen findet sich da, frei verfügbar und für jeden zugreifbar. Ein Wissen, das nicht unbedingt in den Lehrbüchern zu den "Rechnernetzen" oder "Web-Technologien" zu finden ist.

Via Ehrensenf (Sendung vom 26. August) bin ich auf eine wunderbare Webseite der National Science Foundation (NSF) gestoßen. Auf der Seite "NSF and the Birth of the Internet" setzen sich die Amerikaner medial sehr gelungen als Erfinder und Pioniere des Internets in Szene und erzählen seine Geschichte. Eine Geschichte mit Menschen zum "Anfassen", ein Zurückblättern in eine Welt, in der es noch keine Blogs, Chats, ICQs, EMails, Internet-Telefonie und all das gab. Unvorstellbar, nicht wahr?

Vielleicht können Sie nach dem Besuch der NSF-Seite nachvollziehen, warum ein Blättern und Lesen in den alten RFCs aus den 80ern so aufregend und spannend sein kann. Leider lassen die jüngeren RFCs einiges an Qualität und Brillanz vermissen, die noch die "alten" RFCs auszeichnete.

Freitag, August 15, 2008

Multi-Stage Programming

Neben den Programmiersprachen gibt es eine Vielzahl von verschiedenen Techniken und Ansätzen des Gebrauchs, des Einsatzes, der Verwendung und der Erweiterung von Programmiersprachen. Alle diese Techniken bzw. Ansätze enden auf "Programming": Generative Programming, Aspect-Oriented Programming, Object-Oriented Programming, Context-Oriented Programming, Subject-Oriented Programming -- es gibt unzählige solcher Bezeichnungen. Hinter den meisten dieser Namen stecken interessante Ansätze, die auf nur wenigen Konzepten oder Ideen beruhen.

In den vergangenen Tagen habe ich mich mit "Multi-Stage Programming" (MSP) beschäftigt. Dieser Blog-Beitrag ist eine Aufbereitung des Papers "A Gentle Introduction to Multi-Stage Programming" von Walid Taha. Das Paper ist auf seiner Publikationsseite zu finden. Alle Zitate und Code-Beispiele stammen aus dem Paper.

Ich bitte um Nachsicht und um Korrekturen, sollten sich in der folgenden Darstellung des Papers von Taha Fehler finden. Ich bin kein MSP-Experte und bringe dazu auch keine hands on-Erfahrung mit. Auch über klärende Kommentare freue ich mich, insbesondere, was den Vergleich mit Makros angeht.

---

Multi-Stage Programming (MSP) ist eine besondere Form der generativen Programmierung und damit eine Technik der Meta-Programmierung. Zwei Gedanken führen zum MSP: (1) Programmgenerierung bringt einige Probleme mit sich, die in der Generierungsproblematik selber liegen, die also inhärent sind. (2) Es gibt wenig Unterstützung für die Erstellung von Generatoren in Hochsprachen wie Java oder C.

MSP ist der Ansatz mit einer Sprache zu arbeiten, die ausdrücklich zur Generierung von Programmen in ihrer eigenen Sprache geeignet ist und die die mit der Programmgenerierung verbundenen Probleme vermeidet.

Was sind die Probleme?

Man kann Programme in Textform mit Strings generieren. Das Problem: Man kann Programme konstruieren, die syntaktisch ungültig sind.

Eine andere Option ist, ein Programme durch Datentypen zu kodieren, z.B. mit einem abstrakten Syntaxbaum (AST). Es werden immer syntaktisch korrekte Programme zurück geliefert. Das Problem: Datentypen können zwar syntaktische korrekte Programme garantieren, nicht aber, ob diese auch well-typed sind.

MSP nimmt sich dieser Problematik an: MSP stellt sicher, dass ein generiertes Programm syntaktisch korrekt und well-typed ist. Darüber hinaus verhindert MSP Namenskonflikte und unbeabsichtigte Variablenübernahmen. Das klingt gut, besonders, wenn man mit statisch typisierten Sprachen arbeiten möchte.

Drei Basiskonzepte für MSP in MetaOCaml

MetaOCaml ist eine Erweiterung zu OCaml für MSP. Lediglich drei Konzepte werden in der Sprachwelt von OCaml mit MetaOCaml verankert mit denen eine typkonforme Manipulation von Programmfragmenten in OCaml möglich ist.

Brackets ".< >." können einen Ausdruck (expression) umgeben. Sie verzögern seine Ausführung. Brackets konservieren einen Ausdruck als Code-Fragment zur späteren Berechnung (= Compilierung und Ausführung), im Beispiel ".<1+2>.":

# let a = 1+2;;
val a : int = 3
# let a = .<1+2>.;;
val a : int code = .<1+2>.

Neben der Verzögerung weiß ein Bracket um den Typen, den ein geklammerter Ausdruck im Falle der Ausführung zurück gibt. Oben kann man sehen, wie "int code" als Typ auf der Kommandozeile ausgegeben wird. Die Typen "int code" und "int" sind unterschiedlich und lassen sich nicht mixen. Ein "1 + .<5>." ist nicht erlaubt.

Mit einem Escape ".~" können verzögerte Ausdrücke zu neuen verzögerten Ausdrücken komponiert werden. Das "a" bezieht sich aus dem vorangegangenen Beispiel.

# let b = .<.~a * .~a >. ;;
val b : int code = .<(1 + 2) * (1 + 2)>.


Schlussendlich wird mit einem Run ".!" ein verzögerter Ausdruck compiliert und ausgeführt:

# let c = .! b;;
val c : int = 9

Eine Funktion, die Brackets und Escapes enthält (anscheinend auch Annotationen genannt), wird als staged bezeichnet; eine normale Funktion ohne Annotationen als "unstaged". Mit den Annotationen kann die Reihenfolge der Ausführung (evaluation order) explizit spezifiziert werden.

That's it! So einfach sich das anhört, aber gerade die eingebaute Typsicherheit bringt es mit sich, dass man in der Tat nur gültige Programme aus verzögerten Ausdrücken komponieren kann. Für dynamisch typisierte Sprachen wäre das nicht möglich. Mit MSP kann man Staged Interpreters bauen. Sie gelten als ebenso einfach zu bauen wie "normale" Interpreter, sind aber nahezu so effizient wie Compiler.

The primary goal of MSP is to help the programmer reduce the runtime overhead of sophisticated abstraction mechanisms.


Staged Programms = Programming with Makros?

Es schleicht sich allmählich der Verdacht ein, dass es sich bei Bracket, Escape und Run lediglich um ein Makrosystem handelt, das darauf achtet, typkonforme Konstrukte zu erzeugen. Trifft dieses Mapping auf Lisp zu, wenn man mal von der Typisierung absieht? Bracket = Quote, Escape = Makrodefinition, Run = Makroauflösung?

Ein Beispiel, das diese Beobachtung stützt findet sich in Kapitel 2.2 "A Classic Example". Die Power-Funktion x^n löst sich auf in die n-fache Anwendung der Multiplikation von x. x^3 liefert also x*x*x. Das kann in einer rein funktionalen Programmiersprache nur iterativ ausgedrückt werden. In MetaOCaml sieht das wie folgt aus:

let rec power (n, x) =
match n with
0 -> 1 | n -> x * (power (n-1, x));;

Nehmen wir an, wir machen häufig Gebrauch von der Quadratfunktion power2:

let power2 (x) = power (2,x);;

Oder alternativ in etwas anderer Ausdrucksweise, die wir unten wieder verwenden werden:

let power2 = fun x -> power (2,x);;

Ärgerlich ist der Overhead, das bei jeder Quadrierung der parametrisierte Aufruf power(2,x) eine Rekursion ausführt. Das führt zu Performanzverlusten. Günstiger wäre es, power2 iterationslos auf "x*x" abzubilden. Annotieren wir power(n,x) entsprechend, dann kann man diese Auflösung forcieren:

let rec power (n, x) =
match n with
0 -> .<1>. | n -> .<.~x * .~(power (n-1, x))>.;;

Damit hat sich aber auch der Typ des zweiten Arguments (x) verändert: Hier muss ein Code vom Typ Integer übergeben werden, z.B. .<3>., so dass power (2,.<3>.) aufgelöst wird zu:

.< .<3>. * .<3>. * .<1>. >.

Das ist auch der Grund, warum der match-Fall für 0 abgebildet wird auf .<1>. und nicht 1, so sonst die Multiplikation nicht mehr konform Typen vom Typ "code of type int" verkettet.

Folglich kann nun power2 definiert werden über eine staged function:

let power2 = .! . .~(power (2,..))>.;;

power2 erzeugt eine verzögerte Funktion mit x als Eingabeparameter. Bereits zur Compilezeit wird über das Escape ein Aufruf der Funktion power vorgenommen (so verstehe ich das zumindest), wobei x via .. typmäßig angepasst wird. Der Aufruf von power liefert ein verzögertes x*x*1 zurück. Das Run .! erlaubt dem Compiler auch diesen Code gleich weiter zu übersetzen, so als ob er direkt x*x*1 übersetzt hätte.

Das Ergebnis ist also, dass wir über das power-"Makro", Code generieren konnten, der so effizient ist wie handgeschriebener Code für power2.

In Kapitel 3 "Implementing DSLs Using Staged Intepreters" demonstriert Taha, wie man mit stage programming eine DSL umsetzen kann, die im Stil eines Interpreters geschrieben wird, durch Staging jedoch soviel wie möglich zur Compilezeit erledigt. Im Endeffekt soll damit zur Ausführungszeit der DSL eine Performanz erreicht werden, die der Performanz entspricht, hätte man einen Compiler für die DSL geschrieben. Natürlich ist mit einem Compiler als Zielsprache die Implementierungssprache gemeint, mit der auf der staged Interpreter geschrieben wird. Ansonsten ist der Vergleich natürlich absurd. So heißt es bei Taha:

A staged interpreter is a translator

Das Paper demonstriert an einer sehr simplen DSL den Bau eines Staged Interpreters, und merkt dann an: "... further reserach is need [Schreibfehler im Original] to show that we can apply MSP to realistic programming languages.". Das heißt: Wir müssen noch lernen, unserer MSP strukturiert in verschiedenen Themenbereichen einzusetzen.

Montag, August 11, 2008

Der Computer als "verlängertes" Hirn

Schließen Sie die Augen! Konzentrieren Sie sich! Gehen Sie in Gedanken durch das Zimmer oder den Raum, in dem Sie sich gerade befinden. Beginnen Sie, vor Ihrem geistigen Auge die Möbel umzuräumen. Wie wäre es mit ein paar Pflanzen in der Ecke? Bekommen sie dort genug Licht? Lassen Sie die Morgensonne durch das Fenster scheinen. Dann die Mittags- und zu guter letzt die Abendsonne. Gefällt Ihnen, wie sich die Lichtverhältnisse ändern? Geht es der Pflanze an ihrem Standort gut? Streichen Sie die Tapeten in Gedanken einmal rot, blau oder gelb. Wie wäre es mit grün? Mehr hellgrün oder dunkelgrün?

Ihnen geht es sicher wie mir. Ich bin mit meiner Vorstellungskraft überfordert. Ich kann mein Arbeitszimmer gedanklich zwar irgendwie einfärben, aber willentlich klare Farben aussuchen und diese Szenerie vor dem geistigen Auge so zu betrachten als sei es real -- unmöglich. Wie ich mir Lichteindrücke vorstellen soll, ich habe keine Ahnung.

Prof. Dr. Temple Grandin kann sowas. Sie beschreibt es in ihrem Buch "Thinking in Pictures". Ihr Gedächtnis speichert "Filme". Sie hat die Fähigkeit, sich in ihrer "Filmwelt" dreidimensional zu bewegen und die Welt aus verschiedenen Blickwinkeln zu betrachten. Sie kann auch Änderungen in der Vorstellungswelt vornehmen. Wir dürfen uns das vermutliche wie eine Simulationswelt denken, in der man beliebige Kamerafahrten machen und beliebige Eingriffe durchspielen kann. So eine Art Grand Theft Auto IV im Kopf. Wobei man nicht nur Spieler, sondern auch Spieleentwickler ist. Frau Grandin nutzt ihre Begabung zum Entwurf von Anlagen zur Viehhaltung und -schlachtung.

Es ist beeindruckend, zu welchen Ausnahme-Leistungen unser Gehirn in der Lage ist. Doch der Preis für solche Inselbegabungen scheint hoch zu sein. Temple Grandin ist Autistin. Autismus ist eine Entwicklungsstörung, die die betroffenen Menschen in ihrem Vermögen zu sozialer und kommunikativer Interaktion erheblich einschränkt. Frau Grandin ist insofern eine Ausnahme, als dass sie einen Weg der Kommunikation mit uns Nicht-Autisten gefunden hat.

Doch es geht mir in diesem Beitrag weniger um den Autismus. Als ich das erste Kapitel zu Grandins Buch las, war ich beeindruckt von dieser Fähigkeit. Mit solchen Hirnleistungen kann man Dinge tun und erreichen, die Otto-Normal-Hirn verwehrt sind.

Oder?

Ja, das ist richtig. Aber wir Menschen haben uns ein wunderbares Werkzeug erschaffen, das sozusagen als "verlängertes" Hirn fungieren kann: der Computer. Mit einem Computer können wir Simulationen durchführen. Wir können uns in selbst erschaffenen Welten bewegen, können Autos crashen lassen ohne einem Dummy ein Haar zu krümmen. Wir können das Wetter vorhersagen, die Höhe der Altersrente errechnen, Risikoanalysen durchführen und und und.

Aber nutzen wir dieses Werkzeug eigentlich systematisch?

Haben Sie in Schule, Ausbildung oder Studium jemals mit Simulationen gearbeitet? Haben Ihre Lehrer, Ausbilder oder Dozenten Sie dazu animiert, selber Gedankenexperimente mit dem Rechner auszuführen. Sei es um Häuser an virtuellen Baugruben zu errichten, um zu verstehen, wie ein Staubsauber funktioniert (Wie saugt man Luft an?) und wie es auf Autobahnen zu Staus aus dem Nichts kommen kann. Welche einfachen Regeln erklären die Streifen auf dem Zebra? Haben Sie's mal am Rechner ausprobiert? Heute schon die zu erwartende Projektdauer per Monte-Carlo-Simulation ermittelt?

Der Computer ist ein wunderbares Werkzeug. Jedem von uns steht diese "Hirnprothese" zur Verfügung. Nur nutzen wir sie nicht. Jedenfalls nicht zur Modellierung und Simulation alltäglicher Phänomene. Wir haben's nicht gelernt, den Rechner als Verstehens- und Entscheidungshilfe zu verwenden; haben nicht einmal die richtigen Programme dazu zur Hand und auf dem Rechner installiert. Eigentlich schade.

Montag, August 04, 2008

Im Kampf gegen Monstersysteme


Im Urlaub war es wieder soweit: Das, was wir Informatiker den Menschen um uns herum so zumuten, das machte mir ein fürchterlich schlechtes Gewissen.

Was war geschehen? Eigentlich nichts spektakuläres. Die Vermieterin unserer Ferienwohnung brauchte Hilfe bei der Einrichtung ihres neu erworbenen Laptops. In drei Stunden war der Rechner mit Windows Vista hergerichtet, die neuesten Updates installiert, Flash Player, Adobe Reader, OpenOffice nachgerüstet -- das Übliche halt. Schon dabei wurde mir ganz mulmig.

Und dann, am nächsten Abend, begann ich der guten Frau eine Einführung in Vista zu geben. "Hier klicken, da klicken, gucken Sie mal, alles ganz einfach, dann hier klicken, da klicken. Huch, die Firewall meldet sich. Wissen Sie, was das ist? Nein? Egal, hier klicken, da klicken, dann geht's weiter. Lassen sie sich von sowas nicht irritieren." Was fühlte ich mich elend. "Wenn Sie Ihre Kochrezepte anschauen wollen, hier klicken, da klicken, sehen Sie, OpenOffice startet, dann hier klicken, da klicken. Voilà. Einfach, gell?" Und ich wusste, dass ich log. Nix einfach! Ganz und gar nicht einfach. Da sitzt eine ältere Frau neben mir, die ich in einer Informationsflut ertränkte, die gerade einmal ins Internet möchte, EMails und Briefe schreiben will, vielleicht einmal mit Videotelefonie übers Internet Familienkontakte pflegen möchte und ansonsten an die Archivierung und den Ausbau ihrer Sammlung von Kochrezepten denkt.

Wozu muss so jemand ein komplexes Betriebssystem erlernen? Was belästigen wir die Menschen mit der Nachfrage zu Software-Updates? Welche Arten von Entscheidungen verlangt da eigentlich eine Firewall? Warum muss Otto-Normal-Verbraucher erst einen VHS-Kurs zu OpenOffice machen, bevor er oder sie sich einigermaßen in den Büro-Programmen zurechtfindet?

Warum in aller Welt sind unsere Betriebssysteme, Browser und Anwendungen so kompliziert?

Wir sind's selber schuld! Wir erschaffen wahre Monster, derer wir selber nicht mehr Herr sind. Auf dem "Workshop on Self Sustaining Systems (S3) 2008" am Hasso-Plattner-Institut (HPI) illustrierte Ian Piumarta Mitte Mai als Invited Speaker die Komplexität heutiger Systeme anhand folgender Zahlen: Windows Vista besteht seinen Angaben zufolge aus 50 Millionen Zeilen Programmcode, Mac OSX aus 86 Millionen Zeilen, OpenOffice aus 10 Millionen Zeilen Code (Links zum Foliensatz und zum Talk "Late-bound Object Lambda Architectures" als Video). Solche Systeme sind allein ihrer schieren Größe wegen von einem Entwickler bzw. einer Entwicklerin nicht mehr überschau- und verstehbar. Kein Wunder, das ein BugFixing das nächste jagt und manche Probleme oder Fehler über Monate, wenn nicht gar Jahre, im System bleiben, obwohl sie bekannt sind.

Kann es sein, dass wir den Bau solcher Systeme grundlegend falsch angehen? Piumarta glaubt, dass das alles viel einfacher geht, gehen muss, dass es auch mit 20.000 Zeilen Code möglich sein muss, eine Umgebung auf einem Rechner zu erstellen, die all das abdeckt, was moderne Betriebssysteme bereitstellen. Mit 20.000 Zeilen Code ist eine Größe erreicht, die einem 400 Seiten-Buch entspricht. Ein Umfang, der von einem Menschen in wenigen Wochen vollständig erfassbar und verdaubar ist.

Ich glaube, dass Piumarta mehr als Recht mit seinem Anliegen hat. Die Systeme, die wir heutzutage bauen, sind zu komplex. Es geht einfacher, es muss einfacher gehen. Piumarta selbst liefert in seinem Vortrag einige Beispiele dazu. Wir müssen lernen Systeme zu bauen, die einfach und klein im Kern sind, damit einfach verstehbar sind, und skalieren. Erst damit schaffen wir die Grundlage für Systeme, die vielleicht irgendwann auch einmal einfach bedienbar sind und sich zuschneiden lassen auf die Bedürfnisse ganz spezieller Nutzergruppen.

Wer sich für solche Überlegungen interessiert, dem sei der oben verlinkte Vortrag ans Herz gelegt. Über das zugrunde liegende Objektsystem habe ich schon einmal berichtet im Beitrag "'Open, reusable object models' in Python". Mehr an solchen radikalen Überlegungen lassen sich beim Viewpoint Research Institute unter "Fundamental New Computer Technologies" finden. Geistiger Urheber vieler dieser Gedanken ist übrigens Alan Kay, ein Urgestein der Informatik.

Hinweis: Monster-Bild von Kaptain Kobold

Donnerstag, Juli 10, 2008

Typen in Wandlung: Das Paar, die Liste und der Stack

Ich habe meinen lieben HardCore-Informatik-Leser(inne)n schon lange keinen Programmcode mehr als Denkspur hinterlassen. Heute ist es mal wieder soweit. Zwei Punkte haben mich umgetrieben: (1) Die Fähigkeit von Objekten, ihren Typ zu verändern. (2) Der Vergleich von Liste und Stack.

Es wird ein langes Posting werden, aber vielleicht haben Sie Lust auf diese kleine Denk-Reise. Ein wenig setze ich voraus, dass Sie sich mit Scheme/Lisp und dort mit den Datentypen der Liste und des Paars auskennen. Und was ein Stack ist, wissen Sie als Informatiker sowieso.

Einleitung

Ein einfaches Beispiel mag die Idee von einem Objekt veranschaulichen, das seinen Typ ändern kann: Eine Ellipse ist beispielsweise über die Größe der Hauptachse und die Größe der Nebenachse eindeutig definiert. Sind Haupt- und Nebenachse gleich groß, dann haben wir einen Kreis, und die Unterscheidung in Haupt- und Nebenachse wird hinfällig; es genügt die Angabe eines Wertes, des Radius'. So kann ein sich veränderndes Ellipsen-Objekt zum Kreis-Objekt werden.

Nachfolgend möchte ich anhand der Datenstrukturen von Liste und Paar (beide bilden die Grundlage der Programmiersprache Scheme) zeigen, dass die Typbestimmung und -anpassung zur Laufzeit eine reizvolle Technik ist, die elegant mit Objekt-Orientierung umgesetzt werden kann. In Scheme wird die Liste wie auch das Paar mit ein- und derselben Grundoperation erzeugt, der cons-Operation. Einzig und allein die Verwendung einer leeren Liste an einer bestimmten Stelle im Konstruktor entscheidet, ob das resultierende Objekt eine Liste oder ein Paar ist.

Es zeigt sich aber auch ein schwerwiegendes Problem: Die OO-Lösung koppelt die Typen (Liste und Paar) in der Vererbungshierarchie über den Typen der leeren Liste miteinander. Das macht es andererseits unmöglich, die Liste wie einen Stack zu benutzen. Und das, obwohl Liste und Stack praktisch identisch sind. Ohne die Kopplung wäre das eine triviale Anpassung.

Die dynamische Typauflösung verträgt sich nicht mit der Konstruktion eines durchgehenden objekt-orientierten Typsystems. Ich frage mich, ob diese Kopplung von Liste, Paar und leerer Liste nicht zwangsläufig zu Problemen im Typsystem führen muss. Handelt es sich hier gar um einen Designfehler in Scheme/Lisp? [Anbei: Ich würde mich freuen, Gedanken und Hinweise von Typ-Experten zu bekommen.]

Bevor die Anwendung des Codes die Sachverhalte demonstrieren soll, bietet es
sich an, den Python-Code durchzugehen.

Programmcode: EmptyList, Cons, Pair, List

Die Codezeilen für __repr__ blasen den Code ein wenig auf. Ansonsten ist der Code schlank, er trägt alle Konzepte (EmptyList, List und Pair) explizit vor und nutzt Vererbung, um die Gemeinsamkeiten von List und Pair via Shared klar hervorzuheben. Die Klasse Cons dient dazu, die Typfestlegung erst durch den Gebrauch einer EmptyList() am "Ende" der Konstruktion via Cons möglich zu machen. Der Typ wird also, wenn man so möchte, dynamisch angepasst.

Es sei bereits an dieser Stelle darauf hingewiesen, dass der Code für List und Pair zwar wunderbar symmetrisch aussieht, es im Kern aber nicht ist. List und EmptyList bilden eine Allianz gegen Pair, obwohl List und Pair als gleichberechtigte Partner in der Vererbungshierarchie auftauchen. Diese Asymmetrie ist für die Unmöglichkeit verantwortlich, warum List nicht mit Stack überein gebracht werden kann. Wir kommen darauf noch zurück.


class EmptyList(object):
def is_empty(self): return type(self) == EmptyList
def __repr__(self): return "()"

class Cons(object):
def __new__(cls,car,cdr):
if type(cdr) in (List,EmptyList): return List(car,cdr)
return Pair(car,cdr)

class Shared(EmptyList):
def __init__(self,car,cdr):
self._car, self._cdr = car, cdr
def car(self): return self._car
def cdr(self): return self._cdr
def __repr__(self):
return "(%s %s" % (self._car,self._cdr.__repr__()[1:])

class List(Shared):
def __init__(self,car,cdr):
assert type(cdr) in (List,EmptyList)
Shared.__init__(self,car,cdr)
def __repr__(self):
if type(self._cdr) != List: # => type is EmptyList
return "(%s)" % self._car
return Shared.__repr__(self)

class Pair(Shared):
def __init__(self,car,cdr):
assert type(cdr) not in (List, EmptyList)
Shared.__init__(self,car,cdr)
def __repr__(self):
if type(self._cdr) != Pair:
return "(%s . %s)" % (self._car, self._cdr)
return Shared.__repr__(self)


Programmcode: EmptyStack und Stack

Vergleicht man den Aufbau des Stack mit dem der Liste, so fällt die absolute
Gleichheit ins Auge. EmptyStack entspricht EmptyList, Stack entspricht List.
Ich habe den Stack natürlich nicht ohne Absicht genau der gleichen Bauweise
unterworfen. Es ist lediglich abzugleichen, dass oben bei der Liste via
Shared Vererbung genutzt wird, um die gleichen Anteile von Pair und List
zusammenzufassen.


class EmptyStack(object):
def push(self,element): return Stack(element,self)
def is_empty(self): return type(self) == EmptyStack
def __repr__(self): return "[]"

class Stack(EmptyStack):
def __init__(self,ontop,bottom):
assert type(bottom) in (Stack,EmptyStack)
self.ontop, self.bottom = ontop, bottom
def top(self): return self.ontop
def pop(self): return self.bottom
def __repr__(self):
if type(self.bottom) != Stack: # => type is EmptyStack
return "[%s]" % self.ontop
return "[%s %s" % (self.ontop,self.bottom.__repr__()[1:])


Diskussion

Beginnen wir mit der leeren Liste. Sie können all das in einer interaktiven Python-Console ausprobieren.


>>> EmptyList()
()
>>> EmptyList().is_empty()
True


Paare können direkt erzeugt werden.


>>> Pair(1,2)
(1 . 2)
>>> Pair(1,2).is_empty()
False
>>> Pair(Pair(1,2),Pair(3,4))
((1 . 2) 3 . 4)
>>> Pair(Pair(1,2),Pair(3,4)).car()
(1 . 2)
>>> Pair(Pair(1,2),Pair(3,4)).cdr()
(3 . 4)


Ein Paar darf in seinem cdr keine leere Liste beheimaten -- das Paar würde sonst zur Liste mutieren.


>>> Pair(1,EmptyList())
Traceback (most recent call last):
...
AssertionError


Listen können direkt erzeugt werden. Im Konstruktor wird strikt eingefordert, dass der cdr selbst eine Liste oder eine EmptyList ist.


>>> List(1,2)
Traceback (most recent call last):
...
AssertionError
>>> l1 = List(1,EmptyList())
>>> l1
(1)
>>> l1.is_empty()
False
>>> l2 = List(1,List(2,EmptyList()))
>>> l2
(1 2)
>>> List(l1,List(3,l2))
((1) 3 1 2)
>>> List(3,List(l2,EmptyList()))
(3 (1 2))


Die Klassen List und Pair erzwingen ein vorheriges Festlegen auf einen Typen. Mittels Cons kann in gewohnter Lisp-Manier der Konstruktor bemüht werden. Abhängig vom cdr wird der entsprechende Typ (Liste oder Paar) automatisch erzeugt. Ein Punkt im Ausgabestring gibt wie zuvor an, ob es sich um ein Paar handelt oder nicht.


>>> Cons(1,2)
(1 . 2)
>>> Cons(1,EmptyList())
(1)
>>> Cons(1,Cons(2,Cons(3,EmptyList())))
(1 2 3)
>>> Cons(1,Cons(2,Cons(3,4)))
(1 2 3 . 4)


Car und cdr arbeiten natürlich wie Lisp/Scheme.


>>> Cons(1,2).car()
1
>>> Cons(1,2).cdr()
2
>>> Cons(1,Cons(2,Cons(3,EmptyList()))).car()
1
>>> Cons(1,Cons(2,Cons(3,EmptyList()))).cdr()
(2 3)
>>> Cons(1,Cons(2,Cons(3,EmptyList()))).cdr().car()
2


Kommen wir zum Stack, der -- wenn man möchte -- wie eine Liste aufgesetzt werden kann. Ich habe die Beispiele zur Liste hier übernommen. Ersetzt man gedanklich die vormals runden Klammern durch eckige, dann kommt exakt dasselbe raus. Wen wundert's, da doch der Code praktisch dergleiche ist?!


>>> EmptyStack()
[]
>>> EmptyStack().is_empty()
True
>>> Stack(1,2)
Traceback (most recent call last):
...
AssertionError
>>> s1 = Stack(1,EmptyStack())
>>> s1
[1]
>>> s1.is_empty()
False
>>> s2 = Stack(1,Stack(2,EmptyStack()))
>>> s2
[1 2]
>>> Stack(s1,Stack(3,s2))
[[1] 3 1 2]
>>> Stack(3,Stack(s2,EmptyStack()))
[3 [1 2]]


Der Unterschied zwischen einer Liste und einem Stack besteht jedoch im grundsätzlichen Gebrauch. In Scheme/Lisp kann eine Liste ausschließlich über den Konstruktor cons erzeugt werden (wir lassen set-car! und set-cdr! außen vor, wir bleiben rein funktional).


>>> l = Cons(1,Cons(2,EmptyList()))
>>> l
(1 2)
>>> l.car()
1
>>> l.cdr()
(2)


Ein Stack hingegen wird ausgehend vom EmptyStack über push-Operationen gefüllt.


>>> s = EmptyStack().push(2).push(1)
>>> s
[1 2]
>>> s.top()
1
>>> s.pop()
[2]


Schaut man in die Umsetzung der push-Operation, so verbirgt sie nur den Konstruktor-Aufruf, der im Hintergrund ausgeführt wird.

Im Grunde können die Liste und der Stack als vollkommen gleichwertige Datenstrukturen aufgefasst werden. Für eine Liste gälte es lediglich, eine der Push-Operation entsprechende Methode hinzuzufügen, die man "add" oder besser noch "prefix" nennen könnte. (Das "prefix" scheint mir als Gegenentwurf zu "append" gut zu passen, da die Liste ja sozusagen nach vorne wächst und nicht über Anhängsel erweitert wird.) Den Stack könnte man analog den Aufbau über eine Konstruktor-Funktion erlauben, wie hier schon geschehen. Das sind, wenn man so möchte, Details, die es anzugleichen gilt. Liste gleich Stack, Stack gleich Liste.

Im Scheme/Lisp-Kontext ist das jedoch nicht ganz korrekt. Und das hat mit dem Pair-Typen zu tun. Das Pair bringt einen neuen Twist in die Angelegenheit.

Da bei Pair im cdr jedes beliebige Element stehen kann außer EmptyList und List, verbietet sich die Möglichkeit, von einem Ausgangselement (z.B. der Zahl 7) via push bzw. prefix ein Pair zu konstruieren! Denn das hieße, dass jeder Objekttyp (Zahl, String, Boolean etc.) diese push/prefix-Operation anbieten müsste. EmptyList könnte eine solche Operation für die Konstruktion von Listen anbieten. Dort passt die Operation logisch hin. Aber warum um alles in der Welt sollte eine 7 ein push kennen und realisieren. In OO-Denke hieße das, dass der Typ an der Spitze des Typsystem eine push-Operation anbieten muss, von dem alle anderen Typen erben. Damit wäre allen Objekten im System die Grundmöglichkeit gegeben, sich via push in einen Container namens Pair zu verfrachten. Ein eigenartiges Typsystem wäre das.

Aus dieser Problematik heraus hat man natürlich das push/prefix bei Scheme nicht im Angebot. Der minimalen Asymmetrie im nicht gleichen Umgang mit EmptyList durch Pair und List ist es geschuldet, dass Listen nicht dasselbe Interface wie Stacks anbieten und damit in letzter Konsequenz auch nicht als solche zu gebrauchen sind.

Man sieht die Folgen dieser Konzeption (der asymmetrischen Verschneidung von Listen und Paaren) auch im Python-Code. List und Pair erben von EmptyList über den Zwischenschritt von Shared. Ergo kennen beide die Operation is_empty(). Tatsächlich ist ein is_empty() für Pairs vollkommen überflüssig, da die Anfrage an den falschen Typen adressiert wird. Ein Pair kann niemals empty sein! Genauso wenig, wie eine Zahl jemals empty sein kann.

Ich finde es verwunderlich, dass man bei List, Pair und EmptyList im Grunde kein konsistentes OO-Typgebäude errichten kann, was dem "gefühlten" Zusammenhang von Pair, List und EmptyList gerecht wird _und_ offen bleibt für Erweiterungen.

Montag, Juli 07, 2008

17 Fragen

Marc Scheloske, der Betreiber des Wissenschafts-Cafes, hat mit mir ein Interview geführt. Marc macht diese Interviews seit einiger Zeit mit den unterschiedlichsten Bloggern und stellt seinen Interview-Partnern 17 Fragen. Viel Spaß beim Lesen! Und halten Sie sich mal eine Weile im Wissenschafts-Cafe auf, ich könnte mir vorstellen, dass es Ihnen dort gefällt!

Dienstag, Juni 24, 2008

Komponenten-Orientierung: Service vs. Funktionsbaustein

Wenn man sich mit Komponenten-Orientierung befasst, wird man feststellen, dass es zwei "Schulen" gibt, die etwas unterschiedliche Sichten auf den Komponenten-Begriff haben. Die eine Denkschule hat die Enterprise Applications vor Augen. Bei den Unternehmensanwendungen stehen Themen wie Persistenz, Transaktionen, Verteilung, Webservices etc. im Vordergrund. Im Systems Engieering dominieren hingegen Gesichtspunkte der Modularisierung und Komposition.

Für einen Systems Engieer kann jede Software-Komponente grundsätzlich auch durch einen funktionsgleichen Baustein aus Hardware ersetzt werden -- und umgekehrt. Für Enterprise-Entwickler wird eine Komponente als Software-Einheit gesehen, die vielmehr einen Service realisiert, der zur Erfüllung definierter Aufgaben herangezogen werden kann. Der Systems Engineer baut Systeme, die er aus Komponenten und Subsystemen zusammensetzt. Der Enterprise-Entwickler baut Netze von Mehrwertdiensten, die aus der Kollaboration (möglicherweise transparent verteilter) mehrerer Services entstehen.

So erklärt sich auch, dass in der Enterprise-Welt etwa im Java Kontext die Plain Old Java Objects (POJOs) als Basis für eine Komponente vollauf genügen. Vom Entwickler wird lediglich gefordert, seine POJOs so weit als möglich nur gegen Interfaces zu programmieren. Komponenten-Frameworks wie Spring erledigen dann den Rest. Sie kümmern sich um die Verschaltung von Komponenten, um das Lifecycle-Management und bieten einfache Anbindungen an andere Service-Komponenten, die Persistenz, Zugriffssteuerung etc. ermöglichen.

Systems Engineers benötigen einen konzeptionellen Überbau, wenn Software-Einheiten als Komponenten fungieren sollen. Denn die meisten objekt-orientierten Programmiersprachen bieten keine Komposition an. Objekte lassen sich via Referenzen zwar zu Kollaborationsnetzen verschalten (die Denke der Enterpriseler), nicht jedoch zu Kompositionsbeziehungen. Eine Komponente ist ein Container, der andere Komponenten kapselt und verwaltet. In der Kommunikation zwischen Komponenten arbeiten Systems Engineers typischerweise mit Nachrichten, nicht mit Methoden-Aufrufen. Methoden-Aufrufe sind zu software-spezifisch; Nachrichten taugen in einem Harware- wie auch in einem Software-Umfeld zur Kommunikation. Sie machen alle Kommunikation per se asynchron und frei von impliziten Objekt-Referenzen.

Es ist wichtig, von dieser Unterscheidung zu wissen. Die UML 2 bietet beiden "Schulen" Möglichkeiten zur Modellierung von Komponenten an. Nur kümmert sich die UML nicht darum, den Werkzeugkasten zur Modellierung in die Fächer "Service-Komponenten" und "Komponenten als Funktionsbausteine" zu zerlegen. Darum muss sich der Modellierer selber kümmern.

Mittwoch, Juni 18, 2008

Alles ist ein Eingabegerät

Ich weiß, ich bin spät dran, wenn schon Spiegel-Online darüber berichtet in "Massenmordversuch an der Maus" (Christian Stöcker, 18. Juni 2008). Aber diese Idee ist so schön und abgefahren, das muss man sich ansehen -- ich habe ein Faible für solche Ideen (siehe auch "Sichtweisen in 3D: Balance halten"). Genug der Worte. Nehmen Sie eine Flasche, einen Tacker, einen Stift, Ihren Fingerverband, was auch immer ... oder eine Maus, und legen Sie los:



Ärgern Sie sich auch darüber, weder selbst darauf gekommen zu sein, noch -- falls Sie die Idee hatten -- es umgesetzt zu haben?

Was könnte man damit alles machen? Haben Sie Ideen?

Freitag, Juni 13, 2008

Von der falschen Rede

Eine kleine Anekdote: In der Vorlesung zu den Grundlagen der Informatik sprach ich heute von Rekursion und Iteration. Ich erklärte, was Rekursion ist. Die Studierenden merkten auf und unterbrachen mich: "Sie meinen Rekursion!". "Wie bitte? Habe ich etwas anderes gesagt?" "Ja, sie sagten Iteration." "Oh sorry, ich meinte Rekursion." Da hatte mir mein Hirn einen Streich gespielt, der mir vollkommen unbemerkt blieb. Ich glaubte mich etwas sagen zu hören, was ich nicht gesagt hatte. Kennen Sie das? Haben Sie bestimmt auch schon einmal erlebt.

Also startete ich einen neuen Versuch "Rekursion ist, wenn sich die Funktion selber wieder aufruft." Und schoss die Frage hinterher: "Habe ich Rekursion gesagt?" "Ja", lautete die Antwort unisono.

Während ich weiter sprach, blieben meine Gedanken an der letzten Frage hängen: Irgendwie war die Frage dumm gewesen. Stellen Sie sich einmal vor, das wäre nur mein Gedanke, meine Sprachabsicht gewesen. Tatsächlich hätte ich aber (fälschlicherweise) gesagt: "Iteration ist, wenn sich die Funktion selber wieder aufruft". Und meine Frage wäre mir ebenso falsch über die Lippen gekommen "Habe ich Iteration gesagt?". Dann wäre die Antwort der Studierenden mit "Ja" ebenso korrekt gewesen. Sprich, meine Nachfrage "Habe ich Rekursion gesagt?" war vollkommen unsinnig und überflüssig. Zumindest aus einer logischen Betrachtungsweise. Wenn mein Hirn mir einen Streich spielt und mir meine gedachten Worte unbemerkt mit der Lautbildung eines anderen Wortes über die Lippen kommen, dann bin ich chancenlos. Oder?

In der Tat bin ich das, wenn mein Gehör die Rede anderer ebenso konsistent falsch hört. Die eigene Rede ist davon ausgenommen, da das Ohr bezüglich der eigenen Rede extrem voreingenommen ist. Es weiß ja, was es hören soll -- und das verführt zu einer gewissen Nachlässigkeit. Also muss das Sprechen und das Hören zeitlich entzerrt werden. Ich muss aktiv Feedback einholen. Und solange die Anteile zur Sprachbildung und Spracherkennung nicht über den gleichen Fehler gekoppelt sind, dann sind Abweichungen erkennbar, wenn man das richtige Feedback einfordert.

Wie hätte nach meiner Erläuterung der Rekursion die Nachfrage lauten sollen? Richtig: "Wie nennt man den Prozess des Selbstaufrufs einer Funktion." Die Studis hätten "Rekursion" gesagt und ich hätte eine Chance zur Fehlererkennung gehabt, da mein Sprechen das Wort nicht wieder falsch einbringen konnte.

Die Moral von der Geschicht? Stellen Sie niemals Ja/Nein-Fragen, wenn Sie Ihren Geisteszustand überprüfen wollen. Oder, um den Bezug zum Software Engineering herzustellen: Stellen Sie einem Kunden, wenn Sie z.B. Anforderungen erheben wollen, möglichst keine Ja/Nein-Fragen. Ja/Nein-Fragen erhöhen das Risiko, dass Sie eigene Inkonsistenzen oder ein irrtümliches Verständnis nicht aufdecken.

Dienstag, Mai 27, 2008

Tipps zur Teamarbeit

Ein (Projekt-)Team ist ein Gruppe von Menschen, an die eine Herausforderung oder eine Aufgabe herangetragen wird und von der man die zielgerichtete Bewältigung der Herausforderung erwartet. Oft geschieht das unter Randbedingung wie begrenzten Geldmitteln und Zeitbeschränkungen. Die Teammitglieder sind außerdem gegenseitig voneinander abhängig, um die Herausforderung bewältigen zu können.

Arbeitsteilung und Spezialisierung sind die Wunderwaffen der Teamarbeit. Ein gutes Team bewältigt eine Herausforderung schneller als ein schlechtes Team. Ein gutes Team teilt die Arbeit besser auf und bildet bessere Experten aus als ein schlechtes Team. Ein gutes Team schafft schneller oder mehr. Nachfolgend ein paar Tipps, die Ihnen helfen sollen, gute und effektive Teamarbeit zu leisten.

Definieren Sie eine Teamleitung. Machen Sie eine Person zu Ihrer Teamleitung und übertragen Sie ihr die Verantwortung zur Koordination des Teams. Im Zweifel hat die Teamleitung das Recht Entscheidungen zu treffen, damit eine Handlungsunfähigkeit mangels Entscheidung aufgelöst werden kann. Die Teamleitung trägt die Verantwortung für das Team und damit auch für das Ergebnis.

Nutzen Sie Ihre Stärken -- oder machen Sie sich stark. Teilen Sie sich die Arbeit gemäß den Spezialisierungen im Team auf und/oder nutzen Sie die Arbeitsteilung, um einzelne Personen zu Experten werden zu lassen. Klären Sie, wer welche Kompetenzen und Interessen mitbringt. Nutzen Sie die Stärken und Talente eines jeden Teammitglieds. Oder bauen Sie Stärken auf.

Keine Aufgabe, die nicht zielführend ist. Fragen Sie sich bei jeder Aufgabe, warum diese Aufgabe sein muss. Eine Aufgabe ist dann überflüssig, wenn auch ohne sie ein Erfolg denkbar ist.

Keine Aufgabe ohne ein klar definiertes Ergebnis. Das Ergebnis ist dann klar definiert, wenn entscheidbar ist, wann die Aufgabe beendet ist. Beispiel: "Ich schau mir mal JavaScript an" ist kein definiertes Ergebnis, "Ich stelle eine Übersicht der Kontrollstrukturen von JavaScript zusammen" hingegen schon.

Keine Aufgabe ohne Klarstellung, für wen das Ergebnis ist. Betrachten Sie Ihre Aufgabe und das Ergebnis als Dienstleistung, als Service für den Empfänger des Ergebnisses. Betrachten Sie den Empfänger als Kunden – und machen Sie ihn glücklich! Denken Sie daran, dass Ihr Kunde von dem Ergebnis profitieren und nicht mehr Zeit als nötig zum Verarbeiten des Ergebnisses investieren möchte. Dennoch sind Quellen, Begründungen etc. anzugeben, denn die Plausibilität ihrer Ergebnisse muss im Zweifelsfall nachvollziehbar sein.

Keine Aufgabe, die länger als zwei Wochen benötigt. Die Zeitspanne von maximal zwei Wochen ist für viele Menschen ein guter Maßstab. "Kleine" Aufgaben sind psychologisch wichtig. Es zwingt außerdem dazu, eine Herausforderung in überschaubare Aufgabe runterzubrechen und erlaubt der Teamleitung ein besseres Nachhalten über den Stand der Dinge.

Keine Aufgabe ohne einen(!) Aufgaben-Verantwortlichen. Wer treibt eine Aufgabe voran, wer kümmert sich darum, dass sie in Angriff genommen wird, wer hält den Arbeitsforschritt nach, wer meldet rechtzeitig Probleme, wer erklärt eine Aufgabe für erledigt? Der Verantwortliche bzw. die Verantwortliche erntet Ruhm wie auch Tadel. Bei kleinen Aufgaben fallen die Rollen zusammen: dann ist eine Person sowohl Aufgaben-Verantwortliche als auch Ausführende. Bei größeren Aufgaben mag man sich die Arbeit teilen, die Verantwortung jedoch nicht. Denn: Verantwortung ist nicht teilbar!

Lernen Sie, auf das Ende einer Aufgabe hinzuarbeiten -- alles andere ist uninteressant. Nehmen wir an, Sie haben die Aufgabe, die Kontrollstrukturen von JavaScript in einer Übersicht zusammenzustellen. Diese Aufgabe ist schnell erledigt, Sie bedarf vielleicht gerade einer halben Stunde, selbst wenn Sie als Informatik-Student noch nie mit JavaScript Kontakt hatten. Natürlich ist es verführerisch, im Web Links zu JavaScript zu verfolgen und vieles Interessantes über die Sprache in Erfahrung zu bringen; ergebnisorientiert ist das nicht.

Definieren Sie Zeiten zur thematischen Orientierung und zum zielorientierten Kompetenzaufbau. Wir sind Menschen, wir können nicht andauernd in Ergebnissen arbeiten und denken. Wir benötigen Zeiten, um uns zu orientieren oder um Kompetenzen aufzubauen, ohne uns dem Druck und dem Stress von Zielen und Ergebnissen unterwerfen zu müssen. Diese Zeiten sind notwendig um (a) überhaupt Ergebnisse und Ziele definieren zu können (Orientierung) und um (b) in die Lage versetzt zu werden, sich Ergebnisse erarbeiten zu können (Kompetenzaufbau). Aber begrenzen Sie diese Zeiten und vereinbaren Sie sich auf ein Thema. Und: Das Thema muss zielführend sein. Beachten Sie, dass sich Kompetenzen in der Regel anhand konkreter Aufgaben aufbauen lassen. Themenarbeit endet mit einem kurzen Tätigkeits- und Erkenntnisbericht an das Team, schließlich ist auch der Lern- oder Orientierungsprozess für das Team von Interesse.

Keine Person im Team ohne aktuelle Aufgabe oder Themenzeit. Sobald eine Person gar nichts tut und etwa einer anderen Person bei der Arbeit zuschaut (gerne maskiert unter "Wir arbeiten zusammen."), läuft irgendetwas schief mit der Teamarbeit. Es kann an mangelnder Koordination bzw. Kommunikation des Teams liegen. Möglicherweise sind aber auch einfach zu viele Personen in einem Team, mehr, als die Aufgabe hergibt.

Arbeiten Sie allein. Sobald mehr als eine Person das Gleiche tut, findet keine Arbeitsteilung mehr statt. Teamarbeit schließt gemeinsames Arbeiten zur gleichen Zeit in einer gemeinsamen Umgebung nicht aus, aber sie verfehlt ihr Ziel, wenn zwei oder mehr Personen grundlos das Gleiche tun. (Auch hier ist die Maskierung "Wir arbeiten zusammen." nicht selten.) Es ist eine der größten Herausforderungen, die Teamarbeit mit sich bringt: alleine arbeiten zu können. Es sind typische Verhaltensmuster von Unsicherheit und Flucht vor der Herausforderung, die Menschen dazu bewegen, mit jemand anderem an der gleichen Aufgabe zusammen arbeiten zu wollen. Auch wenn es paradox zu sein scheint: Teamfähigkeit heißt, weite Strecken über autonom arbeiten zu können. Anders ist Teamarbeit z.B. über das Web in Form von remote collaboration gar nicht möglich.

Definieren Sie regelmäßige, kurze Treffen zur Koordination. Die Arbeiten müssen regelmäßig unter allen Teammitgliedern abgestimmt werden, wobei Anwesenheit (physisch oder virtuell) mehr als sinnvoll ist. Solche Treffen sind kurz zu halten, da diese Zeiten keine Produktivzeiten sind.

Schaffen Sie Möglichkeiten zur Kommunikation. Menschen in einem Team müssen kommunizieren, um eine Identität als Gruppe entwickeln zu können -- und das gilt es gezielt zu kultivieren. Zum Beispiel durch Kommunikationsecken (die berühmte Ecke oder Küche mit der Kaffeemaschine), gemeinsame Arbeitsräume, gemeinsame Mittagessen, Mailing-Listen, Diskussionsforen, Chat-Rooms etc.

Schaffen Sie sich Zeitblöcke zur ungestörten, konzentrierten Arbeit. Ob Sie an einer Aufgabe arbeiten oder mit einem Themenblock beschäftigt sind, Sie brauchen Zeitblöcke von 1 1/2 bis 4 Stunden, um produktive Arbeit leisten zu können. In dieser Zeit sollten sie ungestört sein und auch für Ihre Teammitglieder nicht zur Verfügung stehen.

Zusammenfassung

Teamarbeit ist Arbeitsteilung -- was wörtlich zu nehmen ist: Sie teilen sich die Arbeit. In aller Regel wird mit der Arbeitsteilung eine Spezialisierung einhergehen. Sie arbeiten meist ergebnisorientiert, gelegentlich themenbezogen. Eine Aufgabe ist zeitlich klar begrenzt und hat ein definiertes Ergebnis. Es gibt einen Aufgaben-Verantwortlichen und eine Person bzw. Personengruppe, für die das Resultat der Aufgabe von Nutzen ist. Die Aufbereitung des Resultats sollte an der Zielgruppe ausgerichtet sein. Themenarbeit ist ebenfalls zeitlich klar begrenzt, zielorientiert und endet mit einem Bericht ans Team.

Übrigens sollte ein Team nicht aus zu vielen Personen bestehen. Jenseits von elf, zwölf Personen bilden sich automatisch Untergruppen heraus, die ein Team in wenig gut steuerbare Einheiten zerfallen lassen.

Mittwoch, Mai 21, 2008

Informatik als angewandte Philosophie

Was war zuerst: Die Henne oder das Ei? Oder setzen wir noch früher an: Was bitte ist ein Ei, was genau ein Huhn? Informatiker setzen sich auf ihre eigene Art und Weise mit solchen Fragen auseinander -- eigentlich sogar tagtäglich. Zwar sprechen sie selten von Hühnern oder Eiern, aber sie haben Antworten zu bieten.

Wollen Sie auch erfahren, was Informatiker so gedankenverloren in den Kaffee schauen lässt und warum Milchtüten eine echte Herausforderung sind?

Dann möchte ich Sie herzlich einladen zu meinem Vortrag "Informatik als Angewandte Philosophie: Gedanken über Bits und Bytes" am Dienstag, 3. Juni 2008, um 17:30 Uhr bis 19 Uhr. Der Vortrag findet statt im Rahmen der Ringvorlesung "Mensch-Umwelt-Zukunft" an der Hochschule Heilbronn (Max-Planck-Str. 39) im Raum E010.

Ich freue mich auf Ihren Besuch. Und wenn Sie Wünsche, Anregungen, Gedanken haben, zu denen Sie gerne etwas hören möchten, dann lassen Sie es mich wissen.

Montag, Mai 12, 2008

Forth gedacht: JavaScript 2

Forth ist eine der Programmiersprachen aus der Frühzeit der Informatik. Die Sprache entstand Anfang der 70er Jahre und wurde von Charles H. Moore erschaffen -- und sie hat bis heute überlebt. Sie ist stack-basiert, äußerst einfach aufgebaut, sie kann mühelos ohne Betriebssystem auskommen und ist beliebig erweiterbar. Die Programme sind schnell und äußerst kompakt, weshalb Forth gerade im Bereich der eingebetteten Systeme noch immer gerne genutzt wird. Und man kann mit Forth Programme interaktiv entwickeln; ein Vorteil, den man von interaktiven, dynamisch-typisierten Sprachen kennt. Was das spannende ist: Forth ist ein entscheidender Baustein im neuesten JavaScript 2 (ECMAScript 4) für den Mozilla-Browser Firefox 4.0.

In der zukünftigen Generation des Firefox-Browsers 4.0 (ich spreche nicht von Firefox 3.0, der bald fertig gestellt sein wird) wollen die Mozilla-Entwickler das dann aktuelle JavaScript 2.0 auf einer Virtuellen Maschine (VM) mit JIT-Kompilierung (just in time compilation) ausführen lassen. Im November 2006 erhielt die Mozilla-Organisation die dafür notwendige Technologie von Adobe Systems. Adobe spendete das etwa 135.000 Zeilen Code umfassende Tamarin an Mozilla. Tamarin ist der Name der VM, die Adobe seit Flash 9 für die Ausführung von ActionScript einsetzt. Derzeit läuft ein Projekt namens ActionMonkey bei Mozilla, das die aktuelle JavaScript-Implementierung für Firefox (SpiderMonkey) und das Tamarin-Projekt zusammenbringt.

Der ByteCode von Tamarin wird in Files mit der Endung .abc abgelegt; sie sind das Analogon zu .class-Files für die Java VM. Der abc-ByteCode wird in Forth als Zwischensprache (Intermediate Language, IL) übersetzt. Für Forth gibt es dann einen C-Interpreter. Wer hier generell einen Einstieg finden möchte, dem sei der Blog "Hacking with Caffein" von Mason Chang empfohlen, insbesondere der Beitrag "Getting started with Tamarin and Forth" (27. März 2008). Man darf gespannt sein, wie sich das ActionMonkey-Projekt machen wird und ob sich Forth als IL in der Virtuellen Maschine halten wird!

Wer sich für ein modernes "Forth" interessiert, der sei auf Factor verwiesen. Siehe dazu auch "Factor: In der Kürze liegt die Würze".