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