Programmation Avancée

TP2: Objets

Exercice 1: laison tardive et mémoisation

Une fonction récursive f : i -> o peut être donnée par le biais d'une fonction d'ordre supérieur f_f : (i -> o) -> (i -> o) dont le premier argument représente moralement les appels récursifs. En un certain sens, f va être le (plus petit) point fixe de f_f. Mais il y a plusieurs façons de former ce point fixe, c'est à dire de calculer la fonction récursive. Notamment, on va pouvoir automatiquement dériver une version mémoisée de f à partir de f_f. 

let rec fact x = if x = 0 then 1 else x * fact (x-1)
let f_fact fact x = if x = 0 then 1 else x * fact (x-1)

(** Combinateur de point fixe pour "refermer" f_f sur elle-même
  * et obtenir ainsi essentiellement f. *)
let rec compute f_f x = f_f (compute f_f) x

let () = assert (6 = compute f_fact 3)

(** "Refermer" en mémoisant. *)
let compute_memo f_f =
  let table = Hashtbl.create 23 in
  let rec f x =
    try Hashtbl.find table x with
      | Not_found ->
          let r = f_f f x in
            Hashtbl.add table x r ;
            r
  in
    f

let memo_fact = compute_memo f_fact
let () = assert (6 = memo_fact 3)

Pour pouvoir appliquer cette technique il faut que la fonction récursive ait été préparée a priori, donnée sous sa forme "ouverte". Nous allons faire la même chose en style objet, et utiliser la liaison dynamique des invocations de méthodes pour dérouter un calcul récursif qui n'est pas a priori prévu pour.

Question 1

Ecrire une classe fibo équipée d'une méthode compute : int -> int qui cacule la fonction de Fibonacci de façon naïve, en faisant des appels récursifs à la méthode compute. Afficher un message à chaque invocation de la méthode, de façon à expliciter, par exemple, que le calcul o#compute 4 nécessite 9 invocations de la méthode compute.

Note: On ne programmerait probablement pas un calcul récursif intensif de cette façon en OCaml, notamment à cause du coût de l'invocation des méthodes.

Question 2

Grâce à la liaison tardive, la récursion ainsi implémentée peut être "ouverte" pour intercaler un bout de code qui peut changer le résultat du calcul ou la façon dont il se déroule.

On peut ainsi écrire une classe memo_fibo qui hérite de la classe précédente et implémente un système de mémoisation pour éviter de recalculer les valeurs des appels à compute. Dans cette nouvelle classe, o#compute n nécessitera (au plus) n+1 invocations de la méthode compute.

Pour se guider, nous allons nous forcer à réaliser cette classe dérivée de façon générique par rapport à la classe étendue, pour que le dispositif ne soit pas appliquable qu'à fibo mais aussi à toutes les classes ayant le même type. On se donne donc la signature suivante, pour parler d'une classe quelconque ayant le type qui nous intéresse: 

module type T = sig
  class c : object
    method compute : int -> int
  end
end

Implémenter Memo de type functor (M:T) -> T qui prend une classe M.c et renvoie un nouveau module dont la classe c est la version mémoisée de M.c.

Tester sur fibo puis sur une autre classe calculant, par exemple, la factorielle ou les coefficients binomiaux.

Note: La généricité de cette solution reste critiquable puisqu'on a dû annoncer d'entrée de jeu le type complet de la classe c attendue: on ne peut pas utiliser le foncteur obtenu ici pour une classe implémentant d'autres méthodes (publiques) que compute : int -> int.

Exercice 2: sous-typage et sous-répertoires

Grâce au sous-typage, il est facile de construire une collection d'objets qui n'ont pas forcément le même type: 

let o = object method pos = (0.,0.) end
let pc = object method pos = (1.,2.) method color = "red" end
let l = [ o ; (pc :> <pos:float*float>) ]

En faisant ceci, on a cependant perdu de l'information sur l'élément pc dans la liste: on ne peut plus appeler sa méthode color. Dans cet exercice, nous allons concevoir un type de collection qui permette de garder une information de typage précise pour un sous-ensemble des objets.

Question 1

Implémenter une classe directory du type suivant, où le paramètre 'a représente le type des objets contenus dans le répertoire et 'b est le type des sous-répertoires: 

class ['a,'b] directory : object
  constraint 'b = < iter : ('a -> unit) -> unit; .. >
  method add_directory : string -> 'b -> unit
  method add_item : string -> 'a -> unit
  method iter : ('a -> unit) -> unit
end

Dans les méthodes d'ajout, le premier argument est le nom de l'objet ajouté. L'ajout d'un élément se fait dans le répertoire courant, et l'itération sur tous les éléments doit aussi visiter les sous-répertoires ajoutés (d'où la contrainte sur 'b).

Question 2

On voudrait convaincre OCaml que le code suivant est valide: 

type p = <pos:float*float>
type pc = <pos:float*float;color:string>
let d = new directory
let d' = new directory
let () =
  d#add_item "o" (object method pos = 0.,0. end) ;
  d'#add_item "pc" (object method pos = 0.,0. method color = "red" end) ;
  (* !! La ligne problématique !! *)
  d#add_directory "points colorés" d'

En l'état, il ne type pas. Ajouter des définitions de type, des annotations et coercions au fragment de code ci-dessus pour le rendre valide. Pour vous aider, réfléchissez aux questions suivantes:

Question 3

On veut maintenant pouvoir afficher nos répertoires, dès lors qu'ils contiennent des éléments de type 'a qui soit un sous-type de <to_string:string>.

Comme plusieurs formats d'affichage sont possibles, on pourrait définir plusieurs classes html_printable_directory, ascii_printable_directory, etc. Mais cette solution ne permet pas d'afficher un même répertoire de deux façons différentes en fonction des circonstances. Une autre solution est d'encapsuler les méthodes d'affichage dans une classe pretty_printer et d'implémenter dans la classe printable_directory la structure générale de l'affichage, en appelant les méthodes d'un pretty_printer pour réaliser les détails de l'opération.

Implémenter cette extension, suivant la signature ci-dessous: 

class type pretty_printer = object
  method open_section : string -> unit
  method close_section : unit
  method paragraph : string -> unit
end

(** ASCII pretty printer *)
class terminal_pp : pretty_printer

class ['a,'b] printable_directory : object
  constraint 'a = < to_string : string; .. >
  constraint 'b =
    < iter : ('a -> unit) -> unit; print : pretty_printer -> 'c; .. >
  inherit ['a,'b] directory
  method print : pretty_printer -> unit
end

Question 4

Pour finir nous utilisons nos classes sur un exemple jouet représentant le catalogue d'un magasin de disques et d'autres trucs.

Créer deux répertoires: un pour les produits génériques, et un sous-répertoire pour les disques. Créer les classes produit et disque tel qu'indiqué ci-dessous, en utilisant un initializer pour que chaque nouvelle instance de ces classes soit ajoutée au répertoire correspondant: 

(** Arguments: titre, genre, prix *)
class produit : string -> string -> int ->
  object
    method genre : string
    method prix : int
    method titre : string
    method to_string : string
  end

(** Arguments: titre, artiste, prix *)
class disque : string -> string -> int ->
  object
    method artiste : string
    method genre : string (* toujours "disque" *)
    method prix : int
    method titre : string
    method to_string : string
  end

On pourra alors exécuter le code suivant, qui crée quelques objets, affiche l'inventaire, et fait des recherches plus ou moins spécifiques: 

let () =
  ignore (new produit "Truc Tour" "place de concert" 42) ;
  ignore (new produit "Bob Marley" "poster" 5) ;
  ignore (new disque "Fashion Nugget" "Cake" 12) ;
  ignore (new disque "At the Pershing" "Ahmad Jamal" 19) ;
  ignore (new disque "Chamboultou" "Têtes Raides" 9)

let () =
  let pp = new terminal_pp in
    pp#open_section "Produits" ;
    produits#print pp ;
    pp#close_section

let () =
  Printf.printf "\nProduits à moins de 10 euros:\n" ;
  produits#iter
    (fun p ->
       if p#prix < 10 then Printf.printf "%s: %s\n" p#titre p#to_string) ;
  Printf.printf "\nDisques de Cake:\n" ;
  disques#iter
    (fun p ->
       if p#artiste = "Cake" then Printf.printf "%s: %s\n" p#titre p#to_string)

Pro tip: Il faut se méfier des tables recensant tous les objets créés, car elles empêchent le garbage collector de faire son travail... à moins d'utiliser une structure de données idoine, à pointeurs faibles (cf. module Weak).