Programmation Avancée

TP2: Objets

Exercice 1: laison tardive et mémoisation

Question 1

Ecrire une classe é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.

Attention! Cette façon de programmer est à éviter pour un calcul récursif intensif, à cause du cout de l'invocation des méthodes.

Question 2

La récursion implémentée ainsi peut être "ouverte" grâce à la liaison tardive des méthodes. Ecrire 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 de la fonction. Dans cette nouvelle classe, o#compute n nécessitera (au plus) n+1 invocations de la méthode compute.

Question 3

Rendre votre code générique par rapport à la classe que l'on étend, pour pouvoir ajouter notre dispositif de mémoisation sur d'autre fonctions récursives comme la factorielle.

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'

Le type ('a,'b) directory est-il covariant (resp. contravariant) en 'a? en 'b? Quel sur-type de directory est covariant en le type de ses éléments?

Ajouter des définitions de type, des annotations et coercions au fragment de code ci-dessus pour le faire bien typer.

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 le design pattern "visiteur": on implémente dans la classe printable_directory la structure générale de l'affichage, en appelant les méthodes d'un visiteur 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 -> unit; .. >

  method add_directory : string -> 'b -> unit
  method add_item : string -> 'a -> unit
  method iter : ('a -> unit) -> unit

  method print : pretty_printer -> unit
end

Question 4

Nous finissons 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).