[Haskell-cafe] overloading show function

[Holger Siegel]

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