Sommaire
Présentation d’Haskell et de GHC
Haskell est un langage de programmation fonctionnelle. Je vous invite à lire la dépêche de la sortie de GHC 8.0.1 qui réalise une présentation plus complète du langage.
Une reformulation de la page de présentation du langage 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 et dans cette vidéo de Simon Peyton Jones : Compiling without continuations.
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 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 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 permet de représenter plus efficacement les types somme (c.‐à‐d. les enums).
NUMA
Des optimisations pour les architectures NUMA 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 est utilisé par de nombreux outils de debug ou d'analyse de performance comme gdb, valgrind, perf. L'amélioration de sa gestion permet, entre autres, une meilleure prise en charge de ces outils.
Pour information, perf est un outil qui permet de faire du profiling 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érent instants.
Cette méthode de profiling 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 profiling 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 détaille ces problématiques et les améliorations réalisées dans GHC 8.2.
BackPack
BackPack vise à proposer un système de module 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 vraie chaîne 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 de l'encodage interne — utf-16 — du fait du surcoût en mémoire comparé à de l'utf-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
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 de OCaml.
Stratégie de dérivation
Haskell propose un mécanisme de dérivation de comportement automatique. Par exemple :
data Vector = Vector {
x :: Float,
y :: Float,
z :: Float
} deriving (Show, Eq)
Crée une classe Vector, représentant un triplet de flottant. La clause deriving permet au compilateur d'écrire automatiquement les fonctions d'affichage des égalités, par exemple :
>>> 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. Puis 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.
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 :
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 de Simon Peyton Jones, Stephanie Weirich, Richard A. Eisenberg et Dimitrios Vytiniotis, détaillé dans cette vidéo de SPJ. 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 hack (un cast) par une opération garantie par le compilateur.
Overloaded record fields
La situation des record, i.e. des structures avec des champs nommés, n'est pas parfaite en Haskell.
Depuis GHC 8.0, beaucoup de travail est fait à ce sujet, notamment avec l'arrivée des extensions :
-
DuplicateRecordField qui permet de définir dans le même module deux types avec des noms de champs égaux.
-
OverloadedLabels qui permet de définir des labels, syntaxiquement
#foo qui seront surchargés en fonction du type.
GHC 8.2 va un peu plus loin et propose la classe HasField qui permet d'extraire un champ de 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"
Richard A. Eisenberg - Levity Polymorphism (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 à un tag 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 permet de forcer l'exhaustivité des patterns.
Par défaut, chaque type crée aussi un pattern utilisable pour construire / déconstruire le type :
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 / déconstruire ses types :
{-# 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éconstruire :
> 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 :
-- | 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 est un outil de gestion de dépendance pour Haskell. Il peut sous-traiter à 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 qui fournit des snapshots de packages 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 qui devrait arriver plus ou moins rapidement, l'auteur parlant de GHC 8.6.
Les Types dépendants permettent d'enrichir le système de type 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 :
data Matrice = Matrice {
nLignes :: Int,
nColonnes :: Int,
donnée :: (... structure non détaillée ...)
}
Le 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ées 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 :
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, tel que :
data Matrice nLignes nColonnes = Matrice {
donnée :: (... structure non détaillée ...)
}
Donnant ainsi le produit suivant :
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 neurone multi couches.
Une des limitations de cette approche est que les tailles, des réseaux de neurone ou des matrices de notre exemple, doivent être connue 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 :
chargerMatrice :: Filename -> IO (Matrice n m)
Je ne détaillerais 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, donc cocorico ;) On note leur publication sur les types linéaires et leur premier article de Blog expliquant le projet.
Les types linéaires apportent à la fois un potentiel de performance et de sécurité / 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 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 de la 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 de la socket. Et la flèche === représente le fait que la fonction accept retourne une nouvelle 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 :
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 de la socket.
Et à cela s'ajoute des fonctions :
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 une socket qui n'est pas dans le bon état.
Sauf que si… Observons le code suivant :
fonctionBugée = do
s <- create
attenteSocket <- bind s anAddr
ecouteSocket <- listen attenteSocket 3
...
transfertSocket <- connect s anotherAddr
Ici 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ù 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 (à 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 d'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 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. Il s'agit d'un problème classique de 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 courantes tel que :
- des « dead lock », où un philosophe sera en attente d'une fourchette prise par une autre philosophe lui-même en attente d'une autre fourchette. On peut imaginer une situation ou tous les philosophes sont bloqués de cette manière.
- des « live lock », 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 impose une grande rigueur. Par exemple en s'assurant de ne prendre et rendre les verrous toujours 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. 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 pas.
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'une 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 threads 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 affiche une lettre majuscule, quand celui-ci 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 de 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 décrivant interpréteur à utiliser. Ici stack. La ligne suivante liste les packages 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.
#!/usr/bin/env stack
-- stack script --resolver lts-9.0 --package "stm random optparse-generic"
{-# LANGUAGE OverloadedStrings #-}
Viennent l'import des modules nécessaires pour notre code. J'ai choisi d'importer de façon qualifier chaque fonction afin que le lecteur puisse connaitre sa provenance.
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 connaitre la présence ou l'absence de ce rien et c'est ce qui nous intéressera.
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.
-- | 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 :
-- | 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, est cela est fait grâce à la fonction pure.
Ne vous en formaliser pas trop, c'est surprenant au début, mais on s'y fait vite.
La création de n fourchettes se fait grace à la fonction replicateM qui réplique l'action mkFork et donc renvoie une liste de Fork. le M ici signifie que 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.
-- | `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.
-- | Un `Philosopher` est représenté par son nom et deux fourchettes
data Philosopher = Philosopher Char Fork Fork
La création de plusieurs philosophes, en se servant de fourchettes est la suivante :
-- | 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ée 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 grace à 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.
-- | 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 qui exécute en boucle infinie grâce à forever une étape de la vie de notre philosophe.
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.
main :: IO ()
main = do
-- Lit le nombre de philosophe 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 threads par philosophe
tIds <- mapM forkPhilosopher philosophers
-- Attend 10 secondes et tue les threads
threadDelay (1000 * 1000 * 10)
mapM_
