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).
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
