haskell - programacion - ¿Cuáles son los beneficios del análisis aplicativo sobre el análisis sintáctico monádico?

monads

Question

Parece haber consenso en que debería usar Parsec como un aplicativo en lugar de una mónada. ¿Cuáles son los beneficios del análisis aplicativo sobre el análisis sintáctico monádico?

• estilo
• actuación
• abstracción

¿El análisis monádico está fuera?

Answer 1

Con Parsec, el beneficio de usar Applicative es solo estilo. Monad tiene la ventaja de que es más potente: puede implementar analizadores sensibles al contexto.

El análisis UU de Doaitse Swierstra es más eficiente si se usa solo de forma aplicativa.

Answer 2

La razón principal por la que puedo ver para preferir los analizadores aplicativos sobre los analizadores monádicos es la misma que la razón principal para preferir el código aplicativo sobre el código monádico en cualquier contexto: al ser menos potentes, los aplicativos son más simples de usar.

Esta es una instancia de un dictum de ingeniería más general: use la herramienta más simple que hace el trabajo. No use una carretilla elevadora cuando lo haga una carretilla. No use una sierra de mesa para cortar cupones. No escriba código en IO cuando podría ser puro. Mantenlo simple.

Pero a veces, necesitas el poder extra de Monad . Una señal segura de esto es cuando necesita cambiar el curso del cálculo en base a lo que se ha calculado hasta ahora. En términos de análisis, esto significa determinar cómo analizar lo que sigue basado en lo que se ha analizado hasta el momento; en otras palabras, puede construir gramáticas sensibles al contexto de esta manera.

Answer 3

Las mónadas son estrictamente una abstracción más funcional que Applicatives. Podrías escribir

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

Pero no hay forma de escribir

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

Entonces sí, es esencialmente una cuestión de estilo . Me imagino que si usas return y ap , entonces no debería haber pérdida de rendimiento con respecto a usar pure y <*> . Debido a que Applicative es una interfaz estrictamente más pequeña que Monad, esto significa que <*> veces puede ser más altamente optimizado que ap . (Pero con las inteligentes reglas de reescritura de GHC, a menudo se pueden lograr las mismas optimizaciones independientemente).

¿El análisis monádico está fuera?

Como las mónadas son un subconjunto de Aplicativos, concluiría que el análisis aplicativo es un subconjunto del análisis sintáctico monádico.

Answer 4

Si un analizador es puramente aplicativo, es posible analizar su estructura y "optimizarla" antes de ejecutarla. Si un analizador es monádico, es básicamente un programa completo de Turing, y realizar casi cualquier análisis interesante de él es equivalente a resolver el problema de detención (es decir, imposible).

Ah, y sí, también hay una diferencia estilística ...

Answer 5

La diferencia principal entre el análisis sintáctico monádico y el aplicativo es la forma en que se maneja la composición secuencial. En el caso de un analizador sintáctico aplicativo, usamos (<*>) , mientras que con una mónada usamos (>>=) .

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

El enfoque monádico es más flexible, ya que permite que la gramática de la segunda parte dependa del resultado de la primera, pero rara vez necesitamos esta flexibilidad adicional en la práctica.

Podrías pensar que tener algo de flexibilidad extra no puede doler, pero en realidad sí puede. Nos impide realizar un análisis estático útil en un analizador sin ejecutarlo. Por ejemplo, digamos que queremos saber si un analizador puede coincidir con la cadena vacía o no, y cuáles pueden ser los primeros caracteres posibles en una coincidencia. Queremos funciones

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

Con un analizador aplicativo, podemos responder fácilmente a esta pregunta. (Estoy engañando un poco aquí. Imagine que tenemos un constructor de datos correspondiente a (<*>) y (>>=) en nuestros "lenguajes" de analizador candidato.

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

Sin embargo, con un analizador monádico no sabemos cuál es la gramática de la segunda parte sin conocer la entrada.

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

Al permitir más, podemos razonar menos. Esto es similar a la elección entre sistemas de tipo dinámico y estático.

Pero, ¿qué sentido tiene esto? ¿Para qué podríamos usar este conocimiento estático adicional? Bueno, podemos, por ejemplo, usarlo para evitar el retroceso en el análisis LL (1) al comparar el siguiente carácter con el first conjunto de cada alternativa. También podemos determinar estáticamente si esto sería ambiguo al verificar si los first conjuntos de dos alternativas se superponen.

Otro ejemplo es que puede utilizarse para la recuperación de errores, como se muestra en el documento Deterministic, Corrección de errores Combinator Parsers por S. Doaitse Swierstra y Luc Duponcheel.

Por lo general, sin embargo, la elección entre el análisis sintáctico y monádico ya ha sido realizada por los autores de la biblioteca de análisis que está utilizando. Cuando una biblioteca como Parsec expone ambas interfaces, la elección de cuál usar es puramente estilística. En algunos casos, el código aplicativo es más fácil de leer que el código monádico y, a veces, es al revés.