Взаимно рекурсивный оценщик в Хаскеле
Обновление: я добавил ответ, который описывает мое окончательное решение (подсказка: единственный 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 для монады "Ошибка". Предыдущий пример теперь работает отлично! Однако приведенный ниже пример не работает правильно:
test4 :: Expr
test4 = LetRec [ ("x", Con 3)
, ("y", Var "x")
]
(Con 0)
Оценивая это, оценщик зацикливается, и ничего не происходит. Я предполагаю, что я сделал что-то слишком строгое, но я не уверен, что это такое. Я нарушаю один из законов MonadFix?
3 ответа
Когда Haskell подходит, это обычно указывает на то, что вы не продумали основную проблему вашей проблемы. В этом случае возникает вопрос: какую модель оценки вы хотите использовать для своего языка? Call-по стоимости или по требованию?
Ваше представление об окружающей среде как [(Var,Value)] предполагает, что вы хотите использовать вызов по значению, так как каждый Expr оценивается в Value прямо перед хранением в окружающей среде. Но letrec не очень хорошо с этим, и ваш второй пример показывает!
Кроме того, обратите внимание, что модель оценки основного языка (Haskell) будет мешать модели оценки языка, который вы хотите реализовать; фактически, это то, что вы сейчас используете для своих примеров: несмотря на их цель, ваш Value S не оцениваются в слабую голову нормальной формы.
Если у вас нет четкого представления о модели оценки вашего небольшого языка выражений, вы не добьетесь большого прогресса в letrec или на средствах проверки ошибок.
Редактировать: для примера спецификации letrec на языке вызовов по стоимости ознакомьтесь с Руководством по Ocaml. На простейшем уровне они допускают только правые части, являющиеся лямбда-выражениями, то есть вещи, которые синтаксически известны как значения.
Может быть, я что-то упустил, но разве не работает?
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
Отвечая на мой собственный вопрос; Я хотел поделиться окончательным решением, которое придумал.
Как правильно заметил Генрих, я не очень продумал, какое влияние оказывает порядок оценки.
В строгом (вызов по значению) языке выражение, которое уже является значением (нормальная форма слабой головы), отличается от выражения, которое все еще нуждается в некоторой оценке. Как только я закодировал это различие в моем типе данных, все стало на свои места:
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, где в глобальной области видимости могут быть определены только функции и константы.
Смотрите полный код для обновленной функции оценки.