Continuons à explorer les flots de la théorie des catégories. Le précédent billet reposait sur un exemple très simple et très artificiel. L’ambition de celui-là est de proposer des techniques utilisables au jour le jour par un développeur et fondées sur l’utilisation des catégories.
Analyses
L’analyse de texte est une de ces tâches de tous les jours. Par texte, j’entends un flux de données (caractères, octets, peu importe) qui suit des règles formalisées par un langage. Certains de ces langages sont peu ambitieux, comme le format csv ; et d’autres le sont extrêmement, comme le C++. Par analyse, j’entends la transformation de ce flux brut en un résultat structuré et exploitable.
Sous forme d’explication d’une « perle fonctionnelle » dont l’article original est disponible ici, j’espère convaincre que les catégories peuvent offrir des outils de tous les jours, commodes et puissants à la fois.
Description naïve et fonctionnelle
Essayons de décrire la tâche à accomplir : nous avons un flux, nous en extrayons des données. Cela fait déjà deux types, mettons s pour le flux et a pour la donnée à extraire. Et bien sûr un troisième type, s -> a, qui est la fonction d’extraction. Cette première approche pourrait être retenue dans un langage impératif :
1
2
3
4
|
typedef int Data ;
typedef std::string Stream ;
Data parseInt(Stream& s) { … } // retourne le premier int décelable et retire du flux les caractères qui le composent |
Néanmoins elle repose sur la possibilité de modifier le flux d’entrée pour analyser le prochain entier. Outre que c’est impossible dans un langage fonctionnel pur comme Haskell, ce n’est même pas désirable, puisqu’on pourrait souhaiter appliquer deux analyseurs différents au même « moment » du flux et décider en fonction du résultat, par exemple.
Transformons un peu notre troisième type pour régler le problème: un analyseur fonctionnel prend un flux en entrée et retourne un couple (donnée, flux); ainsi le flux d’entrée est conservée à l’identique et le flux « consommé » est intégré au type de retour. Voici donc le type transformé: s -> (a, s).
Comme un analyseur peut retourner zéro ou plusieurs réponses (dans le cas d’une grammaire ambiguë, par exemple) il faut transformer encore un peu notre type; nous parvenons à : s -> [(a, s)]. Aucune réponse, l’analyseur renvoie la liste vide ; plusieurs, il renvoie la liste des candidats.
Notre monade
Nous avons donc défini le type de notre analyseur. En choisissant une chaîne de caractère pour représenter le flux, par souci de simplification, nous avons :
newtype Parser a = Parser (String -> [(a, String)])
N.B : newtype est une directive qui permet de recouvrir un type, en lui donnant un autre nom. Contrairement à un alias (ex: typedef), elle crée bien un nouveau type, sans conversion implicite possible.
Comme nous ne pouvons plus lancer directement notre analyseur, nous créons une fonction d’appoint qui lance l’analyseur :parse :: (Parser a) -> (String -> [(a, String)])
parse (Parser p) = p
il est possible dès lors de lancer l’analyseur de la façon suivante :> parse parseur flux
Prenons l’analyseur le plus simple possible, qui extrait un caractère d’une chaîne :item :: Parser Char
item = Parser (\cs -> case cs of
(c:nc) -> [(c, nc)]
_ -> [])
N.B : case x of
Cas1 -> rep1
Cas2 -> rep2
est l’équivalent d’un switch qui permet le pattern-matching
> parse item "abc"
[(a, "bc")]
Rencontre du quatrième type
Il nous reste un dernier type à explorer, peut-être le plus important. Dans notre exemple naïf, la fonction parse contenait les différentes informations nécessaires à la création de l’analyseur: la liste des caractères acceptables pour fournir un entier, le nombre de caractères à lire ou le point d’arrêt à attendre, les mesures à prendre en cas d’échec, etc. Pour peu qu’on extraie cette logique des fonctions codées « en dur », on pourra créer à loisir, par modification, enrichissement, composition, autant d’analyseurs qu’on le souhaite à partir de quelques primitives.
Le quatrième type est donc celui d’un « constructeur » d’analyseurs, qui associe à un paramètre quelconque (une liste, un caractère, une fonction, etc.) un analyseur, soit a -> Parser b.
Ce quatrième type est utilisé pour définir les méthodes monadiques, composition et identité, du type Parser.
Identité et composition
La fonction identité a justement pour signature : a -> Parser a. L’idée derrière l’identité est d’injecter a dans la monade mais en ajoutant le minimum de contexte monadique possible. Elle est donc simplement définie par :
return a = Parser (\cs -> [(a, cs)])
C’est-à-dire qu’elle renvoie un parseur qui laisse le flux inchangé et renvoie la donnée en argument.
La composition demande plus de réflexion :
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a, cs') <- parse p cs])
Cette définition très opaque demande à être explicitée :
- l’argument de concat est une list comprehension :
- 1) pour chacun des résultats (a, cs’) qui proviennent de l’analyse de cs par p,
- 2) on applique f :: a -> Parser b à a et
- 3) on analyse cs’ avec le(s) Parser(s) ainsi obtenus.
- Cette list comprehension produit donc une liste de listes de couples (a, s) ; concat permet d’en faire une seule liste (concat :: [[a]] -> [a])
Cette définition permet ainsi de composer deux analyseurs qui peuvent renvoyer une pluralité de résultats.
Enrichir la monade
Lorsqu’on regarde la définition de la composition, on s’aperçoit que, si l’analyseur p échoue, c’est-à-dire renvoie la liste vide, la fonction f ne sera jamais appelée. Un analyseur qui retourne une liste vide a donc des propriétés particulières, semblables à celle de 0 pour la multiplication :
mzero = Parser (cs -> [])
mzero >>= f = mzero
mzero est l’élément absorbant de la composition des analyseurs, de même que 0 est l’élément absorbant de la multiplication des nombres réels.
A ce stade, nous pouvons donner un premier exemple d’analyseur composé. Nous avons mis au point une primitive item qui renvoie le premier caractère d’un flux. Nous voudrions maintenant créer un analyseur qui renvoie le premier caractère s’il satisfait une certaine condition :
sat :: (Char -> Bool) -> Parser Char
sat f = item >>= \c -> if f c then return c else mzero
La do-notation
Une notation plus lisble, un sucre syntaxique est disponible dans Haskell pour manipuler les monades
| Vanilla |
do-notation |
| sat = |
sat = do |
| item >>= \c -> |
c <- item |
| if f c then… |
if f c then… |
Si on veut l’utiliser sans sauter de lignes, on peut placer les instructions entre accolades et les séparer par des points-virgules. Nous utiliserons la do-notation à l’avenir, qui est souvent plus claire. Un exercice peut-être de les reconvertir en notation salée.
Ainsi, en do-notation :
sat = do { c <- item ; if f c then return c else mzero }
> parse (sat isDigit) "123"
[('1', "23")]
> parse (sat isDigit) "abc"
[]
Pour extraire un caractère en particulier, nous pouvons créer :char :: Char -> Parser Char
char c = sat (c==)
Des analyseurs récursifs
Nous sommes également en mesure de créer des analyseurs récursifs. Si l’on veut extraire une chaîne du flux, nous pouvons par exemple écrire :string :: String -> Parser String
string "" = return ""
string (c:cs) = do { x <- char c; xs <- string cs; return (x : xs) }
Cette récursion fonctionne de la même façon que la récursion fonctionnelle habituelle. Il y a un cas d’arrêt (string "") et un cas n+1. Il est éclairant de noter que si, dans le cas n+1, la fonction 'char' échoue, elle renverra l’élément absorbant mzero et que donc la fonction 'string' sera égale à mzero :
> parse (string "abc") "abcdef"
[("abc", "def")]
> parse (string "abc") "defghi"
[]
Enrichir encore la monade
0 est l’élément absorbant de la multiplication, mais il est également l’élément neutre de l’addition : x + 0 = x
En définissant une fonction d’addition pour nos analyseurs, nous pouvons également donner ce rôle à mzero :
mplus :: Parser a -> Parser a -> Parser a
mplus p q = Parser (\cs -> (parse p cs) ++ (parse q cs))
N.B. (++) concatène deux listes
mplus concatène les listes de résultats obtenus en appliquant p et q à cs. Or [] ++ [1,2,3] = [1,2,3] et [1,2,3] ++ [] = [1,2,3]. mzero, comme 0, est ainsi, selon la relation choisie, soit l’élément absorbant, soit l’élément neutre (au passage, nous venons de définir un monoïde, c’est-à-dire un ensemble pourvu d’une opération associative qui admet un élément neutre).
Lorsque mzero et mplus sont définis pour un type, il peut être défini comme une instance de la catégorie MonadPlus.
Comme nous choisirons des exemples d’analyseurs simples et déterministes, mplus peut être restreint par un opérateur (+++) qui ne retient que le premier choix possible parmi ceux renvoyés par mplus :
(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser (cs -> case p `mplus` q of
[] -> []
(r:_) -> [r])
De l’intérêt d’être un monoïde.
Grâce à ses fonctionnalités supplémentaires, notre type Parser peut désormais gérer l’échec. Tandis que mzero permet de le représenter, mplus et son dérivé (+++) permettent de le surmonter.
On peut ainsi définir deux constructeurs d’analyseurs many et many1, qui prennent en argument un analyseur plus primitif et qui le répètent respectivement un nombre indéfini de fois et au moins une fois :
many :: Parser a -> Parser [a]
many p = many1 p +++ (return [])
Attention, return [] est différent de mzero : return [] = Parser (cs -> [([], cs)] tandis que mzero = Parser (cs -> []).
Ainsi, si many1 échoue, many retourne un résultat positif de 0 occurrences. En effet, mzero `mplus` (return []) = mzero +++ (return []) = return [] puisque mzero est l’élément neutre.
many1 :: Parser a -> Parser [a]
many1 p = do {t <- p; ts <- many p; return (t:ts) }
> parse (many1 (char 'b')) "bbc"
[(['b', 'b'], "c")]
> parse (many (char 'b')) "abbc"
[([], "abbc")]
> parse (many1 (char 'b')) "abbc"
[]
Un dernier pas avant Pascal…
Sur le même modèle, nous définissons encore deux constructeurs d’analyseurs qui nous permettront de composer un analyseur d’expressions arithmétiques simples (notre Pascaline à nous).
chainl et chainl1 prennent en argument deux analyseurs : un qui permet d’obtenir les termes de l’opération (Parser a), un autre qui permet d’obtenir l’opération elle-même (Parser (a -> a -> a)). Il reposent sur le même principe de co-récursion et de gestion d’échec par l’élément neutre et l’addition.
chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a
chainl p op a = chainl1 p op +++ return a
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do { a <- p; rest a}
where rest a = do { f <- op; b <- p; rest (f a b) } +++ return a
L’interpréteur
Maintenant vous en savez assez pour comprendre le code suivant. La beauté réside dans sa forme très proche d’une grammaire au format Backus-Naur (les déclarations de type sont placées en premier pour le faire ressortir ensuite):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| expr :: Parser Int
term :: Parser Int
factor :: Parser Int
digit :: Parser Int
symb :: String -> Parser String
addop :: Parser (Int -> Int -> Int)
mulop :: Parser (Int -> Int -> Int)
-- BNF GRAMMAR
expr = term `chainl1` addop
term = factor `chainl1` mulop
factor = digit +++ do { symb "("; n <- expr; symb ")"; return n }
symb cs = string cs
digit = do { x <- sat isDigit; return (ord x - ord '0') }
addop = do { symb "+"; return (+) } +++ do { symb "-"; return (-) }
mulop = do { symb "*"; return (*) } +++ do { symb "/"; return div } |
> parse expr "1+1-1*1"
[(1, "")] -- CQFD
Conclusion
La courbe d’apprentissage des langages fonctionnels est assez raide. Ce billet utilise un certain nombre de concepts nouveaux et la tournure d’esprit est très différente de celle d’un langage impératif. Néanmoins, une fois surmonté cet obstacle, la modularité, l’extensibilité et la généralité des constructions devient évidente. Avec les primitives décrites ici on peut facilement écrire un interpréteur pour un autre langage, un lecteur de fichiers html ou csv, etc. Je joins un code source consolidé (au format txt à convertir en .hs, qui n’est pas autorisé comme PJ par le site 
) pour ceux qui souhaiteraient expérimenter. parser-1.txt
Je profiterai de cette possibilité dans un des prochains billets pour présenter quelques concepts basiques de logique propositionnelle. Je compte également m’appesantir un peu sur les monoïdes et présenter quelques structures de données fonctionnelles intéressantes.
P.S : les questions, commentaires, suggestions, corrections, etc. sont les bienvenus!!
Exercices :
- lire l’article d’origine
- adapter le programme pour prendre en compte la possibilité d’espaces entre les chiffres (ex : "1 + 1 – 1 * 1")
- ajouter les nombres de plusieurs chiffres
- ajouter la possibilité d’élever un nombre à une puissance n
Consulter le profil
Marquer ce blog comme lu
