Programmation:OCaml:Fonctionnel:VS:Imperatif:Structures

Introduction

Notre objectif dans ce cours est d'étudier les différences concrètes entre programmation impérative et programmation fonctionnelle, notamment en terme de structures de données. Nous étudierons la nature des différentes structures, l'impact que peut avoir l'utilisation d'une version fonctionnelle par rapport à une version impérative, les avantages que peuvent apporter l'une et l'autre représentation et enfin, nous verrons les cas classiques d'utilisations.

Impératif et fonctionnel: quelles différences ?

La frontière entre les deux mondes n'est pas toujours bien comprise. En effet, la notion de structures de données fonctionnelles n'est pas forcément spécifique aux langages dits fonctionnelles. En réalité, les structures de données fonctionnelles font références à une approche particulière d'implantation de ces structures.

En premier lieu, coupons court à la confusion usuelle: fonctionnel ne doit pas être systématiquement assimilé à récursif et impératif à itératif. Voici ce qui s'approche le plus d'une définition correcte pour les deux types de structures:

On parle de structure fonctionnelle lorsque:

• On peut identifier les valeurs particulières (collection vide en générale) de manière unique indépendamment d'un processus de stockage spécifique.
• Les opérations de modifications de la structure sont des fonctions renvoyant une copie modifiée de l'original sans affecter celui-ci.
• Aucune opération ne modifie la structure en place.

On parle de structure impérative lorsque:

• La création d'une instance de la structure implique toujours l'allocation d'un nouvel espace mémoire. Les valeurs particulières ne sont pas physiquement égales.
• Les opérations de modifications sont des procédures qui n'engendrent aucune copie de l'original mais modifie celui-ci en place.
• Les structures impératives persistent indépendamment des fonctions qui les manipulent (elles doivent donc détruites explicitement en fin de vie.)

On le voit, aucune de ces définitions n'impliquent une forme d'algorithme particulière, ni même un paradigme de programmation particulier. Pourtant, nous le verrons plus tard, les fonctionnalités de certains langages s'accordent mieux avec certaines formes de structures.

Même si, en théorie, il est possible de représenter toutes structures de manière fonctionnelle ou impértive, il existe des structures qu'il est plus logique de représenter d'une manière plutôt qu'une autre. Notamment, les structures suivantes sont plus naturellement impératives:

• vecteurs et matrices
• tables de hash
• piles et files (sauf dans certains cas)

Au contraire, les structures suivantes sont plus fonctionnelles:

• listes chaînées
• arbres binaires (ou généraux)
• BST/AVL
• ensembles ordonnées

Structures de données fonctionnelles

Les structures de données impératives sont usuelles, on les rencontre assez souvent dans la pratique et sont même parfois la seule forme de définition que l'on utilise en algorithmique. Nous insisterons donc plus sur les formes fonctionnelles.

Pas de modification ?

L'exemple séminal en terme de structure fonctionnelle est la liste chaînée. Sa nature profondément récursive en fait un compagnon classique du programmeur fonctionnel. Les premières formes de listes sont même apparues en lambda calcul via l'encodage de Church qui (sous forme de fonctions) ressemble assez à la fonction OCaml List.fold_right. Voici la définition générique d'une liste, une liste est:

• soit une liste vide;
• soit un élément associé à une liste.

La liste est donc construite à partir de deux constructeurs (en terme de spécifications algèbriques): la liste vide ([] en OCaml) et la construction tête-reste (:: en OCaml). On peut à partir de ces constructeurs définir les différents opérations classiques sur les listes (taille, recherche, insertions ... ) On notera qu'une représentation dans un langage impératif correspondrait à la même logique: la liste est un pointeur, si celui-ci est null la liste est vide, sinon, il s'agit du constructeur (sous la forme d'un enregistrement) associant la tête et le reste.

Pour comprendre la nature fonctionnelle des listes, nous allons prendre un exemple en OCaml utilisant une insertion triée:

let print_int_list l =
  begin
    Printf.printf "[ ";
    List.iter (Printf.printf "%d; ") l;
    Printf.printf "]\n";
  end
 
let rec insert x = function
    [] -> x::[]
  | h::t when h<x -> h::insert x t
  | l -> x::l
 
let main () =
  let l = [] in
  let l1 = insert 1 l in
  let l2 = insert 2 l1 in
  let l3 = insert 3 l1 in
    begin
      print_int_list l;
      print_int_list l1;
      print_int_list l2;
      print_int_list l3;
      print_int_list (insert 4 l3);
      print_int_list l3;
      exit 0;
    end
 
let _ = main ()

On obtient la sortie suivante:

> ocamlopt.opt -o ex_list ex_list.ml
> ./ex_list
[ ]
[ 1; ]
[ 1; 2; ]
[ 1; 3; ]
[ 1; 3; 4; ]
[ 1; 3; ]
>

On observe bien que les listes l, l1 et l3 ne sont pas affectées par les opérations d'insertion effectuées sur elle.

L'opération d'insertion est en soit très intéressante: on reconstruit une liste nouvelle liste avec les éléments de la tête que l'on accroche au résultat de l'appel récursif. On reconstruit donc ici (au moins) la tête de la liste.

Un point important à noter est qu'en OCaml il n'est pas possible de modifier le corps d'une liste, il n'y a donc aucune ambiguité sur la nature fonctionnelle de celle-ci. Mais dans un langage impératif, il faut garantir d'une manière ou d'une autre l'abscence de modification sur les listes. La solutions classiques consiste à abstraire la structure de donnée en ne fournissant que les opérations correctes (sans modification en place) et en cachant l'implantation de la structure. On verra plus loin que cette garantie est importante.

La question qui nous vient imméditamment est: la liste est-elle intégralement dupliquée ? Et cette question est importante, en effet, si lors d'une insertion (même en tête) on devait recopier l'intégralité de la liste, le coût serait bien trop important. Nous allons voir que, comme nous nous en doutons, ce n'est pas le cas.

Copies, partages et optimisations

Le fait de renvoyer systématiquement une nouvelle valeur à chaque opération sur la liste peut sembler cacher des coûts non négligeable. En réalité, il n'en est rien. Un impératif important pour un langage de haut niveau est d'éviter, le plus possible, les complexités cachées. En effet, si une opération annodine (renvoyer le reste de la liste par exemple) cache en réalité un coût important (parcours complet de la structure par exemple) le programmeur perdrait la maîtrise sur ses programmes.

Par conséquent, la fonction d'ajout en tête du précédent exemple ne recopie pas la partie non modifiée de la liste. L'impacte est multiple:

• pas de surcoût pour recopier la liste
• partage d'une partie de la liste entre la nouvelle et l'ancienne
• cohabitation de version multiples d'une même liste après plusieurs opérations d'ajout.

La première conséquent est la nécessité de garantir l'abscence de modification en place de la liste: en effet, si tel était le cas, on pourrait modifier une liste indirecrement sans le vouloir.

Le deuxième point à considérer est la gestion de la mémoire: les portions non partagées qui ne possèdent plus de point d'entrée continuent à encombrer la mémoire. Il faut pouvoir les supprimer: dans un langage impératif classique, l'opération serait complexe, puisqu'il faut repérer les points de jonctions pour ne pas supprimer les parties partagées. Heureusement, les langages fonctionnels sont souvent accompagné d'une Garbage Collector: le gc se charge d'identifier et de libérer les portions de mémoire réservées mais plus accessible et ceux sans risque pour le reste du programme.

Enfin, il faut tout de même considérer nos opérations de manière à éviter les reconstructions inutiles. En effet, considérons ces versions de l'opération d'insertion dans une liste triée:

let rec insert x = function
    [] -> x::[]
  | h::t when x<h -> x::h::t
  | h::t -> h::insert x t
 
let rec insert2 x = function
    [] -> x::[]
  | h::_ as l when x<h -> x::l
  | h::t -> h::insert2 x t

La différence semble minime (utilisation d'une variable d'alias dans la second version) et pourtant, elle n'est pas si annodine. Dans la première version dans le cas de l'insertion en tête, on reconstruisait une liste à partir de x, h et t le reste da la liste et donc l'ancienne tête h ne faisait pas partie du bloc partagé entre les deux listes. Dans la seconde version, le fait d'utiliser un alias sur le reste de la liste (h y compris) implique que l'ancienne tête fait bien partie de la zone partagée entre les deux listes. Avec un peu d'attention, il est donc possible de diminuer encore le surcoût. Pour simplifier, on écrira la fonction d'insertion de la manière suivante:

let rec insert x = function
    [] -> x :: []
  | h::t when h<x -> h::insert x t
  | l -> x::l

Comme on l'a vu dans l'exemple, il est possible de construire des opérations fonctionnels sur certains structures de données sans impliquer de surcoût trop important (tant en terme de temps que de mémoire.) Bien que l'on se soit limité à un exemple utilisant les listes, on retrouve le même principe pour toutes les structures de données de même nature (chaînées et non cyclique) comme les arbres.

Bien choisir sa structure

On oublie souvent le coût induit par l'utilisation de structures de données, pourtant celles-ci ont presqu'autant d'impact que l'algorithme lui même. Dans les critères de sélection, l'opposition fonctionnelle/impératif est souvent non-négligeable.

Nous allons considérer cette quesion au travers d'un exemple classique : l'évaluation d'expressions arithmétque avec variables (locales et globales.)

Voici le type permettant de représenter nos expressions (basé sur des constructions de type let ... in à la OCaml):

type expr =
    Int of int
  | BinOp of (int -> int -> int) * expr * expr
  | UniOp of (int -> int) * expr
  | Var of string
  | Let of string * expr * expr

On complèra ces expressions à l'aide d'instructions minimales définies par le type:

type instr =
    Print of expr
  | Affect of string * expr

En dehors de la gestion des variables, l'évaluation de ces expressions est relativement simple: on effectue un parcours en profondeur de l'arbre. Voici un extrait du code correspondant (la gestion des variables a complètement été suprimée):

let rec eval = function
    Int i -> i
  | BinOp(op,e1,e2) ->
      op (eval e1) (eval e2)
  | UniOp(op,e) ->
      op (eval e)

La gestion des variables va mettre en jeux la notion d'environnement: une structure qui associe nom de variable et valeur.

Questions de complexité

Le premier point, en général évident, est la complexité associée aux opérations sur la structure de données. Dans notre exemple, nous devons considérer des opérations différentes pour les variables locales et pour les variables globales.

• Opérations pour les variables locales:
  • ajout
  • recherche
  • suppression
• Opérations pour les variables globales:
  • ajout
  • remplacement
  • recherche

Il faut aussi prendre en considération la fréquence avec laquelle les opérations ont lieux: dans le cas des variables locales, les opérations d'ajout et de suppression, bien que moins fréquentes que celle de recherche, sont souvent sollicitées, tandis que dans le cadre des variables globales, l'opération d'ajout est limitée à une phase initiale, les opérations prédominantes étant la recherche et le remplacement.

Enfin, on observe également que les opérations d'ajout et de suppression dans le cadre des variables locales sont imbriqués: lorsque l'on supprime une variable de l'environnement aucune variable présente dans l'environnement ne l'était pas au moment où la variable à supprimer a été ajoutée.

Observons les différentes structures de données qui sont à notre disposition:

• Listes associatives:
  • structure fonctionnelle
  • insertion en temps constants
  • recherche en temps linéaire
  • suppression (en tête) en temps constant
  • remplacement en temps linéaire
  • implantation très simple
• Tables de hachages:
  • structure impérative
  • insertion en temps linéaire (ou pire)
  • recherche en temps constant
  • suppression en temps constant (avec perte d'espace) ou linéaire (sinon)
  • remplacement en temps constant
  • implantation relativement complexe (mais existe souvent sous forme de bibliothèque)
• AVL:
  • structure fonctionnelle
  • insertion en temps logarithmique
  • recherche en temps logarithmique
  • suppression en temps logarithmique
  • remplacement en temps logarithmique
  • implantation relativement complexe (mais existe souvent sous forme de bibliothèque)

Comme la recherche reste l'opération prédominante, on limitera l'usage des listes associatives aux prototypes lorsque les autres structures ne sont pas disponibles.

L'expérience montre que la gain sur le couple d'opération ajout/suppression dans les AVL est suffisant pour compenser le perte dans l'opération de recherche dans les environnements destinés aux variables locales. Par contre, pour les variables globales, on préfera les tables de hachages.

Bénéfices cachés

Une fois que nous avons défricher le terrain avec la question de la complexité, il nous reste à finaliser notre choix. Nous allons ici voir que la différence entre fonctionnel et impératif, va nous permettre de faire un bon (le meilleur ?) choix.

Observons le cas des variables locales: le problème qui nous intéressent concerne l'évaluation de la construction let .. in. En effet, lorsque l'on évalue l'expression let x = e1 in e2, il va falloir étendre l'environnement avec l'association entre x et le résultat de l'évaluation sur e1 pour évaluer e2. Cette association devant être supprimée après.

Supposons que notre environnement (sous forme impérative) dispose des opérations suivantes:

• ajout: add x v env
• recherche: find x env
• suppression: remove x env

La fonction d'évaluation devient:

let rec eval env = function
    Int i -> i
  | BinOp(op,e1,e2) ->
      op (eval env e1) (eval env e2)
  | UniOp(op,e) ->
      op (eval env e)
  | Var x -> find x env
  | Let(x,e1,e2) ->
      begin
        add x (eval env e1) env;
        let r = eval env e2 in
          remove x env;
          r
      end

On remarque l'entrelacement inélégant entre l'ajout et la suppression de l'évaluation de la deuxième expression. Mais cette solution est impérative, il est possible de faire différent en fonctionnel: étant donné que la suppression vient clore l'ajout intial, ce que l'on veut c'est que l'environnement après évaluation soit le même qu'à l'entrée dans la fonction.

Rien de plus simple avec une structure fonctionnellle: l'ajout engendre une nouvelle version de l'environnement (avec les partages qui vont bien) et delà, la suppression devient inutile, il suffit de récupérer l'ancienne version. De plus la solution est particulièrement esthétique et beaucoup plus simple.

Pour les variables globales, la solution est plus évidente, il n'y a jamais de suppression, et le remplacement prédomine l'insertion.

Pour la version finale de notre exemple, nous avons choisi des AVL (module Map d'OCaml) pour les variables locales et des tables de hachages pour les variables globales.

type expr =
    Int of int
  | BinOp of (int -> int -> int) * expr * expr
  | UniOp of (int -> int) * expr
  | Var of string
  | Let of string * expr * expr
 
type instr =
    Print of expr
  | Affect of string * expr
 
module Env = Map.Make(String)
 
let rec eval eg el = function
    Int i -> i
  | BinOp(op,e1,e2) ->
      op (eval eg el e1) (eval eg el e2)
  | UniOp(op,e) ->
      op (eval eg el e)
  | Var x ->
      try
	Env.find x el
      with
	  Not_found -> Hashtbl.find eg x
  | Let(x,e1,e2) ->
      eval eg (Env.add x (eval eg el e1)) e2
 
let eval_instr eg = function
    Print e -> Format.printf "%d\n" (eval eg Env.empty e)
  | Affect(x,e) ->
      Hashtbl.replace eg x (eval eg Env.empty e)

Conclusion

Nous avons dans ce cours que les choix entre impératif (modification en place des données) et fonctionnel (reconstruction d'une nouvelle valeur à chaque opération) n'est pas juste une affaire de goût. Nous avons vu également, que contrairement à certaines légendes urbaines, le choix de structures fonctionnelles n'est pas synonyme de perte de performance.

Par contre, une utilisation judicieuse des structures fonctionnelles, implique souvent de disposer de certains mécannismes comme la gestion automatique de la mémoire (Garbage Collector) ou la protection contre la modification des données.

Cours	Partie
Cours de Programmation EPITA/spé	Programmation:OCaml