[Haskell-cafe] overloading show function

[Holger Siegel]

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.


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