Mélange des styles

Mélange des styles

Comme nous l'avons déjà mentionné, un langage offrant à la fois des traits fonctionnels et impératifs permet de pouvoir choisir le style le plus approprié pour chaque partie de l'implantation d'un algorithme. On peut tout aussi bien utiliser conjointement les deux aspects du langage dans une même fonction. C'est ce que nous illustrons dans ce paragraphe.

Fermetures et effets de bord

Il est d'usage, quand une fonction effectue un effet de bord, de la traiter comme une procédure et de retourner la valeur (), de type unit. Néanmoins, dans certains cas, il peut être utile d'effectuer l'effet de bord à l'intérieur d'une telle fonction et de retourner une valeur pertinente. Nous avons déjà utilisé ce mélange des styles dans la fonction permute_pivot du tri rapide.

L'exemple suivant est un générateur de symboles qui permet d'engendrer un nouveau symbole à chaque appel de la fonction. On utilise simplement un compteur qui est incrémenté à chaque appel.


# let c = ref 0;;
val c : int ref = {contents=0}
# let reset_symb = function () -> c:=0 ;;
val reset_symb : unit -> unit = <fun>
# let new_symb = function s ->  c:=!c+1 ; s^(string_of_int !c) ;;
val new_symb : string -> string = <fun>
# new_symb "VAR" ;;
- : string = "VAR1"
# new_symb "VAR" ;;
- : string = "VAR2"
# reset_symb () ;;
- : unit = ()
# new_symb "WAR" ;;
- : string = "WAR1"
# new_symb "WAR" ;;
- : string = "WAR2"

On peut cacher au reste du programme la référence c en écrivant :


# let (reset_s , new_s) = 
   let c = ref 0 
   in let f1 () = c := 0  
      and f2 s  = c := !c+1 ; s^(string_of_int !c) 
   in (f1,f2) ;;
val reset_s : unit -> unit = <fun>
val new_s : string -> string = <fun>

Cette déclaration crée un couple de fonctions qui partagent toutes deux la variable locale (à la déclaration) c. L'utilisation de ces deux fonctions produit la même exécution que les définitions précédentes.


# new_s "VAR";;
- : string = "VAR1"
# new_s "VAR";;
- : string = "VAR2"
# reset_s();;
- : unit = ()
# new_s "WAR";;
- : string = "WAR1"
# new_s "WAR";;
- : string = "WAR2"

Cet exemple permet d'illustrer la représentation des fermetures. Une fermeture peut être considérée comme un couple contenant d'une part le code (c'est à dire la partie function) et d'autre part un environnement local, contenant les valeurs des variables libres de la fermeture. La figure 4.1 montre la représentation mémoire des fermetures reset_s et new_s.

Figure 4.1 : Représentation mémoire de fermetures

Ces deux fermetures partagent le même environnement (la valeur de c). Quand l'une modifie la référence c, elle modifie le contenu d'une zone mémoire partagée par l'autre fermeture.

Modifications physiques et exceptions

Les exceptions permettent de récupérer des situations où le calcul ne peut pas se poursuivre. Dans ces cas, un récupérateur d'exceptions permet de continuer le calcul sachant qu'une des branches a échoué. Le problème avec les effets de bord provient alors de l'état des données modifiables quand l'exception se déclenche. On ne peut pas garantir cet état s'il y a eu des modifications physiques dans la branche de calcul qui échoue.

Définissons la fonction d'incrément (++) fonctionnant à l'instar de l'opérateur C :


# let (++) x = x:=!x+1; x;;
val ++ : int ref -> int ref = <fun>

L'exemple suivant montre un petit calcul où une division par zéro intervient en concomitance avec un effet de bord :


# let x = ref 2;;
val x : int ref = {contents=2}
(* 1 *)
# !((++) x) * (1/0) ;;
Uncaught exception: Division_by_zero
# x;;
- : int ref = {contents=2}
(* 2 *)
# (1/0) * !((++) x) ;;
Uncaught exception: Division_by_zero
# x;;
- : int ref = {contents=3}

La variable x n'est pas modifiée lors du calcul de l'expression en (*1*), par contre elle l'est pour l'expression en (*2*). Sauf à savoir sauver les valeurs initiales, les constructions try .. with .. ne doivent pas (dans la partie with ..) tenir compte des variables modifiables impliquées dans l'expression ayant déclenché une exception.

Structures de données fonctionnelles modifiables

Une manière de voir qu'en programmation fonctionnelle un programme, au sens d'une expression fonctionnelle, est aussi une donnée manipulable, est d'écrire les listes d'association sous forme d'expressions fonctionnelles. On peut en effet voir, et implanter, une liste d'association ('a * 'b) list comme une fonction partielle de 'a (l'ensemble des clés) dans 'b (l'ensemble des valeurs associées). Autrement dit, une fonction de type 'a -> 'b.

La liste vide est la fonction non définie que l'on simule par le déclenchement d'une exception :


# let nil_assoc = function x -> raise Not_found ;;
val nil_assoc : 'a -> 'b = <fun>

On peut alors écrire la fonction add_assoc qui ajoute un élément à une liste, c'est-à-dire qui étend la fonction pour une nouvelle entrée :


# let add_assoc (k,v) l = function x -> if x = k then v else l x ;;
val add_assoc : 'a * 'b -> ('a -> 'b) -> 'a -> 'b = <fun>
# let l = add_assoc ('1', 1) (add_assoc ('2', 2) nil_assoc) ;;
val l : char -> int = <fun>
# l '2' ;;
- : int = 2
# l 'x' ;;
Uncaught exception: Not_found

On peut réécrire la fonction mem_assoc :


# let mem_assoc k l = try  (l k) ; true  with  Not_found -> false ;;
val mem_assoc : 'a -> ('a -> 'b) -> bool = <fun>
# mem_assoc '2' l ;;
- : bool = true
# mem_assoc 'x' l ;;
- : bool = false

En revanche, il n'est pas immédiat d'écrire une fonction retirant un élément de la liste car on n'a plus accès aux valeurs capturées par les fermetures. Pour cela on masquera l'ancienne valeur par le déclenchement de l'exception Not_found.


# let rem_assoc k l = function x -> if x=k then raise Not_found else l x ;;
val rem_assoc : 'a -> ('a -> 'b) -> 'a -> 'b = <fun>
# let l = rem_assoc '2' l ;;
val l : char -> int = <fun>
# l '2' ;;
Uncaught exception: Not_found

On peut, bien évidement, créer des références et travailler par effet de bord sur de telles valeurs. Il faut cependant prendre quelques précautions.


# let add_assoc_bis (k,v) l =  l := (function x -> if x=k then v else !l x) ;;
val add_assoc_bis : 'a * 'b -> ('a -> 'b) ref -> unit = <fun>

On obtient pour l une fonction qui pointera sur elle-même et donc bouclera. Ce fâcheux effet de bord est dû au fait que le déréférencement !l est dans la portée de la fermeture function x ->. La valeur de !l n'est pas évaluée à la compilation, mais à l'exécution. À ce moment là, l pointe sur la valeur modifiée par add_assoc. Il faut donc amender notre définition en utilisant la fermeture créée par notre définition primitive de add_assoc :


# let add_assoc_bis (k, v) l =  l := add_assoc (k, v) !l ;;
val add_assoc_bis : 'a * 'b -> ('a -> 'b) ref -> unit = <fun>
# let l = ref nil_assoc ;;
val l : ('_a -> '_b) ref = {contents=<fun>}
# add_assoc_bis ('1',1) l ;;
- : unit = ()
# add_assoc_bis ('2',2) l ;;
- : unit = ()
# !l '1' ;;
- : int = 1
# !l 'x' ;;
Uncaught exception: Not_found

Structures paresseuses modifiables

L'utilisation de traits impératifs combinés avec un langage fonctionnel procure de bons outils d'implantation de langages informatiques. Nous proposons dans ce paragraphe d'illustrer ce trait par l'implantation de structures de données à évaluation retardée. Une telle structure de données n'est pas complètement évaluée. Son évaluation avance selon l'usage qui en est fait.

Pour simuler l'évaluation retardée, souvent utilisée dans les langages fonctionnels purs, on utilise des valeurs fonctionnelles, possiblement modifiables. L'intérêt de manipuler des données non complètement évaluées est au moins double : premièrement, ne calculer que ce qui est effectivement utile au calcul ; deuxièmement, travailler sur des données potentiellement infinies.

On définit le type vm qui permet d'obtenir soit une valeur déjà calculée (constructeur Imm), soit une valeur à calculer (constructeur Ret) :


# type 'a v = 
     Imm of 'a
   | Ret of (unit -> 'a);;
# type 'a vm = {mutable c : 'a v };;

Le retardement du calcul est obtenu par encapsulation dans une fermeture. La fonction d'évaluation d'une telle valeur doit soit retourner une valeur déjà calculée, soit évaluer puis stocker une valeur non encore calculée.


# let eval e = match e.c with 
   Imm a -> a
 | Ret f -> let u = f () in e.c <- Imm u ; u ;;
val eval : 'a vm -> 'a = <fun>

Les opérations de retardement de l'évaluation et d'activation de cette évaluation s'appellent aussi geler et dégeler une valeur.

On peut ainsi écrire la structure conditionnelle sous forme de fonction :


# let si_ret c e1 e2 = 
   if eval c then eval e1 else eval e2;;
val si_ret : bool vm -> 'a vm -> 'a vm -> 'a = <fun>

Voici comment on l'utilise pour une fonction récursive comme la factorielle :


# let rec facr n = 
   si_ret {c=Ret(fun () -> n = 0)} 
          {c=Ret(fun () ->  1)} 
          {c=Ret(fun () -> n*(facr(n-1)))};;
val facr : int -> int = <fun>
# facr 5;;
- : int = 120

Notons que la forme classique du if ne peut pas être écrite sous forme de fonction. En effet si l'on définit une fonction si de la manière suivante :


# let si c e1 e2 = if c then e1 else e2;;
val si : bool -> 'a -> 'a -> 'a = <fun>

Alors les trois arguments de si sont évalués lors de leur passage. Ce qui a pour conséquence que la fonction fact boucle car l'appel récursif fact(n-1) est évalué dans tous les cas, y compris dans le cas où n vaut 0.


# let rec fact n = si (n=0) 1 (n*fact(n-1)) ;;
val fact : int -> int = <fun>
# fact 5 ;;
Stack overflow during evaluation (looping recursion?).

Module `Lazy`

La difficulté d'implantation des valeurs gelées provient de la construction d'expressions non évaluées dans le contexte de l'évaluation immédiate d'Objective CAML. Notre tentative de redéfinir la conditionnelle l'a montré. Plus généralement, il n'est pas possible d'écrire une fonction qui gèle une valeur en construisant un objet de type vm :


# let gele e = { c = Ret (fun () -> e) };;
val gele : 'a -> 'a vm = <fun>

Cette fonction suit la stratégie d'évaluation d'Objective CAML et donc évalue l'expression e passée en argument avant de construire la fermeture fun () -> e. On le voit sur l'exemple suivant :


# gele (print_string "trace"; print_newline(); 4*5);;
trace
- : int vm = {c=Ret <fun>}

Pour cette raison, la forme syntaxique suivante a été introduite.

Syntaxe

lazy expr

Warning

Ce trait fait partie des extensions du langage et pourra évoluer dans les prochaines versions.

Le mot clé lazy appliqué à une expression construit une valeur d'un type particulier déclaré dans le module Lazy :


# let x = lazy (print_string "Hello"; 3*4) ;;
val x : int Lazy.status ref = {contents=Lazy.Delayed <fun>}

L'expression (print_string "Hello") n'a pas été évaluée puisqu'aucun affichage n'a eu lieu. On peut forcer cette évaluation par appel à la fonction force du module Lazy :


# Lazy.force x ;;
Hello- : int = 12

On remarque qu'alors la valeur de x a changé :


# x ;;
- : int Lazy.t = {contents=Lazy.Value 12}

C'est devenu la valeur de l'expression gelée, ici : 12.

Un nouvel appel à la fonction force se contente alors de retourner la valeur calculée :


# Lazy.force x ;;
- : int = 12

La chaîne "Hello" n'est plus affichée.

Structures de données << infinies >>

Le deuxième intérêt de l'évaluation retardée est de construire des structures de données potentiellement infinies tel l'ensemble des entiers naturels. Comme il risquerait d'être long de tous les calculer, l'idée ici est de ne calculer qu'une tête et de savoir passer à l'élément suivant.

On définit une structure générique 'a enum qui permettra d'énumérer les éléments d'un ensemble.


# type 'a enum = { mutable i : 'a; f :'a -> 'a } ;;
type 'a enum = { mutable i: 'a; f: 'a -> 'a }
# let next e = let x = e.i in e.i <- (e.f e.i) ; x ;;
val next : 'a enum -> 'a = <fun>

On peut ainsi obtenir l'ensemble des entiers naturels par instanciation des champs de cette structure :


# let nat = { i=0; f=fun x -> x + 1 };;
val nat : int enum = {i=0; f=<fun>}
# next nat;;
- : int = 0
# next nat;;
- : int = 1
# next nat;;
- : int = 2

Un autre exemple est l'ensemble des éléments de la suite de Fibonnacci dont la définition est :

ì
í
î

u₀ = 1

u₁ = 1

u_n+2 = u_n + u_n+1

La fonction de calcul du successeur doit tenir compte de la valeur courante (u_n-1), mais aussi de la précédente (u_n-2). C'est à cela que sert l'état c de la fermeture.


# let fib = let fx = let c = ref 0 in fun v -> let r = !c + v in c:=v ; r
           in { i=1 ; f=fx } ;;
val fib : int enum = {i=1; f=<fun>}
# for i=0 to 10 do  print_int (next fib); print_string "  " done ;;
1  1  2  3  5  8  13  21  34  55  89  - : unit = ()