Dienstag, 23. November 2010

Eine objektorientierte Metasprache

In Computerzeitschriften und Büchern über modellgetriebene Softwareentwicklung wird in jüngster Zeit häufig das Framework Xtext beschrieben und gepriesen — was vor allem dem Umstand zu verdanken ist, dass es für die Integration von Programmiersprachen in die Eclipse IDE verwendet wird.[1] Xtext (bzw. dessen zugrundeliegender Parsergenerator Antlr) ist ein leicht zu erlernendes Tool, um die Grundzüge der Entwicklung domänenspezifischer Sprachen kennenzulernen — gerade deshalb eignet es sich auch gut für den Einstieg in dieses Gebiet. Es gibt aber interessante Alternativen, die man zumindest kennen sollte.

Eine interessantere Option für zur Laufzeit pflegbare Modelle, für Codegenerierung wie auch für die Entwicklung von DSLs stellen in meinen Augen die sogenannten Parsing Expression Grammars (PEG) dar, insbesondere die von Alessandro Warth entwickelte objektorientierte Metasprache OMeta. Der Grundgedanke aller PEGs ist ein verallgemeinerter Begriff des Pattern Matching, wie es z.B. in regulären Ausdrücken verwendet wird. PEGs nutzen die Erkenntnis, dass alle üblicherweise mit dem Bau von Compilern und Interpretern verbundenen Aufgaben in gewisser Weise nur Varianten eines gemeinsamen Mechanismus sind - der Mustererkennung: [2]


  • Der Tokenizer (auch Lexer oder Scanner genannt) transformiert einen Array von Zeichen (die Eingabe, den Quelltext) in eine Folge von syntaktischen Grundeinheiten, die Tokens. Klassisch verwendet man hierzu ein Werkzeug wie lex oder dessen Weiterentwicklung Flex. Im Prinzip stellt ein Lex- oder Flexfile eine Liste von regulären Ausdrücken dar, die der Reihe nach auf die Eingabe angewendet werden, bis ein passender Ausdruck gefunden wird. Jedem regulären Ausdruck ist eine "Aktion" in Form von C-Code zugeordnet, die schliesslich mit der Rückgabe eines wohldefinierten Tokens mitsamt eines etwaigen Token-Arguments enden muss. Zur Illustration, wie ein solches Flexfile notiert wird, mag mein Flex-Definitionsfile apc_lexer.lex im Projekt astropatterns dienen.
  • Der Parser operiert auf dem Array von Tokens, um eine interne Datenstruktur zu erzeugen, die für die effiziente maschinelle Abarbeitung besonders gut geeignet ist. In der Regel ist das Ergebnis des Parsings ein abstrakter Syntaxbaum (AST). Auch das Parsing ist im Grunde Mustererkennung, nur auf einer höheren Ebene: Er arbeitet mit einer anderer Art "Alphabet", das aus terminalen und nichtterminalen Symbolen besteht, und die Muster sind die Syntaxregeln, die sogenannten Produktionsregeln. Parsergeneratoren haben eine lange Geschichte, in denen yacc (yet another compiler compiler) einen ersten Meilenstein darstellte. yacc, obwohl vor über 30 Jahren entwickelt, wird bis heute für den Entwurf von Programmiersprachen verwendet. Ich habe mit Bison, dem Nachfolger von yacc, eine astrologische DSL implementiert, die hier ebenfalls der Veranschaulichung dienen soll. Die Bison-Grammatik dieser DSL zeigt als strukturelle Ähnlichkeit, dass auch hier die Eingabe mit einer Reihe sogenannter Produktionsregeln verglichen wird. Wenn eine passende Regel gefunden wird, wird die zugeordnete semantische Aktion ausgeführt.
  • Type Checker und Optimierer sind Transformationen des AST, die bestimmte Muster erkennen und durch spezifischere oder effizientere Konstruktionen ersetzen. Da das Produkt des Parsers in der Regel ein Syntaxbaum ist, verwendet man häufig das Besucher-Entwurfsmuster, um den Baum zu traversieren und dabei je nach Anwendungsfall spezifische Operationen auszuführen.[3]
  • Das Gleiche gilt schliesslich für den Code Generator, der den AST in Programmquelltext oder Binärcode für einen Prozessor oder eine virtuelle Maschine transformiert. Auch hierfür werden an das Besuchermuster angelehnte Methoden verwendet, obwohl sich auch diese Aufgabe in Form einer Grammatik mit Produktionsregeln formulieren liesse.


Die Programmiersprache OMeta bietet einen Mechanismus, um all diese Aufgaben in Form einer PEG-Grammatik zu formulieren und zu lösen. Das Konzept ist so allgemein gehalten, dass im Prinzip beliebige Transformationen von Quelltexten und Datenstrukturen in andere Zielstrukturen möglich sind. Die OMeta-Syntax kann in verschiedene Hostsprachen eingebettet werden, es gibt z.B. OMeta-Implementierungen für Squeak, COLA (der ersten verwendeten Hostsprache – einer Mischung aus Scheme und Smalltalk), C#, JavaScript, Ruby u.v.a.m. – die Zahl der Implementierungen steigt. Besonders attraktiv finde ich dabei die Kooperation mit dynamischen Hostsprachen wie JavaScript oder Python. Denn die interpretierten Sprachen sind offenbar besonders gut gerüstet für die Vision der modellgetriebenen Softwareentwicklung, zur Laufzeit in einer domänenspezifischen Sprache das Systemverhalten steuern zu können. Die Sprache JavaScript hat darüberhinaus den zusätzlichen Vorteil, dass sie als "Standardsprache der Webbrowser" ohne Extrakosten in Webanwendungen verfügbar ist. Weil ich die Sprache OMeta so wichtig finde, habe ich auf meiner Homepage eine Oberfläche zum Experimentieren unter dem Link

http://ruediger-plantiko.net/ometa/

bereitgestellt. Sie ist ähnlich der auf http://tinlizzie.org bereitgestellten Seite, trennt jedoch klarer den Grammatik-Definitionsteil von der Ausführung des daraus generierten Parsers.

OMeta ist, wie es der Name sagt, eine objektorientierte Metasprache, die viele interessante Features aufweist:

  • Die Eingabe von OMeta muss nicht als Quelltext oder überhaupt als Zeichenfolge vorliegen, sondern kann ein Array von beliebigen Objekten der Hostsprache sein. Das ermöglicht z.B. auch die Transformation von abstrakten Syntaxbäumen. Denn jeder Syntaxbaum ist i.w. als eventuell verschachtelte Folge von Arrays, Tokens und Objekten darstellbar. Das JavaScript-Statement
    document.getElementById("btnSave").click();

    könnte z.B. durch folgenden AST dargestellt werden:
    [ APPLY, 
    [ APPLY, document, "getElementById", ["btnSave" ] ],
    "click", [] ]

    Das ist, formal gesehen, ein Array, der aus Objekten besteht - nämlich wiederum aus Arrays, aus Symbolen wie APPLY (die z.B. auch als Strings realisierbar wären), aus gewöhnlichen JavaScript-Objekten der Hostsprache, wie hier dem DOM-Objekt document, und Datentypen wie Strings, Zahlen, usw.[4] In dieser Form könnte der AST wiederum einem OMeta-Programm zur Verarbeitung vorgelegt werden.

  • Objektorientierung erlaubt die Trennung von Produktionsregeln in verschiedenen Namensräumen. So ist jede Grammatik frei in ihrer Namenswahl für die verwendeten Symbole, unbeeinflusst durch eventuell bereits im selben Prozess bestehende Grammatiken. Ausnahme ist natürlich der explizit gewünschte Bezug auf eine bestehende Grammatik durch den Vererbungsmechanismus. Es ist möglich, eine OMeta-Grammatik von einer anderen erben zu lassen und sich in der Formulierung der Produktionsregeln auf die Regeln der Superklasse zu beziehen. Das erlaubt es, bestehende Parser, z.B. den notwendigerweise existierenden Parser der Hostsprache, mit wenigen Codezeilen um eigene Konstrukte zu erweitern. Dadurch ist OMeta ein ideales Werkzeug für Entwickler von Programmiersprachen, um neue syntaktische Idiome auszuprobieren.

  • Im Gegensatz zu kontextfreien Grammatiken (CFG) ist der Auswahloperator | in einer PEG nichtdeterministisch: Es ist ein priorisierter, "kurzschliessender" Operator, dessen Evaluation bei der ersten passenden Alternative abgebrochen wird. Das kann als Nachteil angesehen werden, da die "veroderten" Operanden dadurch nicht mehr gleichberechtigt sind. Andererseits ist es auch ein Vorteil, da die Interpretation eines priosierten Auswahloperators keine Mehrdeutigkeiten produziert, wodurch die PEGs einfacher nachvollziehbar werden.

  • Das letztgenannte Feature des priorisierten Auswahloperators bringt üblicherweise das Problem von Endlosschleifen für linksrekursive Regeln mit sich. Die Regel
    expr = expr "-" number | number

    zur Definition von Subtraktions-Ausdrücken kann in einer herkömmlichen PEG nicht ausgewertet werden: Um diese Regel zu erkennen, wird zuerst der linke Teil der Alternative ausprobiert; hierzu muss wiederum die Erkennung von expr ausgeführt werden usw. Das führt zu einem unendlichen Abstieg. In komplizierteren Fällen bildet sich ein geschlossener Zykel aus mehreren voneinander abhängigen Regeln, die sogenannte indirekte Linksrekursion.

    Nun lassen sich alle Regeln, die auf das Problem der Linksrekursion stossen, von Hand so umschreiben, dass die Linksrekursion nicht mehr auftritt. Aber die Ausdrücke werden dadurch umständlicher und sind nicht mehr so leicht nachvollziehen. Aus Sicht eines Grammatik-Entwicklers ist es eine unnötige Komplikation, in seiner Grammatik Linksrekursionen vermeiden zu müssen.

    Nun ist es Alessandro Warth mit OMeta gelungen, dieses Problem zu lösen. In OMeta kann man auch linksrekursive Regeln wie die obige notieren. Die Effizienz leidet darunter nicht wesentlich - die Parsezeiten hängen in der Regel weiterhin linear von der Länge des Inputs ab. Die Möglichkeit rekursiver Regeldefinitionen erhöht die Ausdruckskraft von OMeta in der Verwendung als alternative PEG-Implementierungen.

  • OMeta erlaubt die Definition sogenannter parametrisierter Regeln. Das sind, wie der Name sagt, Regeln, die von Parametern abhängen. Warth erläutert dieses Idiom anhand einer Regel für Zeichenmengen. Zeichenmengen kann man traditionell durch den Auswahloperator definieren. Wenn es die eingebaute Regel digit für die Erkennung von Ziffern in OMeta nicht schon gäbe, könnte man sie so definieren:
    digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

    Solche Regeln sind fehleranfällig und langsam in der Ausführung. Hier helfen parametrisierte Regeln wie die folgende (die überdies zeigt, dass auch in parametrisierten Regeln sogenannte semantische Aktionen angegeben werden können, wie hier die Rückgabe des erkannten Zeichens):
    charRange :x :y = char:c ?(x <= c && c <= y) -> c

    Ist die Regel charRange einmal erklärt, kann sie in weiteren "konkreten" Regeln wiederverwendet werden:
    digit     = charRange('0','9'),
    lowerCase = charRange('a','z'),
    upperCase = charRange('A','Z')

    Das Beispiel lässt erkennen, dass die parametrisierten Regeln eine höhere Abstraktionsebene einführen. Wie Vererbung erlauben sie eine "Oben-Unten-Trennung", eine Trennung des Allgemeinen vom Konkreten.

  • Wie um dies noch zu überbieten, unterstützt OMeta sogar Regeln höherer Ordnung: Das sind Regeln, die andere Regeln als Argument haben! Dieses Feature wird möglich durch eine Kombination der parametrisierten Regeln mit einer speziellen eingebauten Regel namens apply. apply nimmt den Namen einer Regel entgegen und führt diese aus. Als sinnvolles, praktisches Beispiel gibt Warth folgende OMeta-Regel:
    listOf :p = apply(p) ( "," apply(p) )*

    Diese Regel erkennt ein oder mehrere, durch Komma getrennte Vorkommen von "etwas, das der Regel p genügt". Beispielsweise erkennt der Term
    listOf('expression')

    eine mit Kommas getrennte Liste von Ausdrücken (die einer früher definierten Regel expression genügen), während
    listOf('name')

    auf eine Liste von Namen (die der früher definierten Regel name genügen) passt.



Ich kann hier nicht die gesamte Sprache OMeta erläutern, sondern nur zu ihrem Studium anregen. Die obigen Erklärungen fassen wesentliche Teile von Warths Dissertation zusammen. Wer mehr erfahren will, sei auf http://www.tinlizzie.org/ometa/ verwiesen.

Immerhin will ich noch ein kleines, in der Szene der "Compilerbauer" beliebtes Beispiel vorführen: einen "Tischrechner". Dieser konkrete Tischrechner kann sogar mit Variablen arbeiten, was nebenbei beweist, dass man mit OMeta auch zustandsbehaftete Parser bauen kann. Auf meiner Testseite erreicht man seine Definition durch Auswahl von Calculator in der Liste der verfügbaren Grammatiken. Auch dieses Beispiel ist der Dissertation von Warth entnommen. Ich will es hier kurz diskutieren.

Mit der ersten Zeile
ometa Calc <: Parser {

wird eine neue Grammatik (eine neue Transformation, ein neuer Parser, ein neues OMeta-Objekt) deklariert. In diesem Fall soll es von der eingebauten Grammatik Parser erben. Diese eingebaute Klasse enthält aktuell nur eine einzige grundlegende Parser-Funktionalität – nämlich eine token-Regel, mit der durch Leerzeichen getrennte Strings erkannt werden können. Diese token-Regel wird in allen von Parser erbenden Grammatikdefinitionen automatisch den in Doppelhochkommata eingeschlossenen Strings unterlegt. Mehr bekommt man durch diese Vererbung nicht.

Die nächste Zeile
var           = spaces letter:x             -> x,

zeigt die typische Syntax einer Produktionsregel in OMeta. Dem Namen der Regel folgt nach einem Gleichheitszeichen ihre Definition, und nach der Definition kann, mit einem Pfeil -> abgetrennt, eine semantische Aktion angegeben werden. Eine semantische Aktion ist im Code der Hostsprache notiert und wird für ein erkanntes Muster evaluiert. Das Ergebnis der Evaluation ist auch der Rückgabewert der sogenannten matchAll()-Methode, mit der man schliesslich den Parser aufrufen kann.

In diesem Fall haben wir eine Regel var zur Erkennung von Variablennamen. Zunächst wird festgelegt, dass Leerzeichen unmittelbar vor einem Variablennamen ignoriert werden sollen. Dies erreicht man mit der eingebauten Regel spaces, die "Null oder mehr Leerzeichen" erkennt. Danach folgt die eigentliche Festlegung, was als Variable erkannt werden soll: Variablen sollen in unserem Tischrechner einbuchstabig sein. Hierzu benutzen wir die eingebaute OMeta-Basisregel letter. Nach dem Doppelpunkt folgt nun ein Variablenname, der bei erfolgreicher Anwendung der Regel das Evaluationsergebnis der semantischen Aktion enthält (oder, wenn keine semantische Aktion ist, den als passend erkannten Teil der Eingabe). Auf diese Variablen, die während des Parsens zugewiesen werden, kann man dann in der semantischen Aktion zurückgreifen – wie hier. Wir legen fest, dass der Rückgabewert der Regel genau der erkannte Buchstabe ist.

Eine einfachere, völlig äquivalente Formulierung wäre übrigens
var           = spaces letter

Aber wir wollen ja schliesslich lernen, wie OMeta funktioniert, und dafür ist die erste Variante besser geeignet.

Nach den Variablen legt die folgende Regel die erlaubten Zahlen fest - positive, ganze Zahlen:
num           = num:n digit:d        -> (n*10 + d*1)
| digit:d -> (d*1),

Hier ist neu der Gebrauch des Auswahloperators | für die Deklaration der Alternativen. Ausserdem lernen wir, dass auch Teilen einer Regel bereits eine semantische Aktion zugeordnet werden darf. Der erste Teil der Regel enthält darüberhinaus die bereits besprochene Linksrekursion.

Diese Regel hätte man äquivalent auch so schreiben können:
num           = digit+:d        -> (1*d.join('')),

Neu ist hier der Quantifier + mit derselben Semantik wie in regulären Ausdrücken. Ein mit dem Quantifier + oder * angereicherter Ausdrucks evaluiert immer zu einem Array mit den einzelnen Treffern als Elementen. Den Array können wir in der semantischen Aktion mittels der Methode join() der JavaScript-Klasse Array zu einem String zusammenspleissen und schliesslich durch Multiplikation mit 1 (type coercion) die Umwandlung in den numerischen Datentyp erzwingen. Auch diese Variante der Regel num ist sicher lehrreich.

Es folgen nun die primären Ausdrücke: Die Eingabe eines Variablennamens soll deren Inhalt zurückliefern, die Eingabe eines Zahlenstrings soll ebendiese Zahl zur Antwort haben, und komplexere Ausdrücke sollen geklammert werden können:
primaryExpr   = spaces var:x         -> self.vars[x]
| spaces num:n -> n
| "(" expr:r ")" -> r,

Neu ist hier der Zugriff auf die Variable self.vars, die in einer speziellen, bei der Parserinstanziierung aufgerufenen sogenannten initialize()-Methode als leerer Hash definiert wird und uns als Container (genauer: als Symboltabelle) für die im Tischrechner eingegebenen Variableninhalte dient.

Es kommen nun die Multiplikations- und Additionsregeln:
mulExpr       = mulExpr:x "*" primaryExpr:y -> ( x * y )
| mulExpr:x "/" primaryExpr:y -> ( x / y )
| primaryExpr,
addExpr = addExpr:x "+" mulExpr:y -> ( x + y )
| addExpr:x "-" mulExpr:y -> ( x - y )
| mulExpr,

Wir benutzen hierbei die Eigenschaft, dass der Auswahloperator priorisierend ist, um der Punktrechnung vor der Strichrechnung den Vorzug zu geben: Es werden immer zuerst die mulExpr erkannt (und evaluiert), bevor ein addExpr erkannt wird. Nicht ganz dem entsprechend, was der Name suggeriert, subsumiert die Regel addExpr insbesondere auch den mulExpr (dritte Alternation der Regel für additive Ausdrücke). Auf der rechten Seite stehen wieder die semantische Aktionen - in den Klammern kann beliebiger JavaScript-Code codiert sein.

Die addExpr ist somit allgemeiner als mulExpr und allgemeiner als die primaryExpr. Sie enthält letztere als Spezialfälle. Mit der folgenden Regel
expr          = var:x  "=" expr:r           -> (self.vars[x] = r)
| addExpr,

umfassen wir somit alle für den Tischrechner gültigen Ausdrücke. Variablenzuweisungen ebenso wie arithmetische Ausdrücke (die auch wieder Variablen enthalten dürfen).

Die letzte Regel doit legt fest, dass soviele Ausdrücke wie möglich evaluiert werden sollen, und schliesslich das Ergebnis des letzten gültigen Ausdrucks ausgegeben werden soll.
doit          = (expr:r)* spaces end        -> r


Hier folgt noch - ausserhalb der OMeta-Grammatik, die bereits erwähnte initialize()-Methode, mit der der Rechner in den Startzustand versetzt wird:
Calc.initialize = function() {  this.vars = {}; }

In meiner "Workbench" kann ich nun die Regel doit auf die Eingabe
x=1 y=2 x+y

anwenden und erhalte die Ausgabe 3. Das liegt daran, dass die doit-Regel mehrere, durch Leerraum getrennte Ausdrücke erkennt und auswertet. Ich hätte aber auch drei Eingaben nacheinander tätigen können: Zuerst
x=1

danach
y=2

und schliesslich
x+y

Auch dann hätte ich die Ausgabe 3 erhalten. Der Grund ist, dass meine "Workbench" in jedem Dialogschritt mit derselben Parserinstanz arbeitet und sich daher alle bereits erfolgten Variablenzuweisungen in der Symboltabelle vars gemerkt hat. Es ist eben ein stateful parser – und mit dieser Eigenschaft ist OMeta auch für REPL Shells verwendbar (read-evaluate-print loops).

Wer mag, kann sich auf meiner OMeta-Workbench auch meinen in OMeta implementierten XML-Parser anschauen: Ein meiner Ansicht nach durchaus lesbarer Quelltext von nur 42 Zeilen erlaubt die Transformation eines XML-Dokuments in einen in JavaScript modellierten Objektbaum. Das sind die Grössen, mit denen man in OMeta arbeiten kann; es ist auch eine der Fragestellungen, mit denen das Viewpoints Research Institute angetreten ist, unter dessen Dach auch OMeta entwickelt wurde: Um wieviele Zehnerpotenzen kann bestehender Programmquelltext bei Einsatz geeigneter, möglichst ausdrucksstarker Programmierumgebungen gekürzt werden, um dennoch das zu erreichen, wozu man heute Computer einsetzt (Textverarbeitung, Graphik, Internet usw.)?

Dies möge als ein erster Einblick in einen hochinteressanten Parsergenerator genügen, den ich zum näheren Studium nur empfehlen kann. Die Einsatzfelder, rund um den Bereich domänenspezifischer Sprachen (DSL) scheinen mir sehr vielversprechend zu sein. Die Sprache ist kompakt und ausdrucksstark. Ihren mächtigen Features, wie etwa der Objektorientierung, den parametrisierten Regeln und der Rekursion, ist es zu verdanken, dass Grammatiken wesentlich eleganter notiert werden können als in früheren Werkzeuge dieser Art.




[1] So in Thomas Stahl, Markus Völter, Sven Efftinge, Arno Haase: Modellgetriebene Software-Entwicklung, 2. Auflage, dpunkt Verlag, Heidelberg 2007.
Jan Köhnlein und Sebastian Zarnekow, Xtext-Praxis, eclipse-Magazin 1.2010, S. 50.
[2] Die folgenden Ideen sind der Dissertation von Alessandro Warth Experimenting with Programming Languages entnommen.
[3] Es geht jedoch auch ohne das Besucher-Entwurfsmuster, das leider intrusiv ist und dem in der Umsetzung eine gewisse Schwerfälligkeit anhaftet (wie ich in meinem Blog gezeigt habe).
[4] Dabei wird die Anwendung einer Methode m des Objekts o mit dem Argument-Array [args...] durch das Konstrukt [APPLY, o, m, [args...]] modelliert.

Keine Kommentare :