Programmation:OCaml:Fonctionnel:VS:Imperatif
Sommaire
Introduction
Les langages pures (c'est à dire qui ne sortent pas de leur paradigme) ont souvent quelques lacunes qui obligent le programmeur à utiliser des constructions compliquées pour faire des choses par ailleurs très simple. Les langages fonctionnels pures ne sont pas en reste de ce type de détours volontaires. Mais ce n'est pas le cas d'OCaml, au contraire, le langage fournit des constructions de nature impérative (avec effet de bord et tout) afin de répondre à certains besoins.
En pratique, on s'apperçoit que ces constructions restent limitées à l'usage sur des parties très spécifiques: gestion des entrées/sorties, options globales, objets ...
Boucles et absences d'effet de bord
- Pourquoi ne peut-on écrire de boucle sans effet de bord ?
Lorsque l'on rencontre les langages fonctionnels pour la première fois, on est souvent surppris de l'abscence de boucle. Mais pourtant, dans un modèle fonctionnel pure, c'est assez évident.
Prennons par exemple la boucle e type while. Cette boucle teste à chaque passage une condition qui doit être modifier dans le corps de la boucle. Essayons avec un exemple simple en OCaml:
let i = 0 in while i < 10 do let i = i + 1 in print_int i done
Ce programme ne s'arrête pas et affiche une série infinie de 1. Pourquoi ? Et bien tout simplement parce que la constante i tester dans le while n'est pas la même que celle redéfinie par le let dans le corps de la boucle. Pour pouvoir écrire cette boucle, il nous faudrait modifier i, or c'est une constante !
On ne peut donc écrire de boucle sans effet de bord. Bien évidement, il est possible d'exprimer toute forme d'itération à l'aide de fonction récursive et donc de se passer de boucle. Mais il est quand même confortable de pouvoir utiliser des boucles de temps en temps.
On peut faire une exception au problème des boucles en fonctionnel avec la boucle de type for. En effet, dans une boucle for, la modification de la variable de boucle (le compteur) est cachée dans la boucle elle même, il est donc possible d'ajouter une construction de type for à un langage fonctionnel sans pour autant ajouter de valeur modifiable. Les boucles que l'on peut ainsi construire, font partie des itérations bornées: le nombre d'itérations de la boucle ne dépend pas des opérations effectuées dans la boucle (comme le for de Pascal, pas celui du C.) Une autre restriction des boucles for sans effet de bord, est justement l'abscence de résultats de telles boucles, elles ne peuvent donc être utilisées que pour des opérations de type affichage ou entrées/sorties.
Voici un petit exemple de boucle for en OCaml:
for i = 0 to 10 do Printf.printf "%d " i done ;;
Il est donc nécessaire de pouvoir de disposer d'effets de bords si l'on veut utiliser des boucles dans un langage fonctionnel. Ces effets de bords sont nécessaires tant pour pouvoir écrire des boucles while mais également pour que ces boucles soient utiles.
Valeurs modifiables
Le langage OCaml disposent de différentes sortes de valeurs modifiables (mutable values): les références, les champs de records mutables, les tableaux, les propriétés des objets ...
Dans ce cours nous nous intéresserons principalement aux références, aux records et aux tableaux, les objets quant à eux feront le sujet d'un autre cours
Références
Une référence peut être vu comme un sorte de pointeur toujours initialisé. En soit, la référence est une valeur constante comme les autres, mais cette valeur pointe sur une cellule mémoire qui, elle, peut être modifiée. Les références d'OCaml (comme les références des autres langages) sont toujours initialisées: elles pointent sur une cellule qui existe et dont le contenu est initialisé. Les références sont également typée et induisent certaines contraintes sur le mécannisme d'inférence.
Syntaxe, sémantique et typage
On définit une référence à l'aide du mot clef ref et on accède au contenu de la cellule via l'opérateur ! et enfin on utilise l'opérateur :=:
# let r = ref 0 ;; val r : int ref = {contents = 0} # r ;; - : int ref = {contents = 0} # !r ;; - : int = 0 # r := 1 ;; - : unit = () # !r ;; - : int = 1 # r := !r + 1 ;; - : unit = () # !r ;; - : int = 2 # incr ;; - : int ref -> unit = <fun> # incr r;; - : unit = () # !r ;; - : int = 3 # decr;; - : int ref -> unit = <fun> # decr r;; - : unit = () # !r ;; - : int = 2
Pour de nombreuses raisons, les références ajoutent des contraintes sur le polymorphisme et l'inférence de type. En effet, dans l'expression ref a, si a ne peut être une valeur polymorphe (comme une fonction ou la liste vide) car sinon, la référence serait elle même polymorphe ce qui conduirait à des contradiction comme l'exemple suivant:
let r = ref [] in r := [1]; true::!r ;;
Si on autorise r à avoir le type 'a list ref alors, les deux opérations qui suivent sont bien typées et l'expression renvoit une liste contenant en tête un booléen suivi d'un entier. La solution choisit pour résoudre ce problème est une restriction appliquée à la généralisation du let: en effet, dans l'expression let x = a in a' le type de x ne peut être polymorphique que si a est une valeur, or ref a n'est pas une valeur (ref n'est pas un constructeur.)
On peut voir facilement les conséquences de ces restrictions:
# let r = ref (fun x -> x) ;; val r : ('_a -> '_a) ref = {contents = <fun>} # !r 1 ;; - : int = 1 # r ;; - : (int -> int) ref = {contents = <fun>} # let r = ref [] ;; val r : '_a list ref = {contents = []} # true::!r;; - : bool list = [true] # r;; - : bool list ref = {contents = []} # let f = (fun x -> fun y -> x y) (fun x -> x) ;; val f : '_a -> '_a = <fun>
Dans tous ces exemples, on peut voir que le type de la variable définie n'est pas polymorphe: plus exactement, s'il est inconnue, il prend la forme '_a qui une variable de type non généralisée et non encore détermininée. Ces variables de type sont remplacées, dès la première unification. On voit dans le dernier exemple, que cette restriction a égalemenet un impacte sur des définitions légitimes sans références (la fonction f est la fonction identité, elle devrait être polymorphe.)
Boucles while avec références
Les références nous permettent d'écrire notre première boucle:
# let compte n = let i = ref 0 in while !i < n do incr i; Printf.printf "!i: %d\n" !i done;; val compte : int -> unit = <fun> # compte 10;; !i: 1 !i: 2 !i: 3 !i: 4 !i: 5 !i: 6 !i: 7 !i: 8 !i: 9 !i: 10 - : unit = ()
On peut réécrire les fonctions arithmétique classiques:
let somme n = let res = ref 0 and i = ref 0 in while !i <= n do res := !res + !i; incr i done; !res let fibo n = let f1 = ref 1 and f2 = ref 1 and i = ref 1 in while (!i < n) do let f = !f1 + !f2 in f2 := !f1; f1 := f; incr i done; !f1
Définitions et copies
La valeur d'une référence est une adresse et par conséquent il faut faire attention aux manipulations que l'on fait avec. Voyons sur des exemples:
# let r = ref 0 ;; val r : int ref = {contents = 0} # let r1 = r ;; val r1 : int ref = {contents = 0} # !r1;; - : int = 0 # r := 2;; - : unit = () # !r;; - : int = 2 # !r1;; - : int = 2
Dans cette exemple, r1 est crée avec la référence (et donc l'adresse) r. Donc r1 n'est pas une nouvelle référence, elle est donc affectée par les modifications faites sur r (et réciproquement.) Notez par contre le comportement de l'exemple suivant:
# let r = ref 0 ;; val r : int ref = {contents = 0} # let r1 = ref 0 ;; val r1 : int ref = {contents = 0} # r = r1;; - : bool = true # r == r1;; - : bool = false
Dans cet exemple, r et r1 sont des références différentes, pourtant r = r1 renvoie vrai ! Il faut savoir que le test d'égalité d'OCaml est structurelle: les deux référence pointent sur des cellules mémoires contenant la même valeur, elles sont donc structurellement équivalentes. Par contre, l'égalité physique (==) donne le résultat opposé, dans ce cas, OCaml fait une comparaison immédiate entre les deux valeurs et donc compare deux adresses différentes.
Variables statiques
Les valeurs fonctionnelles d'OCaml sont des clotures (closure), elles embarquent les parties nécessaires de l'environnement avec elle. On peut utiliser cette notion avec les références pour créer des variables statiques. Dans les langages impératifs, les variables statiques sont des variables de portée locale à la fonction où elles sont définies mais qui ont la même persistance que les variables globales: leur valeur reste entre chaque appel de la fonction. On peut faire la même chose en OCaml avec des références, voici un exemple de compteur, une fonction renvoyant une nouvelle valeur à chaque appel:
# let next = let cpt = ref (-1) in function () -> incr cpt; !cpt;; val next : unit -> int = <fun> # next () ;; - : int = 0 # next () ;; - : int = 1 # next () ;; - : int = 2 # next () ;; - : int = 3 # next () ;; - : int = 4 # next () ;; - : int = 5 # next () ;; - : int = 6
Enregistrements (records)
Les enregitrements (record) sont des blocs de données hétérogènes nommés: chaque membre du bloc à un nom, on parle de champ. Ce sont des structures très classiques (on les retrouve en Pascal ou dans le langage algo, en C sous le nom de struct.) En OCaml les noms des champs servent à déterminer le type d'un enregitrement et ne peuvent donc apparaître que dans une seule définition (à l'intérieur d'un même module.) Il est nécessaire de définir le type du record avant de pouvoir s'en servir. Voici un exemple:
# type r = { a : int ; b : float ; } ;; type r = { a : int; b : float; } # let r1 = { a = 1 ; b = 1. };; val r1 : r = {a = 1; b = 1.} # r1.a ;; - : int = 1 # r1.b ;; - : float = 1. # let r2 = { r1 with a = 2 } ;; val r2 : r = {a = 2; b = 1.}
Rien de bien surprenant ici, mise à part la syntaxe utilisée pour définir r2: { r1 with a = 2 } copie r1 (il s'agit vraiment d'une nouvelle valeur) mais remplace le contenu du champ a.
On peut construire des filtres sur les champs des records:
# let f = function {a = x; b = y} -> y +. float_of_int x;; val f : r -> float = <fun> # f r1 ;; - : float = 3.
On notera qu'il n'est pas obligatoire de mettre tous les champs dans les filtres.
Les records sont des regroupement de cellules mémoires indexées par le nom de leur champ, mais par défaut, ces cellules ne sont pas modifiables, il faut indiquer explicitement pour chaque champ que celui-ci est modifiable avec le mot clef mutable:
# type r = { mutable a : int ; b : float ; } ;; type r = { mutable a : int; b : float; } # let r1 = { a = 1; b = 1. };; val r1 : r = {a = 1; b = 1.} # r1.a <- 2;; - : unit = () # r1 ;; - : r = {a = 2; b = 1.} # r1.b <- 2. ;; Characters 0-10: r1.b <- 2. ;; ^^^^^^^^^^ The record field label b is not mutable
Vous aurez remarqué que les valeurs affichées pour les références avaient la forme { content = 0 }, c'est parce qu'en réalité le type des références est défini comme suit:
type 'a ref = { mutable content : 'a }
Par conséquent, on retrouve les mêmes comportements en ce qui concerne la copie de record:
# type r = { mutable a : int } ;; type r = { mutable a : int; } # let a = { a = 1 } ;; val a : r = {a = 1} # let b = a ;; val b : r = {a = 1} # b == a ;; - : bool = true # a.a <- 2 ;; - : unit = () # b;; - : r = {a = 2}
Tableaux
Enfin les tableaux sont également un construction très classique. Ceux d'OCaml sont directement modifiable (contrairement au champs des records) par contre leur syntaxe est parfois déroutante. Voici quelques exemples:
# let t = [| 1; 2; 3; 4 |];; val t : int array = [|1; 2; 3; 4|] # t.(1) ;; - : int = 2 # t.(0) <- -1 ;; - : unit = () # t.(0) ;; - : int = -1 # Array.length t ;; - : int = 4 # let t2 = Array.make 10 0 ;; val t2 : int array = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]
Il faut faire attention lorsque l'on initialise un tableau avec des valeurs modifiables:
# let t = Array.make 10 (ref 0);; val t : int ref array = [|{contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}|] # t.(0) := 1;; - : unit = () # t ;; - : int ref array = [|{contents = 1}; {contents = 1}; {contents = 1}; {contents = 1}; {contents = 1}; {contents = 1}; {contents = 1}; {contents = 1}; {contents = 1}; {contents = 1}|]
Dans l'expression Array.make 10 (ref 0), la sous-expression ref 0 n'est évaluée qu'une fois au moment de l'appel et par conséquent il n'y a qu'une seule cellule mémoire de créer et chaque case du tableau contient son adresse. Pour créer un tableau avec une référence différente dans chaque tableau, il faut utiliser Array.init qui prend une fonction en paramètre à la place de la valeur passée à Array.make:
# let t2 = Array.init 10 (fun _ -> ref 0) ;; val t2 : int ref array = [|{contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}|] # t2.(0) := 1 ;; - : unit = () # t2;; - : int ref array = [|{contents = 1}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}; {contents = 0}|]
Exceptions
Le mécannisme d'exception d'OCaml permet de gérer les erreurs de manière transversale. Lorsqu'une exception est levée, elle traverse l'ensemble des la pile d'appels et si elle n'est pas rattrapée, elle interromp le programme (et provoque une erreur.) Ce qui est intéressant, c'est que l'on peut rattraper une exception n'importe où dans la chaîne d'appels. On peut également définir des exceptions.
Définir une exception
Pour définir une exception, il suffit de déclarer (à top-level comme un définition globale) son nom avec le mot clef exception:
# exception Mon_exception ;; exception Mon_exception # Mon_exception ;; - : exn = Mon_exception
On peut également ajouter des paramètres à une exception (comme pour les types sommes) :
# exception Mon_exception of int * string * bool;; exception Mon_exception of int * string * bool
Les noms d'exception commence avec une majuscule et leurs paramètre ne peuvent être polymorphes.
Lever une exception
Pour lever une exception, vous devrez utilisr l'opération raise:
# exception Val_negative;; exception Val_negative # let rec fact = function 0|1 -> 1 | n when n>0 -> n * fact (n-1) | _ -> raise Val_negative;; val fact : int -> int = <fun> # fact 5;; - : int = 120 # fact (-5) ;; Exception: Val_negative.
L'opération raise prend en paramètre une exception, avec tous ces arguments (attention au parenthèsage.) Si on regarde son type avec l'interpréteur on obtient:
# raise ;; - : exn -> 'a = <fun>
On observe que le type renvoyer est polymorphe, ce qui est logique, la fonction ne revenant jamais, on peut considérer qu'elle renvoit une valeur de n'importe quel type. Par conséquent, elle peut être utilisé dans n'importe quel contexte, son utilisation sera toujours bien typée.
La levée d'exception est une action transversale, l'exception traverse l'ensemble des appels jusqu'à ce qu'elle soit rattrapée ou jusqu'à interrompre le programme si aucun code ne la rattrape. Prenons en exemple le programme suivant:
exception Mon_exception let _ = raise Mon_exception
Si on le compile (sous le nom always_fail.ml par exemple) et on l'exécute, on obtient le résultat suivant:
> ocamlopt -o always_fail always_fail.ml > ./always_fail Fatal error: exception Always_fail.Mon_exception > echo $status 2
L'exécution du programme est interrompu par l'exception et comme rien ne la rattrape, le programme termine avec un message d'erreur. On notera que dans ce cas là le code de retour du programme est 2 (et non pas 0 qui indique un succès en shell.)
Si l'exception a des arguments (et que ceux-ci sont affichables), le message les présentera également:
exception Mon_exception of int let _ = raise (Mon_exception 42)
> ocamlopt -o always_fail always_fail.ml > ./always_fail Fatal error: exception Always_fail.Mon_exception(42)
Rattraper une exception
L'intéret des exceptions est bien évidement de pouvoir être attrapées. Mais plus important, elles peuvent être attrapées presque n'importe où. En effet, comme elle traverse l'ensemble des appels de fonction du programme, un filtre peut les intercepter à n'importe quel point entre leur émission (là où se trouve le raise) et le corps principal du programme. Mais voyons tout d'abord la syntaxe:
try (* expression *) with Exception -> (* expression *) | Exception -> (* expression *) (* ... *) | Exception -> (* expression *)
L'expression entre try et with correspond au code pouvant lever une exception et chaque ligne après le with est un filtre sur les exceptions du même genre que le pattern matching sur les types sommes: un motif capturant le nom de l'exception (avec ses éventuels arguments) suivit d'une expression correspondant au code à exécuter si l'exception correspondante est capturée.
La sémantique et le typage sont relativement simple: si tout va bien (pas d'exception) le résultat de l'expression dans le try est renvoyé, sinon si l'exception correspond à l'une des branches du filtrage, c'est le résultat de l'expression correspondante qui est renvoyé. Par conséquent, toutes les expressions du filtrage doivent avoir le même type:
# try 42 with Invalid_argument _ -> 0 ;; - : int = 42 # try 42 with Invalid_argument _ -> 0. ;; ^^ Error: This expression has type float but an expression was expected of type int # try 42 with Invalid_argument -> 0. ;; ^^^^^^^^^^^^^^^^ Error: The constructor Invalid_argument expects 1 argument(s), but is applied here to 0 argument(s) # try raise (Not_found); 42. with Not_found -> 42;; ^^ Error: This expression has type int but an expression was expected of type float # try raise (Not_found) with Not_found -> 42;; - : int = 42
On voit ici les différentes erreurs de typage classiques.
Maintenant, observons la traversée des appels de fonctions dans le code suivant (fact.ml):
exception Neg_number of int let rec f = function 0 -> 1 | n when n>0 -> n * f (n-1) | n -> raise (Neg_number n) let g x = Printf.printf "%d! = %d\n" x (f x) let main () = begin Random.self_init (); Printf.printf "On lance le calcule de factorielle.\n"; (* 0 <= Random.int n < n *) g (Random.int 12); g (- Random.int 12); exit 0; end let _ = try main () with Neg_number x -> begin Printf.eprintf "factorielle du nombre négatif %d.\n" x; exit 3; end
> ocamlopt -o fact fact.ml > ./fact On lance le calcule de factorielle. 0! = 1 factorielle du nombre négatif -6. > ./fact On lance le calcule de factorielle. 11! = 39916800 0! = 1
Récursion et exceptions
Comme on l'a vu, la levée d'une exception interromp le flot d'exécution du programme. Notamment, lorsqu'une fonction récursive est interrompue par une levée d'exception, on peut rattrapper celle-ci dans l'appellant extérieur, ou bien dans la fonction elle même (à l'étape précante de récursion.) Les exceptions peuvent donc être utilisée dans certains cas comme cas d'arrêt un peu particulier, notamment dans les récursions sur des flux ou des opérations d'entrées/sorties.
Voici un exemple d'itérateur sur flux (ici on construit un pseudo flux, mais celui-ci pourrait utiliser les streams d'OCaml.) Le flux se présente comme une fonction qui renvoit le prochaine élément à chaque appel et lève une exception lorsqu'il n'y a plus d'élément. L'itérateur va se contenter d'afficher l'ensemble des éléments du flux jusqu'à sa fin.
(* flux.ml : itérateur sur pseudo flux *) (* Construction du flux *) exception Flux_vide (* cons_flux: string -> unit -> char *) (* cons_flux s construit un flux de caractère à partir de s *) let cons_flux s = let pos = ref (-1) in let len = String.length s in function () -> incr pos; if !pos < len then s.[!pos] else raise Flux_vide (* Iterateur *) let rec print_flux f = try Printf.printf "%c" (f ()) ; print_flux f with Flux_vide -> Printf.printf "\n" (* Fonction principale *) let main () = begin let next = cons_flux "Une chaine d'exemple pour le flux ..." in print_flux next; exit 0 end let _ = main ()
> ocamlopt -o flux flux.ml > ./flux Une chaine d'exemple pour le flux ...
La fonction print_flux récupère le prochain caractère du flux (à partir de la fonciton qui lui est passée en argument), l'affiche et se rappelle. Si la fonction passée en argument lève l'exception Flux_vide, la récursion se termine par l'affichage d'un saut de ligne.
Pour la construction du flux (cons_flux) on aurait pu (au lieu de comparer la position courrante avec la longueur de la chaîne) rattraper l'exception levée lorsque l'on dépasse les bornes d'une chaîne (Invalid_argument "index out of bounds") et lever là notre exception.
On notera dans cet exemple l'usage de variables statiques, d'exceptions et de fonctions de première classe.
Conclusion
L'ensemble de ce cours vous a présenté les différentes constructions impératives fournit par OCaml. Ces constructions ne sont pas nécessaires en théorie, pour l'écriture de programmes complets elles nous permettent de prendre des raccourcis moins fonctionnels.
Dans la pratique, les boucles sont peu utilisées dans la programmation en OCaml, on leur préfère des constructions récursives intelligentes. Par contre, les valeurs modifiables et les exceptions sont quasiment indispensables dans un gros programme.
Ils nous restent maintenant à voir une différence plus abstraite entre fonctionnel et impératif: les structures de données. Ce thème fait l'objet d'un autre cours qui traite de l'équilibre à trouver entre des structures modifiables en place et les structures dites fonctionnelles qui nécessitent la construction d'une nouvelle valeur à chaque modification. Nous verrons notamment que les secondes ne sont pas forcément moins performante que les premières.
| Cours | Partie |
|---|---|
| Cours de Programmation EPITA/spé | Programmation:OCaml |
