Programmation Avancée

TP7: itérateurs persistants

Exercices conçu par David Baelde

On peut représenter une collection comme une fonction d'itération, par exemple fun f -> List.iter f l permet en principe de tout faire sur la liste l bien qu'on n'ait pas directement accès à elle. En utilisant des exceptions dans la fonction à itérer, on peut éviter de parcourir toute la collection. Par contre, on n'a aucun moyen de reprendre l'itération à partir d'une position arbitraire, ce qui est nécessaire si l'on veut faire des recherches avec backtracking; en d'autres termes, callcc nous manque.

Pour combler ce manque, on se propose de passer des fonctions d'itération à une notion d'itérateur persistant:

module type ITER = sig
  type t
  type elt
  type init
  val init : init -> t
  val next : t -> (elt*t) option
end

La spécification est:

on crée un itérateur à partir d'une donnée initiale de type init (par exemple une liste, ou la taille d'un échiquier sur lequel on veut résoudre le problème des reines);
puis on accède aux valeurs successives de l'itération via la fonction next;
next renvoie None quand l'itération est terminée;
sinon next renvoie Some (v,i) où v est la première valeur de l'itération et i est un nouvel itérateur représentant la suite de l'iération.

On demande que les itérateurs soient persistants dans le sens où itérateur doit pouvoir être réutilisé pour reprendre une énumération; en d'autres termes un itérateur de change pas quand on appelle sa fonction next.

Question 1

Construire un module L de signature ITER qui énumère simplement les éléments d'une liste d'entiers, dans l'ordre d'apparition dans la liste.

Question 2

Coder une fonction qui prend en argument un itérateur de type L.t et renvoie le nombre de sous-séquences dont la somme des éléments fasse 100. (On supposera que tous les éléments rencontrés sont des entiers strictement positifs.)

Question 3

On se donne maintenant un type d'expressions arithmétiques:

type op = char * (int -> int -> int)
let plus = '+',(+)
let times = '*',( * )
let minus = '-',(-)
type expr =
  | I of int
  | Op of op * expr * expr
let rec eval = function
  | I i -> i
  | Op (o,a,b) -> (snd o) (eval a) (eval b)

Implémentez une fonction iter_subexpr : expr -> (expr -> unit) -> unit qui itère une fonction sur toutes les sous-expressions d'une expression donnée. On s'interdira d'utiliser les exceptions et toute structure de données mutable.

Question 4

Transformez la fonction précédente en CPS. Vous obtenez iter_subexpr_k : expr -> (expr -> (unit -> 'a) -> 'a) -> (unit -> 'a) -> 'a. Définir une implémentation de ITER correspondant aux itérateurs sur sous-expressions, en posant elt = expr et t = (unit -> (elt*t) option) et enfin init e = iter_subexpr_k e f k avec f et k bien choisis.

Attention: Le type t proposé ici est trop immédiatemment récursif, et OCaml ne l'acceptera que si vous lui passez l'option -rectypes. L'alternative est de poser type t = { k = unit -> (elt*t) option }, ou encore type t = T of unit -> (elt*t) option, mais je déconseille ces complications.

Question 5

Dans le module précédemment obtenu, défonctionalisez le type t des itérateurs (qui correspond à un cas particulier du type des continuations de votre fonction d'itération en CPS).

On pourra simplifier le code (avant ou après défonctionalisation) en remarquant qu'un des arguments de votre fonction d'itération prend toujours la même valeur.

Vous obtiendrez ainsi une structure d'itérateur persistant de premier ordre. Peut être aurez-vous aussi re-découvert une implémentation usuelle de cet algorithme.

Adapter le code précédent pour chercher toutes les listes de sous-expressions d'une expression donnée, dont la somme des évaluations fasse 100.

Ci-dessous, un peu de code utile pour lancer un test où l'on doit trouver 6 solutions:

let t1 =
  Op (plus,
      Op (minus,
          Op (plus, Op (times, I 2, I 12), I 7),
          I 42),
      Op (plus, I 11, I 5))

let rec pp_expr ch = function
  | I i -> Format.fprintf ch "%d" i
  | Op (o,a,b) -> Format.fprintf ch "(%a%c%a)" pp_expr a (fst o) pp_expr b

let rec pp_list pp ch = function
  | [] -> ()
  | [a] -> pp ch a
  | a::b::more -> Format.printf "%a, %a" pp a (pp_list pp) (b::more)

let () = Format.printf "Exemple:\n %a\n" (pp_list pp_expr) [t1]
let () = assert (eval t1 = 5)

Question 6

Facile. Définir des itérateurs persistants de premier ordre pour les entiers situés aux feuilles d'une expression arithmétique. Vous pouvez attaquer le problème directement, ou bien passer par une fonction d'itération, une CPS et une défonctionalisation.

Moyen. De même pour les listes extraites d'une liste donnée. (Les listes extraites sont obtenues en enlevant des éléments à des positions arbitraires, par exemple [] et [1;2] sont extraites de [1;3;2;4].)

Difficile. De même pour les expressions extraites d'une expression donnée. (On définit une expression extraite comme étant obtenue par suppression de noeuds dans l'arbre syntaxique original. (Par exemple, à partir de (1+2)*(3+(4*5)) on peut extraire les expressions 1*4, (1+2)*(3+5), etc.)

Difficile. De même pour les sous-expressions (sous-arbres) d'une expression arithmétique, mais selon un parcours en largeur préfixe. (Par exemple, (1+2)+3 doit donner l'expression elle même, suivie de 1+2, 3, 1 et enfin 2.)