Journal Le compilateur GHC Haskell en version 8.0.1

Sommaire

• Introduction, Troll et digressions
  • Exemple
• Nouveautés de GHC 8.0
  • DeriveAnyClass
  • PatternSynonyms
  • En Vrac
• Digressions

Le 21 mai 2016 est sortie la nouvelle version du compilateur Haskell GHC. Le mail d'annonce. notes de version.

GHC est le compilateur principal du langage Haskell, disponible sur plusieurs plate-forme et sous une (https://www.haskell.org/ghc/license](licence) libre qui proche de BSD.

Cette version succède à GHC 7.10.

Ce journal présente rapidement Haskell grâce à un exemple de code puis une sous-partie des nouveauté de GHC 8.0, le compilateur Haskell le plus utilisé. Comme on parle rarement d'Haskell ici, je vais le présenter avec une approche personnelle puis je me servirais de la liste des nouveautés pour présenter quelques fonctionnalités de ce langage de programmation.

Introduction, Troll et digressions

J'ai découvert Haskell début 2015 avec l'envie de découvrir une nouvelle technologie totalement différente de mes pratiques habituelles. Je fais principalement du C++ quand j'ai besoin de performance et du python le reste du temps. À l'époque j'avais un avis bien tranché et négatif sur le typage, n'y voyant qu'un outil de contrainte nécessaire pour les performances. J'ai donc essayé Haskell avec cette envie de me remettre en question : ce langage promettait du typage statique avancé.

Ce langage a changé ma manière de voir la programmation et l'ensemble de mes certitudes sur ce qui fait un bon outil de programmation. J'ai d'ailleurs réalisé une présentation sur Haskell à l'université de Lyon qui aurait dû s'intituler "Comment j'ai appris à ne plus m'inquiéter et à aimer les types".

Alors, rapidement, Haskell c'est :

• un langage fonctionnel, ce qui se résume à une syntaxe et des "design patterns" pas habituels pour qui fait du C++. À l'usage on se fait plaisir à combiner ensemble des fonctions en fonctions de plus haut niveau.
• un langage fonctionnel pur. Pas d'effet de bord par défaut. Les fonctions qui réalisent des effets de bords sont bien repères car cela apparaît dans leur type. Au départ cela semble une contrainte et cela force à réfléchir un peu plus en amont de l'écriture du code. Mais au final j'ai l'impression que cela aide énormément à raisonner sur son code et à le maintenir.
• un langage paresseux, c'est pratique de temps en temps, c'est embêtant le reste du temps. C'est discutable, mais j'apprécie.
• un langage statiquement typé. Je m'attendais à devoir écrire des prototypes de fonction à rallonge, devoir me battre pour faire rentrer le type qui m'intéresse dans la fonction qui m'intéresse. Mais en fait il n'en est rien. En premier lieu Haskell a une inférence de type très robuste et au final on écrit rarement des types. Mon expérience est que le système de type d'Haskell ne m'a rarement posé de problème.

Voila, au final Haskell est devenu pour moi un nouvel outil dans ma sacoche de développeur. Il remplace presque totalement python car je le trouve plus sympa à utiliser, plus sur du fait du typage statique et souvent bien plus performant, il me manque seulement certaines librairies de l'écosystème python scientifique. Il ne remplace pas C++ pour les performances malheureusement, mais s'en approche beaucoup. En pratique, si vous écrivez du code C++ naïf, le code Haskell sera équivalent. Si votre problématique en C++ sont les performances, alors vous pourrez écrire du code C++ bien plus efficace.

Exemple

Donc pour ceux qui n'en on jamais fait et qui ont la flemme d'aller regarder les liens, voici un exemple d'Haskell. Il est discutable sur pleins de points comme tout exemple ;)

Celui-ci lit les mot du dictionnaire /usr/share/dict/french et grouper les mots par anagrammes. Pour cela on part d'un constat simple, les anagrammes ont les même lettres triés. Par exemple "tortue" et "tourte" sont anagrammes l'un de l'autre car sort "tortue" == sort "tourte" == "eorttu". Pour cela, on va réaliser une structure associative (i.e. un dictionnaire) Map qui associe à la chaîne triée la liste de tous les anagrams associés. Par exemple, on pourrait obtenir le dictionnaire suivant :

{
   "cehin" : ["chien", "niche"],
   "eorttu" : ["tortue", "tourte"]
}

Ainsi connaître les anagrammes de "chien" se résume à calculer sa clé d'anagramme en triant les lettres et à regarder dans la structure associée.

Voici le code que je commente tout de suite après :

import qualified Data.Map as Map          -- 1
import qualified Data.List as List        -- 2

filename = "/usr/share/dict/french"       -- 3

main = do                                 -- 4
  content <- readFile filename            -- 5

  let                                     -- 6
      wordList = lines content            -- 7
      anagramMap = mkAnagramMap wordList  -- 8

  print (getAnagrams anagramMap "chien")  -- 9
  print (getAnagrams anagramMap "écrire")
  print (getAnagrams anagramMap "bleurk")

key word = List.sort word                -- 10

getAnagrams anagramMap word = Map.lookup (key word) anagramMap -- 11

mkAnagramMap wordList =                  -- 12
  let
    keyValue = map (\x -> (key x, [x])) wordList       -- 13
  in
    Map.fromListWith (++) keyValue                     -- 14

En premier lieu on observe qu'il n'y a aucune déclaration de type, pas de syntaxe verbeuse pour les faire apparaître. C'est grâce à l'inférence de type. Très souvent les types ne sont pas nécessaire et le compilateur se débrouille seul, mais on peut les ajouter explicitement si on le désire pour documenter ou pour limiter le polymorphisme. On peut exécuter ce code et obtenir :

Just ["niche","chien"]
Just ["r\233crie","\233crire","\233crier"]
Nothing

Rassurez vous, Haskell gère très bien l'unicode, mais pas pour l'affichage dans une structure imbriquée. Notez que pour le mot "bleurk", il n'existe pas d'anagramme, et la fonction renvoie Nothing au lieu de Just ....

• Les lignes 1 et 2 importent les modules de manipulation de liste et de map.

• La ligne 3 est juste une constante de type chaîne de caractère

• La ligne 4 est le début de la fonction main. C'est une fonction particulière, toutes les lignes qui la composent (sauf celles avec let) sont des effets de bords.

• La ligne 5 lit le contenu du fichier dans la variable content. Petite subtilité, on utilise <- au lieu de = pour marquer l'application d'un effet de bord, le égal étant réservé à l'égalité et non pas à l'affectation.

• La ligne 6, bloc let dit que cette zone est sans effet de bord.

• Ligne 7, on sépare le contenu du fichier en une liste avec un élément par ligne (bref, une liste de mots). Ici la fonction de séparation par retour à la ligne s'appelle lines, il existe une fonction words pour séparer par espaces blancs et une fonction split plus générique.

• Ligne 8, on crée la structure qui associe les mot triés à leurs anagrammes en appelant la fonction mkAnagramMap.

• Ligne 9, on affiche les anagrammes avec la fonction getAnagrams.

• Ligne 10, on défini une fonction utilitaire key qui se contente de renvoyer le paramètre trié. Une chaîne de caractère peut être représentée par une liste en Haskell, c'est le choix que j'ai fais pour les besoins de cet exemple.

• Ligne 11, définition de getAnagram qui regarde dans la structure si la clé y est. Pas d'opérateur pour l'accès au cases d'un dictionnaire en Haskell, il faut utiliser Map.lookup qui renvoie Nothing si la clé n'existe pas ou Just value si elle existe.

• Ligne 12, on crée la structure qui contient les anagrammes. Cette création se fait en deux parties.

• Ligne 13, on crée une liste qui à chaque mot associe sa clé et le mot dans une liste. Exemple : ["chien", "tortue"] -> [("cehin", ["chien"]), ("eorttu", ["tortue"])]. Cette association est faite car nous allons créer notre structure à partir d'une liste d'association clé / valeur. Pour cela on utilise la fonction map qui exécute une fonction anonyme \x -> (key x, [x]) sur chaque valeur de wordList. On note que la valeur est encapsulée dans une liste car on veut crée une structure d'association entre une chaîne et une liste de chaînes.

• Ligne 14, on convertie notre liste clé / valeur en Map en utilisant la fonction Map.fromListWith. Les conflits sont réglés par la fonction (++) qui réalise la concaténation des listes d'anagrammes en conflit.

Nouveautés de GHC 8.0

Lorsque le compilateur GHC se distingue de la spécification du langage, il le fait par le biais d'extensions optionnelles. C'est une approche qui permet de garder une retro compatibilité forte. En contrepartie, écrire du code Haskell sans certaines extensions est assez déprimant et on est arrivé à une situation où GHC est le seul compilateur capable de faire tourner la plupart des codes disponibles.

DeriveAnyClass

L'extension DeriveAnyClass s'est vue améliorée et est moins restrictive. En Haskell, du comportement générique sur des types est ajouté par le biais de "typeclass". C'est proche des "concepts" ou "traits" d'autres langage. Dans de nombreux cas ces comportements sont implémentés de façon générique et peuvent ainsi être dérivés automatiquement. Pour l'exemple nous allons implémenter un arbre binaire.

Pour commencer un peu de boilerplate pour importer les modules et extensions nécessaires :

{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveAnyClass #-}

import GHC.Generics
import Data.Serialize

Maintenant nous allons définir notre type d'arbre binaire :

data Tree t = Node t (Tree t) (Tree t) | Leaf
                     deriving (Show, Serialize, Functor, Foldable, Generic)

Ici pas mal de choses à expliquer. data Tree t signifie que nous créons un type Tree polymorphe paramétré par un type arbitraire t. C'est l'équivalent du C++ template<typename T> class Tree {}. Cette arbre peut avoir deux représentations, équivalente d'une union C, mais typée :

• soit un Node associé à trois valeurs : une valeur arbitraire de type t, et deux sous arbres Tree t.
• soit une feuille Leaf.

Ainsi un arbre binaire vide sera représenté par Leaf. Alors que l'arbre binaire suivant :

          5
         / \
        3   6
       / \ / \
      0  ..   .

Sera représenté par :

 Node 5
    (Node 3
      (Node 0 Leaf Leaf)
      Leaf
    )
  (Node 6 Leaf Leaf)

Pour finir, la clause deriving (Show, Serialize, Functor, Foldable, Generic) liste les comportements par défaut que nous voulons automatiquement dériver :

• Show permet d'obtenir la méthode show qui permet d'afficher l'arbre.
• Serialize nous permet de serializer / deserializer notre arbre.
• Functor nous permet d'appliquer une opération sur tous les éléments de l'arbre avec fmap.
• Foldable nous permet d'effectuer des opérations de réduction sur l'arbre. L'implementation par défaut ne profite pas de la structure d'arbre binaire pour optimiser la recherche du maximum et du minimum, il faudrait surcharger spécifiquement ces fonctions.

Soit :

-- Show
> let tree = Node 5 (Node 3 (Node 0 Leaf Leaf) Leaf) (Node 6 Leaf Leaf)
> print tree
Node 5 (Node 3 (Node 0 Leaf Leaf) Leaf) (Node 6 Leaf Leaf)

-- Serialize
> encode tree
"\NUL\NUL\NUL\NUL\NUL\ENQ\NUL\NUL\NUL\NUL\NUL\ETX\NUL\NUL\NUL\NUL\NUL\NUL\SOH\SOH\SOH\NUL\NUL\NUL\NUL\NUL\ACK\SOH\SOH"

-- Functor
> fmap (*2) tree
Node 10 (Node 6 (Node 0 Leaf Leaf) Leaf) (Node 12 Leaf Leaf)

-- Foldable
> maximum tree
6
> minimum tree
0
> sum tree
14

Les nouveautés de GHC 8.0 vont permettre de rendre encore plus générique et facile ce type de comportement par défaut.

PatternSynonyms

Haskell permet le pattern matching basé sur les types, c'est une forme de switch/case avancé. Par exemple on peut imaginer un type Date :

data Date = Date Int Int Int

Et une fonction qui a une liste de date spéciales associe une chaine :

evenements date = case date of
   Date 1 1 year -> "Premier jour de l'année " ++ (show year)
   Date 24 12 _ -> "Noél"
   Date _ 7 _ -> "Le mois de Juillet"
   Date 6 6 _ -> "Joyeux anniversaire"
   _ -> "Jour ininteressant"

Ici le pattern Date permet de réaliser des comparaisons absolues ou partiels (_ est le joker) et permet aussi d'affecter des variables comme ici year. Le soucis c'est que dans certains cas, les patterns par défaut ne sont pas assez expressifs et deviennent trop complexe. Il est possible de mettre en place des synonymes :

{-# LANGUAGE PatternSynonyms #-}

pattern Year x <- Date _ _ x
pattern Noel <- Date 24 12 _
pattern Month x <- Date _ x _
pattern Birthday x y <- Date x y _
pattern FirstOfYear x = Date 1 1 year

Permettant de réécrire le code précédant :

evenements date = case date of
   FirstOfYear year -> "Premier jour de l'année " ++ (show year)
   Noal -> "Noel"
   Month 7 -> "Le mois de Juillet"
   Birthday 6 6 -> "Joyeux anniversaire"
   _ -> "Jour inintéressant"

Ceci permettant de rendre le code bien plus lisible localement. GHC 8.0 apporte donc son lot de nouveauté sur le support des patterns synonymes avancés.

En Vrac

• Un meilleur support pour les information de debug DWARF. Ce qui permet d'utiliser en Haskell tous les outils autour de DWARF, comme le debug de code avec "gdb", le profiling avec "perf" ou la couverture de code.
• Les extensions Strict et StrictData. Par défaut Haskell est un langage paresseux ce qui veut dire que les calculs ne sont effectués que lorsque la valeur est necessaire et non pas au moment de l'appel de fonction. Cela apporte pas mal de souplesse, cela rend certains algorithmes facile à écrire, mais ce n'est pas toujours optimal d'un point de vu performance. Haskell permet de désactiver l'évaluation paresseuse localement, mais c'est souvent source d'erreur et de complexité du code. Ces nouvelles extensions permettent de désactiver l'évaluation paresseuse totalement au sein d'un module. C'est l'un des reproches les plus courant fait à Haskell qui disparaît.
• L'extension DuplicateRecordFields est sans doute un des points les plus important de cette version. Imaginez un type Point2D avec les champs x et y et une type Point3D avec les champs x, y et z et imaginez un instant que cela ne soit pas possible de les faire cohabiter dans le même module… Impensable non ? Et bien c'était le cas en Haskell avant GHC 8.0 et c'est une vraie libération qui va permettre de simplifier beaucoup de code.
• Un meilleur support des pile d'appel, notamment lors de l'affichage d'une exception. Il est maintenant possible de savoir quelle fonction est responsable de cette exception.
• Le développeur peut maintenant paramétrer les erreurs de type, ce qui permet de rendre les librairies plus utilisable car à la place d'une erreur de type simple disant que votre type n'est pas compatible, le développeur de la librairie peut vous expliquer pourquoi.
• Un meilleur support de nombreuses architecture et notamment ARM.
• Extension TypeInType qui permet à n'importe quel type d'être élevé au rang de kind, c'est à dire le type d'un type. C'est un premier pas vers un meilleur support du typage dépendant. En très simplifié cela revient à ajouter des contraintes sur les valeurs d'un types qui seront vérifiés à la compilation. Un exemple simple serait celui d'un tableau de taille fixe. On pourrait définir la concaténation de deux tableaux contenant respectivement N et M éléments comme un tableau de taille fixe contenant N + M elements. Un autre exemple serait un tuple contenant un booléen et un entier, en Haskell son type est (Bool, Int). Par conception, on voudrait que l'entier soit positif si le booléen est à True et négatif sinon. Le système de type pourrait permettre de représenter cela. Un autre exemple, si vous avez une fonction qui ne s'applique que sur une liste non vide, il pourrait être possible de rajouter cette contrainte dans le type d'entrée de la fonction.
• GHC peut se servir de LLVM comme générateur de code. Il a été décidé de forcer la version de LLVM utilisé pour une version spécifique de GHC (3.7 pour GHC 8.0) afin de simplifier la maintenance.

Base est la libraire standard associée à GHC et est maintenant disponible en version 4.9.0.0. Changements majeurs :

• Certaines fonctions comme error and undefined affichent la pile d'appel lorsque utilisée, plus facile pour corriger les bugs.
• Ajout de Data.List.NonEmpty qui représente des listes non vides. Ce type est pratique si lors de votre conception vous savez que vos listes ne peuvent être vide. Cela permet de simplifier et de réduire les risques d'erreur car certaines fonction, comme maximum, qui ne sont pas définie sur les listes vides, peuvent être appelées sans crainte.
• Ajout Data.SemiGroup qui représente l'ensemble des types possédants une opération de réduction mais pas d'élément neutre. J'en parlais dans ce journal sur le tri en Haskell. Les Monoids sont les types qui admettent une opération de réduction et un élément neutre, comme la somme pour les entiers, qui admet 0 comme élément neutre, où la concaténation de chaînes de caractère, qui admet la chaîne vide comme élément neutre. Les entiers admettent l'opération de réduction minimum, mais il n'existe pas d'élément neutre, ainsi ce ne sont pas des Monoids mais ce sont des SemiGroups.

Ces deux nouvelles librairies sont plutôt représentative de la philosophie de typage qui existe en Haskell. Là où dans de nombreux langage on utiliserais naïvement un entier pour stoker le calcul d'un minimum, en Haskell nous utiliserons un type Min Int. Celui-ci à l'avantage de ne permettre que des calculs de minimum, là ou l'entier permet de nombreuses choses comme l'addition, la soustraction, le modulo, … En Haskell on essaye de restreindre les types à leur fonction et rien de plus. Cela permet de documenter par le type et en second lieu on evite des erreus futures en ne rendant pas des opérations fausses disponibles. Par exemple, cela à du sens de faire une addition entre deux monnaies identiques, mais pas de sens de multiplier celles-ci. Une modélisation qui permet la multiplication permet un jour l'usage de celle-ci et ainsi l'introduction d'un bug.

L'écosystème Haskell se met aussi à jour.

• Stack propose depuis le 26 mai 2016 une nighly incluant ghc 8.0.1. On rappel que Stack est un outil de gestion de dépendance pour Haskell qui se charge de télé-charger les dépendances de votre projet et de construire celui-ci. La liste des dépendances possible est disponible sur Stackage qui réalise un travail de sélection des packets fonctionnant entre eux. C'est ainsi une garantie de pouvoir compiler votre projet avec un environnement identique à celui du developpement. Stackage est un sous ensemble de Hackage qui liste tous les packages disponibles pour Haskell. On note qu'il est très facile de commencer avec Haskell et stack puisque une fois stack installé, il suffit d'une commande pour qu'il installe lui même le compilateur et les dépendances nécessaires.
• Hoogle et Hayoo! les moteurs de recherche de fonctions dans hackage supportent la librairie base 4.9.0.0. Vous pouvez donc chercher des fonctions grâce a leurs signature.

Digressions

GHC 8.2 est prévu pour Avril 2017 d'après la page de Status.

GHC vas bientôt passer sur un nouveau système de build basé sur Shake. Je vous encourage à regarder, c'est un remplaçant intéressant à make / cmake qui est performant et typé statiquement et avec quelques fonctionnalités intéressantes.

Je vous encourage aussi à regarder l'outil Liquid Haskell qui propose de la vérification statique de prédicats sur votre code Haskell et qui est un bon complément au typage pour rendre son code encore plus robuste.