用于在Haskell中定义实现little语言的letrec的表达式

我正在为一个小的表达式语言编写一个计算器，但我被LetRec结构卡住了。

这是一种语言：

data Expr = Var Nm  | Lam (Nm,Ty) Expr | App Expr Expr
| Val Int | Add Expr Expr | If Expr Expr Expr
| Let Nm Expr Expr
| LetRec [((Nm,Ty),Expr)] Expr

这是迄今为止的评估者：

type Env = [ (Nm, Value) ]
data Value = Clos Env Expr
| Vint Int
deriving Show
eval :: Env -> Expr -> Value
eval _   (Val n) = Vint n 
eval env (Add e1 e2) = Vint (n1 + n2)  
where
Vint n1 = eval env e1  
Vint n2 = eval env e2
eval env (If e e1 e0) = if n==0 then eval env e0 else eval env e1
where 
Vint n = eval env e
eval env (Var x) = case lookup x env of
Nothing -> error (x)
Just v  -> v
eval env (Lam x e) = Clos env (Lam x e)
eval env (App e1 e2) = case v1 of
Clos env1 (Lam (x,t) e) -> eval ((x,v2):env1) e
where
v1 = eval env e1
v2 = eval env e2
eval env (Let x e1 e2) = eval env' e2
where 
env' = (x,v) : env
v = eval env e1
eval env (LetRec [((x,t),e)] e1) = eval env' e1
where
env' = env ++ map ((v,e) -> (v, eval env' e)) [(x,e)]

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

t1 = LetRec
[ (("not",  INT:->INT), Lam ("i",INT) $ If (Var "i")
(Val 0)
(Val 1))
, (("even", INT:->INT), Lam ("i",INT) $ If (Var "i")
(App (Var "not")
(App (Var "odd") 
(Var "i" `Add` Val (-1))))
(Val 1))
, (("odd",  INT:->INT), Lam ("i",INT) $ If (Var "i")
(App (Var "not") 
(App (Var "even") 
(Var "i" `Add` Val (-1))))
(Val 0))
]
(App (Var "odd") (Val 7))

请注意，您的测试程序是错误的。你不想申请"；而不是"；。如果n-1是奇数，则数字n是偶数，而不是如果它不是奇数。所以，它应该是：
t1 = LetRec [ (("even", INT:->INT), Lam ("i",INT) $ If (Var "i") (App (Var "odd") (Var "i" `Add` Val (-1))) (Val 1)) , (("odd", INT:->INT), Lam ("i",INT) $ If (Var "i") (App (Var "even") (Var "i" `Add` Val (-1))) (Val 0)) ] (App (Var "odd") (Val 7))
您的LetRec案例几乎正确。出于某种原因，您刚刚将其编写为仅处理单例列表。此外，您希望将letrec绑定放在环境绑定列表的开头，而不是末尾，否则letrec之外的绑定将优先。尝试：

eval env (LetRec bnds body) = v where v = eval env' body env' = [(n, eval env' e) | ((n,_),e) <- bnds] ++ env
这是完整的程序。运行时应打印Vint 1:

type Nm = String data Ty = INT | Ty :-> Ty deriving (Show) data Expr = Var Nm | Lam (Nm,Ty) Expr | App Expr Expr | Val Int | Add Expr Expr | If Expr Expr Expr | Let Nm Expr Expr | LetRec [((Nm,Ty),Expr)] Expr deriving (Show) type Env = [ (Nm, Value) ] data Value = Clos Env Expr | Vint Int deriving (Show) eval :: Env -> Expr -> Value eval _ (Val n) = Vint n eval env (Add e1 e2) = Vint (n1 + n2) where Vint n1 = eval env e1 Vint n2 = eval env e2 eval env (If e e1 e0) = if n==0 then eval env e0 else eval env e1 where Vint n = eval env e eval env (Var x) = case lookup x env of Nothing -> error (x ++ " not defined") Just v -> v eval env e@(Lam _ _) = Clos env e eval env (App e1 e2) = case v1 of Clos env1 (Lam (x,t) e) -> eval ((x,v2):env1) e where v1 = eval env e1 v2 = eval env e2 eval env (Let x e1 e2) = eval env' e2 where env' = (x,v) : env v = eval env e1 eval env (LetRec bnds body) = eval env' body where env' = [(n, eval env' e) | ((n,_),e) <- bnds] ++ env t1 :: Expr t1 = LetRec [ (("even", INT:->INT), Lam ("i",INT) $ If (Var "i") (App (Var "odd") (Var "i" `Add` Val (-1))) (Val 1)) , (("odd", INT:->INT), Lam ("i",INT) $ If (Var "i") (App (Var "even") (Var "i" `Add` Val (-1))) (Val 0)) ] (App (Var "odd") (Val 7)) main :: IO () main = print (eval [] t1)

相关内容

最新更新

热门标签：