Haskell中的相互递归评估器

Question

更新： 我已经添加 答案 描述了我的最终解决方案（提示：单曲 Expr 数据类型还不够）。

---

我是 写作 一种评估者的一种表达语言，但我陷入了 LetRec 构造。

这是语言：

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)

到目前为止，这是评估者：

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)

这是我要评估的测试功能：

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)

---

编辑：

根据特拉维斯的回答和卢克的评论，我已经更新了 代码 使用MonadFix实例进行错误单元。上一个示例现在正常工作！但是，示例Bellow无法正常工作：

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

在评估它时，评估器循环，什么也不会发生。我猜想我在这里做了一些太严格，但是我不确定这是什么。我是否违反了一项MonadFix法律？

Answer 1

当哈斯克尔（Haskell）带来合适的情况时，通常表明您对问题的核心问题并不清楚。在这种情况下，问题是：哪个 评估模型 您想用作语言吗？逐个通话或逐个通话？

您对环境的表示 [(Var,Value)] 建议您要逐个通话，因为每次 Expr 被评估为 Value 立即将其存储在环境中。但 letrec 与此相关，您的第二个示例显示！

此外，请注意，主机语言的评估模型（Haskell）将干扰您要实施的语言的评估模型；实际上，这就是您目前正在使用的示例：尽管有目的，但您 Values未评估为弱的正态形式。

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

编辑：对于示例规范 letrec 用价值呼叫的语言，看看 OCAML手册. 。在最简单的层面上，它们仅允许右侧是lambda表达式，即句法是值为值的东西。

Answer 2

也许我缺少一些东西，但没有以下工作？

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

对于您的更新版本：以下方法呢？它在您的测试案例上根据需要起作用，并且不会丢弃错误 LetRec 表达式：

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

Answer 3

回答我自己的问题；我想分享我想出的最终解决方案。

正如海因里希（Heinrich）正确 指出, ，我并没有真正考虑评估顺序的影响。

在严格的（逐个呼叫）语言中，一个已经是值（弱头部正常形式）的表达式与仍然需要评估的表达式不同。一旦我在数据类型中编码了这种区别后，一切都落入到位：

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

data Val
  = Con Int
  | Lam Var Expr
  deriving (Show, Eq)

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

与我的原始的唯一区别 Expr 数据类型是我拔出了两个构造函数（Con 和 Lam）进入他们自己的数据类型 Val. 。这 Expr 数据类型具有新的构造函数 Val, ，这表示值也是一个有效的表达式。

具有自己的数据类型中的值，可以与其他表达式分开处理，例如 letrec 绑定只能包含值，没有其他表达式。

这种区别也用其他严格的语言（例如C）进行，其中只能在全球范围中定义函数和常数。

看到 完成代码 对于更新的评估器功能。