Programmation Avancée

TP1: Modules

Exercice 1: Conteneurs

On considère la signature suivante, définissant des conteneurs (type t) pour un certain type d'éléments (type elt).

module type Container = sig
  type t
  type elt
  val empty  : t
  val add    : elt -> t -> t
  val merge  : t -> t -> t
  val member : elt -> t -> bool
  val fold   : ('a -> elt -> 'a) -> 'a -> t -> 'a
end

La spécification informelle sera que t se comporte comme un multi-ensemble, empty étant le multi-ensemble vide, add l'ajout d'un élément et merge la fusion de deux multi-ensembles. La fonction fold doit réaliser une itération sur tous les éléments d'un multi-ensemble, dans un ordre non spécifié. Par exemple, fold f x0 {e1,e2,e3} = f (f (f x0 e3) e2) e1.

Question 1

Définissez une implémentation du type Container par des listes. Dans ce cas on n'aura besoin d'aucune opération spécifique sur le type des éléments: on réalisera donc notre implémentation comme un foncteur LContainer de AnyT vers Container avec la déclaration

module type AnyT = sig
  type t
end

Question 2

Définir une implémentation par des listes triées, et exploiter l'ordre pour tester l'appartenance. Comme on a besoin d'un ordre sur le type elt, on va cette fois écrire un foncteur SLContainer de Set.OrderedType (cf. bibliothèque standard) vers Container.

Testez vos deux implémentations, au moins avec le code suivant:

let () =
  let module Test (M:Container with type elt = int) =
    struct
      open M
      let () =
        let s = add 42 (add 16 (add 64 empty)) in
        let s = merge s s in
          assert (member 42 s) ;
          assert (member 16 s) ;
          assert (member 64 s) ;
          Printf.printf "Result: " ;
          fold (fun () elt -> Printf.printf "%d+" elt) () s ;
          Printf.printf "ø\n"
    end
  in
  let module A = Test(LContainer(Int)) in
  let module B = Test(SLContainer(Int)) in
    ()

Dans la vraie vie

La première implémentation n'est pertinente en pratique que si on n'a pas d'ordre valable sous la main. La seconde implémentation est meilleure mais sous-optimale: on lui préfèrera des arbres binaires de recherche. En pratique, on utilisera souvent les modules Set, Map et Hashtbl de la bibliothèque standard.

Question 3

On introduit une signature pour les types affichables:

module type Printable = sig
  type t
  val to_string : t -> string
end

Définir la signature PContainer qui étend la signature Container avec un champ to_string : t -> string.

Définir un foncteur MakePrintable qui, étant donnés un ensemble d'éléments affichables et une instance de Container sur ces éléments, renvoie une instance de PContainer.

Tester sur le code suivant:

let () =
  let module Test (M:PContainer with type elt = string) =
    struct
      open M
      let () =
        let s =
          add "d" (merge (add "a" empty) (add "c" (add "b" empty)))
        in
          Printf.printf "Result: %s\n" (to_string s)
    end
  in
  let module A = Test(MakePrintable(String)(LContainer(String))) in
  let module B = Test(MakePrintable(String)(SLContainer(String))) in
    ()

Ajouter un test où l'on construit, puis affiche un conteneur (non trié) de conteneurs (triés) de chaînes de caractères. On devra utiliser MakePrintable deux fois, d'abord pour rendre les conteneurs de chaînes affichables, puis pour rendre les conteneurs de conteneurs affichables.

Question 4

Sur le papier, le système de modules garantit l'abstraction. Un foncteur qui reçoit en argument un module dont un type est abstrait ne pourra jamais accéder aux éléments de ce type autrement que par les fonctions fournies par le module. Il ne peut donc observer l'implémentation du type abstrait que par le biais des fonctions fournies explicitement.

En pratique, cela n'est pas tout à fait vrai: la fonction d'égalité (=) : 'a -> 'a -> bool permet de comparer des valeurs de tout type, y compris un type abstrait. (On notera que cette fonction ne peut être programmée en OCaml: elle est définie côté C dans le runtime du langage. Les fonctions polymorphes définissables dans le langage, comme par exemple List.mem, ne brisent pas l'abstraction.)

Etendre le premier foncteur Test en utilisant l'égalité polymorphe pour tester si M:Container est instantié par LContainer ou SLContainer.

Pensez-vous que cela soit un problème en pratique?