Funktionale Programmierung: Ausdrucksauswertung mit Variablen

Ausdrucksauswertung	und Monaden für Ausdrücke mit Variablen
Gegeben	Eine einfache Datenstruktur für arithmetische Ausdrücke mit ganzen Zahlen wie in der ersten Aufgabe über Monaden und ein Interpretierer in monadischer Form mit Fehlerbehandlung

Kern	-Erweiterung der Monade mit Ausnahmebehandlung war die Erweiterung des Datentyps für das Resultat:
	data Result a = Val { val :: a } \| Exc { exc :: String } deriving (Show) instance Monad Result where return = ... (Exc e) >>= _ = ... (Val v) >>= g = ...
Erweiterung	der Ausdruckssprache
	Die Sprache soll um Variablen und Variablen-Definitionen (let-Ausdrücke) erweitert werden. Dabei soll der Code des gegebenen Interpretierers möglichst nicht verändert, sondern nur erweitert werden.
	In dem gegebenen Beispiel ist die Bedeutung eines Ausdrucks durch eine Funktion eval :: Expr -> Result Int definiert worden. Diese Technik der Semantikdefinition wird als Sprachdefinition mit Hilfe einer denotationellen Semantik bezeichnet. Für eine Reihe von realen Programmiersprachen gibt es Semantikdefinitionen in dieser Form.
	Die Sprache soll in folgender Form erweitert werden:
	data Expr = Const Int \| Var Id -- NEU \| Let Id Expr Expr -- NEU \| Binary BinOp Expr Expr deriving (Show) data BinOp = Add \| Sub \| Mul \| Div \| Mod deriving (Eq, Show) type Id = String
	Als einfache Ausdrücke sind jetzt Variablen, repräsentiert durch einen Namen, zugelassen. Mit dem let-Ausdruck können Teilergebnisse benannt werden. Dieses entspricht lokalen Variablen in realen Programmiersprachen, die bei ihrer Deklaration initialisiert werden, aber wärend der Ausführung nicht verändert werden.
	Die Bedeutungsfunktion von solchen Programmen hängt natürlich von den Werten der freien Variablen in einem Ausdruck ab. Für das Auswerten wird also eine Wertebelegung der Variablen benötigt. Diese Tabelle der Wertebelegungen wird als Umgebung (engl. Environment) bezeichnet.
	Die Bedeutung eines Ausdrucks ist also eine Funktion von dem Environment auf einen Wert (eine Zahl oder eine Fehlermeldung).
	Daraus ergibt sich folgende Änderung der sogenannten semantischen Bereiche (semantic domains):
	data Result a = Res { unRes :: Env -> ResVal a } data ResVal a = Val { val :: a } \| Exc { exc :: String } deriving (Show) type Env = [(Id, Int)]
	Das Environment Env ist hier als einfache Liste von Name-Wert-Paaren realisiert worden. lookup ist eine vordefinierte Funktion, um in einer solchen Liste einen Wert zu finden. Mit dieser Liste kann eine einfache kellerartige Verwaltung der lokalen Variablen realisiert werden.
Aufgabe	Der Typ Result muss eine Instanz von Monad und MonadError bekommen. Zusätzlich muss natürlich das Environment zugreifbar und erweiterbar gemacht werden. Hierfür gibt es eine Schnittstelle MonadReader, die zu implementieren ist.
	instance Monad Result where return x = ... (Res f) >>= g = ... instance MonadError String Result where throwError s = ... catchError (Res f) handler = ... instance MonadReader Env Result where ask = ... local f c = ...
eval	muss für die beiden hinzugekommenen Ausdrucksarten definiert werden. Zu beachten ist, dass in den Ausdrücken undefinierte Variablen vorkommen können, es also einen neuen Fehlerfall gibt.
	eval (Var id) = do ... eval (Let id e1 e2) = do ...
Starten	einer Auswertung erfordert eine Umgebung. Dafür kann man sich eine einfache Funktion entwickeln:
	evalEnv :: Expr -> Env -> ResVal Int evalEnv = ...

Ausdrucksauswertung mit Variablen

Aufgabe