L'approche qualité avec OCaml

Jusqu'à présent nous avons manipulé beaucoup de listes et nous avons laissé de côté les structures plus générales comme les arbres et les graphes. Rattrapons cet oubli.

Commençons par les arbres.

Un programmeur habitué à des langages à typage dynamique pourrait imaginer que la structure list suffira à représenter les arbres n-aires (n-ary trees) par exemple de la façon suivante :

# [[1];[[2;3];[4;5]]];;
Characters 6-11:
  [[1];[[2;3];[4;5]]];;
        ^^^^^
This expression has type 'a list but is here used with type int

Et pourtant cette tentative est immédiatement rejetée par OCaml, pourquoi ?
Parce que le type 'a list est obligatoirement homogène, or ici le 1^er élément de notre liste est de type int list alors que le 2d élément est de type int list list. Notre liste est donc hétérogène, elle est mal typée.

Pensons plutôt notre arbre récursivement. Nous aimerions que chaque noeud puisse contenir un élément de type 'a et une liste de sous-arbres du même type que lui-même. Nous avons donc besoin de deux composantes, ce qui nous laisse le choix de l'implémentation, soit un couple, soit un enregistrement. Nous pouvons alors choisir entre l'une de ces deux déclarations de types.

Ou bien à l'aide d'un enregistrement :

# type 'a tree = {item: 'a; sub: 'a tree list};;
type 'a tree = { item : 'a; sub : 'a tree list; }

Ou bien à l'aide d'un couple :

# type 'a tree = 'a * ('a tree list);;
Characters 4-34:
  type 'a tree = 'a * ('a tree list);;
      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The type abbreviation tree is cyclic

En fait non, nous ne pouvons pas utiliser les couples. La raison peut paraître obscure pourtant elle devient limpide si nous évaluons ces deux expressions :

# 1,[];;
- : int * 'a list = (1, [])
# 1,[2,[];3,[]];;
- : int * (int * 'a list) list = (1, [(2, []); (3, [])])

Le type que nous voudrions définir dépend de la structure de données. Il croît avec elle, nous n'avons pas de moyen de définir le domaine d'une façon générale. Au contraire, avec le type enregistrement, 'a tree est le domaine. Il est déjà défini et donc le type 'a tree list est disponible pour le champ sub. On dit que le type enregistrement est un type récursif, au contraire le type n-uplet n'est pas un type récursif.

Les fonctions sur les arbres rev_tree, map_tree, exists_tree, flatten_tree, suivent de façon assez immédiate leurs correspondantes sur les listes :

let rec rev_tree t =
  {item = t.item; sub = List.rev_map rev_tree t.sub};;

let rec map_tree f t =
  {item = f t.item; sub = List.map (map_tree f) t.sub};;

let rec exists_tree p t =
  (p t.item) or List.exists (exists_tree p) t.sub;;

let rec flatten_tree t =
  t.item::List.flatten (List.map flatten_tree t.sub);;

Passons maintenant aux graphes dirigés avec racine.

Un graphe dirigé avec racine (rooted directed graph) est très semblable à un arbre n-aire avec la possibilité supplémentaire de partager des noeuds, de surcroît des cycles peuvent exister, de ce fait les algorithmes de parcours valables sur un arbre ne sont plus valables sur un graphe dirigé, car un cycle pourrait piéger le parcours dans une boucle infinie.

Afin d'éviter les boucles infinies, on doit arrêter la récursion quand on rencontre un sommet déjà visité. Il nous faut donc trouver un moyen de marquer les sommets déjà visités pendant la traversée. Il nous faut également nettoyer toutes les marques après la traversée. Voici comment on procède : on déclare un graphe dirigé avec racine de la même façon qu'un arbre n-aire tout en lui ajoutant un champ time qui est déclaré mutable :

type 'a rooted_digraph =
  {point: 'a; arrows: 'a rooted_digraph list; mutable time: int};;

Essentiellement il s'agit de relier des sommets (point) par des flèches (arrows) et d'enregistrer l'horaire (time) de la dernière visite.

mutable signifie que la valeur du champ time pourra changer. Nous verrons qu'heureusement ce changement fait l'objet de règles de bonne conduite. Mais d'abord nous allons déclarer l'horloge qui fournira notre temps de référence :

let clock = {point = 1; arrows = []; time = 0};;

Désormais l'heure sera la valeur du champ clock.time.

Notons que, puisque clock est le sommet d'un rooted_digraph, il est logique que chaque sommet d'un rooted_digraph puisse être considéré comme une horloge, chacune de ces horloges pourra soit être à l'heure soit être en retard par rapport à clock notre horloge de référence.

Nous définissons maintenant trois fonctions horaires :

• clock_tick t fait progresser l'horloge de référence de t unités ;
• clock_slow h nous dit si l'horloge h a pris du retard ;
• clock_sync h remet l'horloge h à l'heure de référence.

let clock_tick t =
  assert(t > 0);
  clock.time <- clock.time + t;;

let clock_slow h =
  h.time < clock.time;;

let clock_sync h =
  h.time <- clock.time;;

Les deux fonctions clock_tick et clock_sync garantissent :

• que toute horloge est strictement croissante ;
• que toute horloge est synchronisable avec l'heure de référence ;
• que l'heure de référence est également une heure maximale, aucune horloge ne pourra la dépasser.

Ces deux fonctions sont précisément celles qui justifient la mutabilité du champ time, le qualificatif mutable signifie qu'on peut assigner ce champ à l'aide de l'opérateur ←, cette opération d'assignation renvoie un élément du type unit. En fait le type unit ne contient qu'un seul élément, à savoir (), par conséquent l'opérateur d'assignation renvoie toujours la valeur (). Plus généralement, toute expression de type unit, c'est-à-dire de valeur () est considérée comme une instruction valide. En particulier l'opérateur infixe de séquencement des instructions est le point-virgule, il est associatif à droite et de type unit → 'a → 'a, de sorte que la valeur d'une séquence d'instruction est la valeur de l'expression qui la suit immédiatement.

Preuve :

• la flèche → est associative à droite, par conséquent le point-virgule est de type unit → ('a → 'a) ;
• 'a → 'a est forcément le type de l'identité.

La fonction d'un rooted_digraph la plus élémentaire est length_graph qui donne le nombre de sommets présents dans le graphe :

let length_graph g =
  let rec loop acc g =
    if clock_slow g then begin
      clock_sync g;
      List.fold_left loop (acc + 1) g.arrows
    end else
      acc
  in begin
    clock_tick 1;
    loop 0 g
  end;;

Les mots-clés begin ... end encadrent une séquence d'instructions séparées par un point-virgule.
Une instruction est une expression du type unit, sauf pour la dernière d'entre elles qui est d'un type quelconque, c'est le type de cette dernière instruction qui devient le type de toute la séquence, car les séquences sont typées elles aussi. La valeur () est la seule et unique valeur de type unit. En fait l'expression begin instr1;...;instrn end a exactement la même sémantique que l'expression let () = instr1 and ... and () = instrn-1 in instrn.

Remarque : nous ne décrirons pas la fonction List.fold_left, pour plus d'information sur cette fonction veuillez vous reporter à la documentation en ligne du module List.

Les fonctions exists_graph et flatten_graph sont bâties sur le même modèle que length_graph :

let exists_graph p g =
  let rec loop g =
    if clock_slow g then begin
      clock_sync g;
      (p g.point) or List.exists loop g.arrows
    end else
      false
  in begin
    clock_tick 1;
    loop g
  end;; 

let flatten_graph g =
  let rec loop acc g =
    if clock_slow g then begin
      clock_sync g;
      List.fold_left loop (g.point::acc) g.arrows
    end else
      acc
  in begin
    clock_tick 1;
    List.rev (loop [] g)
  end;;

Dans le cas courant d'un graphe dirigé acyclique, la fonction flatten_graph effectue ce que l'on appelle un tri topologique.

Mais au fait, comment construit-on un rooted_digraph ?
On construit un graphe à l'aide de let rec ... and ... and ... in root où root désigne le sommet racine du graphe.

Exemple avec un automate qui reconnaît les mots anglais race, rat, ray, rice, ride, role, rome, rope, rose, row, rude, rule :

La fonction r_graph construit le graphe de cet automate et place les lettres sur les sommets correspondants :

let r_graph () =
  let
  rec a = {point= 'a'; arrows= [t;y;c];     time=0}
  and c = {point= 'c'; arrows= [e];         time=0}
  and d = {point= 'd'; arrows= [e];         time=0}
  and e = {point= 'e'; arrows= [];          time=0}
  and i = {point= 'i'; arrows= [c;d];       time=0}
  and l = {point= 'l'; arrows= [e];         time=0}
  and m = {point= 'm'; arrows= [e];         time=0}
  and o = {point= 'o'; arrows= [l;m;p;s;w]; time=0}
  and p = {point= 'p'; arrows= [e];         time=0}
  and r = {point= 'r'; arrows= [a;i;o;u];   time=0}
  and s = {point= 's'; arrows= [e];         time=0}
  and t = {point= 't'; arrows= [];          time=0}
  and u = {point= 'u'; arrows= [d;l];       time=0}
  and w = {point= 'w'; arrows= [];          time=0}
  and y = {point= 'y'; arrows= [];          time=0}
  in  r;;

La mauvaise nouvelle c'est que l'interpréteur OCaml est bien maladroit quand il s'agit d'afficher un tel graphe, il parcourt la structure comme un arbre en affichant plusieurs fois les sommets partagés. Pire, si notre graphe contenait une seule boucle elle serait affichée comme une structure infinie, jusqu'à épuisement de la capacité de la console.
C'est pourquoi nous n'avons pas défini le graphe comme une valeur, mais comme une fonction qui attend un élément unit avant de renvoyer le graphe, de cette façon nous coupons court à toute tentative d'affichage tout en définissant un raccourci bien commode pour tester nos fonctions sur ce graphe :

# length_graph (r_graph ());;
- : int = 15
# exists_graph ((=) 'n') (r_graph ());;
- : bool = false
# exists_graph ((=) 'o') (r_graph ());;
- : bool = true
# flatten_graph (r_graph ());;
- : char list =
['r'; 'a'; 't'; 'y'; 'c'; 'e'; 'i'; 'd'; 'o'; 'l'; 'm'; 'p'; 's'; 'w'; 'u']

La bonne nouvelle c'est qu'il n'est pas bien difficile d'écrire une procédure de décision pour les automates :

# let rec recognized l auto =
  match l with
  | [] -> false
  | c::[] -> auto.point=c && auto.arrows=[] 
  | c::l  -> auto.point=c && List.exists (recognized l) auto.arrows
  ;;
val recognized : 'a list -> 'a rooted_digraph -> bool = <fun>
# recognized ['r';'o';'p';'e'] (r_graph ());;
- : bool = true
# recognized ['r';'a';'t';'e'] (r_graph ());;
- : bool = false

Comme nous l'avons mentionné au paragraphe déclarations de variables, il n'est pas possible en OCaml de modifier la valeur d'une variable. D'autre part nous venons de voir qu'il est possible de modifier un champ mutable d'un enregistrement. On peut dès lors imaginer un type conteneur pour un champ mutable. C'est précisément ce qu'est le type prédéfini 'a ref, un type enregistrement polymorphe contenant un seul champ mutable nommé contents :

# type 'a ref = {
    mutable contents : 'a;
  };;
type 'a ref = { mutable contents : 'a; }

Ce type possède un constructeur prédéfini :

# let ref v = {contents = v};;
val ref : 'a -> 'a ref = <fun>

Évidemment la fonction duale est un accesseur, également prédéfini, en position préfixe :

# let (!) r = r.contents;;
val ( ! ) : 'a ref -> 'a = <fun>

Mais la nouveauté réside bien entendu dans les méthodes, également prédéfinies, l'assignation (en position infixe) et ses deux variantes plus spécialisées, l'incrémentation et la décrémentation :

# let (:=) r v = r.contents <- v;;
val ( := ) : 'a ref -> 'a -> unit = <fun>

# let incr r = r.contents <- succ r.contents;;
val incr : int ref -> unit = <fun>

# let decr r = r.contents <- pred r.contents;;
val decr : int ref -> unit = <fun>

Avec ces outils il n'est toujours pas possible de modifier la valeur d'une variable, mais il devient possible de modifier le contenu de la valeur d'une variable, par exemple on pourra déclarer une variable r1 de type int ref :

# let r1 = ref 1;;
val r1 : int ref = {contents = 1}

Ce qui permettra, à valeur constante, de modifier son contenu, par exemple comme ceci :

# let () = (r1 := 4) in !r1;;
- : int = 4

Comme let () = expr1 in expr2 est équivalent à expr1; expr2 on peut écrire plus simplement :

# r1 := 4; !r1;;
- : int = 4

Après cette opération la variable r1 désigne toujours le même enregistrement, cependant le champ contents de cet enregistrement a été modifié :

# r1;;
- : int ref = {contents = 4}

Pour illustrer les possibilités des références nous allons implémenter une fonction prédécesseur pour l'appel de fonction, en conséquence notre fonction pred_call appliquera la fonction f non pas à son argument courant, mais à son argument au précédent appel, nous devons donc fournir une fonction f de type 'a → 'b et un argument initial init de type 'a, le résultat sera une nouvelle fonction de type 'a → 'b :

# let pred_call f init =
  let memo = ref (f init) in
  fun n -> let result = !memo
           in  memo := f n; result;;
val pred_call : ('a -> 'b) -> 'a -> 'a -> 'b = <fun>

Ainsi une fonction successeur pour le moins étrange pourrait renvoyer le succ de son argument au précédent appel :

# let pred_succ = pred_call succ 0;;
val pred_succ : int -> int = <fun>

Voici un exemple de session :

# pred_succ 34;;
- : int = 1
# pred_succ 17;;
- : int = 35
# pred_succ 22;;
- : int = 18

Après cette courte présentation de l'utilité des champs mutable et des références dans un style qui reste somme toute assez fonctionnel, nous allons entrer de plain-pied dans le monde de la programmation impérative.

Il n'existe que deux boucles prédéfinies en OCaml, la boucle while et la boucle for.

La boucle while expression do instruction done répète l'instruction tant que l'expression est égale à true.

Ainsi on se convaincra aisément que le code ci-dessous implémente la même fonction factorial que celle du paragraphe II.12 :

let factorial n =
  assert(n >= 0);
  let i = ref n and result = ref 1 in
  while !i > 1 do
    result := !result * !i;
    decr i
  done;
  !result;;

Règle d'inférence de type
La règle d'inférence d'une expression while expression do instruction done distingue trois cas possibles :

• ou bien expression n'est pas de type bool alors l'expression est mal typée ;
• ou bien instruction n'est pas de type unit alors l'expression est mal typée ;
• ou bien l'expression est de type unit.

Dans les cas où l'on connaît par avance le nombre de répétitions on peut économiser un let en utilisant une boucle for au lieu de la boucle while, on a alors deux sortes de boucle for à notre disposition, ou bien la boucle ascendante for ... to ... do ... done qui incrémente le compteur de boucle :

let factorial n =
  assert(n >= 0);
  let result = ref 1 in
  for i = 1 to n do
    result := !result * i
  done;
  !result;;

Ou bien la boucle descendante for ... downto ... do ... done qui décrémente le compteur de boucle :

let factorial n =
  assert(n >= 0);
  let result = ref 1 in
  for i = n downto 1 do
    result := !result * i
  done;
  !result;;

Ici, nous ne donnerons pas davantage d'exemples de boucles, car ceci fera l'objet du chapitre VI.

Règle d'inférence de type
La règle d'inférence d'une expression for var = start (to|downto) limit do instruction done distingue trois cas possibles :

• ou bien start n'est pas de type int ou encore limit n'est pas de type int alors l'expression est mal typée ;
• ou bien instruction n'est pas de type unit alors l'expression est mal typée ;
• ou bien l'expression est de type unit.

Remarque : l'expression limit est évaluée une fois et une seule pour toute la durée de la boucle for.

Les tableaux (array) permettent l'accès à leur nième élément en temps constant. En outre les éléments d'un tableau sont toujours assignables. Les fonctions sur les tableaux sont réunies dans le module Array, et en particulier :

• Array.length a renvoie le nombre d'éléments dans le tableau a, les indices dans un tableau a seront toujours compris entre 0 et Array.length a - 1 ;
• Array.make n x crée un nouveau tableau de longueur n et dont tous les éléments valent x ;
• Array.get a n renvoie le nième élément du tableau a, cette fonction possède une forme infixe a.(n) ;
• Array.set a n x assigne la valeur x au nième élément du tableau a, cette instruction possède une forme infixe a.(n) ← x.

Ces quelques fonctions sont amplement suffisantes pour implémenter l'équivalent du tri-fusion sur les tableaux.
Pour une spécification plus complète du module Array veuillez consulter sa documentation en ligne.

Écrivons d'abord une fonction qui échange deux éléments d'un tableau a :

let swap a i j =
  let tmp = a.(i) in
  a.(i) <- a.(j); 
  a.(j) <- tmp;;

L'algorithme QiSort est une sorte d'équivalent du tri-fusion pour un tableau, il est bien décrit sur cette page et son implémentation en OCaml est assez immédiate :

let array_sort a =
  let rec qi_sort lower upper =
    let left = ref lower and right = ref upper in
    while !left < !right do
      while !left < !right && a.(!left) < a.(!right) do decr right done;
      if !left < !right then begin
        swap a !left !right;
        incr left;
        while !left < !right && a.(!left) < a.(!right) do incr left done;
        if !left < !right then begin
          swap a !left !right;
          decr right;
        end;
      end;
    done;
    decr left;
    incr right;
    if lower  < !left then qi_sort lower  !left;
    if !right < upper then qi_sort !right upper;
  in qi_sort 0 (Array.length a - 1);;

La notation OCaml pour les tableaux en extension est comparable à celle des listes en extension, à la différence de la barre verticale qui suit le crochet ouvrant et qui précède le crochet fermant :

# let a=[|4;2;5;8;6;9;3;7;0;1|] in array_sort a; a;;
- : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]

Dans la partie VI on développera un module complet qui mettra en œuvre toutes nos nouvelles connaissances sur les références, les tableaux et les boucles, tout cela sans rien mettre de côté de l'approche qualité qui a fait ses preuves jusqu'ici.

À signaler : du fait de la proximité conceptuelle des chaînes de caractères (string) avec les tableaux de char, le module String fournit une interface assez comparable à celle du module Array.
C'est ainsi que les quatre fonctions pour les tableaux ont leurs équivalents exacts pour les chaînes :

• String.length s renvoie le nombre de caractères dans la chaîne s, les indices dans une chaîne s seront toujours compris entre 0 et String.length s - 1 ;
• String.make n c crée une nouvelle chaîne de longueur n et dont tous les caractères valent c ;
• String.get s n renvoie le nième caractère de la chaîne s, cette fonction possède une forme infixe s.[n] ;
• String.set s n c assigne la valeur c au nième caractère de la chaîne s, cette instruction possède une forme infixe s.[n] ← c.

Le module Pervasives exporte des fonctions pour l'affichage des valeurs élémentaires :

# print_int;;
- : int -> unit = <fun>
# print_float;;
- : float -> unit = <fun>
# print_char;;
- : char -> unit = <fun>
# print_string;;
- : string -> unit = <fun>
# print_newline;;
- : unit -> unit = <fun>

Parmi ces fonctions seule print_newline force l'affichage, les autres ne font que remplir un cache d'affichage qui sera vidé lors d'un appel print_newline (). On peut aussi vider explicitement le cache, et ainsi forcer l'affichage sans passage à la ligne, à l'aide de flush stdout.

Le module Pervasives exporte aussi le type in_channel qui désigne un fichier accessible en lecture ainsi que plusieurs fonctions d'accès parmi lesquelles on pourra retenir au moins les trois suivantes :

• open_in : string -> in_channel qui ouvre en lecture le fichier texte situé au chemin d'accès spécifié ;
• input_line : in_channel -> string qui lit une ligne de texte dans un fichier ouvert en lecture ;
• close_in : in_channel -> unit qui ferme un fichier texte ouvert à l'aide de open_in.

Le module Printf quant à lui exporte des fonctions pour l'affichage de chaînes formatées.
Par exemple la fonction Printf.printf accepte des paramètres similaires à son homologue en C :

# Printf.printf "Delay: %04d\n" 89;;
Delay: 0089
- : unit = ()