Quel style choisir ?

Quel style choisir ?

Il n'est pas ici question de religion ni d'esthétique, il n'y a pas a priori un style plus joli ou meilleur que l'autre. En revanche, selon le problème à résoudre un style peut être plus adéquat que l'autre.

La première règle à appliquer est celle de la simplicité. L'algorithme à réaliser (qu'il soit écrit dans un livre ou qu'il soit à l'état de germe dans l'esprit du programmeur) est lui-même décrit dans un certain style; il est naturel d'utiliser le même style pour en faire l'implantation.

Le second critère de choix est l'efficacité du programme. On peut dire qu'un programme impératif (bien écrit) est plus efficace que son homologue fonctionnel, mais dans de très nombreux cas la différence n'est pas suffisamment notable pour justifier de compliquer le code en adoptant un style impératif là où le fonctionnel serait naturel. La fonction map de la section précédente fournit un bel exemple de problème naturellement exprimé dans le style fonctionnel et qui ne gagne rien à être écrit en impératif.

Séquence ou composition de fonctions

Nous avons vu que dès qu'un programme effectue des effets de bord, il est nécessaire d'expliciter précisément l'ordre d'évaluation des éléments de ce programme. Ceci peut se faire dans les deux styles :

fonctionnel :: en utilisant le fait que Objective CAML est un langage strict, c'est-à-dire que l'argument est calculé avant l'application de la fonction. L'expression (f (g x)) est calculée en évaluant d'abord (g x), puis en passant le résultat comme argument de f. Avec des expressions plus complexes, on peut nommer le résultat intermédiaire avec la construction let in mais le principe reste le même : let aux=(g x) in (f aux).
impératif :: en utilisant la séquence ou les autres structures de contrôle (boucles). Dans ce cas, le résultat n'est pas une valeur rendue par une fonction, mais ses effets de bord sur la mémoire : aux:=(g x) ; (f !aux).

Examinons ce problème de choix de style sur un exemple. L'algorithme de tri rapide sur un vecteur se décrit récursivement comme ceci :

choisir un pivot : choisir l'indice d'un élément du tableau;
permuter autour du pivot : permuter les éléments du tableau de sorte que les éléments inférieurs au pivot soient situés avant le pivot et vice et versa;
trier (suivant le même algorithme) les deux tableaux obtenus : les éléments précédant le pivot et ceux le suivant.

Le choix de l'algorithme, à savoir de modifier un tableau pour que ses éléments soient triés, nous incite à utiliser un style impératif au moins pour les manipulations des données.

On commence par définir une fonction permutant deux éléments d'un tableau.


# let permute_element tab n p = 
   let aux = tab.(n) in tab.(n) <- tab.(p) ; tab.(p) <- aux  ;;
val permute_element : 'a array -> int -> int -> unit = <fun>

Le choix d'un bon pivot est déterminant pour l'efficacité de l'algorithme, mais nous retenons ici le choix le plus simple : rendre l'indice du premier élément du (sous) tableau.


# let choisir_pivot tab debut fin = debut ;;
val choisir_pivot : 'a -> 'b -> 'c -> 'b = <fun>

Écrivons l'algorithme que nous souhaitons utiliser pour permuter les éléments du tableau, autour du pivot.

on positionne le pivot au début du tableau en le permutant;
i est l'indice de second élément du tableau;
j est l'indice du dernier élément du tableau;
si l'élément d'indice j est plus grand que le pivot on le permute avec l'élément d'indice i et on incrémente i; sinon on décrémente j;
tant que i est inférieur à j on recommence l'opération précédente;
rendu à ce point chaque élément d'indice inférieur à i (ou j) est inférieur au pivot, les autres lui sont supérieurs; si l'élément d'indice i est inférieur au pivot on le permute avec le pivot, sinon on permute son prédécesseur.

L'implantation de cet algorithme va naturellement adopter des structures de contrôle impératives.


# let permute_pivot tab debut fin ind_pivot = 
    permute_element tab debut ind_pivot ;
    let i = ref (debut+1) and j = ref fin and pivot = tab.(debut) in
    while !i < !j do 
      if tab.(!j) >= pivot then decr j 
      else
        begin
          permute_element tab !i !j ;
          incr i
        end
    done ;
    if tab.(!i) > pivot then decr i ;
    permute_element tab debut !i ;
    !i 
 ;;
val permute_pivot : 'a array -> int -> int -> int -> int = <fun>

Outre son effet sur le tableau, cette fonction retourne en résultat l'indice du pivot.

Il ne nous reste plus qu'à composer les différentes étapes et mettre en place la récursion sur les sous-tableaux.


# let rec quick tab debut fin = 
    if debut < fin 
    then 
      let pivot = choisir_pivot tab debut fin in 
      let place_pivot = permute_pivot tab debut fin pivot in 
      quick (quick tab debut (place_pivot-1)) (place_pivot+1) fin
    else tab ;;
val quick : 'a array -> int -> int -> 'a array = <fun>

Nous avons ici utilisé les deux styles. Le pivot choisi sert d'argument à la permutation autour de ce pivot, et le rang du pivot obtenu après permutation est un argument de l'appel récursif. Par contre, le tableau obtenu après permutation n'est pas retourné par la fonction permute_pivot, ce résultat est rendu par effet de bord. En revanche, la fonction quick retourne un tableau et le tri des sous-tableaux est obtenu par composition des appels récursifs.

La fonction principale est :


# let quicksort tab = quick tab 0 ((Array.length tab)-1) ;;
val quicksort : 'a array -> 'a array = <fun>

C'est une fonction polymorphe car la relation d'ordre < sur les éléments du tableau est elle même polymorphe.


# let t1 = [|4;8;1;12;7;3;1;9|] ;;
val t1 : int array = [|4; 8; 1; 12; 7; 3; 1; 9|]
# quicksort t1 ;;
- : int array = [|1; 1; 3; 4; 7; 8; 9; 12|]
# t1 ;;
- : int array = [|1; 1; 3; 4; 7; 8; 9; 12|]
# let t2 = [|"le"; "petit"; "chat"; "est"; "mort"|] ;;
val t2 : string array = [|"le"; "petit"; "chat"; "est"; "mort"|]
# quicksort t2 ;;
- : string array = [|"chat"; "est"; "le"; "mort"; "petit"|]
# t2 ;;
- : string array = [|"chat"; "est"; "le"; "mort"; "petit"|]

Partage ou copie de valeurs

Tant que les valeurs que nous manipulons ne sont pas modifiables, il n'est pas utile de savoir si elles sont partagées ou non.


# let id x = x ;;
val id : 'a -> 'a = <fun>
# let a = [ 1; 2; 3 ] ;;
val a : int list = [1; 2; 3]
# let b = id a ;;
val b : int list = [1; 2; 3]

Que b soit une copie de la liste a ou que se soit la même liste ne change rien puisque ce sont de toutes façons des valeurs intangibles. Mais si à la place d'entiers nous mettons des valeurs modifiables, nous avons besoin de savoir si la modification d'une valeur entraîne la modification de l'autre.

L'implantation du polymorphisme d'Objective CAML effectue une copie des valeurs immédiates et le partage des valeurs structurées. Bien que le passage des arguments soit toujours par valeur, seul le pointeur d'une valeur structurée est copié. C'est bien le cas de la fonction id :


# let a = [| 1 ; 2 ; 3 |] ;;
val a : int array = [|1; 2; 3|]
# let b = id a ;;
val b : int array = [|1; 2; 3|]
# a.(1) <- 4 ;;
- : unit = ()
# a ;;
- : int array = [|1; 4; 3|]
# b ;;
- : int array = [|1; 4; 3|]

Nous avons ici un vrai choix de programmation pour décider quelle est la manière la plus efficace de représenter une donnée. D'un côté, l'utilisation de valeurs modifiables permet de faire des manipulations en place (c'est-à-dire sans faire d'allocation) mais oblige, dans certains cas, à faire des copies là où l'utilisation d'une valeur non modifiable aurait permis de faire un partage. Nous illustrons ceci avec deux façons d'implanter les listes.


# type 'a liste_fixe = LFnil | LFcons of 'a * 'a liste_fixe ;;
# type 'a liste_modifiable = LMnil | LMcons of 'a * 'a liste_modifiable ref ;;

Les listes fixes sont strictement équivalentes aux listes d'Objective CAML alors que les listes modifiables sont plus dans un style à la C où un maillon est une valeur plus une référence sur le maillon suivant.

Avec les listes fixes, il n'y a qu'une seule façon d'écrire la concaténation et elle impose de dupliquer la structure de la première liste; en revanche, la seconde liste peut être partagée avec le résultat.


# let rec concat l1 l2 = match l1 with 
     LFnil -> l2
   | LFcons (a,l11) -> LFcons(a, (concat l11 l2)) ;;
val concat : 'a liste_fixe -> 'a liste_fixe -> 'a liste_fixe = <fun>

# let lf1 = LFcons(1, LFcons(2, LFnil))
 and lf2 =  LFcons(3, LFcons(4, LFnil)) ;;
val lf1 : int liste_fixe = LFcons (1, LFcons (2, LFnil))
val lf2 : int liste_fixe = LFcons (3, LFcons (4, LFnil))
# let lf3 = concat lf1 lf2 ;;
val lf3 : int liste_fixe =
  LFcons (1, LFcons (2, LFcons (3, LFcons (4, LFnil))))
# lf1==lf3 ;;
- : bool = false
# let tlLF l =  match l with 
   LFnil       -> failwith "Liste vide" 
 | LFcons(_,x) -> x ;;
val tlLF : 'a liste_fixe -> 'a liste_fixe = <fun>
# tlLF(tlLF(lf3)) == lf2 ;;
- : bool = true

Grâce à ces exemples, nous voyons que les premiers maillons de lf1 et de lf3 sont distincts alors que la seconde partie de lf3 est exactement lf2.

Avec les listes modifiables, nous avons le choix entre modifier les arguments (fonction concat_share) ou créer une nouvelle valeur (fonction concat_copy)


# let rec concat_copy l1 l2 =  match l1 with 
     LMnil  -> l2
   | LMcons (x,l11) -> LMcons(x, ref (concat_copy !l11 l2)) ;;
val concat_copy :
  'a liste_modifiable -> 'a liste_modifiable -> 'a liste_modifiable = <fun>

Cette première solution, concat_copy, donne un résultat similaire à la fonction précédente concat. Voici une seconde solution qui partage entièrement arguments et résultat.


# let concat_share l1 l2 = 
  match l1 with
    LMnil -> l2
  | _     -> let rec set_last = function
                LMnil       -> failwith "concat_share : cas impossible !!"
              | LMcons(_,l) -> if !l=LMnil then l:=l2 else set_last !l
             in
               set_last l1 ;
               l1 ;;
val concat_share :
  'a liste_modifiable -> 'a liste_modifiable -> 'a liste_modifiable = <fun>

La concaténation avec partage ne demande aucune allocation (on n'utilise pas le constructeur LMcons), on se contente de faire pointer le dernier maillon de la première liste vers la seconde. Mais alors, la concaténation est susceptible de modifier les arguments qui sont passés à la fonction.


# let lm1 = LMcons(1, ref (LMcons(2, ref LMnil)))
 and lm2 = LMcons(3, ref (LMcons(4, ref LMnil))) ;;
val lm1 : int liste_modifiable =
  LMcons (1, {contents=LMcons (2, {contents=LMnil})})
val lm2 : int liste_modifiable =
  LMcons (3, {contents=LMcons (4, {contents=LMnil})})
# let lm3 = concat_share lm1 lm2 ;;
val lm3 : int liste_modifiable =
  LMcons (1, {contents=LMcons (2, {contents=LMcons (...)})})

On obtient bien le résultat escompté pour lm3. Par contre la valeur liée à lm1 été modifiée.


# lm1 ;;
- : int liste_modifiable =
LMcons (1, {contents=LMcons (2, {contents=LMcons (...)})})

Cela peut donc avoir des conséquences dans le reste du programme.

Éléments de choix

Dans un programme purement fonctionnel, il est interdit d'effectuer des effets de bord, cela prohibe la manipulation de structures de données mutables, les exceptions et les entrées-sorties. Nous donnons une définition moins restrictive du style fonctionnel en disant qu'une fonction ne modifiant pas son environnement global peut être utilisée dans un style fonctionnel. Une telle fonction peut manipuler localement des valeurs mutables (et donc être écrite dans un style impératif) mais ne doit pas modifier de variables globales ni ses arguments. Nous les autorisons de surcroît à lever des exceptions. Vu de l'extérieur, ces fonctions peuvent être considérées comme des << boites noires >> dont le comportement est assimilable à celui d'une fonction purement fonctionnelle si ce n'est qu'elles sont susceptibles de rompre le contrôle par le déclenchement d'une exception. Dans le même esprit, une valeur mutable qui n'est plus modifiée après son initialisation peut être utilisée dans un style fonctionnel.

D'un autre coté, un programme écrit dans un style impératif bénéficie tout de même des avantages apportés par Objective CAML : la sûreté du typage statique, la gestion automatique de la mémoire, le mécanisme d'exception, le polymorphisme paramétrique et l'inférence de types.

Le choix entre style impératif et style fonctionnel dépend de l'application à développer. On peut néanmoins indiquer certaines orientations selon les caractéristiques de celle-ci et les critères jugés important dans son développement.

choix des structures de données : de l'utilisation de structures de données mutables ou non va découler le choix du style de programmation à adopter. En effet, le style fonctionnel est par nature incompatible avec la modification des valeurs mutables. Par contre, la construction et le parcours d'une valeur sont les mêmes quelque soit son statut. Nous rejoignons la discussion sur << modification en place vs copie >> tenue à la page ??. Nous y reviendrons en évoquant les critères d'efficacité.
structures de données imposées : si le programme doit modifier des données mutables, le style impératif est le seul possible. Si par contre, il est juste nécessaire de parcourir les valeurs, alors l'adoption du style fonctionnel garantit l'intégrité des données.
L'utilisation de structures de données récursives entraînent l'usage de fonctions elles-mêmes récursives. Celles-ci peuvent être définies en utilisant les traits de l'un ou de l'autre des styles, mais il est souvent plus facile de résonner par création d'une valeur suivant une définition par récurrence ce qui correspond à une approche fonctionnelle, que d'itérer des traitements par récursion sur cette valeur. Le style fonctionnel permet de définir des itérateurs génériques sur la structure de données manipulée, ce qui factorise le développement et le rend plus rapide.
critères d'efficacité : la modification en place est incomparablement plus efficace que la création d'une valeur. Quand l'efficacité du code est un critère prépondérant, il fera le plus souvent penché la balance vers le style impératif. Notons cependant que la nécessité de départager les valeurs peut s'avérer une tâche très ardue et en définitive plus coûteuse que de copier les valeurs dès le départ.
La pleine fonctionnalité a un coût : l'application partielle et l'utilisation de fonctions passées en argument d'autres fonctions ont un coût à l'exécution plus important que celui de l'application totale d'une fonction provenant d'une déclaration. L'usage de ce trait éminemment fonctionnel doit donc être proscrit des parties d'un programme où l'efficacité est critique.
critères de développement : le plus haut niveau d'abstraction de la programmation fonctionnelle permet d'écrire plus rapidement, un code plus compact et contenant moins d'erreurs que son équivalent impératif qui par nature est plus verbeux. Le style fonctionnel apparaît comme avantagé pour les contraintes que posent le développement d'applications conséquentes. L'indépendance d'une fonction par rapport à son contexte d'évaluation rend le code fonctionnel plus facilement découpable en petites unités examinables séparément et en fin de compte plus lisible.
La plus grande modularité du style fonctionnel avec la possibilité de passer des fonctions (donc des traitements) en argument d'autres fonctions fait que les programmes écrits dans ce style sont plus aisément réutilisables.

Ces quelques remarques montrent qu'il est souvent judicieux de mélanger les deux styles de programmation dans une application. Le style fonctionnel est plus rapide à développer et confère une organisation plus simple de l'application; mais les sections critiques en temps d'exécution auront intérêt à être développé dans un style impératif plus efficace.