Использование государственной монады Haskell пахнет кодом?
Боже, я ненавижу термин "запах кода", но не могу придумать ничего более точного.
В свободное время я разрабатываю высокоуровневый язык и компилятор для Whitespace, чтобы узнать о построении компилятора, проектировании языка и функциональном программировании (компилятор пишется на Haskell).
На этапе генерации кода компилятора я должен поддерживать "состояние" данных, когда я пересекаю синтаксическое дерево. Например, при компиляции операторов управления потоком мне нужно сгенерировать уникальные имена для меток, к которым можно перейти (метки, сгенерированные из счетчика, который передан, обновлен и возвращен, и старое значение счетчика никогда не должно использоваться снова). Другой пример - когда я сталкиваюсь со строковыми литералами в строке синтаксического дерева, их необходимо постоянно преобразовывать в переменные кучи (в пробелах строки лучше всего хранить в куче). Я сейчас обертываю весь модуль генерации кода в монаду состояния, чтобы справиться с этим.
Мне сказали, что написание компилятора является проблемой, хорошо подходящей для функциональной парадигмы, но я обнаружил, что я проектирую это во многом так же, как я бы спроектировал это на C (вы действительно можете написать C на любом языке - даже Haskell ж / государственные монады).
Я хочу научиться думать в Хаскеле (точнее, в функциональной парадигме), а не в Си с синтаксисом Хаскелла. Должен ли я действительно попытаться исключить / свести к минимуму использование государственной монады, или это законный функциональный "шаблон проектирования"?
8 ответов
Я бы сказал, что состояние в общем-то не является запахом кода, если оно остается маленьким и хорошо контролируемым.
Это означает, что использование монад, таких как State, ST или пользовательские, или просто наличие структуры данных, содержащей данные о состоянии, которые вы передаете в несколько мест, не является плохой вещью. (На самом деле, монады - это просто помощь в этом!) Однако иметь состояние, которое происходит повсюду (да, это означает, что вы, IO-монада!) - это неприятный запах.
Довольно наглядным примером этого было то, что моя команда работала над нашей заявкой на участие в Конкурсе программирования ICFP 2009 (код доступен по адресу git://git.cynic.net/haskell/icfp-contest-2009). Мы закончили с несколькими различными модульными частями к этому:
- VM: виртуальная машина, на которой запущена программа симуляции
- Контроллеры: несколько различных наборов подпрограмм, которые читают выходные данные симулятора и генерируют новые входы управления
- Решение: создание файла решения на основе выходных данных контроллеров
- Визуализаторы: несколько различных наборов подпрограмм, которые читают как входной, так и выходной порты и генерируют некоторую визуализацию или журнал того, что происходило в ходе симуляции.
Каждый из них имеет свое собственное состояние, и все они взаимодействуют по-разному через входные и выходные значения виртуальной машины. У нас было несколько разных контроллеров и визуализаторов, каждый из которых имел свое собственное состояние.
Ключевым моментом здесь было то, что внутренние компоненты любого конкретного состояния были ограничены их собственными конкретными модулями, и каждый модуль ничего не знал даже о существовании состояния для других модулей. Любой конкретный набор кода и данных с состоянием обычно составлял всего несколько десятков строк с несколькими элементами данных в состоянии.
Все это было склеено в одну маленькую функцию из примерно дюжины строк, которые не имели доступа к внутренним частям какого-либо из состояний, и которые просто называли правильные вещи в правильном порядке, когда они проходили через симуляцию, и проходили очень ограниченно. количество внешней информации для каждого модуля (конечно же, вместе с предыдущим состоянием модуля).
Когда состояние используется таким ограниченным образом, а система типов не позволяет вам непреднамеренно изменить его, с этим довольно легко справиться. Это одна из красот Хаскелла, которая позволяет вам делать это.
Один ответ говорит: "Не используйте монады". С моей точки зрения, это как раз наоборот. Монады - это структура управления, которая, помимо прочего, может помочь вам минимизировать объем кода, который касается состояния. Если вы посмотрите на монадические парсеры в качестве примера, то состояние синтаксического анализа (т. Е. Анализируемый текст, как далеко он дошел до него, все накопленные предупреждения и т. Д.) Должно проходить через каждый комбинатор, используемый в парсере., Тем не менее, будет лишь несколько комбинаторов, которые фактически манипулируют государством напрямую; все остальное использует одну из этих нескольких функций. Это позволяет вам ясно видеть и в одном месте весь небольшой объем кода, который может изменить состояние, и более легко рассуждать о том, как его можно изменить, снова облегчая работу с ним.
Я написал несколько компиляторов на Haskell, и монада состояния - разумное решение многих проблем компилятора. Но вы хотите сохранить его абстрактным - не показывайте, что вы используете монаду.
Вот пример из компилятора Glasgow Haskell (который я не писал; я просто работаю над несколькими ребрами), где мы строим графы потоков управления. Вот основные способы построения графиков:
empyGraph :: Graph
mkLabel :: Label -> Graph
mkAssignment :: Assignment -> Graph -- modify a register or memory
mkTransfer :: ControlTransfer -> Graph -- any control transfer
(<*>) :: Graph -> Graph -> Graph
Но, как вы обнаружили, поддержка уникальных меток в лучшем случае утомительна, поэтому мы также предоставляем следующие функции:
withFreshLabel :: (Label -> Graph) -> Graph
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition
-> Graph -- code in the 'then' branch
-> Graph -- code in the 'else' branch
-> Graph -- resulting if-then-else construct
Целый Graph вещь - это абстрактный тип, и переводчик просто весело строит графы чисто функциональным образом, не зная, что происходит что-то монадическое. Затем, когда граф окончательно построен, чтобы превратить его в алгебраический тип данных, из которого мы можем сгенерировать код, мы даем ему набор уникальных меток, запускаем монаду состояний и извлекаем структуру данных.
Государственная монада скрыта под; хотя это не подвергается воздействию клиента, определение Graph это что-то вроде этого:
type Graph = RealGraph -> [Label] -> (RealGraph, [Label])
или немного точнее
type Graph = RealGraph -> State [Label] RealGraph
-- a Graph is a monadic function from a successor RealGraph to a new RealGraph
С государственной монадой, скрытой за слоем абстракции, это совсем не воняет!
Вы смотрели на грамматику атрибутов (AG)? (Больше информации о википедии и статье в Monad Reader)?
С AG вы можете добавлять атрибуты в синтаксическое дерево. Эти атрибуты разделены на синтезированные и унаследованные атрибуты.
Синтезированные атрибуты - это вещи, которые вы генерируете (или синтезируете) из своего синтаксического дерева, это может быть сгенерированный код, или все комментарии, или все, что вас интересует.
Унаследованные атрибуты вводятся в ваше синтаксическое дерево, это может быть среда или список меток, используемых при генерации кода.
В Утрехтском университете мы используем систему грамматики атрибутов ( UUAGC) для написания компиляторов. Это препроцессор, который генерирует код haskell (.hs файлы) из предоставленного .ag файлы.
Хотя, если вы все еще изучаете Haskell, возможно, сейчас не время начинать изучать еще один уровень абстракции.
В этом случае вы можете вручную написать код, который генерируют для вас атрибуты грамматики, например:
data AbstractSyntax = Literal Int | Block AbstractSyntax
| Comment String AbstractSyntax
compile :: AbstractSyntax -> [Label] -> (Code, Comments)
compile (Literal x) _ = (generateCode x, [])
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls
in (labelCode l code', comments)
compile (Comment s ast) ls = let (code, comments') = compile ast ls
in (code, s : comments')
generateCode :: Int -> Code
labelCode :: Label -> Code -> Code
Возможно, вы захотите аппликативный функтор вместо монады:
http://www.haskell.org/haskellwiki/Applicative_functor
Я думаю, что оригинальная статья объясняет это лучше, чем вики:
Я не думаю, что использование State Monad - это запах кода, когда он используется для моделирования состояния.
Если вам нужно обработать состояние через ваши функции, вы можете сделать это явно, взяв состояние в качестве аргумента и возвращая его в каждой функции. Монада состояний предлагает хорошую абстракцию: она передает вам состояние и предоставляет множество полезных функций для объединения функций, требующих состояния. В этом случае использование государственной монады (или аппликативов) не является кодовым запахом.
Однако если вы используете State Monad для эмуляции императивного стиля программирования, а функционального решения будет достаточно, вы просто усложняете ситуацию.
В общем, вы должны стараться избегать состояния везде, где это возможно, но это не всегда практично. Applicative делает эффективный код более привлекательным и функциональным, особенно код обхода дерева может выиграть от этого стиля. Для проблемы генерации имен теперь есть довольно хороший пакет: value-supply.
Ну, не используйте монады. Сила функционального программирования заключается в чистоте функций и их повторном использовании. Есть эта статья, которую однажды написал мой профессор, и он один из тех, кто помог построить Хаскелл.
Документ называется " Почему функциональное программирование имеет значение", я предлагаю вам прочитать его. Это хорошее чтение.
Давайте будем осторожны с терминологией здесь. Государство само по себе не плохо; функциональные языки имеют гос. Что такое "запах кода", это когда вы хотите присвоить значения переменных и изменить их.
Конечно, монада состояния Haskell существует именно по этой причине - как и в случае с вводом / выводом, она позволяет вам выполнять небезопасные и нефункциональные действия в ограниченном контексте.
Так что, да, это, вероятно, запах кода.