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.

parseIntWord = do
    i <- parseInt
    w <- parseWord
    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 <*>.

parseIntWord = (,) <$> parseInt <*> parseWord

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 
itemP = Parser p
    where p "" = Nothing
          p (x:xs) = Just (x, xs)

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
            (x, s1) <- p s0
            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
isf = (=='f') <$> itemP

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
digitP = do
    x <- itemP
    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
satisfy p = do
    x <- itemP
    if p x then return x else empty

digitP :: Parser Char
digitP = satisfy isDigit

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
digitsP = some digitP

De même, on écrit un parser symbolP qui lit un caractère donné.

symbolP :: Char -> Parser Char
symbolP c = satisfy (==c)

Enfin, on écrit le parser intP qui lit un nombre entier (positif ou négatif).

intP :: Parser Int
intP = posIntP <|> negIntP
    where 
        posIntP = read <$> digitsP
        negIntP = do
                _ <- symbolP '-'
                x <- digitsP
                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
digitP = satisfy isDigit

digitsP :: Parser String
digitsP = some digitP

intP :: Parser Int
intP = posIntP <|> negIntP
    where 
        posIntP = read <$> digitsP
        negIntP = do
                _ <- char '-'
                x <- digitsP
                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.