Evaluateur mutuellement récursif dans Haskell

Question

Mise à jour: J'ai ajouté an answer qui décrit ma solution finale (indice: le type de données Expr n'était pas suffisant).

---

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

C'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) 

C'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) 

---

MODIFIER:

Basé sur la réponse de Travis et le commentaire de Luke, j'ai mis à jour mon code pour utiliser l'instance MonadFix pour la monade d'erreur. L'exemple précédent fonctionne 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, l'évaluateur des boucles, et rien ne se passe. Je suppose que j'ai fait quelque chose d'un peu trop strict ici, mais je ne suis pas sûr de ce que c'est. Est-ce que je viole l'une des lois MonadFix?

Answer 1

Lorsque Haskell jette un ajustement, c'est généralement une indication que vous avez pas pensé clairement sur une question de base de votre problème . Dans ce cas, la question est: quel modèle d'évaluation voulez-vous utiliser pour votre langue? Appel par valeur ou appel par besoin?

Votre représentation des environnements comme [(Var,Value)] suggère que vous souhaitez utiliser droit d'appel par valeur, puisque chaque Expr est évalué à un Value loin avant de le ranger dans l'environnement. Mais letrec ne va pas bien avec cela, et votre deuxième exemple montre! Par ailleurs, notez que le modèle d'évaluation du langage hôte (Haskell) interférera avec le modèle d'évaluation du langage que vous souhaitez implémenter; en fait, c'est ce que vous utilisez actuellement pour vos exemples: malgré leur but, vos Value ne sont pas évalués à la forme normale de la tête faible.

À moins d'avoir une image claire du modèle d'évaluation de votre petit langage d'expression, vous ne progresserez pas beaucoup sur letrec ou sur les fonctions de vérification d'erreurs.

Edit: Pour un exemple de spécification letrec dans une langue appel par valeur, un coup d'oeil à la Ocaml Manual. Au niveau le plus simple, ils n'autorisent que les parties à droite qui sont des expressions lambda, c'est-à-dire des choses qui sont syntaxiquement connues comme étant des valeurs.

Answer 2

Peut-être qu'il me manque quelque chose, mais ne fonctionne pas?

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 de l'approche suivante? Il fonctionne comme vous le souhaitez sur votre cas de test, et ne jette pas des erreurs dans LetRec expressions:

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 que j'ai trouvée.

Comme Heinrich correctement pointed out, je n'ai pas vraiment réfléchi à l'impact de l'ordre d'évaluation.

Dans un langage strict (appel par valeur), une expression qui est déjà une valeur (forme normale de tête faible) est différente d'une expression qui nécessite encore une évaluation. Une fois que je codé cette distinction dans 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, est que j'ai sorti deux constructeurs (Con et Lam) dans leur propre type de données Val. Le type de données Expr a un nouveau constructeur Val, cela représente le fait qu'une valeur est également une expression valide.

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

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

Voir la complete code pour la fonction d'évaluateur mise à jour.