valutatore reciprocamente ricorsivo in Haskell

Question

Aggiornamento: Ho aggiunto una risposta che descrive la mia soluzione definitiva (suggerimento: il tipo di dati singola Expr non era sufficiente).

---

scrivendo un valutatore per un po 'di linguaggio delle espressioni, ma mi sono bloccato sulla LetRec costrutto.

Questa è la lingua:

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)

E questo questo il valutatore finora:

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)

Questa è la mia funzione di test voglio valutare:

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)

---

Modifica

In base alla risposta di Travis' e il commento di Luca, ho aggiornato il mio codice di utilizzare la MonadFix istanza per l'Error monade. L'esempio precedente funziona bene ora! Tuttavia, l'esempio soffietto non funziona correttamente:

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

Nel valutare questo, il valutatore loop, e non succede nulla. Sto indovinando che ho fatto qualcosa di un po 'troppo severo qui, ma non sono sicuro di cosa si tratta. Am I violando una delle leggi MonadFix?

Answer 1

Quando Haskell lancia un attacco, che di solito è un'indicazione che non avete pensato con chiarezza su una questione fondamentale del problema. In questo caso, la domanda è: quale modello di valutazione vuoi utilizzare per la propria lingua? Chiamata per valore o chiamata per necessità?

Il tuo rappresentazione di ambienti come [(Var,Value)] suggerisce che si desidera utilizzare call-by-value, dal momento che ogni Expr viene valutata ad un Value subito prima di riporla in un ambiente. Ma letrec non va bene con quello, e il tuo secondo esempio mostra!

Inoltre, nota che il modello di valutazione della lingua del paese ospitante (Haskell) interferirà con il modello di valutazione della lingua che si desidera implementare; in effetti, è quello che si sta facendo uso di per i vostri esempi: nonostante la loro finalità, i suoi Values non vengono valutati a forma normale testa debole

.

Se non avete un quadro chiaro del modello di valutazione del tuo piccolo linguaggio delle espressioni, è non farà molti progressi sulla letrec o sul controllo degli errori strutture.

Modifica Per un esempio di specifica letrec in una lingua chiamata per valore, hanno uno sguardo al Manuale O'Caml . Al livello più semplice, che permettono solo sul lato destro che sono le espressioni lambda, vale a dire le cose che sono noti per essere sintatticamente valori.

Answer 2

Forse mi manca qualcosa, ma non lo fa il seguente lavoro?

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

Per la vostra versione aggiornata: Che cosa circa il seguente approccio? Funziona come desiderata sul banco di prova, e non buttare via gli errori nelle espressioni 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

Rispondendo alla mia domanda; Volevo condividere la soluzione finale mi è venuta.

Come Heinrich correttamente sottolineato , non l'ho fatto davvero pensare attraverso l'impatto l'ordine di valutazione ha.

In un linguaggio rigoroso (call-by-value), un'espressione che è già un valore (forma normale testa debole) è diverso da un'espressione che necessita ancora qualche valutazione. Una volta che ho codificato questa distinzione nel mio tipo di dati, tutto è andato a posto:

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)

L'unica differenza con il mio il mio tipo di dati Expr originale, è che ho tirato fuori due costruttori (Con e Lam) nel proprio tipo di dati Val. Il tipo di dati Expr ha un nuovo Val costruttore, questo rappresenta il fatto che un valore è anche un'espressione valida.

Con valori nel loro tipo di dati, possono essere manipolati separatamente dagli altri espressione, per esempio, attacchi letrec può contenere solo i valori, non altre espressioni.

Questa distinzione è fatta anche in altre lingue severe come il C, dove solo le funzioni e le costanti possono essere definite in ambito globale.

completa codice per la funzione di valutatore aggiornato.