Wie kann ich in verschachtelten Monaden sauber arbeiten?

Question

Ich schreibe einen Dolmetscher für eine kleine Sprache. Diese Sprache unterstützt die Mutation, so dass ihr Evaluator für alle Variablen einen Store verfolgt (wobei type Store = Map.Map Address Value, type Address = Int und data Value ein sprachspezifischer ADT ist).

Es ist auch möglich, dass Berechnungen fehlschlagen (z. B. durch Null dividieren), so dass das Ergebnis ein Either String Value sein muss.

Die Art der mein Dolmetscher, dann ist

eval :: Environment -> Expression -> State Store (Either String Value) 

wo type Environment = Map.Map Identifier Address Spur von lokalen Bindungen hält.

Zum Beispiel eine konstante wörtliche Interpretation muss nicht in den Laden berühren, und das Ergebnis ist immer erfolgreich ist, so

eval _ (LiteralExpression v) = return $ Right v 

Aber wenn wir einen binären Operator anwenden, wir brauchen den Laden zu berücksichtigen. Wenn der Benutzer beispielsweise (+ (x <- (+ x 1)) (x <- (+ x 1))) auswertet und x anfänglich 0 lautet, sollte das Endergebnis 3 lauten und x sollte 2 im resultierenden Speicher sein. Dies führt zu dem Fall

eval env (BinaryOperator op l r) = do 
    lval <- eval env l 
    rval <- eval env r 
    return $ join $ liftM2 (applyBinop op) lval rval 

Beachten Sie, dass die do -Notation innerhalb des State Store Monade arbeiten. Weiterhin ist die Verwendung von return monomorph in State Store, während die Verwendungen join und liftM2 monomorph in der Either String Monade sind. Das heißt, hier verwenden wir

(return . join) :: Either String (Either String Value) -> State Store (Either String Value) 

und return . join ist kein No-Op.

(Wie ersichtlich, applyBinop :: Identifier -> Value -> Value -> Either String Value.)

Dies scheint bestenfalls verwirrend, und dies ist ein relativ einfacher Fall. Der Fall der Funktionsanwendung zum Beispiel ist wesentlich komplizierter.

Welche nützliche Best Practices sollte ich kennen, um meinen Code lesbar und schreibbar zu halten?

EDIT: Hier ist ein typisches Beispiel, das die Hässlichkeit besser darstellt. Die NewArrayC Variante hat die Parameter length :: Expression und element :: Expression (es erstellt ein Array mit einer gegebenen Länge mit allen Elementen, die auf eine Konstante initialisiert sind). Ein einfaches Beispiel ist (newArray 3 "foo"), die ["foo", "foo", "foo"] ergibt, aber wir könnten auch schreiben (newArray (+ 1 2) (concat "fo" "oo")), weil wir beliebige Ausdrücke in einem NewArrayC haben können. Aber wenn wir nennen tatsächlich

allocateMany :: Int -> Value -> State Store Address, 

, die die Anzahl der Elemente nimmt zuzuweisen und den Wert für jeden Slot und gibt die Startadresse, müssen wir diese Werte entpacken. In der Logik unten sehen Sie, dass ich eine Menge Logik vervielfältige, die in die Either Monade integriert werden sollte. Alle case s sollte nur gebunden werden.

eval env (NewArrayC len el) = do 
    lenVal <- eval env len 
    elVal <- eval env el 
    case lenVal of 
     Right (NumV lenNum) -> case elVal of 
      Right val -> do 
       addr <- allocateMany lenNum val 
       return $ Right $ ArrayV addr lenNum -- result data type 
      left  -> return left 
     Right _    -> return $ Left "expected number in new-array length" 
     left    -> return left 

Answer 1

Dies ist, wofür Monade-Transformatoren sind. Es gibt einen StateT Transformator, um einen Stapel zu einem Zustand hinzuzufügen, und einen EitherT Transformator, um Either - wie Fehler zu einem Stapel hinzuzufügen; Allerdings bevorzuge ich ExceptT (was Except ähnlich wie Fehler hinzufügt), so werde ich meine Diskussion in Bezug darauf geben. Da Sie das Stateful Bit am äußersten haben möchten, sollten Sie ExceptT e (State s) als Ihre Monade verwenden.

type DSL = ExceptT String (State Store) 

Beachten Sie, dass die Stateful-Operationen get und put geschrieben werden können, und diese sind polymorph über alle Instanzen MonadState; so dass sie insbesondere in unserer DSL monad funktionieren werden. In ähnlicher Weise ist der kanonische Weg, einen Fehler zu erzeugen, throwError, der über alle Instanzen von MonadError String polymorph ist; und insbesondere wird in unserer DSL Monade in Ordnung funktionieren.

So, jetzt wollen wir

eval :: Environment -> Expression -> DSL Value 
eval _ (Literal v) = return v 
eval e (Binary op l r) = liftM2 (applyBinop op) (eval e l) (eval e r) 

Sie könnten auch schreiben eval eine polymorphe Art betrachten zu geben; Es könnte eine (MonadError String m, MonadState Store m) => m Value anstelle einer DSL Value zurückgeben. In der Tat, für allocateMany, ist es wichtig, dass Sie ihm eine polymorphe Art geben:

allocateMany :: MonadState Store m => Int -> Value -> m Address 

Es gibt zwei Stücke von Interesse an dieser Art: Erstens, weil es polymorphe über alle MonadState Store m Instanzen ist, können Sie einfach so sicher sein, dass es hat nur stateful Nebenwirkungen, als ob es den Typ Int -> Value -> State Store Address hatte, den Sie vorschlugen. Jedoch, auch weil es polymorph ist, kann es darauf spezialisiert sein, eine DSL Address zurückzugeben, so dass es zum Beispiel in eval verwendet werden kann. Ihr Beispiel eval Code wird dies:

eval env (NewArrayC len el) = do 
    lenVal <- eval env len 
    elVal <- eval env el 
    case lenVal of 
     NumV lenNum -> allocateMany lenNum elVal 
     _   -> throwError "expected number in new-array length" 

Ich denke, das ist gut lesbar, wirklich; nichts zu fremdes dort.