Programmation Avancée
TP1: Modules
Aujourd'hui, un exercice pour apprendre à maîtriser l'essentiel du système de modules d'OCaml, puis une application pratique de la chose.
Partie I: 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?
Partie II: 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.
Commencez avec un type d'arbres classique, donné par un type variant récursif.
Vous pouvez maintenant compiler et exécuter: make, ./htree.opt.
Utilisez la touche q pour quitter l'application.
Question 2
Exploitez la flexibilité de la signature TREE pour définir des
arbres très grands voire infinis, générés paresseusement: on pourra décrire
l'arbre de tous les mots, l'arborescence du système de fichiers, du web,
l'arbre sémantique d'une formule, etc.
Si vous avez plusieurs implémentations, modifiez le Makefile et le
module Main pour utiliser vos nouveaux modules, par exemple en fonction
d'options passées sur la ligne de commande
de l'application (Sys.argv, cf
doc).
Références
Je recommande l'article d'Alexandre Miquel sur son afficheur d'arbres. Le code source complet est aussi disponible.