Parsing et monade, en Haskell
Voir aussi : video youtube - video peertube - code source
Précédemment, on a vu comment Haskell implémente des structures évoluées comme Functor, Applicative et Monad. On va maintenant voir comment utiliser ses structures pour réaliser du parsing, c’est-à-dire analyser un texte respectant un schéma attendu.
Rappel sur la monade Maybe
Haskell définit, entre autres, les structures Functor
, Applicative
et Monad
. Ces structures sont abondamment utilisées dans le langage et dans ses bibliothèques : IO
, liste, Maybe
…
Par exemple, Maybe
est un Functor
, ce qui signifie qu’on peut “fmapper une fonction à l’intérieur”.
Prelude> (*3) <$> Just 2
Just 6
Prelude> (*3) <$> Nothing
Nothing
Ici, on a appliqué la fonction “multiplier par 3” dans la valeur Just 2
, ce qui produit la valeur Just 6
. Et pour la valeur Nothing
, le résultat est Nothing
.
Maybe
est également une Applicative
, ce qui signifie, très grossièrement, qu’on peut également “fmapper des fonctions à plusieurs paramètres”.
Prelude> (*) <$> Just 2 <*> Just 3
Just 6
Prelude> (*) <$> Nothing <*> Just 3
Nothing
Ici, on a appliqué la fonction “multiplier” (à deux paramètres) sur des valeurs de type Maybe
. Avec Just 2
et Just 3
, on obtient Just 6
. Avec Nothing
et Just 3
, on obtient Nothing
.
Enfin, Maybe
est une Monad
, ce qui signifie qu’on peut “chainer des opérations”. Par exemple, on peut appliquer l’opération (*3)
puis l’opération (+1)
sur Just 2
, ce qui donne Just 7
.
Prelude> Just 2 >>= return . (*3) >>= return . (+1)
Just 7
Et comme Maybe
est une monade, on peut également utiliser la “notation do”.
Prelude> :{ do
Prelude| x <- Just 2
Prelude| y <- Just 3
Prelude| return (x*y)
Prelude| :}
Just 6
Introduction au parsing
Le parsing (ou analyse syntaxique), consiste à “comprendre” un texte, c’est-à-dire à transformer le texte en une valeur, d’un type attendu. Par exemple, si on veut “parser des entiers” alors le texte d’entrée "-42"
(de type String
) donnera la valeur -42
(de type Int
); par contre avec le texte d’entrée "foo"
, le parsing échouera.
Le parsing est un problème très classique en programmation. Il est notamment l’une des premières étapes du processus de compilation d’un logiciel, c’est-à-dire traduire du code source (texte) en code machine (binaire).
Regardons comment implémenter un parser de nombre entiers. Une première idée serait d’écrire une fonction qui transforme un texte en nombre entier.
parse :: String -> Int
-- exemples d'utilisations :
-- "42 foo" ~~> 42
-- "foo 42" ~~> ???
Cette première signature de fonction permet bien de parser du texte valide. Cependant, elle ne permet pas d’indiquer le cas où le texte d’entrée ne correspond pas à un entier,
Au lieu de retourner un Int
, on peut donc retourner un Maybe Int
, et ainsi gérer les entrées invalides.
parse :: String -> Maybe Int
-- exemples d'utilisations :
-- "42 foo" ~~> Just 42
-- "foo 42" ~~> Nothing
Plus généralement, on peut même définir une fonction générique, qui peut retourner un entier, du texte ou autre chose.
parse :: String -> Maybe v
-- exemples d'utilisations :
-- "42 foo" ~~> Just 42
-- "foo 42" ~~> Just "foo"
Enfin, on aimerait bien pouvoir parser plusieurs données dans le texte d’entrée, par exemple juste un entier, ou bien un entier puis un mot.
parse :: String -> Maybe (v, String)
-- exemples d'utilisations :
-- "42 foo" ~~> Just (42, " foo")
-- "42 foo" ~~> Just ((42,"foo"), "")
Ainsi, on peut voir un parser comme une fonction qui prend un texte et retourne, peut-être, la donnée trouvé et le texte restant. Cette fonction a donc le type String -> Maybe (v, String)
. A noter, qu’on peut également représenter un parser de façon différentes, par exemple pour gérer des messages d’erreur de parsing ou des analyses ambigües.
Combinateurs de parsers
Il existe de nombreuses techniques pour faire du parsing, notamment les générateurs de parsers (par exemple, avec Lex et Yacc). Les combinateurs de parsers sont une technique facile à mettre en œuvre et relativement performante. L’idée est de définir des parsers simples puis de les combiner pour définir des parsers plus complexes.
Imaginons par exemple qu’on veuille définir un parser qui cherche, dans le flux d’entrée, un nombre entier et un mot.
parseIntWord :: String -> Maybe ((Int,String), String)
-- exemple d'utilisations :
-- parseIntWord "42 foo bar" ~~> Just ((42,"foo"), " bar")
Si on a déjà des fonctions pour parser un nombre entier ou un mot,
parseInt :: String -> Maybe (Int, String)
parseWord :: String -> Maybe (String, String)
alors, on aimerait pouvoir les combiner pour définir notre nouveau parser. Par exemple, si nos parsers sont définis comme des Monad
, on peut chainer les opérations de parsing pour implémenter un nouveau parser.
= do
parseIntWord <- parseInt
i <- parseWord
w return (i,w)
De même, si les parsers sont définis comme des Applicative
, on peut combiner des parsers, en utilisant les opérateurs <$>
et <*>
.
= (,) <$> parseInt <*> parseWord parseIntWord
Définir un type Parser
Pour implémenter des combinateurs de parsers, il suffit de définir un type Parser
et de lui faire instancier les classes de types voulues (Monad
, Applicative
, etc). Par exemple, on peut définir le type suivant.
newtype Parser v = Parser { runParser :: String -> Maybe (v, String) }
Ici, le type Parser
contient un champ runParser
qui est une fonction dont le type correspond aux fonctions de parsing illustrées dans les sections précédentes.
Ainsi, définir un parser revient à définir une valeur du type Parser
et donc la fonction qu’il contient.
itemP :: Parser Char
= Parser p
itemP where p "" = Nothing
:xs) = Just (x, xs) p (x
Ici, le parser itemP
contient une fonction p
qui “parse” un caractère quelconque, c’est-à-dire qui retourne un Just
avec le tuple “valeur trouvé + texte restant”. Si l’entrée est vide et qu’on ne peut donc rien parser, la fonction p
retourne un Nothing
.
*Parser> runParser itemP "foobar"
Just ('f',"oobar")
*Parser> runParser itemP ""
Nothing
Ici, l’utilisation d’un type (Parser
) ne simplifie pas l’écriture de la fonction de parsing. Cependant, on peut désormais instancier des classes de types, ce qui va nous permettre de combiner les parsers, sans avoir à écrire explicitement des fonctions de parsing.
Par exemple, on peut considèrer qu’un Parser
est un Functor
, c’est-à-dire qu’on peut définir un nouveau parser à partir d’un parser existant et en appliquant une fonction sur le résultat parsé.
instance Functor Parser where
fmap f (Parser p) =
Parser $ \s0 -> do
<- p s0
(x, s1) return (f x, s1)
Par exemple, on peut créer un parser isf
à partir de itemP
simplement en fmappant une fonction qui retourne si le caractère parsé est 'f'
ou non.
isf :: Parser Bool
= (=='f') <$> itemP isf
On peut alors tester isf
sur différentes entrées :
*Parser> runParser isf "foobar"
Just (True,"oobar")
*Parser> runParser isf "barfoo"
Just (False,"arfoo")
De même, on peut instancer Applicative
et Monad
pour le type Parser
. On définit ainsi que Parser
est un contexte dans lequel on peut “consommer une entrée et sortir une valeur”. Et implémenter cela par une monade permet de chainer les opérations de parsing.
instance Applicative Parser where
pure ...
<*>) ...
(
instance Monad Parser where
>>=) ... (
Enfin, pour faire du parsing, il est également intéressant d’instancier la classe Alternative
.
instance Alternative Parser where
...
empty <|>) ... (
On ne s’intéressera pas ici au code exact de ces instances, mais plutôt à l’utilisation qu’on peut en faire ensuite.
Exemple : parser des entiers
A partir du type Parser
précédent et de ses instances, voyons comment on peut implémenter un parser de nombres entiers.
Tout d’abord, on peut écrire un parser digitP
qui reconnait les chiffres.
digitP :: Parser Char
= do
digitP <- itemP
x if isDigit p then return x else empty
Ce parser lit un caractère dans le texte d’entrée, grâce au parser itemP
, puis teste si c’est un chiffre, grâce à la fonction isDigit
.
*Main> runParser digitP "f"
Nothing
*Main> runParser digitP "4"
Just ('4',"")
On notera qu’il est assez courant de juste faire un test sur le résultat du parsing. On peut donc écrire une fonction satisfy
plus générale et ainsi réécrire le parser digitP
.
satisfy :: (Char -> Bool) -> Parser Char
= do
satisfy p <- itemP
x if p x then return x else empty
digitP :: Parser Char
= satisfy isDigit digitP
En fait, la bibliothèque Haskell implémente des fonctions similaires à satisfy
, qu’on peut également utiliser pour nos parsers, grâce aux classes de types.
Par exemple, la fonction some :: Alternative f => f a -> f [a]
permet de définir un parser digitsP
, qui récupère une suite de chiffre dans l’entrée.
digitsP :: Parser String
= some digitP digitsP
De même, on écrit un parser symbolP
qui lit un caractère donné.
symbolP :: Char -> Parser Char
= satisfy (==c) symbolP c
Enfin, on écrit le parser intP
qui lit un nombre entier (positif ou négatif).
intP :: Parser Int
= posIntP <|> negIntP
intP where
= read <$> digitsP
posIntP = do
negIntP <- symbolP '-'
_ <- digitsP
x return (- read x)
Ici, intP
essaie de parser un nombre positif et, s’il échoue, de parser un nombre négatif.
*Main> runParser intP "42"
Just (42,"")
*Main> runParser intP "-42"
Just (-42,"")
*Main> runParser intP "+42"
Nothing
Exemple avec Megaparsec
Les combinateurs de parser monadiques sont tellement classiques en Haskell, qu’il existe de nombreuses bibliothèques les implémentant. Par exemple avec Megaparsec, on peut implémenter l’exemple précédent de la façon suivante.
import Data.Char
import Data.Void
import Text.Megaparsec
import Text.Megaparsec.Char
type Parser = Parsec Void String
digitP :: Parser Char
= satisfy isDigit
digitP
digitsP :: Parser String
= some digitP
digitsP
intP :: Parser Int
= posIntP <|> negIntP
intP where
= read <$> digitsP
posIntP = do
negIntP <- char '-'
_ <- digitsP
x return (- read x)
En réalité, Megaparsec propose de nombreuses fonctionnalités donc on pourrait largement simplifier ce code. Cependant, comme on a essentiellement utilisé les fonctionnalités des Functor
, Applicative
, Monad
et Alternative
, notre code précédent est quasiment réutilisable tel que avec Megaparsec.
*Main> parseMaybe intP "42"
Just 42
*Main> parseMaybe intP "-42"
Just (-42)
*Main> parseMaybe intP "+42"
Nothing
Conclusion
En Haskell, les types algébriques et les classes de types permettent de définir des structures évoluées comme Functor
, Applicative
, Monad
, Alternative
…
Par exemple, un parser peut être implémenté par un type contenant une fonction qui analyse un texte d’entrée. A partir de ce type, on peut notamment instancier la classe Monad
, ce qui nous permet de combiner des parsers très facilement (et ainsi définir toute une suite d’actions de parsing, pour analyser un texte complet).
Ces “combinateurs de parsers monadique” sont d’ailleurs un exemple très classique en Haskell et il existe de nombreuses bibliothèques implémentant cette technique.