On 06/30/2011 08:25 PM, Philipp Schneider wrote:
> On 06/30/2011 02:36 PM, Holger Siegel wrote:
>> Am 29.06.2011 um 23:50 schrieb Philipp Schneider:
>>
>>> Hi cafe,
>>>
>>> in my program i use a monad of the following type
>>>
>>> newtype M a = M (State -> (a, State))
>>>
>>> i use the monad in two different ways. The type variable "a" can be a
>>> pair as in
>>>
>>> interp :: Term -> Environment -> M (Value,Environment)
>>>
>>> and it can be just a value as in
>>>
>>> type Environment = [(Name, Either Value (M Value))]
>> Simple rule: Never return an environment!
>>
>> An environment contains local variable bindings, so no subcomputation will
>> ever need to return its environment. I don't know anything about the
>> language your program interprets, but I'm sure that you can rewrite function
>> interp as
>>
>> interp :: Term -> Environment -> M Value
>>
>> The structure of the interpreter will become clearer and your problem will
>> vanish.
>>
> Hello Holger,
>
> I'm giving two lambda interpreters. The first one is a call by value
> interpreter, the second one a call by name interpreter which are
> described in Philip Wadler's paper "The essence of functional
> programming" page 4 and 12. Now my task is to write a lazy lambda
> interpreter. The exercise is more playful than serious since Wadler's
> call by value interpreter is, since written in lazy Haskell, already a
> lazy lambda interpreter. (To get true call by value one would need to
> force evaluations of the arguments with the seq function.)
> For both of Wadler's interpreters the type of the interpertation
> function is:
> interp :: Term -> Environment -> M Value
>
> Now to simulate lazy interpretation i need to do the following: Decide
> is the value I need already evaluated or is it still a computation. In
> the later case I need to evaluate it and save its value in the
> environment. This is the reason I changed the type of the interpretation
> function to:
> interp :: Term -> Environment -> M (Value,Environment)
>
> I appened my full interpreter. If you can find a more elegant way to
> save the newly interpreted values, you are more than welcome to show my
> how to do it.
>
> Cheers,
> Philipp
I forgot to add the interpreter.
{-# LANGUAGE OverlappingInstances #-}
import Prelude hiding (lookup, fail)
import Control.Monad
-- Basiswerte
data Value = WrongAd
| WrongAp
| WrongL
| Num Int
| Fun (Either Value (M Value) -> M Value)
instance Show Value where
show WrongAd = "<wrong add>"
show WrongAp = "<wrong app>"
show WrongL = "<wrong lookup>"
show (Num i) = show i
show (Fun f) = "<function>"
-- Terme
data Term = Var Name
| Con Int
| Add Term Term
| Lam Name Term
| App Term Term deriving Show
-- Interpretation der Terme (Lazy evaluation)
interp :: Term -> Environment -> M (Value,Environment)
interp (Var x) e = lookup x e
interp (Con i) e = return (Num i,e)
interp (Add u v) e = do
(a,e) <- interp u e
(b,e) <- interp v e
s <- add a b
return (s,e)
interp (Lam x v) e = return (Fun (\m -> (interp v ((x, m):e)) >>= return . fst) , e)
interp (App t u) e = do
(f,e) <- interp t e
a <- (apply f (Right ((interp u e) >>= return . fst)))
return (a,e)
add :: Value -> Value -> M Value
add (Num i) (Num j) = tick >>= (\() -> return (Num (i+j)))
add a b = return WrongAd
apply :: Value -> Either Value (M Value) -> M Value
apply (Fun k) a = tick >>= (\() -> k a)
apply notFun a = return WrongAp
-- Umgebung
type Environment = [(Name, Either Value (M Value))]
type Name = String
lookup :: Name -> Environment -> M (Value,Environment)
lookup x eComplete = lookup_h x eComplete
where
lookup_h x [] = return (WrongL,[])
lookup_h x e@((y,b):etl) =
if x==y then case b of
-- schon ausgewertet
Left a -> return (a,e)
-- noch nicht ausgewertet (speichere den ausgewerteten Wert)
Right a -> (a >>= (\x-> return (x, (y,Left x):eComplete)))
else lookup_h x etl
-- Lazy-Interpreter zaehlt die Reduktionen (Wadler: Beispiel 9)
type State = Int
newtype M a = M (State -> (a, State))
tick = M (\s -> ((), s+1))
instance (Show a,Show b) => Show (M (a,b)) where
show (M f) = let ((v,_), s) = f 0 in
"Value: " ++ show v ++ " Count: " ++ show s
instance Show a => Show (M a) where
show (M f) = let (v, s) = f 0 in
"Value: " ++ show v ++ " Count: " ++ show s
instance Monad M where
return a = M (\s -> (a, s))
(M m) >>= k = M (\s0 -> let (a, s1) = m s0
(M m') = k a
in m' s1
)
fail s = error s -- wird nicht aufgerufen
-- Beispiele:
-- test :: Term -> String
test t = (interp t [])
term0 = (Con 10)
term0' = (Var "x")
term1 = (Add (Con 10) (Con 11))
term2 = (Lam "x" (Add (Var "x") (Con 10)))
term3 = (App term2 (Con 11))
term4 = (Lam "x" (Add (Var "x") (Var "x")))
term5 = (App term4 term1)
term6 = (Lam "x" (Lam "y" (Add (Var "x") (Var "y"))))
term7 = (App term6 (Con 10))
term8 = (App term7 (Con 11))
term7' = (App (Lam "x" (Lam "y" (Add (Var "x") (Var "y"))))
(Con 10))
term8' = (App (App (Lam "x" (Lam "y" (Add (Var "x") (Var "y"))))
(Con 10))
(Con 11))
term9 = (Lam "x" (Var "x"))
term10 = (App (Lam "x" (Var "x")) (Con 15))
term11 = (Add (Con 10) (Add (Con 11) (Con 5)))
twice = (Lam "f" (Lam "x" (App (Var "f")
(App (Var "f") (Var "x")))))
increm = (Lam "x" (Add (Var "x") (Con 1)))
term12 = (App (App twice increm) (Con 5))
-- Beispiele mit Fehlern:
termE1 = (Add (Var "x") (Con 10))
termE2 = (Add (Con 10) term9)
termE3 = (App (Con 1) (Con 2))
termE4 = (App (App twice (Con 3)) (Con 5))
bot = (App (Lam "x" (App (Var "x") (Var "x")))
(Lam "x" (App (Var "x") (Var "x"))))
term13 = (App (Lam "x" (Con 1)) bot)
term14 = (Add term13 (Con 7))_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
