GHC 8.4 et 8.6

31
25
sept.
2018
Programmation fonctionnelle

GHC, le compilateur Haskell est sorti en version 8.6.1 le 22 septembre 2018.
Cette dépêche détaille les nouveautés. De plus, nous n’avions pas fait de dépêche pour la version 8.4.1 du 8 mars 2018, ainsi que pour les versions 8.4.2 et 8.4.3 ayant suivi en avril et mai ; cette dépêche tente de combler ce vide.

Les versions 8.4.2 et 8.4.3 étant principalement des versions mineures consacrées aux corrections de bogues critiques, celles‐ci ne seront pas traitées dans cette dépêche.

Comme d’habitude pour les dépêches concernant les sorties de GHC, nous reviendrons sur les nouveautés de ces versions pour conclure par un petit exemple de Haskell pour vous donner envie d’utiliser ce langage.

Sommaire

Haskell

Haskell est un langage de programmation fonctionnel pur et paresseux.

Le « fonctionnel » signifie qu’on axe l’écriture d’un programme plus sur la transformation des données, que sur des séquences d’instructions à exécuter (contrairement à un langage impératif).

Le « pur » signifie qu’on limite au maximum les effets de bord, par exemple, il n’est pas possible de modifier une valeur.

Le « paresseux » signifie que les calculs décrits ne seront réalisés qu’au moment où l’on en aura besoin. Cet aspect permet d’avoir des listes infinies en données, par exemple.

Version 8.4

Cette version a apporté beaucoup de nouveautés pour les utilisateurs et utilisatrices chevronnés de GHC. Listons rapidement quelques points :

  • L'extension TypeInType a subi des retouches, notamment en cessant de traiter l'opérateur * de façon différente du reste des opérateurs. Rappelons qu'avec cette extension et au niveau des types, cet opérateur n'indique plus le type Kind d'un type : un type est un Type, d'où le nom de l'extension. Cette notion n'est pas très rigoureuse mais GHC n'est pas non plus un outil de preuve mécanique ! En réalité, TypeInType est un ajout incrémental au fonctionnalités de l'extension PolyKinds et apparentées et sera complètement absorbée & dépréciée par celles-ci dès la version 8.6.
  • Le découplage des classes Semigroup et Monoid a franchi une nouvelle étape. Pour rappel, le changement le plus visible est que l'opérateur <> se trouve désormais dans le module Data.Semigroup alors qu'avant le découplage il appartenait à Data.Monoid. Conceptuellement, les Semigroup sont l'ensemble des types qui admettent une opération binaire associative, comme le +. Un Monoid est un Semigroup a qui on ajoute un élément neutre, comme le 0.
  • Les constantes litérales hexadécimales pour les nombres flottants, grâce à l'extension HexFloatLiterals, permettent de representer un nombre flottant en hexadécimal, 0x0.1p4 == 1.0.

Version 8.6

La suite de cette dépêche est consacrée aux changements de GHC 8.6. Cette liste n'est pas exhaustive et représente la vision des auteurs sur les points importants, amusants, ou pouvant être illustrés simplement.

Les nouveautés sont intégrées au sein de GHC par le biais d'extensions, que l'utilisateur aura la liberté d'activer au non. Certaines extensions deviennent officielles lors de la rédaction du Haskell Report, le dernier datant de 2010 et le prochain étant prévu pour 2020.

Entre temps, les développeurs Haskell doivent activer de nombreuses extensions. Sous une apparente contrainte, cela apporte au langage une capacité d'évolution assez intéressante puisque les développeurs ne se refusent pas à implémenter des changements importants sous la forme d'extensions.

Extension à la syntaxe

NumericUnderscores

L'extension NumericUnderscores permet de mettre des _ dans ses nombres, comme 123_456_789. Cela aide la lisibilité.

Notons que jusqu'à présent on pouvait facilement exprimer des grands nombres "ronds" en utilisant la notation exponentielle, l'extension NumDecimals permettant d'obtenir des nombres entiers le cas échéant.

Prelude> 1e3
1000
Prelude> 1.123e3
1123
Prelude> :type 1.123e3
1.123e3 :: Num p => p  -- Un nombre, autant un flottant qu'un entier
Prelude> :t 1.1234e3
1.1234e3 :: Fractional p => p -- Ici c'est forcement un flottant, car la valeur 1123.4 ne peut pas être représentée en entier.

-- La nouvelle syntaxe
Prelude> 1_123
1123

BlockArguments

La nouvelle extension BlockArguments permet un groupement implicite différent des expressions et tout particulièrement des blocs do et des fonctions anonymes.

Par exemple, le bloc suivant va demander le nom de l'utilisateur et le saluer :

do
  putStrLn "Quel est votre nom ?"
  name <- getLine
  putStrLn ("Bonjour " ++ name)

Pour effectuer cette action en boucle, on peut utiliser forever qui prend en argument l'action à répéter à l'infini. Jusqu'alors, il fallait mettre des parenthèses disgracieuses à mon goût :

forever (do
  putStrLn "Quel est votre nom ?"
  name <- getLine
  putStrLn ("Bonjour " ++ name)
  )

Ou utiliser l'opérateur ($) qui est peu apprécié car déroutant pour les débutants :

forever $ do
  putStrLn "Quel est votre nom ?"
  name <- getLine
  putStrLn ("Bonjour " ++ name)

Dans les deux cas, c'est fort peu confortable.

La nouvelle syntaxe, avec l'extension BlockArguments, est maintenant :

forever do
  putStrLn "Quel est votre nom ?"
  name <- getLine
  putStrLn ("Bonjour " ++ name)

Cela prend tout son sens sur des tests unitaires, comme avec HSpec :

describe "factorials" $ do
  it "must be equal 1 when argument is 0" $ do
     fact 0 `shouldBe` 1
  it "must always be positive " $ do
     property $ \(Positive x) -> fact x >= 1
  it "is strictly growing" $ do
     property $ \(Positive x) -> fact x < fact (x + 1)

Notez l'abus de ($), qui peut maintenant se remplacer par :

describe "factorials" do
  it "must be equal 1 when argument is 0" do
     fact 0 `shouldBe` 1
  it "must always be positive" do
     property \(Positive x) -> fact x >= 1
  it "is strictly growing" do
     property \(Positive x) -> fact x < fact (x + 1)

Environment de development

Améliorations des « typed holes »

Les typed holes sont une syntaxe où le développeur peut laisser des trous dans son programme et demander au compilateur de l'aide pour les combler.

_ && True

Cette expression évalue le ET booléan entre _ et True. _ est un typed hole, ainsi le compilateur va simplement nous renvoyer un message d'erreur incluant le type déduit de l'expression, ici Bool :

<interactive>:28:1: error:
    • Found hole: _ :: Bool
    • In the first argument of ‘(&&)’, namely ‘_’
      In the expression: _ && True
...

Depuis GHC 8.6, le support s'améliore et le compilateur fait aussi des suggestions à partir des symboles actuellements accessibles :

      Valid hole fits include
        otherwise :: Bool
          (imported from Prelude (and originally defined in GHC.Base))
        False :: Bool
          (imported from Prelude (and originally defined in GHC.Types))
        True :: Bool
          (imported from Prelude (and originally defined in GHC.Types))

À terme on pourra imaginer une intégration plus poussée dans les éditeurs avec de l'auto-complétion, ou avec la documentation et la fonction interactive :doc.

Command :doc dans le shell

La nouvelle commande :doc permet d’accéder à la documentation des fonctions dans le shell ghci.

Le shell est un des outils les plus importants pour un développeur Haskell, on y passe beaucoup de temps à expérimenter. Jusqu'à présent on pouvait obtenir des informations sur le type :

>>> :type reverse
reverse :: [a] -> [a]

On peut aussi maintenant demander la documentation associée:

>>> :doc reverse
 'reverse' @xs@ returns the elements of @xs@ in reverse order.
 @xs@ must be finite

Le code Haskell étant documenté par Haddock, un langage de documentation intégré à Haskell, on peut maintenant accéder à ces informations dans le shell. Le fait d'avoir un point d'entrée standardisé nous laisse imaginer un meilleur support d'outils dans le futur, tel qu'une intégration aux éditeurs de texte.

L'argument -fshow-docs-of-hole-fits devrait permettre une interaction entre la documentation et les "typed holes" du paragraphe précédent en affichant la documentation en face des suggestions.

Extension au mécanisme de programmation générique

DerivingVia

Cette nouvelle extension augmente le mécanisme de dérivation présent dans GHC. Pour bien comprendre cette nouvelle fonctionnalité, il faut faire un petit rappel sur un point clé d'Haskell, les type-class et le mécanisme de dérivation.

Notion d'instance et de class

En Haskell, une class est une interface et une instance est l’implémentation de celle-ci pour un type. Le vocabulaire n'est pas du tout le même que celui utilisé plus habituellement dans des langages objets.

Par exemple, on peut imaginer la classe Shape :

class Shape t where
   area :: t -> Float

Qui propose la fonction area qui, appliquée à n'importe quel type implémentant le type-classe Shape, va retourner sa surface. Par exemple :

-- Création de deux types, 'Square' et 'Rectangle'
data Square = Square Float
data Rectangle = Rectangle Float Float

-- Implémentation de 'area' pour les deux
instance Shape Square where
  area (Square side) = side * side

instance Shape Rectangle where
  area (Rectangle a b) = a * b

Avec ici deux types, Square et Rectangle et leur implementation instance de la classe.

On peut donc maintenant écrire des fonctions polymorphiques fonctionnant uniquement sur les instances de Shape :

print_area shape = do
    putStrLn "La surface de la forme est :"
    print (area shape)

Nous avons vu ici la création d'instances manuelle.

deriving

Haskell propose le mécanisme de deriving qui permet de dériver automatiquement des instances pour nos types. Ce mécanisme a beaucoup évolué et on peut :

  • dériver des comportements proposés par le compilateur ou par une bibliothèque tierce, ici pour le type Point3D nous dérivons les instances Show et Serialize qui permettent d'afficher (avec show) et de sérialiser avec encode / decode :
data Point3D = Point3D Float Float Float deriving (Show, Serialize)
  • dériver des comportements d'un type interne si le type n'est qu'une encapsulation du précédent. Par exemple :
data Counter = Counter Int deriving (Num)

Counter est maintenant un type qui contient un Int, qui implémente toute la classe Num de façon similaire aux Int, donc il implémente les opérations primaires comme l'addition, la soustraction, etc. Mais ce type n'est pas compatible avec un Int.

C'est très pratique pour faire des interfaces robustes.

DerivingVia

DerivingVia est une nouvelle extension qui ajoute une nouvelle manière de dériver. On peut imaginer plusieurs types ayant la même représentation interne et pour lesquels on veuille dériver le même comportement. Au lieu de recopier ce comportement plusieurs fois, on peut faire appelle à derive via.

Par exemple :

-- `Normalize` regroupe tous les types pouvant être "normalisés"
class Normalize t where
   normalize :: t -> t

-- Un triplet de points représentant une couleur
newtype RGBColor = RGBColor (Float, Float, Float)

-- Son instance de 'Normalize'
instance Normalize RGBColor where
   normalize (RGBColor (a, b, c)) = RGBColor (a / s, b / s, c / s)
       where s = sqrt (a * a + b * b + c * c)

-- Le même travail est à répéter pour ces nouveaux types, similaires. 
-- On va gagner du temps avec `deriving via`
newtype Direction = Direction (Float, Float, Float) deriving Normalize via RGBColor

newtype Position = Position (Float, Float, Float) deriving Normalize via RGBColor

Ce travail permet ainsi une plus grande réutilisation. L'idée étant que souvent des types représentant des choses incompatibles peuvent avoir des fonctionnalités similaires. On pourrait citer l'exemple des monnaies. Un "Dollar" est incompatible avec un "Euro", ainsi l'addition entre les deux n'a pas de sens. Cependant l'addition entre euros est exactement la même que l'addition entre dollars, il est donc dommage d’implémenter celle-ci pour chaque monnaie.

Greffons de compilation

GHC propose une infrastructure de greffons (plugins) permettant aux utilisateurs d'étendre le compilateur sans avoir à mettre les mains dans un code complexe et sans avoir à compiler une nouvelle version du compilateur complet.

On trouve trois types de greffons :

  • Les greffons d'optimisation, qui permettent d'étendre la phase de génération de code. Par exemple, Herbie permet de réécrire des calculs afin de les rendre numériquement plus stables.
  • Les greffons de validation de type vont étendre la phase de validation des types. Par exemple, thoralf permet de sous-traiter à un solveur SMT des preuves de type. Cela permet d'exprimer assez simplement des preuves plus complexes.

Les greffons sources

Introduits par GHC 8.6, ils permettent à un développeur d'observer le code source après analyse syntaxique afin de transformer celui-ci ou de simplement le passer en parallèle à une tâche annexe.

Ils ont comme intérêt, à mon sens, de permettre de réaliser en parallèle de la compilation d'autres tâches ayant besoin de l'analyse syntaxique et de réutiliser celle-ci. Lorsque je compile mon code, je génère aussi la documentation, je passe un linter dessus, je passe un formateur dessus et je génère des informations comme une base de données des fonctions définies, un graphique des modules, etc. Chacun de ces outils demande actuellement une nouvelle phase d'analyse syntaxique réalisée par un outil externe qui implémente souvent sa propre version limitée et défectueuse du parseur. Pouvoir réaliser ces tâches annexes pendant la compilation principale serait donc un gain en temps et en qualité.

GHC 8.6 n'etait pas encore sorti que de nombreux projets s’essayaient à la tache :

  • Une réécriture de graphmod permet de générer des graphiques représentant les dépendances entre modules Haskell.
  • hlint-source-plugin permet de réaliser un lint, c'est à dire une analyse du style du code.
  • idiom-bracket L'auteur a judicieusement remarqué qu'il est rare de mettre entre parentheses des listes : on va rarement écrire ([f,g,h]) car les parenthèses semblent redondantes. L'auteur "vole" donc cette syntaxe pour exprimer une toute nouvelle construction.

Quantified Constraints

Ceci est une nouveauté phare de cette version qui simplifie les contraintes lors de la définition d'une instance.

Prenons un exemple simple pour la mise en contexte. Si on veut définir une instance de Show pour une liste de a, on écrira :

instance Show a => Show [a] where
   show = ...

Ce qui veut littéralement dire que [a] admet une instance de Show si et seulement si a admet une instance de Show. Ou, dit autrement, on peut afficher une liste de a si on sait afficher a. Cela a du sens, on va définir l'affichage pour la liste, en déléguant l'affichage de chaque élément aux fonctions déjà définies pour ces éléments.

Prenons l'exemple plus élaboré d'un type User paramétré :

data User f = User
  { nom :: f String
  , age :: f Int
  , superUtilisateur :: f Bool
  }

Le paramétrage par f permet d'utiliser le même type pour representer de nombreuses variations :

  • User Identity est, à un détail près, un record User sans le paramétrage, il contient donc une String, un Int et un Bool.
  • User Maybe est un User dont tous les champs sont des Maybe, c'est à dire qu'ils peuvent avoir une valeur ou pas. C'est pratique en première étape d'un système de validation, par exemple, on pourrait imaginer une fonction de validation validation :: User Maybe -> Maybe (User Identity).
  • User [] contient une liste pour chaque champs. C'est pratique pour faire du Structure of Array. On pourrait même imaginer une fonction toArray :: [User Identity] -> User [] et fromArray :: User [] -> [User Identity] permettant de passer d'une liste d'utilisateur à un utilisateur contenant des listes et inversement.

Vous pouvez lire cet article sur les functor functors pour plus de détails sur cet usage.

Il n'est pas aisé de dériver des instances pour User. En effet, pour pouvoir être affiché, un User f doit pouvoir afficher chaque champs, c'est-à-dire :

  • f String pour le nom
  • f Int pour l'age
  • f Bool pour le superUtilisateur

Ainsi, pour dériver automatiquement l'instance de Show, il faudrait écrire :

deriving instance
   ( Show (f String)
   , Show (f Int)
   , Show (f Bool)
   ) => Show (User f)

Cette écriture est lourde, source d'erreur, peu générique et évolue difficilement. Par exemple, si demain j'ajoute un champs droitUtilisateur :: f Droits, je devrais ajouter une clause Show (f Droits) à toutes mes instances.

Ce qui serait agréable c'est de pouvoir dire que si on peut afficher un f b, alors on peut afficher un User f. C'est ce qui est maintenant possible avec QuantifiedConstraints :

deriving instance (forall b. Show b => Show (f b)) => Show (User f)

Notez le forall b. Show b => Show (f b) qui signifie que quel que soit b, si on peut afficher b, alors si on sait afficher f b alors on sait afficher User f.

Cette nouvelle extension apporte donc une très grosse simplification de cas d'instances complexes sur des types paramétriques.

Plus de tests d’exhaustivité

GHC réalise des tests d'exhaustivité sur les cases et les appels de fonctions. Par exemple, le code suivant :

data Couleur = Rouge | Vert | Bleu

phraseIdiote Rouge = "La lune est rouge, du sang a coulé cette nuit"
phraseIdiote Vert = "Les martiens sont tous verts"

Il manque le cas pour Bleu et le compilateur va s'en rendre compte:

<interactive>:16:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘phraseIdiote’: Patterns not matched: Bleu

Cette capacité est maintenant étendue aux guard et à la syntaxe if étendue. Par exemple, le code suivant ne gère pas le cas ou b est False :

-- si 'b' est True, retourne '1', sinon... ?
foo b = if | b -> 1

Ce code va maintenant générer un warning lors de la compilation.

Plus de constant folding

GHC effectue maintenant plus de constant folding lors de la compilation.

Par exemple, le code (5 + 4*x) - (3*x + 2) est équivalent à 3 + x tout en coûtant deux multiplications, une addition et une soustraction de moins.

Extension de PartialTypeSignatures

PartialTypeSignatures est permet de ne pas expliciter tous les types dans une signature.

On rappelle qu'en Haskell, les types sont inférés, donc il n'est presque jamais nécessaire de mettre de signature aux fonctions. Cependant cela permet de temps en temps de rendre le code plus lisible, de documenter ou de rendre la signature moins polymorphique.

PartialTypeSignatures permet de ne préciser que les types necessaires, les autres étant déduits via l'inférence de type.

C'est particulièrement utile avec certains types complexes ayant beaucoup de contraintes. Par exemple, la signature suivante qui cherche une valeur dans une liste:

-- 'Eq v' signifie que les valeurs dans la liste doivent pouvoir être comparées 
search :: Eq v => [v] -> v -> Bool

Pourrait être simplifiée en:

_ => [v] -> v -> Bool

C'est très pratique lors de l'usage de bibliothèques ayant de nombreuses contraintes.

Depuis GHC 8.6, on peut maintenant utiliser le symbole _ dans plus de contextes, et tout particulièrement lors de la définition d'une instance, par exemple deriving instance Show v => Show [v] qui dérive l'affichage de toute liste dont le type interne dérive l'affichage, pourra être écrit _ => Show [v].

Heap View

http://hackage.haskell.org/package/ghc-heap-view est maintenant integré à ghci (le shell) et permet d'observer l'organisation en mémoire des valeurs manipulées. https://patrickdoc.github.io/heap-view.html est une bonne introduction.

Par exemple :

>>> import GHC.Exts.Heap
>>> p = sum [1..10::Int]

Cette valeur n'est pas encore évaluée :

>>> getClosureData p
APClosure {info = StgInfoTable {entry = Nothing, ptrs = 0, nptrs = 0, tipe = AP, srtlen = 0, code = Nothing}, arity = 26827633, n_args = 0, fun = 0x0000004201996250, payload = []}

Chaque objet en mémoire en Haskell commence par une table d'information info qui contient des informations pour le garbage collector et pour l'évaluation. Ici on peut voir que le tipe est AP, une fonction à appliquer.

Nous pouvons forcer l'évaluation de la valeur :

>>> p
55
>>> getClosureData p
ConstrClosure {info = StgInfoTable {entry = Nothing, ptrs = 0, nptrs = 1, tipe = CONSTR_0_1, srtlen = 0, code = Nothing}, ptrArgs = [], dataArgs = [55], pkg = "ghc-prim", modl = "GHC.Types", name = "I#"}

Ici, on a une ConstrClosure, c'est à dire un constructeur, un type concret. 55 apparaît bien dans la liste des arguments et on peut voir que le constructeur est I#, le wrapper autour des entiers machine.

Cela sera sans doute un très bon outil pour comprendre les comportements en mémoire de certains algorithmes.

On rappelle que le shell ghci vient avec :sprint qui permet d'observer moins de choses, mais au moins l'évaluation paresseuse, les êléments non évalués étant remplacés par _ :

Création d'une liste l contenant des chaines, tout est paresseux, d'ou l = _ :

>>> l = ["Hello", "Youpi", "Yoda", "You", "Are", "Beautiful"]
>>> :sprint l
l = _

Récupérer le premier élément provoque l'évaluation de seulement celui-ci :

>>> head l
    "Hello"
>>> :sprint l
l = "Hello" : _

Calculer la longueur de la liste provoque l'évaluation de celle-ci, mais pas des sous éléments. Le premier est toujours évalué.

>>> length l
    6
>>> :sprint l
l = ["Hello",_,_,_,_,_]

map head l va récupérer le premier caractère de chacun des éléments de la liste, ce qui va provoque l'évaluation partielle de ceux-ci :

>>> map head l
    "HYYYAB"
>>> :sprint l
l = ["Hello",('Y' : _),('Y' : _),('Y' : _),('A' : _),('B' : _)]

La recherche d'un élément =="You" est passionnante. "Hello" est déjà évalué, il ne change rien. "Youpi" doit être évalué jusqu'au i pour réaliser que ce n'est pas la bonne valeur. "Yoda" pareil. "You" est totalement évalué et l’exécution s'arrête :

>>> any (=="You") l
    True
>>> :sprint l
l = ["Hello",('Y' : 'o' : 'u' : 'p' : _),('Y' : 'o' : 'd' : _),
     "You",('A' : _),('B' : _)]

La création d'une liste paresseuse qui contient la longueur de tous les éléments de la liste ne change rien :

>>> l2 = map length l
>>> :sprint l
l = ["Hello",('Y' : 'o' : 'u' : 'p' : _),('Y' : 'o' : 'd' : _),
     "You",('A' : _),('B' : _)]

Mais l'observation du dernier élément force l'évaluation du dernier élément de la première liste :

>>> last l2
    9
>>> :sprint l
l = ["Hello",('Y' : 'o' : 'u' : 'p' : _),('Y' : 'o' : 'd' : _),
     "You",('A' : _),"Beautiful"]

L'évaluation paresseuse c'est formidable ;)

MonadFail

Jusqu'à présent, la classe Monad incluait une fonction fail qui était utilisée en cas d'erreur de pattern dans une do notation. Par exemple, le code suivant, qui fonctionne pour toutes les Monads :

f = do
  Just x <- anOperation
  pure x

Peut échouer, car il n'y a aucune garantie que la valeur matchée par Just x ne sera pas Nothing. Ainsi Monad incluait une fonction fail pour permettre de surcharger ce comportement.

Il y a des cas où l'implementation de fail a du sens. Dans les autres cas, fail est implementé comme une exception. Ce qui veut dire que du code qui a l'air parfaitement anodin peut en fait planter lors de l'exécution, ce qui est inadmissible (avis d'un auteur ;) en Haskell où on préfère les erreurs statiques que les erreurs d'exécution.

Il a donc été décidé de déplacer fail de la classe Monad dans une super classe de Monad, appelée MonadFail.

Ainsi, le code suivant, qui ne peut pas échouer :

f = do
   x <- anOperation
   pure x

Aura comme type Monad m => m t et est garanti sans exception.

Alors que le code suivant, qui peut échouer :

f' = do
  Just x <- anOperation
  pure x

Aura comme type MonadFail m -> m t et le comportement en cas d'erreur dépend de la Monad utilisée. Par exemple :

  • La monad de liste va ignorer l'élément associé à cet echec
  • Une opération d'IO va réaliser une exception
  • Une monad type Maybe va renvoyer Nothing.

La différence permet de faire apparaître la notion d'erreur possible dans le type. Bien sûr, l'utilisation de f' dans un contexte Monad (et non MonadError) provoquera une erreur de compilation.

L'honneur est donc sauf, moins d'erreur à l'exécution, plus d'erreurs à la compilation.

StarIsStar

StarIsStar est une nouvelle extension activée par défaut (et désactivable avec NoStarIsStar) qui permet d'utiliser * comme symbole pour Type : le type de la plupart des types. Le but est à terme de désactiver cette extension afin de libérer le symbole * pour qu'il puisse être utilisé comme symbole de multiplication au niveau du type.

Ce n'est pas clair ? Il faut voir un type comme un ensemble de valeurs possibles. Par exemple, Int est l'ensemble des valeurs 0, 1, 2, 3, ..., -1, -2, -3, .... Il existe aussi un ensemble des types, qui s'appelle Type (ou * avec StarIsStar), cet ensemble contient Int, Double, … et tous les types que vous allez créer.

Cela a de l’intérêt car on peut aussi définir des types qui ne sont pas dans cet ensemble Type, c'est pratique pour faire des opérations au niveau du type.

Et le problème c'est que, au niveau du type, n'importe quel symbole Haskell peut être utilisé pour implémenter un opérateur, sauf * qui est un cas particulier pour représenter Type, d'où la motivation pour faire disparaître celui-ci afin de simplifier le compilateur et permettre son utilisation en tant qu'opérateur.

Analyser le journal des modifications de LinuxFr.org

Comme souvent avec les dépêches sur une nouvelle sortie de GHC, celle-ci en profite pour montrer un exemple d'utilisation de Haskell dans la nature ! Il s'agit d'analyser syntaxiquement et de stocker de façon personnalisée les changelogs de ce site où une entrée typique est générée sous cette forme :

commit ac34cc5d787f569a237d16a2ec8be994c2a37acc
Author: Bruno Michel <bmichel@menfin.info>
Date:   Fri Aug 3 15:58:34 2018 +0200

    Revert putting the phare on top of the logo and sidebar

Un modèle syntaxique correspondant en BNF où les chevrons représentent les terminaux :

Eol         ::= <fin_de_ligne>

Lettre      ::= <lettre_minuscule> | <lettre_majuscule>

Condensat   ::= <lettre_minuscule> | <chiffre> | Eol

Espace      ::= <simple_espace> | <tabulation>

Début_e     ::= <<>
Email       ::= Début_e | Lettre | <@> | <.> | <-> | <_> | Fin_e
Fin_e       ::= <>>

Author      ::= Lettre | Espace | Email | Eol

Date        ::= Lettre | <chiffre> | <:> | <+> | <-> | Espace | Eol

Message     ::= Lettre | Espace | <,> | <-> | <.> | </> | <:> | Eol

Log         ::= Condensat | Author | Date | Message | <fin_de_fichier>

Dans cette grammaire, on remarque d'emblée que tous les symboles, terminaux ou non, sont traités de façon ad hoc, même pour les cas ayant des standards les définissant très précisément : adresses électroniques, condensats et dates notamment. Cela vient d'une volonté de simplifier au maximum l'exemple. La suite de cette section montrera comment s'y prendre en Haskell pour exprimer ce que Log exprime en BNF.

Au sein de l'écosystème Haskell, il existe plusieurs bibliothèques destinées à traiter des grammaires comme celle-ci dont un certain nombre peuvent être regroupées sous l'appellation “Parser Combinators”. Ainsi de parsec qui a longtemps été la vitrine de telles bibliothèques, du fait d'un nom trop bien choisi entre autres choses (le c étant pour … “combinators”). Il y a bien sûr d'autres bibliothèques qui s'y prennent autrement, à l'instar de happy et alex qui sont utilisées pour gérer GHC lui-même. Notre exemple utilisera megaparsec, une alternative de parsec. Dans les paragraphes qui vont suivre, les blocs de code seront tirés d'un fichier source appelé Depeche.hs. Voici l'en-tête qui déclare les modules requis :

module Depeche where

import           Data.Either                        -- base
import           Data.Foldable                      -- base
import           Data.Maybe                         -- base
import           Data.Void                          -- base
import           Prelude                            -- base
import           Text.Megaparsec                    -- megaparsec
import           Text.Megaparsec.Char               -- megaparsec
import           Text.Read                          -- base
import qualified Text.Megaparsec.Char.Lexer as Lx   -- megaparsec
import           Data.Time                          -- time

Notons qu'à part megaparsec et time, une seule bibliothèque livrée avec GHC fournit les modules requis par cet exemple. La dernière déclaration est dite « qualifiée » dans le sens où toute entité venant de ce module devra être précédée soit du nom de celui-ci, soit d'un préfixe à préciser (ici Lx) ; c'est pour éviter la collision entre les espaces de noms de ce module et du reste des modules de megaparsec qui exposent des entités homonymes. Définissons ensuite les types représentant une entrée du journal :

data Author = MkAuthor
    { firstName :: String
    , lastName  :: String
    , emailAddr :: String
    } deriving Show


data ChangelogEntry = MkEntry
    { commitHash    :: String
    , commitAuthor  :: Author
    , commitDate    :: UTCTime
    , commitMsg     :: String
    } deriving Show

Author est un enregistrement à trois champs, chacun étant une chaîne de caractères. Une valeur de ce type est créée avec la fonction MkAuthor, automatiquement générée par le compilateur, et deriving Show permet de generer automatiquement la fonction show d'affichage. Une description similaire est applicable à ChangelogEntry. UTCTime provient de Data.Time et représente une date.

Passons ensuite aux parseurs qui auront tous ce format :

type Parser = Parsec Void String

Ainsi, un parseur est un type composite qui met ensemble un type Parsec, ne se préoccupe pas de personnaliser la gestion des erreurs (Void) et prend en entrée une chaîne de caractères de type String. Tout ça est tout bonnement synonyme de Parser pour nous. Parser a est donc le type qui décrit un parseur d'une valeur de type a. Viennent ensuite les parseurs proprement dit, en commençant par les « sous-parseurs » :

mixAlnumPunc :: [Char] -> Parser String
mixAlnumPunc xs = some (alphaNumChar <|> oneOf xs)

parseEmail, parseHash, parseLetters, parseMessage :: Parser String

parseEmail      = between
    (single '<')
    (single '>')
    (mixAlnumPunc "@.-_")

parseHash       = many (lowerChar <|> digitChar)

parseLetters    = many letterChar

parseMessage    = mixAlnumPunc " ,-./:"

Cet extrait ressemble furieusement à la grammaire de départ ! Veut-on des Lettre ::= <lettre_minuscule> | <lettre_majuscule> ? Tient : many (lowerChar <|> upperChar) ! Ou alors veut-on un tiret ou un espace souligné, Tiret_ou_blanc_souligné ::= <-> | <_> ? Et bien, voilà : single '-' | single '_' ! Bref, avec les combineurs de parseurs, on définit les éléments syntaxiques d'une manière très proche des notations usuelles.

Il reste maintenant à mettre ensemble ces petites briques pour bâtir le parseur qui nous intéresse. Si le ciment/sable/boue/gravier joue le rôle de liaison entre plusieurs briques, les différents caractères d'espacement jouent un rôle similaire lorsqu'il s'agit d'assembler des éléments syntaxiques dans notre grammaire. Le sous-parseur suivant permet de passer outre tout espace éventuel avant de passer la main à un autre parseur, ceci afin de ne garder que les briques :

ignoreBlanks :: Parser a -> Parser a
ignoreBlanks = Lx.lexeme (Lx.space space1 empty empty)

Lx.lexeme est une fonction permettant de décrire un parseur d'espace blanc. Elle peut aussi traiter les commentaires, ce que nous ignorons ici avec empty.

Alors, où est le principal parseur ?

parseEntry :: Parser ChangelogEntry
parseEntry = do
    _               <- ignoreBlanks (string "commit")
    theHash         <- ignoreBlanks parseHash
    _               <- ignoreBlanks (string "Author:")
    theFirstName    <- ignoreBlanks parseLetters
    theLastName     <- ignoreBlanks parseLetters
    theEmail        <- ignoreBlanks parseEmail
    _               <- ignoreBlanks (string "Date:")
    theDate         <- ignoreBlanks parseUTC -- Voir plus bas
    theMessage      <- ignoreBlanks parseMessage
    pure $ MkEntry
        theHash (MkAuthor theFirstName theLastName theEmail)
        theDate theMessage

Extraire des composants syntaxiques dans le changelog revient dans notre cas à y aller méthodiquement de gauche à droite et de haut en bas, une étape donnée se déroulant en commençant exactement là où les précédentes étapes se sont arrêtées. La notation do … ← … sert à séquencer les transitions pour faire intervenir un sous-parseur à chaque fois. Là où le résultat intermédiaire est inutile, il est immédiatement abandonné en l'envoyant dans le joker _. À la fin du parsing, tous les éléments sont réunis pour invoquer le constructeur MkEntry.

Pour terminer, voici une utilisation de notre parseur :

main :: IO ()
main = do
    fromStdIn <- getContents
    print $
        find (\ x -> commitHash x == "a9bfdd7b21320ba18497519f4e2e471d1529c448") $
        fromRight [] $
        runParser (someTill parseEntry eof) "Changelog" fromStdIn

Décryptons un peu ce code condensé :

  • someTill parseEntry eof est un parseur qui utilise parseEntry plusieurs fois jusqu'à trouver une fin de fichier eof.
  • runParser p "Changelog" fromStdIn applique le parseur p sur l'entrée fromStdIn qui aura le nom de Changelog dans les messages d'erreurs.
  • Un parseur peut échouer et renvoyer Left unMessageD'erreur ou Right leResultat. La fonction fromRight nous permet d'ignorer l'échec et de le remplacer par une liste vide [].
  • find va chercher dans cette liste une entrée avec un numéro de commit précis.

Pour compiler et expérimenter avec le programme dans le Shell, faire :

ghc Depeche.hs
./Depeche < 'linuxfr_changelog'

On pourra aussi l’exécuter directement sans compilation, ce code n'étant pas très demandeur en terme de ressource, il s’exécutera sans souci en mode interprété avec runhaskell Depeche.hs < linuxfr_changelog.

En conclusion, à partir d'une grammaire utilisant les notations habituelles comme BNF, les bibliothèques comme megaparsec permettent de définir confortablement des analyseurs syntaxiques, le confort résidant dans la similitude entre leur syntaxe à la fois avec des syntaxes comme BNF et du langage Haskell lui-même.

Addendum
Le parsing des dates utilise les fonctionnalités de parsing de la libraire Data.Time. En voici le code :

dateFormat = "%a %b %e %H:%M:%S %Y %Z"

parseUTC :: Parser UTCTime
parseUTC = do
  s <- manyTill anySingle eol
  parseTimeM False defaultTimeLocale dateFormat s
  • manyTill anySingle eol parse jusqu'à la fin de ligne tous les caractères qui seront ensuite passés à parseTimeM.
  • parseTimeM ... va parser la chaîne de caractère en fonction de la chaîne de format spécifiée par dateFormat. On voit ici une des forces de Haskell qui est la possibilité de combiner les fonctions de Data.Time et de Text.Megaparsec ensemble.

Conclusion

GHC 8.6.1 n’apporte pas forcement des nouveautés capables de motiver à l’utilisation de Haskell, mais apporte son lot de petites améliorations qui, ensemble, rendent GHC plus pratique.

GHC 8.8, prévu pour mars 2019 devrait apporter son lot de nouveautés avancées au niveau du système de type, et fait quelques promesses concernant les performances du compilateur et du code généré.

Envoyer un commentaire

Suivre le flux des commentaires

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