Как понять evalState в этом фрагменте кода Monad Haskell штата? - PullRequest
Новая
       68

Как понять evalState в этом фрагменте кода Monad Haskell штата?

0 голосов
/ 11 апреля 2019

Я смотрю на этот фрагмент кода компилятора и не понимаю, что делает evalState, будучи новичком в State Monad.

compileToAst :: FilePath -> String -> Either Errors (Contract (Check Type, Env, SourcePos))
compileToAst source code = case parse parser source code of
    Right ast -> let ast'            = evalState ast [globals]
                     errors          = lefts $ map ann $ toList ast'
                     ann (a, _, pos) = a `extend` sourcePosPretty pos
                 in if null errors then Right ast' else Left errors
    Left err  -> Left [(SyntaxError $ parseErrorTextPretty err, sourcePosPretty . NE.head $ errorPos err)]

Если предположить, что вычисление с состоянием выполняется в форме s -> (a, s), ast - это монада, [globals] - это s, а evalState ast [globals] возвращает тип a.Где я могу найти определение вычислений с состоянием, преобразующее s в новое s и дающее результат a?

1 Ответ

1 голос
/ 13 апреля 2019

Функция evalState имеет тип: 

evalState :: State s a -> s -> a

Тип первого аргумента, а именно State s a, фактически изоморфен типу функции s -> (a, s). Формально это означает, что между ними существуют две функции: 

runState :: State s a -> (s -> (a, s))
state :: (s -> (a, s)) -> State s a

и если вы примените одну из этих функций, а затем другую, вы вернетесь к тому, с чего начали (т. Е. Они являются обратными, а их состав - тождественной функцией).

Менее формально это означает, что везде, где вы видите State s a, вы можете притворяться, что это тип s -> (a, s) и наоборот, поскольку вы можете конвертировать туда и обратно по желанию, используя эти служебные функции runState и state.

Следовательно, все, что evalState делает, это берет первый аргумент, изоморфный вычислению с состоянием s -> (a, s), и запускает его, используя начальное состояние, заданное его вторым аргументом. Затем он выбрасывает конечное состояние s и выдает окончательный результат вычисления.

Так как это первый аргумент evalState, это вычисление с учетом состояния, на самом деле ast возвращается, когда parse parser source code успешно, это преобразование с состоянием s -> (a, s), которое вы ищете.

То есть значение ast имеет тип: 

ast :: State Env (Contract (Check Type, Env, SourcePos))

который изоморфен: 

ast :: Env -> (Contract (Check Type, Env, SourcePos), Env)

так что это преобразование с состоянием, которое работает в состоянии, состоящем из окружения (список таблиц символов) и дает контракт. Все, что evalState делает, это передает это преобразование с сохранением состояния в начальное состояние / среду, состоящую из синглтона, представляющего глобальную таблицу символов, и затем выдает свой окончательный результат контракта (отбрасывая окончательный список таблиц символов, так как он больше не важен после заключения контракта). генерируется). * +1041 *

Таким образом, способ, которым разработан этот компилятор, он компилирует код в «абстрактное синтаксическое дерево», которое вместо того, чтобы быть древовидной структурой данных, на самом деле является функцией, дающей преобразование с сохранением состояния по состоянию среды, которое создает контракт ; evalState просто "запускает" преобразование для генерации контракта.

...