Haskell中的相互遞歸求值器

Question

更新：我已經添加了an answer，它描述了我的最終解決方案（提示：單個的Expr數據類型是不夠的）。

---

我writing一點點表達式語言的評估，但是我卡上的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的評論，我更新了我的code以針對Error monad使用MonadFix實例。前面的例子現在工作正常！但是，示例波紋管不能正常工作：

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

評估此操作時，評估程序會循環，並且什麼都不會發生。我猜我在這裏做了一些太嚴格的事情，但我不確定它是什麼。我違反MonadFix法律之一嗎？

Answer 1

當哈斯克爾拋出一個合適的，這通常是你有沒有清楚地想過你的問題的一個核心問題的指示。在這種情況下，問題是：您想使用哪種評估模型您的語言？按價值撥打還是按需撥號？

您將環境表示爲[(Var,Value)]表明您希望使用按值撥打電話，因爲每個Expr在將其存儲在環境中之前立即被評估爲Value。但是letrec不適合那個，你的第二個例子顯示！此外，請注意宿主語言（Haskell）的評估模型將干擾您要實施的語言的評估模型;事實上，這就是你正在使用的例子：儘管他們的目的，你的Value s不評估弱頭正常形式。

除非您對小表達式語言的評估模型有清晰的瞭解，否則您在letrec或錯誤檢查工具上不會取得很大進展。

編輯： 對於letrec在呼叫按值語言的例子說明，看看在Ocaml Manual。在最簡單的層面上，它們只允許右側是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

回答我自己的問題;我想分享我提出的最終解決方案。

正如海因裏希正確pointed out，我並沒有真正考慮評估訂單的影響。

在嚴格的（按值調用）語言中，已經是值（弱頭標準形式）的表達式與仍需要某些評估的表達式不同。有一次，我在我的數據類型編碼的這種區別，一切就明白了：

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中進行的，其中只有函數和常量可以在全局範圍內定義。

查看complete code獲取更新的評估函數。