Каковы преимущества аппликативного разбора над монадическим разбором?

Ответ 1

Основное различие между монадическим и аппликативным анализом заключается в том, как обрабатывается последовательная композиция. В случае аппликативного анализатора мы используем (<*>), тогда как с монадой мы используем (>>=).

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

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

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

empty :: Parser a -> Bool
first :: Parser a -> Set Char

С помощью аппликативного анализатора мы можем легко ответить на этот вопрос. (Я немного обманываю здесь. Представьте, что у нас есть конструкторы данных, соответствующие (<*>) и (>>=) в наших языках-парсерах кандидата).

empty (f <*> x) = empty f && empty x
first (f <*> x) | empty f   = first f `union` first x
                | otherwise = first f

Однако с монадическим синтаксическим анализатором мы не знаем, что грамматика второй части не знает ввода.

empty (x >>= f) = empty x && empty (f ???)
first (x >>= f) | empty x   = first x `union` first (f ???)
                | otherwise = first x

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

Но в чем смысл этого? Для чего мы можем использовать это дополнительное статическое знание? Ну, мы можем, например, использовать его, чтобы избежать повторения в анализе LL (1), сравнивая следующий символ с набором first каждой альтернативы. Мы также можем определить статически, было ли это неоднозначно, проверяя, перекрываются ли наборы <2 > 2 двух альтернатив.

Другим примером является то, что его можно использовать для восстановления ошибок, как показано в документе Детерминированные, исправляющие ошибки комбайнеры Parsers от S. Doaitse Swierstra и Luc Duponcheel.

Обычно, однако, выбор между аппликативным и монадическим разбором уже сделан авторами используемой вами библиотеки синтаксического анализа. Когда библиотека, такая как Parsec, предоставляет оба интерфейса, выбор которых для использования является чисто стилистическим. В некоторых случаях аппликативный код легче читать, чем монадический код, а иногда и наоборот.

Ответ 2

Если синтаксический анализатор является чисто аппликативным, его можно проанализировать и "оптимизировать" перед его запуском. Если синтаксический анализатор является монадическим, он в основном представляет собой программу Turing-complete и выполняет практически любой интересный анализ, эквивалентный решению проблемы остановки (т.е. Невозможно).

О, да, там тоже стилистическая разница...

Ответ 3

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

Это пример более общего инженерного изречения: используйте простейший инструмент, который выполняет свою работу. Не используйте вилочный погрузчик, когда будет делать тележка. Не используйте настольную пилу для вырезания купонов. Не пишите код в IO, когда он может быть чистым. Будь проще.

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

Ответ 4

С Parsec преимущество использования аппликативного - это просто стиль. Преимущество Monad состоит в том, что оно более мощное - вы можете реализовать анализаторы, чувствительные к контексту.

Doaitse Swierstra UU parsing более эффективен, если используется только применительно.

Ответ 5

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

instance (Monad m) => Applicative m where
  pure  = return
  (<*>) = ap

Но писать

instance (Applicative a) => Monad a where
  return = pure
  (>>=) = ???

Итак, это, по сути, вопрос стиля . Я полагаю, что если вы используете return и ap, то при использовании pure и <*>. должна быть потеря производительности. Поскольку Applicative является строго меньшим интерфейсом, чем Monad, это означает, что <*> иногда может быть более оптимизирован, чем ap. (Но с умными правилами перезаписи GHC, часто можно добиться одинаковых оптимизаций.)

Является ли монадическое разбор?

Так как Monads являются подмножеством Applicatives, я бы сделал вывод, что аппликативный синтаксический анализ является подмножеством монадического разбора.