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.

Keine Kommentare: