Использование монады состояния Haskell — запах кода?

Question

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

Answer 2

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

Вы посмотрели Грамматики атрибутов (АГ)?(Подробнее о Википедия и статья в читателе монад)?

С помощью AG вы можете добавить атрибуты в синтаксическое дерево.Эти атрибуты разделены на синтезированный и унаследованный атрибуты.

Синтезированные атрибуты — это вещи, которые вы генерируете (или синтезируете) из своего синтаксического дерева. Это может быть сгенерированный код, все комментарии или что-то еще, что вас интересует.

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

В Утрехтском университете мы используем Грамматическая система атрибутов (УУАГК) для написания компиляторов.Это препроцессор, который генерирует код 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 предлагает хорошую абстракцию:Он проходит для вас состояние и обеспечивает много полезных функций для сочетания функций, которые требуют состояния.В этом случае использование State Monad (или Applicatives) не является запахом кода.

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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