Dieser Artikel ist der dritte einer Serie von Artikeln über
Monaden in Haskell.
- Im ersten Artikel der Serie haben wir die Grundlagen
diskutiert.
- Im zweiten Teil der Serie haben wir begonnen, eigene
Monaden zur Lösung Software-technischer Aufgaben zu entwickeln
und haben dabei die
Fehler-Monade und die Listen-Monade kennen gelernt.
Im heutigen Teil möchten wir diesen Aspekt vertiefen und erneut
demonstrieren, wie durch Monaden
ein Stück Software modular und durch lokale Erweiterungen um neue
Funktionalität ergänzt werden kann, ohne bestehende Teile zu verändern
oder zu refaktorisieren.
Als laufendes Beispiel haben wir die klassische Aufgabe der Auswertung von
Ausdrücken behandelt.
Die Mächtigkeit der Ausdruckssprache war bisher aber noch sehr beschränkt.
Wir werden nun die Sprache als erstes um freie und gebundene Variablen
erweitern. Zur Verarbeitung hierfür wird die sogenannte Reader-Monade
eingesetzt werden.
Im folgenden Schritt werden Zuweisungen, Sequenzen, Verzweigungen und
Schleifen hinzu kommen. Damit bekommen wir schon eine
Turing-vollständige Programmiersprache. Die Reader-Monade wird
durch die Zustands-Monade ersetzt werden.
Die letzte Erweiterung wird die Ein- und Ausgabe betreffen. Der
Interpretierer muss dann also in der IO-Monade laufen. Dieses
oftmals schwierig Vorgehen, nämlich erst am
Schluss eines Entwicklungsprozesses an Ein- und Ausgabe zu denken,
wird uns in diesem Fall durch den monadischen Programmierstil keinerlei
Schwierigkeiten bereiten.
Ausdrücke mit Variablen
Im diesem ersten Schritt werden wir die Ausdruckssprache um Variablen
erweitern. Dazu wird die abstrakte Syntax, der Datentyp Expr auf
zwei Arten erweitert. Als einfache Ausdrücke werden Variablen
zugelassen. Außerdem sollen, wie in Haskell auch, lokale Variablen
durch let-Ausdrücke eingeführt werden können.
Es stellt sich dann natürlich die Frage, ob, und wenn ja, wie diese
Erweiterung zu der existierenden Lösung hinzugefügt werden kann. Wir
werden, um die Beispiele übersichtlich zu halten, den
Nichtdeterminismus nicht weiter betrachten, sondern wieder von
Expr2.hs ausgehen.
Der Datentyp Expr erweitert um die beiden neuen Varianten:
data Expr = ...
| Var Id
| Let Id Expr Expr
type Id = String
Was ist die Bedeutung eines Ausdrucks mit freien Variablen? Zur
Auswertung solcher Ausdrücke brauchen wir eine Zuordnung von Werten zu
den freien Variablen. Diese Zuordnung werden wir in
einer sogenannten Umgebung, engl. Env-ironment speichern. Die
Bedeutung eines Ausdrucks kann als eine Funktion aufgefasst werden,
die eine Umgebung auf einen Resultatwert abbildet. eval wird also
einen Ausdruck (Expr) nehmen, und daraus eine Funktion
berechnen. Erst wenn diese Funktion auf eine Umgebung angewendet wird,
bekommen wir einen konkreten Wert, eine Zahl oder eine Fehlermeldung.
newtype Result a
= Res { unRes :: Env -> ResVal a }
type Env = [(Id, Int)]
data ResVal a
= Val { val :: a }
| Exc { exc :: String }
deriving (Show)
Der Result-Typ wird zu einem Funktionstyp Env -> ResultVal a, der
wegen der Monad-Instanz in einen newtype verpackt werden
muss. Damit berechnet eval aus einem Ausdruck eine Funktion vom Typ
Env -> ResVal Int. Dieser entspricht dem alten Result aus
Expr2.hs. Für die Umgebung wird hier eine einfache
Schlüssel-Wert-Liste genommen. Bei praktischen Anwendungen werden
üblicherweise effizientere Container-Implementierungen, z.B. aus
Data.Map genutzt.
Um eine Auswertung von Ausdrücken mit Variablen zu starten
(runEval), benötigen wir also neben dem Ausdruck auch noch eine
Belegung der Variablen.
runEval :: Expr -> Env -> ResVal Int
runEval e env
= let (Res f) = eval e in
f env
Der Kern dieser Erweiterung ist die Monaden-Instanz für Result:
instance Monad Result where
return x = Res $ \ env -> Val x
(Res f) >>= g = Res $ \ env ->
case f env of
(Exc e) -> (Exc e)
(Val v) -> unRes (g v) env
return x konstruiert eine Funktion, deren Resultat immer Val x
ist, also nicht von der Umgebung abhängt.
Bei >>= müssen wir wieder eine Funktion konstruieren. In dieser wird
als erstes f auf die Umgebung angewendet, was entweder einen Fehler
e liefert oder eine Wert v. Dieser kann auf g angewendet werden,
was uns eine weitere Funktion liefert, die ebenfalls auf die Umgebung
env angewendet wird. Sowohl f als auch g v nutzen also die
gleiche Umgebung.
Wir haben aber noch keine direkten Funktionen, die das env nutzen,
was aber bei der Auswertung von Var ident notwendig ist. Hierfür
definieren wir eine Funktion ask zum Auslesen der gesamten Umgebung.
ask :: Result Env
ask = Res $ \ env -> Val env
Mit ask kann jetzt die eval-Funktion für Variablenzugriff erstellt
werden.
eval (Var ident)
= do env <- ask
case lookup ident env of
Nothing -> throwError
$ "free variable '"
++ ident
++ "' found"
Just v -> return v
Es wird das Environment ausgelesen und mit lookup ident env der Wert
der Variablen in der Umgebung gesucht. Dieser bildet das Resultat. Im
Fehlerfall wird eine entsprechende Fehlermeldung generiert.
Mit der Redefinition der Monade und dieser Erweiterung von eval ist
die Erweiterung der Ausdrücke um freie Variablen abgeschlossen.
Was noch fehlt, sind die lokalen, mit Let eingeführten Variablen für
Zwischenergebnisse. Hierfür muss das Environment lokal erweitert und
für die lokale Auswertung der Ausdrücke genutzt werden.
Diese lokale Veränderung kann man, wie bei ask, allgemeingültig
implementieren mit einer local genannten Funktion
local :: (Env -> Env) -> Result a -> Result a
local f (Res g) = Res $ \ env -> g (f env)
Mit Hilfe von local können lokal gebundene Variablen auf folgende
Art implementiert werden:
eval (Let ident e1 e2)
= do v1 <- eval e1
local (addEnv ident v1)
(eval e2)
where
addEnv i v env = (i, v) : env
Der Ausdruck e1 bestimmt den Wert der lokalen Variablen ident. Er
wird hier in dem bisherigen env ausgewertet. Das Paar (ident, v1)
wird vorne vor die env-Liste eingefügt, so dass es in einer Suche
als erstes gefunden wird. Mit diesem neuen Environment wird der
Ausdruck e2 ausgewertet.
Damit ist die Erweiterung der Ausdruckssprache um freie und um lokal
gebundene Variablen vollständig. Wieder waren nur Veränderungen an der
Monade und Erweiterungen um die neuen Sprachelemente notwendig. Nichts
Bestehendes musste refaktorisiert werden.
Es fehlen noch einige einfache Ausdrücke für einen Testlauf:
x = Var "x"
y = Var "y"
l1 = Binary Mul x y
l2 = Let "x" (Const 6) l1
l3 = Let "y" (Const 7) l2
v0 = runEval l1 []
v1 = runEval l1 [("x",2),("y",3)]
v2 = runEval l1 [("x",4),("y",5)]
v3 = runEval l2 [("y",5)]
v4 = runEval l3 []
und eine ghci-Session
zwiebel> ghci Expr4.hs
...
*Expr4> l1
Binary Mul (Var "x") (Var "y")
*Expr4> runEval l1 []
Exc {exc = "free variable 'x' found"}
*Expr4> runEval l1 [("x",2),("y",3)]
Val {val = 6}
*Expr4> [("x",4),("y",5)]
Val {val = 20}
*Expr4> l2
Let "x" (Const 6) (Binary Mul (Var "x") (Var "y"))
*Expr4> runEval l2 [("y",5)]
Val {val = 30}
*Expr4> l3
Let "y" (Const 7) (Let "x" (Const 6) (Binary Mul (Var "x") (Var "y")))
*Expr4> runEval l3 []
Val {val = 42}
Die Monade mit dem Environment und den Funktionen ask und local
ist die sogenannte Reader-Monade. ask und local sind deklariert
in Control.Monad.Reader. In
Real-World-Haskell-Programmen wird diese Monade häufig genutzt,
um Konfigurations-Parameter an den unterschiedlichtsten Stellen
zugreifbar zu machen, ohne diese explizit durch Funktionen durch zu
reichen.
Ausdrücke mit Programm-Variablen und Zuweisungen
In der folgenden Erweiterung der Ausdruckssprache werden wir
Programm-Variablen, Zuweisungen, Sequenzen, Schleifen und
Verzweigungen hinzu nehmen. Um das Beispiel übersichtlich zu halten,
werden wir nicht, wie es in realen Anwendungen sinnvoll wäre,
syntaktisch zwischen Ausdrücken und Anweisungen unterscheiden. Auch
werden wir, wie es in vielen Skriptsprachen (leider) üblich ist, auf
die Deklaration von Variable verzichten. Variablen entstehen bei der
ersten Zuweisung. Die Zuweisungen werden, wie in C, als Ausdrücke mit
Seiteneffekten behandelt.
Die abstrakte Syntax hat folgende Gestalt:
data Expr = Const Int
| Binary BinOp Expr Expr
| Var Id
| Assign Id Expr -- neu
| If Expr Expr Expr -- neu
| While Expr Expr -- neu
data BinOp = Add | Sub | Mul | Div | Mod
| Seq -- neu
Die Berechnungen finden also wie in dem letzten Beispiel in einer
Umgebung statt. Diese speichert die Belegung der Variablen. Der
entscheidende Unterschied ist aber, dass die Belegung sich während der
Berechnung ändern kann. Diese sich ständig ändernde Umgebung
bedeutet, dass neben dem eigentlichen Wert immer noch der
möglicherweise veränderte Zustand als zusätzliches Resultat zurück
geliefert wird. Wir werden hierfür die Zustands-Monade nutzen.
type VarState = [(Id, Int)]
data ResVal a
= Val { val :: a }
| Exc { exc :: String }
deriving (Show)
newtype Result a
= Res { unRes :: VarState -> (ResVal a, VarState) }
Der Zustand VarState ist wie oben als einfache Liste von
Schlüssel-Wert-Paaren realisiert. Die entscheidende Veränderung
gegenüber Expr4.hs ist das Tupel (ResVal a, VarState) als
Resultattyp.
Die Monade für Result wird als Kombination der Fehler- und der
Zustands-Monade realisiert:
instance Monad Result where
return x = Res $ \ st0 -> (Val x, st0)
(Res f1) >>= g = Res $ \ st0 ->
let (r1, st1) = f1 st0 in
case r1 of
(Exc e) -> (Exc e, st1)
(Val v) -> let Res f2 = g v in
f2 st1
return konstruiert aus einem Wert eine Funktion, die den Zustand
unverändert durchreicht. In >>= wird in der Funktion st0 über
st1 bis zum Endergebnis durchgefädelt.
Wir benötigen aber noch, analog zu ask Funktionen zum lesenden und
schreibenden Zugriff (get und put).
get :: Result VState
get = Res $ \ st -> (Val st, st)
put :: VState -> Result ()
put new = Res $ \ old -> (Val (), new)
get arbeitet analog zu ask. put nimmt einen neuen Zustand und
wechselt den alten gegen diesen aus. Das eigentliche Resultat dieser
Aktion () ist hier unwesentlich.
Wie werden die neuen Sprachelemente implementiert? Beginnen wir mit
der Zuweisung:
eval (Assign ident e1)
= do v1 <- eval e1
st <- get
put (setVar ident v1 st)
return v1
where
setVar i v s = (i, v) : filter ((/= i) . fst) s
Die rechte Seite der Zuweisung wird ausgewertet, der Zustand
ausgelesen (get), der modifizierte Zustand berechnet (setVar) und
geschrieben. Wie in der Sprache C ist hier das Resultat der Zuweisung
der Wert der rechten Seite.
Für die häufig auftretende Codefolge get >>= \ x -> put (f x) gibt
es eine Bequemlichkeitsfunktion
modify :: (s -> s) -> Result s
modify f
= do s <- get
put (f s)
Die Verzweigung und die Schleife werden nach dem üblichen Muster
interpretiert, wobei in den Bedingungen 0 als False und alle
anderen Werte als True aufgefasst werden.
eval (If c t e)
= do v <- eval c
if v /= 0
then eval t
else eval e
eval st@(While c b)
= do v <- eval c
if v /= 0
then do eval b
eval st
else return v
Es bleibt die Sequenz. Diese ist nichts anderes als ein 2-stelliger
Operator (in der Sprache C das ,). Bei der Auswertung wird der erste
Teilausdruck ausgewertet und das Ergebnis vergessen. Nur der Effekt
auf den Zustand ist von Interesse. Die Funktionstabelle für die
Operatoren muss also nur um eine Zeile erweitert werden.
ftab :: [(BinOp, BinFct)]
ftab = [ ...
, (Seq, liftM2 (\ x y -> y))
]
Es bleibt noch der Start einer Berechnung mittels runEval. Diese
Funktion liefert jetzt zwei Werte, ein Resultat und einen Endzustand.
runEval :: Expr -> VarState -> (ResVal Int, VarState)
runEval e st0
= let (Res f) = eval e in
f st0
Mit diesen wenigen Erweiterungen haben wir aus der Auswertung
arithmetischer Ausdrücke eine kleine, aber vollständige imperative
Programmiersprache entwickelt. Und, wie immer unter Verwendung des
monadischen Stils, ausschließlich durch Modifikation der
Monaden-Definition und einiger lokaler Erweiterungen.
Es fehlt noch eine Demo mit zwei kleinen Programmen:
p1 = foldr1 (Binary Seq)
[ Assign "t" (Var "x")
, Assign "x" (Var "y")
, Assign "y" (Var "t")
]
p2 = While
(Binary Sub x (Const 100))
(Assign "x" (Binary Add x (Const 1)))
where
x = Var "x"
Im ersten Programm p1 werden zwei Variablen x und y vertauscht,
in p2 wird bis 100 gezählt.
zwiebel> ghci Expr5.hs
...
*Expr5> runEval p1 [("x", 42), ("y",23)]
(Val {val = 42},[("y",42),("x",23),("t",42)])
*Expr5> runEval p2 [("x", 1)]
(Val {val = 0},[("x",100)])
Programme mit Ein- und Ausgabe
Einer der größten Entwurfsfehler beim Entwickeln in Haskell ist eine
fehlende Überlegung, in welchen Funktionen Ein- und/oder Ausgabe
gemacht werden muss. Solche Fehler sind bei späteren Erweiterungen
häufig nicht mehr zu auszubessern, ohne große Teile eines Systems neu
zu schreiben.
In den bisher entwickelten Beispielen haben wir genau diesen Fehler
gemacht. Was passiert, wenn wir für Expr5.hs im zweiten
Release die Anforderung bekommen, bei der Auswertung von Ausdrücken
Werte einlesen oder Zwischenergebnisse ausgeben zu müssen?
Dieses bedeutet, das während der Auswertung nicht nur der interne
Zustand mit den Programm-Variablen verändert wird sondern auch der
Weltzustand in der IO-Monade. Wir müssen also die Result-Monade
mit der IO-Monade kombinieren. Nur dadurch, dass wir bisher in
einem monadischen Stil entwickelt haben, werden wir wieder auf
einfache Weise den Aspekt der Ein- und Ausgabe in das bisherige System
integrieren können.
Der Result-Datentyp wird so verändert, dass die Funktionen
in der IO-Monade laufen:
newtype Result a
= Res { unRes :: VarState -> IO (ResVal a, VarState) }
-- ^^^^
Entsprechend müssen return und >>= sowie throwError, get und
put so verändert werden, dass sie in der IO-Monade laufen.
instance Monad Result where
-- Das return auf der linken Seite des = ist das zu definierende der
-- Result-Monade. Das return auf der rechten Seite kommt aus der
-- IO-Monade.
return x = Res $ \ st0 -> return (Val x, st0)
(Res f1) >>= g = Res $ \ st0 ->
do (r1, st1) <- f1 st0
case r1 of
(Exc e) -> return (Exc e, st1)
(Val v) -> let Res f2 = g v in
f2 st1
instance MonadError String Result where
throwError s = Res $ \ st -> return (Exc s, st)
instance MonadState VarState Result where
get = Res $ \ st -> return (Val st, st)
put new = Res $ \ _ -> return (Val (), new)
Um auf den Weltzustand mit den vordefinierten IO-behafteten
Laufzeitsystem-Funktionen in der Result-Monade zu arbeiten,
benötigen wir noch eine lift-Funktion liftIO
liftIO :: IO a -> Result a
liftIO a = Res $ \ st ->
do v <- a
return (Val v, st)
Für liftIO gibt es wieder eine vordefinierte Klasse MonadIO.
Mit dieser Erweiterung der Result-Monade können wir beginnen, die
Ein- und Ausgabeoperationen zu implementieren. Wir benötigen zwei
neue syntaktische Konstrukte für das Lesen und Schreiben von Werten.
data Expr = ...
| Read
| Write String Expr
Read wird zum Einlesen einer Zahl genutzt, Write zur Ausgabe eines
Strings und dem Resultat eines Ausdrucks. Die eigentliche
Schnittstelle zum I/O-System bilden hier die Hilfsfunktionen readInt
und writeInt.
eval Read
= readInt
eval (Write msg e)
= do v <- eval e
writeInt msg v
return v
readInt :: Result Int
readInt = liftIO $ ...
writeInt :: Show a => String -> a -> Result ()
writeInt m v = liftIO $ ...
Der vollständige Code ist in Expr6.hs zu finden. Wir werden
diesen mit zwei keinen Beispielen ausprobieren:
-- read 2 numbers and display product
p1 = Write "Result is: "
(Binary Mul Read Read)
-- count to 100 with trace
p2 = While
(Binary Sub x (Const 100))
(Write "x = "
(Assign "x" (Binary Add x (Const 1))))
where
x = Var "x"
Eine ghci-Session mit zwei Testläufen zeigt die erwarteten
Ergebnisse:
zwiebel> ghci Expr6.hs
...
*Expr6> runEval p1 []
give a number: 6
give a number: 7
Result is: 42
(Val {val = 42},[])
*Expr6> runEval p2 [("x", 1)]
x = 2
x = 3
...
x = 99
x = 100
(Val {val = 0},[("x",100)])
Die Integration von Ein- und Ausgabe konnte, dank des monadischen
Stils, wieder duch lokale Änderung der Monade und lokale Erweiterungen
realisiert werden. Alle anderen existierenden Codeteile konnten
unverändert weiter verwendet werden.
Zusammenfassung und Ausblick
Wir haben in den Beispielen Expr1.hs bis Expr6.hs
gesehen, dass wir die einfache Ausdrucksauswertung in unterschiedliche
Richtungen erweitern konnten, ohne existierende Funktionalität zu
überarbeiten. Neue Aspekte konnten alleine durch die Erweiterung des
Result-Datentyps und der monadischen Operationen return und >>=
und deren Verwandten integriert werden.
In einem nichtmonadischen Stil hätten wir für jeden neuen Aspekt die
Schnittstellen und die Implementierungen vieler über das gesamte
Programm verstreuter Funktionen erweitern müssen.
Wir haben in den Beispielen alle Monaden per Hand gebaut und auch
per Hand kombiniert. Für das Verständnis von Monaden ist dieses ein
sehr sinnvolles Vorgehen. Aber die verwendeten Monaden und deren
Kombinationen wiederholen sich. In vielen etwas anspruchsvolleren
Projekten muss man IO, Fehlerbehandlung und einen internen Zustand
verwalten, meist kommt noch die Notwendigkeit einer Konfigurierbarkeit
dazu, d.h. man muss wiederholt eine IO-Exception-Reader-State-Monade
entwickeln, was spätestens nach dem zweiten Mal langweilig wird.
Dieses ruft nach einem Werkzeugkasten, mit dem man Standard-Monaden
auf flexible Art zu einem Monaden-Stapel ( monad stack ) zusammen
setzten kann. Hierzu gibt es die sogenannten Monaden-Transformatoren
( monad transformer ), mit denen man aus einer gegebenen Basis-Monade
eine neue Monade erzeugen kann, die dann um einen neuen Aspekt
angereichert worden ist.
Die meisten der hier diskutierten Monaden, könnte man mit diesen
Monaden-Transformatoren zusammen setzten, so auch unsere letzte
IO-Exception-State-Monade. Auf hackage findet man zum Beispiel
die mtl-und transformers-Bibliotheken, die im Moment überwiegend
für diesen Zweck eingesetzt werden. Unter anderem werden im
Real-World-Haskell-Buch einige in der Praxis bedeutsame
Beispiele für den Einsatz von Monaden-Transformatoren behandelt.
Monaden sind inzwischen nicht mehr nur eine Domäne von Haskell. Auch
in anderen Sprachen, wie Scala, Javascript, Ruby, … wird versucht,
diesen Ansatz des programmierbaren Semikolons einzusetzen.
Insbesondere bei eingebetteten Domänen-spezifischen Sprachen (DSLs)
bietet dieser Stil Software-technisch viele Vorteile.
Die hier vorgestellten Beispiele sind also nicht das Ende der
Geschichte, sondern erst der Anfang.
Viel Spaß beim Ausprobieren der Beispiele.