Metaprogrammierung mit Template Haskell

4 Anwendungsbeispiele

In diesem Kapitel werden einige Beispiele zur Verdeutlichung der Einsatzmöglichkeiten von Template Haskell vorgestellt, die sich an der eingangs zu dieser Arbeit genannten Motivation orientieren.

4.1 Bedingte Kompilierung

Aufgrund der strengen Typisierung von Haskell ist es nicht möglich, einer Funktion mehrer mögliche Resultattypen zuzuweisen. Eine Funktion, die in Abhängigkeit eines bestimmten Parameters entweder eine Zahl oder einen String zurückgibt ist daher nicht zulässig, kann aber unter Verwendung sog. Dependent Types konstruiert werden. Der folgende Code zeigt, wie eine solche Funktion aber auch mithilfe von Template Haskell realisiert werden kann:

```
mk42 :: Bool -> ExpQ
```
```
mk42 True = [|"zweiUndVierzig"|]
```
```
mk42 False = [|42|]
```

Der Idee besteht hierbei darin, dem Ergebnistyp der Funktion einfach den allgemeinen Typ ExpQ zuzuweisen und die unterschiedlichen Ergebnisse in Quasi-Quotes einzuwickeln. Der folgende Aufruf zeigt, dass der Resultattyp von mk42 erst beim Splice festgelegt wird:


> ( $(mk42 True) , $(mk42 False) )
("zweiUndVierzig", 42)

4.2 Unrolling von Algorithmen

Mit Unrolling ist hier die Ausführung eines Algorithmus zur Compilezeit gemeint. Insbesondere bei recheninstensiven Algorithmen kann dadurch die Rechenzeit in die Compilezeit verlagert werden. Im Folgenden soll eine Potenzfunktion pow konstruiert werden, die zu einer gegebenen Zahl x die n-te Potenz berechnet. Eine einfache und naheliegende Funktion kann in Haskell wie folgt realisiert werden:

```
pow :: Integer -> Integer -> Integer
```
```
pow x 0 = 1
```
```
pow x n = x * pow x (n-1)
```

Durch die rekursive Definition der Funktion kann der sich bildende Aufruf-Stack für große Exponenten stark anwachsen und somit zu Ressourcenproblemen bezogen auf die Laufzeit und den Speicherverbrauch führen. Die Idee besteht nun darin, unter Verwendung von Template Haskell diese Rekursionen in die Compilezeit auszulagern. Die folgende Defition pow' wandelt die rekursiven Aufrufe dafür in geschachtelte Lambda-Ausdrücke um.

```
pow' :: Int -> ExpQ
```
```
pow' 0 = [| \x -> 1 |]
```

pow' n | n > 0 = [| \x -> x * $(pow (n-1)) x |]

Man erkennt schnell, dass der entstehende Ausdruck der Form (\x1 ->(x1 * \x2 ->(x2 * .....) ) ) x zur Laufzeit, nach wie vor zum Anlegen eines aufwändigen Aufrufstacks führt. Der Grund dafür ist, dass jede Lambda-Funktion eine eigene neue Pattern-Variable erzeugt. Durch die Angabe des Compiler-Flags -ddump-splices ist es möglich, sich beim Kompiliervorgang die Aufrufstruktur der Splices und den so enstehenden Syntaxbaum anzeigen zu lassen. Die folgende Abbildung zeigt den Syntaxbaum für die fünfte Potenz:


  pow 5
======>
  \ x[a1S1]
      -> (x[a1S1]
        `GHC.Num.*`
          \ x[a1S2]
              -> (x[a1S2]
                `GHC.Num.*`
                  \ x[a1S3]
                      -> (x[a1S3]
                        `GHC.Num.*`
                          \ x[a1S4]
                              -> (x[a1S4]
                                `GHC.Num.*`
                                  \ x[a1S5] -> (x[a1S5] `GHC.Num.*` \ x[a1S6] -> 1 x[a1S5])
                                    x[a1S4])
                            x[a1S3])
                        x[a1S2])
            x[a1S1])

Um eine echte Laufzeit- und Speicherverbesserung zu erreichen, kann man die überflüssigen Lambda-Ausdrücke im Template durch eine geschachtelte Multiplikation ersetzen, wie im Folgenden ersichtlich.

-- Hilfsfunktion zum Erzeugen der geschachtelten Multiplikation

```
prod :: ExpQ -> Int -> ExpQ
```
```
prod x 0 = [| 1 |]
```

prod x n | n > 0 = [| $x * $(prod x (n-1)) |]

```
 
```
```
pow2' :: Int -> ExpQ
```
```
pow2' n = [| \x -> $(prod [|x|] n) |]
```

Die Hilfsfunktion prod generiert die Zuweisung für die Lambda-Funktion von pow'. prod übernimmt für die vollständige Abwicklung der Rekursionen zur Compilezeit. Das Ergebnis - eine große verkettete Multiplikation - wird dann der einen Lambda-Funktion von pow' zugewiesen, für die sich nach der Auswertung folgender Ausdruck ergibt: (\x1 -> x1 * (x1 * ..... (x1 * 1)) ) x. Auch hier kann man sich den Syntaxbaum anzeigen lassen:


  pow2' 5
======>
  \ x[a1RF]
      -> (x[a1RF]
        `GHC.Num.*`
          (x[a1RF]
          `GHC.Num.*`
           (x[a1RF]
           `GHC.Num.*`
             (x[a1RF] `GHC.Num.*` (x[a1RF] `GHC.Num.*` 1)))))

Anhand der beiden gezeigten Definitionen der Potenzfunktion wird ersichtlich, dass korrekte Metaprogramme nicht unbedingt auch zu optimalen Objektprogrammen führen. Zwar berechnen beide Funktionen das richtige Ergebnis, allerdings ist pow2' wesentlich effizienter, denn: Bei der Version mit den Lambda-Ausdrücken führte das Pre-Expansions-Binding dazu, dass für x zunehmend neue Variablen eingeführt wurden.

4.3 Erweiterte Abstraktionsmechanismen

In Haskell ist es standardmäßig nicht möglich, Tupel beliebiger Länge zu verarbeiten, wie dies bspw. bei Listen der Fall ist. Will man bspw. eine Funktion zum Zugreifen auf das n-te Element eines Tupels definieren, so müsste man, je nach Anzahl der zu erwartenden Tupelelemente, einen Tupel-Pattern der Art (a1,a2,a3,...) händisch angeben. Mithilfe von Template Haskell ist es möglich, diese Aufgabe durch integer-indizierte Funktionen an den Compiler zu delegieren, wie der folgende Code zeigt.

```
sel :: Integer -> Integer -> ExpQ
```
```
sel i n = lamE [pat] expr
```
```
          where 
```

             pat  = tupP [varP $ mkName $ "a" ++ (show i) | i <- [1..n]]

             expr = varE $ mkName $ "a" ++ (show i)

Die Signatur in der ersten Zeile sagt aus, dass die Funktion sel zwei Int Parameter erwartet. Der erste Parameter i gibt den Index des Tupel-Elements an, auf das zugegriffen werden soll. Der zweiter Parameter n gibt die Größe des zu verarbeitenden Tupels an. In Zeile vier werden mithilfe einer List-Comprehension die Tupel-Variablen a₁ - a_n generiert. In Zeile fünf wird ein einfacher Ausdruck (varE) mit dem Namen a_i erzeugt, welcher somit an die entsprechende Variable a_i im Tupel-Pattern gebunden wird.

Liste konvertieren in ein Tupel

In diesem Beispiel wird gezeigt, wie man eine Liste der Größe n in ein n-elementiges Tupel konvertiert. Die Idee besteht hierbei darin, eine Lambda-Funktion zu konstruieren, welche eine Liste mit der maximalen Länge n als Parameter auf ein Tupel der Größe n abbildet. Jedes Tupelfeld beinhaltet dabei eine Funktion, die indiziert auf die übergebene Liste liste zugreift, d.h.: Das erste Feld des Tupels gibt den ersten Listeneintrag (liste !! 0) wieder, das zweite Feld des Tupels den zweiten Listeneintrag (liste !! 1) u.s.w. Für eine konkrete Liste der Länge drei ist also folgende Lambda-Funktion zu konstruieren:

\liste -> (liste !! 0, liste !! 1, liste !! 2)

Folglich muss zunächst wieder bekannt sein, wie lang die umzuwandelnde Liste ist, damit das entsprechend große Tupel konstruiert werden kann. Die im folgenden Code definierte Funktion tuple, zum Konvertieren einer Liste, erwartet daher einen Parameter n, der die Länge der Liste angibt.

```
tuple :: Int -> ExpQ
```

tuple n = [|\list -> $(tupE (exprs [|list|])) |]

```
      where
```

          exprs list = [ infixE (Just (list))

                                (varE $ mkName "!!")

                                (Just (litE $ integerL (toInteger num)))

                            | num <- [0..(n - 1)]

```
                       ]
```

In der zweiten Zeile wird mithilfe des Quasi-Quotings eine lambda-Funktion erzeugt. Die rechte Seite der Funktion errechnet sich durch einen Splice zur Compile-Zeit. Innerhalb des Splices wird mithilfe der Funktion tupE ein Tupel erzeugt, wobei die Liste der Tupel-Variablen von einer Funktion exprs generiert wird. Die Funktion exprs konstruiert dabei mithilfe einer List-Comprehension die Indizes 0 - n-1, welche die Funktion infixE wiederum zur Erzeugung der Parameter der Funktion !! (indizierter Zugriff) benötigt.