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,
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
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. 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