Evaluierer ohne Monad


... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ...

Übersicht: Evaluierer ohne Monad


Basisevaluierer

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.

[ nach oben ]


Evaluierer mit Exceptions

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

[ nach oben ]


Evaluierer mit Trace-Output

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: 42

Es ist festzuhalten, dass auch bei dieser Modifikation die Basisstruktur stark verändert wurde.

[ nach oben ]


Evaluierer mit States

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

[ nach oben ]


Probleme

Was für Probleme sind zu erkennen bei diesen Beispielen?

Lösung: Evaluierer mit Hilfe von Monaden entwickeln.


... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ... [ nach oben ] ...