Quels sont les avantages de l'analyse applicative par rapport à l'analyse monadique ?

Question

Il semble y avoir un consensus sur le fait que vous devriez utiliser Parsec comme un applicatif plutôt que comme une monade. Quels sont les avantages de l'analyse applicative par rapport à l'analyse monadique ?

• style
• performance
• abstraction

L'analyse syntaxique monadique est-elle exclue ?

Answer 1

La principale différence entre l'analyse syntaxique monadique et applicative réside dans la manière dont la composition séquentielle est traitée. Dans le cas d'un analyseur applicatif, on utilise (<*>) alors qu'avec une monade, on utilise (>>=) .

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

L'approche monadique est plus flexible, car elle permet à la grammaire de la deuxième partie de dépendre du résultat de la première, mais nous avons rarement besoin de cette flexibilité supplémentaire en pratique.

Vous pourriez penser qu'avoir une certaine flexibilité supplémentaire ne peut pas nuire, mais en réalité, c'est le cas. Cela nous empêche de faire une analyse statique utile sur un analyseur sans l'exécuter. Par exemple, disons que nous voulons savoir si un analyseur peut faire correspondre la chaîne vide ou non, et quels sont les premiers caractères possibles dans une correspondance. Nous voulons les fonctions

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

Avec un analyseur applicatif, nous pouvons facilement répondre à cette question. (Je triche un peu ici. Imaginons que nous ayons un constructeur de données correspondant à (<*>) y (>>=) dans les "langues" de notre analyseur candidat).

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

Cependant, avec un analyseur monadique, nous ne savons pas quelle est la grammaire de la deuxième partie sans connaître l'entrée.

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

En autorisant plus, nous sommes en mesure de raisonner moins. Ceci est similaire au choix entre les systèmes de types dynamiques et statiques.

Mais quel est le but de tout cela ? A quoi pourrait servir cette connaissance statique supplémentaire ? Eh bien, nous pouvons par exemple l'utiliser pour éviter le retour en arrière dans l'analyse syntaxique LL(1) en comparant le caractère suivant à l'indice first de chaque alternative. Nous pouvons également déterminer de manière statique si cela serait ambigu en vérifiant si la fonction first les ensembles de deux alternatives se chevauchent.

Un autre exemple est qu'il peut être utilisé pour la récupération d'erreurs, comme le montre l'article Analyseurs combinatoires déterministes et correcteurs d'erreurs par S. Doaitse Swierstra et Luc Duponcheel.

En général, cependant, le choix entre l'analyse applicative et monadique a déjà été fait par les auteurs de la bibliothèque d'analyse que vous utilisez. Lorsqu'une bibliothèque telle que Parsec expose les deux interfaces, le choix de celle à utiliser est purement stylistique. Dans certains cas, le code applicatif est plus facile à lire que le code monadique et parfois c'est l'inverse.

Answer 2

Si un analyseur est purement applicatif, il est possible d'analyser sa structure et de l'"optimiser" avant de l'exécuter. Si un analyseur est monadique, il s'agit fondamentalement d'un programme Turing-complet, et effectuer presque toute analyse intéressante de celui-ci est équivalent à résoudre le problème de l'arrêt (c'est-à-dire impossible).

Oh, et oui, il y a aussi une différence stylistique...

Answer 3

La principale raison que je vois de préférer les analyseurs applicatifs aux analyseurs monadiques est la même que la principale raison de préférer le code applicatif au code monadique dans n'importe quel contexte : étant moins puissants, les applicatifs sont plus simples à utiliser.

Il s'agit d'un exemple d'un dicton d'ingénierie plus général : utiliser l'outil le plus simple qui permet de faire le travail. N'utilisez pas un chariot élévateur lorsqu'un dolly fait l'affaire. N'utilisez pas une scie à table pour découper des coupons. N'écrivez pas de code dans IO alors qu'elle pourrait être pure. Restez simple.

Mais parfois, vous besoin de la puissance supplémentaire de Monad . Un signe évident de cette situation est la nécessité de modifier le cours du calcul en fonction de ce qui a été calculé jusqu'à présent. En termes d'analyse syntaxique, cela signifie déterminer comment analyser ce qui vient ensuite en fonction de ce qui a été analysé jusqu'à présent ; en d'autres termes, vous pouvez construire des grammaires sensibles au contexte de cette façon.

Answer 4

Avec Parsec, l'avantage d'utiliser Applicative n'est que du style. Monad a l'avantage d'être plus puissant - vous pouvez implémenter des analyseurs sensibles au contexte.

L'analyse syntaxique UU de Doaitse Swierstra est plus efficace si elle est utilisée uniquement de manière applicative.

Answer 5

Les monades sont strictement un abstraction plus riche en fonctionnalités que les applicatifs. Vous pourriez écrire

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

Mais il n'y a aucun moyen d'écrire

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

Donc oui, c'est essentiellement une question de style . J'imagine que si vous utilisez return y ap alors il devrait y avoir aucune perte de performance sur l'utilisation pure y <*> . Comme Applicative est une interface strictement plus petite que Monad, cela signifie que <*> peut parfois être plus optimisé que ap . (Mais avec des règles de réécriture GHC intelligentes, on peut souvent obtenir les mêmes optimisations indépendamment).

L'analyse syntaxique monadique est-elle exclue ?

Puisque les monades sont un sous-ensemble des applicatifs, j'en conclurais que l'analyse applicative est un sous-ensemble de l'analyse monadique.