monadas monada monad funtores functores dividir haskell coding-style monads state-monad

funtores - monada io haskell



¿El uso de la mónada del estado de Haskell es un olor de código? (8)

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 y un compilador de Whitespace en mi tiempo libre para aprender sobre construcción de compiladores, diseño de lenguaje y programación funcional (el compilador está siendo escrito en Haskell).

Durante la fase de generación de código del compilador, tengo que mantener los datos "state" -ish mientras recorro el árbol de sintaxis. Por ejemplo, al compilar declaraciones de control de flujo, necesito generar nombres únicos para las etiquetas a las que saltar (etiquetas generadas desde un contador que se transfiere, actualiza y devuelve, y el valor anterior del contador nunca debe volver a usarse). Otro ejemplo es cuando encuentro literales de cadenas en línea en el árbol de sintaxis, necesitan convertirse permanentemente en variables de montón (en Espacios en blanco, las cadenas se almacenan mejor en el montón). Actualmente estoy envolviendo todo el módulo de generación de código en la mónada de estado para manejar esto.

Me han dicho que escribir un compilador es un problema que se adapta bien al paradigma funcional, pero creo que estoy diseñando esto de la misma manera en que lo diseñaría en C (realmente puedes escribir C en cualquier idioma, incluso Haskell con mónadas de estado).

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

¿Has mirado las gramáticas de atributos (AG)? (Más información en wikipedia y un article en el Monad Reader)?

Con AG puede agregar atributos a un árbol de sintaxis. Estos atributos están separados en atributos sintetizados y heredados .

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

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

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

Aunque, si todavía 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 generan las gramáticas para usted, 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

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ó y es uno de los tipos que ayudó a construir Haskell.

El documento se llama " Por qué la programación funcional es importante ", le sugiero que lo lea. Es una buena lectura.

En general, debe intentar 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 árbol puede beneficiarse de este estilo. Para el problema de la generación de nombres, ahora hay un paquete bastante agradable disponible: value-supply .

He escrito múltiples 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 que sea obvio que está usando una mónada.

Aquí hay un ejemplo del compilador Haskell de Glasgow (que no escribí, simplemente trabajo en algunos bordes), donde construimos gráficos de flujo de control. Estas son las formas básicas para 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 asunto de Graph es de tipo abstracto, y el traductor simplemente construye gráficos alegremente de manera puramente funcional, sin darse cuenta de que algo monádico está sucediendo. Luego, cuando finalmente se construye el gráfico, para convertirlo en un tipo de datos algebraicos desde los cuales podemos generar código, le damos un suministro de etiquetas únicas, ejecutamos la mónada de estado 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 escondida detrás de una capa de abstracción, ¡no huele mal!

No creo que usar State Monad sea un olor a código cuando se usaba para modelar el estado.

Si necesita enhebrar estado a través de sus funciones, puede hacerlo explícitamente, tomando el estado como argumento y devolviéndolo en cada función. State Monad ofrece una buena abstracción: le transfiere el estado y proporciona muchas funciones útiles para combinar funciones que requieren estado. En este caso, usar State Monad (o Applicatives) no es un olor a código.

Sin embargo, si usa State Monad para emular un estilo imperativo de programación, mientras que una solución funcional sería suficiente, simplemente está complicando las cosas.

Tengamos cuidado con la terminología aquí. El estado no es per se malo; los lenguajes funcionales tienen estado. Lo que es un "olor a código" es cuando desea asignar valores de variables y cambiarlos.

Por supuesto, la mónada del estado de Haskell está ahí por esa misma razón, al igual que con E / S, le permite hacer cosas inseguras y poco funcionales en un contexto restringido.

Entonces, sí, probablemente sea un olor a código.

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

Esto significa que no es malo el uso de mónadas como State, ST o personalizadas, o simplemente tener una estructura de datos que contenga datos de estado que pase a algunos lugares. (¡En realidad, las mónadas son solo ayuda para hacer exactamente esto!) Sin embargo, tener un estado que va por todos lados (sí, esto significa que usted, ¡IO mónada!) Es un mal olor.

Un ejemplo bastante claro de esto fue cuando mi equipo estaba trabajando en nuestra entrada para el Concurso de programación ICFP 2009 (el código está disponible en git: //git.cynic.net/haskell/icfp-contest-2009). Terminamos con varias partes modulares diferentes a 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 diversas maneras a través de los valores de entrada y salida de la máquina virtual. Teníamos varios controladores y visualizadores diferentes, cada uno de los cuales tenía su propio tipo diferente de estado.

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

Todo esto estaba pegado 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 llamaba a las cosas correctas en el orden correcto, ya que pasaba por la simulación, y pasaba una muy limitada cantidad de información externa a cada módulo (junto con el estado previo del módulo, por supuesto).

Cuando el estado se usa de manera limitada y el sistema de tipos impide que usted lo modifique 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 un ejemplo, el estado del análisis sintáctico (es decir, el texto analizado, cuánto ha llegado uno, las advertencias que se han acumulado, etc.) debe ejecutarse a través de cada combinador utilizado 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 claramente y en un solo lugar toda una pequeña cantidad de código que puede cambiar el estado, y más fácilmente razonar sobre cómo se puede cambiar, lo que hace que sea más fácil de tratar.