Les pointeurs en Caml

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:

/* Le type des cellules et des listes */
struct cellule {
  int hd;
  struct cellule *tl;
};

typedef struct cellule cellule, *liste;

Ce qui se traduit en Caml par une définition de type somme sans pointeurs:

type liste = | Nil | Cons of int * liste;;

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:

/* La liste vide */
#define nil NULL

/* Le constructeur de listes */
liste cons (element x, liste l)
{
  liste result;
  result = (liste) malloc (sizeof (cellule));
  result -> hd = x;
  result -> tl = l;
  return (result);
}

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 liste = | Nil | Cons of cellule
and cellule = {mutable hd : int; tl : liste};;

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 liste = | Nil | Cons of cellule
and cellule = {mutable hd : int; mutable tl : liste};;

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)

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 prefix !^ = function
 | Null -> invalid_arg "Attempt to dereference the null pointer"
 | Pointer r -> !r;;
!^ : 'a pointer -> 'a = <fun>

let prefix ^:= p v =
 match p with
 | Null -> invalid_arg "Attempt to assign the null pointer"
 | Pointer r -> r := v;;
^:= : 'a pointer -> 'a -> unit = <fun>

On définit aussi l'allocation d'un nouveau pointeur vers une valeur donnée:

let new_pointer x = Pointer (ref x);;
new_pointer : 'a -> 'a pointer = <fun>

Un exemple: un pointeur vers un entier.

#let p = new_pointer 0;;
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:

(* Le type des listes ``à 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};;
new_cell : unit -> cell = <fun>

let cons x l =
 let c = new_cell () in
 c.hd <- x;
 c.tl <- l;
 (new_pointer c : ilist);;
cons : int -> ilist -> ilist = <fun>

let hd (l : ilist) = !^l.hd;;
hd : ilist -> int = <fun>
let tl (l : ilist) = !^l.tl;;
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:

(* L'append physique *)
let append (l1 : ilist) (l2 : ilist) =
 let temp = ref l1 in
 while tl !temp <> Null do
  temp := tl !temp
 done;
 !^ !temp.tl <- l2;;
append : ilist -> ilist -> unit = <fun>

(* Un exemple: *)
let l1 = cons 1 (cons 2 Null);;
l1 : ilist = Pointer (ref {hd = 1; tl = Pointer (ref {hd = 2; tl = Null})})

let l2 = cons 3 Null;;
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 polymorphes

type 'a lists == 'a cell pointer
and 'a cell = {mutable hd : 'a pointer; mutable tl : 'a lists};;

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