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

Question

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

Answer 2

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

Документ называется «Why functional programming matters», я предлагаю вам прочитать его. Это хорошо читать.

Answer 3

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

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

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

Answer 4

Вы посмотрели Attribute grammars (AG)? (Дополнительная информация о wikipedia и article в Monad Reader)?

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

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

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

В Утрехтском университете мы используем Attribute Grammar System (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 5

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

Вот пример из компилятора Glasgow Haskell (который я сделал не write; я просто работаю с несколькими краями), где мы строим графики потока управления. Вот основные способы сделать графики:

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 6

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

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

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

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

Answer 7

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

Answer 8

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

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

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