Précédent Index Suivant

Comparaison entre fonctionnel et impératif

Les chaînes de caractères (string) et les listes chaînées ('a list) vont nous servir d'exemple pour illustrer les différences entre << fonctionnel >> et << impératif >>.

Du côté du fonctionnel

La fonction map (voir page ??) est l'une des plus classiques des langages fonctionnels. Dans un style fonctionnel pur, elle s'écrit : 

# let rec map f l = match l with 
      []   ->  []
   | t::q  ->  (f t) :: (map f q)  ;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>


La liste résultat de l'application de f aux éléments de la liste passée en argument est construite récursivement en spécifiant indépendamment sa tête (f t) et sa queue (map f q). En particulier, le programme ne précise pas lequel des deux sera calculé en premier.

De plus, la représentation physique des listes n'a pas besoin d'être connue du programmeur pour écrire une telle fonction. En particulier, les problèmes d'allocation et de partage des données sont gérés implicitement par le système et non par le programmeur. L'exemple ci-dessous en est une illustration : 

# let exemple = [ "un" ; "deux" ; "trois" ] ;;
val exemple : string list = ["un"; "deux"; "trois"]
# let resultat = map (function x -> x) exemple  ;;
val resultat : string list = ["un"; "deux"; "trois"]


Les listes exemple et resultat contiennent des valeurs égales : 

# exemple = resultat ;;
- : bool = true


Ces deux valeurs ont exactement la même structure bien que leur représentation en mémoire diffère, comme on s'en rend compte en utilisant le test d'égalité physique : 

# exemple == resultat ;;
- : bool = false
# (List.tl exemple) == (List.tl resultat) ;;
- : bool = false


Du côté impératif

Reprenons l'exemple précédent, et modifions une chaîne de la liste resultat. 

# (List.hd resultat).[1] <- 's' ;;
- : unit = ()
# resultat ;;
- : string list = ["us"; "deux"; "trois"]
# exemple ;;
- : string list = ["us"; "deux"; "trois"]
Manifestement, cette opération a modifié la liste exemple. Donc, il est indispensable de connaître la structure physique des deux listes manipulées dès que nous utilisons des traits impératifs.

Voyons maintenant comment l'ordre d'évaluation des arguments d'une fonction peut constituer un piège dans un programme impératif. Nous définissons une structure de liste modifiable avec les fonctions de base de création , rajout et accès : 

# type 'a ilist = { mutable c : 'a list } ;;
type 'a ilist = { mutable c: 'a list }
# let icreate () = { c = [] }
 let iempty l = (l.c = []) 
 let icons x y = y.c <- x::y.c ; y
 let ihd x = List.hd x.c
 let itl x = x.c <- List.tl x.c ; x ;;
val icreate : unit -> 'a ilist = <fun>
val iempty : 'a ilist -> bool = <fun>
val icons : 'a -> 'a ilist -> 'a ilist = <fun>
val ihd : 'a ilist -> 'a = <fun>
val itl : 'a ilist -> 'a ilist = <fun>
# let rec imap f l = 
   if iempty l then icreate()
   else icons (f (ihd l))  (imap f (itl l)) ;;
val imap : ('a -> 'b) -> 'a ilist -> 'b ilist = <fun>


Bien qu'ayant repris l'architecture générale de la fonction map du paragraphe précédent, nous obtenons avec, imap, un résultat sensiblement différent : 

# let exemple = icons "un" (icons "deux" (icons "trois" (icreate()))) ;;
val exemple : string ilist = {c=["un"; "deux"; "trois"]}
# imap (function x -> x) exemple ;;
Uncaught exception: Failure("hd")


Que s'est-il passé ? Simplement, l'évaluation de (itl l) a eu lieu avant celle de (ihd l) de sorte que, à la dernière itération de imap, la liste référencée par l devient la liste vide avant que l'on n'examine sa tête. La liste exemple est désormais définitivement vide bien que nous n'ayons obtenu aucun résultat : 

# exemple ;;
- : string ilist = {c=[]}


Le défaut de la fonction imap provient d'un mélange insuffisamment contrôlé des genres : nous avons laissé au système le choix de l'ordre d'évaluation. Nous pouvons reformuler la fonction imap en explicitant l'ordre d'évaluation à l'aide de la construction syntaxique let .. in .. 

# let rec imap f l = 
   if iempty l then icreate()
   else let h = ihd l  in  icons (f h)  (imap f (itl l)) ;;
val imap : ('a -> 'b) -> 'a ilist -> 'b ilist = <fun>
# let exemple = icons "un" (icons "deux" (icons "trois" (icreate()))) ;;
val exemple : string ilist = {c=["un"; "deux"; "trois"]}
# imap (function x -> x) exemple ;;
- : string ilist = {c=["un"; "deux"; "trois"]}


Cependant, la liste initiale a ici encore été perdue : 

# exemple ;;
- : string ilist = {c=[]}


Une seconde façon de rendre explicite l'ordre d'évaluation est d'utiliser l'opérateur de mise en séquence et une structure de boucle. 

# let imap f l = 
   let l_res = icreate ()  
   in while not (iempty l) do 
        ignore (icons (f (ihd l)) l_res) ;
        ignore (itl l)
      done ;
      { l_res with c = List.rev l_res.c } ;;
val imap : ('a -> 'b) -> 'a ilist -> 'b ilist = <fun>
# let exemple = icons "un" (icons "deux" (icons "trois" (icreate()))) ;;
val exemple : string ilist = {c=["un"; "deux"; "trois"]}
# imap (function x -> x) exemple ;;
- : string ilist = {c=["un"; "deux"; "trois"]}
La présence de ignore illustre bien le fait que ce n'est pas le résultat des fonctions qui nous importe mais leurs effets de bord sur leur argument. Il a de plus été nécessaire de remettre dans le bon ordre (par la fonction List.rev) les éléments du résultat.

Récursif ou itératif

On associe souvent à tort récursif avec fonctionnel et itératif avec impératif. Un programme purement fonctionnel ne pourra pas être itératif car la valeur de la condition d'une boucle ne varie jamais. Par contre un programme impératif peut être récursif : la fonction imap en est un exemple.

L'appel d'une fonction conserve les valeurs de ses arguments le temps de son calcul. Si elle appelle une autre fonction, celle-ci conservera en plus ses propres arguments. Ces valeurs sont conservées dans la pile d'exécution. Au retour de l'appel ces valeurs sont dépilées. Cet espace mémoire étant borné, il est possible d'en atteindre la limite en utilisant une fonction récursive dont la profondeur des appels serait trop importante. Dans ce cas Objective CAML déclenche l'exception Stack_overflow. 

# let rec succ n = if n = 0 then 1 else 1 + succ (n-1) ;;
val succ : int -> int = <fun>
# succ 100000 ;;
Stack overflow during evaluation (looping recursion?).


Dans la version itérative l'occupation de la pile par l'appel de succ_iter ne dépend pas de son argument. 

# let succ_iter n = 
   let i = ref 0 in 
     for j=0 to n do incr i done ;
     !i ;;
val succ_iter : int -> int = <fun>
# succ_iter 100000 ;;
- : int = 100001


La version récursive suivante a a priori la même profondeur d'appels et pourtant réussit à s'exécuter avec le même argument. 

# let succ_rt n = 
   let rec succ_aux n accu = 
     if n = 0 then accu  else succ_aux (n-1) (accu+1) 
   in 
     succ_aux 1 n ;;
val succ_rt : int -> int = <fun>
# succ_rt 100000 ;;
- : int = 100001


Cette fonction a une forme particulière d'appel récursif, dit récursif terminal qui veut que le résultat de l'appel soit le résultat de la fonction sans autre calcul. Il n'est donc pas nécessaire d'avoir conservé les valeurs des arguments de la fonction pendant le calcul de l'appel récursif. Objective CAML quand il sait reconnaître une fonction récursive terminale libère les arguments empilés avant d'effectuer l'appel. Cette optimisation permet d'avoir des fonctions récursives ne faisant pas grossir la pile.

La détection des fonctions récursives terminales existe dans beaucoup de langages, mais elle est indispensable dans un langage fonctionnel où par nature on utilise beaucoup de fonctions récursives terminales.

Précédent Index Suivant