Come posso lavorare in monade annidate in modo pulito?

Question

Sto scrivendo un interprete per una lingua piccola. Questo linguaggio supporta la mutazione, quindi il suo valutatore tiene traccia di uno Store per tutte le variabili (dove type Store = Map.Map Address Value, type Address = Int e data Value è un ADT specifico per la lingua).

È anche possibile che i calcoli non vadano a buon fine (ad es., Dividendo per zero), quindi il risultato deve essere un Either String Value.

Il tipo di mio interprete, poi, è

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

dove type Environment = Map.Map Identifier Address registra attacchi locali.

Per esempio, interpretando un letterale costante non ha bisogno di toccare il negozio, e il risultato riesce sempre, in modo da

eval _ (LiteralExpression v) = return $ Right v 

Ma quando applichiamo un operatore binario, abbiamo bisogno di prendere in considerazione il negozio. Ad esempio, se l'utente valuta (+ (x <- (+ x 1)) (x <- (+ x 1))) e x è inizialmente 0, il risultato finale deve essere 3 e 2 nel negozio risultante. Questo porta al caso

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

Si noti che il do -notation sta lavorando all'interno della State Store monade. Inoltre, l'uso di return è monomorfo in State Store, mentre gli usi di join e liftM2 sono monomorfi nella monade Either String. Cioè, qui usiamo

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

e return . join non è un no-op.

(Come è evidente, applyBinop :: Identifier -> Value -> Value -> Either String Value.)

Questo sembra confusa al massimo, e questo è un caso relativamente semplice. Il caso dell'applicazione della funzione, ad esempio, è notevolmente più complicato.

Quali utili best practice dovrei sapere per mantenere il mio codice leggibile e scrivibile?

MODIFICA: Ecco un esempio più tipico, che mostra meglio la bruttezza. La variante NewArrayC ha parametri length :: Expression e element :: Expression (crea una matrice di una determinata lunghezza con tutti gli elementi inizializzati su una costante). Un semplice esempio è (newArray 3 "foo"), che produce ["foo", "foo", "foo"], ma potremmo anche scrivere (newArray (+ 1 2) (concat "fo" "oo")), perché possiamo avere espressioni arbitrarie in un NewArrayC. Ma quando effettivamente chiamiamo

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

che prende il numero di elementi per allocare e il valore per ogni slot, e restituisce l'indirizzo di partenza, dobbiamo disfare tali valori. Nella logica sottostante, puoi vedere che sto duplicando un po 'di logica che dovrebbe essere integrata nella monade Either. Tutti i case devono essere semplicemente associati.

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

Questo è ciò che i trasformatori monad sono per. C'è un trasformatore StateT per aggiungere lo stato a uno stack e un trasformatore EitherT per aggiungere lo stack Either -like allo stack; tuttavia, preferisco ExceptT (che aggiunge Except -come errore), quindi darò la mia discussione in termini di ciò. Dal momento che vuoi il bit più preciso, dovresti usare ExceptT e (State s) come monade.

type DSL = ExceptT String (State Store) 

Nota che le operazioni di stateful possono essere scritte get e put, e questi sono polimorfici su tutte le istanze di MonadState; così che in particolare funzioneranno bene nella nostra monade DSL. Allo stesso modo, il modo canonico di generare un errore è throwError, che è polimorfico su tutte le istanze di MonadError String; e in particolare funzionerà bene nella nostra monade DSL.

Così ora avremmo scrivere

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) 

si potrebbe anche prendere in considerazione dando eval un tipo più polimorfico; potrebbe restituire un (MonadError String m, MonadState Store m) => m Value anziché uno DSL Value. Infatti, per allocateMany, è importante che si dà un tipo polimorfico:

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

Ci sono due pezzi di interesse su questo tipo: in primo luogo, perché è polimorfa su tutte le MonadState Store m casi, si può essere altrettanto sicuri che ha solo effetti secondari sullo stato come se avesse il tipo Int -> Value -> State Store Address suggerito. Tuttavia, anche perché è polimorfico, può essere specializzato per restituire uno DSL Address, quindi può essere utilizzato in (ad esempio) eval. Il codice di esempio eval diventa questo:

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" 

Penso che sia abbastanza leggibile, in realtà; niente di troppo estraneo lì.