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 实例作为 Error monad。前面的例子现在可以正常工作了！但是，下面的示例无法正常工作：

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

评估此示例时，评估器会循环，并且不会发生任何事情。我猜我在这里做了一些过于严格的事情，但我不确定它是什么。我是否违反了 MonadFix 法律之一？

Answer 1

当 Haskell 发脾气时，通常表明你还没有清楚地思考问题的核心问题。在这种情况下，问题是：您想要为您的语言使用哪种评估模型？按价值调用还是按需求调用？

您将环境表示为 [(Var,Value)] 表明您希望使用按值调用，因为每个 Expr 都会评估为 Value< /code> 立即将其存储在环境中。但是 letrec 并不能很好地适应这一点，你的第二个例子表明了这一点！

此外，请注意，宿主语言（Haskell）的评估模型会干扰您要实现的语言的评估模型；事实上，这就是您当前在示例中使用的内容：无论其目的如何，您的 Value 都不会被评估为弱头正常形式。

除非您清楚地了解您的小表达式语言的评估模型，否则您不会在 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

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

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

在严格（按值调用）语言中，已经是值的表达式（弱头范式）与仍需要某些计算的表达式不同。一旦我在数据类型中编码了这种区别，一切就都到位了：

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）中也存在，其中只能在全局范围内定义函数和常量。

有关更新的评估器函数，请参阅完整代码。