Der Evaluierer ist recht einfach gehalten, er kann eine Konstante oder eine Division auswerten. Dies erkennt man auch an der Datenstruktur:
data Term = Con Int | Div Term Term
Mit der Funktion eval kann nun das Ergebnis eines Termes
berechnet werden:
eval :: Term -> Int eval (Con x) = x eval (Div t u) = (eval t) `div` (eval u)
Wird eine Konstante (Con x) ausgewertet, ist das Ergebnis x. Bei
einem Divisonsterm (Div t u) wird zuerst der linke Term t, dann
der rechte Term u ausgewertet und dann das Divisionsergebnis zurückgeliefert.
Nun haben wir zwei Beispiel-Terme:
answer,wrong :: Term answer = (Div (Div (Con 1972) (Con 2)) (Con 23)) wrong = (Div (Con 2) (Div (Con 1) (Con 0)))
Die Auswertung von answer führt zu:
? eval answer
42
Doch die Auswertung von wrong führt zu einem unkontrolliertem
Programmabbruch, da der Term eine Division durch null beinhaltet. Die Lösung des
Problems ist eine Exceptionbehandlung.
Eine neue Datenstruktur ist nötig:
data Exc a = Raise Exception | Return a type Exception = String
Eine Exception Exc kann entweder eine ausgelöste Exception
Raise Exception oder das Ergebnis vom Typ a Return a
sein.
Und so sieht der modifizierte Evaluierer aus:
evalExc :: Term -> Exc Int
evalExc (Con x) = Return x
evalExc (Div t u)
= h (evalExc t)
where
h (Raise e) = Raise e
h (Return x) = h'(evalExc u)
where
h' (Raise e) = Raise e
h' (Return y)
= if y == 0
then Raise "Division by zero"
else Return (x `div` y)Beim ersten Blick fällt sofort auf, dass die kurze Struktur des Basisevaluierers (3 Zeilen) nun länglich (13 Zeilen) und vollkommen zerstört ist. Dies liegt an der Überprüfung, ob eine Exception schon ausgelöst wurde.
Die Auswertung einer Konstanten ist gleich geblieben, da dort nicht festgestellt werden kann, ob durch null dividiert wird.
Bei der Auswertung des Divisionsterms wird wieder zuerst der linke Teilterm ausgewertet und das Ergebnis überprüft. Handelt es sich um eine ausgelöste Exception, dann wird diese weiter nach oben durchgereicht und abgerbrochen, handelt es sich um einen Wert, so wird der rechte Teilterm ausgewertet und das Ergebnis genauso überprüft. Ist keine Exception ausgelöst worden, wird nun anhand des Rückgabewerts eine Exception oder das Divisionsergebnis zurückgeliefert.
Der Aufruf mit dem falschen Term:
? evalExc wrong
exception: Division by zero
Eine andere Erweiterung für den Evaluierer wäre ein Trace-Output, der jede Auswertungszeile und dessen Ergebnis ausgibt. Dies wird durch Sammeln aller Zeilen in einem String erreicht. Deshalb wird nun das Ergebnis um ein Output erweitert:
newtype Out a = MkOut(Output,a) type Output = String
Der Rückgabewert der eval-Funktion ist nun ein Tupel aus
Ergebnis des Terms und der dazugehörige Output.
Es ist eine zusätzliche Funktion nötig, die aus einem Term und dessen Ergebnis ein String zusammenstellt:
line :: Term -> Int -> Output line t x = "Term: " ++ show t ++ " ergibt: " ++ show x ++ "\n"
Der veränderte Evaluierer sind nun wie folgt aus:
evalOut :: Term -> Out Int evalOut (Con x) = MkOut(line (Con x) x,x) evalOut (Div t u) = MkOut(ox ++ oy ++ line (Div t u) z,z) where MkOut (ox,x) = evalOut t MkOut (oy,y) = evalOut u z = x `div` y
Die Auswertung einer Konstanten liefert ein Tupel mit der Zahl und der Stringrepräsentation der Konstanten.
Bei der Auswertung eines Divisionsterms werden wieder die beiden Teilterme ausgewertet. Die Stringrepräsentationen ox und oy werden zusammmen mit der aktuellen Auswertungszeile konkateniert und die Ergebnisse x und y voneinander dividiert.
Der Aufruf mit dem richtigen Term sieht nun so aus:
? evalOut answer
Term: (Con 1972) ergibt: 1972
Term: (Con 2) ergibt: 2
Term: (Div (Con 1972) (Con 2)) ergibt: 986
Term: (Con 23) ergibt: 23
Term: (Div (Div (Con 1972) (Con 2)) (Con 23)) ergibt: 42
Ergebnis: 42Es ist festzuhalten, dass auch bei dieser Modifikation die Basisstruktur stark verändert wurde.
Als letztes Beispiel wird nun der Evaluierer um einen Zustand erweitert. Dieser Zustand soll zählen, wie häufig eine Division durchgeführt wurde.
Der erste Ansatz, den wir aus imperativen Programmiersprachen verwenden würden, ist die Einführung einer globalen Variablen, die pro Division inkrementiert wird. Dies ist jedoch bei funktionalen Programmiersprachen nicht realisierbar, da update-Zuweisungen nicht möglich sind. Deshalb muss der Zustand auf parameterbasis durchgeschleift werden.
Die Datenstruktur sieht nun wie folgt aus:
newtype St a = MkSt(State -> (a,State)) type State = Int
Das Ergebnis des Evaluierers ist nun eine Funktion. Hier wird nun die grundsätzliche Ansicht einer Funktion ausgenutzt. Eine Funktion ist nichts anderes als ein Zustandstransformator, der einen Anfangszustand bekommt und einen Endzustand zurückliefert. Diese Funktion erhält auch einen Zustand als Parameter und liefert ein Tupel mit Endzustand und Ergebnis zurück.
Nun wird wieder eine Funktion nötig, die die Ergebnisfunktion mit einem Zustand aufruft:
apply :: St a -> State -> (a,State) apply (MkSt f) s = f s
Der modifizierte Evaluierer sieht nun wie folgt aus:
evalSt :: Term -> St Int evalSt (Con x) = MkSt f where f s = (x,s) evalSt (Div t u) = MkSt f where f s = (x `div` y, s'' +1) where (x,s') = apply (evalSt t) s (y,s'') = apply (evalSt u) s'
Bei der Auswertung des Konstantenterms wird eine Funktion zurückgeliefert, die die Konstate und den als Parameter der Fuktion übergebene, unveränderte Zustand als Tupel zurückliefert.
Bei einem Divisionsterm wird auch eine Funktion erstellt. Wieder wird der
linke Teilterm ausgewertet und die Ergebnisfunktion wird mit
apply und dem Zustand s aufgerufen und liefert ein Tupel mit
Ergebnis und neuen Zustand s' zurück. Mit diesem neuen Zustand wird das Ergebnis
des rechten Teilterms aufgerufen und man erhält einen veränderten Zustand
s''. Dieser wird dann inkrementiert, da eine Division durchgeführt wurde, und
mit dem Divisionsergebnis zurückgegeben.
Als letztes fehlt noch, wann die Ergebnisfunktion der Evaluierung mit dem
Initialzustand aufgerufen wird. Dies geschieht in der
show-Funktion.
instance Show a => Show (St a) where
show f = "value: " ++ show x ++ "\ncount: " ++ show s
where (x,s) = apply f 0
? evalExc answer
value: 42
count: 2
Was für Probleme sind zu erkennen bei diesen Beispielen?
Lösung: Evaluierer mit Hilfe von Monaden entwickeln.