URL: https://linuxfr.org/news/sortie-de-ghc-8-2-1 Title: Sortie de GHC 8.2.1 Authors: Guillaum Davy Defaud, Benoît Sibaud, Snark, BAud, Yves Bourguignon, ZeroHeure, gipoisson, palm123, Nÿco, Sytoka Modon, octachron et Pierre Jarillon Date: 2017年04月13日T10:18:18+02:00 License: CC By-SA Tags: ghc et haskell Score: 46 Une nouvelle version majeure du compilateur GHC pour [Haskell](https://www.haskell.org/) est sortie. ![GHC](https://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png) Cette dépêche présente rapidement le langage Haskell, puis les nouveautés de la version 8.2.1 qui vient de sortir. En fin de dépêche, un exemple plus complet d’un code Haskell est présenté afin de motiver à l’usage de ce langage. ---- [DLFP : Sortie de GHC 8.0.2 et une petite histoire de typage statique](https://linuxfr.org/news/sortie-de-ghc-8-0-2-et-une-petite-histoire-de-typage-statique) [[ANNOUNCE] GHC 8.2.1 release candidate 1](https://mail.haskell.org/pipermail/ghc-devs/2017-April/014096.html) [[ANNOUNCE] GHC 8.2.1 release candidate 2](https://mail.haskell.org/pipermail/ghc-devs/2017-May/014197.html) [[ANNOUNCE] GHC 8.2.1 release candidate 3 available](https://mail.haskell.org/pipermail/ghc-devs/2017-July/014364.html) [[ANNOUNCE] GHC 8.2.1 available](https://mail.haskell.org/pipermail/ghc-devs/2017-July/014422.html) [Notes de version de la 8.2.1](https://downloads.haskell.org/%7Eghc/8.2.1/docs/html/users_guide/8.2.1-notes.html) ---- # Présentation d’Haskell et de GHC [Haskell](https://fr.wikipedia.org/wiki/Haskell) est un [langage de programmation fonctionnelle](https://fr.wikipedia.org/wiki/Programmation_fonctionnelle). Je vous invite à lire la [dépêche de la sortie de GHC 8.0.1](http://linuxfr.org/news/le-compilateur-ghc-haskell-en-version-8-0-1) qui réalise une présentation plus complète du langage. Une reformulation de [la page de présentation du langage](https://www.haskell.org) pourrait être la suivante : - Haskell est un langage statiquement typé, chaque expression a un type qui est déterminé à la compilation et le compilateur s’assure que l’assemblage d’expressions a un sens ; ceci permet de fournir quelques garanties sur le programme, mais cela permet aussi beaucoup d’expressivité. - Haskell est un langage au typage inféré, cela signifie que tous les avantages du typage statique viennent gratuitement, sans devoir écrire de déclaration complexe de type ; - Haskell est purement fonctionnel, c’est un des langages (sans parler des langages dérivés d’Haskell ou d’un de ses ancêtres, Miranda, purement fonctionnel et à évaluation paresseuse) qui a cette propriété où, de façon simplifiée, les effets de bords apparaissent explicitement ; - Haskell est concurrent, GHC, son compilateur le plus connu propose des primitives efficaces pour la concurrence et est capable d’exploiter tous les cœurs de calcul d’une machine ; - Haskell est rapide : dans certains cas, on peut approcher les performances de langages comme C++ ; - Haskell est paresseux, c’est un des rares langages à ma connaissance ayant cette caractéristique ; - Haskell vient avec de nombreux paquets pour de nombreuses applications. À mon avis, Haskell / GHC est un outil intéressant à regarder, car il est un des rares langages « grand public » à proposer certaines fonctionnalités, comme la séparation explicite des effets de bord ou l’évaluation paresseuse. En outre, Haskell propose un système de type très puissant permettant de modéliser son domaine de travail de façon élégante. Il s’agit d’un outil capable dans beaucoup de domaines, allant du Web au HPC, proposant de très bonnes performances et une sécurité accrue. # Changements Comme d’habitude, de nombreux bogues et autres subtilités ont été réglés. J’ai essayé de résumer dans cette section les points que je trouve intéressants dans les notes de mise à jour. Mon changement préféré est que le compilateur affiche maintenant ses messages d’erreur avec de la couleur et un petit symbole montrant la zone de l’erreur. ## Performance Un des gros apports de cette 8.2.1 concerne la performance du compilateur qui est annoncé comme plus rapide, mais les notes de versions sont pauvres d’informations à ce sujet. De nombreux points visant les performances du code exécuté ont été traités, certains sont discutés dans les points suivants. ## Join points Les « _join points_ » sont [décrits sur le wiki](https://ghc.haskell.org/trac/ghc/wiki/SequentCore) et dans cette vidéo de Simon Peyton Jones : [_Compiling without continuations_](https://www.youtube.com/watch?v=LMTr8yw0Gk4). Il s’agit d’une optimisation permettant de détecter plus de code sujet à être transformé en appel récursif terminal, ceci permettant une réduction non négligeable des allocations, puisqu’un appel récursif terminal se résume à peu de choses près à un saut dans le programme. ## Compact regions Un des gros reproches faits à la gestion de mémoire par [ramasse‐miettes](https://fr.wikipedia.org/wiki/Ramasse-miettes_(informatique)) est le temps que peuvent prendre les phases de collection de mémoire. Dans le cas d’Haskell, l’implémentation choisie est en mode « _stop the world_ », dit autrement, tout s’arrête pendant la phase de récupération de la mémoire. Cette phase peut être longue car toute la mémoire utilisée par le processus doit être scannée pour mettre à jour la liste des objets vivants ou morts, et ceci peut introduire des pauses peu acceptables dans certains contextes temps réel. GHC 8.2 propose les [_compact regions_](https://hackage.haskell.org/package/compact-0.1.0.1/docs/Data-Compact.html) qui sont des espaces de stockage d’objets qui ne font pas référence à d’autres objets en dehors de cet espace. Ainsi le ramasse‐miettes peut ignorer cet espace pendant sa phase de parcours de la mémoire pour un gain de temps proportionnel à la quantité de mémoire qui n’a pas été parcourue. Point intéressant, une région compacte peut être sérialisée sur le disque de façon efficace. ## Types somme unpacked La représentation en mémoire d’un objet hiérarchique en Haskell dans GHC est composée de nombreuses indirections de pointeurs qui consomment de la mémoire et coûtent cher en performance du fait de l’absence de localité et d’un stress supplémentaire sur le ramasse‐miettes. Le travail sur l’extension [UnpackedSumTypes](https://ghc.haskell.org/trac/ghc/wiki/UnpackedSumTypes) permet de représenter plus efficacement les types somme (c.‐à‐d. les _enums_). ## NUMA Des optimisations pour les architectures [NUMA](https://fr.wikipedia.org/wiki/Non_Uniform_Memory_Access "Non Uniform Memory Access") sont en place. Pour rappel, les architectures NUMA ont des zones de la mémoire qui sont privilégiées par certains cœurs de calcul. Ainsi, il est plus efficace d’allouer la mémoire nécessaire pour un cœur dans une zone proche de celui‐ci. ## Meilleure gestion du format DWARF Le format [DWARF](https://en.wikipedia.org/wiki/DWARF) est utilisé par de nombreux outils de débogage ou d’analyse de performance comme [_gdb_](https://www.gnu.org/software/gdb/), [_valgrind_](valgrind.org), [_perf_](https://perf.wiki.kernel.org). L’amélioration de sa gestion permet, entre autres, une meilleure prise en charge de ces outils. Pour information, [_perf_](https://perf.wiki.kernel.org) est un outil qui permet de faire du profilage statistique de tout programme. Au lieu d’instrumenter le code pour compter très précisément les appels de fonctions, ce que pourrait faire un compilateur, _perf_ se contente de regarder l’état du programme à différents instants. Cette méthode de profilage a de nombreux avantages. Elle ne nécessite pas de recompiler le code source pour ajouter l’instrumentation et, ainsi, elle ne modifie pas l’exécution du programme. Les résultats sont plus pertinents qu’une méthode avec instrumentation car celle‐ci peut avoir un coût qui biaise les résultats. Elle permet aussi de lancer le profilage sur un programme qui s’exécute déjà. Malheureusement, GHC génère des programmes avec un modèle d’exécution bien différent de ceux des langages plus traditionnels, d’où la difficulté d’utiliser ces outils. La [page du wiki GHC sur DWARF](https://ghc.haskell.org/trac/ghc/wiki/DWARF/Status) détaille ces problématiques et les améliorations réalisées dans GHC 8.2. ## BackPack [BackPack](https://ghc.haskell.org/trac/ghc/wiki/Backpack) vise à proposer un système de modules plus puissant. On rappelle qu’en Haskell il existe une quantité impressionnante de types pouvant représenter une chaîne de caractères : - `String`, qui n’est autre qu’une liste chaînée de caractères Unicode (`[Char]`) ; celle‐ci est déconseillée pour la gestion de vraies chaînes de caractères du fait du coût en mémoire et des performances associées aux listes chaînées ; - `Text`, qui est une représentation compacte de chaînes Unicode ; performante, elle est cependant critiquée par son choix d’encodage interne — UTF-16 — du fait du surcoût en mémoire comparé à de l’UFT-8 ; ce type vient en version stricte et paresseuse ; - `ByteString`, qui est une représentation compacte de suite d’octets. Utilisée principalement pour les interactions binaires, elle vient en version stricte et paresseuse ; - les [Foundation](https://hackage.haskell.org/package/foundation) `String` qui se veulent une alternative au `Text` en utilisant le codage interne en UTF-8. Il en existe sûrement d’autres. Bref, c’est la jungle, car chaque type a son utilité en fonction de ses besoins en traitement correct des caractères, en traitement binaire, en évaluation paresseuse ou stricte. Avant BackPack, faire un module gérant les différents types de chaîne de caractères disponibles dans Haskell revenait à devoir faire autant de modules que d’implémentations à gérer... Bonjour la duplication de code. Grâce à BackPack, les modules peuvent être paramétrés par une interface de type, permettant une implémentation générique du module. C’est très similaire aux [modules paramétrés d’OCaml](https://caml.inria.fr/pub/docs/oreilly-book/html/book-ora132.html). ## Stratégie de dérivation Haskell propose un mécanisme de dérivation de comportement automatique. Par exemple : ```haskell data Vector = Vector { x :: Float, y :: Float, z :: Float } deriving (Show, Eq) ``` Crée une classe `Vector`, représentant un triplet de flottants. La clause `deriving` permet au compilateur d’écrire automatiquement les fonctions d’affichage des égalités, par exemple : ```haskell>>> v = Vector 1 2 3>>> v Vector {x = 1.0, y = 2.0, z = 3.0}>>> v2 = Vector 4 5 6>>> v == v2 False>>> v == v True ``` On peut aussi imaginer dériver automatiquement les comportements de séralisation, _hash_, conversion avec JSON... Ce mécanisme a évolué au cours de la vie de Haskell, au départ il permettait de ne dériver que certains comportements fixes proposés par le compilateur. Ensuite, de nouveaux comportements ont été ajoutés. Puis, il est devenu possible pour un utilisateur de proposer son propre système pour dériver automatiquement des comportements. Du fait de la profusion de mécanismes de dérivation, certains cas sont devenus ambigus. GHC 8.2 fait un peu le ménage en proposant `DerivingStrategies` qui permet de choisir explicitement la stratégie à utiliser. [Cet article résume le problème et démontre la solution](https://ryanglscott.github.io/2017/04/12/improvements-to-deriving-in-ghc-82/). ## Amélioration du typage dynamique Haskell est un langage au typage statique. À ce titre, il prend en charge bien évidemment la notion de typage dynamique par le biais du module `Data.Dynamic`. On peut encapsuler n’importe quel type dans un type `Dynamic`. Mais, pour le récupérer, il faudra explicitement fournir le bon type : ```haskell Prelude Data.Dynamic> a = toDyn "Hello" Prelude Data.Dynamic> b = toDyn True Prelude Data.Dynamic> :type a a :: Dynamic Prelude Data.Dynamic> :type b b :: Dynamic Prelude Data.Dynamic> (fromDynamic a) :: Maybe String Just "Hello" Prelude Data.Dynamic> (fromDynamic a) :: Maybe Bool Nothing Prelude Data.Dynamic> (fromDynamic b) :: Maybe String Nothing Prelude Data.Dynamic> (fromDynamic b) :: Maybe Bool Just True ``` GHC 8.2 apporte l’implémentation du papier [_A reflection on types_](https://www.seas.upenn.edu/~sweirich/papers/wadlerfest2016.pdf) de Simon Peyton Jones, Stephanie Weirich, Richard A. Eisenberg et Dimitrios Vytiniotis, détaillé dans une [vidéo de SPJ](https://www.youtube.com/watch?v=k5sxhU65dHg). Ces changements ne seront pas forcément visibles pour un utilisateur final, mais ils simplifient et sécurisent l’implémentation de bibliothèques comme `Dynamic` en remplaçant un bricolage (un _cast_) par une opération garantie par le compilateur. ## Overloaded record fields La situation des `record`, c.‐à‐d. des structures avec des champs nommés, [n’est pas parfaite en Haskell](http://nikita-volkov.github.io/record/). Depuis GHC 8.0, beaucoup de travail est fait à ce sujet, notamment avec l’arrivée des extensions suivantes : - [DuplicateRecordField](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#duplicate-record-fields), qui permet de définir dans le même module deux types avec des noms de champs égaux ; - [OverloadedLabels](https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#overloaded-labels), qui permet de définir des étiquettes, syntaxiquement `#foo` qui seront surchargées en fonction du type. GHC 8.2 va un peu plus loin et propose la classe [`HasField`](https://downloads.haskell.org/~ghc/8.2.1/docs/html/users_guide/glasgow_exts.html#record-field-selector-polymorphism) qui permet d’extraire un champ d’un `record` de façon polymorphique. Par exemple, `getField @"x" v` permet d’extraire le champ `x` de `v` quel que soit le type de `v`. Notez que GHC 8.2 est incompatible avec le code de `OverloadedLabels` de GHC 8.2 et qu’il faudra adapter son code. ## Un meilleur support du polymorphisme « levity » _Cf._ [Richard A. Eisenberg — _Levity Polymorphism_](https://www.youtube.com/watch?v=lSJwXZ7vWBw) (en anglais). En Haskell (et dans de nombreux autres langages), il existe des objets « boxés » et des objets non « boxés ». Par exemple, un `Int#` est représenté par un entier machine sur 64 bits, alors qu’un `Int` est représenté par un pointeur de constructeur, que l’on pourrait assimiler à une étiquette de type, et par un `Int#` ; tout cela pour deux fois plus de mémoire. Généralement, on n’utilise pas les types « non boxés » et le compilateur optimise cela comme il peut. Cependant, quand les performances sont attendues, il peut être intéressant d’écrire du code sur des types non « boxés » et, à un moment, il devient important de pouvoir écrire des fonctions polymorphiques travaillant aussi bien sur des types « boxés » que « non boxés ». ## Exhaustivité des patterns Le nouveau pragma [COMPLETE](https://downloads.haskell.org/~ghc/8.2.1/docs/html/users_guide/glasgow_exts.html?highlight=pragma#complete-pragmas) permet de forcer l’exhaustivité des motifs (_patterns_). Par défaut, chaque type crée aussi un _pattern_ utilisable pour construire et déconstruire le type : ```haskell data Point = Point Float Float deriving (Show) isOrigin (Point 0 0) = True isOrigin _ = False getX (Point x _) = x translate (Point x y) (dx,dy) = Point (x + dx) (y + dy) ``` Il est cependant possible de créer ses propres _patterns_ pour créer de nouvelles façons de construire et déconstruire ses types : ```haskell {-# LANGUAGE ViewPatterns #-} {-# LANGUAGE PatternSynonyms #-} pattern PolarPoint r phi <- (\ (Point x y) -> (sqrt (x*x+y*y), atan2 y x)) -> (r, phi) where PolarPoint r phi = Point (r * cos phi) (r * sin phi ``` Ici, je crée un _pattern_ `PolarPoint r phi` qui représente un point en coordonnées polaires. On peut s’en servir autant pour créer que pour détruire : ```haskell> PolarPoint 10 0 Point 10.0 0.0> PolarPoint 10 (pi / 2) Point (-4.371139e-7) 10.0> PolarPoint r angle = Point 2 2> r 2.8284271247461903> angle 0.7853981633974483 ``` Cependant, avant GHC 8.2, le compilateur râlait sur les fonctions utilisant ce _pattern_ : ```haskell -- | Retourne `True` si le point est plus loin qu'un rayon de 10 isFar :: Point -> Bool isFar (PolarPoint r _) = r> 10 ``` ``` Polar.hs:18:1: warning: [-Wincomplete-patterns] Pattern match(es) are non-exhaustive In an equation for ‘isFar’: Patterns not matched: _ | 18 | isFar (PolarPoint r _) = r> 10 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ``` En effet, le compilateur ne peut pas prouver tous les cas de figure des _patterns_, ce qui se traduit par beaucoup de faux positifs dans lesquels les vrais positifs sont cachés, rendant cette fonctionnalité peu utilisable. Depuis GHC 8.2, l’utilisateur peut fournir une directive de compilation `{-# COMPLETE PolarPoint #-}` permettant de spécifier que le _pattern_ `PolarPoint` couvre tous les cas de figure. # L’écosystème [Stack](https://docs.haskellstack.org/en/stable/README/) est un outil de gestion de dépendance pour Haskell. Il peut sous‐traiter à [Nix](https://nixos.org/nix/) pour les dépendances non Haskell, permettant ainsi la compilation dans un environnement contrôlé. Pour faire simple, un programme Haskell peut être compilé en une seule ligne de commande `stack build` sans devoir se préoccuper de l’installation de dépendances. L’utilisation de [Stackage](https://www.stackage.org/) qui fournit des instantanés de paquets versionnés garantit qu’un programme compilé il y a quelques mois le sera dans les mêmes conditions. Stack a gagné dernièrement une nouvelle commande `script` qui permet d’exécuter un programme Haskell comme un script en installant les dépendances listées dans le script lui‐même. Nous verrons un cas d’usage dans la section d’exemples plus loin. # Le futur Haskell (et GHC) évolue constamment. Cette section liste quelques projets excitants pour l’avenir. ## Typage dépendant [Cet article de blog détaille le travail sur les types dépendants en Haskell](https://typesandkinds.wordpress.com/2016/07/24/dependent-types-in-haskell-progress-report/) qui devrait arriver plus ou moins rapidement, l’auteur parlant de GHC 8.6. Les [types dépendants](https://fr.wikipedia.org/wiki/Type_d%C3%A9pendant) permettent d’enrichir le système de types afin de garantir plus de choses. Pour expliciter cela, nous allons traiter un petit problème de multiplication de matrices. Soit un type `Matrice` qui pourrait être représenté comme suit en Haskell : ```haskell data Matrice = Matrice { nLignes :: Int, nColonnes :: Int, donnée :: (... structure non détaillée ...) } ``` [Le produit matriciel](https://fr.wikipedia.org/wiki/Produit_matriciel) est une opération classique d’algèbre qui s’effectue entre deux matrices et renvoie une nouvelle matrice. Cependant, il y a une contrainte entre la taille des matrices d’entrée et le résultat de la matrice de sortie. Une matrice de taille `(m, n)` ne peut être multipliée que par une matrice de taille `(n, p)` pour obtenir une matrice de taille `(m, p)`. Bien souvent, cette contrainte est assurée par une vérification à l’exécution : ```haskell produitMatrice :: Matrice -> Matrice -> Matrice produitMatrice (Matrice m n dataA) (Matrice n' p dataB) | n == n' = (Matrice m p (... calcul non détaillé ...)) | otherwise = error "Pas les bonnes tailles" ``` Il est à l’heure actuelle possible en Haskell de spécifier ces tailles directement dans le type, de la manière suivante : ```haskell data Matrice nLignes nColonnes = Matrice { donnée :: (... structure non détaillée ...) } ``` Donnant ainsi le produit suivant : ```haskell produitMatrice :: Matrice m n -> Matrice n p -> Matrice m p produitMatrice (Matrice dataA) (Matrice dataB) = Matrice (... calcul non détaillé ...) ``` Cette approche force le compilateur à vérifier que les tailles de nos matrices sont correctes pendant la compilation, ce qui supprime totalement toute une classe d’erreur à l’exécution. Justin Le a rédigé une très bonne série d’articles qui traite de l’état actuel du typage dépendant en Haskell en implémentant [un réseau de neurones multi‐couche](https://blog.jle.im/entry/practical-dependent-types-in-haskell-1.html). Une des limitations de cette approche est que les tailles des réseaux de neurones ou des matrices de notre exemple, doivent être connues intégralement à la compilation, empêchant l’écriture d’un outil pouvant charger depuis le disque une matrice de taille quelconque. Dans la seconde partie de son article, Justin Le parle de ce problème et montre les solutions existantes pour réaliser ce type d’opérations. On peut donc écrire une fonction de chargement de matrice depuis le disque avec des tailles statiques : ```haskell chargerMatrice :: Filename -> IO (Matrice n m) ``` Je ne détaillerai pas la solution, c’est, à mon avis, lourd et rébarbatif. Le travaille sur le typage dépendant qui est en cours dans GHC vise à simplifier cela. ## Typage linéaire Le typage linéaire devrait arriver sous peu dans GHC. Ce travail est en grande partie réalisé par une société française, [tweag.io](http://www.tweag.io/). Donc, cocorico ! ;) On note [leur publication sur les types linéaires](https://github.com/tweag/linear-types/releases/download/v2.0/hlt.pdf) et leur [premier article de Blog expliquant le projet](http://www.tweag.io/posts/2017-03-13-linear-types.html). Les types linéaires apportent à la fois un potentiel de performance, de sécurité et de modélisation. Pour simplifier, c’est une façon de dire qu’une valeur ne sera utilisée qu’une et une seule fois. Je ne rentrerai pas dans les détails de son implémentation en Haskell puisque c’est tout nouveau et que les choses peuvent beaucoup bouger, je me contenterai de donner deux exemples de problématiques que les types linéaires peuvent résoudre. ### Sécurité et modélisation [Cet article de blog](http://www.tweag.io/posts/2017-08-03-linear-typestates.html) détaille ce point, l’exemple qui suit est similaire. Quand on utilise des _sockets_, on peut faire de nombreuses actions en fonction de l’état du socket, qui sont résumées dans le graphe suivant : ``` Non initialisée ——bind()—→ En attente ——listen()—→ En écoute \ / \ accept() \——connect()—→ Envoyer / Recevoir <==========/ ``` Ici, une flèche simple représente un changement d’état du _socket_. Et la flèche `<===` représente le fait que la fonction `accept()` retourne un nouveau _socket_ directement dans l’état d’envoi et de réception de message. À chaque état est associé une liste d’opérations possibles. Par exemple, `recv()` et `send()` ne sont possibles que dans l’état de transfert. On pourrait modéliser ces états par des types différents : ```haskell data NonInitSocket = NonInitSocket Int data AttenteSocket = AttenteSocket Int data EcouteSocket = EcouteSocket Int data TransfertSocket = TransfertSocket Int ``` L’`Int` représentant le descripteur de fichier bas niveau du _socket_. Et à cela s’ajoutent des fonctions : ```haskell create :: IO NonInitSocket bind :: NonInitSocket -> Addr -> IO AttenteSocket listen :: AttenteSocket -> Int -> IO EcouteSocket connect :: NonInitSocket -> Addr -> IO TransfertSocket accept :: EcouteSocket -> IO TransfertSocket send :: TransfertSocket -> String -> IO () recv :: TransfertSocket -> Int -> IO String closeEcoute :: EcouteSocket -> IO () closeTransfert :: TransfertSocket -> IO () ``` Les `IO` matérialisant que chacune de ces fonctions réalise des effets de bord. Et, là, tout est beau dans le meilleur des mondes, on ne peut pas exécuter une fonction qui n’a pas de sens sur un _socket_ qui n’est pas dans le bon état. Sauf que si !... Observons le code suivant : ```haskell fonctionBugée = do s <- create attenteSocket <- bind s anAddr ecouteSocket <- listen attenteSocket 3 ... transfertSocket <- connect s anotherAddr ``` Ici l’on voit qu’on se sert deux fois de `s`, ce qui est faux puisque à ce moment le descripteur de _socket_ qui est stocké dans `s` correspond à une _socket_ en état d’écoute. On remarque aussi qu’on ne ferme jamais nos _sockets_. Les types linéaires peuvent ici nous sauver en refusant à la compilation le second usage de `s`. De même, la compilation pourrait refuser ce code qui n’utilise pas `ecouteSocket` ni `transfertSocket`, la seule façon de les utiliser étant de les fermer. Ainsi, les types linéaires permettent de détecter à la compilation des mauvais usages de ressources. ### Performance Haskell est un langage où l’on maximise la non‐mutabilité. Ainsi, on va préférer créer une nouvelle structure de données plutôt que d’en modifier une. Haskell tire profit de cette non‐mutabilité pour partager au maximum les parties communes entre plusieurs données. S’il existe des [structures non mutables performantes](https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf) (à lire, c'est très instructif), ce n’est pas le cas de toutes les structures. Ainsi, un vecteur n’est pas du tout adapté à la non‐mutabilité, car il faut recopier intégralement celui‐ci en cas de modification d’une unique case. Une des premières choses qui vient à l’esprit c’est que si personne d’autre n’utilise la donnée, on pourrait la modifier sans scrupule. Cette information n’est cependant pas connue à la compilation et serait trop coûteuse à calculer lors de l’exécution. Les types linéaires permettent de garantir que notre valeur ne sera utilisée qu’une seule fois, sous peine de refuser de compiler. Cette information en main, une bibliothèque pourra proposer des fonctions optimisées avec mutation pour remplacer les fonctions qui copient. Et cela sans faire apparaître de mutation dans le code utilisateur. # Exemple de Haskell : le dîner des philosophes La fin de cette dépêche est consacrée à un exemple de résolution d’un problème en Haskell. Merci à [_jiehong_](http://linuxfr.org/users/jiehong) de m’avoir soufflé l’idée de présenter la mémoire transactionnelle. ## Introduction Nous allons nous intéresser au problème des [philosophes](https://fr.wikipedia.org/wiki/D%C3%AEner_des_philosophes). Il s’agit d’un problème classique de [programmation concurrente](https://fr.wikipedia.org/wiki/Programmation_concurrente) qui brille autant par son énoncé trivial que par le nombre de problématiques d’implémentation qu’il soulève. À une table *ronde* d’un restaurant italien, des philosophes discutent en mangeant. Chaque philosophe a à sa droite et sa gauche une fourchette, qu’il partage avec son voisin de droite et de gauche. Pour manger, un philosophe doit prendre les deux fourchettes, il pourra ensuite manger pendant un laps de temps variable, puis reposera les fourchettes. Cependant, en prenant les fourchettes, il empêche son voisin de droite et de gauche de manger. Le problème est donc d’ordonnancer le repas des philosophes en évitant des situations d’[interblocage](https://fr.wikipedia.org/wiki/Interblocage) courantes telles que : - des « _dead locks_ », où un philosophe sera en attente d’une fourchette prise par un autre philosophe lui‐même en attente d’une autre fourchette. On peut imaginer une situation où tous les philosophes sont bloqués de cette manière ; - des « _live locks_ », où les fourchettes changent de main en permanence, mais sans que personne ne puisse manger. Une solution simple à ce problème consiste en l’usage d’un verrou global. Chaque philosophe désirant manger va tenter de prendre le verrou global et, une fois celui‐ci verrouillé, il prendra ses deux fourchettes si et seulement si les deux sont disponibles. Cette solution est triviale à implémenter, mais ne passe pas à l’échelle, car elle séquence toutes les opérations de prise ou de dépose des fourchettes. Il faut donc employer une stratégie plus fine. Il existe de nombreuses solutions à ce problème, nombreuses sont complexes à implémenter et imposent une grande rigueur. Par exemple, en s’assurant de ne toujours prendre et rendre les verrous que dans le même ordre, on s’assure théoriquement qu’il n’y a pas d’interblocage. Par exemple, si un philosophe s’assure de prendre la fourchette gauche avant la droite. Mais, il y a le cas du dernier philosophe de la table qui doit prendre sa fourchette droite avant la gauche, la fourchette droite étant en fait la première de la table. Bref, vous l’aurez compris, ce n’est pas trivial. Dans cet exemple de code Haskell, nous présenterons une solution utilisant les primitives de *STM*, _Software Transactional Memory_, [Mémoire transactionnelle logicielle](https://fr.wikipedia.org/wiki/M%C3%A9moire_transactionnelle_logicielle). Cette technique offre de nombreux avantages, en termes de facilité de programmation et de composition du code. ## STM et Haskell En Haskell, nous pouvons créer une zone de mémoire modifiable par STM grâce à la fonction `newTMVarIO`. Cette zone contiendra ou pas une valeur. Grâce à `putTMVar`, nous pouvons mettre une valeur dans la zone. `takeTMVar` vide la zone et renvoie la valeur. Cette opération est bloquante. Nous pouvons représenter une fourchette par une `TMVar ()` contenant simplement un `()`. On aurait pu mettre n’importe quoi dedans, la seule chose nous intéressant étant de savoir si la valeur est dedans ou non. On peut composer ensemble un certain nombre d’opérations sur des `TMVar` et exécuter atomiquement le bloc grâce à `atomically`. Les STM divergent d’une stratégie plus classique à base de mutex par : - des opérations sont composables. On peut créer une action plus complexe à partir d’un ensemble de petits actions. Bien évidemment, plus l’action est complexe, plus la transaction a des chances d’échouer et de devoir recommencer ; - les opérations atomiques ont une granularité très fine car elles ne « verrouillent » que les variables impliquées dans la transaction. Ainsi, on peut facilement imaginer modifier une structure de données en plusieurs points par plusieurs fils d’exécution sans qu’il n’y ait de conflit. ## Exemple d’exécution Pour exécuter le programme, nous ferons appel à `stack` qui, après installation des bibliothèques nécessaires, va utiliser GHC en mode interprété, ce programme ne demandant pas de performance particulière. Le programme prend en paramètre le nombre de philosophes autour de la table. Chaque philosophe est nommé par une lettre. Quand celui‐ci commence à manger, la console affichera une lettre majuscule, quand il s’arrête, elle affichera une lettre minuscule. Les philosophes essayent de manger pendant 30 secondes. Avec deux philosophes, on est en situation où seulement l’un peut manger : ``` $ ./Philosopher.hs 2 AaBbAaBbAaBbAaBbA ``` Avec trois philosophes, seulement un peut manger : ``` $ ./Philosopher.hs 3 AaBbCcAaBbCcA ``` Avec quatre, c’est plus intéressant. Les philosophes ne peuvent manger ensemble que par groupes de 2, c’est‐à‐dire soit A et C, soit B et D. Ainsi, pour changer de groupe, il faut que les deux philosophes du même groupe arrêtent de manger en même temps. L’implémentation fait manger les philosophes pendant un temps aléatoire compris entre 0 et 2 secondes et ils se reposent pendant 100 ms avant de recommencer à essayer de prendre les fourchettes. Ainsi, le moment ou les deux philosophes d’un groupe viennent de s’arrêter de manger ensemble est assez rare : ``` $ ./Philosopher.hs 4 ACcCaAcCaAcCaAcCcaBDdDdDbBdDbdACcaBDdDbB # ----------------| ICI ``` Avec plusieurs philosophes, c’est bien plus drôle : ``` $ ./Philosopher.hs 10 ACEGIcgCGcCgGcaBiJjIeDgFbAiHdChIfGEgGeiEcICaAcCaAeiEIicICgGiIaAeEeEcCgGiIaAeEicICcCigH ``` ## Implémentation Cette section détaille une solution en Haskell à ce problème. Des paragraphes d’explications s’intercalent entre les blocs de code qui peuvent être copiés‐collés en tant que tels dans un fichier `Philosopher.hs`. ### Prélude On commence par le [_Shebang_](https://en.wikipedia.org/wiki/Shebang_(Unix)) décrivant l’interpréteur à utiliser. Ici `stack`. La ligne suivante liste les paquetages nécessaires pour ce fichier, à savoir `stm` pour l’usage de la mémoire transactionnelle, `random` pour générer des nombres aléatoires et `optparse-generic` pour lire la ligne de commande. ```haskell #!/usr/bin/env stack -- stack script --resolver lts-9.0 --package "stm random optparse-generic" {-# LANGUAGE OverloadedStrings #-} ``` Viennent l’importation des modules nécessaires pour notre code. J’ai choisi d’importer de façon qualifiée chaque fonction afin que le lecteur puisse connaître sa provenance. ```haskell module Main where import Control.Monad (replicateM, forever) import Control.Concurrent.STM (TMVar, putTMVar, takeTMVar, newTMVarIO, STM, atomically) import Control.Concurrent (forkIO, killThread, threadDelay, ThreadId) import System.Random (randomRIO) import Data.Char (toLower) import Options.Generic (getRecord) ``` ### Fourchettes La gestion des fourchettes. En premier lieu, le type `Fork` qui représente une fourchette. Celui‐ci contient un `TMVar ()`, c’est‐à‐dire un conteneur STM qui peut contenir un `()`, c’est‐à‐dire « rien ». Mais on peut connaître la présence ou l’absence de ce rien et c’est ce qui nous intéressera. ```haskell data Fork = Fork (TMVar ()) ``` `takeFork` et `releaseFork` respectivement prennent et reposent une fourchette. `takeFork` sera bloquant. On note au type des fonctions que ces opérations s’effectuent sous le contrôle de la `STM`. ```haskell -- | Prend une fourchette. Bloquant. takeFork :: Fork -> STM () takeFork (Fork var) = takeTMVar var -- | Repose une fourchette. Non Bloquant. releaseFork :: Fork -> STM () releaseFork (Fork var) = putTMVar var () ``` La création d’une fourchette avec `mkFork` implique la création d’une `TMVar` avec `newTMVarIO` : ```haskell -- | Crée une fourchette mkFork :: IO Fork mkFork = do var <- newTMVarIO () pure (Fork var) ``` Ce morceau de code implique énormément de choses sur Haskell, nous allons nous y attarder un moment. Le type de la fonction est `IO Fork`, c’est une action d’entrée‐sortie qui renvoie une fourchette. La première ligne réalise une action `newTMVarIO ()` qui crée une nouvelle `TMVar` contenant un `()`. Celle‐ci est stockée dans `var`. Il ne s’agit pas d’une égalité, mais d’une affectation ; ici, `var` est bien le résultat de l’exécution d’une action et non pas une égalité qui serait représentée avec le signe `=`. La valeur de retour de la fonction est `Fork var` c’est‐à‐dire la `TMVar` encapsulée dans le type `Fork`. Cette expression `Fork var`, de type `Fork`, ne représente pas une action à effet de bord, ainsi elle ne peut pas être la valeur finale de la fonction (qui est de type `IO Fork`). Il faut donc encapsuler de nouveau le `Fork` dans une `IO` et cela est fait grâce à la fonction `pure`. Ne vous en formalisez pas trop, c’est surprenant au début, mais on s’y fait vite. La création de `n` fourchettes se fait grâce à la fonction `replicateM` qui réplique l’action `mkFork` et donc renvoie une liste de `Fork`. Le `M` ici signifie que l’on réplique une action. Sinon, on pourrait écrire `replicate 3 True == [True, True, True]` sans le `M` car `True` n’est pas une action. ```haskell -- | `mkForks n` crée une liste de `n` `Fork` disponibles mkForks :: Int -> IO [Fork] mkForks n = replicateM n mkFork ``` ### Philosophes Un philosophe est simplement une structure qui comprend un nom, sous la forme d’un `Char`, et deux `Fork` : ```haskell -- | Un `Philosopher` est représenté par son nom et deux fourchettes data Philosopher = Philosopher Char Fork Fork ``` La création de plusieurs philosophes se servant de fourchettes est la suivante : ```haskell -- | Crée le nombre de philosophes associés aux fourchettes mkPhilosophers :: [Fork] -> [Philosopher] mkPhilosophers forks = zipWith3 Philosopher ['A'..] forks (last forks : forks) ``` Cette fonction est très concise mais complexe. Nous avons une liste de fourchettes (pour simplifier `[fork0, fork1, fork2]`) et nous voulons créer une liste de philosophes, chacun associé à une lettre et à deux fourchettes. On aimerait la liste suivante : `[Philosopher 'A' fork0 fork2, Philosopher 'B' fork1 fork0, Philosopher 'C' fork2 fork1]`. Un motif apparaît, on voit qu’il s’agit de la fonction `Philosopher` appliquée à 3 arguments pris respectivement dans 3 listes distinctes grâce à la fonction `zipWith3` : - `['A', 'B', 'C']`, que nous représentons ici avec la liste infinie `['A' .. ]` ; - `[fork0, fork1, fork2]`, c’est tout simplement `forks` ; - `[fork2, fork0, fork1]`, qui est ici `(last forks : forks)`. Cela fonctionne car `zipWith3` ne consomme qu’en fonction de la longueur de la liste la plus courte. ### Vie d’un philosophe Une étape de la vie d’un philosophe est une fonction assez longue, mais peu complexe. La prise et la relâche des fourchettes est réalisée dans un bloc `atomically`, le reste n’étant que des attentes et un peu d’affichage. ```haskell -- | Un `Philosopher` essaye de manger. runPhilosopher :: Philosopher -> IO () runPhilosopher (Philosopher name forkA forkB) = do -- Prends les fourchettes de façon atomique, garantie par STM atomically $ do takeFork forkA takeFork forkB -- Affiche son nom en majuscules putChar name -- Mange pendant un temps aléatoire compris entre 0 et 2 secondes time <- randomRIO (0, 2 * 1000 * 1000) threadDelay time -- Affiche la fin du repas (nom en minuscule) putChar (toLower name) -- Repose les fourchettes de façon atomique atomically $ do releaseFork forkA releaseFork forkB -- Attend avant de recommencer pendant 100 ms threadDelay (1000 * 100) ``` ### forkPhilosopher Cette fonction, pour un philosophe donné `p`, crée un [_green thread_](https://en.wikipedia.org/wiki/Green_threads) qui exécute en boucle infinie grâce à `forever` une étape de la vie de notre philosophe. ```haskell forkPhilosopher :: Philosopher -> IO ThreadId forkPhilosopher p = forkIO (forever (runPhilosopher p)) ``` ### main Le main contient un peu de logique pour lire la ligne de commande et crée les philosophes : ```haskell main :: IO () main = do -- Lit le nombre de philosophes sur la ligne de commande nPhilosopher <- getRecord "Philosopher" -- Crée les fourchettes et les philosophes forks <- mkForks nPhilosopher let philosophers = mkPhilosophers forks -- Crée les fils d’exécution par philosophe tIds <- mapM forkPhilosopher philosophers -- Attend 10 secondes et tue les fils d’exécution threadDelay (1000 * 1000 * 10) mapM_ killThread tIds ``` Quelques points à discuter dans cette fonction `main`. En premier lieu, j’utilise `getRecord` pour lire la ligne de commande. Cette fonction, du module `optparse-generic`, est capable de créer toute seule une interface ligne de commande en fonction du type de retour demandé, ici un `Int`, en gérant automatiquement la lecture de la ligne de commande, la validation des arguments et l’affichage de l’aide, si nécessaire. Cela m’a économisé trois lignes de logique pour lire les arguments, vérifier qu’il y en avait au moins un et le convertir en `Int`, et afficher une erreur le cas échéant. Ce n’était pas forcement nécessaire dans ce contexte, mais cela devient extraordinaire avec une interface plus complexe impliquant des arguments optionnels, des drapeaux booléens, ou autres. La création des fourchettes est une opération avec effets de bord, d’où l’affectation du résultat avec `<-`. La création des philosophes, elle, ne réalise pas d’effet de bord, c’est une fonction pure, d’où l’égalité `=` qui signifie réellement que `philosophers` est sémantiquement équivalent à `mkPhilosopher forks` dans les lignes qui suivent. C’est un outil de compréhension de code que je trouve plaisant. Pour finir, la création des fils d’exécution se fait avec `mapM`, qui va appliquer la fonction `forkPhilosopher` à chaque philosophe et renvoyer l’identifiant du fil d’exécution créé. # Conclusion GHC 8.2 c’est sympa, il y a plein de nouvelles fonctionnalités qui rendent heureux un développeur Haskell régulier. Mais, soyons réaliste, ce ne sont pas ces nouvelles fonctionnalités qui vont vous motiver à utiliser Haskell, c’est pourquoi j’ai essayé de présenter un cas concret d’utilisation du langage sur un problème assez classique d’algorithmie.

AltStyle によって変換されたページ (->オリジナル) /