Haskell中的相互递归评估器

本文介绍了Haskell中的相互递归评估器的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

更新:我添加了一个答案描述了我的最终解决方案(提示:单个 Expr 数据类型还不够).

Update: I've added an answer that describes my final solution (hint: the single Expr data type wasn't sufficient).

我编写一种表达语言的评估程序，但我仍然坚持 LetRec 构造.

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

这是语言:

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)

根据Travis的回答和Luke的评论，我更新了代码以使用MonadFixError monad的实例.前面的示例现在可以正常工作！但是，下面的示例无法正常工作:

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)

当对此进行评估时，评估器会循环，并且什么也没有发生.我猜我在这里做了一些太严格的规定，但是我不确定是什么.我违反了MonadFix的其中一项法律吗?

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?

推荐答案

当Haskell提出要求时，通常表明您没有清楚地考虑问题的核心问题.在这种情况下，问题是:您要为您的语言使用哪种评估模型?按价值致电还是按需致电?

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?

您将环境表示为 [(Var，Value)] 表示您希望使用按值调用，因为每个 Expr 均被评估为 Value ，然后将其存储在环境中.但是 letrec 不能很好地做到这一点，第二个示例显示了！

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!

此外，请注意，宿主语言(Haskell)的评估模型将干扰您要实现的语言的评估模型；实际上，这就是您当前在示例中使用的内容:尽管有其用途，但您的 Value 并没有被评估为弱头范式.

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.

除非您对小表达语言的评估模型有清晰的了解，否则在 letrec 或错误检查工具上不会有太大进展.

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.

修改:有关使用值调用语言的 letrec 的示例规范，请查看 Ocaml手册.从最简单的角度讲，它们只允许使用lambda表达式的右手边，即在语法上已知为值的东西.

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.