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

Question

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

• стиль
• спектакль
• абстракция

Монадический разбор?

Answer 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 набор каждой альтернативы. Мы также можем статически определить, будет ли это двусмысленным, проверив, first наборы двух альтернатив перекрываются.

Другим примером является то, что его можно использовать для восстановления после ошибок, как показано в статье " Детерминированные, исправляющие ошибки комбинаторные парсеры", выполненные С. Доайце Свирстра и Люком Дюпоншилом.

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

Ua-анализ Doaitse Swierstra более эффективен, если используется только для его применения.

Answer 5

Монады - строго более содержательная абстракция, чем Аппликативы. Вы могли бы написать

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

Но нет возможности написать

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

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

Монадический разбор?

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