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 *)
val tab : int array = [|1; 2; 3|]
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 '#'*)
val tab2 : char array =
[|'#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#';
'#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#';
'#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'; '#';
'#'; '#'; '#'; '#'; '#'; '#'; '#'; '#'|]
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 *)
- : int array = [|0; 1; 4; 9; 16; 25; 36; 49; 64; 81|]
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 *)
- : int = 2
tab.(-1)
Exception: Invalid_argument "index out of bounds".
Raised by primitive operation at unknown location
Called from file "toplevel/toploop.ml", line 208, characters 17-27
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! *)
- : unit = ()
tab (* le contenu de tab a changé de manière irréversible. *)
- : int array = [|0; 2; 3|]
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 *)
}
type etat_civil = { date_naissance : int; mutable date_deces : int option; }
let christ = {date_naissance= -33; date_deces = Some(0)}
val christ : etat_civil = {date_naissance = -33; date_deces = Some 0}
christ.date_deces <- None
- : unit = ()
christ
- : etat_civil = {date_naissance = -33; date_deces = None}
Si le champs n'a pas été déclaré mutable, pas le droit d'y toucher
christ.date_naissance <- -34
File "[13]", line 1, characters 0-28:
1 | christ.date_naissance <- -34
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: The record field date_naissance is not mutable
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} *)
val r : int ref = {contents = 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"
File "[15]", line 1, characters 7-9:
1 | if r = 42 then print_string "r = 42" else print_string "r <> 42"
^^
Error: This expression has type int but an expression was expected of type
int ref
À 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
val r2 : int ref = {contents = 42}
r == r2 (* r et r2 sont deux "boites" différentes *)
- : bool = false
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 *)
- : int = 42
!r = !r2
- : bool = true
Pour modifier la valeur contenue dans une référence, on utilise l'opérateur infixe (:=).
r := 43
- : unit = ()
r
- : int ref = {contents = 43}
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
- : int ref = {contents = 42}
!r = !r2
- : bool = false
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 *)
val r' : int ref = {contents = 43}
r == r' (* les variables r et r' désignent la même adresse mémoire *)
- : bool = true
r := 44 (* modifie la valeur à l'adresse égale à la valeur de r ... *)
- : unit = ()
!r' (* ... qui était aussi l'adresse égale à la valeur de r' *)
- : int = 44
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
hello
val x : int = 3
La valeur de x est 3, mais pendant son calcul, OCaml a affiché hello.
let compteur = ref 0
val compteur : int ref = {contents = 0}
let suivant () = compteur := !compteur + 1 ; !compteur
val suivant : unit -> int = <fun>
let x1 = suivant () in let x2 = suivant () in let x3 = suivant () in
(x1, x2, x3)
- : int * int * int = (1, 2, 3)
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 *)
File "[32]", line 1, characters 0-5:
1 | 2 + 1 ; 3 + 2
^^^^^
Warning 10: this expression should have type unit.
File "[32]", line 1, characters 0-5:
1 | 2 + 1 ; 3 + 2
^^^^^
Warning 10: this expression should have type unit.
- : int = 5
let () = 2+1 in 3+2
File "[33]", line 1, characters 4-6:
1 | let () = 2+1 in 3+2
^^
Error: This pattern matches values of type unit
but a pattern was expected which matches values of type int
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
val x : int = 3
File "[85]", line 1, characters 30-43:
1 | let x = print_string "hello"; print_newline; 3
^^^^^^^^^^^^^
Warning 10: this expression should have type unit.
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 *)
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 *)
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 *)
val tab5 : int array = [|0; 0; 0; 0; 0|]
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()
01234
- : unit = ()
for i=4 downto 0 do begin
print_int i
end done;
print_newline()
43210
- : unit = ()
let i = ref 0
val i : int ref = {contents = 0}
while !i < 5 do print_int !i; i := !i + 1 done;
print_newline()
01234
- : unit = ()
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 ; *)
val somme : (int -> int) -> int -> int = <fun>
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
val somme : (int -> int) -> int -> int = <fun>
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
val somme : (int -> int) -> int -> int = <fun>
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
$$ \begin{array}{ll} & \mathsf{somme}(\mathsf{id},3)\\ = & \mathsf{somme}\_\mathsf{depuis}(0,0) \\ = & \mathsf{somme}\_\mathsf{depuis}(1,0+\mathsf{id}(0)) \\ = & \mathsf{somme}\_\mathsf{depuis}(1,0)\\ = & \mathsf{somme}\_\mathsf{depuis}(2,0+\mathsf{id}(1)) \\ = & \mathsf{somme}\_\mathsf{depuis}(2,1)\\ = & \mathsf{somme}\_\mathsf{depuis}(3,1+\mathsf{id}(2)) \\ = & \mathsf{somme}\_\mathsf{depuis}(3,3)\\ = & 3 \end{array} $$
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
val inc : int ref -> unit = <fun>
let c0 = ref 0
val c0 : int ref = {contents = 0}
inc c0
- : unit = ()
!c0
- : int = 1
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
val swap : 'a array -> int -> int -> unit = <fun>
let tab3 = [|0; 1; 2|]
val tab3 : int array = [|0; 1; 2|]
swap tab3 1 2
- : unit = ()
tab3
- : int array = [|0; 2; 1|]
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 *)
val x : int = 0
val f : int -> int = <fun>
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" *)
val x : int = 1
f 1 (* f 1 = x * 1 ... mais avec l'ancien x *)
- : int = 0
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 next =
let n = ref 0 in
fun () -> n:= !n + 1 ; !n
for i=1 to 5 do print_int (next ()); print_newline() done
1 2 3 4 5
- : unit = ()
Notre fonction next ressemble beaucoup à
la fonction suivant vue tout à l'heure:
let compteur = ref 0
let suivant () = compteur:= !compteur + 1; !compteur
let next =
let n = ref 0 in
fun () -> n:= !n + 1; !n
La différence entre suivant et next est la suivante: suivant utilise une variable "globale" (avec des guillements) compteur que tout le monde peut modifier, tandis que next utilise une variable n "locale" et surtout "privée": il est impossible de lire ou modifier le contenu de la référence n autrement qu'en appelant next.
Le mot-clé static permet de faire quelque chose d'un peu similaire en C (une variable "à portée locale" mais à durée de vie "globale", qui "survit" aux appels de fonction).
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
val f1 : int -> int = <fun>
val f2 : int -> int = <fun>
val f3 : int -> int = <fun>
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
- : int -> int -> int = <fun>
function x y -> x+y
File "[61]", line 1, characters 11-12:
1 | function x y -> x+y
^
Error: Syntax error
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)
val f : 'a -> 'a = <fun>
val nil : 'a list = []
- : int * string * int list * string list = (1, "toto", [1], ["toto"])
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 []
val f : ('_weak1 -> '_weak1) ref = {contents = <fun>}
val nil : '_weak2 list ref = {contents = []}
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 *)
- : int = 1
let toto () = !f "toto" (* trop tard, !f est maintenant de type int -> int *)
File "[65]", line 1, characters 17-23:
1 | let toto () = !f "toto" (* trop tard, !f est maintenant de type int -> int *)
^^^^^^
Error: This expression has type string but an expression was expected of type
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 *)
val liste : int list = [1]
nil := ['#']
(* je n'ai plus le droit de l'utiliser comme une référence
sur une liste de caractères *)
File "[67]", line 1, characters 8-11:
1 | nil := ['#'] (* je n'ai plus le droit de l'utiliser comme une référence sur une liste de caractères *)
^^^
Error: This expression has type char but an expression was expected of type
int
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)