Как я могу работать во вложенных монадах чисто?

Question

Я пишу переводчика для небольшого языка. Этот язык поддерживает мутацию, поэтому его оценщик отслеживает Store для всех переменных (где type Store = Map.Map Address Value, type Address = Int и data Value - это специфический для языка ADT).

Также возможно, чтобы вычисления были сбой (например, деление на ноль), поэтому результат должен быть Either String Value.

Тип моего переводчика, то есть

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

где type Environment = Map.Map Identifier Address отслеживает локальных привязок.

Например, интерпретации постоянного Литерал не нужно трогать магазин, и результат всегда удается, так

eval _ (LiteralExpression v) = return $ Right v 

Но когда мы применяем бинарную операцию, нам необходимо рассмотреть магазин. Например, если пользователь производит вычисления (+ (x <- (+ x 1)) (x <- (+ x 1))) и x изначально 0, тогда конечный результат должен быть 3, а x должен быть 2 в полученном магазине. Это приводит к случаю

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

Обратите внимание, что do -notation работает в State Store монады. Кроме того, использование return мономорфно в State Store, а использование join и liftM2 мономорфно в монаде Either String. То есть, здесь мы используем

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

и return . join не является не-ор.

(Как видно, applyBinop :: Identifier -> Value -> Value -> Either String Value.)

Это кажется запутанным, в лучшем случае, и это относительно простой случай. Случай приложения функции, например, значительно сложнее.

Какие полезные рекомендации следует знать о том, чтобы мой код был удобочитаемым и доступным для записи?

EDIT: Вот более типичный пример, который лучше демонстрирует уродство. Вариант NewArrayC имеет параметры length :: Expression и element :: Expression (он создает массив заданной длины со всеми элементами, инициализированными константой). Простым примером является (newArray 3 "foo"), который дает ["foo", "foo", "foo"], но мы также можем написать (newArray (+ 1 2) (concat "fo" "oo")), потому что мы можем иметь произвольные выражения в NewArrayC. Но когда мы на самом деле назвать

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

, который принимает количество элементов для распределения и значение для каждого слота, и возвращает начальный адрес, мы должны распаковать эти значения. В логике ниже вы можете увидеть, что я дублирую кучу логики, которая должна быть встроена в монаду Either. Все case s должны просто связываться.

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

Это то, для чего предназначены трансформаторы монады. Существует трансформатор StateT, чтобы добавить состояние в стек, и трансформатор EitherT, чтобы добавить Either-подобный сбой в стек; однако я предпочитаю ExceptT (что добавляет Except-подобный сбой), поэтому я дам свое обсуждение в терминах этого. Поскольку вы хотите, чтобы бит состояния оставался самым внешним, вы должны использовать ExceptT e (State s) в качестве вашей монады.

type DSL = ExceptT String (State Store) 

Обратите внимание, что с состоянием операция может быть написана get и put, и они являются полиморфными над всеми экземплярами MonadState; так что, в частности, они будут хорошо работать в нашей монаде DSL. Аналогичным образом, канонический способ повышения ошибки - throwError, который является полиморфным во всех случаях MonadError String; и, в частности, будет работать в нашей монаде DSL.

Так что теперь мы будем писать

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) 

Вы могли бы также рассмотреть вопрос о предоставлении eval более полиморфный тип; он может вернуть (MonadError String m, MonadState Store m) => m Value вместо DSL Value. В самом деле, для allocateMany, это важно, что вы даете ему полиморфный тип:

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

Там две части, представляющие интерес об этом типе: во-первых, потому что это полиморфный по всем MonadState Store m случаях, вы можете быть столь же уверены, что он имеет только побочные эффекты, как если бы у него был тип Int -> Value -> State Store Address, который вы предложили. Однако также, поскольку он является полиморфным, он может быть специализирован для возврата DSL Address, поэтому его можно использовать (например) eval. Ваш пример eval код становится следующим образом:

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" 

Я думаю, что это вполне читаемым, на самом деле; там нет ничего лишнего.