import Data.List (intercalate) -- Een lambdacalculus -------------------------------------------------------------------------------- -- Een variabelenaam type Name = String -- Een term in de lambdacalculus data Term = Var Name | Con Int | Add Term Term | Lam Name Term | App Term Term -- nieuwe taalconstructies | Amb Term Term | Fail -- Een waarde in de lambdacalculus data Value = Wrong -- De term was ongeldig | Num Int -- Een getal | Fun (Value -> M Value) -- Een monadische functie -- De evaluatieomgeving: variabelenamen gecombineerd met hun waarde type Environment = [(Name,Value)] -- Een waarde afdrukken instance Show Value where show Wrong = "<wrong>" show (Num i) = show i show (Fun f) = "<function>" -- Een eigen monad -------------------------------------------------------------------------------- -- M is de ambiguiteitsmonad type M a = undefined unitM :: a -> M a unitM x = undefined bindM :: M a -> (a -> M b) -> M b x `bindM` k = undefined showM :: (Show a) => M a -> String showM = undefined plusL :: M a -> M a -> M a m1 `plusL` m2 = undefined -- De monadische interpreter -------------------------------------------------------------------------------- -- Zoek een variabele op in de omgeving lookUp :: Name -> Environment -> M Value lookUp x [] = unitM Wrong lookUp x ((y,b):e) = if x == y then unitM b else lookUp x e -- Tel twee getalwaarden op add :: Value -> Value -> M Value add (Num i) (Num j) = unitM (Num (i+j)) add _ _ = unitM Wrong -- Pas een functiewaarde toe op een argumentwaarde apply :: Value -> Value -> M Value apply (Fun k) a = k a apply _ _ = unitM Wrong -- Bereken de waarde van een term gegeven een omgeving interp :: Term -> Environment -> M Value interp (Var x) e = lookUp x e interp (Con i) e = unitM (Num i) interp (Add u v) e = interp u e `bindM` (\a -> interp v e `bindM` (\b -> add a b)) interp (Lam x v) e = unitM (Fun (\a -> interp v ((x,a):e))) interp (App t u) e = interp t e `bindM` (\f -> interp u e `bindM` (\a -> apply f a)) interp Fail e = undefined -- ^ TODO geeft "geen" antwoord terug interp (Amb u v) e = undefined -- ^ TODO geeft alle mogelijke antwoorden terug -- Een term uitrekenen en afdrukken test :: Term -> String test t = showM (interp t [])