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
