évaluateur récursive en Haskell Mutually

Question

Mise à jour: J'ai ajouté une réponse qui décrit ma solution finale (indice: le type de données Expr seul ne suffisait pas).

---

Je écriture un évaluateur pour une langue peu d'expression, mais je suis coincé sur la LetRec construction.

Ceci est la langue:

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)

Et ce ce l'évaluateur jusqu'à présent:

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)

Ceci est ma fonction de test que je veux évaluer:

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)

---

EDIT:

D'après la réponse de Travis et le commentaire de Luc, je l'ai mis à jour mon code pour utiliser le MonadFix par exemple pour l'erreur monade. L'exemple précédent fonctionne très bien maintenant! Cependant, l'exemple ci-dessous ne fonctionne pas correctement:

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

Lors de l'évaluation cela, les boucles évaluateur, et rien ne se passe. Je devine que je l'ai fait quelque chose d'un peu trop stricte, mais je ne suis pas sûr de ce qu'il est. Suis-je ne respecte pas l'une des lois MonadFix?

Answer 1

Quand Haskell jette un ajustement, qui est habituellement une indication que vous avez pas pensé clairement sur une question de base de votre problème. Dans ce cas, la question est: qui modèle d'évaluation vous souhaitez utiliser pour votre langue? Appel par valeur ou appel par le besoin?

Votre représentation des environnements comme [(Var,Value)] suggère que vous souhaitez utiliser l'appel par valeur, puisque chaque Expr est évalué à un Value tout de suite avant de le ranger dans l'environnement. Mais letrec ne va pas bien avec cela, et votre deuxième exemple montre!

En outre, notez que le modèle d'évaluation de la langue d'accueil (Haskell) va interférer avec le modèle d'évaluation de la langue que vous souhaitez mettre en œuvre; en fait, c'est ce que vous faites actuellement l'utilisation de vos exemples: en dépit de leur but, vos Values ne sont pas évalués à la tête faible forme normale

.

Sauf si vous avez une image claire du modèle d'évaluation de votre langue peu d'expression, vous ne serez pas faire beaucoup de progrès sur letrec ou sur l'erreur Systèmes de contrôle.

Edit: Pour un exemple de spécification letrec dans une langue appel par valeur, un coup d'oeil à la Ocaml Manuel . Au niveau le plus simple, ils ne permettent Droites qui sont des expressions lambda, à savoir les choses qui sont syntaxiquement connus pour être des valeurs.

Answer 2

Peut-être que je manque quelque chose, mais ne pas les travaux suivants?

eval env (LetRec bs ex) = eval env' ex
  where
    env' = env ++ map (\(v, e) -> (v, eval env' e)) bs

Pour votre version mise à jour: Qu'en est-il l'approche suivante? Il fonctionne comme vous le souhaitez sur votre cas de test, et ne jette pas des erreurs dans les expressions 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

répondre à ma propre question; Je voulais partager la solution finale, je suis venu avec.

Comme sur Heinrich pointu correctement , je ne pas vraiment réfléchir à l'impact de l'ordre d'évaluation a.

Dans une langue stricte (appel par valeur), une expression qui est déjà une valeur (tête faible forme normale) est différent d'une expression qui a encore besoin d'évaluation. Une fois que je cette distinction dans encodé mon type de données, tout est tombé en place:

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)

La seule différence avec mon mon type de données Expr original, que j'ai sorti deux constructeurs (Con et Lam) dans leur propre Val de type de données. Le type de données Expr a un nouveau Val constructeur, cela représente le fait qu'une valeur est aussi une expression valide.

Avec des valeurs dans leur propre type de données, elles peuvent être traitées séparément une autre expression, par exemple les liaisons de letrec ne peut contenir des valeurs, pas d'autres expressions.

Cette distinction est également faite dans d'autres langues strictes comme C, où seules les fonctions et les constantes peuvent être définies dans une portée globale.

Voir la code complet pour la fonction évaluateur mise à jour.