Pattern Matching Algebra
Die Pattern Matching Tools, die ich kenne, müsste man mal auf eine solidere Grundlage stellen. Sie mixen alle verschiedene Aspekte einer Pattern Matching Algebra, die man auch mal sauber und in funktionaler Manier implementieren könnte:
- Basis-Matcher m: Sie nehmen einen Text T und erzeugen daraus eine Menge M =<t,<start,ende,transformation>*> (Vereinfachend könnte man einfach sagen: Input ist bereits eine solche Menge, mit <t,ø>
Der Matcher kann auf irgendeine Art die Patterns erzeugen: Über einen regulären Ausdruck, eine Grammatik, ein Lexikon, was auch immer. Mit anderen Worten, ein Matcher ist eine Abbildung <t,<start,ende,transformation>*> -> <t,<start,ende,transformation>*>, wobei in den meisten Fällen der Input = t sein wird.
Darauf kann man nun Operationen anwenden:
- Oder: M | M ist einfach die Vereinigung der beiden Mengen, wobei jeweils das Resultat eines Matchers m ist und wiederum einen Matcher darstellt (all diese Operationen gehen nur, wenn T1=T2).
- Und: M & M, die Schnittmenge
- Minus: M - M, die Differenz. Oder auch: "Blacklisting"
- Komposition: M o M: Output des ersten ist Input des zweiten: "Pipelines"
- Komplement: Das wären alle denkbaren Matches aus T außer den Einträgen in M. Macht wohl keinen Sinn.
- Filter: longest(M), shortest(M) etc.: filtert M nach gewissen Prädikaten.
Bei Verwendung einer funktionalen Programmiersprache wären diese Operationen offensichtlich. Die Berechnung würde hier immer "lazy" erfolgen, also nur, wenn ein Client sie anfragt.
Die Verwendung imperativer Programmiersprachen verhindert, dass man diesen Zusammenhang sieht. Im schlimmsten Fall erzeugt das Programm die Matches und schreibt sie selbst irgendwo hin - Komposition unmöglich. Besser ist es, wenn die Operationen durch eine Cursor-Algebra implementiert werden, also auf Basis von Iteratoren. Das ist in imperativen Sprachen aber oft sehr umständlich. Es erfordert, dass man eine Schleife in der Mitte abbricht, zurückspringt, und die Verarbeitung danach an der gleichen Stelle wieder aufnimmt. Manche Sprachen wie Python machen einem hier das Leben auf Sprachebene leichter (siehe auch meine Bemerkungen zu yield, unten).
Die Verwendung einer Cursor-Algebra hat einen weiteren Vorteil: Der entstehende Baum von Iteratoren kann umgeformt und damit optimiert werden. Würde die Programmiersprache dies unterstützen, könnte man on the fly umformen, etwa dass (M1 o (M2 o M3)) = o(M1,M2,M3), wobei o dann eine optimierte n-äre Implementation des Operators o wäre (wenn ich es richtig verstanden habe, unterstützt LISP genau das).
Dies in C++ durchzuführen, ist allerdings ein arbeitsames Unterfangen. Es würde sich lohnen, sich mehr mit Sprachen wie ML oder Lisp zu beschäftigen, die hier gewisse Erleichterungen bringen.
Wie lässt sich nun ausdrücken, dass dieselben Operationen auch auf den Transformationen möglich sind, ohne dass man (wie bei Transducern) Information vergessen, also die Transformation zum neuen T machen muss?
Diese Gedanken zum Thema funktionale Programmierung bringen mich auf zwei weitere: Das Problem der Aggregation und das der Parallelisierbarkeit.
Aggregation ist das Sammeln von Statistiken, das "Eindampfen" von Ergebnissen der oben genannten Operationen. Der count() Operator von SQL wäre so ein Fall (übrigens ist SQL ein Paradebeispiel dafür, wie man es nicht machen sollte - die meisten Implementationen haben große Probleme mit Kompositionalität). Das Zählen von Einträgen im Tupel mit dem gleichen Wert. Derartige Dinge.
Die Erkenntnis von heute: Im Endeffekt sind wir hier bei einer Reduce-Operation, wie es sie etwain Python gibt. Und eine Funktion f: M -> M ist ein Mapping. Auch ein Python-Konstrukt. Beides ist natürlich keine Python-Erfindung, sondern schon aus Lisp-Zeiten bekannt. Und natürlich gibt es die MapReduce-Variante von Google. In Hadoop hat dazu kürzlich eine Open-Source-Implementierung das Licht der Welt erblickt. Sehr angenehm.
Das zweite ist Parallelisierbarkeit. Einzelne Mappings lassen sich natürlich parallelisieren, auf verschiedene Rechner verteilen - wenn sie nicht voneinander abhängen. Hier kann man das Rad neu erfinden und nennt das dann "verteilter matcher". Dieser bekommt einen matcher als argument und ist selbst einer. Und der andere läuft dann auf einem anderen Rechner, in einem eigenen Server, für das man dann ein Kommunikationsprotokoll schreiben muss.
Parallelisierbarkeit ist das Stichwort der nächsten Jahre. Die Steigerungen bei der Gigahertz-Zahl sind zunächst mal gestoppt. Jeder Prozessor wird aus 2, 4, 8, 16... Kernen bestehen. Data Crunching passiert auf 1000en Computern gleichzeitig. Wird Zeit, dass sich die Programme anpassen.
Die Konzepte wurden allerdings bereits anfang der 60er Jahre entwickelt. Das Multics-System war bereits ein symmetrisches Multiprozessor-System, mehrere Prozessoren teilten sich einen Hauptspeicher (siehe das Essay von Jack Dennis - noch einer, der recht hat)
Dennis hat ein paar weitere Ideen: Er will Hardware und Software besser aufeinander abstimmen und baut deshalb einen Rechner, der sich für Parallelisierung besser eignet als jetzige. Er hat in einer Präsentation u.a. Prinzipien für Parallelisierbarkeit aufgestellt:
- Basis-Matcher m: Sie nehmen einen Text T und erzeugen daraus eine Menge M =<t,<start,ende,transformation>*> (Vereinfachend könnte man einfach sagen: Input ist bereits eine solche Menge, mit <t,ø>
Der Matcher kann auf irgendeine Art die Patterns erzeugen: Über einen regulären Ausdruck, eine Grammatik, ein Lexikon, was auch immer. Mit anderen Worten, ein Matcher ist eine Abbildung <t,<start,ende,transformation>*> -> <t,<start,ende,transformation>*>, wobei in den meisten Fällen der Input = t sein wird.
Darauf kann man nun Operationen anwenden:
- Oder: M | M ist einfach die Vereinigung der beiden Mengen, wobei jeweils das Resultat eines Matchers m ist und wiederum einen Matcher darstellt (all diese Operationen gehen nur, wenn T1=T2).
- Und: M & M, die Schnittmenge
- Minus: M - M, die Differenz. Oder auch: "Blacklisting"
- Komposition: M o M: Output des ersten ist Input des zweiten: "Pipelines"
- Komplement: Das wären alle denkbaren Matches aus T außer den Einträgen in M. Macht wohl keinen Sinn.
- Filter: longest(M), shortest(M) etc.: filtert M nach gewissen Prädikaten.
Bei Verwendung einer funktionalen Programmiersprache wären diese Operationen offensichtlich. Die Berechnung würde hier immer "lazy" erfolgen, also nur, wenn ein Client sie anfragt.
Die Verwendung imperativer Programmiersprachen verhindert, dass man diesen Zusammenhang sieht. Im schlimmsten Fall erzeugt das Programm die Matches und schreibt sie selbst irgendwo hin - Komposition unmöglich. Besser ist es, wenn die Operationen durch eine Cursor-Algebra implementiert werden, also auf Basis von Iteratoren. Das ist in imperativen Sprachen aber oft sehr umständlich. Es erfordert, dass man eine Schleife in der Mitte abbricht, zurückspringt, und die Verarbeitung danach an der gleichen Stelle wieder aufnimmt. Manche Sprachen wie Python machen einem hier das Leben auf Sprachebene leichter (siehe auch meine Bemerkungen zu yield, unten).
Die Verwendung einer Cursor-Algebra hat einen weiteren Vorteil: Der entstehende Baum von Iteratoren kann umgeformt und damit optimiert werden. Würde die Programmiersprache dies unterstützen, könnte man on the fly umformen, etwa dass (M1 o (M2 o M3)) = o(M1,M2,M3), wobei o dann eine optimierte n-äre Implementation des Operators o wäre (wenn ich es richtig verstanden habe, unterstützt LISP genau das).
Dies in C++ durchzuführen, ist allerdings ein arbeitsames Unterfangen. Es würde sich lohnen, sich mehr mit Sprachen wie ML oder Lisp zu beschäftigen, die hier gewisse Erleichterungen bringen.
Wie lässt sich nun ausdrücken, dass dieselben Operationen auch auf den Transformationen möglich sind, ohne dass man (wie bei Transducern) Information vergessen, also die Transformation zum neuen T machen muss?
Diese Gedanken zum Thema funktionale Programmierung bringen mich auf zwei weitere: Das Problem der Aggregation und das der Parallelisierbarkeit.
Aggregation ist das Sammeln von Statistiken, das "Eindampfen" von Ergebnissen der oben genannten Operationen. Der count() Operator von SQL wäre so ein Fall (übrigens ist SQL ein Paradebeispiel dafür, wie man es nicht machen sollte - die meisten Implementationen haben große Probleme mit Kompositionalität). Das Zählen von Einträgen im Tupel mit dem gleichen Wert. Derartige Dinge.
Die Erkenntnis von heute: Im Endeffekt sind wir hier bei einer Reduce-Operation, wie es sie etwain Python gibt. Und eine Funktion f: M -> M ist ein Mapping. Auch ein Python-Konstrukt. Beides ist natürlich keine Python-Erfindung, sondern schon aus Lisp-Zeiten bekannt. Und natürlich gibt es die MapReduce-Variante von Google. In Hadoop hat dazu kürzlich eine Open-Source-Implementierung das Licht der Welt erblickt. Sehr angenehm.
Das zweite ist Parallelisierbarkeit. Einzelne Mappings lassen sich natürlich parallelisieren, auf verschiedene Rechner verteilen - wenn sie nicht voneinander abhängen. Hier kann man das Rad neu erfinden und nennt das dann "verteilter matcher". Dieser bekommt einen matcher als argument und ist selbst einer. Und der andere läuft dann auf einem anderen Rechner, in einem eigenen Server, für das man dann ein Kommunikationsprotokoll schreiben muss.
Parallelisierbarkeit ist das Stichwort der nächsten Jahre. Die Steigerungen bei der Gigahertz-Zahl sind zunächst mal gestoppt. Jeder Prozessor wird aus 2, 4, 8, 16... Kernen bestehen. Data Crunching passiert auf 1000en Computern gleichzeitig. Wird Zeit, dass sich die Programme anpassen.
Die Konzepte wurden allerdings bereits anfang der 60er Jahre entwickelt. Das Multics-System war bereits ein symmetrisches Multiprozessor-System, mehrere Prozessoren teilten sich einen Hauptspeicher (siehe das Essay von Jack Dennis - noch einer, der recht hat)
Dennis hat ein paar weitere Ideen: Er will Hardware und Software besser aufeinander abstimmen und baut deshalb einen Rechner, der sich für Parallelisierung besser eignet als jetzige. Er hat in einer Präsentation u.a. Prinzipien für Parallelisierbarkeit aufgestellt:
- Ausdrücke: (u + v) * (x + y) - jeder Unterausdruck kann parallel berechnet werden
- Funktionen: z=f(x,u)+g(x) lässt sich parallelisieren, da keine derFunktionen vom Output der anderen abhängt
- Daten: Ein linearer Durchlauf durch ein Array lässt sich parallelisieren, wenn es keinen weiteren Zustand außer der Schleifenvariable gibt:
Z := for i in [1..n]
z = X[i-1]+Y[i+1]*2.0
returns array of z
end for;
Hier ist die Zeile z = ... verteilbar. Die Sprache ist übrigens Sisal. - Producer/Consumer:
producer:
x = f(x)
sende g(x) an port
consumer:
y = lese port
z = h(z,y)
Dieses Pattern ist in vielen Sprachen eingegangen, etwa auch die Generatoren von Python, eine Art von Coroutinen, oder auch Threads in Java mit PipedInputStream/OutputStream und der Concurrency Bibliothek
- Wer Data Crunching betreibt, suche nach Möglichkeiten, Kompositionalität zu erreichen, indem eine Algebra erstellt wird. Ansonsten wird man, wie bei SQL geschehen, bestimmte Konstrukte, die durch die Algebra ausgedrückt werden könnten, fix vorgeben und die Flexibilität dadurch von "unendlich" auf eine finite Anzahl Konstruktionen einschränken.
- Es lohnt sich, sich näher mit funktionaler Programmierung auseinanderzusetzen. Der steigende Grad an Parallelisierung wird es ermöglichen, funktional geschriebene Programme blitzschnell auf Terabytes von Daten operieren zu lassen.
- Google MapReduce implementiert die hier besprochenen Konstrukte auf elegante Art und ermöglicht massive Verteilung
- Und wer meint, Sisal wäre eine tote Sprache, der irrt: Viele Operationen in MapReduce werden bei Google in der hauseigenen Sprache Sawzall geschrieben. Obwohl das Paper Sisal nicht direkt zitiert - kaum anzunehmen, dass es außer dem Namen keine Anklänge daran gibt.
- Die schlechte Nachricht: Es war alles schon mal da, und es ist wieder da. Und alles bei Google. Wenig, was dem noch hinzuzufügen wäre.
posted by Clemens at 3:43 PM
0 Comments:
Kommentar veröffentlichen
<< Home