我正在为一种小表达式语言编写一个评估器,但我被困在这个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))