Programmation Avancée

TP7: transformations de monades et parsing monadique

On définit la notion de monade ainsi que la monade identité: 

module type MONAD = sig
  type 'a m
  val return : 'a -> 'a m
  val bind : 'a m -> ('a -> 'b m) -> 'b m
end

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 doit être char list -> (char list * 'a) list.

Question 1

Construire la base de la monade Parsing en appliquant les transformations précédentes sur la monade Id.

Question 2

Définir dans cette monade les opérations suivantes: 

val plus : 'a m -> 'a m -> 'a m
val zero : 'a m
val read : char m
val eos  : bool m

Le plus correspond au choix non-déterministe entre deux calculs, et zero est l'échec. L'opération read lit 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é.

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.

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 char list 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 : char list 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 () =
  assert (List.length (string "fo" ['b';'a';'r']) = 0) ;
  assert (List.length (string "fo" ['f';'o';'o']) = 1) ;
  assert (List.length (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 (List.length (!(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 char list 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.