Conception d’un parser simple en programmation fonctionnelle

Une calculatrice en programmation fonctionnelle

Dans cet exercice, nous allons découvrir comment implémenter une calculatrice de A à Z en utilisant des techniques de programmation fonctionnelle pure. Nous verrons le principe de base d’un parser, et les possibilités offertes par une interface de type applicative functor. Aucune connaissance préalable de librairie n’est requise pour cet exercice, en dehors du prelude de Haskell dont nous utiliserons les fonctions de base. Nous définirons tout ce qui nous sera utile nous-même, et le code complet fera moins de 100 lignes. Cette implémentation pourra ainsi être traduite facilement dans un autre langage de programmation.

Le but de notre exercice est la conception d’une calculatrice de base, dont l’utilisation se fera comme suit :

> evalExpr "(12 - 2) * 5"
Just 50
> evalExpr "12 - 2 * 5"
Just 2
> evalExpr "3 - foobar"
Nothing

Commençons le module Calc

module Calc where

Définition du type d’une expression algébrique

Les opérations que notre calculatrice peut traiter sur les entiers sont les additions, soustractions et multiplications.

data Expr = Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Lit Integer

L’évaluateur d’une telle expression est simple à définir de façon récursive.

eval :: Expr -> Integer
eval e = case e of
  Add a b -> eval a + eval b
  Sub a b -> eval a - eval b
  Mul a b -> eval a * eval b
  Lit n   -> n

Définition du type d’un parser

Nous allons définir un type qui correspond à un parser basique. Sous sa forme la plus simple, un parser est une fonction (->) qui prend un flux (String) en paramètre, et qui va analyser le début de ce flux jusqu’à pouvoir produire, si possible, (Maybe) un résultat. Dans ce cas, le résultat sera retourné, ainsi que le restant du flux (partie non-traîtée). Si aucun résultat ne peut être produit, alors rien du tout ne sera retourné (Nothing). Le type est paramétré par r, qui définit le type du résultat que le parser peut produire. Un parser qui lirait un nombre entier dans le flux pourrait produire des Integer, son type serait donc Parser Integer.

type Parser r = String -> Maybe (r, String)

Primitives pour manipuler les parsers

Muni de notre type de donnée définissant la forme générale d’un parser, nous allons maintenant définir des primitives qui nous seront utiles pour les manipuler. Nous en profiterons pour définir une interface de type « applicative functor », permettant de combiner et d’enchaîner des parsers ensembles.

Tout d’abord, nous aurons besoin d’une primitive qui nous permet de construire un parser en définissant par avance sa valeur résultat. Cela nous sera utile en particulier dans le cas où nous ne voulons plus consommer le flux et nous savons par ailleurs quel résultat retourner.

pure :: a -> Parser a
pure x = \s -> Just (x, s)

Nous allons ensuite définir la fonction « map » sur notre functor. En effet, tous les applicative functors sont, à la base, des functors, qui doivent donc être munis de l’opération map. Pour plus de commodité, nous allons la définir sous la forme d’un opérateur infix, de sorte que f <$> x == map f x.

La définition de map pour notre functor est simple :

• on prend une fonction à appliquer et un parser sur lequel l’appliquer
• si le parser réussit, on applique la fonction sur le résultat
• si le parser échoue (Nothing), on ne fait rien

(<$>) :: (a -> b) -> Parser a -> Parser b
f <$> p = \s -> case p s of
  Just (a, s') -> Just (f a, s')
  Nothing      -> Nothing

Nous allons ensuite définir une autre fonction, toujours sous forme d’opérateur infix pour plus de commodité. Nous la nommerons apply et nous la noterons <*>. Cette fonction rappelle un peu la précédente, sauf que cette fois-ci la fonction a appliquer est contenue dans notre functor parser. Apply va nous servir à enchaîner des parsers dans le flux, mais pas de n’importe quelle façon. Avec apply, nous pourrons enchaîner des parsers qui seront les paramètres successifs d’une fonction. L’idée est la suivante, nous avons une fonction (ou un constructeur, c’est similaire) qui doit trouver ses multiples paramètres à la suite dans le flux. Utilisée conjointement à map, notre fonction apply va nous permettre d’utiliser directement cette fonction avec nos parsers sans traîter explicitement le flux. Le principe de apply est simple, le parser de gauche traite le flux, si il réussit il produit une fonction ainsi qu’un restant de flux. On applique alors le parser de droite sur le restant de flux, et si cela réussit, on applique la fonction produite par le premier parser au résultat du second parser, et on retourne ça avec le flux restant. Pour l’utiliser dans le cas typique, on construira le premier parser avec map sur une fonction f, puis on enchaînera les paramètres de f avec apply.

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
p1 <*> p2 = \s -> case p1 s of
                   Just (f, s') -> case p2 s' of
                     Just (a, s'') -> Just (f a, s'')
                     Nothing       -> Nothing
                   Nothing -> Nothing

Cet opérateur apply est au cœur du concept de applicative functor. Au premier abord, le concept n’est pas évident à saisir, c’est pourquoi en cas de besoin je vous invite à trouver de la documentation générale sur ce sujet. Vous pouvez aussi continuer la lecture de ce document jusqu’à arriver aux exemples d’utilisation, puis revenir à la définition ci-dessus pour mieux comprendre ces exemples.

Les deux fonctions suivantes sont des variantes commodes de apply, qui ignorent respectivement le paramètre de droite, et celui de gauche. Elles sont utiles lorsqu’on veut consommer une portion de flux avec un parser sans utiliser le résultat en paramètre d’une fonction. Imaginez par exemple que vous souhaitez parser une addition de deux entiers, pour construire la valeur Add Int1 Int2. Parser le signe «+» est une nécessité pour valider l’expression, mais on ne va pas utiliser ce signe parsé par la suite, une fois l’opération identifiée. Vous pourrez donc écrire Add <$> number <*> (plus *> number), ainsi le constructeur Add sera utilisé avec les deux paramètres retenus, mais le parser aura vérifié et consommé le signe ‘+’ dans le flux.

(<*) :: Parser a -> Parser b -> Parser a
p1 <* p2 = const <$> p1 <*> p2

(*>) :: Parser a -> Parser b -> Parser b
p1 *> p2 = (flip const) <$> p1 <*> p2

Un autre outil dont nous aurons besoin est l’opérateur or, noté <|>. Son fonctionnement est simple aussi : si le parser de gauche réussit, son résultat est retourné et le parser de droite est ignoré. Sinon, c’est la valeur du parser de droite qui est retournée. Cet opérateur nous permettra d’essayer plusieurs parsers sur notre flux, dans le cas où plusieurs possibilités s’offrent à nous.

(<|>) :: Parser a -> Parser a -> Parser a
p1 <|> p2 = \s -> let r1 = p1 s in
  case r1 of
   Just _  -> r1
   Nothing -> p2 s

Cette fonction or définit la nature alternative functor de notre type Parser a.

La fonction runParser sert simplement à appliquer un parser sur un flux et à retourner le résultat, s’il existe, et si le flux a été intégralement consommé.

runParser :: Parser a -> String -> Maybe a
runParser p s = case p s of
  Just (r, "") -> Just r
  _            -> Nothing

Les combinateurs utiles

Équipés de nos primitives, nous allons pouvoir définir quelques combinateurs que nous utiliserons pour définir nos parsers.

Pour commencer, nous pouvons définir le combinateur many, qui répète un parser, et qui produit la liste des résultats. Notez que le parser many n’échoue jamais, s’il ne peut pas appliquer son parser en paramètre, il réussit avec la liste vide en résultat. Sa définition récursive repose sur map (avec comme fonction l’opérateur binaire de concaténation de liste (:)) et apply pour les deux paramètres (la tête et la queue récursive).

many :: Parser a -> Parser [a]
many p = ((:) <$> p <*> many p) <|> pure []

Some est une variante de many, pour laquelle il faut au moins une occurence de réussite (la tête de liste) pour que le parser réussisse.

some :: Parser a -> Parser [a]
some p = ((:) <$> p <*> many p)

Check est un combinateur qui travaille sur le premier caractère du flux. Il vérifie un prédicat sur ce caractère (paramètre) et en cas de succès, produit le caractère en résultat (et le consomme dans le flux). Sinon il échoue.

check :: (Char -> Bool) -> Parser Char
check f = \s -> case s of
  (x:xs) | f x -> Just (x, xs)
  _            -> Nothing

Parsers

Nous allons maintenant définir les quelques parsers dont nous aurons besoin pour analyser une expression arithmétique.

Le parser char parse un caractère précis en tête de flux.

char :: Char -> Parser Char
char c = check (== c)

Le parser oneOf prend une liste de char en paramètre, et cherche à parser l’un de ces caractères en tête de flux.

oneOf :: [Char] -> Parser Char
oneOf cs = check (\c -> elem c cs)

Le parser spaced consomme les espaces autour d’un parser, et retourne le résultat du parser. Il sert à nettoyer le flux des séparateurs qui n’ont pas d’incidence sémantique.

spaced :: Parser a -> Parser a
spaced p = spaces *> p <* spaces
  where spaces = many (check (== ' '))

number lit un nombre entier dans le flux. Il utilise la fonction haskell read pour convertir une chaîne de caractères en nombre entier.

number :: Parser Integer
number = read <$> some digit
  where digit = oneOf "0123456789"

Voilà, c’est tout ce dont nous aurons besoin comme parsers de base pour découper les expressions arithmétiques, et ainsi définir le parser d’expression expr.

Pour rappel, la grammaire de notre calculatrice est la suivante

number = digit { digit }
digit  = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
expr   = mul + mul | mul - mul | mul
mul    = factor * factor | factor
factor = "(" expr ")" | number

La traduction sous forme de parser est directe avec la boite à outil que nous avons définie ci-dessus. Par souci de concision, nous définissons aussi une petite fonction utilitaire binOp qui combine un opérateur binaire (constructeurs Add, Sub et Mul) et un parser qui sera appliqué deux fois.

Ce parser construit directement l’arbre syntaxique correspondant à notre expression. La souplesse de notre parser permet d’exprimer directement les règles de priorité des opérations, en fonction de l’ordre d’application des parsers.

expr :: Parser Expr
expr = add_sub
  where
    add_sub = binOp Add '+' mul <|> binOp Sub '-' mul <|> mul
    mul = binOp Mul '*' factor <|> factor
    factor = parens <|> lit
    lit = Lit <$> spaced number
    parens = spaced (char '(' *> expr <* char ')')
    binOp c o p = c <$> (p <* spaced (char o)) <*> p

Le petit outil suivant regroupe en une seule fonction le parser d’expression et l’évaluateur.

evalExpr :: String -> Maybe Integer
evalExpr s = (fmap eval) $ runParser expr s

Code complet

Voici le code complet de notre outil. Pour l’utiliser, copier le contenu dans un fichier, chargez-le avec ghci (ghci calc.hs), et utilisez la fonction evalExpr.

module Calc where

data Expr = Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Lit Integer

eval :: Expr -> Integer
eval e = case e of
  Add a b -> eval a + eval b
  Sub a b -> eval a - eval b
  Mul a b -> eval a * eval b
  Lit n   -> n


type Parser r = String -> Maybe (r, String)

pure :: a -> Parser a
pure x = \s -> Just (x, s)

(<$>) :: (a -> b) -> Parser a -> Parser b
f <$> p = \s -> case p s of
  Just (a, s') -> Just (f a, s')
  Nothing      -> Nothing

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
p1 <*> p2 = \s -> case p1 s of
                   Just (f, s') -> case p2 s' of
                     Just (a, s'') -> Just (f a, s'')
                     Nothing       -> Nothing
                   Nothing -> Nothing

(<*) :: Parser a -> Parser b -> Parser a
p1 <* p2 = const <$> p1 <*> p2

(*>) :: Parser a -> Parser b -> Parser b
p1 *> p2 = (flip const) <$> p1 <*> p2

(<|>) :: Parser a -> Parser a -> Parser a
p1 <|> p2 = \s -> let r1 = p1 s in
  case r1 of
   Just _  -> r1
   Nothing -> p2 s

runParser :: Parser a -> String -> Maybe a
runParser p s = case p s of
  Just (r, "") -> Just r
  _            -> Nothing

many :: Parser a -> Parser [a]
many p = ((:) <$> p <*> many p) <|> pure []

some :: Parser a -> Parser [a]
some p = ((:) <$> p <*> many p)

check :: (Char -> Bool) -> Parser Char
check f = \s -> case s of
  (x:xs) | f x -> Just (x, xs)
  _            -> Nothing

char :: Char -> Parser Char
char c = check (== c)

oneOf :: [Char] -> Parser Char
oneOf cs = check (\c -> elem c cs)

spaced :: Parser a -> Parser a
spaced p = spaces *> p <* spaces
  where spaces = many (check (== ' '))

number :: Parser Integer
number = read <$> some digit
  where digit = oneOf "0123456789"

expr :: Parser Expr
expr = add_sub
  where
    add_sub = binOp Add '+' mul <|> binOp Sub '-' mul <|> mul
    mul = binOp Mul '*' factor <|> factor
    factor = parens <|> lit
    lit = Lit <$> spaced number
    parens = spaced (char '(' *> expr <* char ')')
    binOp c o p = c <$> (p <* spaced (char o)) <*> p

evalExpr :: String -> Maybe Integer
evalExpr s = (fmap eval) $ runParser expr s

Définition alternative, utilisant les typeclass standards de Haskell

Dans sa librairie de base, Haskell propose des typeclass pour les interfaces functor, applicative et alternative. Utiliser ces typeclass apporte quelques avantages, en particulier le fait qu’avec une définition minimale de l’instance, on dispose automatiquement de tout un jeu de fonction utiles. C’est le cas par exemple de *>, de many, some etc. Voici, ci-dessous, une définition qui repose sur ces classes standards (environ 50 lignes de code).

module CalcApplicative where

import Control.Applicative

data Expr = Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Lit Integer

eval :: Expr -> Integer
eval e = case e of
  Add a b -> eval a + eval b
  Sub a b -> eval a - eval b
  Mul a b -> eval a * eval b
  Lit n   -> n

-- Nouveau datatype nécessaire pour les instances
data Parser r = Parser {parse :: String -> Maybe (r, String)}

-- Instances
instance Functor Parser where
  fmap f (Parser p) = Parser $ \s -> case p s of
    Just (a, s') -> Just (f a, s')
    Nothing      -> Nothing

instance Applicative Parser where
  pure x = Parser $ \s -> Just (x, s)
  Parser p1 <*> pp2 = Parser $ \s -> case p1 s of
    Just (f, s') -> case parse pp2 s' of
      Just (a, s'') -> Just (f a, s'')
      Nothing       -> Nothing
    Nothing -> Nothing

instance Alternative Parser where
  empty = Parser $ const Nothing
  (Parser p1) <|> pp2 = Parser $ \s -> p1 s <|> parse pp2 s

-- Le reste est identique
runParser :: Parser a -> String -> Maybe a
runParser (Parser p) s = case p s of
  Just (r, "") -> Just r
  _            -> Nothing

check :: (Char -> Bool) -> Parser Char
check f = Parser $ \s -> case s of
  (x:xs) | f x -> Just (x, xs)
  _            -> Nothing

char :: Char -> Parser Char
char c = check (== c)

oneOf :: [Char] -> Parser Char
oneOf cs = check (\c -> elem c cs)

number :: Parser Integer
number = read <$> some digit
  where digit = oneOf "0123456789"

expr :: Parser Expr
expr = add_sub
  where
    add_sub = binOp Add '+' mul <|> binOp Sub '-' mul <|> mul
    mul = binOp Mul '*' factor <|> factor
    factor = parens <|> lit
    lit = Lit <$> number
    parens = char '(' *> expr <* char ')'
    binOp c o p = c <$> p <*> (char o *> p)

evalExpr :: String -> Maybe Integer
evalExpr s = (fmap eval) $ runParser expr $ concat $ words s

Voir aussi :

• La conception par les catégories
• Les monades dans la programmation fonctionnelle
• Plateforme collaborative AtikTeam