[Haskell-cafe] Re: Re: implementing recursive let

[Ryan Ingram]

The problem is that ErrorT makes any argument to mdo *much* more
strict, and therefore much more likely to loop.

This is because each action needs to know whether the previous action
was successful before it can continue.

Notice that when you got it to work, you *always* return "Right v";
that is, you never actually have an error.

If you want to avoid introducing bottoms into your code, I would avoid
using fix/mdo except in cases where you can prove that the code is
non-strict.  You keep running into cases where your code is more
strict than you would like which is introducing the bottoms.

To understand this better, consider the following function:

fixEither :: (a -> Either e a) -> Either e a
fixEither f = x where
    x = f a
    (Right a) = x

Here, f *cannot* attempt to do anything with its argument until it is
absolutely known that f is returning a "Right" value.

Perhaps there is a different way to write this interpreter that avoids
needing to tie the knot so tightly?  Can you split recursive-let into
two stages, one where you construct the environment with dummy
variables and a second where you populate them with the results of
their evaluations?  You might need some sort of mutable thunk that you
can store in the environment, which makes sense to me; in GHC Core,
"let" means "allocate a thunk on the heap".

  -- ryan

On 11/27/09, Ben Franksen <ben.franksen at online.de> wrote:
> Ben Franksen wrote:
>> Ok, it seems I have a version that does what I want. It is not very
>> elegant, I have to manually wrap/unwrap the ErrorT stuff just for the Val
>> case, but at least it seems to work. Here it goes:
>>
>>> eval (Var x) = Eval $ ErrorT $ do
>>>   env <- get
>>>   v <- case M.lookup x env of
>>>     Just v -> return v
>>>     Nothing -> do
>>>       warning ("reference to undefined variable " ++ show x)
>>>       let v = Data ""
>>>       modify (M.insert x v)
>>>       return v
>>>   return (Right v)
>>>
>>> warning s = tell $ ["Warning: " ++ s]
>
> While this works for simple var=constant declarations, it breaks down again
> as soon as I add lambdas and application. Same symptoms as before: eval
> loops; and it works again if I remove the ErrorT (but then I get a pattern
> match failure if I apply a non-function which is of course what I wanted to
> avoid with the ErrorT).
>
> This is maddening! There must be some way to get mutual recursion to work
> while still allowing for clean handling of failure. What galls me the most
> is that it is so unpredictable whether the program will terminate with a
> given input or not.
>
> (The code is attached.)
>
> Cheers
> Ben
>