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!
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.
By the way, do you already know Peter Sestoft's paper "Deriving a lazy abstract
machine"?
Cheers, Holger
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
