Взаимно рекурсивный оценщик в Хаскелле

Question

Обновлять: я добавил Ответ Это описывает мое окончательное решение (подсказка: сингл 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 для ошибки Monad. Предыдущий пример работает нормально! Тем не менее, пример Bellow не работает правильно:

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

При оценке этого, оценка петли, и ничего не происходит. Я предполагаю, что я сделал что -то слишком строгое здесь, но я не уверен, что это такое. Я нарушаю один из законов Monadfix?

Answer 1

Когда Хэскелл подходит, это обычно это указывает на то, что вы не думали ясно о основной проблеме вашей проблемы. В этом случае вопрос: кто модель оценки Вы хотите использовать для своего языка? Позвоните по цене или по вызову?

Ваше представление об окружающей среде как [(Var,Value)] предполагает, что вы хотите использовать вызов, так как каждый Expr оценивается в Value сразу, прежде чем хранить его в окружающей среде. Но letrec с этим не очень хорошо, и ваш второй пример показывает!

Кроме того, обратите внимание, что модель оценки языка хоста (Хаскелл) будет мешать модели оценки языка, который вы хотите реализовать; На самом деле, это то, что вы сейчас используете для своих примеров: несмотря на их цель, ваша ValueS не оцениваются до слабой головы нормальной формы.

Если у вас нет четкой картины модели оценки вашего небольшого языка выражения, вы не будете добиваться большого прогресса в letrec или на установках ошибок.

Редактировать:Для примера спецификации letrec На языке вызовов посмотрите на OCAML Руководство. Анкет На самом простом уровне они допускают только правые стороны, которые являются выражениями 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

Отвечая на мой собственный вопрос; Я хотел поделиться окончательным решением, которое я придумал.

Как Генрич правильно указал, Я действительно не продумал влияние, которое оказал заказ оценки.

На строгом (вызовом) языке выражение, которое уже является значением (слабая нормальная форма головы), отличается от выражения, которое все еще требует некоторой оценки. Как только я закодировал это различие в своем типе данных, все встало:

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, где только функции и константы могут быть определены в глобальном объеме.

Увидеть Полный код Для обновленной функции оценщика.