Funktionale Programmierung: Ausdrucksauswertung mit Monaden

Ausdrucksauswertung	und Monaden
Gegeben	Eine einfache Datenstruktur für arithmetische Ausdrücke mit ganzen Zahlen.

-- ---------------------------------------- -- -- Simple expression evaluator -- for integer arithmetic -- -- ---------------------------------------- module Expr0 where import Data.Maybe -- ---------------------------------------- -- syntactic domains data Expr = Const Int \| Binary BinOp Expr Expr deriving (Show) data BinOp = Add \| Sub \| Mul \| Div \| Mod deriving (Eq, Show) -- ---------------------------------------- -- semantic domains type Result = Int -- ---------------------------------------- -- the meaning of an expression eval :: Expr -> Result eval (Const i) = i eval (Binary op l r) = let mf = lookupMft op in mf (eval l) (eval r) -- ---------------------------------------- -- the meaning of binary operators type MF = Result -> Result -> Result lookupMft :: BinOp -> MF lookupMft op = case lookup op mft of Nothing -> error "operation not implemented" Just mf -> mf mft :: [(BinOp, MF)] mft = [ (Add, (+)) , (Sub, (-)) , (Mul, (*)) , (Div, div) ] -- ---------------------------------------- -- sample expressions e1 = Binary Mul (Binary Add (Const 2) (Const 4) ) (Const 7) e2 = Binary Div (Const 1) (Const 0) e3 = Binary Mod (Const 1) (Const 0) [v1,v2,v3] = map eval [e1, e2, e3] -- ----------------------------------------
Die Quelle

Problem	mit dieser Lösung
	Es wird im Interpretierer keine Fehlerbehandlung gemacht. Bei Fehlern während der Auswertung bricht der Interpretierer mit einem Laufzeitfehler ab.
Erweiterung	Um den Interpretierer brauchbar zu machen, muss dieser erweitert werden. Und zwar muss als Resultat nicht nur eine Zahl zugelassen werden, sondern auch eine Fehlermeldung.
	Dieses erfordert eine Erweiterung des Result-Datentyps, ein Int reicht hier nicht mehr.
	In einem rein funktionalen Programmierstil führt diese Erweiterung dazu, dass alle Teile der eval-Funktion mit zusätzlichen Fallunterscheidungen versehen werden müssen.
	Die Erweiterung kann also nicht modular erfolgen.
Monaden	können hier die Lösung für eine modulare Programmierung sein, in der nur die Teile zu ändern sind, in denen Fehlerbehandlung gemacht werden muss.
Monadischer Stil	Das obige Beispiel kann in eine monadische Form gebracht werden, ohne dass die Semantik verändert wird, wenn mit der Identitäts-Monade gearbeitet wird.

{-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE TypeSynonymInstances #-} -- The following compiler options are neccessary -- for the extension concerning the error handling -- they are not required for this simple example -- ---------------------------------------- -- -- Monadic version of simple expression -- evaluator. -- No extensions, same semantics as in Expr0 -- -- ---------------------------------------- module Expr1 where import Control.Monad () -- ---------------------------------------- -- syntactic domains data Expr = Const Int \| Binary BinOp Expr Expr deriving (Show) data BinOp = Add \| Sub \| Mul \| Div \| Mod deriving (Eq, Show) -- ---------------------------------------- -- semantic domains data Result a = Val { val :: a } deriving (Show) -- ---------------------------------------- -- the identity monad instance Monad Result where return = Val (Val v) >>= g = g v -- ---------------------------------------- -- the meaning of an expression eval :: Expr -> Result Int eval (Const i) = return i eval (Binary op l r) = do mf <- lookupMft op mf (eval l) (eval r) -- ---------------------------------------- -- the meaning of binary operators type MF = Result Int -> Result Int -> Result Int lookupMft :: BinOp -> Result MF lookupMft op = case lookup op mft of Nothing -> error "operation not implemented" Just mf -> return mf mft :: [(BinOp, MF)] mft = [ (Add, liftM2 (+)) , (Sub, liftM2 (-)) , (Mul, liftM2 (*)) , (Div, liftM2 div) ] -- defined in Control.Monad liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r liftM2 f m1 m2 = do x1 <- m1 x2 <- m2 return (f x1 x2) -- ---------------------------------------- -- sample expressions e1 = Binary Mul (Binary Add (Const 2) (Const 4) ) (Const 7) e2 = Binary Div (Const 1) (Const 0) e3 = Binary Mod (Const 1) (Const 0) [v1,v2,v3] = map eval [e1, e2, e3] -- ----------------------------------------
Die Quelle

Aufgabe	Erweitern Sie das Programm so, dass nicht mehr mit der Identität sonder mit einer Fehlermonade.
	Eine Fehlermonade arbeitet immer mit einem Summen-Datentyp, bei dem es eine Variante für die eigentlichen Werte gibt und eine zweite für die Beschreibung der Fehlersituation. Eine Fehlermonade arbeitet ähnlich wie die Maybe-Monade, nur wird im Fehlerfall noch eine Fehlermeldung gespeichert.
	Für diese Fehlermonaden gibt es eine allgemein einsetzbare Schnittstelle (Typklasse) MonadError aus Control.Monad.Error. Diese kann hier benutzt werden, ist aber nicht zwingend erforderlich.
	Der Result-Typ für die Werte muss hier erweitert und die Instanz für Monad verändert werden. Zum Auslösen eines Fehlers muss eine eigene modadische Aktion implementiert werden. In der Control.Monad.Error Schnittstelle heißt diese Funktion throwError. Das Abfangen wird dort mit catchError gemacht, wird hier aber (noch) nicht benötigt, kann also erst einmal entfallen.
	In den Funktionen müssen dann die error-Aufrufe ersetzt werden durch throwError-Aufrufe. Es sollten also nur die Stellen betroffen sein, bei denen bisher die Fehlerbehandlung ignoriert worden ist.
	Es sollte möglich sein, die Lösung mit höchstens 20 neuen oder veränderten Zeilen aus der monadischen Variante, die mit der Identitätsmonade arbeitet, abzuleiten.

Ausdrucksauswertung mit Monaden

Aufgabe 1