Ausdrucksauswertung
|
und Monaden für Ausdrücke mit Variablen
|
Gegeben |
Eine einfache Datenstruktur für arithmetische
Ausdrücke mit ganzen Zahlen und Variable wie in der vorigen Aufgabe über
Monaden und ein Interpretierer in monadischer Form mit Environment und Fehlerbehandlung.
|
| |
Syntaktische Bereiche |
data Expr = Const Int
| Var Id
| Let Id Expr Expr
| Binary BinOp Expr Expr
deriving (Show)
data BinOp = Add | Sub | Mul | Div | Mod
deriving (Eq, Show)
type Id = String
|
Semantische Bereiche |
Das Resultat war eine Funktion von
einem Environment auf einen Wert oder eine Fehlermeldung.
|
|
data ResVal a
= Val { val :: a }
| Exc { exc :: String }
deriving (Show)
newtype Result a
= Res { unRes :: Env -> ResVal a }
type Env = [(Id, Int)]
|
|---|
Veränderung |
der Ausdruckssprache
|
|
Eine andere Richtung der Erweiterung um Variablen ist die, mit Programmvariablen und Zuweisungen zu arbeiten.
In diesem Fall sind natürlich auch ein Sequenz-Operator und Schleifen
sinnvoll.
|
|---|
Neue syntaktische Bereiche |
data Expr = Const Int
| Var Id
| Assign Id Expr
| If Expr Expr Expr
| While Expr Expr
| Binary BinOp Expr Expr
deriving (Show)
data BinOp = ... | Seq
deriving (Eq, Show)
type Id = String
|
Aufgabe |
Das vorige Beispiel soll so verändert werden, dass nicht mehr
auf einem Environment gearbeitet wird (und nur gelesen wird), sondern
auf einem jederzeit veränderbaren Zustand.
Eine Operation
kann also nicht nur einen Wert berechnen, sondern auch einen neuen Zustand.
Es muss die Bedeutungsfunktion so abgeändert werden, dass sie diese
beiden Werte als Resultat liefert.
|
Neue semantische Bereiche |
data ResVal a
= Val { val :: a }
| Exc { exc :: String }
deriving (Show)
newtype Result a
= Res { unRes :: VState -> (ResVal a, VState) }
type VState = [(Id, Int)]
|
MonadState |
Für die Verwaltung so eines Zustands gibt
es wieder eine Typklasse MonadState, die hier sinnvollerweise
verwendet werden sollte.
|
Definition |
der Monaden-Klassen
|
|
instance Monad Result where
return x = Res $ ...
(Res f) >>= g = Res $ ...
instance MonadError String Result where
throwError s = Res $ ...
instance MonadState VState Result where
get = Res $ ...
put new = Res $ ...
|
|---|
Interpretierer- |
Veränderungen und Erweiterungen sind
an den folgenden Stellen nötig:
|
|
eval (Var id)
= do ...
eval (Assign id e1)
= do ...
eval (If c t e)
= do ...
eval st@(While c b)
= do ...
...
mft :: [(BinOp, MF)]
mft
= [ ...
, (Seq, ...)
]
evalSt :: Expr -> VState -> (ResVal Int, VState)
evalSt = unRes . eval
|
|---|
Ausdrücke |
zum Testen
|
|
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)
e4 = Var "x"
e5 = Binary Mul (Binary Add e4
(Const 1)
) e4
e4' = Binary Seq (Assign "x" (Const 42)) e4
e5' = Binary Seq (Assign "x" (Const 6)) e5
e6' = foldr1 (Binary Seq) $
[ Assign "x" (Const 42)
, Assign "y" (Const 13)
, Assign "t" (Var "x")
, Assign "x" (Var "y")
, Assign "y" (Var "t")
]
e7' = foldr1 (Binary Seq) $
[ e6'
, Assign "r" (Binary Sub (Var "x") (Var "y"))
, If (Var "r") (Var "r") (Var "x")
]
e8 = Binary Seq e4' $
While (Var "x")
(Assign "x" (Binary Sub (Var "x")
(Const 1)))
|
|---|
Erweiterung |
um Ein- und Ausgabe
|
|
Möchte man die Sprache um Ein- und Ausgabe erweitern, beispielhaft um das Einlesen und Ausgeben einer Zahl,
so wird man den Resultat-Typ erweitern, so dass er in der IO-Monade läuft.
Außerdem wird man normale IO-Aktionen in diese Monade liften müssen. Hierfür gibt es wieder
eine vorgefertigte Schnittstelle MonadIO und eine Funktion liftIO.
Der Ausdrucksdatentyp wird anschließend um Lese- und Schreiboperationen erweitert. Diese
werden dann mit Hilfe von einfachen IO-Aktionen implementiert.
|
|---|
Syntaktische Bereiche |
data Expr = ...
| Read
| Write String Expr
|
Semantische Bereiche |
newtype Result a
= Res {unRes :: VState -> IO (ResVal a, VState)}
|
Monaden- |
Erweiterung
|
|
instance Monad Result where
return x = Res $ ...
(Res f) >>= g = Res $ ...
instance MonadError String Result where
throwError s = Res $ ...
instance MonadState VState Result where
get = Res $ ...
put new = Res $ ...
instance MonadIO Result where
liftIO a = Res $ ...
|
|---|
Interpretierer- |
Erweiterungen
|
|
eval Read
= ...
eval (Write msg e)
= ...
|
|---|
Funktionale Programmierung: Ausdrucksauswertung mit Zuweisungen und Schleifen
