Le statut des pointeurs en Caml
Les pointeurs existent en Caml, ils sont même omni-présents.
On les utilise soit implicitement (la plupart des usages), soit
explicitement (pour les rares cas où les pointeurs implicites
sont moins pratiques). Dans la grande majorité des usages
habituels des pointeurs, le programmeur Caml n'a pas à se soucier
des pointeurs car ils sont automatiquement insérés et gérés par
le compilateur.
Par exemple pour les listes ou les arbres vous décrivez ces
structures de données sans avoir besoin des pointeurs explicites,
par une définition de type somme en Caml. L'implémentation
sous-jacente est faite à l'aide de pointeurs, mais cette gestion
est automatique et entièrement prise en charge par le
compilateur.
Pour les rares cas où l'on a besoin de pointeurs explicites (la plupart du temps, c'est pour traduire un algorithme déjà écrit dans un langage impératif classique), on dispose des références qui sont d'ailleurs des pointeurs de première classe (on peut les passer en argument, les mettre dans les structures de données, les retourner en résultat).
Les pointeurs explicites sont les valeurs Caml du type
ref
Vous pouvez donc tout faire à coup de références si vous le désirez, mais encore une fois ce n'est la plupart du temps pas nécessaire.
Prenons l'exemple des listes chaînées (listes d'entiers pour simplifier). Ce type de données est défini en C (ou en Pascal) avec des pointeurs, par exemple:
/* Cells and lists type in C */
struct cell {
int hd;
struct cell *tl;
};
typedef struct cell cell, *list;
{Cells and lists type in Pascal}
type
list = ^cell;
cell = record
hd: integer;
tl: cell;
end;
Ce qui se traduit en Caml par une définition de type somme sans pointeurs:
type list = Nil | Cons of int * list;;
Les cellules de listes sont donc représentées en Caml par une
paire, et la structure récursive des listes est mise en évidence,
avec les deux cas, liste vide (constructeur Nil) et
liste non vide (constructeur Cons).
La gestion automatique des pointeurs et de l'allocation en Caml,
se traduit aussi par le fait que la fonction de construction des
cellules de listes est fournie par la définition du type: on
écrit simplement Cons (x, l) pour ajouter
x en tête de la liste l. En C, il faut
écrire cette fonction, allouer une nouvelle cellule, puis en
remplir les champs soi-même. Par exemple :
/* The empty list */
#define nil NULL
/* The constructor of lists */
list cons (element x, list l)
{
list result;
result = (list) malloc (sizeof (cellule));
result -> hd = x;
result -> tl = l;
return (result);
}
De même, en Pascal :
{Creating a list cell}
function cons (x: integer; l: list): list;
var p: list;
begin
new(p);
p^.hd := x;
p^.tl := l;
cons := p
end;
On constate ainsi qu'en C il est indispensable que les cellules de listes aient des champs physiquement modifiables, sous peine de ne pas pouvoir les initialiser. En revanche en Caml, l'allocation et l'initialisation sont confondues en une seule opération, l'application du constructeur. Cela permet de définir des structures de données non mutables. Si les modifications physiques sont cependant nécessaires pour d'autres raisons que la simple initialisation des données, on utilise alors en Caml des enregistrements à champs mutables. Par exemple, un type liste dont les éléments sont modifiables serait :
type list = Nil | Cons of cell
and cell = { mutable hd : int; tl : list };;
Si l'on veut aussi pouvoir modifier la structure de la liste
elle-même (supprimer physiquement des cellules), on rendra le
champ tl mutable:
type list = | Nil | Cons of cell
and cell = {mutable hd : int; mutable tl : list};;
Les modifications physiques restent cependant inutiles pour
l'allocation des données: on écrit Cons {hd = 1; tl =
l} pour ajouter 1 à la liste l.
Les modifications physiques qui subsistent dans les programmes
sont celles qui sont strictement indispensables à la logique de
l'algorithme implémenté.
Pointeurs et champs mutables ou vecteurs
Très souvent l'usage de pointeurs sert à implémenter la modification physique de structures de données. Cela se traduit en Caml par l'utilisation de vecteurs ou de champs mutables dans les enregistrements. Dans ce type d'usages, l'instruction Pascal :
x^.label := val (où x
est une valeur d'un enregistrement comportant le champ
label)
correspond en Caml à
x.label <- val (où x est une valeur
d'un enregistrement comportant le champ label
mutable). Le ^ de Pascal a disparu car le
déréférencement est géré automatiquement par le compilateur
Caml.
En conclusion: Vous pouvez travailler en Caml avec des pointeurs explicites, exactement comme en Pascal ou C, mais ce n'est pas naturel, et l'on retrouve alors les difficultés de manipulation des pointeurs des langages classiques. Voyez l'exemple complet ci-dessous.
Définition des pointeurs en Caml
Le type général des pointeurs: un pointeur est soit le pointeur nul, soit un pointeur vers une zone de mémoire affectable :
type 'a pointer = Null | Pointer of 'a ref;;
On définit sans difficulté le déréférencement (c'est-à-dire
l'accès à la valeur pointée) et l'affectation du pointeur
(c'est-à-dire l'écriture de la zone pointée, ou le changement de
la valeur pointée). On définit ici le déréférencement comme
l'opérateur préfixe !^, et l'affectation comme
l'opérateur infixe ^:=.
let ( !^ ) = function | Null -> invalid_arg "Attempt to dereference the null pointer" | Pointer r -> !r;; val ( !^ ) : 'a pointer -> 'a = <fun> let ( ^:= ) p v = match p with | Null -> invalid_arg "Attempt to assign the null pointer" | Pointer r -> r := v;; val ( ^:= ) : 'a pointer -> 'a -> unit = <fun>
(L'exemple ci-dessus est donné dans la syntaxe d'OCaml.
Pour Caml Light, écrivez
let prefix !^ = ... et let prefix ^:= = ... à la place de let ( !^ ) = ... et let ( ^:= ) = ....)
On définit aussi l'allocation d'un nouveau pointeur vers une valeur donnée :
let new_pointer x = Pointer (ref x);;
val new_pointer : 'a -> 'a pointer = <fun>
Un exemple: un pointeur vers un entier.
let p = new_pointer 0;; val p : int pointer = Pointer (ref 0) p^:=1;; - : unit = () !^p;; - : int = 1
Listes d'entiers
On peut définir maintenant le type des listes avec des pointeurs, comme dans les langages traditionnels, en Pascal ou C :
(* The list type ``à la Pascal'' *)
type ilist = cell pointer
and cell = {mutable hd : int; mutable tl : ilist};;
On définit alors l'allocation d'une nouvelle cellule, le constructeur des listes et les destructeurs associés.
let new_cell () = {hd = 0; tl = Null};;
val new_cell : unit -> cell = <fun>;
let cons x l =
let c = new_cell () in
c.hd <- x;
c.tl <- l;
(new_pointer c : ilist);;
val cons : int -> ilist -> ilist = <fun>
let hd (l : ilist) = !^l.hd;;
val hd : ilist -> int = <fun>
let tl (l : ilist) = !^l.tl;;
val tl : ilist -> ilist = <fun>
On retrouve alors tous les algorithmes classiques à base de manipulations de pointeurs, avec leurs boucles, leurs problèmes de partage insoupçonnés et de déréférencement du pointeur nul. Par exemple, la concaténation des listes décrite dans la littérature, qui accroche physiquement la seconde liste au bout de la première :
(* Physical append *)
let append (l1 : ilist) (l2 : ilist) =
let temp = ref l1 in
while tl !temp <> Null do
temp := tl !temp
done;
!^ !temp.tl <- l2;;
val append : ilist -> ilist -> unit = <fun>
(* An example: *) let l1 = cons 1 (cons 2 Null);; val l1 : ilist = Pointer (ref {hd = 1; tl = Pointer (ref {hd = 2; tl = Null})}) let l2 = cons 3 Null;; val l2 : ilist = Pointer (ref {hd = 3; tl = Null}) append l1 l2;; - : unit = ()
Les listes l1 et l2 sont
effectivement concaténées:
l1;; - : ilist = Pointer (ref {hd = 1; tl = Pointer (ref {hd = 2; tl = Pointer (ref {hd = 3; tl = Null})})})
Seul petit problème: la liste l1 contient
maintenant la concaténation des deux listes l1 et
l2, si bien que la liste l1 a disparu:
en quelque sorte la fonction append
consomme son premier argument. En d'autres termes, la
valeur d'une donnée dépend maintenant de son histoire,
c'est-à-dire de la suite des appels de fonctions auxquels elle a
participé. C'est ce comportement étrange qui rend la manipulation
explicite de pointeurs très difficile. Essayez par exemple :
append l1 l1;;
- : unit = ()
Puis évaluez l1 :
l1;;
Listes polymorpes
Pour aller au-delà de Pascal, il faut définir avec les pointeurs des listes polymorphes :
type 'a list = 'a cell pointer
and 'a cell = {mutable hd : 'a pointer; mutable tl : 'a list};;
let new_cell () = {hd = Null; tl = Null};;
let cons x l =
let c = new_cell () in
c.hd <- new_pointer x;
c.tl <- l;
(new_pointer c : 'a lists);;
let hd (l : 'a lists) = !^l.hd;;
let tl (l : 'a lists) = !^l.tl;;
let append (l1 : 'a lists) (l2 : 'a lists) =
let temp = ref l1 in
while tl !temp <> Null do
temp := tl !temp
done;
!^ !temp.tl <- l2;;