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.