La motivation
Lorsque j'ai commencé à apprendre Haskell, j'étais très ennuyé par l'utilisation généralisée d'abstractions complexes au lieu de solutions spécifiques. Il m'a semblé qu'il vaut bien mieux de toujours suivre le principe KISS et d'écrire des bicyclettes en utilisant des constructions de langage élémentaire que de comprendre toutes ces classes de types afin d'écrire une construction soi-disant pratique quelque part.
Je n'avais pas un bon exemple où les efforts consacrés au développement du "matériel" porteraient leurs fruits. Pour moi, l'un des exemples les plus réussis était les analyseurs. Maintenant, j'en parle souvent quand ils me demandent quelles tâches courantes vous pouvez magnifiquement utiliser Haskell.
Je veux proposer aux débutants de suivre cette voie et de créer une petite base de fonctions à partir de zéro pour une implémentation pratique des analyseurs, puis de l'utiliser pour écrire leur propre analyseur, dont le code répétera littéralement la grammaire utilisée pour l'analyse.
J'espère que cela aide quelqu'un à surmonter la peur des abstractions et à lui apprendre à les utiliser correctement (oui, je pense toujours qu'il est parfois plus efficace d'écrire un vélo).
Je n'ai aucun but et désir de faire un cours Haskell à partir d'un article, donc je suppose que le lecteur est familier avec la syntaxe et les programmes simples développés indépendamment. Au cas où, je parlerai brièvement des classes de types avant de passer à la description de l'implémentation.
Pour ceux qui n'ont jamais écrit à Haskell, mais qui veulent comprendre ce qui se passe ici, je vous recommande de consulter d'abord la page correspondante sur Learn X dans Y minutes . En tant qu'excellent livre en russe pour les débutants, je conseille "A propos d'Haskell en tant qu'être humain" de Denis Shevchenko.
J'essaierai d'utiliser les constructions de langage les plus simples que les débutants peuvent comprendre. À la fin de l'article, un lien est donné au référentiel source, où dans certaines parties du code une entrée plus pratique et plus courte est utilisée, ce qui peut être moins clair à première vue.
Et oui, messieurs Haskellistes, beaucoup de choses sont expliquées très simplement et maladroitement, pour des cas spéciaux, pas très abstraitement, sans utiliser des termes de la théorie des catégories et d'autres mots effrayants. Je suis heureux que vous les connaissiez et bien sûr, ils les maîtrisent facilement. Je les connais aussi, mais je ne pense pas qu'il soit nécessaire de vider une telle quantité d'informations dans ce contexte sur des lecteurs non préparés.
Classes de type
Les classes de type Haskell n'ont rien à voir avec les classes en C ++ et autres langages orientés objet. Si nous établissons une analogie avec la POO, les classes de types ressemblent davantage à une surcharge de méthodes et de fonctions.
Les classes déterminent quelles actions peuvent être effectuées avec des objets des types qui composent la classe. Par exemple, tous les nombres peuvent être comparés pour l'égalité, mais tout peut être ordonné à l'exception des nombres complexes, et en général, les fonctions ne peuvent pas du tout être comparées. La classe de types qui peut être comparée est appelée Eq , ordonnée - Ord (les types n'ont pas besoin d'être numériques). Ce qui peut être imprimé en traduisant en chaîne appartient à la classe Show , il a la classe Read "opposée", qui détermine comment convertir les chaînes en objets du type souhaité.
Pour un ensemble de classes de type standard (telles que Eq , Show , Read ...), vous pouvez demander au compilateur d'implémenter la fonctionnalité souhaitée de manière standard, en utilisant le mot clé deriving après avoir déterminé le type:
data Point = Point { xCoord :: Float , yCoord :: Float } deriving (Eq, Show)
Vous pouvez définir vos propres classes de types:
class PrettyPrint a where pPrint :: a -> String
Ici, PrettyPrint est le nom de la classe, a est une variable de type. Le mot-clé where est suivi d'une liste des méthodes dites de classe, c'est-à-dire fonctions qui peuvent être appliquées aux objets de type de cette classe.
Afin d'indiquer l'appartenance d'un type de données à une classe, la construction suivante est utilisée:
instance PrettyPrint Point where pPrint (Point xy) = "(" ++ show x ++ ", " ++ show y ++ ")"
Le langage vous permet de spécifier des restrictions sur les classes de type auxquelles les arguments de fonction doivent se rapporter:
showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String) showVsPretty x = (show x, pPrint x)
Pour chaque appel de fonction, le compilateur vérifie si ces exigences de type sont remplies et, en cas d'échec, affiche une erreur (cela se produit bien sûr au stade de la compilation).
>>> showVsPretty (Point 2 3) ("Point {xCoord = 2.0, yCoord = 3.0}","(2.0, 3.0)") >>> showVsPretty "str" error: No instance for (PrettyPrint [Char]) arising from a use of 'showVsPretty'
Implémentation
L'analyseur reçoit une chaîne d'entrée qu'il doit analyser selon des règles prédéfinies et obtenir la valeur du type dont nous avons besoin (par exemple, un entier). Dans ce cas, la ligne d'entrée peut ne pas se terminer et le reste servira d'entrée pour une analyse plus approfondie. De plus, notre analyseur sera généralement non déterministe, c'est-à-dire renverra plusieurs résultats d'analyse possibles sous forme de liste.
Un tuple de deux éléments (String, a) convient pour décrire un résultat de l'opération de l'analyseur, où a est une variable de type qui peut désigner n'importe quel type d'utilisateur.
Puisque l'analyseur analyse la chaîne selon certaines règles, nous la décrivons comme une fonction qui prend une chaîne en entrée et renvoie une liste de résultats:
newtype Parser a = Parser { unParser :: String -> [(String, a)] }
Nous considérerons que l'analyse est réussie si la liste des résultats se compose d'un élément et que la chaîne d'entrée a été complètement traitée. Nous implémentons une fonction d'assistance qui essaie d'analyser de manière unique la chaîne entière:
parseString :: String -> Parser a -> Maybe a parseString s (Parser p) = case (ps) of [("", val)] -> Just val _ -> Nothing
Analyseurs simples
Nous implémentons plusieurs analyseurs simples, qui seront ensuite utiles pour créer des combinaisons plus complexes.
Nous commençons par analyser un seul caractère qui doit satisfaire un prédicat. Si la chaîne d'entrée est vide, le résultat du travail est une liste vide. Sinon, nous vérifions la valeur du prédicat sur le premier caractère de la chaîne. Si True renvoyé, le résultat de l'analyse est ce caractère; renvoyez-le avec le reste de la chaîne. Sinon, l'analyse échoue également.
predP :: (Char -> Bool) -> Parser Char predP p = Parser f where f "" = [] f (c : cs) | pc = [(cs, c)] | otherwise = []
Nous pouvons maintenant écrire un analyseur qui prend un caractère spécifique au début de la ligne. Pour ce faire, utilisez le predP juste écrit et passez-le comme argument une fonction qui compare son argument avec le caractère dont nous avons besoin:
charP :: Char -> Parser Char charP char = predP (\c -> c == char)
Le cas le plus simple suivant: un analyseur qui accepte uniquement une certaine chaîne dans son ensemble. stringP . La fonction à l'intérieur de l'analyseur compare la ligne d'entrée avec celle souhaitée et, si les lignes sont égales, renvoie une liste d'un élément: une paire de lignes vides (il ne reste plus rien à l'entrée) et l'original. Sinon, l'analyse a échoué et une liste vide de résultats est renvoyée.
stringP :: String -> Parser String stringP s = Parser f where fs' | s == s' = [("", s)] | otherwise = []
Très souvent, vous devez ignorer les caractères qui ont une certaine propriété pendant qu'ils vont au début de la ligne (par exemple, les espaces blancs). De plus, le résultat de l'analyse n'est pas important pour nous et ne sera pas utile à l'avenir. Nous écrivons une fonction de skip qui saute les caractères initiaux de la chaîne tandis que la vraie valeur du prédicat est préservée. Comme résultat d'analyse, nous utilisons un tuple vide.
skip :: (Char -> Bool) -> Parser () skip p = Parser (\s -> [(dropWhile ps, ())])
Les deux analyseurs suivants sont très similaires l'un à l'autre. Les deux vérifient le préfixe de la ligne d'entrée, seul le premier en cas de succès renvoie ce préfixe et le second renvoie un tuple vide, c'est-à-dire vous permet de sauter une ligne arbitraire au début de l'entrée. L'implémentation utilise la fonction isPrefixOf définie dans le module Data.List .
prefixP :: String -> Parser String prefixP s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, s)] else [] skipString :: String -> Parser () skipString s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, ())] else []
Un peu plus tard, nous envisagerons une implémentation plus simple de cette dernière fonction et nous débarrasserons de la duplication de code.
Analyseur en tant que foncteur
Nous pouvons distinguer toute une classe de types de conteneurs pour lesquels les conditions suivantes sont vraies: si vous savez comment convertir des objets à l'intérieur d'un conteneur, vous pouvez convertir les conteneurs eux-mêmes. L'exemple le plus simple est une liste en tant que conteneur et une fonction de map , qui est disponible dans presque toutes les langues de haut niveau. En effet, vous pouvez parcourir tous les éléments d'une liste de type [a] , appliquer a -> b à chacun, et obtenir une liste de type [b] .
Cette classe de type s'appelle Functor ; la classe a une méthode fmap :
class Functor f where fmap :: (a -> b) -> fa -> fb
Supposons que nous savons déjà comment analyser des chaînes en objets d'un certain type a et, en outre, nous savons comment convertir des objets de type a en objets de type b . Est-il possible de dire qu'il existe alors un analyseur pour les objets de type b ?
S'il est exprimé sous la forme d'une fonction, il aura alors le type suivant:
(a -> b) -> Parser a -> Parser b
Ce type coïncide avec le type de la fonction fmap , essayons donc de faire de l'analyseur un foncteur. Créons un analyseur de valeurs de type b partir de zéro, qui appellera d'abord le premier analyseur (nous en avons déjà un), puis appliquera la fonction aux résultats de son analyse.
instance Functor Parser where fmap :: (a -> b) -> Parser a -> Parser b fmap f (Parser p1) = Parser p2 where p2 :: String -> [(String, b)] p2 s = convert (p1 s) convert :: [(String, a)] -> [(String, b)] convert results = map (\(s, val) -> (s, f val)) results
La fonction fmap a un synonyme d'infixe pratique: fmap fx == f <$> x .
Si nous utilisons une fonction comme argument pour fmap qui remplace simplement son premier argument par une nouvelle valeur, nous obtenons une autre opération utile qui est déjà implémentée pour tous les foncteurs même en deux copies (elles ne diffèrent que dans l'ordre des arguments):
(<$) :: Functor f => a -> fb -> fa ($>) :: Functor f => fa -> b -> fb
Vous vous souvenez de l'analyseur qui saute une ligne spécifique ( skipString )? Vous pouvez maintenant l'implémenter comme suit:
skipString :: String -> Parser () skipString s = () <$ prefixP s
Combinaisons d'analyseurs
Dans Haskell, toutes les fonctions sont curry par défaut et sont partiellement utilisables. Cela signifie qu'une fonction de n arguments est en fait une fonction d'un argument, renvoyant une fonction de n-1 arguments:
cons :: Int -> [Int] -> [Int] cons = (:) cons1 :: [Int] -> [Int] cons1 = cons 1
Nous appliquons une fonction de trois arguments à une valeur à l'intérieur de l'analyseur en utilisant fmap . Les types seront les suivants:
f :: c -> a -> b p :: Parser c (fmap fp) :: Parser (a -> b)
L'analyseur de fonction s'est avéré?! Bien sûr, une situation est possible lorsque la représentation de la fonction est vraiment dans la ligne d'entrée, mais je voudrais pouvoir utiliser cette fonction, ou plutôt combiner les Parser (a -> b) et Parser a pour obtenir l' Parser b :
applyP :: Parser (a -> b) -> Parser a -> Parser b
Le type de cette fonction est très similaire au type fmap , seule la fonction elle-même qui doit être appliquée est également dans le conteneur. Cela donne une compréhension intuitive de ce à quoi devrait ressembler l'implémentation de la fonction applyP : récupérer la fonction à partir du conteneur (à la suite de l'application du premier analyseur), obtenir les valeurs auxquelles la fonction doit s'appliquer (résultat de l'application du deuxième analyseur), et "empaqueter" les valeurs converties à l'aide de cette fonction. dans le conteneur (créer un nouvel analyseur). Dans l'implémentation, nous utiliserons la compréhension de liste:
applyP :: Parser (a -> b) -> Parser a -> Parser b applyP (Parser p1) (Parser p2) = Parser f where fs = [ (sx, fx) | (sf, f) <- p1 s,
Il existe une classe Applicative qui a une méthode avec le même prototype. La deuxième méthode de la classe est appelée pure et est utilisée pour «envelopper» ou «soulever» ( soulever ) une valeur, y compris une valeur fonctionnelle. Dans le cas de l'implémentation de l'analyseur, la fonction pure ajoute son argument au résultat de l'analyseur, sans changer la chaîne d'entrée.
class Functor f => Applicative f where pure :: a -> fa (<*>) :: f (a -> b) -> fa -> fb instance Applicative Parser where pure x = Parser (\s -> [(s, x)]) pf <*> px = Parser (\s -> [ (sx, fx) | (sf, f) <- unParser pf $ s, (sx, x) <- unParser px $ sf])
La fonction applyP est le <*> de la classe Applicative . Les types appartenant à cette classe sont appelés foncteurs applicatifs.
Pour les foncteurs applicatifs, deux fonctions auxiliaires sont implémentées qui nous seront utiles:
(*>) :: fa -> fb -> fb (<*) :: fa -> fb -> fa
Ces fonctions effectuent deux actions consécutives et renvoient le résultat d'une seule d'entre elles. Pour les analyseurs, ils peuvent être utilisés, par exemple, pour ignorer les espaces de tête avant d'analyser une partie d'une chaîne qui porte une charge sémantique.
En combinant <$> et <*> , vous pouvez créer des conceptions très pratiques. Considérez le type de données suivant:
data MyStructType = MyStruct { field1 :: Type1 , field2 :: Type2 , field3 :: Type3 }
Le constructeur de valeurs MyStruct est également une fonction, dans ce cas, il est de type Type1 -> Type2 -> Type3 -> MyStructType . Vous pouvez travailler avec le constructeur comme avec n'importe quelle autre fonction. Supposons que des analyseurs ont déjà été écrits pour les types de champs de structure:
parser1 :: Parser Type1 parser2 :: Parser Type2 parser3 :: Parser Type3
En utilisant la fonction fmap , vous pouvez appliquer partiellement MyStruct au premier de ces analyseurs:
parserStruct' :: Parser (Type2 -> Type3 -> MyStructType) parserStruct' = MyStruct <$> parser1
Essayons d'appliquer la fonction qui est maintenant "à l'intérieur" de l'analyseur. Pour ce faire, vous devez déjà utiliser <*> :
parserStruct'' :: Parser (Type3 -> MyStructType) parserStruct'' = parserStruct' <*> parser2 parserStruct :: Parser MyStructType parserStruct = parserStruct'' <*> parser3
En conséquence, nous avons obtenu un analyseur pour toute la structure (bien sûr, nous utilisons ici l'hypothèse que dans la ligne d'origine, les représentations de ses champs sont alignées). La même chose peut être faite sur une seule ligne:
parserStruct :: Parser MyStructType parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3
De telles constructions seront souvent rencontrées dans les cas d'utilisation.
Supposons maintenant que nous essayons d'écrire un analyseur qui analyse des expressions arithmétiques simples dans lesquelles des entiers et des identificateurs peuvent être présents en tant qu'opérandes. Créons pour eux un type d' Operand distinct:
data Operand = IntOp Int | IdentOp String
Si nous savons déjà comment analyser des entiers et des identifiants (par exemple, comme en C), alors nous avons besoin d' un analyseur pour les opérandes qui peuvent analyser l'un ou l'autre. Cet analyseur est une alternative aux deux autres, nous avons donc besoin d'une fonction qui peut combiner des analyseurs afin que les résultats de leur travail soient combinés. Le résultat de l'analyseur est une liste, et la combinaison des listes est leur concaténation. Nous implémentons la fonction altP combinant deux analyseurs:
altP :: Parser a -> Parser a -> Parser a altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)
Ensuite, l'analyseur d'opérande peut être implémenté à l'aide de cette fonction (ici, on suppose que parserInt et parserIdent déjà décrits quelque part:
parserOperand :: Parser Operand parserOperand = altP parserIntOp parserIdentOp where parserIntOp = IntOp <$> parserInt parserIdentOp = IdentOp <$> parserIdent
Bien sûr, pour les alternatives, nous avons déjà trouvé une classe distincte, qui s'appelle Alternative . Il a une autre méthode, empty , qui décrit l'élément neutre pour l'opération alternative. Dans notre cas, c'est un analyseur qui n'analyse jamais rien, c'est-à-dire renvoie toujours une liste de résultats vide. Pour l'analyseur, l'implémentation des méthodes de la classe Alternative ressemble à ceci:
class Applicative f => Alternative f where empty :: fa (<|>) :: fa -> fa -> fa instance Alternative Parser where empty = Parser (const []) px <|> py = Parser (\s -> unParser px s ++ unParser py s)
L'opération <|> est la fonction altP uniquement en notation infixe, ce qui est plus pratique à utiliser en combinant plusieurs analyseurs dans une rangée.
Pour tous les types de cette classe, deux fonctions sont implémentées, some et many type fa -> f [a] . Chacun d'eux peut s'exprimer à travers l'autre:
some v = (:) <$> v <*> many v many v = some v <|> pure []
En termes d'analyseurs, ces fonctions vous permettent d'analyser des séquences de données si vous savez comment analyser un seul élément de données. Dans le cas de l'utilisation de some séquence doit être non vide.
Exemple d'utilisation
Nous sommes maintenant prêts à écrire votre propre analyseur, par exemple, pour des expressions arithmétiques simples avec la grammaire suivante:
expr ::= constExpr | binOpExpr | negExpr const ::= int int ::= digit{digit} digit ::= '0' | ... | '9' binOpExpr ::= '(' expr ' ' binOp ' ' expr ')' binOp ::= '+' | '*' negExpr ::= '-' expr
L'expression se compose de constantes entières, du moins unaire et de deux opérations binaires d'infixe: addition et multiplication. Des crochets sont requis autour d'une expression avec une opération binaire, le symbole d'opération est séparé des opérandes par exactement un espace, les espaces de début et de fin ne sont pas autorisés.
Exemples d'écriture d'expression correcte:
"123" "-(10 + 42)" "(1 + ((2 + 3) * (4 + 5)))"
Exemples d'entrées incorrectes:
" 666 " "2 + 3" "(10 * 10)"
Nous déclarons les types de données nécessaires (l'expression elle-même et l'opération binaire):
data Expr = ConstExpr Int | BinaryExpr Expr Operator Expr | NegateExpr Expr data Operator = Add | Mul
Vous pouvez commencer l'analyse! L'expression elle-même se compose de trois alternatives. Nous écrivons donc:
Une constante est un entier positif. Dans notre type de données, il est "encapsulé" dans le constructeur, nous ne pouvons donc pas utiliser directement l'analyseur pour un entier, mais nous pouvons utiliser fmap pour obtenir la valeur du type souhaité.
Un entier, selon la grammaire, est représenté comme une séquence de nombres non vide. Pour analyser un chiffre, nous utilisons la fonction auxiliaire predP et le prédicat isDigit du module Data.Char . Maintenant, pour construire un analyseur pour analyser une séquence de nombres, nous utilisons la fonction some (pas many , car il doit y avoir au moins un chiffre). Le résultat d'un tel analyseur renvoie une liste de toutes les options d'analyse possibles, en commençant par l'enregistrement le plus long. Par exemple, si la chaîne d'entrée est «123ab», la liste des résultats sera la suivante: [("ab", "123"), ("3ab", "12"), ("23ab", "1")] . Nous devons analyser la plus longue séquence de chiffres et la convertir en type Int . La mise en œuvre entière est la suivante:
La prochaine façon d'écrire une expression consiste à utiliser une opération binaire. Selon la grammaire, la parenthèse ouvrante doit d'abord comprendre la parenthèse ouvrante, le premier opérande, l'espace, le symbole d'opération, un autre espace, le deuxième opérande et la parenthèse fermante. Pour analyser des caractères individuels (crochets et espaces), nous utilisons la fonction charP . Les opérandes sont des expressions, et il existe déjà un analyseur ( exprParser ) pour les analyser. Pour analyser le symbole d'opération binaire, nous décrivons l'analyseur auxiliaire juste en dessous. Il reste à combiner parfaitement cet ensemble d'analyseurs. Il devrait y avoir des crochets au début et à la fin de l'expression: vous devez vérifier cela, mais jetez le résultat lui-même. Pour ce faire, utilisez *> et <* :
binParser :: Parser Expr binParser = charP '(' *> ??? <* charP ')'
Entre ces analyseurs pour les parenthèses, une expression doit être construite à l'aide du constructeur BinaryExpr et des analyseurs pour l'expression et l'opération. N'oubliez pas les espaces autour du symbole d'opération, en utilisant la même méthode que pour les crochets. Cette partie est la suivante:
BinaryExpr <$> exprParser
Nous substituons cette expression au lieu de points d'interrogation:
Une opération binaire est soit un caractère + qui analyse la valeur Add , soit * qui analyse le Mul :
Reste la partie la plus simple de la grammaire, la négation de l'expression. Avec un symbole - faisons la même chose qu'avec les crochets et les espaces. Ensuite, appliquez le constructeur NegateExpr au résultat de l'analyse récursive:
Ainsi, toutes les parties de l'analyseur sont implémentées. Le code ressemble beaucoup à une grammaire et coïncide complètement avec lui dans sa structure.
Le code source est disponible sur GitLab: https://gitlab.com/fierce-katie/applicative-parsers-demo .
Là, il est plus facile d'évaluer son volume et son degré d'expressivité, car il y a beaucoup moins de commentaires. Vous pouvez compiler le projet avec l'utilitaire Stack et exécuter l'interpréteur primitif à l'aide de l'analyseur que nous avons écrit:
$ stack build $ stack exec demo-parser
Pour ceux qui veulent pratiquer davantage par eux-mêmes, je peux conseiller ce qui suit:
- La grammaire peut être améliorée de toutes les manières, par exemple, pour autoriser les espaces de début et de fin, ajouter de nouvelles opérations, etc.
- L'analyseur traduit la chaîne en représentation interne de l'expression. Cette expression peut être calculée et l'interpréteur converti de sorte qu'il n'imprime pas le résultat de l'analyse, mais le résultat du calcul.
- Explorez les possibilités des
attoparsec parsec , attoparsec , applicative-parsec et optparse-applicative et essayez de les utiliser.
Merci de votre attention!
Matériaux utiles
- Apprenez Haskell en Y minutes
- Denis Shevchenko. "A propos d'Haskell en tant qu'être humain"
- Bibliothèque Parsec
- Bibliothèque Attoparsec
- Bibliothèque applicative-parsec
- Bibliothèque applicative Optparse