Vorlesung: Praxis der Funktionalen Programmierung | Index

Interpreter-Monaden

Im bisherigen Beispiel war der Wert eines Ausdrucks eine Zahl, und die Operatoren standen für Funktionen :: Integer -> Integer -> Integer. Wir können das aber völlig generisch halten: erstens müssen es nicht immer Zahlen sein, sondern irgendein Resultattyp a. Zweitens möchten wir auch modellieren, daß Rechnungen (unsere Ausdrücke beschreiben Rechnungen) eventuell kein oder mehrer Resultate haben, aber alle vom Typ a. Wir können hier eine Monade m verwenden, die Instanz von MonadZero und MonadPlus ist.

module Monad_Let_Eval where

import Let_Type
import Let_Form
import Env
import Meaning

import MonadZero
import MonadPlus

import Prelude hiding (mapM)
import MapM

eval :: (MonadZero m, MonadPlus m) 
     => Envs Integer -> Term -> m Integer
eval envs t = case t of
    Constant n  -> return n
    Apply o l r -> do let [mx, my] = map (eval envs) [l, r]
		      let f = meaning o
		      x <- mx; y <- my
		      f x y
    Var n -> case finds envs n of
		  Nothing -> error $ "Variable " ++ n ++ " nicht gebunden"
		  Just x  -> return x
    Let binds body -> do
	    nxs <- mapM ( \ (n, t) -> do x <- eval envs t
				         return (n, x) )
			binds	    
	    eval (mkEnv nxs : envs) body

eval_top :: (MonadZero m, MonadPlus m) 
	 => Term -> m Integer
eval_top = eval nullEnvs

Wir sehen, daß die monadische Notation kaum noch Änderungen erfordert. Wir bemerken die Hilfsfunktion mapM mit der Definition

module MapM where
import Prelude hiding ( mapM )

mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f [] = return []
mapM f (x : xs) = do y <- f x; ys <- mapM f xs; return $ y : ys

Diese schaltet mehrere Rechnungen hintereinander. Die jeweils nächste ignoriert die Ergebnisse der vorigen. Die "Nebenwirkungen" natürlich nicht, die werden ja durch die Reihenfolge des "do" geordnet. Beispiel:

putStr = mapM putChar

Übung: berechne (erst auf dem Papier, dann mit hugs)

mapM ( \ x -> [x, x+1]) [2,4,6]

Benutzung des monadischen Interpreters

Was können wir mit dem Hauptprogramm

module Monad_Let_Main where

import Let_Type
import Let_Parser
import Let_Form
import Monad_Let_Eval

import MaybeMonadPlus
import ListMonadPlus

read_eval :: String -> String
read_eval input = 
    case parse (final term) input of
        Left msg -> msg
	Right t  -> let x = eval_top t :: [ Integer ]
		    in	show x

main = do
    input <- getContents
    putStrLn $ read_eval input

anstellen? Wir bemerken wieder, daß es nur einen Unterschied zu früher (nicht-monadisch) gibt: an eval_top t steht ein Typ dran. Diese Deklaration legt fest, in welcher Monade wir rechnen. (Übung: entferne die Deklaration und kompiliere.)

module Meaning where

import MonadZero
import MonadPlus
import Op

meaning :: (MonadZero m, MonadPlus m) 
	=> Op -> (Integer -> Integer -> m Integer)
meaning Plus  x y = return ( x + y )
meaning Minus x y = return ( x - y )
meaning Mal   x y = return ( x * y )
meaning Durch x y = if 0 == y then zero 
			      else return (x `div` y)
meaning Oder  x y = return x `plus` return y

Wir benutzen Maybe für eventuell fehlschlagende Rechnungen. Testeingabe: eval_read "8 / 0"

Was man sich wünschen könnte, wäre eine genauere Information im Fehlerfall, also statt Maybe gerne der Fehler-Typ des Parsers, der ja auch die Fehlerstelle im Quelltext angeben kann. Allerdings ist zur Zeit der Auswertung der Quelltext längst verschwunden. Man sieht, daß es sich trotzdem lohnt, Teile des Quelltextes, oder wenigestens Zeilennummern, im Syntaxbaum aufzuheben. (Das machen ja die klassischen Compiler auch, bei gcc -c -g werden Zeilennummern einkompiliert, damit der debugger sich dann besser zurechtfindet.)

Oder wir nehmen List für verzweigende Rechnungen. Eine solche geben wir durch den Oder-Strich ein. Testeingaben:

read_eval "3 * (4 | 5)"

Bei unserer Definition haben wir

read_eval "(3 | 4) * (3 | 4)"        ==> [9, 12, 12, 16]
read_eval "let {x = 3 | 4} in x * x" ==> [9, 16]

Wir haben es nämlich so eingerichtet, daß Variablen an Zahlen gebunden werden. Dabei gilt, wie wir sehen, die eigentlich erwartete Äquivalenz der beiden Ausdrücke nicht.

Man hätte es sich auch anders wünschen können: Variablen werden an Rechnungen gebunden (d. h. hier Resultatlisten), und bei jeder Benutzung (nicht nur bei jeder Bindung) kann jeder Wert drankommen, weil die Berechnung "neu ausgeführt" wird.

Rechnet man bei jeder Benutzung, ist man vielleicht flexibler. Rechnet man nur einmal und bindet den Wert, geht das schneller (vorausgesetzt, man braucht den Wert überhaupt.)

Genau dieses Tradeoff habe ich auch beim Musik-Sequenzer berücksichtigt. Es gibt dort in der Sprache Bindungen mit "=" (Rechnung) und mit "==" (Wert). Den Unterschied bemerkt man, wenn man "x = ask random" und "x == ask random" vergleicht. Das erste x ist bei jeder Benutzung ein anderes, das zweite ist bei jeder Benutzung das gleiche. Siehe dieses Beispiel. Dort steht x == ask random, weil wir den einmal gewürfelten Wert (Ton) in Folge oft benutzen wollen.

Zur Implementierung suche nach Let und LetEval im Quelltext.

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de