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é) 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?

Exercice 2: Visualisation d'arbres

Nous allons maintenant jouer avec une application créée par Alexandre Miquel, qui utilise la géométrie hyperbolique pour afficher de gros arbres.

Récupérez les sources de l'application. L'archive est incomplète: cela ne compilera pas tout de suite. Elle contient un Makefile qui décrit comment compiler mli et ml et comment lier le tout avec les bibliothèques requises pour obtenir une application. Le Makefile inclut aussi un fichier de dépendances entre fichiers sources, (re)généré automatiquement à l'aide d'ocamldep. Si tout ceci n'est pas déja familier, jetez-y un oeil à un moment ou un autre, si besoin en s'aidant de la documentation.

Question 1

L'application n'impose pas un type de données particulier, mais fonctionne pour tout type d'arbre satisfaisant la signature suivante:

module type TREE = sig
  type t
  type label
  val children : t -> t list
  val label : t -> label
  val string_of_label : label -> string
end

Votre objectif est de créér un fichier mytree.ml satisfaisant l'interface TREE avec en plus un champ val root : t correspondant à l'arbre à afficher au lancement de l'application. Pour commencer, définir un module Mytree basé sur un type d'arbres classique tel que type t = Leaf of int | Node of int * t * t.

Vous pouvez maintenant compiler et exécuter: make, ./htree.opt. Utilisez la touche q pour quitter l'application.

Question 2

La signature TREE permet de parler d'arbres très grands, voire infinis, générés paresseusement. Réalisez un second module implémentant TREE, dont les éléments du type t sont des arbres infinis de mots sur {0,1}, où les deux fils d'un noeud étiqueté par w sont w.0 et w.1.

Modifiez le Makefile pour inclure votre nouveau fichier, et modifiez module main.ml pour utiliser votre nouveau module, par exemple en fonction d'options passées sur la ligne de commande de l'application (Sys.argv, cf doc).

D'autres idées de types d'arbres: l'arbre des parties possibles pour un jeu (morpion, dames...), l'arbre sémantique d'un ensemble de clauses, l'arborescence du système de fichiers, du web, etc.

Références

Le code source complet de l'afficheur d'arbres d'Alexandre Miquel est disponible ici. Il y a aussi un article en français qui explique les maths et l'implémentation modulaire de cet outil.