Programmation Avancée

TP3

Nous commencerons la séance par une brève présentation des variants polymorphes. 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 3

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, voici un exemple adapté de la page Haskell sur le sujet. On veut manipuler des chaînes en s'assurant qu'une chaîne est "nettoyée" exactement une fois avant son utilisation, typiquement pour enlever des caractères spéciaux. Pour cela on va travailler avec un type abstrait, donné dans la signature suivante:

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

L'implémentation est très simple, sans aucun surcoût:

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

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 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 2

Au lieu de variants polymorphes, utilisez l'autre trait de OCaml qui offre du sous-typage: les objets.

Pour aller plus loin

Vous connaissez maintenant de nombreuses façons d'organiser du code, de façon à le rendre facile à lire et à écrire, maintenable, et vous savez éviter par typage un certain nombre d'erreurs. Pour aller plus loin dans ce sens, un aspect important d'OCaml est les arguments étiquettés et optionnels, que vous pourrez découvrir dans le manuel.

Variants polymorphes et étiquettes sont fréquemment utilisés dans les bibliothèques OCaml, par exemple labltk, lablgtk ou encore cairo.