views:

169

answers:

2

I'm writing an evaluator for a little expression language, but I'm stuck on the LetRec construct.

This is the language:

type Var = String
type Binds = [(Var, Expr)]

data Expr
  = Var     Var
  | Lam     Var    Expr
  | App     Expr   Expr
  | Con     Int
  | Sub     Expr   Expr
  | If      Expr   Expr  Expr
  | Let     Var    Expr  Expr
  | LetRec  Binds  Expr
  deriving (Show, Eq)

And this this the evaluator so far:

data Value
  = ValInt   Int
  | ValFun   Env   Var  Expr
  deriving (Show, Eq)

type Env = [(Var, Value)]

eval :: Env -> Expr -> Either String Value
eval env (Var x)       = maybe (throwError  $ x ++ " not found")
                               return
                               (lookup x env)
eval env (Lam x e)     = return $ ValFun env x e
eval env (App e1 e2)   = do
                         v1 <- eval env e1
                         v2 <- eval env e2
                         case v1 of
                           ValFun env1 x e -> eval ((x, v2):env1) e
                           _ -> throwError "First arg to App not a function"
eval _   (Con x)       = return $ ValInt x
eval env (Sub e1 e2)   = do
                         v1 <- eval env e1
                         v2 <- eval env e2
                         case (v1, v2) of
                           (ValInt x, ValInt y) -> return $ ValInt (x - y)
                           _ -> throwError "Both args to Sub must be ints"
eval env (If p t f)    = do 
                         v1 <- eval env p
                         case v1 of
                           ValInt x -> if x /= 0
                                       then eval env t
                                       else eval env f
                           _ -> throwError "First arg of If must be an int"
eval env (Let x e1 e2) = do
                         v1 <- eval env e1
                         eval ((x, v1):env) e2
eval env (LetRec bs e) = do
                         env' <- evalBinds
                         eval env' e
  where
    evalBinds = mfix $ \env' -> do
      env'' <- mapM (\(x, e') -> eval env' e' >>= \v -> return (x, v)) bs
      return $ nub (env'' ++ env)

This is my test function I want to evaluate:

test3 :: Expr
test3 = LetRec [ ("even", Lam "x" (If (Var "x")
                                      (Var "odd" `App` (Var "x" `Sub` Con 1))
                                      (Con 1)
                                  ))
               , ("odd",  Lam "x" (If (Var "x")
                                      (Var "even" `App` (Var "x" `Sub` Con 1))
                                      (Con 0)
                                  ))
               ]
               (Var "even" `App` Con 5)

EDIT:

Based on Travis' answer and Luke's comment, I've updated my code to use the MonadFix instance for the Error monad. The previous example works fine now! However, the example bellow doesn't work correctly:

test4 :: Expr
test4 = LetRec [ ("x", Con 3)
               , ("y", Var "x")
               ]
               (Con 0)

When evaluating this, the evaluator loops, and nothing happens. I'm guessing I've made something a bit too strict here, but I'm not sure what it is. Am I violating one of the MonadFix laws?

+1  A: 

Maybe I'm missing something, but doesn't the following work?

eval env (LetRec bs ex) = eval env' ex
  where
    env' = env ++ map (\(v, e) -> (v, eval env' e)) bs

For your updated version: What about the following approach? It works as desired on your test case, and doesn't throw away errors in LetRec expressions:

data Value
  = ValInt Int
  | ValFun EnvWithError Var Expr
  deriving (Show, Eq)

type Env = [(Var, Value)]
type EnvWithError = [(Var, Either String Value)]

eval :: Env -> Expr -> Either String Value
eval = eval' . map (second Right)
  where
    eval' :: EnvWithError -> Expr -> Either String Value
    eval' env (Var x)        = maybe (throwError  $ x ++ " not found")
                                     (join . return)
                                     (lookup x env)
    eval' env (Lam x e)      = return $ ValFun env x e
    eval' env (App e1 e2)    = do
                               v1 <- eval' env e1
                               v2 <- eval' env e2
                               case v1 of
                                 ValFun env1 x e -> eval' ((x, Right v2):env1) e
                                 _ -> throwError "First arg to App not a function"
    eval' _   (Con x)        = return $ ValInt x
    eval' env (Sub e1 e2)    = do
                               v1 <- eval' env e1
                               v2 <- eval' env e2
                               case (v1, v2) of
                                 (ValInt x, ValInt y) -> return $ ValInt (x - y)
                                 _ -> throwError "Both args to Sub must be ints"
    eval' env (If p t f)     = do 
                               v1 <- eval' env p
                               case v1 of
                                 ValInt x -> if x /= 0
                                             then eval' env t
                                             else eval' env f
                                 _ -> throwError "First arg of If must be an int"
    eval' env (Let x e1 e2)  = do
                               v1 <- eval' env e1
                               eval' ((x, Right v1):env) e2
    eval' env (LetRec bs ex) = eval' env' ex
      where
        env' = env ++ map (\(v, e) -> (v, eval' env' e)) bs
Travis Brown
When cleaning up my original code, I also removed the error messages the evaluator generates. I've updated my question.
Tom Lokhorst
Hmmm... yes, that does work. Although the `LetRec` bindings have now become lazy; If the body doesn't use the bindings, errors won't be printed. Also, I'm not sure if this will work with other monads. Like a Writer monad for printing logging information, I'll look into that. Thanks for all your help, btw!
Tom Lokhorst
It is possible to handle letrec using any monad that has a `MonadFix` instance.
luqui
+2  A: 

When Haskell throws a fit, that's usually an indication that you have not thought clearly about a core issue of your problem. In this case, the question is: which evaluation model do you want to use for your language? Call-by-value or call-by-need?

Your representation of environments as [(Var,Value)] suggests that you want to use call-by-value, since every Expr is evaluated to a Value right away before storing it in the environment. But letrec does not go well with that, and your second example shows!

Furthermore, note that the evaluation model of the host language (Haskell) will interfere with the evaluation model of the language you want to implement; in fact, that's what you are currently making use of for your examples: despite their purpose, your Values are not evaluated to weak head normal form.

Unless you have a clear picture of the evaluation model of your little expression language, you won't make much progress on letrec or on the error checking facilities.

Edit: For an example specification of letrec in a call-by-value language, have a look at the Ocaml Manual. On the simplest level, they only allow right-hand sides that are lambda expressions, i.e. things that are syntactically known to be values.

Heinrich Apfelmus
Those are good points, have an upvote! And yes, I want a call-by-value language, as the environment indicates. The particular reason I wanted `letrec` however, was to encode mutual recursive functions, I hadn't really thought about non-function values. I guess this means I should disallow non-function values in `letrec`, as they don't make much sense anyway.
Tom Lokhorst
Also, I think in this case Haskells laziness only serves as a way to implement sharing between the environments. Although its probably true that the forcing of some `Value` thunk is the reason the evaluator loops.
Tom Lokhorst
Added a link to the Ocaml manual for their specification of `letrec`. Concerning Haskell's laziness, *you* should force all `Value` s to get proper call-by-value semantics; this doesn't affect sharing. Concerning the current loop, I think the problem is the `lookup` in the first case of `eval`: it tries to inspect part of the environment whose very existence depends on the result of said `lookup`; this is circular.
Heinrich Apfelmus
Thanks for your help, I hadn't thought of looking at the OCaml manual. Especially the [recursive definition of values](http://caml.inria.fr/pub/docs/manual-ocaml/manual021.html#s:letrecvalues) language extension is interesting. I've accepted your answer.
Tom Lokhorst
Glad I could help. :-)
Heinrich Apfelmus