Une conception à grande échelle à Haskell? [fermé]

565

Quelle est une bonne façon de concevoir / structurer de grands programmes fonctionnels, en particulier dans Haskell?

J'ai parcouru un tas de tutoriels (Write Yourself a Scheme étant mon préféré, avec Real World Haskell juste après) - mais la plupart des programmes sont relativement petits et à usage unique. De plus, je ne considère pas que certains d'entre eux soient particulièrement élégants (par exemple, les vastes tables de recherche dans WYAS).

Je veux maintenant écrire des programmes plus grands, avec plus de pièces mobiles - acquérir des données à partir d'une variété de sources différentes, les nettoyer, les traiter de différentes manières, les afficher dans les interfaces utilisateur, les conserver, communiquer sur les réseaux, etc. une meilleure structure de ce code pour être lisible, maintenable et adaptable aux exigences changeantes?

Il existe une assez grande littérature traitant de ces questions pour les grands programmes impératifs orientés objet. Des idées comme MVC, des modèles de conception, etc. sont des prescriptions décentes pour atteindre des objectifs généraux tels que la séparation des préoccupations et la réutilisabilité dans un style OO. De plus, les nouveaux langages impératifs se prêtent à un style de refactoring de conception à mesure que vous grandissez auquel, à mon avis novice, Haskell semble moins bien adapté.

Existe-t-il une littérature équivalente pour Haskell? Comment le zoo des structures de contrôle exotiques disponibles en programmation fonctionnelle (monades, flèches, applicatives, etc.) est-il le mieux employé à cet effet? Quelles meilleures pratiques pourriez-vous recommander?

Merci!

EDIT (ceci fait suite à la réponse de Don Stewart):

@dons a mentionné: "Les monades capturent les conceptions architecturales clés en types."

Je suppose que ma question est: comment penser les conceptions architecturales clés dans un langage fonctionnel pur?

Prenons l'exemple de plusieurs flux de données et de plusieurs étapes de traitement. Je peux écrire des analyseurs modulaires pour les flux de données dans un ensemble de structures de données, et je peux implémenter chaque étape de traitement comme une fonction pure. Les étapes de traitement requises pour une donnée dépendront de sa valeur et des autres. Certaines étapes doivent être suivies d'effets secondaires tels que les mises à jour de l'interface graphique ou les requêtes de base de données.

Quelle est la «bonne» façon de lier les données et les étapes d'analyse d'une manière agréable? On pourrait écrire une grosse fonction qui fait ce qu'il faut pour les différents types de données. Ou on pourrait utiliser une monade pour garder une trace de ce qui a été traité jusqu'à présent et que chaque étape de traitement obtienne tout ce dont elle a besoin à partir de l'état de la monade. Ou on pourrait écrire des programmes largement séparés et envoyer des messages (je n'aime pas beaucoup cette option).

Les diapositives qu'il a liées ont une puce Things we Need: "Idioms for mapping design on types / functions / classes / monads". Quels sont les idiomes? :)

Dan
la source
9
Je pense que l'idée de base lors de l'écriture de grands programmes dans un langage fonctionnel est de petits modules spécialisés et sans état communiquant via le passage de messages . Bien sûr, vous devez faire semblant un peu parce qu'un vrai programme a besoin d'un état. Je pense que c'est là que F # brille sur Haskell.
ChaosPandion
18
@Chaos mais seulement Haskell applique l'apatridie par défaut. Vous n'avez pas le choix, et vous devez travailler dur pour introduire l'état (pour briser la compositionnalité) dans Haskell :-)
Don Stewart
7
@ChaosPandion: Je ne suis pas en désaccord, en théorie. Certainement, dans un langage impératif (ou fonctionnel conçu autour de la transmission de messages), cela pourrait très bien être ce que je ferais. Mais Haskell a d'autres façons de gérer l'État, et peut-être me laisse-t-il plus de bénéfices «purs».
Dan
1
J'ai écrit un peu à ce sujet sous "Design Guidelines" dans ce document: community.haskell.org/~ndm/downloads/…
Neil Mitchell
5
@JonHarrop n'oublions pas que même si MLOC est une bonne métrique lorsque vous comparez des projets dans des langages similaires, cela n'a pas beaucoup de sens pour la comparaison entre langages, en particulier avec des langages comme Haskell, où la réutilisation et la modularité du code sont beaucoup plus faciles et sûres. par rapport à certaines langues.
Tair

Réponses:

519

J'en parle un peu dans Engineering Large Projects à Haskell et dans la conception et la mise en œuvre de XMonad. L'ingénierie dans son ensemble consiste à gérer la complexité. Les principaux mécanismes de structuration de code dans Haskell pour gérer la complexité sont:

Le système de type

  • Utilisez le système de type pour appliquer les abstractions, simplifiant les interactions.
  • Appliquer des invariants clés via des types
    • (par exemple que certaines valeurs ne peuvent pas échapper à une certaine portée)
    • Ce code ne fait pas d'E / S, ne touche pas le disque
  • Appliquer la sécurité: exceptions vérifiées (Peut-être / Soit), éviter de mélanger les concepts (Word, Int, Adresse)
  • De bonnes structures de données (comme les fermetures à glissière) peuvent rendre certaines classes de tests inutiles, car elles excluent par exemple les erreurs hors limites statiquement.

Le profileur

  • Fournissez des preuves objectives des profils de tas et de temps de votre programme.
  • Le profilage de tas, en particulier, est le meilleur moyen de garantir une utilisation inutile de la mémoire.

Pureté

  • Réduisez considérablement la complexité en supprimant l'état. Échelles de code purement fonctionnelles, car elles sont de composition. Tout ce dont vous avez besoin est le type pour déterminer comment utiliser du code - il ne se cassera pas mystérieusement lorsque vous modifiez une autre partie du programme.
  • Utilisez beaucoup de programmation de type "modèle / vue / contrôleur": analysez les données externes dès que possible dans des structures de données purement fonctionnelles, opérez sur ces structures, puis une fois que tout le travail est terminé, restituez / rincez / sérialisez. Garde la majeure partie de votre code pur

Essai

  • QuickCheck + Haskell Code Coverage, pour vous assurer de tester les choses que vous ne pouvez pas vérifier avec les types.
  • GHC + RTS est idéal pour voir si vous passez trop de temps à faire du GC.
  • QuickCheck peut également vous aider à identifier des API orthogonales propres pour vos modules. Si les propriétés de votre code sont difficiles à énoncer, elles sont probablement trop complexes. Continuez le refactoring jusqu'à ce que vous ayez un ensemble propre de propriétés qui peuvent tester votre code, qui se composent bien. Ensuite, le code est probablement aussi bien conçu.

Monades pour structurer

  • Les monades capturent les conceptions architecturales clés en types (ce code accède au matériel, ce code est une session mono-utilisateur, etc.)
  • Par exemple, la monade X dans xmonad, capture précisément la conception pour quel état est visible pour quels composants du système.

Classes de types et types existentiels

  • Utilisez des classes de types pour fournir l'abstraction: masquez les implémentations derrière les interfaces polymorphes.

Concurrence et parallélisme

  • Faufilez- parvous dans votre programme pour battre la concurrence avec un parallélisme facile à composer.

Refactor

  • Vous pouvez refactoriser beaucoup à Haskell . Les types garantissent que vos modifications à grande échelle seront sûres, si vous utilisez les types à bon escient. Cela aidera votre échelle de base de code. Assurez-vous que vos refactorisations entraîneront des erreurs de type jusqu'à la fin.

Utilisez le FFI à bon escient

  • Le FFI facilite le jeu avec le code étranger, mais ce code étranger peut être dangereux.
  • Soyez très prudent dans les hypothèses sur la forme des données renvoyées.

Programmation méta

  • Un peu de Template Haskell ou de génériques peut enlever le passe-partout.

Emballage et distribution

  • Utilisez Cabal. Ne lancez pas votre propre système de construction. (EDIT: En fait, vous voulez probablement utiliser Stack maintenant pour commencer.).
  • Utilisez Haddock pour de bons documents API
  • Des outils comme graphmod peuvent montrer les structures de vos modules.
  • Comptez sur les versions Haskell Platform des bibliothèques et des outils, si possible. C'est une base stable. (EDIT: Encore une fois, ces jours-ci, vous voudrez probablement utiliser Stack pour obtenir une base stable et opérationnelle.)

Avertissements

  • Utilisez -Wallpour garder votre code propre des odeurs. Vous pouvez également consulter Agda, Isabelle ou Catch pour plus d'assurance. Pour une vérification semblable à des peluches, consultez le grand hlint , qui suggérera des améliorations.

Avec tous ces outils, vous pouvez maîtriser la complexité, en supprimant autant d'interactions entre les composants que possible. Idéalement, vous disposez d'une très grande base de code pur, qui est vraiment facile à maintenir, car il est de composition. Ce n'est pas toujours possible, mais cela vaut la peine d'être visé.

En général: décomposez les unités logiques de votre système en les plus petits composants référentiellement transparents possibles, puis implémentez-les en modules. Les environnements globaux ou locaux pour les ensembles de composants (ou à l'intérieur des composants) peuvent être mappés sur des monades. Utilisez des types de données algébriques pour décrire les structures de données principales. Partagez largement ces définitions.

Don Stewart
la source
8
Merci Don, votre réponse est excellente - ce sont toutes des directives précieuses et je les consulterai régulièrement. Je suppose que ma question survient une étape avant d'avoir besoin de tout cela, cependant. Ce que j'aimerais vraiment savoir, ce sont les "idiomes pour mapper la conception sur des types / fonctions / classes / monades" ... Je pourrais essayer d'inventer les miens, mais j'espérais qu'il pourrait y avoir un ensemble de meilleures pratiques distillées quelque part - ou sinon, des recommandations pour un code bien structuré à lire d'un système de grande taille (par opposition à, disons, une bibliothèque ciblée). J'ai édité mon message pour poser cette même question plus directement.
Dan
6
J'ai ajouté du texte sur la décomposition de la conception des modules. Votre objectif est d'identifier les fonctions logiquement liées dans des modules qui ont des interfaces référentiellement transparentes avec d'autres parties du système et d'utiliser des types de données purement fonctionnels dès que possible, autant que possible, pour modéliser le monde extérieur en toute sécurité. Le document de conception xmonad couvre une grande partie de ceci: xmonad.wordpress.com/2009/09/09/…
Don Stewart
3
J'ai essayé de télécharger les diapositives de la conférence Engineering Large Projects in Haskell , mais le lien semblait rompu. En voici une qui fonctionne: galois.com/~dons/talks/dons-londonhug-decade.pdf
mik01aj
3
J'ai réussi à trouver ce nouveau lien de téléchargement: pau-za.cz/data/2/sprava.pdf
Riccardo T.
3
@Heather Même si le lien de téléchargement sur la page que j'ai mentionnée dans le commentaire juste avant ne fonctionne pas, il semble que les diapositives peuvent toujours être consultées sur scribd: scribd.com/doc/19503176/The-Design-and-Implementation-of -xmonad
Riccardo T.
118

Don vous a donné la plupart des détails ci-dessus, mais voici mes deux cents de faire des programmes avec état vraiment nitty-graveleux comme les démons système dans Haskell.

  1. À la fin, vous vivez dans une pile de transformateurs monade. En bas se trouve IO. Au-dessus de cela, chaque module majeur (dans le sens abstrait, pas le sens module dans un fichier) mappe son état nécessaire dans une couche de cette pile. Donc, si vous avez votre code de connexion à la base de données caché dans un module, vous écrivez tout pour être sur un type de connexion MonadReader m => ... -> m ... et vos fonctions de base de données peuvent toujours obtenir leur connexion sans fonctions d'autres modules devant être conscients de son existence. Vous pourriez vous retrouver avec une couche portant votre connexion à la base de données, une autre votre configuration, une troisième vos différents sémaphores et mvars pour la résolution du parallélisme et de la synchronisation, une autre que votre fichier journal gère, etc.

  2. Calculez votre erreur de manipulation d' abord . La plus grande faiblesse à l'heure actuelle pour Haskell dans les systèmes plus grands est la pléthore de méthodes de gestion des erreurs, y compris les moche comme Peut-être (ce qui est faux parce que vous ne pouvez pas retourner d'informations sur ce qui s'est mal passé; utilisez toujours Soit au lieu de Peut-être, sauf si vous avez vraiment signifie simplement des valeurs manquantes). Découvrez comment vous allez le faire en premier et configurez des adaptateurs à partir des divers mécanismes de gestion des erreurs que vos bibliothèques et autres codes utilisent dans votre dernier. Cela vous sauvera un monde de chagrin plus tard.

Addendum (extrait des commentaires; merci à Lii & liminalisht ) -
plus de discussion sur les différentes façons de découper un grand programme en monades dans une pile:

Ben Kolera donne une excellente introduction pratique à ce sujet, et Brian Hurt discute des solutions au problème de l' liftintégration d'actions monadiques dans votre monade personnalisée. George Wilson montre comment utiliser mtlpour écrire du code qui fonctionne avec n'importe quelle monade qui implémente les classes de caractères requises, plutôt que votre type de monade personnalisé. Carlo Hamalainen a écrit quelques notes courtes et utiles résumant le discours de George.

user349653
la source
5
Deux bons points! Cette réponse a le mérite d'être raisonnablement concrète, ce que les autres ne sont pas. Il serait intéressant de lire plus de discussions sur les différentes façons de découper un grand programme en monades dans une pile. Veuillez publier des liens vers ces articles si vous en avez!
Lii
6
@Lii Ben Kolera donne une excellente introduction pratique à ce sujet, et Brian Hurt discute des solutions au problème de l' liftintégration d'actions monadiques dans votre monade personnalisée. George Wilson montre comment utiliser mtlpour écrire du code qui fonctionne avec n'importe quelle monade qui implémente les classes de caractères requises, plutôt que votre type de monade personnalisé. Carlo Hamalainen a écrit quelques notes courtes et utiles résumant le discours de George.
liminalisht
Je suis d'accord que les piles de transformateurs monades ont tendance à être des fondations architecturales clés, mais j'essaie très fort de garder les E / S hors de leur portée. Ce n'est pas toujours possible, mais si vous pensez à ce que "et puis" signifie dans votre monade, vous découvrirez peut-être que vous avez vraiment une continuation ou un automate quelque part en bas qui peut ensuite être interprété dans IO par une fonction "run".
Paul Johnson
Comme @PaulJohnson l'a déjà souligné, cette approche Monad Transformer Stack semble en conflit avec le modèle de conception ReaderT de
McBear Holden
43

Concevoir de grands programmes dans Haskell n'est pas si différent de le faire dans d'autres langues. La programmation dans son ensemble consiste à diviser votre problème en éléments gérables et à savoir comment les assembler; le langage d'implémentation est moins important.

Cela dit, dans un grand modèle, il est agréable d'essayer de tirer parti du système de saisie pour vous assurer que vous ne pouvez assembler vos pièces que d'une manière correcte. Cela peut impliquer des types nouveaux ou fantômes pour que les choses qui semblent avoir le même type soient différentes.

Quand il s'agit de refactoriser le code au fur et à mesure, la pureté est une grande aubaine, alors essayez de garder autant de code que possible pur. Le code pur est facile à refactoriser, car il n'a aucune interaction cachée avec d'autres parties de votre programme.

auguste
la source
14
En fait, j'ai trouvé que la refactorisation est assez frustrante si les types de données doivent changer. Cela nécessite de modifier fastidieusement l'arité de nombreux constructeurs et correspondances de motifs. (Je conviens que la refactorisation de fonctions pures en d'autres fonctions pures du même type est facile - tant que l'on ne touche pas aux types de données)
Dan
2
@Dan Vous pouvez vous en sortir complètement gratuit avec des modifications plus petites (comme l'ajout d'un champ) lorsque vous utilisez des enregistrements. Certains voudront peut-être faire des disques une habitude (je suis l'un d'eux ^^ ").
MasterMastic
5
@Dan Je veux dire que si vous changez le type de données d'une fonction dans n'importe quelle langue, ne devez-vous pas faire de même? Je ne vois pas comment un langage comme Java ou C ++ pourrait vous aider à cet égard. Si vous dites que vous pouvez utiliser une sorte d'interface commune à laquelle les deux types obéissent, vous devriez avoir fait cela avec Typeclasses dans Haskell.
point
4
@semicon la différence pour des langages comme Java est l'existence d'outils de refactoring matures, bien testés et entièrement automatisés. Généralement, ces outils intègrent des éditeurs fantastiques et enlèvent une grande partie du travail fastidieux associé au refactoring. Haskell nous donne un système de type génial avec lequel détecter les choses qui doivent être modifiées dans un refactoring, mais les outils pour effectuer réellement ce refactoring sont (à l'heure actuelle) très limités, en particulier par rapport à ce qui était déjà disponible dans Java écosystème depuis plus de 10 ans.
jsk
16

J'ai appris la programmation fonctionnelle structurée la première fois avec ce livre . Ce n'est peut-être pas exactement ce que vous recherchez, mais pour les débutants en programmation fonctionnelle, cela peut être l'une des meilleures premières étapes pour apprendre à structurer des programmes fonctionnels - indépendamment de l'échelle. À tous les niveaux d'abstraction, la conception doit toujours avoir des structures clairement disposées.

L'art de la programmation fonctionnelle

L'art de la programmation fonctionnelle

http://www.cs.kent.ac.uk/people/staff/sjt/craft2e/

comonad
la source
11
Aussi génial que le Craft of FP soit - j'en ai appris Haskell - c'est un texte d'introduction pour les programmeurs débutants , pas pour la conception de grands systèmes dans Haskell.
Don Stewart,
3
Eh bien, c'est le meilleur livre que je connaisse sur la conception d'API et le masquage des détails d'implémentation. Avec ce livre, je suis devenu un meilleur programmeur en C ++ - simplement parce que j'ai appris de meilleures façons d'organiser mon code. Eh bien, votre expérience (et votre réponse) est certainement meilleure que ce livre, mais Dan pourrait probablement être un débutant à Haskell. ( where beginner=do write $ tutorials `about` Monads)
comonad
11

J'écris actuellement un livre intitulé "Design fonctionnel et architecture". Il vous fournit un ensemble complet de techniques pour construire une grande application en utilisant une approche fonctionnelle pure. Il décrit de nombreux modèles et idées fonctionnels lors de la construction d'une application de type SCADA «Andromeda» pour contrôler les vaisseaux spatiaux à partir de zéro. Ma langue principale est le haskell. Le livre couvre:

  • Approches de la modélisation de l'architecture à l'aide de diagrammes;
  • Analyse des besoins;
  • Modélisation de domaine DSL intégré;
  • Conception et mise en œuvre DSL externe;
  • Monades comme sous-systèmes avec effets;
  • Monades libres comme interfaces fonctionnelles;
  • EDSL fléchés;
  • Inversion de contrôle à l'aide d'eDSL monadiques gratuits;
  • Mémoire transactionnelle logicielle;
  • Lentilles;
  • État, lecteur, écrivain, RWS, monades ST;
  • État impur: IORef, MVar, STM;
  • Modélisation de domaine multithreading et simultanée;
  • GUI;
  • Applicabilité des techniques et approches traditionnelles telles que UML, SOLID, GRASP;
  • Interaction avec des sous-systèmes impurs.

Vous pouvez vous familiariser avec le code du livre ici , et le code du projet 'Andromeda' .

Je m'attends à terminer ce livre à la fin de 2017. En attendant, vous pouvez lire mon article "Conception et architecture en programmation fonctionnelle" (Rus) ici .

MISE À JOUR

J'ai partagé mon livre en ligne (5 premiers chapitres). Voir le post sur Reddit

graninas
la source
Alexander, pourriez-vous bien vouloir mettre à jour cette note lorsque votre livre est terminé, afin que nous puissions le suivre. À votre santé.
Max
4
Sûr! Pour l'instant, j'ai terminé la moitié du texte, mais c'est un tiers du travail global. Alors, gardez votre intérêt, ça m'inspire beaucoup!
graninas
2
Salut! J'ai partagé mon livre en ligne (seulement les 5 premiers chapitres). Voir le post sur Reddit: reddit.com/r/haskell/comments/6ck72h/…
graninas
merci pour le partage et le travail!
Max
J'attends vraiment ça avec impatience!
patriques
7

Le blog de Gabriel Les architectures de programme évolutives méritent peut-être une mention.

Les modèles de conception Haskell diffèrent des modèles de conception traditionnels d'une manière importante:

  • Architecture conventionnelle : combiner plusieurs composants de type A pour générer un "réseau" ou une "topologie" de type B

  • Architecture Haskell : combinez plusieurs composants de type A pour générer un nouveau composant du même type A, qui ne se distingue pas de ses parties substituantes

Il me semble souvent qu'une architecture apparemment élégante a souvent tendance à tomber des bibliothèques qui présentent ce joli sens de l'homogénéité, d'une manière ascendante. À Haskell, cela est particulièrement apparent - les modèles qui étaient traditionnellement considérés comme une «architecture descendante» ont tendance à être capturés dans des bibliothèques comme mvc , Netwire et Cloud Haskell. . C'est-à-dire, j'espère que cette réponse ne sera pas interprétée comme une tentative de remplacer l'une des autres dans ce fil, juste que les choix structurels peuvent et doivent idéalement être abstraits dans les bibliothèques par des experts du domaine. À mon avis, la vraie difficulté de construire de grands systèmes est d'évaluer ces bibliothèques sur leur «bonté» architecturale par rapport à toutes vos préoccupations pragmatiques.

Comme le mentionne liminalisht dans les commentaires, Le modèle de conception de catégorie est un autre article de Gabriel sur le sujet, dans la même veine.

Rehno Lindeque
la source
3
Je mentionnerais un autre article de Gabriel Gonzalez sur le modèle de conception de catégorie . Son argument de base est que ce que nous, les programmeurs fonctionnels, considérons comme une "bonne architecture" est en réalité une "architecture de composition" - c'est la conception de programmes utilisant des éléments dont la composition est garantie. Puisque les lois de catégorie garantissent que l'identité et l'associativité sont préservées sous la composition, une architecture de composition est obtenue en utilisant des abstractions pour lesquelles nous avons une catégorie - par exemple, fonctions pures, actions monadiques, tuyaux, etc.
liminalisht
3

Peut-être devez-vous prendre un peu de recul et réfléchir à la façon de traduire la description du problème en conception en premier lieu. Étant donné que Haskell est si haut niveau, il peut capturer la description du problème sous la forme de structures de données, les actions en tant que procédures et la transformation pure en tant que fonctions. Ensuite, vous avez un design. Le développement commence lorsque vous compilez ce code et trouvez des erreurs concrètes sur les champs manquants, les instances manquantes et les transformateurs monadiques manquants dans votre code, car par exemple, vous effectuez un accès à une base de données à partir d'une bibliothèque qui a besoin d'une certaine monade d'état dans une procédure d'E / S. Et voila, il y a le programme. Le compilateur nourrit vos esquisses mentales et donne une cohérence à la conception et au développement.

De cette façon, vous bénéficiez de l'aide de Haskell depuis le début, et le codage est naturel. Je ne voudrais pas faire quelque chose de «fonctionnel» ou de «pur» ou assez général si ce que vous avez en tête est un problème concret ordinaire. Je pense que la suringénierie est la chose la plus dangereuse en informatique. Les choses sont différentes lorsque le problème est de créer une bibliothèque qui résume un ensemble de problèmes connexes.

agocorona
la source