English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Les pointeurs en Caml

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;;