El uso de la mónada del estado de Haskell un olor a código

Question

Dios, odio el término "olor a código", pero no puedo pensar en nada más preciso.

Estoy diseñando un lenguaje de alto nivel & amp; compilador a Whitespace en mi tiempo libre para aprender sobre la construcción del compilador, el diseño del lenguaje y la programación funcional ( el compilador se está escribiendo en Haskell).

Durante la fase de generación de código del compilador, tengo que mantener el estado de los datos disponibles al atravesar el árbol de sintaxis. Por ejemplo, al compilar sentencias de control de flujo, necesito generar nombres únicos para que las etiquetas salten (etiquetas generadas desde un contador que se pasa, se actualiza y se devuelve, y el valor antiguo del contador nunca se debe usar nuevamente) . Otro ejemplo es cuando me encuentro con los literales de cadena en línea en el árbol de sintaxis, deben ser convertidos permanentemente en variables de pila (en Whitespace, las cadenas se almacenan mejor en la pila). Actualmente estoy envolviendo todo el módulo de generación de código en la mónada estatal para manejar esto.

Me han dicho que escribir un compilador es un problema que se adapta bien al paradigma funcional, pero me parece que lo estoy diseñando de la misma manera que lo haría en C (realmente puedes escribir C en cualquier lenguaje - incluso Haskell w / estado mónadas).

Quiero aprender a pensar en Haskell (más bien, en el paradigma funcional), no en C con la sintaxis de Haskell. ¿Debería realmente intentar eliminar / minimizar el uso de la mónada estatal o es un patrón de diseño "patrón" legítimo y funcional "?

Answer 1

Yo diría que el estado en general no es un olor a código, siempre que se mantenga pequeño y bien controlado.

Esto significa que usar mónadas como State, ST o personalizadas, o simplemente tener una estructura de datos que contenga datos de estado que se pasan a algunos lugares, no es algo malo. (¡En realidad, las mónadas son solo ayuda para hacer exactamente esto!) Sin embargo, tener un estado que se extiende por todo el lugar (¡sí, esto significa que tú, IO mónada!) Es un mal olor.

Un ejemplo bastante claro de esto fue cuando mi equipo estaba trabajando en nuestra entrada para el ICFP Programming Contest 2009 (el el código está disponible en git: //git.cynic.net/haskell/icfp-contest-2009). Terminamos con varias partes modulares diferentes para esto:

• VM: la máquina virtual que ejecutó el programa de simulación
• Controladores: varios conjuntos diferentes de rutinas que leen la salida del simulador y generan nuevas entradas de control
• Solución: generación del archivo de solución basado en la salida de los controladores
• Visualizadores: varios conjuntos diferentes de rutinas que leen los puertos de entrada y salida y generan algún tipo de visualización o registro de lo que estaba sucediendo a medida que avanzaba la simulación

Cada uno de estos tiene su propio estado, y todos interactúan de varias maneras a través de los valores de entrada y salida de la VM. Teníamos varios controladores y visualizadores diferentes, cada uno de los cuales tenía su propio tipo de estado.

El punto clave aquí fue que las partes internas de cualquier estado particular estaban limitadas a sus propios módulos particulares, y cada módulo no sabía nada sobre la existencia de estado para otros módulos. Cualquier conjunto particular de código y datos con estado generalmente tenía solo unas pocas docenas de líneas, con un puñado de elementos de datos en el estado.

Todo esto se pegó en una pequeña función de alrededor de una docena de líneas que no tenían acceso a las partes internas de ninguno de los estados, y que simplemente llamaron las cosas correctas en el orden correcto a medida que giraba a través de la simulación, y aprobaron una cantidad muy limitada de información externa a cada módulo (junto con el estado anterior del módulo, por supuesto).

Cuando el estado se usa de una forma tan limitada, y el sistema de tipos le impide modificarlo inadvertidamente, es bastante fácil de manejar. Es una de las bellezas de Haskell que te permite hacer esto.

Una respuesta dice: "No uses mónadas". Desde mi punto de vista, esto es exactamente al revés. Las mónadas son una estructura de control que, entre otras cosas, puede ayudarlo a minimizar la cantidad de código que toca el estado. Si observa los analizadores monádicos como ejemplo, el estado del análisis (es decir, el texto que se está analizando, hasta qué punto se ha introducido uno, las advertencias que se han acumulado, etc.) debe pasar por todos los combinadores utilizados en el analizador. . Sin embargo, solo habrá unos pocos combinadores que realmente manipulen el estado directamente; cualquier otra cosa usa una de estas pocas funciones. Esto le permite ver con claridad y en un solo lugar toda una pequeña cantidad de código que puede cambiar el estado, y razonar más fácilmente sobre cómo se puede cambiar, lo que hace que sea más fácil de tratar.

Answer 2

He escrito varios compiladores en Haskell, y una mónada de estado es una solución razonable para muchos problemas de compilación. Pero desea mantenerlo abstracto --- no haga obvio que está usando una mónada.

Aquí hay un ejemplo del compilador Haskell de Glasgow (que no escribí no ; solo trabajo alrededor de algunos bordes), donde creamos gráficos de flujo de control. Aquí están las formas básicas de hacer gráficos:

empyGraph    :: Graph
mkLabel      :: Label -> Graph
mkAssignment :: Assignment -> Graph  -- modify a register or memory
mkTransfer   :: ControlTransfer -> Graph   -- any control transfer
(<*>)        :: Graph -> Graph -> Graph

Pero como ha descubierto, mantener un suministro de etiquetas únicas es tedioso en el mejor de los casos, por lo que también ofrecemos estas funciones:

withFreshLabel :: (Label -> Graph) -> Graph
mkIfThenElse :: (Label -> Label -> Graph) -- branch condition
             -> Graph   -- code in the 'then' branch
             -> Graph   -- code in the 'else' branch 
             -> Graph   -- resulting if-then-else construct

Todo el elemento Graph es un tipo abstracto, y el traductor simplemente construye gráficos de manera puramente funcional, sin ser consciente de que algo monádico está sucediendo. Luego, cuando finalmente se construye el gráfico, para convertirlo en un tipo de datos algebraico desde el cual podemos generar código, le damos un suministro de etiquetas únicas, ejecutamos la mónada estatal y extraemos la estructura de datos.

La mónada estatal está oculta debajo; Aunque no está expuesto al cliente, la definición de Graph es algo como esto:

type Graph = RealGraph -> [Label] -> (RealGraph, [Label])

o un poco más preciso

type Graph = RealGraph -> State [Label] RealGraph
  -- a Graph is a monadic function from a successor RealGraph to a new RealGraph

¡Con la mónada estatal oculta detrás de una capa de abstracción, no tiene mal olor!

Answer 3

¿Has visto Atributo de las gramáticas (AG)? (Más información en wikipedia y artículo en el Monad Reader)?

Con AG puede agregar atributos a un árbol de sintaxis. Estos atributos se separan en los atributos sintetizados y heredados .

Los atributos sintetizados son cosas que genera (o sintetiza) a partir de su árbol de sintaxis, este podría ser el código generado, todos los comentarios, o cualquier otra cosa que le interese.

Los atributos heredados se ingresan en su árbol de sintaxis, esto podría ser el entorno o una lista de etiquetas para usar durante la generación de código.

En la Universidad de Utrecht usamos el Sistema de gramática de atributos ( UUAGC ) para escribir compiladores. Este es un preprocesador que genera código de haskell (archivos .hs ) a partir de los archivos proporcionados .ag .

---

Aunque, si aún estás aprendiendo Haskell, quizás este no sea el momento de comenzar a aprender otra capa de abstracción sobre eso.

En ese caso, podría escribir manualmente el tipo de código que los atributos que generan las gramáticas, por ejemplo:

data AbstractSyntax = Literal Int | Block AbstractSyntax
                    | Comment String AbstractSyntax

compile :: AbstractSyntax -> [Label] -> (Code, Comments)
compile (Literal x) _      = (generateCode x, [])
compile (Block ast) (l:ls) = let (code', comments) = compile ast ls
                             in (labelCode l code', comments)
compile (Comment s ast) ls = let (code, comments') = compile ast ls
                             in (code, s : comments')

generateCode :: Int -> Code
labelCode :: Label -> Code -> Code

Answer 4

Es posible que desee un funtor aplicativo en lugar de un mónada:

http://www.haskell.org/haskellwiki/Applicative_functor

Sin embargo, creo que el artículo original lo explica mejor que la wiki:

http://www.soi.city.ac. uk / ~ ross / papers / Applicative.html

Answer 5

No creo que usar la Mónada estatal sea un olor de código cuando se utiliza para modelar el estado.

Si necesita enlazar el estado a través de sus funciones, puede hacer esto explícitamente, tomando el estado como un argumento y devolviéndolo en cada función. La Mónada estatal ofrece una buena abstracción: pasa el estado por usted y proporciona muchas funciones útiles para combinar funciones que requieren estado. En este caso, el uso de la mónada estatal (o de los aplicativos) no es un olor de código.

Sin embargo, si utiliza la Mónada estatal para emular un estilo imperativo de programación Si bien una solución funcional sería suficiente, solo estás complicando las cosas.

Answer 6

En general, debes tratar de evitar el estado siempre que sea posible, pero eso no siempre es práctico. Applicative hace que el código efectivo se vea mejor y más funcional, especialmente el código de cruce de árboles puede beneficiarse de este estilo. Para el problema de la generación de nombres, ahora hay un paquete bastante agradable disponible: value-supply .

Answer 7

Bueno, no uses mónadas. El poder de la programación funcional es la pureza de la función y su reutilización. Hay un artículo que un profesor mío escribió una vez y es uno de los tipos que ayudó a construir Haskell.

El documento se llama " Por qué importa la programación funcional " ;, te sugiero que lo leas. Es una buena lectura.

Answer 8

tengamos cuidado con la terminología aquí. El Estado no es per se malo; Los lenguajes funcionales tienen estado. ¿Qué es un " olor de código " es cuando te encuentras con ganas de asignar valores de variables y cambiarlos.

Por supuesto, la mónada del estado de Haskell está ahí solo por esa razón, como con I / O, le permite hacer cosas inseguras y no funcionales en un contexto restringido.

Entonces, sí, es probable que sea un olor a código.