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

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 из двух альтернатив.

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

Обычно, однако, выбор между аппликативным и монадическим синтаксическим анализом уже сделан авторами используемой библиотеки синтаксического анализа.,Когда библиотека, такая как 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 часто можно добиться одинаковых оптимизаций независимо от этого.)

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

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