Mutation et état¶
Pour le moment, les variables et les structures de données que nous avons rencontrées sont non mutables (listes, chaînes de caractères, arbres, etc): une fois qu'une variable est définie, on ne peut pas changer sa valeur - au mieux on peut la masquer par une nouvelle définition de variable portant le même nom.
Dans les langages impératifs, en revanche, la valeur d'une variable change en permanence, de même que le contenu des structures de données en mémoire, les informations systèmes (fichiers ouverts, communications établies, etc).
D'une manière générale, un programme impératif modifie l'état dans lequel le programme se trouve à chaque instruction qu'il exécute.
Certains langages fonctionnels, notamment Haskell, sont farouchement déclaratifs: rien de ce qui a été défini ne peut être modifié, l'état n'existe pas. C'est un peu extrémiste, mais cela permet de faire en permanence de l'évaluation paresseuse, une idée très intéressante dont on aura l'occasion de reparler...
OCaml est un langage un peu plus consensuel. Il nous pousse certes à programmer sans modifier l'état, mais il nous laisse aussi la possibilité de programmer de façon impérative, d'une façon très similaire à ce qu'on ferait en Python, C, Java, etc.
Les tableaux¶
Les tableaux (arrays en anglais) sont une structure de données mutable fréquemment utilisée en OCaml.
Pour créer un tableau, on peut lister les valeurs qu'il contient. La syntaxe est presque la même que pour les listes, sauf qu'on écrit [|...|] au lieu de [...].
let tab = [|1;2;3|] (* <==> tab = [1,2,3] en Python *)
Array.make n v renvoie un nouveau tableau de n cases contenant toutes la valeur v.
let tab2 = Array.make 50 '#' (* un tableau de 50 caractères '#'*)
Array.init n f renvoie le tableau [|f(0); f(1);...;f(n-1)|].
On utilise souvent Array.init avec une fonction anonyme de la forme fun x -> ...
Array.init 10 (fun i -> i * i) (* <=> [i*i for i in range(10)] en Python *)
Contrairement aux listes, l'accès au $i$ème élément d'un tableau se fait en temps constant.
tab.(1) (* <==> tab[1] en Python *)
tab.(-1)
Attention, on n'est pas en Python, les seuls indices valables sont ceux compris entre 0 et (Array.length tab) - 1 !
Voyons donc maintenant comment faire muter un tableau.
tab.(0) <- 0 (* mutation! *)
tab (* le contenu de tab a changé de manière irréversible. *)
Notez le type unit de l'expression tab.(0) <- 0: il s'agit d'une instruction, elle n'a pas de valeur (ou plutôt, elle a la valeur ()), mais elle fait un effet de bord.
Les enregistrements mutables¶
Par défaut, les champs des enregistrements ne sont pas mutables. On peut cependant rendre mutable un champs avec le mot-clé mutable.
type etat_civil = {
date_naissance: int; (* champs non mutable *)
mutable date_deces: int option (* champs mutable *)
}
let christ = {date_naissance= -33; date_deces = Some(0)}
christ.date_deces <- None
christ
Si le champs n'a pas été déclaré mutable, pas le droit d'y toucher
christ.date_naissance <- -34
Les références¶
Une référence est une case mémoire qui contient une valeur, autrement dit c'est une sorte de tableau de dimension 1.
Pour OCaml, c'est simplement un enregistrement à un seul champs nommé contents qui est mutable. La librairie standard définit
le type 'a ref ainsi
type 'a ref = {mutable contents: 'a}
Pour créer une nouvelle référence, on utilise la fonction ref
let r = ref 42 (* création d'une nouvelle référence qui contient 42 *)
(* <=> let r = Array.make 1 42 *)
(* <=> let r = {content=42} *)
La valeur de r n'est pas 42. La valeur de r est "une certaine adresse mémoire". Cela n'a même pas de sens de comparer l'entier 42 à la référence r.
if r = 42 then print_string "r = 42" else print_string "r <> 42"
À chaque appel à ref, une nouvelle référence est créée, différente des précédentes. On parle d'allocation mémoire (malloc en C, new en Java, souvent implicite en Python)
let r2 = ref 42
r == r2 (* r et r2 sont deux "boites" différentes *)
L'égalité physique == est la même que celle de C ou Java, où elle s'écrit d'ailleurs de la même façon.
Attendons un peu pour comparer des références avec l'égalité "profonde" notée = en OCaml...
Pour lire la valeur contenue dans la case mémoire, on utilise l'opérateur ! (prononcez "bang")
!r (* <=> r.(0) <=> r.content *)
!r = !r2
Pour modifier la valeur contenue dans une référence, on utilise l'opérateur infixe (:=).
r := 43
r
Notez que l'affectation r:=e est une instruction (une expression de type unit). L'affectation modifie l'état, mais "ne renvoie rien".
Sans surprise, on ne modifie que la valeur contenue à l'"adresse" r, mais pas aux autres adresses.
r2
!r = !r2
L'aliasing¶
Deux variables peuvent désigner une même référence.
let r' = r (* r et r' sont deux alias pour une même référence *)
r == r' (* les variables r et r' désignent la même adresse mémoire *)
r := 44 (* modifie la valeur à l'adresse égale à la valeur de r ... *)
!r' (* ... qui était aussi l'adresse égale à la valeur de r' *)
La gestion mémoire: soulevons (à peine) le capot...¶
Si on veut se représenter la situation par un dessin avec des boites, il faut comprendre qu'il y a deux niveaux de boites:
- les boites des variables, qui contiennent la valeur des variables. La valeur d'une variable de type
'a refest une adresse - les boites à des adresses quelconques, qui contiennent la valeur désignée par la référence
Une valeur de la forme ref 48 est donc une adresse mémoire d'une boite qui contient 48. OCaml ne permet pas d'afficher ou d'avoir une quelconque information sur cette adresse.
En fait rien ne dit même que cette adresse ne sera pas changée par OCaml en cours de programme!
Pourquoi OCaml changerait-il l'adresse d'une référence en mémoire?
C'est le gestionnaire mémoire d'OCaml (le garbage collector, GC) qui peut déplacer des références pendant l'exécution du programme, de manière transparente pour le programme.
Déplacer des références est utile pour lutter contre la fragmentation. Le chapitre 9 du livre Developing applications with Objective Caml est consacré au GC d'OCaml, n'hésitez pas à le lire pour approfondir le sujet...
Les séquences d'instructions¶
L'opérateur ; permet de composer une instruction avec une seconde expression. C'est cette seconde expression qui donne la valeur de l'expression globale
let x = print_string "hello"; print_newline() ; 3
La valeur de x est 3, mais pendant son calcul, OCaml a affiché hello.
let compteur = ref 0
let suivant () = compteur := !compteur + 1 ; !compteur
let x1 = suivant () in let x2 = suivant () in let x3 = suivant () in
(x1, x2, x3)
A chaque appel, suivant incrémente compteur par effet de bord.
La fonction suivant renvoie !compteur, qui est différent à chaque fois.
Pour faire la même chose en Python, on aurait utilisé une variable globale, et surtout on aurait eu besoin du mot-clé return.
compteur = 0
def suivant () :
global compteur
compteur += 1
return compteur
La vie sans return¶
Le mot-clé
returnn'existe pas en OCaml, simplement la valeur "renvoyée" par une suite d'expressions est la valeur de la dernière expression.
En fait, e1; e2 est presque équivalent à let () = e1 in e2. Il y a une petite nuance toutefois...
2 + 1 ; 3 + 2
(* évalue 2+1, jette le résultat, puis évalue 3+2 et "renvoie" le résultat *)
let () = 2+1 in 3+2
Conclusion:
- dans
let () = e1 in e2,e1doit être de typeunit - dans
e1; e2, sie1n'est pas de typeunit, ça passe, mais on a droit à un avertissement.
Petit conseil, si OCaml vous affiche un warning à propos de ;, c'est sûrement que votre programme a un petit soucis. Voici une erreur ultra classique.
let x = print_string "hello"; print_newline; 3
Voyez-vous pourquoi il y a un warning, et pourquoi hello ne s'est pas affiché?
Les blocs d'instructions¶
Le plus souvent il n'y a pas d'ambiguïté sur le début et la fin d'un bloc d'instructions. Cependant il est courant de marquer un bloc avec des parenthèses ou des begin/end pour plus de lisibilité.
Et dans certaines situations, marquer le bloc est vraiment nécessaire.
let () = if 0=1 then print_string "hello "; print_string "world"; print_newline()
(* affiche world *)
let () =
if 1=1 then begin
print_string "hello ";
print_string "world";
print_newline() (* <- le dernier ; est autorisé mais il n'est pas nécessaire *)
end
(* affiche hello world *)
let () = if 0=1 then (
print_string "hello";
print_string "world";
print_newline(); (* <- le dernier ; est autorisé mais il n'est pas nécessaire *)
)
(* affiche hello world*)
Les boucles¶
Oui! Les boucles existent bien en OCaml. Elles ont une syntaxe légèrement inhabituelle... mais on s'y habitue!
let tab5 = [|0;0;0;0;0|] (* un tableau de 5 entiers *)
for i=0 to 4 do (* <- 4 inclus *)
tab5.(i) <- i;
print_int i; (* <- le dernier ; est autorisé mais il n'est pas nécessaire *)
done;
print_newline()
for i=4 downto 0 do begin
print_int i
end done;
print_newline()
let i = ref 0
while !i < 5 do print_int !i; i := !i + 1 done;
print_newline()
Style impératif et style récursif¶
Quand on doit écrire une fonction qui s'écrit naturellement avec une boucle dans un langage non fonctionnel, on peut l'écrire avec une boucle for ou while en OCaml.
Mais, comme on l'a déjà vu, on peut aussi l'écrire en utilisant une fonction récursive.
Comparons les deux styles sur un exemple: le calcul de la somme $f(0) + f(1) + \cdots + f(n-1)$ pour une fonction $f$ donnée.
En style impératif, cela donne
let somme f n =
let res = ref 0 in
for i=0 to n-1 do
res := !res + f i
done;
!res (* return implicite, c'est la dernière valeur d'une séquence de ; *)
En style récursif, on utilise une fonction récursive auxiliaire pour imiter la boucle for
let somme f n =
let rec somme_depuis i = (* f(i) + f(i+1) + ... + f(n-1) *)
if i = n
then 0
else f i + somme_depuis (i+1)
in somme_depuis 0
La pile d'appel¶
Déroulons le calcul de somme id 3, où id = fun x -> x
L'appel récursif étant enveloppé, il faut mémoriser des calculs en attente. Ici, je mets en attente l'addition $i +\cdots$ à l'étape $i$.
Ces calculs en attente sont mémorisés dans la pile d'appel, dont nous avions déjà parlé en Python. Cette pile d'appel peut consommer rapidement beaucoup de mémoire, c'est pourquoi Python ne favorise pas la programmation par récurrence.
Et c'est aussi pour cela que, si l'on devait choisir entre la version impérative et la version récursive précédentes, il faudrait privilégier la version impérative.
Mais alors, les programmeurs Haskell et les puristes du style fonctionnel ont-ils tort de ne jamais programmer avec de boucles for et while?
Récursivité terminale (aka itération)¶
Il y a une autre façon d'écrire la fonction récursive somme_depuis utilisée pour calculer la fonction somme: on peut ajouter un accumulateur en paramètre.
let somme f n =
let rec somme_depuis i acc =
if i = n
then acc
else somme_depuis (i+1) (acc + f i)
in somme_depuis 0 0
L'intérêt de cette définition est que la récurrence n'est plus enveloppée, on n'a plus besoin de mettre des calculs en attente.
On parle de récursivité terminale.
Observons la différence quand on développe le calcul de somme id 3
Les compilateurs des langages fonctionnels optimisent les fonctions récursives terminales: au lieu de générer du code pour un appel de fonction "classique", qui remplirait la pile d'appel, ils transforment le code en quelque chose de proche d'une boucle while.
C'est pourquoi quand vous lirez du code fonctionnel écrit par un adepte de programmation fonctionnelle, vous trouverez souvent des fonctions récursives là où vous vous attendriez à voir une boucle while.
pause musicale: https://www.youtube.com/watch?v=-PX0BV9hGZY
Appel par adresse¶
Certaines fonctions prennent en paramètre des mutables et "écrivent dedans". Un exemple classique est la fonction qui incrémente un compteur.
let inc c = (* incrémente le compteur c*)
c := !c + 1
let c0 = ref 0
inc c0
!c0
Et en Python?
L'appel par adresse ne concerne pas les variables. Les tableaux, en revanche, sont passés par adresse.
c = 0
def inc(c) : c = c + 1
inc(c)
print(c) # -> 0
c = [0]
def inc(c) : c[0] = c[0] + 1
inc(c)
print(c[0]) # -> 1
Autre exemple: l'échange de valeurs dans un tableau
let swap tab i j =
let tmp = tab.(i) in
tab.(i) <- tab.(j);
tab.(j) <- tmp
let tab3 = [|0; 1; 2|]
swap tab3 1 2
tab3
Notion de clôture¶
Laissons un instant les références pour préciser un point sur les définitions de fonctions.
Le corps d'une fonction peut faire référence à des variables "globales": par exemple
let x = 0 (* une variable "globale" *)
let f = fun n -> x * n (* une fonction qui utilise la variable globale x *)
Que se passe-t-il si l'on redéfinit la variable globale x? La fonction f change-t-elle?
let x = 1
(* redéfinition de la variable x; l'ancienne définition est "masquée" *)
f 1 (* f 1 = x * 1 ... mais avec l'ancien x *)
On observe que le x utilisé par f n'est pas celui de la deuxième définition, mais celui de la première.
Essayons de reconstituer ce qu'il s'est passé:
- Lorsqu'on a défini
f, OCaml a sauvegardé le contexte de définitions dans lequel il faut évaluerx * n. - Lorsque, plus tard, on a appellé la fonction
f, on a restauré ce contexte de définitions.
C'est "comme si" on avait directement remplacé le x par sa valeur 0 au moment de la définition de f.
La variable f a pour valeur la fonction qui à n associe x * n dans le contexte de définitions où x=0.
La valeur de f est appellée une clôture : une clôture est donc constituée de trois parties
- un identifiant de variable pour décrire le paramètre de la fonction (ici
n) - une expression (ici
x * n) - un contexte de définitions (ici restreint à une seule définition,
x=0)
Clôtures et références¶
Revenons-en maintenant aux références, et leur utilisation combinée aux clôtures.
let suivant =
let n = ref 0 in
fun () -> n:= !n + 1 ; !n
for i=1 to 5 do print_int (suivant ()); print_newline() done
Notre fonction suivant ressemble beaucoup à celle de tout à l'heure, à une différence près: elle n'utilise plus de variable "globale" n. Désormais, la variable n est une variable locale. C'est le seul point d'entrée vers la référence. Il est donc impossible de lire ou modifier le contenu de la référence n autrement qu'en appelant suivant.
On dit que n est une variable statique (elle est "allouée statiquement"). Le mot-clé static permet de faire la même chose en C.
int suivant() {
static int n = 0; /* variable locale à durée de vie globale, initialisée en début de programme */
n++;
return n;
}
fun, function, ou let f x = ... ?¶
Nous avons vu plusieurs façons de définir des fonctions: récapitulons
let f1 x = x + 1
let f2 = function x -> x + 1
let f3 = fun x -> x + 1
En fait let f x1 .. xn = e est complètement équivalent à let f = fun x1 .. xn -> e.
Par ailleurs, function ... est un racourci pour fun x -> match x with .... On utilise donc le plus souvent function à la place d'un match/with.
En revanche, pour définir une fonction anonyme, on utilise plutôt fun. D'ailleurs, on ne peut pas écrire une fonction anonyme à plusieurs variables avec function.
fun x y -> x+y
function x y -> x+y
Références et polymorphisme¶
Avant de passer au dernier sujet de ce cours, évoquons un point un peu subtil sur le typage des références. Il s'agit plus de collecter quelques observations que d'expliquer les raisons profondes de cette subtilité.
On a déjà rencontré plusieurs valeurs polymorphes dont le type est paramétré par une ou plusieurs variables de type, par exemple
(fun x-> x):'a->'a[]:'a list.
Ces valeurs peuvent être utilisées dans différents contexte en instanciant de plusieurs façons la variable de type.
let f = fun x -> x
let nil = []
let _ = (f 1, f "toto", 1::nil, "toto"::nil)
Si l'on manipule ces valeurs au travers d'une référence, la variable de type se présente un peu différemment: ce n'est plus 'a mais '_weak
let f = ref (fun x -> x)
let nil = ref []
On parle ici de type monomorphe: les variables _weak ne peuvent pas être remplacées tantôt par int ou string comme ce serait le cas avec un type polymorphe.
La variable de type _weak désigne un type que l'inférence de type n'a pas encore réussi à déterminer.
C'est la première utilisation de la référence qui permettra de déterminer ce type, et on ne pourra plus le changer ensuite.
!f 1 (* j'utilise !f avec un entier: donc _weak1=int *)
let toto () = !f "toto" (* trop tard, !f est maintenant de type int -> int *)
Il faut avoir en tête que la fonction toto peut être appelée plus tard, en particulier après avoir effectué l'affectation f:= fun x -> x+1... Ce serait problématique de passer "toto" comme argument à fun x -> x+1.
Cet autre exemple illustre le problème d'une autre façon.
let liste = 1 :: !nil (* j'utilise nil comme une référence sur une liste d'entiers *)
nil := ['#']
(* je n'ai plus le droit de l'utiliser comme une référence
sur une liste de caractères *)
Plutôt normal, on n'a pas envie que liste devienne [1; '#'], ce serait une liste mal typée...
Résumons¶
On peut programmer de manière impérative en OCaml:
- on simule une variable "mutable" d'un programme impératif avec une référence
- on peut utiliser des boucles for et while
- on n'a pas besoin de return, il suffit de placer la valeur que l'on veut renvoyer à la fin de la suite d'instructions
- si on veut simuler un return pour interrompre une boucle, il faudra utiliser une exception (prochain cours)