home Funktionale Programmierung: Prof. Dr. Uwe Schmidt FH Wedel
InhaltsverzeichnisFunktionale Programmierung

weiter
weiter

Aufgabe 1

Ausdrucksauswertung
und Monaden
Gegeben
 Eine einfache Datenstruktur für arithmetische Ausdrücke mit ganzen Zahlen.
weiter
-- ----------------------------------------
--
-- 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, Result -> Result -> Result)]
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 = eval e1
v2 = eval e2
v3 = eval e3
 
-- ----------------------------------------
weiter
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.
schlecht
 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.
weiter
{-# OPTIONS
    -XTypeSynonymInstances
    -XMultiParamTypeClasses #-}
 
-- 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 Data.Maybe
    ( fromMaybe )
 
import Control.Monad ()         -- ( liftM2 )
 
-- ----------------------------------------
-- 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 = eval e1
 
-- ----------------------------------------
weiter
Aufgabe
 Erweitern Sie das Programm so, dass nicht mehr mit der Identität sonder mit der Fehlermonade (MonadError aus Control.Monad.Error) gearbeitet wird.
Hierzu muss der Result-Typ erweitert werden, die Instanz für Monad verändert werden, und eine Instanz für MonadError entwickelt werden.
throwError muss implementiert werden.
catchError wird hier nicht benötigt, kann also erst einmal auf undefined gesetzt werden.
 
 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.
gut
 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.