[Haskell-cafe] Re: implementing recursive let

[Derek Elkins]

On Wed, Nov 25, 2009 at 3:48 PM, Ben Franksen <ben.franksen at online.de> wrote:
> Derek Elkins wrote:
>> The following code works fine for me, so it seems you are missing some
>> details that may help.
>> [...snip code...]
>
> Thank you! Indeed I did simplify the code when writing the message --
> because I thought that those other bits could not possibly be at
> fault... ;-)
>
> *trying out many changes to my own code and yours*
>
> Ok, I finally found it. What actually made the difference was the case for
> variables:
>
> Your version is
>
>> eval (Var x)   = gets (fromJust . M.lookup x)
>
> which is suitably lazy, whereas mine was (more or less)
>
>> eval e@(Var name) = do
>>   env <- ask
>>   case M.lookup name env of
>>     Nothing  -> do
>>       -- undefined variable reference
>>       warning ("reference to undefined variable " ++ show name)
>>       let val = Data ""
>>       modify (M.insert name val)
>>       return val
>>     Just val -> return val
>
> Note that whatever I do in the 'Nothing' case is irrelevant, your code with
> the Var case replaced by
>
>> eval e@(Var name) = do
>>   env <- ask
>>   case M.lookup name env of
>>     Just val -> return val
>
> loops as well.
>
> My problem is that I still don't understand why this is so! I know of course
> that pattern matching is strict, but I thought this should be ok here,
> since I evaluate the declarations _before_ the body, so when evaluation of
> the body demands the variable, it will be defined.
>
> What am I missing?

The problem is the liftM2 in the Let branch of eval.  You are
executing the body while making the bindings, so you are trying to
look up x while you are still trying to bind it.  One solution is to
move the execution of the body after the binding as in:

eval (Let decls body) = mdo
 let (names,exprs) = unzip decls
     updateEnv env = foldr (uncurry M.insert) env $ zip names values
 values <- local updateEnv $ mapM eval exprs
 local updateEnv $ eval body