Für die Verarbeitung von XML und damit für den n-stelligen Baum NTree sind einige einfache Funktionen nötig: das Testen von Knoten auf bestimmte Eigenschaften, das Selektieren von Teilen eines Knotens und das Verändern von Knoten oder Teilen. Diese einfachen Funktionen sind natürlich auch für Teilbäume, also Mengen von Knoten nötig und daher müssen auch Teilbäume getestet, selektiert oder modifiziert werden können. Wenn diese einfachen Funktionen jetzt noch beliebig kombinierbar sind, ergiebt sich ein mächtiges Werkzeug für die Verarbeitung von XML. Da durch die Kombination von den einfachen, vordefinierten Funktionen alle möglichen komplexen Funktionen erzeugt werden, läßt sich die Menge der einfachen Funktionen als Sprache auffassen. Diese Sprache ist speziell für die Verarbeitung von XML definiert, also für ein konkretes Problem und deshalb wird sie auch als Domain Specific Language (DSL) bezeichnet.
Eine DSL ist eine Programmiersprache, die im Gegensatz zu Java oder C++, für ein bestimmtes Problem eingesetzt wird. Häufig ist die Sprache in eine Software-Umgebung eingebunden und wird daher auch als eingebettete Sprache bezeichnet.
Die Haskell XML Toolbox bedient sich diesem Konzept der Domain Specific Language, welches auch in HaXML, einem anderen Haskell XML-Parser, benutzt wurde. Die Unterschiede und Vorteile von der Haskell XML Toolbox zu HaXML werden in Kapitel 5 vorgestellt.
In der Haskell XML Toolbox werden für die eben erwähnten einfachen Funktionen Filter eingesetzt. Um die Filter beliebig zu kombinieren, sind sie alle vom gleichen Typ TFilter bzw. TSFilter. Jeder Filter bekommt als Parameter einen Knoten oder eine Liste von Knoten und gibt eine Liste von Knoten zurück, die je nach Filter auch leer sein kann.
type TFilter node = NTree node -> NTrees node type TSFilter node = NTrees node -> NTrees node
Weil die Filter über den generischen Datentyp NTree definiert sind, lassen sich alle möglichen Bäume unabhängig ob es eine DTD, ein XML-Dokument oder irgendein anderer Baum ist, mit den Filtern verarbeiten. Außerdem ist es für die Entwicklung von einfachen Filtern nicht nötig, über die konkrete Struktur der Knoten-Attribute Bescheid zu wissen.
Test-Filter/Prädikate, also Filter, die Eigenschaften von Knoten überprüfen, haben als Rückgabewert üblicherweise einen Wahrheitswert (Bool), nämlich True oder False. Der Typ TFilter erlaubt aber nur eine Liste von Knoten als Rückgabewert, weshalb die Resultate für die Prädikat-Filter etwas anders definiert wurden, als es von der Aussagenlogik bekannt ist. Hat ein Prädikat den Wert True, gibt der Filter eine Ergebnisliste zurück, das kann z.B. der geprüfte Knoten sein. Bei einer ungültigen Aussage, also bei False, liefert der Filter die leere Menge zurück.
Basierend auf TFilter sind XmlFilter und XmlSFilter definiert, die nur mit dem Datentyp XNode arbeiten. Alle XML-spezifischen Filter sind von diesem Typ.
type XmlFilter = TFilter XNode type XmlSFilter = TSFilter XNode
Die folgende Aufstellung zeigt einige der einfachen allgemeinen Filter, die zum Selektieren, Testen und zum Modifizieren einzelner Knoten in dem n-stelligen Baum geeignet sind. Zwei der wichtigsten Prädikate/Test-Filter sind - angelehnt an die Mathematik - die Nullfunktion und die Identitätsfunktion. Die Nullfunktion stellt das neutrale Element dar. Diese beiden Filter sind entscheidend um mehrere Aussagen/Filter miteinander zu kombinieren.
none :: a -> [b] none _ = []
Der Nullfilter gibt immer die leere Liste zurück.
this :: a -> [a] this n = [n]
Der Identitätsfilter gibt immer eine Ein-Elementige Liste mit dem Übergabeelement zurück.
Die Funktion isOf ermöglicht das allgemeine Testen von Prädikaten.
isOf :: (a -> Bool) -> (a -> [a])
isOf p t
= if p t then [t] else []
isOf bekommt ein Prädikat übergeben und gibt entweder 'this' oder 'none' zurück, je nach Prädikat. Die Funktion wandelt also ein Prädikat in einen Filter um.
isOfNode :: (node -> Bool) -> TFilter node isOfNode p = isOf (p . getNode)
Der Filter isOfNote bekommt auch ein Prädikat übergeben, gibt aber einen Filter zurück, der entweder eine Liste von Knoten oder die leere Liste zurückgibt, je nachdem ob das Prädikat True oder False ist. Die Funktion getNode ist eine Selektor-Funktion. Sie gibt den Knoten des übergebenen Baumes zurück.
getNode :: NTree node -> node
getNode (NTree n _)
= n
Eine weitere wichtige Selektor-Funktion ist getChildren. Sie gibt alle Kindelemente eines Knotens zurück.
getChildren :: NTree node -> NTrees node
getChildren (NTree _ cs)
= cs
Der Filter replaceNode dient zum Ersetzen eines Knotens in einem Baum, ist also ein Modifizierungsfilter. Er bekommt den neuen Knoten übergeben und liefert den editierenden Filter zurück.
replaceNode :: node -> TFilter node
replaceNode n (NTree _ cs)
= [NTree n cs]
Neben den vorgestellten einfachen Filtern gibt es noch eine Reihe weiterer Filter, die das Modifizeren von Knoten ermöglichen.
Um eine Domain Specific Language zu erhalten, reicht es nicht aus, die Worte zu definieren, sondern es muss auch die Möglichkeit geschaffen werden die Worte zu kombinieren, so dass Sätze gebildet werden können. Bei der DSL der Haskell XML Toolbox bilden die einfachen Filter die Worte der Sprache und zum Verbinden der Worte zu Sätzen bietet die Haskell XML Toolbox Filter-Kombinatoren an. Filter-Kombinatoren sind Funktionen, die andere Funktionen kombinieren. In der Funktionalen Programmierung werden solche Funktionen "Funktionen höherer Ordnung" genannt (s. Abschnitt 1.5). Durch die Kombination von den zuvor vorgestellten einfachen Filtern lassen sich so neue und komplexe Filter erzeugen.
Da alle Filter außerdem den selben Typ TFilter besitzen, lassen sie sich beliebig kombinieren. Der Ansatz, Filter-Kombinatoren einzusetzten, ist an HaXML angelehnt.
Wie bei den Filtern kann auch bei den Kombinatoren ein Bezug zu der Aussagenlogik hergestellt werden. Zu den zwei wichtigsten Kombinatoren gehören zum einen der `o`-Kombinator, der das logische Und bei der Kombination von Prädikatfiltern darstellt. Der andere wichtige Kombinator ist der +++-Kombinator, der das logische Oder darstellt. Bei dem `o`-Kombinator handelt es sich um die "Irish composition", die auch von den 'pipes' aus Unix bekannt ist. Bei den 'pipes' geht es darum, den Output eines Programms an den Input eines anderen Programms weiterzugeben. Die selbe Aufgabe hat die "Irish composition" bei den Filtern, indem das Ergebnis eines Filters an einen zweiten Filter weitergegeben wird. Der +++-Operator vereinigt das Ergebnis zweier Filter dagegen sequenziell, die Filter werden also "gleichzeitig" auf den Baum angewendet. Bei den Kombinatoren wird ein weiteres Feature von Haskell ausgenutzt, nämlich die Möglichkeit, eigene Infix-Operatoren zu definieren. Viele Filter-Kombinatoren stehen als Infix-Operator zu Verfügung, so dass eine natürliche, aus der Mathematik bekannte Schreibweise möglich ist.
Definition von 'Und' und 'Or':o :: (a -> [b]) -> (c -> [a]) -> (c -> [b]) f `o` g = concatMap f . g (+++) :: (a -> [b]) -> (a -> [b]) -> (a -> [b]) f +++ g = \ t -> f t ++ g t
Den `o`-Operator gibt es auch noch in der "umgedrehten" Variante. Der .>-Operator ist so definiert, dass erst f, und dann g ausgeführt wird, was also der Irish Composition von links nach rechts entspricht.
(.>) :: (a -> [b]) -> (b -> [c]) -> (a -> [c]) f .> g = g `o` f
Zur Auswahl zwischen zwei Filtern wird der `orElse`-Operator eingesetzt. Je nach Filter wird entweder der erste oder der zweite übergebene Filter auf den Baum angewendet.
orElse :: (a -> [b]) -> (a -> [b]) -> (a -> [b])
f `orElse` g
= \ t-> let
res = f t
in
if null res
then g t
else res
Ein weiterer Auswahl-Filter ist der "if-then-else"-Filter, der als `iff`-Operator definiert wurde. Der erste Paramter ist das if-Prädikat, der zweite der then-Filter und der dritte Parameter der else-Filter. Zurückgegeben wird dann der passende Auswahlfilter.
iff :: (a -> [c]) -> (a -> [b]) -> (a -> [b]) -> (a -> [b])
iff p f g
= \ c -> if (satisfies p) c then f c else g c
Der letzte hier vorgestellte Auswahl-Filter ist der `when`-Operator. Der Filter bekommt ein Prädikat und einen Filter übergeben. Wenn das Prädikat wahr ist, wird der Filter angewendet, sonst wird 'this' zurückgegeben.
when :: (a -> [a]) -> (a -> [a]) -> (a -> [a])
f `when` g
= iff g f this
In der folgenden Aufstellung sind noch einige weitere Kombinatoren aufgelistet, die nicht genauer erklärt werden sollen.
| Kombinator | Beschreibung |
|---|---|
| neg f | Die Negation. Gibt genau den Filter zurück, bei dem f falsch ist. |
| f /> g | Interior Search; liefert die innere Struktur. |
| f </ g | Exterior Search; liefert die äußere Struktur. |
| f `whenNot` g | Das Komplement von `when`. Eine Kurzform von f `when` neg g |
| f `guards` g | When das Prädikat f wahr ist, wird g angewendet, sonst wird none zurückgegeben. |
Es gibt noch viele weitere Filter-Kombinatoren, die hier nicht aufgeführt werden. Außerdem sind alle einfachen Filter und Kombinatoren auch als monadische Filter vorhanden, so dass diese direkt auf I/O-Operationen angewandt werden können.
Bisher wurden nur solche Filter vorgestellt, die sich nur auf ein Element im Baum und maximal auf dessen Kindelemente beziehen. In den häufigsten Fällen sollen aber bestimmte Modifikationen oder Tests auf den ganzen Baum angewendet werden. Dafür bietet die Haskell XML Toolbox spezielle rekursive Filter, die die Baumstruktur traversieren und die verschiedenen einfachen Filter auf alle Elemente des Baumes anwenden. Für das Traversieren von Bäumen gibt es zwei Strategien: Top-Down und Bottom-Up. Bei Top-Down wird die Baumstruktur vom obersten Knoten bis zur Wurzel durchlaufen, bei Bottom-Up wird von der Wurzel zur Spitze traversiert.
Zum Suchen bestimmter Knoten im Baum gibt es die Filter deep und deepest. deep ist ein Top-Down, deepest ein Bottom-Up Filter.
deep :: TFilter node -> TFilter node
deep f
= f `orElse` (deep f `o` getChildren)
deepest :: TFilter node -> TFilter node
deepest f
= (getChildren .> deepest f) `orElse` f
Beide Filter stoppen die Suche, wenn der Filter f ein positives Ergebnis liefert. Um bestimmte Knoten in einem Baum zu bearbeiten, gibt es wieder zwei Filter für die Top-Down und Bottom-Up Traversierung.
processBottomUp :: TFilter node -> TFilter node
processBottomUp f
= processChildren (processBottomUp f) .> f
processTopDown :: TFilter node -> TFilter node
processTopDown f
= f .> processChildren (processTopDown f)
processBottomUp und processTopDown liefern den Filter zurück, der den Filter f auf alle Knoten im Baum anwendet.
Der rekursive Filter multi wendet den jeweiligen Filter auf den gesamten Baum an und liefert das Ergebnis zurück. Er kann z.B. genutzt werden, um alle Knoten mit einer bestimmten Eigenschaft zu extrahieren.
multi :: TFilter node -> TFilter node
multi f
= f +++ (getChildren .> multi f)
Auch die Beschreibung der rekursiven Filter hat wieder nur einen kleinen Teil der gesamten zur Verfügung stehenden Filter vorgestellt. Aber alle weiteren Filter bedienen sich am selben Konzept und basierend meistens auf den hier erwähnten Filtern.
Nachdem nun das Konzept der Domain Specific Language in der Haskell XML Toolbox vorgestellt wurde, soll ein einfaches Beispiel zeigen, wie einfach es ist, eigene Filter zu implementieren. Das folgende Beispiel beschreibt und zeigt, wie man alle XText-Elemente aus einem XML-Baum entfernt. Dabei werden die einfachen Filter, die Filter-Kombinatoren und die rekursiven Filter eingesetzt.
Um alle XText-Elemente aus einem XML-Baum zu entfernen, muss zunächst ein Prädikat definiert werden, welches testet, ob ein Knoten ein Filter ist, oder nicht.
Das Prädikat isXTextNode:isXTextNode :: XNode -> Bool isXTextNode (XText _) = True isXTextNode _ = False
Die Funktion isXTextNode kann aber noch nicht als Filter eingesetzt werden, weil sie nicht vom Typ TFilter ist. Nur dann kann sie mit anderen Filtern kombiniert werden und mit Hilfe der rekursiven Filter auf einen kompletten XML-Baum angewendet werden. Daher wird auf dem Prädikat isXTextNode der Filter isXText definiert.
Der Filter isXText:isXText :: XmlFilter isXTexT = isOfNode isXTextNode
Der Filter benutzt die Selektor-Funktion isOfNode, die eine Liste mit Knoten zurückgibt, bei denen das Prädikat True ergab.
Als nächstes wird der Filter zum Entfernen von XText-Knoten definiert. Der Filter bekommt einen Knoten geliefert und gibt die leere Liste zurück, wenn der Knoten ein XText ist, andernfalls liefert er eine Liste mit dem übergebenen Knoten zurück. removeXText kombiniert die beiden einfachen Filter none und isXText mit dem Kombinator `when`.
Der Filter removeXText:removeXText :: XmlFilter removeXText = none `when` isXText
Nachdem nun das Prädikat, der einfache Filter und der Filter zum Entfernen definiert wurden, muss das Löschen der XText-Elemente nur noch auf einen kompletten Baum ausgeführt werden und damit wird jetzt ein rekursiver Filter benötigt. Hierfür wird der Filter processBottomUp verwendet, der einen übergebenen Filter auf den Baum von der Wurzel bis zur Spitze anwendet. Das Ergebnis ist dann ein neuer XML-Baum, aus dem alle XText-Knoten entfernt wurden.
Der Filter removeAllXText:removeAllXText :: XmlFilter removeAllXText = processBottomUp removeXText
Das Beispiel hat gezeigt, wie einfach es ist, aus einfachen Filtern neue und komplexe Filter zu konstruieren, wobei alle Funktionen zur eigentlichen Verarbeitung dem Entwickler verborgen bleiben.