Programmation Avancée
TP4: dites le avec des types
Dans chaque exercice, la dernière question est optionnelle et il est recommandé de la sauter pour traiter le reste avant la fin de la séance.
Exercice 1: variants polymorphes
Question 1
Déclarer un type récursif 'a list
avec des variants polymorphes.
Ecrire les fonctions map : ('a -> 'b) -> 'a list -> 'b list
et equals : 'a list -> 'a list -> bool
.
Vérifiez que vous obtenez bien les types attendus. Pour éviter les types illisibles, le mieux est de donner les types attendus dans des annotations ou dans une signature.
Question 2
Dans de nombreux algorithmes (par exemple, manipulation de texte) il est utile de ne pas calculer instantanément la concaténation de listes (ou de chaînes) mais de l'amortir. Pour supporter ceci, on étend notre type de listes avec un constructeur représentant la concaténation.
Indiquer pourquoi la déclaration suivante n'est pas pleinement satisfaisante, et corriger:
type 'a alist = [ 'a list | `Append of 'a list * 'a list ]
Ecrire
amap : ('a -> 'b) -> 'a alist -> 'b alist
,
équivalent de map
pour les listes concaténables,
ainsi que l'aplatissement flatten : 'a alist -> 'a list
qui effectue les concaténations.
Sans variants polymorphes, aplatir ne suffirait pas à obtenir une liste, il faudrait aussi convertir les constructeurs d'un type vers l'autre.
Corriger le code suivant et tester:
let () = let make = List.fold_left (fun a b -> `Cons (b,a)) `Nil in let a = make ['b';'l';'a'] in let b = `Append (a,a) in assert (equals b (make ['b';'l';'a';'b';'l';'a']))
Question bonus
Proposer une méthode pour pouvoir étendre map
en amap
sans
avoir à dupliquer de code (on ne veut pas traiter les cas `Nil
et `Cons
dans amap
).
Indice: il va falloir ouvrir des récursions.
On rappelle aussi la notation pour filtrer les variants correspondant à un sous-type:
type t = [ ... ] type t' = [ t | ... ] match (x:t') with | #t as y -> (* Capture les termes qui sont dans le type t. * Dans la branche, utiliser l'alias y:t' plutôt * que x dont le type est moins précis. *) ...
Exercice 2: types fantômes
L'idée générale des types fantômes est d'attacher à un type abstrait un paramètre de type qui serait inutile du point de vue du type concret associé, ceci afin d'obtenir une API agréable et (plus) sure.
Cette idée n'est pas propre à OCaml. Le wiki Haskell illustre cette technique avec l'exemple (vu en cours) de sanitisation de chaines de caratères. On rappelle ce que cela donne en OCaml. D'abord la signature:
type 'a str type clean type dirty (* On peut calculer la longueur de toute chaîne, * les inputs sont sales (on se méfie de l'utilisateur) * et doivent êtres nettoyés avant affichage. *) val length : 'a str -> int val read : unit -> dirty str val write : clean str -> unit val sanitize : dirty str -> clean str
puis l'implémentation, très simple et sans surcoût à l'exécution:
type 'a str = string type clean = unit (* ou autre, qu'importe *) type dirty = unit let length s = String.length s let read () = read_line () let write s = Printf.printf "%s\n" s let sanitize s = Filename.quote s
Dans l'API ci-dessus on a des fonctions qui ne prennent qu'un type de chaine, et des fonctions qui les prennent tous. Dans cet exercice, nous allons exploiter le sous-typage pour faire des distinctions plus fines.
Question 1
En Ocaml, les variants polymorphes sont souvent utilisés avec les
types fantômes, pour bénéficier de sous-typage.
Nous allons voir cela avec un type de descripteur de fichier annoté
par les permissions que l'on a sur le fichier (rw
pour lecture+écriture,
ro
pour lecture seule, wo
pour écriture seule).
Récupérer la base de code ici.
Quand vous tapez make
, cela compile le module File
ainsi que
quelques tests d'utilisation. Dans l'archive initiale, le test
positif test.ml
compilera bien mais les test qui ne sont
pas sensés compiler (ie. notest*.ml
) compilent quand même,
ce qui provoque une erreur dans le Makefile.
Votre mission est de mettre en place une discipline de type qui empêche
les mauvais bouts de code de compiler,
en modifiant uniquement file.mli
et file.ml
(il est est interdit
d'insérer ne serait-ce qu'une coercion dans test.ml
).
Vous utiliserez un type fantôme, dont le paramètre sera instancié
par différents types variants polymorphes selon les permissions
associées au fichier.
Question bonus
Au lieu de variants polymorphes, utilisez l'autre trait de OCaml qui offre du sous-typage: les objets.