nicht angemeldet
Hallo Uwe,
ich antworte mal in eine etwas andere Richtung in der Hoffnung, dass ein anderer Blick das klarer macht.
- XSLT ist eine funktionale Sprache,
Ich würde das gerne auf einer anschaulichen Ebene diskutieren, sonst reden wir plötzlich darüber wie XSLT beispielsweise als Sprache einzuordnen ist.
Zum Verständnis ist es aber durchaus praktisch, sich dessen bewusst zu sein. Dazu argumentiere ich mal ein bisschen durch die gedachten Vorteile, die man dadurch bekommt, dass XSLT funktional ist.
Ich habe eine geordnete Menge, hier eine Knotenliste, die current node list. Diese Menge (Knotenliste) wird in der gegebenen Reihenfolge durchlaufen, wobei bei jedem Durchlauf ein durch die Reihenfolge gegebenes Element (Knoten) zum gegenwärtigen Element (current node) wird, auf das ich unmittelbaren Zugriff habe.
Da stimmt Dir jeder zu – bis auf „in der gegebenen Reihenfolge durchlaufen“. Das ist nämlich nicht nötig.
Stell Dir mal vor Du implementierst eine Funktion, die xsl:for-each in einem gedachtem XSLT-Prozessor implementiert. Dieser Prozessor übernimmt irgendwo das Parsen, startet irgendwo die Verarbeitung und ruft irgendwas xsl.forEach() mit bestimmten Parametern auf. Hier mal in Pseudo-JavaScript diese Funktion in einer naiven Variante:
~~~javascript
function forEach (seq : Sequence, construct : Function, sorting : Function) : Sequence {
var result : Sequence = new Sequence();
for (currentNode in seq) {
var x : Sequence = construct(currentNode);
result.append(x);
}
return result.sort(sorting);
};
Die Funktion nimmt als Parameter eine Sequenz (Das Resultat des select-Attributes), eine Sortier-Funktion (Meine gedachte Zusammenfassung von den optionalen <xsl:sort>-Elementen) und eine Funktion namens construct. Ich bleibe hier extra in der Terminologie von XSLT (2.0). Das Element <xsl:for-each> erwartet eine Sequenz auf der es arbeiten kann und innerhalb dürfen optionale <xsl-sort>s und ein Sequenz Konstruktor notiert werden. Letzterer gibt eine Sequenz von Knoten zurück, mehr wissen wir nicht über ihn. Deswegen ist er als abgeschlossene Funktion notiert. Die Funktion ist wie angekündigt billig und naiv, jeder Knoten in der Sequenz wird der Reihe nach durchlaufen, als Argument des Sequenz-Konstruktors aufgerufen, die zurückgegebene Sequenz wird an eine for-each-Sequenz (Array-ähnlich) eingehängt. Am Ende wird diese Sequenz mit dem Sortierkriterium (xsl:sort..) sortiert und zurückgegeben.
Da ist sie doch, die Schleife. Sogar eine Mengenschleife. Jupp. Ich sage ja, eine naive Implementierung. Machen wir es spannender. Was wird in letzer Zeit spannend an modernen Computern? U.a. dass die Prozessoren mehrere Kerne bekommen können. Mehrprozessor-Computer in einem Prozessor. Dadurch können Threads und Prozesse wirklich gleichzeitig ausgeführt werden und man kriegt einen Geschwindigkeitsschub. Das wäre doch toll, wenn forEach() das auch könnte. Dummerweise ist unsere Schleife iterativ und jeder Teilabschnitt der Schleife muss darauf warten, dass die vorherige Iteration beendet wurde. Also eine neue, immer noch naive Implementierung:
~~~javascript
function forEach (seq, construct, sorting) {
var result = new Sequence();
for (currentNode in seq) {
var t = new Thread(function () {
var s = contruct(currentNode);
result.insert(currentNode.position, s);
});
t.run();
};
return result.sort(sorting);
};
(Ich weiss, dass Javascript keine Threads kann. Also musste ich mir eine sehr simple API aus dem Arm schütteln, die keine Rücksicht auf Performance und ähnliches nimmt. Ist nur zu Demonstrationszwecken, nicht rumschreien.)
Zwei Änderungen: Zum einen wird für jede Ausführung des Sequenz-Konstruktors ein neuer Thread erstellt, der angenommenerweise gerade auf dem Prozessor-(Kern) läuft, der gerade frei ist. Und zum anderen wird das Resultat nicht mehr einfach an die Resultatssequenz angehängt sondern an die „Position“ des Knotens gestellt. Dies liegt daran, dass wir uns nicht mehr sicher sein können, dass die Threads sich in Reihenfolge zurückmelden. Vielleicht braucht Iterationsschritt 19 einfach länger, wegen einer Verzweigung im Template oder weil es sich den Prozessor mit World of Warcraft teilen muss. Um die Reihenfolge zu wahren hab ich eine insert-Methode erfunden.
Das ist der Knackpunkt. Das Starten der Ausführung der jeweiligen Verarbeitung eines Knotens geschieht hier immer noch in einer Schleife („Da loopt was“™). Aber das konkrete Ausführen und das Sammeln der Resultate nicht mehr. Das ist schon keine klassische Schleife mit einem vorhersehbaren Nacheinander mehr.
Der andere Punkt sind die Variablen ausserhalb der Schleife. In einer klassischen iterativen Schleife kann man auf diese zugreifen, sie verändern und hat dennoch in jeden Iterationsschritt vorhersehbar und berechenbar weil es einen globalen konsistenten Status gibt. Stell Dir mal vor, construct() würde auf Variablen zugreifen, die ausserhalb ihrer selbst liegen. Und nun stell Dir vor:
• Iterationsschritt 2 und 4 wollen gleichzeitig auf eine globale Variable zugreifen oder sie gar verändern.
• Iterationsschritt 16 ist schneller als Iterationsschritt 4 und hat eine globale Variable verändert. Dummerweise braucht Iterationsschritt 4 noch den vorherigen Zustand – die Variable hat diesen aber nicht mehr.
Es gibt haufenweise Methoden, um solche Konflikte zu verhindern, aber alle erfordern noch viel mehr Code und es macht das alles viel, viel komplexer. Und damit nerviger und bug-anfälliger. Und nun stell Dir vor, jede Funktion sei in sich abgeschlossen, kennt nur ihre Parameter und andere Funktionen und verändert nichts ausserhalb. Kleine, zweckbestimmte Arbeiter, die aus ihrer Eingabe eine Ausgabe produzieren und sonst nichts machen. Und komplexere Funktionen sind ebenso kleine Funktionen, die aber mit anderen Funktionen arbeiten.
Das ist meiner Meinung nach einer der Hauptvorteile an Funktionalen Programmiersprachen und mit ein Grund, weswegen die in sehr nerdigen Zirkeln plötzlich wieder hip werden: Die sind sehr einfach zu parallelisieren. Und das ist nicht nur hypothetisch.
Stell Dir mal vor, Du wärst verrückt und hättest das gesamte spiderbare Internet in XHTML normalisiert und in einer einzigen XML-Datei gespeichert. Und nun wolltest Du ein neues XML-Dokument erstellen, dass die Adressen aller Webseiten enthält, die auf http://de.selfhtml.org/ verlinken. Und das in XSLT; ich sag ja: verrückt. ;)
~~~xml
output:sites
<xsl:for-each select="/g:internet/g:page">
<xsl:if test="//xhtml:a[@href = 'http://de.selfhtml.org/']">
output:site
<xsl:attribute name="uri">
<xsl:value-of select="@href"/>
</xsl:attribute>
</output:site>
</xsl:if>
</xsl:for-each>
</output:sites>
Du wärst doch sehr froh, wenn da xsl:for-each einfach parallelisierbar wäre statt einer Schleife, so dass die konkrete Ausführung verteilt laufen könnte. Zum Beispiel auf dem größtem Computercluster der Welt.
Google hat sich ein eigenes Software-Framework geschrieben, dass mit solch funktionalen Methoden solch riesige Berechnungen erstellt wie z.B. den Pagerank zu berechnen. Das Problem wird in kleine, unabhängig voneinander arbeitende Funktionen aufgeteilt und diese mit dann mit einer Funktion ähnlich die for-each parallelisiert. Ähnlich, obwohl dort natürlich noch viel, viel mehr passiert, die Jobs werden auf haufenweise Computer aufgeteilt und es gibt Vorkehrungen dafür, dass da ein Computerknoten abstürzen kann und und und. Aber das Prinzip ist ähnlich. Der Name des Frameworks lautet [MapReduce](http://labs.google.com/papers/mapreduce.html).
[Map()](http://en.wikipedia.org/wiki/Map_%28higher-order_function%29) und [Reduce()](http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29) sind zwei Archetypen von generellen Funktionen die auf Kollektionen (Listen, Arrays arbeiten) und dazu eine weitere beliebige Funktion nutzen. Wenn man xsl:sort weglässt, ist xsl:for-each nichts anderes als map() – es führt eine Funktion auf jedes Element einer Sequenz aus und gibt die andere Sequenz zurück.
`var result = map(seq, construct);`{:.language-javascript} (1)
Es ist \_keine\_ Schleife, weil das wesentliche Element einer Schleife fehlt: Das Nacheinanderfolgen der Ausführung der Funktion. Es ist schlichtweg wurst, in welcher Reihenfolge das geschieht – schließlich kann die Funktion die Welt ausserhalb sich selbst nicht verändern.
(1) In echtem JS 1.6: `var result = seq.map(construct)`{:.language-javascript}
> Übrigens, um dich vielleicht etwas zu verwirren, auch »apply-templates« ist nach dieser Definition eine Schleife. Muss dann ja auch so sein, den prinzipiell gibt es ja zwischen »apply-templates« und »for-each« keinen Unterschied.
Ja. Oder apply-templates ist eine Funktion, die auf gegebene Knoten jeweils passende Funktionen (Templates) anwendet. Soll heissen: Ich sehe inzwischen in jedem XSLT-Konstrukt eine Funktion, weil es ich es nur noch als funktionelle Sprache sehe.
Aber auch wenn ich hier massiv von Parallelisierung rede und stark denke, dass sich die Autoren von XSLT-Prozessoren das auf jeden Fall nutzen, glaube ich nicht, dass das der wesentliche Grund hinter der Erstellung von XSLT/XPath als Funktionale Programmiersprache war. Ich glaube eher, dass das funktionale Programmierparadigma sehr gut auf die Baumstruktur der Eingabe und die Baumstruktur Ausgabe passte. Eine Funktion für den gesamten Baum, die Funktionen auf Teilbäume anwenden, die Funktionen auf Teilbäume anwenden, die Funktionen auf Knoten anwenden. Das ist ein weiterer Teilaspekt der Funktionalen Programmierung, durch die Abschottung und Spezialisierung von Funktionen in der Zusammenarbeit mit generellen Funktion kann man sich immer gut auf Teilaspekte des Problems konzentrieren und kann dadurch einer Vermischung von Top (Dem Großen Ganzen) und Bottom (dem fitzeligen Detail bei der Hand) aus dem Weg gehen und dadurch saubereren Programmcode erhalten. Wobei „sauber“ bei der verfluchten XML-Syntax eher konzeptionell zu begreifen ist. Ist aber nur meine Privattheorie, vielleicht waren die XSLT-Erfinder auch nur Sprachfanatiker. Aber dieser Aspekt der Aufteilung von Problemen in lauter kleinere unabhängige Probleme als passender Programmierstil für XML-Bäume war hier nicht so gut zu erklären wie das Beispiel der Parallelisierung, deswegen musstest Du unter diesem Sermon leiden.
Tim
MudGuard