»Der Laie staunt, der Fachmann wundert sich.« Zufallszahlen in XSLT sind soetwas wie die Quadratur des Kreises. Warum? Eine der absoluten Grundlagen funktionaler Programmiersprachen, zu denen auch XPath und XSLT gehören, ist der Verzicht auf Seiteneffekte, d.h. das Ergebnis einer Operation oder Funktion hängt ausschließlich von den übergebenen Parametern ab und nicht von anderen Programmzuständen, die beispielsweise in Variablen gespeichert und extern verändert werden könnten. Ebenso werden während der Berechnung einer Funktion oder der Ausführung eines Templates keine Programmzustände geändert. Der Vorteil dieser Restriktion ist, dass Programmzustände wesentlich leichter vorhergesagt und damit die Ausführung von Programmen gut optimiert werden können: wenn bspw. einmal log10($input) berechnet wurde, kann der Prozessor beim nächster Auftreten von log10($input) auf das letzte Ergebnis zurückgreifen, weil sich $input per funktionalem Paradigma nicht ändern darf. Daraus folgt, dass eine Funktion random(), die bei jedem Aufruf ein anderes Ergebnis liefert, ein Paradox ist.
XSLT und XPath sind (manchmal zum Verzweifeln) strikt in Bezug auf Seiteneffektfreiheit. Ein Loch im System – das sogar durch den XSLT-Standard gedeckt ist – fand aber Vladimir Nesterovsky: generate-id() muss für jeden Knoten eine andere ID liefern; das schließt im Stylesheet generierte temporäre Knoten ein. Eine Funktion, die einen temporären Knoten erzeugt und für diesen generate-id() aufruft, gibt deshalb bei jedem Aufruf ein anderes Ergebnis zurück:
<xsl:stylesheet version="2.0" xmlns:f="data:,f" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> <xsl:template match="/"> <xsl:message select=" for $i in 1 to 8 return f:fun()"/> </xsl:template> <xsl:function name="f:fun" as="xs:string"> <xsl:variable name="x">!</xsl:variable> <xsl:sequence select="generate-id($x)"/> </xsl:function> </xsl:stylesheet> |
Das Ergebnis mit Saxon ist bspw. tt2 tt3 tt4 tt5 tt6 tt7 tt8 tt9.
Damit kann man nun einen Pseudozufallsszahlengenerator füttern. Ich habe mich für einen linearen Kongruenzgenerator entschieden, weil er sich recht einfach implementieren lässt:
<xsl:function name="intern:linear-congruential-generator" as="xs:integer+"> <xsl:param name="length" as="xs:integer"/> <xsl:param name="vortrag" as="xs:integer+"/> <xsl:choose> <xsl:when test="$length eq 0"> <xsl:sequence select="$vortrag[position() gt 1]"/> </xsl:when> <xsl:otherwise> <xsl:sequence select="intern:linear-congruential-generator($length - 1, ($vortrag, (1103515245 *$vortrag[last()] + 12345) mod 4294967296) )"/> </xsl:otherwise> </xsl:choose> </xsl:function> |
Die numerischen Konstanten werden so bei der glibc verwendet, ich habe sie einfach übernommen. Die Funktion ist rekursiv, sie fügt bei jedem Aufruf an die vortrag-Sequenz (die mit einem möglichst zufälligem Startwert – englisch seed – initialisiert wird) eine Pseudozufallszahl an. Der Startwert wird aus der Rückgabe entfernt; so kann man diese Funktion (mit einer length von 1) zum einfachen Umwandeln eines Eingabewertes benutzen. intern:linear-congruential-generator(5, 1) ergibt bspw. 1103527590 2524885223 662824084 3295386429 4182499122. Dieses Ergebnis ist reproduzierbar, d.h. jeder Aufruf mit den Parametern 5, 1 liefert genau diese Sequenz zurück.
An diesem Punkt kommt die oben besprochene Funktion zum Erzeugen veränderlicher Werte ins Spiel. Ich habe sie um eine Verarbeitung von Datum und Uhrzeit ergänzt, damit bei jedem Aufruf des Stylesheets neue Pseudozufallswerte erzeugt werden:
<xsl:function name="intern:seed" as="xs:integer"> <xsl:param name="seed" as="xs:anyAtomicType"/> <xsl:variable name="integer-of-seed" as="xs:integer" select="if ($seed castable as xs:integer) then xs:integer($seed) else sum(string-to-codepoints(string($seed) ) )"/> <xsl:variable name="integer-of-current-date" as="xs:integer" select="xs:integer(format-dateTime(current-dateTime(), '[Y][d][H][m][s][f]') )"/> <xsl:variable name="temporary_node" as="text()">?</xsl:variable> <xsl:variable name="sequence-of-weighted-id-integers" as="xs:integer+"> <xsl:for-each select="string-to-codepoints(generate-id($temporary_node) )"> <xsl:sequence select="intern:power(xs:integer(10), position()) * xs:integer(.)"/> </xsl:for-each> </xsl:variable> <xsl:sequence select="intern:linear-congruential-generator(1, $integer-of-seed + $integer-of-current-date + xs:integer(sum($sequence-of-weighted-id-integers) ) )"/> </xsl:function> |
Disclaimer: Ich bin kein Mathematiker und kann deshalb die Güte der Zufallszahlen nicht beurteilen. Sie eignen sich sicher nicht für kryptographische Anwendungen. Auf der anderen Seite zeigt ein Plot eine recht gleichmäßige Verteilung, so dass sie für die meisten Zwecke ausreichen dürften.
Bei den ersten Tests sahen die Ergebnisse sehr gut aus, aber dann schlug die Optimierung von Saxon zu: for $i in 1 to 100 return string(xsb:random(1)) lieferte 100 Mal den selben zufälligen Wert. Die Lösung ist, die Evaluierung der Funktion zu erzwingen, indem als Argument ein möglichst veränderlicher Wert übergeben wird. Das ist hier naheliegend die Zählvariable $i: for $i in 1 to 100 return string(xsb:random($i)) liefert wieder recht zufällige Werte. Aus pädagogischen Gründen habe ich deshalb in der XSLT-SB keine xsb:random()-Funktion ohne Argument implementiert. Natürlich könnte ein sehr intelligenter Prozessor auch hier wieder optimieren, aber je schwerer man ihm das macht, umso unwahrscheinlicher ist sein Erfolg.
siehe auch
- Dimitre Novatchev: Casting the Dice with FXSL: Random Number Generation Functions in XSLT (englisch)
