Direkt zum Hauptbereich

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.

Beliebte Posts aus diesem Blog

Lidl und der Kassen-Bug

Es gibt Fehler, im Informatiker-Jargon "Bugs", die etwas anrühriges haben. Ich bat den Menschen an der Kasse bei Lidl um einen Moment Geduld und meine Kinder um Ruhe, um nicht den wunderbaren Moment zu verpassen, bei dem es passierte. Der Lidl-Mensch fluchte kurz auf -- und ich war entzückt! "Einen Moment, davon muss ich ein Foto machen!" Und dann machte ich noch eines. Ich bin heute extra für diesen Fehler zu Lidl gepilgert -- ich wollte es mit eigenen Augen sehen. Gestern hat mir ein Student (vielen Dank Herr Breyer) von diesem Fehler in einer EMail berichtet. Ein richtig schöner Fehler, ein Klassiker geradezu. Ein Fehler, den man selten zu Gesicht bekommt, so einer mit Museumswert. Dafür wäre ich sogar noch weiter gereist als bis zum nächsten Lidl. Der Fehler tritt auf, wenn Sie an der Kasse Waren im Wert von 0 Euro (Null Euro) bezahlen. Dann streikt das System. Die kurze Einkaufsliste dazu: Geben Sie zwei Pfandflaschen zurück und Lidl steht mit 50 Cent bei Ihne

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 Syn

Mit Prof. Handke im Gespräch: Vom Workbook zum Inverted Classroom

Aus dem Netz in Handkes Büro Es gibt diese schönen Momente, da führen soziale Medien zu sozialen Begegnungen im echten Leben. Ich twittere im Nachgang zur #BiDiWe16, ein Dialog mit Jürgen Handke ergibt sich, er schickt mir seine Telefonnummer, ich rufe sofort durch, wir verabreden uns. Drei Tage nach der #BiDiWe16 sitze ich bei Handke im Büro, das gleichzeitig sein beachtlich ausgestattetes Aufnahmestudio beherbergt. Es ist Freitagmorgen, 9. September 2016. Jürgen Handke ist mir kein Fremder. Ich habe zwei seiner ICM-Konferenzen besucht, auf der #BiDiWe16 in Berlin hielt er die Keynote. Er hat für seine Lehre Preise erhalten, zuletzt 2015 den Ars Legendi-Preis für exzellente Hochschullehre. Zugegeben, ich hadere mit dem Konzept des Inverted Classroom -- auch Flipped Classroom genannt. Meine Erfahrungen mit der Programmierausbildung von Informatik-Studierenden des 1. und 2. Semesters lassen mich zweifeln. Videos habe ich auch schon produziert, aber vor allem das selbstgesteuerte