Utilisation de la monade d’État de Haskell une odeur de code?

Question

Mon Dieu, je déteste le terme "odeur de code", mais je ne vois rien de plus précis.

Je conçois un langage de haut niveau & amp; compilateur à espace blanc pendant mon temps libre pour en savoir plus sur la construction du compilateur, la conception du langage et la programmation fonctionnelle ( le compilateur est écrit en Haskell).

Au cours de la phase de génération de code du compilateur, je dois conserver les données "state", au fur et à mesure que je traverse l'arbre de syntaxe. Par exemple, lors de la compilation d'instructions de contrôle de flux, je dois générer des noms uniques pour les étiquettes (étiquettes générées à partir d'un compteur transmis, mis à jour, renvoyé et l'ancienne valeur du compteur ne devant plus jamais être utilisée). . Un autre exemple est lorsque je rencontre des littéraux de chaîne en ligne dans l'arbre de syntaxe, ils doivent être convertis de manière permanente en variables de segment de mémoire (dans Whitespace, les chaînes sont mieux stockées dans le segment de mémoire). Je suis en train d'envelopper tout le module de génération de code dans la monade d'état pour gérer cela.

On m'a dit qu'écrire un compilateur est un problème qui convient bien au paradigme fonctionnel, mais je constate que je le conçois de la même façon que je le concevrais en C (vous pouvez vraiment écrire C dans n'importe langue - 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. Devrais-je vraiment essayer d’éliminer / minimiser l’utilisation de la monade d’État, ou s’agit-il d’un "modèle de conception" fonctionnel légitime?

Answer 1

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 personnalisées, ou simplement la présence d'une structure de données contenant des données d'état que vous transmettez à quelques emplacements, n'est pas une mauvaise chose. (En fait, les monades ne font que nous aider à faire exactement cela!) Cependant, avoir un état qui va partout (oui, cela veut dire que vous, IO monad!) Est une mauvaise odeur.

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

• 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 à partir de la sortie des contrôleurs
• Visualiseurs: plusieurs ensembles de routines différents lisant à la fois les ports d’entrée et de sortie et générant une sorte de visualisation ou un journal de ce qui se passait au fur et à mesure de la progression de la simulation

Chacune de celles-ci a son propre état et elles interagissent toutes de différentes manières via les valeurs d'entrée et de sortie de la VM. Nous avions plusieurs contrôleurs et visualiseurs, chacun ayant son propre état.

Le point clé ici était que les composants internes d’un État donné étaient limités à leurs propres modules et que chaque module ne savait rien de l’existence même de l’état pour les autres modules. Un ensemble particulier de codes et de données avec état ne contient généralement que quelques dizaines de lignes, avec une poignée d'éléments de données dans l'état.

Tout cela était collé dans une petite fonction d’une douzaine de lignes qui n’avait aucun accès aux éléments internes des États et qui appelait simplement les bonnes choses dans le bon ordre lorsqu’elle passait en boucle dans la simulation et passait. une quantité très limitée d'informations extérieures pour chaque module (avec l'état précédent du module, bien sûr).

Lorsque state 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 qui vous permet de le faire.

Une réponse indique "N'utilisez pas de monades". De mon point de vue, c'est exactement à l'envers. Les monades sont une structure de contrôle qui, entre autres choses, peut vous aider à minimiser la quantité de code en contact avec l'état. Si vous prenez comme exemple les analyseurs monadiques, l’état de l’analyse (c’est-à-dire le texte analysé, la distance parcourue, les avertissements qui se sont accumulés, etc.) doit passer par chaque combinateur utilisé dans l’analyseur. . Pourtant, il ne restera que quelques combinateurs manipulant directement l’Etat; tout le reste utilise l'une de ces quelques fonctions. Cela vous permet de voir clairement et au même endroit toute une petite quantité de code qui peut changer l’état, et plus facilement de savoir comment il peut être changé, ce qui facilite encore le traitement.

Answer 2

J'ai écrit plusieurs compilateurs dans Haskell et un monad d'état est une solution raisonnable à de nombreux problèmes de compilation. Mais vous voulez garder le résumé - ne vous rendez pas compte que vous utilisez une monade.

Voici un exemple tiré du Glasgow Haskell Compiler (que j'ai pas écrit; je ne travaille que sur quelques arêtes), dans lequel nous construisons des graphiques de flux de contrôle. Voici les méthodes de base pour créer des graphiques:

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, le maintien d'un stock d'étiquettes uniques est fastidieux, nous proposons donc é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 de Graph est un type abstrait et le traducteur construit gaiement des graphes de manière purement fonctionnelle, sans se rendre compte que quelque chose de monadique se passe. Ensuite, lorsque le graphe est enfin construit, afin de le transformer en un type de données algébrique à partir duquel nous pouvons générer du code, nous lui fournissons un lot d’étiquettes uniques, nous exécutons la monade d’état et extrayons la structure de données.

La monade d’État est cachée dessous; bien que cela ne soit pas exposé au client, la définition de Graph ressemble à peu près à ceci:

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, ça ne sent pas du tout!

Answer 3

Avez-vous consulté les grammaires attributaires (AG)? (Plus d'infos sur wikipedia et un article dans Monad Reader)?

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

Les attributs synthétisés sont des éléments que vous générez (ou synthétisez) à partir de votre arborescence de syntaxe. 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 entrés dans votre arborescence de syntaxe. Il peut s'agir de l'environnement ou d'une liste d'étiquettes à utiliser lors de la génération de code.

L'Université d'Utrecht utilise 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 (fichiers .hs ) à partir des fichiers .ag fournis.

Bien que, si vous apprenez toujours Haskell, alors ce n’est peut-être pas le moment de commencer à apprendre encore une autre couche d’abstraction.

Dans ce cas, vous pouvez écrire manuellement le type de code qui attribue les grammaires générés 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 d’application au lieu d’un monade:

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

Je pense que le document d'origine 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 l'état Monad soit une odeur de code lorsqu'elle modélisait l'état.

Si vous avez besoin de passer l'état à travers 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 combiner des fonctions nécessitant un état. Dans ce cas, l’utilisation de la monade d’État (ou d’applications) n’est pas une odeur 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.

Answer 6

En général, vous devriez essayer d’éviter l’état lorsque cela est possible, mais ce n’est pas toujours pratique. Applicative rend le code efficace plus beau et plus fonctionnel, en particulier le code de traversée d’arbres peut bénéficier de ce style. Pour le problème de la génération de noms, il existe maintenant un joli paquet disponible: offre de valeur .

Answer 7

Bien, n'utilisez pas de monades. La puissance de la programmation fonctionnelle est la pureté de la fonction et sa réutilisation. Il y a ce journal qu'un professeur à moi a écrit et qu'il est l'un des types qui ont aidé à construire Haskell.

Le document s'appelle & Pourquoi la programmation fonctionnelle est importante " ;, Je vous suggère de le lire. C'est une bonne lecture.

Answer 8

Faisons attention à la terminologie ici. L'état n'est pas mauvais en soi; les langages fonctionnels ont l'état. Qu'est-ce qu'une "odeur de code"? c’est quand vous voulez assigner des valeurs à des variables et les changer.

Bien sûr, la monade d’état de Haskell n’est là que pour cette raison - comme pour les E / S, elle vous permet de faire des choses dangereuses et non fonctionnelles dans un contexte contraint.

Donc, oui, c'est probablement une odeur de code.