Использование государственной монады Haskell пахнет кодом?

Question

Боже, я ненавижу термин «кодовый запах», но не могу придумать ничего более точного.

Я разрабатываю язык и компилятор высокого уровня для Пробелы в свободное время, чтобы узнать о построении компилятора, проектировании языка и функциональном программировании (компилятор пишется на Haskell).

На этапе генерации кода компилятора я должен поддерживать «состояние» данных, когда я пересекаю синтаксическое дерево. Например, при компиляции операторов управления потоком мне нужно сгенерировать уникальные имена для меток, к которым нужно перейти (метки, сгенерированные из счетчика, который передан, обновлен и возвращен, и старое значение счетчика никогда не должно использоваться снова). Другой пример - когда я сталкиваюсь со строковыми литералами в строке синтаксического дерева, их необходимо постоянно преобразовывать в переменные кучи (в пробелах строки лучше всего хранить в куче). В настоящее время я обертываю весь модуль генерации кода в монаду состояния, чтобы справиться с этим.

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

Я хочу научиться думать в Haskell (точнее, в функциональной парадигме), а не в C с синтаксисом Haskell. Должен ли я действительно попытаться исключить / свести к минимуму использование государственной монады, или это законный функциональный «шаблон проектирования»?

Answer 1

Я написал несколько компиляторов на 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

С государственной монадой, скрытой за слоем абстракции, это совсем не воняет!

Answer 2

Я бы сказал, что состояние в общем-то не является запахом кода, если оно остается маленьким и хорошо контролируемым.

Это означает, что использование монад, таких как State, ST или пользовательские, или просто наличие структуры данных, содержащей данные о состоянии, которые вы передаете в несколько мест, не является плохой вещью. (На самом деле, монады - просто помощь в выполнении именно этого!) Однако иметь состояние, которое происходит повсюду (да, это означает, что вы, IO монада!) - это неприятный запах.

Довольно наглядный пример этого был, когда моя команда работала над нашей заявкой на ICFP Programming Contest 2009 (код доступен по адресу git: //git.cynic.net/haskell/icfp- конкурс-2009). Мы закончили с несколькими различными модульными частями к этому:

• VM: виртуальная машина, на которой запущена программа моделирования
• Контроллеры: несколько различных наборов подпрограмм, которые читают выходные данные симулятора и генерируют новые управляющие входы
• Решение: создание файла решения на основе выходных данных контроллеров
• Визуализаторы: несколько различных наборов подпрограмм, которые читают как входные, так и выходные порты и генерируют какую-то визуализацию или журнал того, что происходило в ходе симуляции.

Каждый из них имеет свое собственное состояние, и все они взаимодействуют по-разному через входные и выходные значения виртуальной машины. У нас было несколько разных контроллеров и визуализаторов, каждый из которых имел свой собственный тип состояния.

Ключевым моментом здесь было то, что внутренности любого конкретного состояния были ограничены их собственными конкретными модулями, и каждый модуль ничего не знал даже о существовании состояния для других модулей. Любой конкретный набор кода и данных с состоянием обычно составлял всего несколько десятков строк с несколькими элементами данных в состоянии.

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

Когда состояние используется таким ограниченным образом, а система типов не позволяет вам непреднамеренно изменить его, с ним довольно легко справиться. Это одна из красот Хаскелла, которая позволяет вам делать это.

Один ответ говорит: «Не используйте монады». С моей точки зрения, это как раз наоборот. Монады - это структура управления, которая, помимо прочего, может помочь вам минимизировать объем кода, который касается состояния. Если вы посмотрите на монадические парсеры в качестве примера, то состояние синтаксического анализа (т. Е. Анализируемый текст, как далеко он дошел до него, все накопленные предупреждения и т. Д.) Должно проходить через каждый комбинатор, используемый в парсере. , Тем не менее, будет лишь несколько комбинаторов, которые фактически манипулируют государством напрямую; все остальное использует одну из этих нескольких функций. Это позволяет вам ясно видеть и в одном месте весь небольшой объем кода, который может изменить состояние, и более легко рассуждать о том, как его можно изменить, снова облегчая работу с ним.

Answer 3

Вы смотрели на Грамматику атрибутов (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

Answer 4

Возможно, вы захотите аппликативный функтор вместо монада:

http://www.haskell.org/haskellwiki/Applicative_functor

Я думаю, что оригинальная статья объясняет это лучше, чем вики:

http://www.soi.city.ac.uk/~ross/papers/Applicative.html

Answer 5

Я не думаю, что использование State Monad является запахом кода, когда он используется для моделирования состояния.

Если вам нужно продвинуть состояние через ваши функции, Вы можете сделать это явно, принимая состояние в качестве аргумента и возвращая его в каждой функции. Государственная Монада предлагает хорошую абстракцию: она передает состояние для вас и предоставляет множество полезных функций для объединения функций, требующих состояния. В этом случае использование государственной монады (или аппликативов) не является запахом кода.

Однако, если вы используете State Monad для эмуляции императивного стиля программирования хотя функционального решения будет достаточно, вы просто усложняете ситуацию.

Answer 6

В общем, вы должны стараться избегать состояния везде, где это возможно, но это не всегда практично. Applicative делает эффективный код более привлекательным и функциональным, особенно код обхода дерева может выиграть от этого стиля. Для проблемы генерации имен теперь доступен довольно приятный пакет: value-supply .

Answer 7

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

Конечно, монада состояния Haskell существует именно по этой причине - как и в случае с вводом / выводом, она позволяет вам выполнять небезопасные и не функциональные действия в ограниченном контексте.

Так что, да, это, вероятно, запах кода.

Answer 8

Ну, не используйте монады. Сила функционального программирования заключается в чистоте функций и их повторном использовании. Есть эта статья, которую однажды написал мой профессор, и он один из тех, кто помогал строить Haskell.

Статья называется " Почему функциональное программирование имеет значение ", я предлагаю вам прочитать ее. Это хорошее чтение.