Programmation Avancée

TP11: parsing monadique

Exercices conçu par David Baelde

On rappelle la signature des monades: 

module type MONAD = sig
  type +'a m
  val return : 'a -> 'a m
  val bind : 'a m -> ('a -> 'b m) -> 'b m
end
Ainsi que la monade identité: 
module Id : MONAD with type 'a m = 'a = struct
  type 'a m = 'a
  let return x = x
  let bind m f = f m
end

Exercice 1: Transformations de monades

Pour cet exercice, il n'est pas nécessaire d'implémenter la fonction lift des transformations de monades: on se contentera d'un foncteur de MONAD vers MONAD.

Question 1

On a vu que le type list permet de construire une monade pour le calcul non-déterministe. La construction peut être généralisée en une transformation de monade, permettant d'étendre une monade sur 'a m en une monade sur 'a list m, ajoutant la notion de non-déterminisme aux calculs représentés. Implémenter la transformation ListT : functor (M:MONAD) -> MONAD with type 'a m = 'a list M.m. On pourra s'aider d'une fonction auxiliaire mconcat : 'b list M.m list -> 'b list M.m qui exécute dans M tous les calculs de la liste passée en argument, et renvoie dans M la concaténation des listes résultantes.

Question 2

La monade de lecture permet de représenter des calculs qui lisent un flux de données en le consommant graduellement. Cela permet par exemple de modéliser la lecture d'un fichier, ou du canal d'entrée standard, telle qu'effectuées avec l'API Unix. Dans ce mode de lecture, si on compose deux calculs et que le premier lit trois caractères, la première opération de lecture du second calcul devra lire le quatrième caractère du flux initial. On peut construire la monade de lecture from scratch sur le type 'a m = char list -> char list * 'a, mais on va ici faire les choses de façon plus modulaire: implémenter la transformation ReaderT : functor (M:MONAD) -> MONAD with type 'a m = char list -> (char list * 'a) M.m.

Exercice 2: Monade de parsing

La monade de parsing combine la monade de lecture (on lit un flux de tokens) et la monade de non-déterminisme (par défaut, une grammaire est ambigue et le parsing peut avoir plusieurs résultats). Le type de la monade est 'a m = char list -> (char list * 'a) list. Les calculs représentés (des parsers) prennent en entrée une suite de tokens de type char et renvoient une liste d'alternatives, chacune étant composée:

Pour fixer les idées, cette monade va nous permettre d'écrire des parsers et de les composer. Par exemple le parser int lira un maximum de caractères de [0-9] dans le flux de tokens, et renverra (avec la liste de tokens restante) leur interprétation comme un int. Le parser plus pourra ensuite exécuter le parser d'entiers, récupérer son résultat n, puis lire le caractère + et relancer le parser d'entiers, récupérer son résultat m, et renvoyer m. On notera ici deux points: les caractères consommés dans la char list par un calcul de la monade ne sont plus disponibles pour les calculs suivants; dans cet exemple on retourne au plus un résultat, mais la structure de liste permet de modéliser les échecs (par exemple, sur l'entrée 123++).

Question 1

Construire un module Parsing de signature MONAD de telle sorte que les opérations return et bind respectent la sémantique attendue:

Question 2

Etendre votre module, et lui attacher la signature suivante: 

module type PARSING = sig
  include MONAD
  val plus : 'a m -> 'a m -> 'a m
  val zero : 'a m
  val read : char m
  val eos  : bool m
  val run  : 'a m -> char list -> (char list * 'a) list
end

Le plus correspond au choix non-déterministe entre deux calculs, et zero est l'échec (aucun résultat possible). L'opération read lit (et consomme) le premier char du flux d'entrée, échoue si le flux est déja terminé. L'opération eos (end of stream) indique enfin si le flux est terminé. Enfin, run exécute un calcul sur une entrée donnée.

Bonus (dur!)

La monade de parsing combine deux aspects: le non-déterminisme et la lecture. Chacun de ces aspects peut être implémenté séparemment comme un transformateur de monades (sans opérateur lift: on se contentera d'un foncteur de MONAD vers MONAD). Reconstruire ainsi la monade de parsing.

Exercice 3: parsing

L'objectif, à partir de maintenant, est de ne plus jamais s'appuyer sur la définition de 'a Parsing.m, mais d'utiliser uniquement les opérations élémentaires définies ci-dessus. (Techniquement, on s'appuiera sur le fait que le type 'a m est abstrait dans la signature PARSING et qu'on travaille désormais en dehors de ce module.)

On pose type word = char list. Nous allons définir des combinateurs de parsing qui permettent notamment de construire, pour tout langage régulier L, un parseur p(L) de type word m tel que, pour tout préfixe w du flux d'entrée, p(L) lit w et renvoie (au moins) une fois w ssi w appartient à L. L'opération zero : word m correspond déja au langage vide selon cette spécification, et plus correspond à l'union de langages.

Question 1

Définir one : char list m correspondant au langage contenant uniquement le mot vide: one ne doit donc rien lire et juste renvoyer [].

Définir char : char -> char list m tel que char c reconnaisse le mot restreint au caractère c; le calcul doit donc vérifier qu'il y a un caractère à lire, et qu'il s'agit bien de c.

Définir concat : char list m -> char list m -> char list m qui corresponde à la concaténation de langages.

Utiliser les opérations précédemment définies pour dériver le parser reconnaissant une chaîne donnée: string : string -> char list m. Tester: 

let plength m l = List.length (Parsing.run m l)
let () =
  assert (plength (string "fo") ['b';'a';'r'] = 0) ;
  assert (plength (string "fo") ['f';'o';'o'] = 1) ;
  assert (plength (string "fo") ['f';'a'] = 0)

Question 2

Définir star : char list m -> char list m en suivant l'équation A* = 1 + AA*. Il faudra faire attention aux récursions, et introduire si besoin une notion de concaténation paresseuse qui ne calcule son second parseur qu'une fois qu'on a obtenu un résultat du premier parseur.

Tester: 

let (!) = star
let (++) = plus
let () =
  assert (plength !(char 'a' ++ char 'b') ['a';'b';'a'] = 4)

Quels résultats obtenez vous pour !(char 'a' ++ string "aa") sur ['a';'a';'a']?

Question 3

Un parseur ne doit pas seulement servir à reconnaître des (sous-)mots, mais aussi à les structurer ou les interpréter. Nous allons donc arrêter de considérer uniquement des objets de type word m.

Définir digit : int m qui reconnaît les mots composés d'un seul chiffre et renvoie leur valeur numérique. En déduire un parser expr : int m qui reconnaît les expressions arithmétiques simples définies ci-dessous et renvoie leur interprétation dans int: 

digit ::= ['0'-'9']
expr  ::= digit | digit '+' expr

Que se passe-t-il si on écrit le même langage par une grammaire récursive à gauche?

On pourra enfin ajouter la multiplication en respectant les priorités usuelles, du parenthésage, lire des entiers supérieurs à 9, etc.

Références

Functional Pearl: Monadic parsing in Haskell de Graham Hutton et Erik Meijer.