Sortie de GHC 8.2.1

Posté par Guillaum (site web personnel) le 07 août 2017 à 11:52. Édité par Davy Defaud, Benoît Sibaud, Snark, BAud, Yves Bourguignon, ZeroHeure, gipoisson, palm123, Nÿco, Sytoka Modon, Pierre Jarillon et octachron. Modéré par patrick_g. Licence CC By‑SA.

Étiquettes :

août

2017

Une nouvelle version majeure du compilateur GHC pour Haskell est sortie.

GHC

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.

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 débogage 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 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 détaille ces problématiques et les améliorations réalisées dans GHC 8.2.

BackPack

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 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.

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 flottants. 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. 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.

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 une 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 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.

Depuis GHC 8.0, beaucoup de travail est fait à ce sujet, notamment avec l’arrivée des extensions suivantes :

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 étiquettes, syntaxiquement #foo qui seront surchargées en fonction du type.

GHC 8.2 va un peu plus loin et propose la classe HasField 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 (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 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 :

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 :

{-# 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 :

> 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 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 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 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 :

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é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 :

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 :

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 neurones multi‐couche.

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 :

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. 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, 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 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 :

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 :

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 :

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 (à 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 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 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. 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 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.

#!/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.

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.

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 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.

-- | `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 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é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.

-- | 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 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.

Aller plus loin

DLFP : Sortie de GHC 8.0.2 et une petite histoire de typage statique (250 clics)
[ANNOUNCE] GHC 8.2.1 release candidate 1 (80 clics)
[ANNOUNCE] GHC 8.2.1 release candidate 2 (78 clics)
[ANNOUNCE] GHC 8.2.1 release candidate 3 available (72 clics)
[ANNOUNCE] GHC 8.2.1 available (83 clics)
Notes de version de la 8.2.1 (117 clics)

# Merci pour la dépêche

Posté par karchnu le 07 août 2017 à 13:10. Évalué à 2.

Merci pour avoir pris le temps d'écrire aussi bien une dépêche sur GHC. J'espère que ça intéressera des gens à essayer le langage. :)
# Super dépêche mais 2 remarques

Posté par nokomprendo (site web personnel) le 07 août 2017 à 20:46. Évalué à 3.
Merci pour cette dépêche très intéressante. Deux petites remarques :
- Haskell est un super langage mais ce n'est pas non plus la solution merveilleuse à tous les problèmes du monde. Un lien intéressant sur les domaines d'application d'Haskell : https://github.com/Gabriel439/post-rfc/blob/master/sotu.md.
- Concernant Nix, on peut aussi l'utiliser indépendamment de stack/cabal, pour se faire très rapidement un environnement de développement, par exemple via un fichier shell.nix contenant :
```
with import <nixpkgs> {};
with pkgs; stdenv.mkDerivation {
    name = "my-haskell-env";
    buildInputs = [ 
       (haskell.packages.ghc802.ghcWithPackages (ps: with ps; [
            # liste des modules à installer
            split 
            parsec3
        ]))
    ];
}
```
- [^] # Re: Super dépêche mais 2 remarques
  
  Posté par Guillaum (site web personnel) le 07 août 2017 à 22:17. Évalué à 2.
  
  Merci pour la remarque sur Nix. En effet, Haskell n'est pas le langage universel, mais je pense qu'il n'y en a pas ;) Par exemple, dans mon métier j'ai un ENORME besoin de performance, et Haskell n'est pas, à l'heure actuel, capable de rivaliser avec du code C++ tunné au millimètre près.
# Haskell pour les nuls

Posté par Denis Bernard (site web personnel) le 07 août 2017 à 21:28. Évalué à 2. Dernière modification le 07 août 2017 à 22:30.
Bon, je ne connaissais jusqu'ici Haskell que de nom.
J'ai installé la version 8.2.1 sur mon ordi qui est sous Gentoo. J'ai fait le classique "hello world!" en créant un source (hello.hs) contenant :
main = putStrLn "Hello, World!"

À la ligne de commande, j'ai fait :
ghc hello.hs
Ce qui m'a généré 3 fichiers :
- hello (2 293 936 octets)
- hello.hi (858 octets)
- hello.o (3576 octets)
La commande file dit que que hello.o est :
hello.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped, with debug_info

Pour hello.hi :
hello.hi: data

Et pour l'exécutable hello lui-même :
hello: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, not stripped, with debug_info

L'exécutable me semble énorme. Alors je fais un strip hello mais il fait encore 749 072 octets.

J'ai passé pas mal de temps sur les tutoriels et autre pages Wikipédia. Ce qui n'a fait que m'embrouiller un peu plus. Alors ma question : est-ce que GHC est un pur compilateur faisant du vrai code natif ou bien une bidouille embarquant un interpréteur ?
- [^] # Re: Haskell pour les nuls
  
  Posté par Denis Bernard (site web personnel) le 07 août 2017 à 21:38. Évalué à 1.
  
  Pour le modérateur, une typo : changer le mot "embarquent" de la dernière phrase par "embarquant". Merci !
  - [^] # Re: Haskell pour les nuls
    
    Posté par ZeroHeure le 07 août 2017 à 22:30. Évalué à 2.
    
    c'est corrigé
    
    "La liberté est à l'homme ce que les ailes sont à l'oiseau" Jean-Pierre Rosnay
- [^] # Re: Haskell pour les nuls
  
  Posté par Guillaum (site web personnel) le 07 août 2017 à 22:24. Évalué à 5.
  
  GHC est autant un interpréteur qu'un compilateur. Dans ton cas tu as compilé ton code Haskell en code natif. Cependant le code Haskell compilé avec GHC vient avec un "runtime" qui gère, entre autre, les entrée / sorties, l'allocation de mémoire, le ramasse miette, le parallélisme, …, et presque tous ces points sont nécessaires même pour le plut petit programme.
  
  Ce qui disqualifie Haskell dans des environnement aux ressources limités, mais dans un contexte plus classique, Haskell (et GHC) sont capable de générer du code natif assez performant. Dans mes applications habituelles, je suis, dans le pire des cas, 3x plus lent que du code de calcul C++ pure, mais souvent je suis dans les 10/15% plus lent. À voir si c'est suffisant ou pas.
  
  Ceci étant dis, si tu veux continuer ton expérience Haskell, je te conseille de regarde "stack" qui s'occupera de la compilation / strip / gestion des dépendances pour toi.
  - [^] # Re: Haskell pour les nuls
    
    Posté par Denis Bernard (site web personnel) le 07 août 2017 à 22:52. Évalué à 1.
    
    OK, merci pour ta réponse claire ! Elle confirme mon impression première… Mon intérêt portait sur la possibilité de programmation mixte. À ce que j'ai compris de mes lectures, les anciennes version de GHC avaient la possibilité de générer un source en langage C mais ce ne serait plus le cas aujourd'hui. J'ai vu un tutoriel où, dans le cas d'un main en C, la procédure écrite en GHC doit au préalable être initialisée (ce qui me faisait pencher pour un interpréteur embarqué).
    
    Il en découle qu'il ne semble pas avoir d'avenir pour GHC pour jouer avec des interfaces graphiques (GTK ou QT) qui sont le plus souvent écrites en C/C++ . Reste, peut-être, les Widgets interprétées ?
    
    Concernant GHC en tant que substitut au C++ dans le domaine du calcul intensif, je m'interroge : quitte à s'investir intellectuellement dans l'apprentissage d'un nouveau langage, pourquoi ne pas préférer Fortran (version F2015, pas F77 !) ?
    
    Ceci étant, concernant la galère que représente la chaîne de compilation classique (autotools) du C, ou pire de Fortran, GHC est apparemment infiniment plus confortable.
    
    En définitive, la fabrication d'un exécutable et son paquetage est une punition injuste avec les anciens langages. Le processus standard actuel est une survivance de l'époque où les ordinateurs étaient si faibles qu'il mettaient un temps fou à compiler. D'où les Makefiles actuels (et leur cortège d'utilitaires atroces) qui n'ont plus de raison d'être avec les machines d'aujourd'hui. Alors oui, qu'est-ce qui est le plus simple : créer un nouveau langage avec un processus de compilation/paquetage indolore ou bien dépoussiérer l'existant ?
    - [^] # Re: Haskell pour les nuls
      
      Posté par Guillaum (site web personnel) le 08 août 2017 à 00:38. Évalué à 6.
      
      Tu peux facilement utiliser un FFI pour aller appeler n'importe quelle fonction d'un autre langage. Haskell est même "premier de sa classe" dans ce domaine avec de superbes libraires de FFI pour s'interfacer avec du C, du C++ (là j'ai des doutes), du java, du python, du fortran, du R, et j'en passe. L'interface avec du C est aussi trivial que de taper ton code C au milieu de ton code Haskell avec le module inline-C (regarde les exemples).
      
      J'ai vu un tutoriel où, dans le cas d'un main en C, la procédure écrite en GHC doit au préalable être initialisée (ce qui me faisait pencher pour un interpréteur embarqué).
      
      Il faut initialiser entre autre le ramasse miette pour que ton code Haskell puisse allouer / désallouer de la mémoire. Après ce serait un interpréteur cela ne me choquerais pas tant que cela quand on vois les performances dingues qu'un interpréteur JIT peut donner (il n'y a qu'à voir Java ou PyPy). Bref, je pense qu'en dehors de certains contextes limités en mémoire, il ne faut pas cracher sur les interpréteurs. (Mais bon, GHC fait tout de même du code natif).
      
      Il en découle qu'il ne semble pas avoir d'avenir pour GHC pour jouer avec des interfaces graphiques (GTK ou QT) qui sont le plus souvent écrites en C/C++ .
      
      Il y a des bindings Haskell pour GTK, Qt, wxwidget, fltk, OpenGL, … et j'en passe. J'ai peu de retour à faire, (je n'aime pas faire des interfaces graphiques, alors le peu que je fais je le garde pour le boulot et là c'est en LUA ;), mais le code gtk en Haskell que j'ai vu avait l'air plutôt acceptable.
      
      Bien que les librairies d'interface graphique soient souvent écrites en C ou C++, c'est souvent un autre langage qui tape dedans, python, lua, …
      
      Concernant GHC en tant que substitut au C++ dans le domaine du calcul intensif, je m'interroge : quitte à s'investir intellectuellement dans l'apprentissage d'un nouveau langage, pourquoi ne pas préférer Fortran (version F2015, pas F77 !) ?
      
      Du peu que je connais de Fortran, j'ai l'impression que Haskell à une syntaxe et un système de type bien plus agréable à utiliser, mais je peu me tromper ;)
      - [^] # Re: Haskell pour les nuls
        
        Posté par Denis Bernard (site web personnel) le 08 août 2017 à 15:28. Évalué à 1.
        
        Merci pour ces précisions ! Effectivement les FFI sont chose intéressante pour la programmation mixte. Ça existe maintenant en Fortran (blocs INTERFACE). Pas plus tard qu'il y a une semaine, je me suis amusé à jouer avec gettimeofday() de la libc (voir ici).
        
        Mon agacement au sujet des langages interprétés (que ce soit avec interpréteur externe ou runtime embarquée dans l'exécutable) est qu'ils font confusion entre les notions de programmation et de développement. Ayant biberonné avec Basic, j'ai eu à pâtir de cette ambiguïté et en définitive éprouvé des frustrations dès que l'on pousse le langage dans ses limites. Je pense qu'il est malhonnête de présenter un langage comme relevant de la programmation alors qu'il est définitivement limité au développement. Ou, pour parler plus clairement, si l'on souhaite étendre les fonctionnalités de base par modules à l'aide de ce même langage, on provoque des instabilités au delà d'un certain niveau d'imbrication des modules à l'intérieur des modules. Ce genre de choses se voit couramment en TeX/LaTeX. Ceci n'a pas trop d'importance pour quiconque ayant fait de longues études en informatique (car pouvant toujours se rabattre sur le langage C ou un assembleur). Mais, pour un hobbyiste de mon genre, quel temps perdu à apprendre un langage qui se révèle être une impasse !
        
        Du peu que je connais de Fortran, j'ai l'impression que Haskell a une syntaxe et un système de type bien plus agréable à utiliser, mais je peux me tromper ;)
        
        Le langage Fortran évolue à toute vitesse. Il est bien difficile de se faire une opinion sur des bases anciennes… Rien que l'introduction des modules (et tout récemment des sous-modules) change totalement la donne en génie logiciel. Mais on ne trouve que très peu de code lisible en ligne qui soit rédigé en Fortran moderne comme ici (un module pour les fichiers JSON).
        
        Ceci me fait prendre conscience qu'il serait opportun de rédiger une dépêche sur le Fortran moderne. Mais, clairement, je n'ai pas le niveau ! Cependant brosser un historique de ce langage sexagénaire, au travers d'une dépêche sur ce site, devrait être à ma portée.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Guillaum (site web personnel) le 08 août 2017 à 16:28. Évalué à 6.
        
        Mon agacement au sujet des langages interprétés (que ce soit avec interpréteur externe ou runtime embarquée dans l'exécutable) est qu'ils font confusion entre les notions de programmation et de développement.
        
        Puis-je te demander de développer un peu ? Je trouve que la différence entre langage interprété et compilé est de plus en plus faible. Chaque programme, quel que soit le langage qui a permis de le "compiler" embarque un "runtime" fournissant les fonctions de bases nécessaires à l’exécution d'un programme. Celui du C est minime, mais il existe. Celui du C++ est plus gros, mais reste raisonnable. Celui d'Haskell est bien plus gros, et cela est acceptable ou non en fonction du contexte, mais j'ai du mal à saisir ton point de vue.
        
        Ayant biberonné avec Basic, j'ai eu à pâtir de cette ambiguïté et en définitive éprouvé des frustrations dès que l'on pousse le langage dans ses limites. Je pense qu'il est malhonnête de présenter un langage comme relevant de la programmation alors qu'il est définitivement limité au développement.
        
        Tu peux développer encore ici la différence que tu fais entre "programmation" et "développement" ?
        
        Ou, pour parler plus clairement, si l'on souhaite étendre les fonctionnalités de base par modules à l'aide de ce même langage, on provoque des instabilités au delà d'un certain niveau d'imbrication des modules à l'intérieur des modules. Ce genre de choses se voit couramment en TeX/LaTeX. Ceci n'a pas trop d'importance pour quiconque ayant fait de longues études en informatique (car pouvant toujours se rabattre sur le langage C ou un assembleur). Mais, pour un hobbyiste de mon genre, quel temps perdu à apprendre un langage qui se révèle être une impasse !
        
        Personnellement, j'ai eu moins de surprises et de problèmes avec langages "interprétés" (Comme python, lua), ou avec de gros "runtime" (comme Haskell, Java (je ne sais pas trop ou mettre java, c'est interprété ou compilé ? ;)) qu'en C++, et pourtant je gagne ma vie en faisant du C++.
        
        Selon quels critères qualifies-tu un langage d'impasse ? Si tu te qualifies d'hobbyiste, je suis près à parier que n'importe quel langage (et implémentation) doit pouvoir convenir à ton besoin tant que tu n'as pas des problématiques d'embarqué ou de performance particulières.
        
        Ceci me fait prendre conscience qu'il serait opportun de rédiger une dépêche sur le Fortran moderne.
        
        Si tu te sens, commences dans l'espace de modération, d'autres suivront surement. Bon courage.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Benoît Sibaud (site web personnel) le 08 août 2017 à 16:44. Évalué à 3.
        
        Si tu te sens, commences dans l'espace de modération, d'autres suivront surement. Bon courage.
        
        Dans l'espace de rédaction.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Denis Bernard (site web personnel) le 08 août 2017 à 19:08. Évalué à 1.
        
        Concernant l'intérêt des interpréteurs, je n'ai rien n'a ajouter de plus de ce que dit Backus dans son papier The IBM Speedcoding system (Journal of the ACM, Volume 1, Issue 1, Janv 1954, pp. 4-6). Leur intérêt est évident. Et ils existent depuis plus longtemps que le premier langage de programmation jamais commercialisé par la même équipe du susdit.
        
        Cependant, malgré leur indéniable (et irremplaçable) utilité, les interpréteurs ont leurs limites. Car si une fonction est codable en soft, elle est tout aussi parfaitement codable en hard dans un CPU. Et là, la question des performances se pose. L'équipe qui a créé Speedcoding est la même qui a créé peu après Fortran : la technologie ayant permis de coder en dur une unité de calcul sur les flottants, il n'y avait plus de raison de continuer avec un interpréteur. Pour ceux qui ont connu les premiers PC d'avant les Pentium, ils étaient livrés avec un coprocesseur optionnel. Ceux qui n'avaient pas les sous choisissaient le modèle sans qui faisait tout aussi bien mais plus lentement car passant par un émulateur.
        
        Pour donner un exemple vécu et que j'ai développé sur ce site au travers plusieurs journaux : le cas d'un générateur de pages HTML pour un blog statique. Il en existe une multitude mais presque tous codés sous interpréteur. Quand on arrive à une certain nombre de billets de blog, le logiciel rame. La seule issue est de coder en natif. Donc, à un moment, il faut bien mettre les mains dans le cambouis. L'alternative existe : vous prenez WordPress, vous installez une base de donnée qu'il vous faudra maintenir, vous mettez PHP qu'il faudra bien mettre à jour de temps à autre et vous croisez les doigts pour que vous ne fassiez pas pirater. Personnellement, je me suis mis au Fortran pour la seule nécessité de développer un moteur de blog statique. Il est capable de générer une centaine de pages HTML là où WordPress en génère une seule pour le même laps de temps. Et mon moteur de blog n'est pas hackable car il ne réside pas sur le site Web. Et je n'ai pas besoin d'ingurgiter une dose massive de SQL et PHP pour savoir comment marche le bousin. Tout ça par la seule grâce d'un langage compilé. Mais j'aurais pu tout aussi bien opter pour ADA car mon passé en Basic me permettait un auto apprentissage des langages "verbeux". Je précise qu'à l'époque je ne connaissais pas de compilo Basic sous Linux et que je ne voulais plus entendre parler de Windows ni utiliser de Basic en mode interpréteur. Sur ce dernier point, j'ai été échaudé par le fait que l'interpréteur rattrapant assez facilement des erreurs d'écriture logicielle, et même fournissant des avertissements (cas du QBasic de MS) là où un compilo natif refuserait d'aller plus loin, on n'est pas assez rigoureux dans son codage. En natif, les erreurs détectées sont implacables ! Même si on ne les voit pas toutes de prime abord.
        
        À bon escient, les interpréteurs ont leur utilité. Là où il y a une dérive, c'est quand une organisation humaine (typiquement une université ou un industriel du logiciel) fait la promotion d'une nouvelle-machine-virtuelle-qui-va-bouleverser-la-planète c'est qu'elle entraîne dans ses filets une multitude de gens qui deviennent comme les adeptes d'une nouvelle religion. Le nombre de ces miroirs aux alouettes brisés ou encore scintillants est inouï.
        
        Concernant la distinction entre développement et programmation, elle me semble évidente ! Dans un cas on assemble des composants logiciels écrits par d'autres, dans l'autre on tape avec ses petits doigts sur le clavier pour fabriquer un par un lesdits composants. C'est la même différence qu'entre ouvrir une boite de conserve de petits pois et les réchauffer en 3 minutes ou les prendre à l'état cru, les écosser et attendre 3/4 d'heure que ça cuise. Au quotidien, j'opte pour la conserve. Mais je sais aussi le faire à l'ancienne ! Et je sais même aussi les faire pousser !
        
        Selon quels critères qualifies-tu un langage d'impasse
        
        Il est vrai que les langages interprétés sont au moins aussi fiables que ceux compilés. Mais, en "mode parano", leur avenir est suspendu au bon vouloir de soit un très petit comité (pas toujours ouvert sur la communauté), soit d'un industriel qui peut mettre la clé sous la porte du jour au lendemain. Et le miroir aux alouettes est alors brisé.
        
        Dans le cas d'un langage compilé le risque est mieux réparti. D'une part parce que tant que le CPU et la plateforme continue d'exister, la maintenance est possible même si son fournisseur disparaît. Et dans la mesure où il normalisé, il devient légal de créer un compilateur substitutif. Si une machine virtuelle, breveté ou sous licence, a une faille de sécu et qu'elle n'est plus maintenue c'est la mort du petit cheval.
        
        C'est, pour moi une première impasse. La seconde concerne la création de nouveaux composants logiciel en assemblant des composants de base. j'ai évoqué le cas du processeur de texte LaTeX où l'on l'empilement de macros peut produire des effets indésirables. Ah, j'aimerai avoir une connaissance a minima du JavaScript pour donner d'autres exemples illustrant les inconvénients de la stratification logicielle…
        
        [^] # Re: Haskell pour les nuls
        
        Posté par nokomprendo (site web personnel) le 08 août 2017 à 21:52. Évalué à 7.
        
        Salut. Je dois être idiot mais je trouve que ce que tu racontes n'a aucun sens. Juste un exemple :
        
        Personnellement, je me suis mis au Fortran pour la seule nécessité de développer un moteur de blog statique. Il est capable de générer une centaine de pages HTML là où WordPress en génère une seule pour le même laps de temps. Et mon moteur de blog n'est pas hackable car il ne réside pas sur le site Web. Et je n'ai pas besoin d'ingurgiter une dose massive de SQL et PHP pour savoir comment marche le bousin. Tout ça par la seule grâce d'un langage compilé.
        
        WordPress n'est pas un générateur de pages statiques, donc ce n'est pas comparable. De plus, les systèmes dynamiques utilisent généralement un cache qui évite d'avoir à recréer les pages.
        
        Le temps de génération des pages statiques n'a pas beaucoup d'importance. Prendre une 1s ou 1mn pour la mise à jour quotidienne d'un blog, ça ne change vraiment rien. Et là aussi, les générateurs statiques modernes ne recalculent que les pages qui ont changé.
        
        La "grâce d'un langage compilé" n'a aucun sens ici. Personnellement, je génère des docs statiques avec sphinx qui produit également les diagrammes UML, les graphes, le code formaté et les équations inclus dans ces docs; l'interpréteur python qui est utilisé pour cela n'a jamais été un problème (par contre bon courage pour coder un outils équivalent en fortran).
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Denis Bernard (site web personnel) le 08 août 2017 à 23:27. Évalué à -2.
        
        WordPress n'est pas un générateur de pages statiques, donc ce n'est pas comparable. De plus, les systèmes dynamiques utilisent généralement un cache qui évite d'avoir à recréer les pages.
        
        WordPress est archi dominant sur le marché des moteurs de blog. Si tu ne me crois pas, va sur le site de OVH (par exemple) et regarde combien de logiciels de blog il propose : tu as le choix entre WordPress et WordPress. Si on veut comparer un quelconque moteur de blog, le bon sens le plus élémentaire est de le faire par rapport à WordPress. Cependant la vérité oblige à dire qu'il n'est seulement en mode dynamique que pour la partie HTML. Les illustrations, elles, sont traitées comme les pages de blog statique. Autant dire, sur un blog banal, la partie générée par PHP-MySQL ne représente pas la majorité de la bande passante consommée. Concernant la mise en cache d'un blog généré dynamiquement, elle est tout aussi faisable (et même indiquée !) pour un blog en pages statiques.
        
        Le temps de génération des pages statiques n'a pas beaucoup d'importance. Prendre une 1s ou 1mn pour la mise à jour quotidienne d'un blog, ça ne change vraiment rien.
        
        Honnêtement, tiens-tu un blog que tu héberges toi-même ? Si oui, peux-tu me jurer que tu rédiges tes billets d'un façon si absolument parfaite que jamais tu ne ressentes la nécessité d'une correction ? Personnellement, je suis dans l'incapacité de rédiger ma copie sans de nombreux brouillons jetés à la corbeille. Dans ce cas, entre un logiciel qui prend une seconde et celui qui prend une minute ça fait une sacrée différence. Mais bon, si tu es un super écrivain, ça peut le faire. Ah, au fait, il est où ton blog ?
        
        Et là aussi, les générateurs statiques modernes ne recalculent que les pages qui ont changé.
        
        Ça, c'est une remarque pertinente ! Elle me met du baume au cœur à un point que tu ne peux pas imaginer… Je suis bien d'accord, absolument tous les blogs statiques que j'ai pu voir sont en mode page unique. C'est pour ça que j'ai créé mon propre moteur ! Avec le mien, les pages sont liées les unes aux autres. Ce qui veut dire que si l'on est sur une page, on peut cliquer sur celle qui précède ou qui suit. Ce qui veut dire qu'à chaque fois que l'on intercale une page, il faut générer au moins deux autres. Et si en plus on pousse le vice à proposer un menu pour retrouver un billet à une date donnée, il faut tenir à jour l'index des pages. Donc, le plus simple à coder est de tout regénérer. On peut faire une regénération partielle comme avec NanoBlogger autrefois. Mais, pour l'avoir vécu, c'est source de bien des soucis. Et comme si le vice précédent ne suffisait pas, je propose aussi une version imprimable de chaque billet. La double peine. Alors, crois-moi, Fortran est bon pour moi.
        
        La "grâce d'un langage compilé" n'a aucun sens ici. Personnellement, je génère des docs statiques avec sphinx qui produit également les diagrammes UML, les graphes, le code formaté et les équations inclus dans ces docs; l'interpréteur python qui est utilisé pour cela n'a jamais été un problème (par contre bon courage pour coder un outils équivalent en fortran).
        
        Absolument d'accord avec toi. Python bénéficie d'une somme considérable de modules en tout genre et c'est sa qualité première. (Peut-être même la seule ?). Mais le Fortran moderne est un tout autant un langage orienté objet et tout autant modulaire. La facilité à développer en Python vient surtout de son environnement : plus il y a de modules, de dépôts de source, d'outils en tout genre, plus c'est facile de créer de nouveaux modules. Partir from scratch est une toute autre affaire ! Pour Fortran, il n'existe guère que de vieilles bibliothèques scientifiques et quasiment aucun module écrit au 21ème siècle. Donc, rien que pour parser un fichier de configuration, une ligne de commande. Alors il faut agiter ses petits doigts sur le clavier. Mais bon, c'est ce que j'aime. Je ne suis pas payé pour, c'est pour le fun !
        
        [^] # Re: Haskell pour les nuls
        
        Posté par nokomprendo (site web personnel) le 09 août 2017 à 08:59. Évalué à 5.
        
        Mais bien sûr, les générateurs statiques comme Jekyll et autres ne sont pas capables de détecter les pages modifiées qu'il faut régénérer ni de mettre des liens entre les pages ou plusieurs billets par page. Et tant qu'on y est, ils n'autorisent que les voyelles dans les billets de blog ?
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Denis Bernard (site web personnel) le 09 août 2017 à 12:28. Évalué à -1.
        
        Le fil de discussion portait sur un langage de programmation précis et non pas sur les moteurs de blog. Incidemment la conversation a dérivée sur la vitesse à l'exécution d'un code Haskell. L'auteur de la dépêche disait :
        
        Haskell (et GHC) sont capable de générer du code natif assez performant. Dans mes applications habituelles, je suis, dans le pire des cas, 3x plus lent que du code de calcul C++ pure, mais souvent je suis dans les 10/15% plus lent.
        
        et, dans un autre commentaire :
        
        Si tu te qualifies d'hobbyiste, je suis près à parier que n'importe quel langage (et implémentation) doit pouvoir convenir à ton besoin tant que tu n'as pas des problématiques d'embarqué ou de performance particulières.
        
        À l'époque où j'ai débuté l'écriture de mon moteur de blog, il en existait déjà bien d'autres. Je participais à la traduction de l'un deux et c'est là que j'ai pris conscience qu'il ne passait pas l'échelle au-delà d'une centaine de billets postés. Aujourd'hui, avec les disques SSD et l'augmentation des performances globale des machines, il redevient utilisable. Ceci était le premier point.
        
        Le second point, était que l'on devait pouvoir poster un billet dans le cadre d'un voyage long et lointain depuis un cyber café sur une machine Windows. J'ai choisi de le rendre compatible avec Putty. Incidemment, la liaison pouvant être rompu, le logiciel devait pouvoir faire avec. Ceci impliquait d'abandonner la notion de session. Or opter pour une régénération partielle imposait un suivi de session.
        
        Le troisième point était que je voulais un onglet "archive" plus efficace que ce que l'on voit avec habituellement où l'on n'indexe les billets que par mois mais sans les classer au préalable par année. Au début ça le fait mais au bout de dix ans on a 120 mois. Je voulais en plus pouvoir faire un classement jour par jour dans un mois donné. (Ce n'est pas encore implémenté dans mon projet.)
        
        De tout ce qui précède, la solution la plus sûre était celle d'une régénération totale à chaque mise à jour. J'ai eu la colossale surprise, en testant les billets rapatriés depuis des blogs tenus depuis longtemps par de grands bavards, de voir que le temps mis à générer la totalité était ridiculement bas. Ce qui se passe est que l'on a des I/O massives et que passer par un interpréteur ça ralenti considérablement. Mais en natif, il m'est apparu que le surcout d'une génération totale comparée à une génération partielle était infime. Compte tenu de mon problème de ne pas pouvoir assumer un suivi de session ça tombait bien.
        
        Voilà la raison de mon entêtement au sujet des performance en vitesse. Reste un dernier point qui me fait lorgner ailleurs qu'avec Fortran : l'interface graphique. Sous Windows, on peut faire des fenêtres avec Fortran aisément mais pas aussi facilement sous Linux. Donc soit je mets à la programmation mixte soit je vais voir ailleurs. Je n'ai pas pris encore de décision.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Guillaum (site web personnel) le 09 août 2017 à 14:05. Évalué à 5.
        
        Le problème de la discussion que nous avons c'est que tu ne veux pas accepter qu'un interpreteur, ou un langage avec un gros runtime (comme Haskell) peut donner de très bonnes performances.
        
        Certains langages de haut niveau permettent d'exposer des optimisations qui ne sont pas possibles dans d'autres langages, comme la fusion en Haskell.
        
        D'autres langages interprétés, comme python, java, php, lua, javascript, utilisent la compilation à la volée pour générer à l’exécution du code natif performant. Cela marche assez bien.
        
        Alors oui, on ne battra surement jamais de l'assembleur optimisé à la main pour un problème précis par un spécialiste (bonjour le niveau du spécialiste), mais est-ce que cela vaut le coup ? Si avec un code robuste / portable / maintenable de 10 lignes tu fais "juste" 10% mois vite qu'un code de 200000 lignes non portable et que personne sans 4 PhD ne peux comprendre, est-ce que cela vaut le coup ?
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Denis Bernard (site web personnel) le 09 août 2017 à 17:12. Évalué à 1.
        
        En toute humilité je n'ai pas le niveau intellectuel suffisant pour avoir saisi, ne serait-ce que le sens général, du concept de fusion en Haskell à la lecture du lien. Certes l'exemple qui y est donné avec le module Data.Text me parle un peu plus car c'est pile dans le domaine que doit traiter un moteur de blog.
        
        Mais, à ce que je suppose, on n'est plus dans le domaine du langage de programmation mais dans celui de l'optimisation par le compilateur. En ce cas, quel que soit le langage compilable en natif la question se pose à l'identique. Alors, toujours si j'ai bien compris, les langages compilables permettent usuellement d'ajouter des directives de compilation ; ainsi en fortran où l'on peut déclarer une fonction comme étant "pure", "elemental" ou même "impure" (et aussi, maintenant, la gestion du parallélisme).
        
        Que Haskell soit tout à la fois un langage de programmation et un compilateur est une nouvelle donne. Et elle est intéressante car elle peut intégrer plus finement la phase d'optimisation. Le compilateur Fortran que j'utilise est GCC et suit à peu près le même processus que C dans le sens où il converti le source en Gimple puis en assembleur. Il s'en suit que l'on doit posséder de bonne base théorique en informatique pour produire un exécutable performant. Et ensuite c'est l'édition de lien et, là encore, le bagage intellectuel requis est assez lourd (du moins pour ma petite tête !). J'appréhende le jour où je devrai me plonger dans l'apprentissage du LTO…
        
        Le gros avantage des interpréteurs est qu'ils lissent toutes ces contingences puisqu'ils créent leur univers et donc les règles qui leur sont propre ; c'est excellent pour la portabilité d'un logiciel. A contrario, en natif, la compilation et l'édition doivent être ajustées à la machine.
        
        Donc, je suis (et je l'étais déjà avant) d'accord avec toi à 100% sur le fait qu'un langage interprété peu s'approcher de la performance globale d'un langage compilé non optimisé pour une machine donnée. Et je suis tout à fait conscient que l'optimisation "aux petits oignons" n'est guère portable et nécessite tout autant du temps et le bagage intellectuel adéquat. Et je suis pleinement d'accord qu'une perte de 10% de performance est acceptable et que c'est immensément compensé par la facilité de mise en production dans les délais les plus courts. Et je n'ignore pas non plus que absolument tous les exécutables sous Linux tournent sous l'interpréteur ELF…
        
        Là où j'ai un souci avec les interpréteurs en général (mais je n'ai jamais essayé Haskell donc je n'ai pas d'opinion à son sujet) c'est quand on a à générer un très grand nombre de fichiers en lecture / écriture. En ce cas l'interpréteur doit sortir de son monde intérieur pour se tourner vers le système d'exploitation et il me semble bien que c'est une situation où les performances s'effondrent. (Là encore, je suis un modeste autodidacte et peut-être que je dis des sottises.) Alors oui, la parade consiste à charger en mémoire vive lesdits fichiers et les recracher en bloc après traitement. Mais ce n'est pas toujours possible s'ils sont très volumineux et nombreux. En ce cas, on tombe dans un traitement séquentiel par lot et la performance tombe à cause du double traitement des I/O (une fois dans l'interpréteur et l'autre dans l'appel système sous-jacent).
        
        Dans le cas de mon moteur de blog, je me suis fixé comme règle que le nombre de fichiers de données traitables ne doit être limité que par le système de fichier. Ou, à tout le moins, de générer les billets de blog (stockés en fichiers plats) sur la base d'un post par jour pendant 30 ans. Ce qui fait dans les 10950 fichiers individuels pour les données. Et je fais mes tests sur cette base en générant un blog où toutes les pages contiennent la version HTML de la GPL. Sachant qu'un billet de blog a sa déclinaison en version imprimable, qu'il y a les pages d'indexation année par année et mois par mois, on arrive à nombre de fichiers à générer conséquent. Autre règle que je me suis fixé : une empreinte mémoire minimale. aussi n'ai-je en mémoire globale durant le traitement que les métadonnées des billets limitées aux dates et titres.
        
        Ceci étant dit, je le répète, je n'ai pas d'opinion sur Haskell en particulier et je suis dans le flou le plus total quant à la performance des interpréteurs en lectures/écritures massives. Je ne sais même pas s'il est procédé des essais comparatifs sur des PC familiaux.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Guillaum (site web personnel) le 09 août 2017 à 23:40. Évalué à 6.
        
        En toute humilité je n'ai pas le niveau intellectuel suffisant pour avoir saisi, ne serait-ce que le sens général, du concept de fusion en Haskell […]
        
        C'est un mécanisme qui permet de supprimer des opérations intermédiaires lors d'un calcul. Ainsi un calcul décrit avec de nombreuses structures de donnée temporaires peut au final ne rien allouer.
        
        Que Haskell soit tout à la fois un langage de programmation et un compilateur est une nouvelle donne.
        
        Pour différents langages, il existe différents moyen de faire exécuter le programme par un processeur. On peut interpréter ce code, ou le compiler en natif pour la machine ciblée. Pour de nombreux langage, il existe autant d’interpréteur que de compilateur. Il existe des interpréteurs Haskell et des compilateurs Haskell, il existe des interpréteurs C et des compilateurs C. En fait, tous les langages qui ont un frontend pour LLVM ont un interpréteur et un compilateur qui s'appelle LLVM. Ainsi, il existe des interpréteurs pour C, C++, Fortran, …
        
        Le gros avantage des interpréteurs est qu'ils lissent toutes ces contingences puisqu'ils créent leur univers et donc les règles qui leur sont propre ;
        
        Je ne comprend rien là.
        
        où j'ai un souci avec les interpréteurs en général (mais je n'ai jamais essayé Haskell donc je n'ai pas d'opinion à son sujet)
        
        Tu as bien compris que Haskell n'est qu'un langage qui peut être compilé ou interprété en fonction des besoins ?
        
        c'est quand on a à générer un très grand nombre de fichiers en lecture / écriture. En ce cas l'interpréteur doit sortir de son monde intérieur pour se tourner vers le système d'exploitation et il me semble bien que c'est une situation où les performances s'effondrent.
        
        Quand tu lis un fichier, que ce soit en python, en Haskell, ou en C, ton dénominateur commun c'est l'appel système et à peu de choses près, tes performances dépendent de cet appel système.
        
        En ce cas, on tombe dans un traitement séquentiel par lot et la performance tombe à cause du double traitement des I/O (une fois dans l'interpréteur et l'autre dans l'appel système sous-jacent).
        
        Mais l’interpréteur ne fait RIEN de plus que faire un appel système. Il y a des fois une surcouche pour réaliser l'appel, mais celle-ci ne coûte souvent presque rien comparé au coût de l'appel système.
        
        Tu as des benchmark à l'appui pour ce que tu dis ? Je serais vraiment interessé.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Denis Bernard (site web personnel) le 10 août 2017 à 14:39. Évalué à 1.
        
        Tu as des benchmark à l'appui pour ce que tu dis ? Je serais vraiment interessé.
        
        Non, je n'ai rien sous la main aujourd'hui. Mes évaluations datent de tant d'années… En plus comme le matériel évolue (surtout avec l'arrivée des SSD) tout est absolument à refaire. J'ai, de toute façon, besoin de faire des tests tant sur ma machine que sur celle de l'hébergeur de mes blog statiques.
        
        Aussi ai-je créé sur GitHub un banc de test GPL_Torture.
        
        J'y mettrai le source Fortran d'un test qui se passera en deux temps :
        
        Mise en mémoire de la version texte de la licence GPL-v3 puis création de n fichiers texte identiques et dont le nommage sera 1.txt, 2.txt, 3.txt … n.txt. Le temps de création de ces fichiers sera un test en écriture.
        
        Lecture des fichiers texte créés, un par un, et ajout des balises HTML pour en faire des pages HTML dotées d'un titre reprennant le n° de fichier, d'un menu avec les liens "home - prev - next -last", et le texte de la licence elle-même encadrée par les balises PRE. Leur nommage sera 1.html, 2.html, 3html … n.html . Ce sera donc un test en lecture - écriture.
        
        L'intérêt de la chose, outre de voir les capacités de son système, est que l'on peut zipper les fichiers HTML et les uploader chez l'hébergeur. Ainsi on peut voir la latence de son prestataire.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par nokomprendo (site web personnel) le 10 août 2017 à 18:28. Évalué à 1.
        
        Ça me fait penser à un générateur d'albums photo que j'avais codé pour tester différents langages : https://github.com/nokomprendo/gen_album. C'est du code vieux et moche que j'aurais honte de relire aujourd'hui mais ça fonctionnait. Je ne l'avais pas codé en fortran cependant…
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Guillaum (site web personnel) le 10 août 2017 à 18:38. Évalué à 2.
        
        Cool, vas y, je jouerais avec ;) Je suis près à parier une bière sur le résultat ;)
        
        [^] # Re: Haskell pour les nuls
        
        Posté par nokomprendo (site web personnel) le 10 août 2017 à 19:07. Évalué à 2. Dernière modification le 10 août 2017 à 19:09.
        
        J'ai dû faire du fortran une fois dans ma vie pour modifier un programme et il m'a effectivement fallu un certain nombre de bières pour m'en remettre… Pour le générateur d'albums, il y a des appels à convert (imagemagick) via la fonction system pour redimensionner les photos. Donc que le générateur soit écrit en assembleur ou en Ruby interprété par un webservice hébergé sur Mars, ça ne changera pas grand chose…
        
        Pour le GPL_torture, je suis impatient de tester également.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par GuieA_7 (site web personnel) le 10 août 2017 à 20:39. Évalué à 6.
        
        tous les exécutables sous Linux tournent sous l'interpréteur ELF…
        
        ELF est un format de fichiers exécutables (ou bibliothèques dynamiques) binaire, qui sont chargés en mémoires pour être exécutés par le processeur. Pas d'interprétation là dedans.
        
        Tu as tendance à considérer les performances comme quelque chose d'absolu (tel langage est plus performant que tel autre), mais en fait c'est plus complexe. Fortran a été pensé pour le calcul de vecteurs/matrices, et a donc une sémantique adaptée, que les compilateurs vont savoir exploiter (SIMD et compagnie) ; mais pour certaines problématiques ses qualités vont être inutiles (pas/peu de matrices/vecteurs).
        
        Par exemple sur ce premier benchmark Fortran est premier, mais sur ce second benchmark il est derrière java/Go/C# (il est possible que le code Fortran soit mauvais, mais on devra s'en contenter si personne ne l'améliore).
        
        [^] # Re: Haskell pour les nuls
        
        Posté par djano le 13 août 2017 à 10:03. Évalué à 3.
        
        Je vois que tu tires beaucoup de conclusion de ces moteurs de blogs. Je n'ai pas regardé le codecode (et je ne le ferai jamais). Tous les problèmes que tu décris semblent venir d'un problème algorithmique. Les performances intrinsèques du langage (interprété vs. compilé) me semble secondaires pour ce cas d'utilisation. Autrement dit, puisque les IO dominent le temps CPU, un langage interprété doit être capable de faire aussi bien qu'un langage compilé.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par djano le 13 août 2017 à 10:07. Évalué à 2.
        
        Quand YouTube a été racheté par Google, le code était implémenté en Python (je ne sais pas ce qu'il en est aujourd'hui). Car les performances de Python n'importent pas lorsque le programme doit attendre que les I/Os se fassent.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par Denis Bernard (site web personnel) le 13 août 2017 à 16:14. Évalué à -5. Dernière modification le 13 août 2017 à 16:18.
        
        Autrement dit, puisque les IO dominent le temps CPU, un langage interprété doit être capable de faire aussi bien qu'un langage compilé
        
        Nous sommes au cœur du sujet : "(…) un langage interprété doit faire aussi bien qu'un langage compilé".
        
        L'informatique est-elle une science ou une techno ?
        
        Dans le premier cas, est-ce une science spéculative. ou bien une science expérimentale ? Pour le premier, nos écoles et nos instituts en tous genres regorgent d'enseignants très bavard sur le sujet. Dans le second, on trouve beaucoup moins de bavards.
        
        En seconde hypothèse, avons nous une alternative carrément différente avec les logiciels disponibles à la vente en matière de langage de programmation ? Ainsi, y a-t-il des interfaces graphiques natives écrites autrement qu'avec C/C++ ? Avons-nous des suites bureautiques écrites autrement qu'avec C/C++ ? Et ainsi de suite.
        
        Alors reste la presse spécialisée. Qui reste très consensuelle. Et si la vérité établie ne collait pas à la réalité ? Et si les langages de programmation vedette n'étaient que daube ? Tant qu'on n'a pas essayé, c'est la bouteille à l'encre.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par GuieA_7 (site web personnel) le 13 août 2017 à 20:20. Évalué à 8.
        
        Avons-nous des suites bureautiques écrites autrement qu'avec C/C++ ?
        
        Une bonne partie des fonctionnalités de LibreOffice sont implémentées en Java et Python (Python remplace peu à peu Java).
        
        Le moteur de rendu (en C++ donc) n'est pas IO bound, donc je ne vois pas le rapport avec ce à quoi tu réponds (à savoir: pour du IO bound, c'est grosso-modo pareil).
        
        Tu fustiges la presse mais tu fais toi-même un bien mauvais travail d'investigation.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par nokomprendo (site web personnel) le 13 août 2017 à 20:34. Évalué à 5.
        
        @Denis Bernard : Sérieusement, tu devrais arrêter avec tes messages. Non seulement, c'est de la philosophie de comptoir à 2 balles réchauffée plusieurs fois mais en plus ça n'a aucun rapport avec la dépêche. Quant à tes généralités méprisantes et infondées sur les enseignants et sur la presse, ce n'était vraiment pas nécessaire.
        
        [^] # Re: Haskell pour les nuls
        
        Posté par djano le 14 août 2017 à 08:00. Évalué à 3.
        
        Tu surinterprète un choix de mots.
        Quand au reste de ton commentaire, tu pars en vrille.
- [^] # Re: Haskell pour les nuls
  
  Posté par Frédéric Blanc le 08 août 2017 à 19:44. Évalué à 5.
  
  À mon avis, cette entrée sur stackoverflow répondra à votre problème de surpoids (exemple d'une appli graphique passant de 13Mo à 124ko après liage dynamique aux bibliothèques au lieu d'un liage statique par défaut, et qui sont au final tombés à 84ko une fois dépouillé des derniers éléments de débug).
  - [^] # Re: Haskell pour les nuls
    
    Posté par Denis Bernard (site web personnel) le 08 août 2017 à 20:06. Évalué à 1.
    
    Merci de l'info. Elle remet Haskell dans ma liste des langages à étudier lors des longues soirées d'hiver !
  - [^] # Re: Haskell pour les nuls
    
    Posté par Guillaum (site web personnel) le 08 août 2017 à 22:04. Évalué à 2.
    
    Merci, je viens d'apprendre que on pouvait linker le RTS en dynamic ;)
# Quelques erreurs (mineures) dans le programme des philosophes

Posté par lancelotsix le 07 août 2017 à 22:57. Évalué à 4.
Tout d’abord, merci pour cette dépêche très bien construite et qui me fait regretter de ne pas utiliser plus ce langage.

Il y a une typo dans les imports, c’est Options.Generic, non Option.Gereric (notez le s).

Ensuite, la signature de la fonction forkPhilosopher ne correspond pas à ce que fait la fonction. Le type de forkIO est IO () -> IO ThreadId et non IO () -> IO (). La signature de forkPhilosopher doit donc être la suivante:
```
forkPhilosopher :: Philosopher -> IO ThreadId
forkPhilosopher p = forkIO (forever (runPhilosopher p))
```
Pour que ceci fonctionne, il faut également importer ThreadId depuis Control.Concurrent :
```
import Control.Concurrent (forkIO, killThread, threadDelay, ThreadId)
```
Une fois ces petite ajustements faits, ça marche très bien !
- [^] # Re: Quelques erreurs (mineures) dans le programme des philosophes
  
  Posté par Benoît Sibaud (site web personnel) le 07 août 2017 à 23:14. Évalué à 3.
  
  Corrigé, merci.
- [^] # Re: Quelques erreurs (mineures) dans le programme des philosophes
  
  Posté par Guillaum (site web personnel) le 08 août 2017 à 00:45. Évalué à 3.
  Bonnes remarques. Il s'agit de petits changements de dernière minute que je n'ai pas testé dans le fichier original. Honte sur moi.
  
  Pour la petite histoire, j'ai remplacé dans le main tIds <- mapM_ (forkIO . forever . runPhilosopher) philosophers par tIds <- mapM_ forkPhilosopher philosophers afin de simplifier la compréhension et ne pas devoir introduire / expliquer l'opérateur (.) ou une lambda ;)
  
  Pour Options.Generic, j'ai tout simplement remplacé un gros :
```
args <- getArgs
let nPhilosopher = case args of
   [] -> error "Vous devez fournir un argument"
   (x:_) -> case readMaybe x of
                Nothing -> error "Cela doit étre un int"
                Just i -> i
```
  Par nPhilosopher <- getRecord "bla bla bla".
  
  Cela m'apprendra ;)
  
  PS: à quand un compilateur dans linuxfr qui vérifie le sens des article, le code, et la grammaire ? ;) J'en aurais eu bien besoin. J'en profite pour remercier tous ceux qui ont fait un travail de relecture, sans eux cette daipaich auré aitè plu dur a lir. Merci.
# Structures non mutables performantes

Posté par chimrod (site web personnel) le 08 août 2017 à 14:42. Évalué à 3.

Je suis surpris de voir mentionner Okasaki ici. Son ouvrage est certes très instructif pour un développeur de langage fonctionnel (encore que écrit en standard ML, plus très utilisé aujourd'hui), il est complètement inutile dans le cas d'Haskell qui réalise l'évaluation paresseuse par défaut.

Sur le plan pratique, la plupart des langages offres des structures de données avec évaluation paresseuses par défaut dans la librairie de base, ce qui réserve la lecture du livre à ceux qui souhaitent avoir une connaissance théorique du sujet, tout en sachant qu'ils n'auront jamais l'occasion de le mettre en pratique dans la vie de tous les jours.

Ça n'enlève rien de l'intérêt qu'on peut avoir pour cette lecture, mais il faut vraiment aimer l'informatique théorique :)
- [^] # Re: Structures non mutables performantes
  
  Posté par Guillaum (site web personnel) le 08 août 2017 à 16:09. Évalué à 4.
  
  Okasaki […] il est complètement inutile dans le cas d'Haskell qui réalise l'évaluation paresseuse par défaut.
  
  Je ne suis pas forcement d'accord, la lecture du livre (j'ai lié sa thèse dans la dépêche, le livre est une version restructurée de celle-ci) m'a permis de comprendre les problématiques d'analyse de complexité amortie de ces structures dans un contexte paresseux, ce qui est carrément applicable à Haskell. Si je ne m'abuse, le livre fourni en annexe une version (datée) en Haskell de tous les codes.
  
  Cependant je suis d'accord avec toi qu'il s'agit d'une lecture purement théorique, peu sont les informaticiens qui auront à implémenter une structure de donnée (qu'elle soit mutable ou non, paresseuse ou non) étant donné la qualité de celles qui existent déjà dans les librairies accessibles dans tout langage. De plus cette lecture est totalement dépassé dans le sens où dans la vraie vie il y a d'autres problèmes (typiquement le cache) qui entrent en jeu dans les performances d'une structure de donnée. D'ailleurs je cherche encore une ressource accessible traitant de façon pertinente de l’implémentation de différentes structures de donnée (lazy ou non / mutable ou non) efficace sur des architectures de CPU modernes.
  
  J'ai voulu cependant introduire un peu le concept et fournir une bonne ressource car je trouve que on néglige trop souvent les structures de donnée dans l'apprentissage de l'informatique, et on néglige encore plus les structures non mutables qui offrent des propriétés très intéressantes.
  - [^] # Re: Structures non mutables performantes
    
    Posté par chimrod (site web personnel) le 08 août 2017 à 18:21. Évalué à 2.
    
    Je pense que les structures de données font partie des sujets qui sont oubliés dès que l'on a terminé sa formation et que l'on commence sa vie de développeur (-: . Mais je suis d'accord avec toi, ça fait du bien de revenir de temps en temps aux structures de base, ne serait-ce parce que les même les langages fonctionnels évoluent, mais pas forcément les structures de base. La mode est maintenant de tout typer, voire surtyper, (via des types fantômes et des GADTs), il est parfois nécessaire de réécrire des structures (en OCaml par exemple, l'arbre binaire fourni par la librairie standard ne permet pas de stocker des clefs paramétrées).
    
    D'une manière plus générale, la première chose que je mettrai entre les mains d'un développeur qui veut se lancer dans la programmation fonctionnelle ne serait pas les structures de données, mais plutôt les function pattern (par analogie avec les design pattern de la POO). Surtout que ces fonctions commencent à transpirer hors du monde fonctionnel (par exemple on peut citer les architecture MapReduce qui sont utilisées par des gens qui n'ont jamais fait de programmation fonctionnelle de leur vie).
    
    Il est dommage qu'il n'existe pas un équivalent au Typeclassopedia qui soit générique, la page du wiki est trop orientée Haskell, et risque de décourager quelqu'un qui ne connaît pas la syntaxe, pourtant il s'agit pour moi d'une mine d'information qui peut être utilisée dans un cadre beaucoup plus élargi.
  - [^] # Re: Structures non mutables performantes
    
    Posté par kantien le 09 août 2017 à 18:29. Évalué à 3.
    J'ai voulu cependant introduire un peu le concept et fournir une bonne ressource car je trouve que on néglige trop souvent les structures de donnée dans l'apprentissage de l'informatique, et on néglige encore plus les structures non mutables qui offrent des propriétés très intéressantes.
    
    C'est dommage que les structures persistantes soient négligées : la persistance, c'est le bien ! :-)
    
    Dans leur ouvrage Apprendre à programmer avec OCaml, Sylvain Cochon et Jean-Christophe Filliâtre consacrent un paragraphe sur l'utilité et les avantages de la persistance :
    
    Les intérêts pratiques de la persistance sont multiples. De manière immédiate, on comprend qu'elle facilite la lecture du code et sa correction. En effet, on peut alors raisonner sur les valeurs manipulées par le programme en termes « mathématiques », puisqu'elles sont immuables, de manière équationnelle et sans même se soucier de l'ordre d'évaluation. Ainsi est-il facile de se persuader de la correction de la fonction append précédente une fois qu'on a énoncé ce qu'elle est censé faire (i.e append l1 l2 construit la liste formée des éléments de l1 suivis des éléments de l2) : une simple récurrence sur la structure de l1 suffit. Avec des listes modifiables en place et une fonction append allant modifier le dernier pointeur de l1 pour le faire pointer sur l2, l'argument de correction est nettement plus difficile. L'exemple est encore plus flagrant avec le renversement d'une liste. La correction d'un programme n'est pas un aspect négligeable et doit toujours l'emporter sur son efficacité : qui se soucie en effet d'un programme rapide mais incorrect ?
    
    Le code de la fonction append en question est :
```
let rec append l1 l2 = match l1 with
  | [] -> l2
  | x :: xs -> x :: append xs l2
```
    et effectivement un simple raisonnement par récurrence sur la structure de l1 suffit à prouver sa correction. On peut même facilement formaliser un tel résultat dans un assistant de preuve comme Coq pour certifier le code. Là où avec des structures impératives se sera une toute autre paire de manches.
    
    Ils continuent en prenant un exemple de problématiques de backtracking : parcourir un labyrinthe pour trouver une sortie. La position dans le labyrinthe est modélise par un état e dans un type de donnés persistants. On suppose qu'on a une fonction is_exit qui prend un état et renvoie un booléen pour savoir si on est à une sortie. On a également une fonction possible_moves qui renvoie la liste de tous les déplacements possibles à partir d'un état donné et une fonction move pour effectuer un tel déplacement. La recherche d'une sortie s'écrit alors trivialement à l'aide de deux fonctions mutuellement récursives :
```
let rec find e =
  is_exit e || try_move (possible_moves e)
and try_move e = function
  | [] -> false
  | d :: r -> find (move d e) || try_move e r
```
    Avec des structures impératives il faudrait, après chaque déplacement, annuler celui-ci avant d'en faire un autre : ce genre de code est un vrai nid à bugs.
```
let rec find () =
  is_exit () || try_move (possible_moves ())
and try_move = function
  | [] -> false
  | d :: r -> (move d; find ()) || (undo_move d; try_move r)
```
    ici il faudrait s'assurer que la fonction undo_move annule bien correctement le déplacement d effectué via l'appel à move d. Non seulement cela complique le code, mais en plus cela ouvre la porte à des erreurs potentielles.
    
    Dans le même ordre d'idées, on peut prendre le cas de la mise à jour d'une base de données. Avec un structure de donnés modifiables, on aurait un code du style :
```
try
 (* effectuer l'opération de mise à jour *)
with e ->
 (* rétablir la base dans un état cohérent *)
 (* traiter ensuite l'erreur *)
```
    Avec un structure persistante, c'est plus simple et moins propice aux bugs.
```
(* on stocke la base dans une référence *)
let bd = ref base_initale

try
  bd := (* opération de mise à jour de !bd *)
with e ->
  (* traitement de l'erreur *)
```
    Ici la mise à jour construit une nouvelle base qui est ensuite affectée à l'ancienne via une opération atomique qui ne peut échouer. Si il y a une erreur lors de l'opération de mise à jour alors l'ancienne base n'a pas été modifiée et il n'est pas nécessaire de la remettre dans un état cohérent avant de traiter l'erreur proprement dite.
    
    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
    - [^] # Re: Structures non mutables performantes
      
      Posté par Guillaum (site web personnel) le 10 août 2017 à 00:11. Évalué à 3.
      
      Très bon ;)
      
      Je complète avec un exemple d'usage que j'ai eu en vrai. Je manipule un très gros graph dans une interface graphique. Tous les paramètres de l'interface, jusqu'au champs qui a le focus, sont stockés dans un arbre. Pour info, une fois sérialisé (en binaire), le graph fait plusieurs centaines de Mo, voir quelques Giga. Chaque modification crée une nouvelle copie de cette structure et est ajouté dans une liste de modification (en fait c'est un graph). Faire annuler revient à revenir en arrière d'un cran dans le graph. Faire "redo" revient à avancer en avant d'un cran dans le graph. En moyenne chaque copie du graph coûte O(log(n)) en mémoire, ce qui est négligeable et permet de conserver une grande quantité d'étape d'undo/redo. On peut même les sauvegarder avec le fichier. C'est gratuit à faire avec des structures persistantes, modulo qu'en C++ je dois me balader avec des shared_ptr de partout, mais cela fonctionne.
      - [^] # Re: Structures non mutables performantes
        
        Posté par kantien le 10 août 2017 à 12:13. Évalué à 2.
        
        En moyenne chaque copie du graph coûte O(log(n)) en mémoire, ce qui est négligeable et permet de conserver une grande quantité d'étape d'undo/redo. On peut même les sauvegarder avec le fichier. C'est gratuit à faire avec des structures persistantes, modulo qu'en C++ je dois me balader avec des shared_ptr de partout, mais cela fonctionne.
        
        Ton exemple me rappelle un commentaire que j'avais écrit sur une dépêche C++. Freem se demandait à quoi pouvait bien servir les shared_ptr, et de ce que j'en avais compris je lui avais soumis comme idée une structure de tableaux persistants. J'avais bien compris le fonctionnement des shared_ptr ? Le principe consisté à conserver toutes les opérations de transformations effectuées sur une structure modifiables à la manière d'un gestionnaire de version. C'est ce que tu fais aussi avec tes graphes ? D'ailleurs l'exemple des tableaux persistants est tiré du livre de mon commentaire précédent.
        
        Le bouquin est bien fait, toute la seconde partie est consacrée aux structures de données : modifiables ou persistantes avec analyse de la complexité. Une structure que je trouve particulièrement élégante est le zipper de Gérard Huet pour se déplacer facilement à l'intérieur d'un type inductif (listes, arbres…). Le zipper sur les listes a pour type :
        
        type 'a zipper = { left : 'a list ; right : 'a list }
        
        c'est l'exemple des Queues que Okasaki¹ étudie dans la troisième partie de sa thèse. Gérard Huet en propose une version plus détaillée dans la présentation de The Zen Computational Linguistics Toolkit, voir la troisième partie : Top-down structures vs bottom-up structures.
        
        Pour ce qui est du coût mémoire, qui reste acceptable, même avec des structures impératives on peut difficilement faire sans dès que l'on veut pouvoir annuler des opérations. Prenons un exemple idiot et sans grand intérêt : un pointeur sur un int. Si une opération de modification consiste à lui ajouter un int quelconque, il faudra bien conserver cette valeur quelque part au cas où on voudrait annuler l'addition avec une soustraction : la valeur finale contenue dans le pointeur ne contenant aucune information sur la quantité qui lui a été ajoutée. Autant encapsuler toute cette mécanique dans une structure persistante : cela simplifie son usage et le risque de bugs dans le code client de la structure.
        
        le livre d'Okasaki fait d'ailleurs partie des références bibliographiques données en fin d'ouvrage. ↩
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Structures non mutables performantes
        
        Posté par Guillaum (site web personnel) le 10 août 2017 à 14:29. Évalué à 2.
        
        Le principe consisté à conserver toutes les opérations de transformations effectuées sur une structure modifiables à la manière d'un gestionnaire de version. C'est ce que tu fais aussi avec tes graphes ? D'ailleurs l'exemple des tableaux persistants est tiré du livre de mon commentaire précédent.
        
        J'ai regardé ton exemple, et si je comprend bien, tu maintient une liste de diff, mais dans le sens inverse. C'est à dire que reroot applique l'ensemble des diff sur le tableau, et modifie les références vers les anciens tableaux pour remplacer ceux-ci par un diff. Ce qui veut dire que si tu accèdes alternativement à un ancienne et une nouvelle version du tableau, tu passes ton temps à faire de la cuisine interne de pointeur pour que le tableau réellement stocké soit à un moment l'ancien et à un moment le nouveau ? Si tu pensais que les shared_ptr était un moyen d'obtenir un pointeur sur un pointeur et de pouvoir modifier le pointeur interne, ce n'est pas le cas. Sinon je ne vois pas trop comment utiliser des shared_ptr dans ton implémentation.
        
        Un shared_ptr n'est rien d'autre qu'un pointeur qui est responsable de la durée de vie de ce qui est pointé. Quand le shared_ptr est copié, le compteur de référence est incrémenté (atomiquement). Quand il est détruit, le compteur de référence est décrémenté, et si il atteint 0, la valeur pointée est aussi détruite. C'est un garbage collector à comptage de référence. Il y a quelques subtilités en plus car le shared_ptr peut pointer sur un objet et maintenir la durée de vie d'un autre objet, c'est pratique si tu veux pointer directement sur les éléments d'une grosse structure et que tu veux garder la grosse structure en vie tant qu'il existe un pointeur sur l'un de ses enfants. C'est un truc inutile dans un contexte avec un garbage collector, puisque c'est le garbage collector qui fait ce travail. Mais en C++, c'est le développeur qui est responsable de la durée de vie de ses éléments alloués sur le tas, et la mode est de plus en plus à l'usage de unique_ptr et shared_ptr pour simplifier ce travail. Les shared_ptr sont un peu l'équivalent du GC de Haskell / OCaml et les unique_ptr sont un peu l'équivalent de la gestion de ressources sur des types linéaires (Grosse simplification, on vas un jour me ressortir cela en entretien et j'aurais honte ;)
        
        Ce que je fais avec mes graph, ils sont non mutables. Quand j'en veux un nouveau, j'en crée une copie intégrale en réutilisant un maximum l'ancien graph. Dans le pire des cas, c'est en O(n) avec n la profondeur maximum du graph. Et je met ce nouveau graph dans ma liste d'opérations effectuée.
        
        En gros, j'ai une liste [graph0, edition (graph0), edition' (edition (graph 0))], mais en pratique l'utilisation mémoire n'est pas équivalente à 3 graph. Après il suffit de bouger le "pointeur" (qui peut être un zipper) sur cette liste pour annuler / refaire. La seule subtilité c'est ce qui se passe quand une nouvelle édition arrive alors que on est pas en queue de liste. Soit on détruit les états suivants (le plus classique). Example, si on annule et que on fait edition'', la liste sera [graph0, edition (graph0), edition'' (edition (graph 0)]. Mais on peut aussi crée un arbre, tel que :
        
        - graph0 - edition (graph0) - edition' (edition (graph0) - edition'' (edition (graph 0))
        
        Mais c'est dur à conceptualiser pour les utilisateurs, soit on peut considérer que l'annulation EST une opérations, et donc obtenir la liste suivante : [graph0, edition (graph0), edition' (edition (graph0)), edition (graph0), edition'' (edition (graph0))]. Ce qui est amusant c'est que chaque étape ne coûte rien en mémoire.
        
        Dans ce contexte, j'utilise des shared_ptr pour les pointeurs vers chaque noeuds du graph. Quand je réutilise un nœud dans le graph suivant (ce qui arrive très souvent), alors le shared ptr est incrémenté. En gros cela me gère gratuitement la durée de vie des noeuds de tous les états de mon arbre.
        
        Quand il est tant de faire un peu de ménage, je peux par exemple supprimer les éléments les plus vieux de mon historique. Soit ceux-ci sont encore utilisés par un graph plus récent, et ils sont conservé, soit ils ne le sont pas, le compteur du shared ptr tombe à zéro, et l'élément est supprimé et récursivement le même mécanisme est appliqué à tous ses enfants.
        
        Ce qui est beau avec cette approche c'est qu'il n'est pas nécessaire de stocker la liste des opérations et il n'est pas nécessaire de réfléchir à comment inverser une opération, le code est assez trivial puisque il consiste en une gestion d'une pile d'opération, et chaque nouvelle opération crée une copie modifié du graph et ajoute celle ci dans la pile.
        
        Merci pour la référence bibliographique, je lirais cela dans le train ;)
        
        [^] # Re: Structures non mutables performantes
        
        Posté par kantien le 10 août 2017 à 16:26. Évalué à 2. Dernière modification le 10 août 2017 à 16:30.
        
        Effectivement, tu as bien compris comment fonctionnaient ces tableaux persistants. En interne il y a des effets de bords sur un véritables tableaux à la mode impératif. Cela vient en partie de la conception de la persistance des deux auteurs de l'ouvrage sus-mentionné :
        
        Cela ne signifie pas pour autant qu'une structure de données persistantes soit nécessairement codée sans aucun effet de bord. La bonne définition de persistant est :
        
        persistant = observationnellement immuable
        
        et non purement applicatif (au sens de l'absence d'effet de bord). On a seulement l'implication dans un sens :
        
        purement applicatif => persistant
        
        La réciproque est fausse, à savoir qu'il existe des structures de données persistantes faisant usage d'effets de bord. Cet ouvrage contient plusieurs exemples de telles structures.
        
        Dans cet exemple, on utilise les effets de bords pour avoir des opérations de lecture et d'écriture en temps constant tant qu'on utilise pas la persistance (sinon, il faut prendre en compte le temps de se rebaser sur le bon tableau via reroot en appliquant les patchs).
        
        Pour ce qui est du fonctionnement des shared_ptr, en lisant ton explication, il me semble bien que c'est ce que j'en avais déjà compris. La discussion avec freem sur le sujet commence à ce commentaire et il pensait qu'en programmation fonctionnelle on privilégiait la copie alors que l'on favorise le partage de la mémoire (là où je voyais un rapport avec les shared_ptr, qui apportent aussi une gestion automatique de la mémoire à la manière des GC). Je prenais cet exemple de représentation en mémoire de deux listes qui partagent leur queue :
        
        let l = [1; 2; 3];; (* la représentation mémoire de celle-ci est une chaîne : | 1 | -|-->| 2 | -|-->| 3 | -|-->| | *) let l1 = 4 :: l and l2 = 5 :: l;; (* ce qui en mémoire donne : | 4 | \| \ -->| 1 | -|-->| 2 | -|-->| 3 | -|-->| | / | 5 | /| *)
        
        De ce que je comprends de ta gestion mémoire pour tes graphes, c'est que tu évites les effets de bords et tu gères tes pointeurs comme le feraient les compilateurs Haskell et OCaml pour les types inductifs. Ai-je tort ? La liste l qui est partagée entre l1 et l2 n'est-elle pas proche d'un shared_ptr ?
        
        Dans le cas de mes tableaux persistants :
        
        type 'a t = 'a data ref and 'a data = |Arr of 'a array |Diff of int * 'a * 'a t
        
        ce n'est pas avec le type paramétrique 'a t des tableaux que je crois voir une analogie avec les shared_ptr, mais avec le type 'a data. Pour ce qui du type 'a t, c'est une simple référence comme on en trouve en C++. Suis-je à côté de la plaque ?
        
        Pour la note historique, d'après les auteurs du livre, cette structure de tableaux persistants serait due à Henry Baker qui l'utilisait pour représenter efficacement les environnements dans des clôtures LISP. (Henry G. Baker. Shallow binding makes functionnal array fast).
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Structures non mutables performantes
        
        Posté par Guillaum (site web personnel) le 11 août 2017 à 00:40. Évalué à 3.
        
        La réciproque est fausse, à savoir qu'il existe des structures de données persistantes faisant usage d'effets de bord.
        
        J'ai eu cette révélation quand j'ai commencé à faire de la Memoization en Haskell.
        
        Tu as bien compris ce que je raconte, la liste l partagée entre l1 et l2 peut être vue comme un shared_ptr. Sauf que en Haskell (et je crois en OCaml), la gestion de la mémoire est faite avec un GC traçant, alors que là en C++ c'est un comptage de référence, avec ses avantages et inconvénients.
        
        Tu as bien compris l'usage de shared_ptr, sauf que dans ce cas de figure c'est loin d’être trivial puisque en fait il faut garder un weak_ptr sur chaque shared_ptr… Bref, je me suis amusé un peu et cela donne ça :
        
        https://gist.github.com/guibou/73c33d9e511385f4c52b313cb3d4d0e6
        
        Version C++ et Haskell.
        
        La version C++ est peu propre, il y aurait pas mal de choses à traiter pour faire un vrai truc qui marche. La version Haskell et pas mal mais fait peur car en Haskell il faut faire un choix :
        
        Pas d'effet de bord, c'est facile
        
        Des effets de bord, ils sont alors visible par le biais de :
        
        IO, des effets de bords
        
        ST, des effets de bords qui sont limités à une fonction et que le compilateur peu garantir comme étant limités à une fonction.
        
        unsafePerformIO, des effets de bords qui ne sont pas limités à une fonction et pour lequel c'est ton boulot de développeur de garantir que tu ne fais pas n'importe quoi. C'est ce que j'ai essayé de faire, mais sans garantie ;)
        
        Note, si mon benchmark n'est pas faux (j'ai des doutes quand je manipule des effets de bords de ce type), alors :
        
        modifier un vecteur non mutable (i.e.: créer une copie) c'est super rapide sur des petits vecteurs, mais cela devient linéairement lent avec la taille du vecteur qui augmente
        
        modifier un vecteur avec ta technique c'est en O(1)
        
        modifier un vecteur "vraiment" mutable vue de l’extérieur est un poil plus rapide.
        
        Merci pour la discussion, je me suis amusé.
        
        [^] # Re: Structures non mutables performantes
        
        Posté par kantien le 14 août 2017 à 15:04. Évalué à 2.
        
        Heureux de voir que j'avais bien compris le principe des shared_ptr. Je suppose qu'en C++ la nécessité de recourir au weak_ptr doit venir du côté mutuellement récursif des deux type 'a t et 'a data.
        
        Note, si mon benchmark n'est pas faux (j'ai des doutes quand je manipule des effets de bords de ce type), alors :
        
        modifier un vecteur non mutable (i.e.: créer une copie) c'est super rapide sur des petits vecteurs, mais cela devient linéairement lent avec la taille du vecteur qui augmente
        
        modifier un vecteur avec ta technique c'est en O(1)
        
        modifier un vecteur "vraiment" mutable vue de l’extérieur est un poil plus rapide.
        
        Je suis étonné qu'une copie complète soit plus rapide sur de petits vecteurs, j'aurais parié le contraire (je suis surtout étonné par l'écart de temps : 4 ms vs 30 ms). En revanche, le coût constant si on n'enchaîne que des update est bien conforme à mes attentes. Néanmoins, le code de ta fonction update est « erroné », en OCaml c'est celui-ci :
        
        let set pa i v = let a = reroot pa in let old = a.(i) in a.(i) <- v; let res = ref (Arr a) in pa := Diff (i, old, res); res
        
        Il faut d'abord se rebaser sur le « véritable » vecteur représentant ton tableau, faire une mise à jour à l'index, construire une référence sur le vecteur mis à jour et modifier l'ancien tableau persistant pour le voir comme un Diff du nouveau, puis enfin retourner le nouveau tableau. Ceci dit, cela ne doit pas changer les invariants de la structure par rapport à ton code. Chaque tableau persistant est, dans le fond, une classe d'équivalence¹ au sein du type 'a data puis ton code et celui en OCaml ne renvoie simplement pas le même élément de la classe en question.
        
        Merci pour la discussion, je me suis amusé.
        
        À mon tour de te remercier pour ta très intéressante dépêche. La partie sur l'introduction du typage linéaire (dont je suivrai l'évolution avec intérêt) m'a enfin décidé à acheter certains ouvrages de Jean-Yves Girard² : j'y pensais depuis longtemps mais je repoussais toujours l'achat (sans raison aucune à vrai dire). Je me suis acheté la transcription de ses cours de Logique, Le Point Aveugle en deux tomes, ainsi que son dernier livre Le Fantôme de la transparence. Si les deux premiers livres sont très techniques et théoriques, le dernier est, quant à lui, un ouvrage plus grand publique de « vulgarisation ». J'attends toujours la livraison de ses cours, mais j'ai en revanche reçu ce matin Le Fantôme de la transparence dans lequel je peux lire, à mon grand plaisir, en conclusion de sa préface de présentation :
        
        Le principal bénéficiaire de cette visite non guidée aura été l'auteur, tout surpris d'y trouver matière à de futurs développements techniques. Et de découvrir la surprenante adéquation du kantisme — au sens large — à la logique contemporaine. Ce qui n'est pas très étonnant après tout : que veut dire « raison pure », sinon logique ?
        
        Le graissage est bien entendu de moi :-). La chose m'étonne moins : étudiant, je m'étais inscrit au master Logique Mathématique et Fondements de l'Informatique parce que j'étais déjà kantien et que je voulais approfondir mes connaissances en logique. Puis lorsque Jean-Louis Krivine m'enseigna la lambda-calcul typé, le système F et la correspondance de Curry-Howard, ma première réaction fût : c'est comme la théorie kantienne des catégories dans la Critique de la Raison Pure³ ! ;-) Pour Kant (pour faire court et en employant des termes actuels), le type du rapport de cause à effet c'est la forme des jugements hypothétiques, forme qui est le type des fonctions en programmation fonctionnelle. \o/
        
        la relation d'équivalence étant pa ~ pa' si et seulement si reroot pa = reroot pa'. ↩
        
        il paraît, d'ailleurs, que son système F est une des représentations intermédiaires du compilateur GHC. ↩
        
        et la machine universelle de Turing, c'est comme la théorie du schématisme dans le même ouvrage, mais en moins abstraite et moins générale (donc plus facile à comprendre ;-). ↩
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Structures non mutables performantes
        
        Posté par Guillaum (site web personnel) le 14 août 2017 à 23:36. Évalué à 2.
        
        Je suppose qu'en C++ la nécessité de recourir au weak_ptr doit venir du côté mutuellement récursif des deux type 'a t et 'a data.
        
        Cela vient du fait que que C++, les shared_ptr doivent être "clonés" à partir d'un précédant shared_ptr pointant vers le même objet, d'où le besoin de concerver cette information dans un weak_ptr. Dans une implémentation ou la gestion de la mémoire est assurée par un garbage collector traçant, le problème est tout autre, puisque pour cloner une "référence" vers soit, il suffit de cloner son adresse, et le GC traçant, lors de sa passe de recherche, trouvera qu'il existe plusieurs références vers la même adresse. Avec les avantages et inconvénients des deux méthodes : le shared_ptr n'a pas besoin d'un scan entier de la mémoire pour fonctionner.
        
        Je suis étonné qu'une copie complète soit plus rapide sur de petits vecteurs, j'aurais parié le contraire (je suis surtout étonné par l'écart de temps : 4 ms vs 30 ms)
        
        Copier un petit tas de pointeur, t'as toutes les chances que cela tombe dans une ligne de cache, donc en gros c'est assimilé à une unique lecture / écriture en RAM, ce qui est assez rapide. Cela doit sans doute venir de là.
        
        Néanmoins, le code de ta fonction update est « erroné »
        
        Oui, en effet, il est différent du tient, je t'avoue ne pas avoir recopié, mais implémenté from scratch en me basant sur ce que j'avais compris ;)
        
        C'est un compromis différent, plus "paresseux" puisque le reroot n'est fait qu'au moment de la lecture de la structure. Je ne pense pas que cela change grand chose au final.
        
        [^] # Re: Structures non mutables performantes
        
        Posté par kantien le 15 août 2017 à 01:48. Évalué à 2.
        
        Au sujet de la gestion automatique de la mémoire, je dois dire que je n'y connais pas grand chose. Tout comme sur le fonctionnement interne des CPU et de leur cache.
        
        En revanche, j'ai reréfléchi à ton implémentation de update et je doute qu'elle soit optimale pour l'usage de cette structure. Déjà on perd totalement l'intérêt d'avoir un tableau modifiable en interne : tu n'utilises jamais son set en O(1). Et comme tu ne rerootes pas sur le V.IOVector avant de modifier le valeur à un index donné, au fur et à mesure tu ajoutes des indirections à coup de Diff par rapport au tableau : au prochain get sur un tableau nouvellement créé, tu te retrouves à aller chercher l'équivalent du dernier élément d'une liste chaînée dont le temps sera proportionnel au nombre de set que tu auras fait (tu as une chose du genre Diff Diff Diff ... (Array v)). Là où avec l'implémentation proposée en OCaml le nombre de Diff reste petit : le nouveau tableau est juste une référence sur un tableau boxé (ref (Arr a)) et l'ancien (celui passé en entrée) et maintenant un Diff sur le nouveau et reste donc à une distance 1 d'un « véritable » tableau (Diff (idx,v,ref (Arr a))). Ton code risque d'en pâtir sur la complexité en temps des get.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
        
        [^] # Re: Structures non mutables performantes
        
        Posté par Guillaum (site web personnel) le 16 août 2017 à 00:10. Évalué à 3.
        
        Au sujet de la gestion automatique de la mémoire, je dois dire que je n'y connais pas grand chose. Tout comme sur le fonctionnement interne des CPU et de leur cache.
        
        What every programmer should know about memory est une lecture vivement conseillée dans ce cas.
        
        En revanche, j'ai reréfléchi à ton implémentation de update et je doute qu'elle soit optimale pour l'usage de cette structure. […]
        
        Il est vrai qu'une suite de set vas créer une cascade de Diff qu'il faudra résoudre lors du premier get. En gros, le premier get est en O(n) avec n le nombre de set fait pendant ce temps. Mais en analyse amortie, je pense que c'est équivalent, puisque le temps "gagné" à ne pas faire le reroot lors de chaque set sera "utilisé" lors du premier get.
        
        Par contre, cela change pas mal le comportement en mémoire. Dans mon cas, le garbage collector ne vas pas supprimer les n Diff intermédiaires, tant qu'il n'y aura pas de reroot, même si les vecteurs précédents ne sont pas utilisés.
        
        Quoi qu'il arrive, cette structure se comporte très mal quand tu utilises les anciennes copies. cela coûte très chère si tu essayes d’accéder consécutivement à deux version assez éloignées, car il faut reroot en permanence entre les deux, avec un O(n), n étant le nombre d'étape séparant les deux.
        
        En Haskell, dans mon implémentation paresseuse, c'est encore plus drôle si tu met à jour des cases avec le contenu d'un vecteur précédant (voir futur si tu as envie, c'est la beauté d'Haskell). Imagine le code suivant :
        
        vec = ... -- on a un vecteur initialisé vec2 = update vec 0 (index vec 0 + 1) -- incremente la case 0 vec3 = update vec2 0 (index vec2 0 + 1) -- incrémente encore la case 0 print vec3
        
        chaque opération est paresseuse, donc en fait, vec2 et vec3 ne sont que des opérations paresseuses. Quand tu vas vouloir afficher vec3, il vas d'abord construire le Diff sur vec2 qui est un Diff sur vec. Puis, pour afficher la case 0, il va reroot sur vec3 jusqu'à réaliser que la case 0 c'est index vec2 0 + 1, donc il va reroot sur vec2, pour réaliser que c'est une fonction de vec, donc il vas reroot sur vec. Fin de l'évaluation paresseuse de la case 0. Pour passer à la case 1, il doit de nouveau reroot sur vec3, et là c'est bon. On peut bien évidemment contrôler ce comportement en forçant l'évaluation paresseuse judicieusement, mais quoi qu'il arrive il y aura des comportements tordus.
        
        Par contre, j'ai benché mon code en ajoutant des lectures, puisque sinon la seule chose que on faisait c'est empiler des création de Diff, et il est clair qu'il y a une différence non négligeable de performance car le reroot doit être effectué, et en fonction du pattern d'utilisation, les performances peuvent être catastrophiques.
        
        En gros, nous avons une structure persistante qui remplace un vecteur, mais dont les performances se cassent la gueule en fonction du nombre de versions partagées, et dont la place mémoire dépend du nombre de versions partagées et du nombre d'étapes entre les versions partagées. Bref, j'en arrive à conclure que c'est une structure amusante, mais pas si performante que cela. Je pense que on peut faire beaucoup mieux avec un HAMT qui conserve des propriétés de modification / insertion en O(log n) avec une très grosse base pour le log. La librairie unordered-containers utilise une base 16 pour le trie.
        
        Après, j'utiliserais sans doute un vecteur mutable, ou, quand cela sortira, des vecteurs en type "linéaires".
        
        [^] # Re: Structures non mutables performantes
        
        Posté par kantien le 18 août 2017 à 10:34. Évalué à 3.
        
        What every programmer should know about memory est une lecture vivement conseillée dans ce cas.
        
        Cela à l'air on ne peut plus complet ! :-O
        N'étant pas programmeur, je mets cela de côté et le lirai quand j'aurais le temps par pure curiosité intellectuelle. C'est fou ce que la technique évolue, il n'y a pas longtemps j'ai relu l'article de Turing sur son test de l'imitation et l'on y lit :
        
        Dans le système nerveux, les phénomènes chimiques sont au moins aussi importants que les phénomènes électriques. Dans certains ordinateurs le système de mémorisation est principalement acoustique.
        
        Je n'ose imaginer leur capacité mémoire et les temps de réponse. :-P
        
        Pour la structure et ses performances, cela doit surtout dépendre de son usage. Dans le pire des cas concevables, un vecteur est totalement distinct du contenu du vecteur modifiable partagé et dans ce cas, il faudrait qu'il ne se trouve pas à plus de n Diff de ce dernier (où n est la taille des vecteurs). Le tout étant qu'une telle distance ne soit que rarement dépassée : avec ton implémentation c'est plus dur à obtenir car tu ne rebases jamais quand tu changes le contenu d'une cellule, avec mon implémentation cela doit pouvoir se réaliser dans certains usages.
        
        Il se peut, aussi, que l'aspect paresseux d'Haskell est également un impact. En tout cas, dans ton implémentation, vu la façon dont tu vas solliciter le GC cela peut aussi avoir son impact. Gasche a écrit un article de comparaison des GC : Measuring GC latencies in Haskell, OCaml, Racket.
        
        Intéressant la structure des HAMT, je regarderai cela de plus près. Les modules Map et Set sont implémentés avec des arbres binaires balancés en OCaml. Mais la doc Haskell précise que :
        
        A HashMap is often faster than other tree-based set types, especially when key comparison is expensive, as in the case of strings.
        
        Si j'ai le temps, j'essaierai d'implémenter la chose en OCaml et de comparer les performances.
        
        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
  - [^] # Re: Structures non mutables performantes
    
    Posté par djano le 13 août 2017 à 10:16. Évalué à 3.
    
    J'ai voulu cependant introduire un peu le concept et fournir une bonne ressource car je trouve que on néglige trop souvent les structures de donnée dans l'apprentissage de l'informatique, et on néglige encore plus les structures non mutables qui offrent des propriétés très intéressantes.
    
    Ça dépend où tu as fait tes études.
    J'en ai bouffé des structures de données, et nos TDs / TPs consistaient à coder les structures de données classiques (listes, arbres binaires équilibrés) en C++ / Java.
    
    Je suis d'accord avec toi pour les structures non mutables. On les appelle "persistentes" (ce que je trouve contre intuitif par rapport à une base de données)
    - [^] # Re: Structures non mutables performantes
      
      Posté par Guillaum (site web personnel) le 13 août 2017 à 14:31. Évalué à 4.
      
      Ça dépend où tu as fait tes études.
      
      En effet. Dans mon école d'ingénieur on passait beaucoup de temps à faire du chiffrage et de la planification de réunion, mais peu de temps à faire de la technique ;( Il parait que cela a changé depuis.
      
      J'en ai bouffé des structures de données, et nos TDs / TPs consistaient à coder les structures de données classiques (listes, arbres binaires équilibrés) en C++ / Java.
      
      Pour être passé du coté obscure de la force et enseigner à mes heures perdues, je suis impressionné par le nombre d'étudiants qui arrivent en master 2 avec aucune notion de complexité des structures de donnée.
      
      Les cours de structures de donnée que j'ai pu donner en licence sont souvent mélangés avec d'autres problématiques, comme les templates en C++., ou le réseau, ou l'image. Au final le message est dilué et seul les étudiants curieux qui m'offrent un café pendant le TD ont le droit à mes discussions enflammées sur les structures de donnée.
      
      J'ai souvent tendance à dire "non mutable" en place de "persistante" pour la simple et bonne raison que souvent personne ne sait ce que c'est. Ainsi "non mutable" provoque souvent la question "mais comment on fait pour la modifier si elle est non modifiable", alors que persistante, c'est souvent confondu avec, comme tu le dis, les moyens de persistances types BDD ou sérialisation.
  - [^] # Re: Structures non mutables performantes
    
    Posté par kantien le 08 septembre 2017 à 15:38. Évalué à 2.
    D'ailleurs je cherche encore une ressource accessible traitant de façon pertinente de l’implémentation de différentes structures de donnée (lazy ou non / mutable ou non) efficace sur des architectures de CPU modernes.
    
    Je suppose que tu cherches des structures pour langage fonctionnel (comme dans le livre de Okasaki). Tu trouveras peut être ton bonheur dans ces liens :
    Edward Kmett est l'auteur du blog The Comonad.Reader.
    
    En espérant que ça puisse t'être utile.
    
    Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.