L'utilisation de la monade d'état Haskell est une odeur de code ?

Question

Mon Dieu, je déteste le terme "odeur de code", mais je ne peux pas penser à quelque chose de plus précis.

Je conçois un langage de haut niveau et un compilateur pour Espace blanc pendant mon temps libre pour apprendre la construction de compilateurs, la conception de langages et la programmation fonctionnelle (le compilateur est écrit en Haskell).

Pendant la phase de génération du code du compilateur, je dois maintenir des données de type "état" pendant que je parcours l'arbre syntaxique. Par exemple, lors de la compilation d'instructions de contrôle de flux, je dois générer des noms uniques pour les étiquettes à sauter (étiquettes générées à partir d'un compteur qui est transmis, mis à jour et renvoyé, et l'ancienne valeur du compteur ne doit jamais être réutilisée). Un autre exemple est lorsque je rencontre des chaînes de caractères en ligne dans l'arbre syntaxique, elles doivent être converties de façon permanente en variables de tas (dans Whitespace, les chaînes de caractères sont mieux stockées dans le tas). Je suis en train d'envelopper l'ensemble du module de génération de code dans la monade state pour gérer cela.

On m'a dit que l'écriture d'un compilateur est un problème bien adapté au paradigme fonctionnel, mais je trouve que je le conçois à peu près de la même manière que je le concevrais en C (on peut vraiment écrire du C dans n'importe quel langage - même Haskell avec des monades d'état).

Je veux apprendre à penser en Haskell (plutôt, dans le paradigme fonctionnel) - pas en C avec la syntaxe Haskell. Dois-je vraiment essayer d'éliminer ou de minimiser l'utilisation de la monade d'état, ou s'agit-il d'un "modèle de conception" fonctionnel légitime ?

Answer 1

J'ai écrit plusieurs compilateurs en Haskell, et une monade d'état est une solution raisonnable à de nombreux problèmes de compilation. Mais il faut rester abstrait - ne pas rendre évident l'utilisation d'une monade.

Voici un exemple tiré du compilateur Glasgow Haskell (que j'ai fait no écrire ; je ne travaille que sur quelques bords), où nous construisons des graphes de flux de contrôle. Voici les méthodes de base pour construire des graphes :

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

Mais comme vous l'avez découvert, maintenir un stock d'étiquettes uniques est au mieux fastidieux, c'est pourquoi nous proposons également ces fonctions :

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

L'ensemble Graph est un type abstrait, et le traducteur construit allègrement des graphes de manière purement fonctionnelle, sans être conscient que quelque chose de monadique se passe. Puis, lorsque le graphe est finalement construit, afin de le transformer en un type de données algébrique à partir duquel nous pouvons générer du code, nous lui donnons un ensemble d'étiquettes uniques, nous exécutons la monade d'état et nous sortons la structure de données.

La monade d'état est cachée en dessous ; bien qu'elle ne soit pas exposée au client, la définition de l'option Graph est quelque chose comme ça :

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

ou un peu plus précisément

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

Avec la monade d'état cachée derrière une couche d'abstraction, cela ne sent pas du tout mauvais !

Answer 2

Je dirais que l'État en général n'est pas une odeur de code, tant qu'il reste petit et bien contrôlé.

Cela signifie que l'utilisation de monades telles que State, ST ou des monades personnalisées, ou le simple fait de disposer d'une structure de données contenant des données d'état que vous faites circuler à plusieurs endroits, n'est pas une mauvaise chose. (En fait, les monades sont une aide pour faire exactement cela !) Cependant, avoir un état qui va partout (oui, cela veut dire toi, monade IO !) est une mauvaise odeur.

Un exemple assez clair de ceci a été lorsque mon équipe travaillait sur notre entrée pour le concours de l Concours de programmation ICFP 2009 (le code est disponible à git://git.cynic.net/haskell/icfp-contest-2009). Nous nous sommes retrouvés avec plusieurs parties modulaires différentes :

• VM : la machine virtuelle qui a exécuté le programme de simulation.
• Contrôleurs : plusieurs ensembles différents de routines qui lisent la sortie du simulateur et génèrent de nouvelles entrées de contrôle.
• Solution : génération du fichier de solution basé sur la sortie des contrôleurs.
• Visualisateurs : plusieurs ensembles différents de routines qui lisent les ports d'entrée et de sortie et génèrent une sorte de visualisation ou de journal de ce qui se passe au fur et à mesure de la simulation.

Chacun d'entre eux possède son propre état, et ils interagissent tous de diverses manières par le biais des valeurs d'entrée et de sortie de la VM. Nous avions plusieurs contrôleurs et visualiseurs différents, chacun ayant son propre type d'état.

Le point clé ici était que les internes de tout état particulier étaient limités à leurs propres modules particuliers, et chaque module ne savait rien de l'existence même de l'état des autres modules. Tout ensemble particulier de code et de données avec état ne comptait généralement que quelques dizaines de lignes, avec une poignée d'éléments de données dans l'état.

Tout cela a été collé ensemble dans une petite fonction d'environ une douzaine de lignes qui n'avait aucun accès aux internes de l'un des états, et qui a simplement appelé les bonnes choses dans le bon ordre comme il a bouclé à travers la simulation, et transmis une quantité très limitée d'informations extérieures à chaque module (avec l'état précédent du module, bien sûr).

Lorsque l'état est utilisé de manière aussi limitée, et que le système de types vous empêche de le modifier par inadvertance, il est assez facile à gérer. C'est l'une des beautés de Haskell que de vous permettre de le faire.

Une réponse dit : "N'utilisez pas les monades." De mon point de vue, c'est exactement l'inverse. Les monades sont une structure de contrôle qui, entre autres choses, peut vous aider à minimiser la quantité de code qui touche à l'état. Si l'on prend l'exemple des analyseurs syntaxiques monadiques, l'état de l'analyse (c'est-à-dire le texte en cours d'analyse, l'état d'avancement de l'analyse, les avertissements qui se sont accumulés, etc. ) doit passer par tous les combinateurs utilisés dans l'analyseur syntaxique. Pourtant, seuls quelques combinateurs manipulent directement l'état ; tout le reste utilise l'une de ces quelques fonctions. Cela vous permet de voir clairement et en un seul endroit toute la petite quantité de code qui peut modifier l'état, et de raisonner plus facilement sur la façon dont il peut être modifié, ce qui facilite encore une fois la gestion.

Answer 3

Avez-vous regardé Grammaires d'attributs (AG) ? (Plus d'informations sur wikipedia et un article dans le lecteur de monades) ?

Avec AG, vous pouvez ajouter attributs à un arbre syntaxique. Ces attributs sont séparés en synthétisé y hérité de attributs.

Les attributs synthétisés sont des éléments que vous générez (ou synthétisez) à partir de votre arbre syntaxique. Il peut s'agir du code généré, de tous les commentaires ou de tout autre élément qui vous intéresse.

Les attributs hérités sont des entrées dans votre arbre syntaxique, il peut s'agir de l'environnement ou d'une liste d'étiquettes à utiliser pendant la génération du code.

À l'Université d'Utrecht, nous utilisons le Système de grammaire des attributs ( UUAGC ) pour écrire des compilateurs. Il s'agit d'un préprocesseur qui génère du code haskell ( .hs ) à partir des fichiers fournis .ag des fichiers.

---

Cependant, si vous êtes encore en train d'apprendre Haskell, ce n'est peut-être pas le moment de commencer à apprendre une autre couche d'abstraction par-dessus.

Dans ce cas, vous pourriez écrire manuellement le type de code que les grammaires d'attributs génèrent pour vous, par exemple :

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

Il est possible que vous souhaitiez un foncteur applicatif au lieu d'un monade :

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

Je pense que l'article original l'explique mieux que le wiki, cependant :

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

Answer 5

Je ne pense pas que l'utilisation de la monade d'état soit un problème de code lorsqu'elle est utilisée pour modéliser l'état.

Si vous avez besoin de faire passer l'état dans vos fonctions, vous pouvez le faire explicitement, en prenant l'état comme argument et en le retournant dans chaque fonction. La monade d'état offre une bonne abstraction : elle transmet l'état pour vous et fournit de nombreuses fonctions utiles pour la gestion de l'état. fournit de nombreuses fonctions utiles pour combiner les fonctions qui nécessitent un état. Dans ce cas, l'utilisation de la monade d'état (ou des applicatifs) n'est pas un problème de code.

Cependant, si vous utilisez la monade d'état pour émuler un style de programmation impératif alors qu'une solution fonctionnelle suffirait, vous ne faites que compliquer les choses.