Wechselseitig rekursive Auswerter in Haskell

Question

Update: Ich habe hinzugefügt, um eine Antwort , dass meine endgültige Lösung (Hinweis: der einzigen Expr Datentyp war nicht ausreichend) beschreibt.

---

Ich Schreiben Evaluator für eine wenig Ausdruckssprache, aber ich bin fest auf der LetRec Konstrukt.

Dies ist die Sprache:

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)

Und das dies der Evaluator so weit:

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)

Das ist meine Testfunktion I auswerten möchten:

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:

Auf der Grundlage von Travis' Antwort und Lukes Kommentar habe ich meine Code die MonadFix zu verwenden Beispiel für den Fehler Monade. Das obige Beispiel funktioniert jetzt! Allerdings ist das Beispiel unten nicht korrekt funktionieren:

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

Wenn diese Auswertung, Schleifen der Evaluator, und nichts passiert. Ich schätze, dass ich etwas ein bisschen zu streng hier gemacht habe, aber ich bin nicht sicher, was es ist. Bin ich da mindestens eine der MonadFix Gesetze?

Answer 1

Wenn Haskell wirft einen Sitz, die in der Regel ist ein Hinweis darauf, dass Sie nicht gedacht, eindeutig um eine Kernfrage des Problems. In diesem Fall stellt sich die Frage: Welche Bewertungsmodell haben Sie für Ihre Sprache verwenden möchten? Call-by-Wert oder Call-by-Bedarf?

Ihre Darstellung von Umgebungen wie [(Var,Value)] schlägt vor, dass Sie Call-by-Wert verwendet werden sollen, da jeder Expr zu einem Value ausgewertet wird sofort, bevor es in der Umwelt zu speichern. Aber letrec nicht gut gehen mit dem, und Ihrem zweiten Beispiel zeigt!

Darüber hinaus beachten Sie, dass das Bewertungsmodell der Hostsprache (Haskell) mit dem Bewertungsmodell der Sprache stört Sie implementieren möchten; in der Tat, das ist, was Sie verwenden derzeit für Ihre Beispiele zu machen sind: trotz ihrer Absicht, Ihre Values nicht zu schwacher Kopfnormalform ausgewertet werden

.

Wenn Sie ein klares Bild von dem Bewertungsmodell Ihrer kleinen Ausdruckssprache haben, werden Sie nicht vielen Fortschritt auf letrec machen oder auf der Fehlerprüfung Einrichtungen.

Edit: Ein Beispiel für die Spezifikation von letrec in einem Call-by-value Sprache, haben einen Blick auf die Ocaml Handbuch . Auf der einfachsten Ebene, sie erlauben nur die rechten Seiten, die Lambda-Ausdrücke sind, das heißt Dinge, die syntaktisch bekannt sind, Werte zu sein.

Answer 2

Vielleicht bin ich etwas fehlt, aber nicht mit dieser Arbeit?

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

Für Ihre aktualisierte Version: Was ist mit dem folgenden Ansatz? Es funktioniert wie auf Ihrem Testfall gewünscht wird, und wirft keine Fehler in LetRec Ausdrücke entfernt:

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

meine eigene Frage zu beantworten; Ich wollte die endgültige Lösung teilen, die ich kam mit.

Als Heinrich richtig wies darauf hin , habe ich nicht wirklich denken über die Auswirkungen der Auswertungsreihenfolge hat.

In einem strengen (Call-by-value) Sprache, ein Ausdruck, der bereits ein Wert (schwache Kopfnormalform) unterscheidet sich von einem Ausdruck, dass noch einige Auswertung benötigt. Sobald ich diese Unterscheidung in meinem Datentyp codiert, alles an seinem Platz:

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)

Der einzige Unterschied mit meiner meinem ursprünglichen Expr Datentyp, ist, dass ich zwei Konstruktoren herausgezogen (Con und Lam) in ihre eigenen Datentyp Val. Der Expr Datentyp einen neuen Konstruktor Val hat, bedeutet dies, dass ein Wert ist auch ein gültiger Ausdruck.

Mit Werten in ihren eigenen Datentyp, können sie getrennt von anderen Ausdruck behandelt werden, zum Beispiel letrec Bindungen nur Werte enthalten, keine anderen Ausdrücke.

Diese Unterscheidung auch in anderen strengen Sprachen wie C gemacht wird, wo nur Funktionen und Konstanten können in globalem Bereich definiert werden.

Siehe vollständiger Code für die aktualisierte Auswertungsfunktion.