[Haskell-cafe] Re: Re: Re: implementing recursive let
Ryan Ingram wrote: 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. Thanks, you are confirming what I suspected. I just wasn't sure that I didn't do something stupid that could easily be fixed. Notice that when you got it to work, you *always* return Right v; that is, you never actually have an error. Yes, exactly. It helps in the simplest cases, but with function definitions even this is not enough. 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. Interesting. I'll have to think about this one. 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. Yea, this is how I would do it in an imperative language. I thought I could avoid mtuable cells by exploiting lazyness. I am not yet ready to give up, however. One thing I want to try is whether I can come up with a variation of ErrorT that is less strict. Another idea I just had is that maybe continuations might help, as they provide a possibility to 'jump' out of a calculation. Chers Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: Re: implementing recursive let
On Fri, Nov 27, 2009 at 1:40 PM, Ben Franksen ben.frank...@online.de wrote: Thanks, you are confirming what I suspected. I just wasn't sure that I didn't do something stupid that could easily be fixed. Well, lets unwrap your newtype into the actual functions: Eval (ErrorT String (StateT Env (Writer [String])) a) ErrorT e m a ~= m (Either e a) StateT s m a ~= s - m (a,s) Writer w a ~= (a,w) So we have Eval a ~= ErrorT String (StateT Env (Writer [String])) a) ~= StateT Env (Writer [String])) (Either String a) ~= Env - Writer [String] (Either String a, Env) ~= Env - ((Either String a, Env), [String]) Also I notice you really only use Eval Value; everything else is just minor side effects. So this is pretty clear; we are given an environment, and we need to return another environment, a list of strings, and either an error message or a Value. Now the question is, what do you want to happen when given a malformed let expression? I am pretty sure that you need more complicated flow-control here in order to get the result. I believe you are on the right track with continuations. Here is a question; what should these expressions do? let y = x; x = 1 in y let y = x x; x = 1 in x let x = x in x The last one is quite telling; I can see three possible behaviors here: 1) Loop 2) return some simple undefined value 3) Give an error blackhole I will note that behavior (1) seems very difficult to achieve with your current monad stack; eval (Var x) terminates simply by looking up the value in the environment. I think you need to think hard about evaluation order and decide what you really want to happen. The simplest answer, if you want to stay with strict evaluation, is probably to only allow recursive *function* definitions. This way you can delay fully initializing the environment until after you've finished evaluating the functions themselves. Also, your definition of Function seems to have problems with scoping; unless you intended to make a dynamically scoped language, (Value - Eval Value) seems very likely to get evaluated in the context it is called in. -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
