2

更新：我添加了一个描述我最终解决方案的答案（提示：单一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)

编辑：

根据 Travis 的回答和 Luke 的评论，我更新了我的代码以将 MonadFix 实例用于 Error monad。前面的示例现在可以正常工作了！但是，下面的示例无法正常工作：

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

评估时，评估器循环，没有任何反应。我猜我在这里做了一些过于严格的事情，但我不确定它是什么。我是否违反了 MonadFix 法律之一？

4

3 回答 3

4

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

您对环境的[(Var,Value)]表示表明您希望使用按值调用，因为在将其存储在环境中之前，每个都Expr被立即评估为 a 。Value但这letrec并不顺利，你的第二个例子显示了！

此外，请注意宿主语言（Haskell）的评估模型会干扰您要实现的语言的评估模型；实际上，这就是您目前在示例中使用的内容：尽管有其目的，但您Value的 s 并未评估为弱头部正常形式。

除非您清楚地了解您的小表达式语言的评估模型，否则您不会在错误检查工具上letrec或在错误检查工具上取得太大进展。

编辑： 有关按值调用语言的示例规范，letrec请查看Ocaml Manual。在最简单的层面上，它们只允许 lambda 表达式的右侧，即在语法上已知为值的事物。

于 2010-08-20T12:01:59.547 回答
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
于 2010-08-19T19:04:33.557 回答
1

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

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

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

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

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

于 2010-12-21T21:43:13.727 回答