On fait un corrigé commenté du TP (~15 à 20 minutes)
Au niveau le plus bas, un ordinateur est une machine impérative :
Pour calculer sur un ordinateur, il faut donc, à un moment, faire des effets de bords. Nous allons voir :
La notion la plus simple est la notion de référence représentée par le type 'a ref. Il s'agit d'une case mémoire modifiable dont le contenu est de type 'a. Les opérations sont :
let x = ref 42
let () =
Printf.printf "%d\n" !x; (* affiche 42 *)
x := !x + 1;
Printf.printf "%d\n" !x (* affiche 43 *)
On peut vouloir créer une fonction uid() qui renvoie un entier unique (ex: créer des noms de fichiers distincts, donner des IDs unique à des données, …)
let cpt = ref 0
let uid () =
let c = !cpt in
cpt := c + 1;
c
let x = uid () (* 0 *)
let y = uid () (* 1 *)
let z = uid () (* 2 *)
Quel problème potentiel avec cette fonction ?
La référence est accessible, du code erroné pourrait faire:
let () = cpt := 0 (* réinitialisation! le compteur n'est plus unique *)
Peut-on faire mieux ?
On peut utiliser un let in
let uid =
let cpt = ref 0 in
fun () -> let c = !cpt in
cpt := c + 1;
c
C'est un exemple simple de coopération entre programmation impérative (une référence) et fonctionnelle (on définit une fonction en plein milieu d'une expression, ici un let … in)
Attention, l'ordre d'évaluation en OCaml n'est spécifié que pour certaines expressions :
Dans tous les autres cas, l'ordre n'est pas spécifié !
let x = ref 0
let a, b = (!x, (x:= !x+1; !x)) (* a ? b ? *)
(* on suppose que l'on a encore jamais appelé uid() *)
let c = (uid ()) - (uid ()) (* 1 - 0 ou 0 - 1 ? *)
Ne jamais écrire un tel code ! Les résultats dépendent d'un ordre d'évaluation non spécifié, l'ordre peut changer selon les versions d'OCaml.
(* définition de type *)
type r = { l1: t1; …; ln : tn }
(* définition de valeur *)
let r = { l1 = e1; …; ln = en }
Dans la définition de type, on peut qualifier un champ de mutable pour dire qu'on peut le mettre à jour.
type point = { mutable x : float; mutable y : float }
let move p i j =
p.x <- p.x +. i;
p.y <- p.y +. j
let p = { x = 0.0; y = 0.0 }
let () = move p 1.0 2.0
let () = Printf.printf "%f, %f\n" p.x p.y (* 1.0, 2.0 *)
Les références ne sont qu'un cas particulier d'enregistrement mutable
type 'a ref = { mutable contents : 'a }
let ref x = { contents = x }
let x = ref 0 (* création d'une ref *)
let y = ref 0 (* création d'une autre ref *)
let z = x (* x et z sont la même ref *)
let () =
x := 1;
Printf.printf "%d, %d, %d\n" !x !y !z
(* affiche 1, 0, 1 *)
L'utilisation des structures mutable permet d'observer le partage des objets en mémoire, chose qu'on ne pouvait pas faire en prog. fonctionnelle pure.
Nous reviendrons sur cet aspect qui est source de bug.
OCaml possède un type pour les tableaux de taille fixe pour des éléments de type 'a
let tab = [| 1; 5; 42; -3 |]
let x = tab.(0)
let () =
tab.(0) <- x + 1;
Printf.printf "%d\n" tab.(0) (* affiche 2 *)
Comme pour les listes, les tableaux sont homogènes (on ne peut pas mélanger d'éléments de plusieurs types différents dans le même tableau)
Les fonctions sur les tableaux sont regroupées dans le module Array. Ce module regroupe
Tout ceux qu'on aime connaît :
La fonction de tri est :
Array.sort : ('a -> 'a -> int) -> 'a array -> unit
(* Tri en place, le tableau est modifié par le tri *)
C'est une différence significative d'API avec les listes, ici le tableau est modifié. Si on veut conserver le tableau original, il faut utiliser Array.copy
let tab = Array.make 3 [| 0; 0; 0 |] (* une "matrice" de taille 3x3 ? *)
let pr_tab t =
Array.iter (fun s ->
Array.iter (fun i -> Printf.printf "%d " i) s;
Printf.printf "\n") t
let () = tab.(0).(0) <- 42
let () = pr_tab tab
(*
42 0 0
42 0 0
42 0 0
C'est le même tableau interne qui est utilisé 3 fois !
On écrira plutôt :
*)
let tab2 = Array.init 3 (fun _ -> Array.make 3 0)
(* la fonction est rappelée pour chaque case, un nouveau tableau est alloué
à chaque fois *)
La boucle while est classique. On utilise les mots clés doet done pour délimiter le corp dela boucle:
let res = ref 0
let i = ref 0
let () =
while !i < 10 do
res := !res + i;
i := !i + 1
done
Comme la boucle doit utiliser une condition qui change (sinon c'est une boucle infinie), on doit utiliser des effets de bords pour modifier les valeurs testées (ici on modifie la référence i)
La boucle for permet d'aller d'une borne à une autre par pas de 1:
let () =
for i = 0 to 42 do
Printf.printf "%d\n" i;
done;
for j = 100 downto 0 do
Printf.printf "%d\n" j;
done
let average tab =
let total = ref 0.0 in
for i = 0 to Array.length tab - 1 do
total := !total +. tab.(i);
done;
!total /. (float (Array.length tab))
(* average: float array -> float *)
Le langage OCaml ne possède pas les mots clés break et continue. 😭
On peut les simuler grâce a des exceptions. 🤔
exception Break
exception Continue
let () =
try
for i in 0 to 100 do
try
... (* le code ici peut contenir raise Continue
ou raise Break *)
with Continue -> ()
done
with Break -> ()
C'est pour montrer que c'est possible, mais en pratique on utilise plutôt les itérateurs prédéfinis qui s'arrêtent au bon moment.
Le modèle mémoire d'un langage de programmation est la façon dont ce dernier représente ses valeurs en mémoire, i.e. comme des suites d'octets.
De ce point de vue, l'impact le plus grand pour langage est la présence d'un GC ou garbage collector.
Le garbage collector (ou GC) est un "sous-programme" dont le rôle est de désallouer automatiquement la mémoire allouée. Exemple :
Pourquoi le GC a-t'il un impact ?
Comment le GC détecte-t'il qu'un objet peut être désalloué ?
Il doit stocker avec chaque objet de l'information supplémentaire. La nature de cette information à un impact sur le modèle mémoire.
OCaml distingue 2 sortes de valeurs à l'exécution
Ainsi, toutes les valeurs OCaml sont représentées de façon uniforme, un mot mémoire de 64 bits qui est soit un entier soit un pointeur.
Comment désallouer ?
Exemple, let x = (41, 42). La variable x contient un pointeur vers un bloc de taille 3 * 64 bits = 3* 8 octets = 24 octets.
Le GC parcours l'ensemble des valeurs pendant l'exécution du programme (en « parallèle »).
Il commence son parcours depuis les variables globales et la pile d'appel courante (variable locale visible)
Si le GC rencontre un pointeur, il va voir le bloc correspondant, et met un 1 dans les 2 bits réservés. Puis il parcours les blocs suivants et suis les pointeurs ≡ parcours du graphe des pointeurs.
Après le parcours, on re-parcourt une nouvelle fois. Toutes les valeurs marquées sont gardées (et la marque remise à 0), les autres sont désallouées.
Cette technique est appelée Mark and Sweep.
Problème, quand le GC voit la valeur « 42 » dans un bloc, est-ce qu'il s'agit de l'entier 42 (on ne fait rien) ou est-ce qu'il s'agit du pointeur vers l'adresse 42 (et il faut suivre ce pointeur).
Solution: Les entiers sont marqués en décalant à gauche de 1 bit mettant leur bit de poids faible à 1.
Ça marche car les adresses mémoires vers des blocs de 8 octets sont toujours des multiples de 8 donc pairs.
Donc: si on voit un nombre pair, c'est un pointeur on le suit
Si on
voit un nombre impair, on le divise par 2 et on obtient la valeur avec
laquelle on peut calculer.
On voit donc la différence qu'il y a entre « être structurellement égal » et être identique (pointer vers le même bloc)
Les trie on la propriété que si deux sous-arbres sont structurellement égaux, on peut les remplacer par le même pointeur.
On verra la prochaine fois comment utiliser cela pour rendre du code plus efficace