Re: [Haskell-cafe] overloading show function
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] overloading show function
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
Re: [Haskell-cafe] overloading show function
On 06/30/2011 09:49 PM, Holger Siegel wrote: Am 30.06.2011 um 20:23 schrieb Philipp Schneider: 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.) Hello Philipp, that's a nice exercise. 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) But that won't work: After you have evaluated an entry of the environment, you store the resulting value but you throw away its updated environment. That means, you lose the results of all subcomputations instead of propagating them to all other copies of the environment. Consider the following expression: let x = big_computation in let y = x in y + x First, big_computation is bound to the name x, resulting in an environment [(x, big_computation)]. Then a closure consisting of this environment together with the right hand side 'x' is bound to the name y. Now y+x is evaluated: The closure is entered, and from its environment the content of x - a call to big_computation - is looked up. Now big_computation is evaluated and the result is bound to x in this environment. After that, this result is also returned as the value of y. But when returning from the evaluation of y, the environment with the updated value of x is lost and you have to re-evaluate it in order to calculate x+y! Hello Holger, Can you give me an example of a lambda term in which this would be an issue? Evaluating the following works just fine in my implementation. interp (App (Lam x (Add (Var x) (Var x))) big_computation) [] When the first variable x is evaluated my interp function returns the value and the updated environment. Then to evaluate the second variable the value is just looked up from this environment. Of course in the following big_computation would be evaluated twice (App (Lam x (App (Lam y (Add (Var x) (Var y))) big_computation)) big_computation) But i simply don't have a concept like let x=y. And that is why I say never return an environment. It is either wrong or unnecessary or the resulting semantics of the interpreter is hard to comprehend. In order to implement lazy evaluation correctly, you have to maintain some global state in which the thunks are updated. For example, your environment could bind IORefs that contain unevaluated thunks to variable names and update them when the thunk is evaluated. But then your interpreter has to run in the IO monad. I agree that this would be the proper way to do it, but I was trying to minimize the use of monads since they have just been introduced in the course. By the way, do you already know Peter Sestoft's paper Deriving a lazy abstract machine? I haven't read is so far, but thanks for pointing it out. Cheers, Holger Cheers, Philipp ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] overloading show function
On 06/30/2011 11:46 PM, Holger Siegel wrote: Am 30.06.2011 um 22:57 schrieb Philipp Schneider: On 06/30/2011 09:49 PM, Holger Siegel wrote: (...) But that won't work: After you have evaluated an entry of the environment, you store the resulting value but you throw away its updated environment. That means, you lose the results of all subcomputations instead of propagating them to all other copies of the environment. Consider the following expression: let x = big_computation in let y = x in y + x First, big_computation is bound to the name x, resulting in an environment [(x, big_computation)]. Then a closure consisting of this environment together with the right hand side 'x' is bound to the name y. Now y+x is evaluated: The closure is entered, and from its environment the content of x - a call to big_computation - is looked up. Now big_computation is evaluated and the result is bound to x in this environment. After that, this result is also returned as the value of y. But when returning from the evaluation of y, the environment with the updated value of x is lost and you have to re-evaluate it in order to calculate x+y! Hello Holger, Can you give me an example of a lambda term in which this would be an issue? Evaluating the following works just fine in my implementation. interp (App (Lam x (Add (Var x) (Var x))) big_computation) [] When the first variable x is evaluated my interp function returns the value and the updated environment. Then to evaluate the second variable the value is just looked up from this environment. Of course in the following big_computation would be evaluated twice (App (Lam x (App (Lam y (Add (Var x) (Var y))) big_computation)) big_computation) But i simply don't have a concept like let x=y. App (Lam x (App (Lam y (Add (Var y) (Var x))) (Var x ))) (Con 2) takes three reduction steps, which is correct, but App (Lam x (App (Lam y (Add (Var y) (Var x))) (Var x ))) (Add (Con 1)(Con 1)) takes five reduction steps although it should take only four. Ok, I now see the problem. Thanks for pointing it out to me. And that is why I say never return an environment. It is either wrong or unnecessary or the resulting semantics of the interpreter is hard to comprehend. In order to implement lazy evaluation correctly, you have to maintain some global state in which the thunks are updated. For example, your environment could bind IORefs that contain unevaluated thunks to variable names and update them when the thunk is evaluated. But then your interpreter has to run in the IO monad. I agree that this would be the proper way to do it, but I was trying to minimize the use of monads since they have just been introduced in the course. That shouldn't be too hard. Just change your definition of monad M to newtype M a = M (State - IO (a, State)) and define the corresponding monad instance as an exercise :) (or ask me by private mail if you like). I'll try to implement it tomorrow. Hopefully I'll succeed without your help. ;) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] overloading show function
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))] now in any case when i print the monad, i just want to print the value and never the environment. More specific i want to use somthing like the following 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 however this gives me the following error message: Overlapping instances for Show (M (Value, Environment)) arising from a use of `print' Matching instances: instance (Show a, Show b) = Show (M (a, b)) -- Defined at /home/phil/code/haskell/vorlesung/ue09/ue09-3c3.hs:78:10-42 instance Show a = Show (M a) -- Defined at /home/phil/code/haskell/vorlesung/ue09/ue09-3c3.hs:82:10-29 In a stmt of an interactive GHCi command: print it Any ideas how to fix it? Thanks! Philipp ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] overloading show function
Thank you very much, this worked.
On 06/30/2011 12:03 AM, aditya siram wrote:
Try enabling OverlappingInstances extension by adding this to the top
of the file:
{-# LANGUAGE OverlappingInstances #-}
-deech
On Wed, Jun 29, 2011 at 4:50 PM, Philipp Schneider
philipp.schneid...@gmx.net wrote:
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))]
now in any case when i print the monad, i just want to print the value
and never the environment.
More specific i want to use somthing like the following
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
however this gives me the following error message:
Overlapping instances for Show (M (Value, Environment))
arising from a use of `print'
Matching instances:
instance (Show a, Show b) = Show (M (a, b))
-- Defined at
/home/phil/code/haskell/vorlesung/ue09/ue09-3c3.hs:78:10-42
instance Show a = Show (M a)
-- Defined at
/home/phil/code/haskell/vorlesung/ue09/ue09-3c3.hs:82:10-29
In a stmt of an interactive GHCi command: print it
Any ideas how to fix it? Thanks!
Philipp
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
